#include "axislayout.h"

//------------------------------------------------------------------------
// Tell the sum of weights for a given layout
//------------------------------------------------------------------------
int getFitness(int numAxes, int* layout, graph* g) {
  int i, v1,v2, fitness=0;
  for(i=1;i<numAxes;i++) {
     //printf("  %d,",layout[i-1]);
     v1=layout[i]; v2=layout[i-1];
     if(v1<v2) SWAP(v1,v2);
     if( (v1!=v2) && (g->mat2d[v1][v2]!=INAN)) {
       fitness += g->mat2d[v1][v2];
       //fprintf(stderr,"%d %d=%d\n",v1,v2,g->mat2d[v1][v2]);
     }
  }
  //printf("  %d = %d\n",layout[numAxes-1],fitness);
  return fitness;
}

int getFitnessMultiFile(int numAxes, int* layout, graph** sg) {
  int i, v1,v2, fitness=0;
  for(i=1;i<numAxes;i++) {
     //printf("  %d,",layout[i-1]);
     v1=layout[i]; v2=layout[i-1];
     if(v1<v2) SWAP(v1,v2);
     if( (v1!=v2) && (sg[i-1]->mat2d[v1][v2]!=INAN)) {
       fitness += sg[i-1]->mat2d[v1][v2];
       //fprintf(stderr,"%d %d=%d\n",v1,v2,weight);
     }
  }
  //printf("  %d = %d\n",layout[numAxes-1],fitness);
  return fitness;
}

int getMaxCell(graph* g, int* maxX, int* maxY) {
  int i,j;
  short int val, max;

  //--Get the numAxes best pairs
  *maxX=*maxY=-1;
  max=SHRT_MIN;

  for(i=0;i<g->numVerts;i++) {
    for(j=0;j<i;j++) {

      //See if this is a new max
      val = g->mat2d[i][j];
      if (val!=INAN) {
        if(max<val) {
          max=val;
          *maxX = j;
          *maxY = i;
        }
      }

   }
  }//end O(V^2)

  return 0;
}

int* getBestByMaxChain(int numAxes, graph* g, int sX, int sY, int allowRepeats) {
  int i,k;
  int axis,alreadyGotten;
  int *layout;
  short int val, max;

  layout=(int*)malloc(numAxes*sizeof(int));
  if(layout==NULL) {
    perror("axislayout.c: getBestByMaxChain() layout"); return NULL;
  }
  for(i=0;i<numAxes;i++) layout[i]=-1;

  //--Seed values to start the greedy search
  layout[0]=sX;
  layout[1]=sY;

  //--Get the numAxes best pairs
  for(axis=2; axis<numAxes; axis++) {
    max=SHRT_MIN;

	  for(i=0;i<g->numVerts;i++) {

      //See if we already have this location as a max
      alreadyGotten=0;
      if(allowRepeats==1) {
        for(k=2;k<axis;k++) {
          if(i==layout[k-2] || i==layout[k-1]) {
            alreadyGotten=1;
            break;
          }
        }
      }
      else {
        for(k=0;k<axis;k++) {
          if(i==layout[k]) {
            alreadyGotten=1;
            break;
          }
        }
      }

      //See if this is a new max
      if(layout[axis-1]>i) val = g->mat2d[layout[axis-1]][i];
      else val = g->mat2d[i][layout[axis-1]];
      if (val!=INAN && alreadyGotten==0) {
        if(max<val) {
          max=val;
          layout[axis]=i;
        }
      }

	  }//end O(V)

  }//end O(kV)

  printf("Best pairs found by greedy are:\n");
  for(i=0;i<numAxes-1;i++) {
    printf("  (%d,%d)=%d,",layout[i],layout[i+1],
      layout[i+1]>layout[i]?g->mat2d[layout[i+1]][layout[i]]:g->mat2d[layout[i]][layout[i+1]]);
  }
  printf("\n");

  return layout;
}

int getBestPairs(int numAxes, graph* g, int** targetX, int** targetY, int allowRepeats) {
  int i,j,k;
  int axis,alreadyGotten;
  int *tarX, *tarY;
  short int val, max;

  tarX=(int*)malloc(numAxes*sizeof(int));
  if(tarX==NULL) {
    perror("axislayout.c: getBestPairs() tarX"); return -1;
  }
  tarY=(int*)malloc(numAxes*sizeof(int));
  if(tarY==NULL) {
    perror("axislayout.c: getBestPairs() tarY"); return -1;
  }
  for(i=0;i<numAxes;i++) tarX[i]=tarY[i]=-1;

  //--Get the numAxes best pairs
  for(axis=0; axis<numAxes; axis++) {
    max=SHRT_MIN;

	  for(i=0;i<g->numVerts;i++) {
		  for(j=0;j<i;j++) {

        //See if we already have this location as a max
        alreadyGotten=0;
        for(k=0;k<axis;k++) {
          if(allowRepeats==1) {
            if(i==tarY[k] && j==tarX[k]) {
              alreadyGotten=1;
              break;
            }
          }
          else {
            if(i==tarY[k] || j==tarX[k] || i==tarX[k] || j==tarY[k]) {
              alreadyGotten=1;
              break;
            }
          }
        }

        //See if this is a new max
        val = g->mat2d[i][j];
			  if (val!=INAN && alreadyGotten==0) {
             if(max<val) {
               max=val;
               tarX[axis] = j;
               tarY[axis] = i;
             }
			  }

      }
	  }//end O(V^2)

  }//end best pairs

  *targetX = tarX;
  *targetY = tarY;
  return 0;
}

int getWorstPairs(int numAxes, graph* g, int** targetX, int** targetY, int allowRepeats) {
  int i,j,k;
  int axis,alreadyGotten;
  int *tarX, *tarY;
  short int val, min;

  tarX=(int*)malloc((numAxes)*sizeof(int));
  if(tarX==NULL) {
    perror("axislayout.c: getWorstPairs() tarX"); return -1;
  }
  tarY=(int*)malloc((numAxes)*sizeof(int));
  if(tarY==NULL) {
    perror("axislayout.c: getWorstPairs() tarY"); return -1;
  }
  for(i=0;i<numAxes;i++) tarX[i]=tarY[i]=-1;

  //--Get the numAxes best pairs
  for(axis=0; axis<numAxes; axis++) {
    min=SHRT_MAX;

	  for(i=0;i<g->numVerts;i++) {
		  for(j=0;j<i;j++) {

        //See if we already have this location as a min
        alreadyGotten=0;
        for(k=0;k<axis;k++) {
          if(allowRepeats==1) {
            if(i==tarY[k] && j==tarX[k]) {
              alreadyGotten=1;
              break;
            }
          }
          else {
            if(i==tarY[k] || j==tarX[k] || i==tarX[k] || j==tarY[k]) {
              alreadyGotten=1;
              break;
            }
          }
        }

        //See if this is a new min
        val = g->mat2d[i][j];
			  if (val!=INAN && alreadyGotten==0) {
             if(min>val) {
               min=val;
               tarX[axis] = j;
               tarY[axis] = i;
             }
			  }

      }
	  }//end O(V^2)

  }//end best pairs

  *targetX = tarX;
  *targetY = tarY;
  return 0;
}

// NOTICE:  Copyright 1991-2008, Phillip Paul Fuchs
void display(int num, int *a, int j, int i) {
   int x;
   for(x=0; x<num; x++) printf("  %d,",a[x]);
   printf("   swapped(%d, %d)\n", j, i);
   //getch();  // press any key to continue...
}
int* QuickPermPair(int num, int* tarX, int* tarY, graph* g) {
   int *a, *p;
   int i, j, k, max, fitness, tmp; // Upper Index i; Lower Index j
   int *layout, *bestLayout;

   a = (int*)malloc(num*sizeof(int));
   p = (int*)malloc((num+1)*sizeof(int));
   if(a==NULL || p==NULL) {
      perror("QuickPermPair(): a/p");
      return NULL;
   }

   bestLayout = (int*)malloc((num+1)*sizeof(int));
   if(bestLayout==NULL) {
      perror("QuickPermPair(): bestLayout");
      free(a); free(p);
      return NULL;
   }

   //Get fitness for the default layout
   layout = (int*)malloc((num+1)*sizeof(int));
   if(layout==NULL) {
      perror("QuickPermPair(): layout");
      free(a); free(p);
      free(bestLayout);
      return NULL;
   }
   for(k=0;k<num+1;k++) {
     if(k%2==0) layout[k] = tarX[k/2];
     else layout[k] = tarY[k/2];
   }
   max=getFitness(num+1,layout,g);
   memcpy(bestLayout,layout,(num+1)*sizeof(int));

   //Start permutations
   for(i=0; i<num; i++) {  // initialize arrays; a[num] can be any type
      a[i] = i;            // a[i] value is not revealed and can be arbitrary
      p[i] = i;
   }
   p[num] = num; // p[N] > 0 controls iteration and the index boundary for i
   //display(a, 0, 0);   // remove comment to display array a[]
   i = 1;   // setup first swap points to be 1 and 0 respectively (i & j)
   while(i < num) {
      p[i]--;             // decrease index "weight" for i by one
      j = i % 2 * p[i];   // IF i is odd then j = p[i] otherwise j = 0
      tmp = a[j];         // swap(a[j], a[i])
      a[j] = a[i];
      a[i] = tmp;

      //display(num, a, j, i); // remove comment to display target array a[]
      //See if this permutation is the best one so far
      for(k=0;k<(num+1)/2;k++) {
        layout[2*k] = tarX[a[k]];
        layout[2*k+1] = tarY[a[k]];
      }
      if( (num+1)%2 == 1) {
        layout[num] = tarX[a[(num+1)/2]];
      }
      fitness=getFitness(num+1,layout,g);
      if(fitness>max) {
         max = fitness;
         memcpy(bestLayout,layout,(num+1)*sizeof(int));
      }

      i = 1;              // reset index i to 1 (assumed)
      while (!p[i]) {     // while (p[i] == 0)
         p[i] = i;        // reset p[i] zero value
         i++;             // set new index value for i (increase by one)
      } // while(!p[i])
   } // while(i < num)

   free(a);
   free(p);
   return bestLayout;
} // QuickPermPair()

int* QuickPerm(int num, int* list, graph* g) {
   int *a, *p;
   int i, j, k, max, fitness, tmp; // Upper Index i; Lower Index j
   int *layout, *bestLayout;

   a = (int*)malloc(num*sizeof(int));
   p = (int*)malloc((num+1)*sizeof(int));
   if(a==NULL || p==NULL) {
      perror("QuickPerm(): a/p");
      return NULL;
   }

   bestLayout = (int*)malloc((num+1)*sizeof(int));
   if(bestLayout==NULL) {
      perror("QuickPerm(): bestLayout");
      free(a); free(p);
      return NULL;
   }

   //Get fitness for the default layout
   layout = (int*)malloc((num+1)*sizeof(int));
   if(layout==NULL) {
      perror("QuickPerm(): layout");
      free(a); free(p);
      free(bestLayout);
      return NULL;
   }
   for(k=0;k<num+1;k++) {
     layout[k]=list[k];
   }
   max=getFitness(num+1,layout,g);
   memcpy(bestLayout,layout,(num+1)*sizeof(int));

   //Start permutations
   for(i=0; i<num; i++) {  // initialize arrays; a[num] can be any type
      a[i] = i;            // a[i] value is not revealed and can be arbitrary
      p[i] = i;
   }
   p[num] = num; // p[N] > 0 controls iteration and the index boundary for i
   //display(a, 0, 0);   // remove comment to display array a[]
   i = 1;   // setup first swap points to be 1 and 0 respectively (i & j)
   while(i < num) {
      p[i]--;             // decrease index "weight" for i by one
      j = i % 2 * p[i];   // IF i is odd then j = p[i] otherwise j = 0
      tmp = a[j];         // swap(a[j], a[i])
      a[j] = a[i];
      a[i] = tmp;

      //display(num, a, j, i); // remove comment to display target array a[]
      //See if this permutation is the best one so far
      for(k=0;k<num+1;k++) {
        layout[k] = list[a[k]];
      }
      fitness=getFitness(num+1,layout,g);
      if(fitness>max) {
         max = fitness;
         memcpy(bestLayout,layout,(num+1)*sizeof(int));
      }

      i = 1;              // reset index i to 1 (assumed)
      while (!p[i]) {     // while (p[i] == 0)
         p[i] = i;        // reset p[i] zero value
         i++;             // set new index value for i (increase by one)
      } // while(!p[i])
   } // while(i < num)

   free(a);
   free(p);
   free(layout);
   return bestLayout;
} // QuickPerm()

int choose(int n, int k) {
  int i,j,inci;
  int* l;

  if(k>n) return -1;

  l=(int*)malloc(k*sizeof(int));
  if(l==NULL) {
    fprintf(stderr,"Error: choose() l\n");
    return -1;
  }
  for(i=0;i<k;i++) l[i]=i;

  for(i=0;i<k;i++) printf("\t%d",l[i]);
  printf("\n");

  while (l[0] < n-k) {
    inci = k-1;
    while (l[inci] >= n-k+inci) inci--;
    l[inci]++;
    for (j=inci+1;j<k;j++) l[j] = l[inci]+j-inci;
    
    for(i=0;i<k;i++) printf("\t%d",l[i]);
    printf("\n");
  }
  return 0;
}

int* chooseAxes(int n, int k, graph* g) {
  int i,j,inci, max,fitness;
  int *l,*layout,*bestLayout;
  clock_t oldTime;

  if(k>n) return NULL;

  l=(int*)malloc(k*sizeof(int));
  if(l==NULL) {
    fprintf(stderr,"chooseAxes(): l\n");
    return NULL;
  }
  for(i=0;i<k;i++) l[i]=i;

  bestLayout = (int*)malloc(k*sizeof(int));
  if(bestLayout==NULL) {
     fprintf(stderr,"chooseAxes(): bestLayout");
     free(l);
     return NULL;
  }

  //for(i=0;i<k;i++) printf("\t%d",l[i]);
  //printf("\n");
  //Get fitness for the default layout
  layout=QuickPerm(k,l,g);
  fitness=getFitness(k,layout,g);
  max=getFitness(k,layout,g);
  memcpy(bestLayout,layout,k*sizeof(int));

  oldTime=clock();
  while (l[0] < n-k) {
    inci = k-1;
    while (l[inci] >= n-k+inci) inci--;
    l[inci]++;
    for (j=inci+1;j<k;j++) l[j] = l[inci]+j-inci;
    
    //TEST
    //if(l[0]==1) printf(" QuickPerm for one iteration of (n,k) takes = %dms\n",k,1000.f*(clock()-oldTime)/CLOCKS_PER_SEC);
    free(layout);
    layout=QuickPerm(k,l,g);
    fitness=getFitness(k,layout,g);
    if(fitness>max) {
      max = fitness;
      memcpy(bestLayout,layout,k*sizeof(int));
      //printf("Found better solution (%d) - %d %d %d %d %d %d %d\n",max,l[0],l[1],l[2],l[3],l[4],l[5],l[6]);
    }

  }
  free(l);
  return bestLayout;
}

//------------------------------------------------------------------------
// Creates a layout of axes that's near optimal by picking out the
// highest-valued pair and then greedily creating a layout which optimizes
// the total edge weight of consecutive axes connected to the last.
// O(|V|^2 + |V|*(k-2))
//------------------------------------------------------------------------
int* bestByGreedy(int numAxes, graph* g) {
  int seedX, seedY;

  //O(|V|^2)
  getMaxCell(g,&seedX,&seedY);
  return getBestByMaxChain(numAxes,g, seedX,seedY, 0);
}

//------------------------------------------------------------------------
// Creates a layout of axes that's near optimal by picking out the
// highest-valued pairs and then creating a layout which optimizes
// the total edge weight of consecutive axes.
// O(k|V|^2 + k!)
//------------------------------------------------------------------------
int* bestByPairs(int numAxes, graph* g) {
  int i;
  int *tarX, *tarY;

  //O(k|V|^2)
  getBestPairs(numAxes-1, g, &tarX, &tarY, 0);

  printf("Best pairs found are:\n");
  for(i=0;i<numAxes-1;i++) {
    printf("  (%d,%d)=%d,",tarX[i],tarY[i],g->mat2d[tarY[i]][tarX[i]]);
  }
  printf("\n");
  //--Got the numAxes-1 best pairs

  //--Combine pairs to create layout
  //O(k!)
  return QuickPermPair(numAxes-1, tarX, tarY, g);
}

//------------------------------------------------------------------------
// Creates a layout of axes by brute-force searching all possible axis
// combinations.
// O( (n choose k) * k!) = O( n!/(n-k)! )
//------------------------------------------------------------------------
int* bestByBruteForce(int numAxes, graph* g) {
  return chooseAxes(g->numVerts,numAxes,g);
}

int searchiv(int numElems, int* array, int target) {
   int i,cnt;

   cnt=0;
   for(i=0;i<numElems;i++) {
      if(array[i]==target) cnt++;
   }
   return cnt;
}

int findNew(int num1, int* array1, int num2, int* array2) {
   int i,j,exists;

   for(i=0;i<num2;i++) {
      exists=0;
      for(j=0;j<num1;j++) {
         if(array2[i]==array1[j]) exists=1;
      }
      if(exists==0) return array2[i];
   }
   return -1;
}

//------------------------------------------------------------------------
// Creates a layout of axes by taking an integer array which denotes
// whether the axes should contain max or min values in all supplied
// graphs and calculates the requested layout by choosing best paris
//------------------------------------------------------------------------
int* comboMultiFile(int numAxes, int* combo, graph** sg, int allowRepeats) {
  int i, getFromY,newAxis;
  int *bestLayout;
  int **tarX, **tarY;

  bestLayout=(int*)malloc(numAxes*sizeof(int));
  if(bestLayout==NULL) {
    fprintf(stderr,"Error: comboMultiFile() bestLayout\n");
    return NULL;
  }
  tarX=(int**)malloc(numAxes*sizeof(int*));
  tarY=(int**)malloc(numAxes*sizeof(int*));
  if(tarX==NULL || tarY==NULL) {
    fprintf(stderr,"Error: comboMultiFile() tarX tarY\n");
    return NULL;
  }

  for(i=0;i<numAxes;i++) {
    if(combo[i]==0) getWorstPairs(numAxes,sg[i],&(tarX[i]),&(tarY[i]),allowRepeats);
    if(combo[i]==1) getBestPairs(numAxes,sg[i],&(tarX[i]),&(tarY[i]),allowRepeats);
  }


  /*for(i=0;i<numAxes;i++) {
     for(newAxis=0;newAxis<numAxes;newAxis++) {
        printf(" %d %d",tarX[i][newAxis],tarY[i][newAxis]);
     }
     printf("\n");
  }*/

  if(allowRepeats==0) {
     for(i=0;i<numAxes;i++) {
        getFromY=0;
        newAxis=findNew(i,bestLayout,numAxes,tarX[i]);
        if(newAxis==-1) {
           getFromY=1;
           newAxis=findNew(i,bestLayout,numAxes,tarY[i]);
        }
        if(newAxis==-1) {
           fprintf(stderr,"comboMultiFile(): cannot find unique axis\n");
           free(tarX); free(tarY); free(bestLayout);
           return NULL;
        }
        else {
           if(getFromY==0) bestLayout[i]=newAxis;
           else bestLayout[i]=newAxis;
        }
     }
  }
  else {
     for(i=0;i<numAxes;i++) {
        bestLayout[i]=tarX[i][0];
     }
  }

  /*printf("Pairs found for");
  for(i=0;i<numAxes;i++) printf(" %1d",combo[i]);
  printf(" are:\n");
  for(i=0;i<numAxes;i++) {
    printf("  (%d,%d)=%d,",targetX[i],targetY[i],sg[i]->mat2d[targetY[i]][targetX[i]]);
  }
  printf("\n");*/

  free(tarX); free(tarY);
  return bestLayout;
}

//------------------------------------------------------------------------
// Creates a layout of axes by taking an integer array which denotes
// whether the axes should contain max or min values in all supplied
// graphs.
//------------------------------------------------------------------------
int* comboMultiFileAvg(int numAxes, int* combo, graph** sg) {
   int i,j,k, v1,v2, min,max,idx;
   int *bestLayout, **cnt, **bin;

   //Allocate memory
   bestLayout=(int*)malloc(numAxes*sizeof(int));
   if(bestLayout==NULL) {
      fprintf(stderr,"combo() bestLayout\n");
      return NULL;
   }
   bin=(int**)malloc(numAxes*sizeof(int*));
   cnt=(int**)malloc(numAxes*sizeof(int*));
   if(bin==NULL || cnt==NULL) {
      fprintf(stderr,"combo() bin cnt\n");
      return NULL;
   }
   for(i=0;i<numAxes;i++) {
      bin[i]=(int*)malloc(sg[0]->numVerts*sizeof(int));
      cnt[i]=(int*)malloc(sg[0]->numVerts*sizeof(int));
      if(bin[i]==NULL || cnt[i]==NULL) {
         fprintf(stderr,"combo() bin[] cnt[]\n");
         return NULL;
      }
   }
   for(i=0;i<numAxes;i++) {
      for(j=0;j<sg[0]->numVerts;j++) {
         bin[i][j]=cnt[i][j]=0;
      }
   }

   //Update the bin to record the sum of each vertex in the graph
   for(i=0;i<numAxes;i++) {
      for(j=0;j<sg[0]->numVerts;j++) {
         for(k=0;k<sg[0]->numVerts;k++) {
            v1=j; v2=k;
            if(v1<v2) SWAP(v1,v2);
            if( (v1!=v2) && (sg[i]->mat2d[v1][v2]!=INAN) ) {
               bin[i][j]+=sg[i]->mat2d[v1][v2];
               cnt[i][j]++;
            }
         }
      }
   }

   //Convert from sum to average
   for(i=0;i<numAxes;i++) {
	    for(j=0;j<sg[0]->numVerts;j++) {
        if(cnt[i][j]!=0) bin[i][j]=bin[i][j]/cnt[i][j];
      }
   }

   for(i=0;i<numAxes;i++) {
	   min=INT_MAX; max=INT_MIN; idx=-1;
      if(combo[i]==0) {//getmin
	      for(j=0;j<sg[0]->numVerts;j++) {
            if(bin[i][j]<min) {
			         min=bin[i][j];
               idx=j;
            }
	      }
         bestLayout[i]=idx;
      }
      else if (combo[i]==1) {//getmax
	      for(j=0;j<sg[0]->numVerts;j++) {
            if(bin[i][j]>max) {
			      max=bin[i][j];
               idx=j;
            }
	      }
         bestLayout[i]=idx;
      }
      else fprintf(stderr,"comboMultiFile(): Unsupported combo option\n");
   }

   for(i=0;i<numAxes;i++) free(bin[i]);
   free(bin);

   return bestLayout;
}
