#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <math.h>


#define MAX_NUM_PTS 10000000  // maximum # of marked entries in prediction matrix
#define UNASSIGNED -2
#define CANDIDATE -1
#define PROCESSED 0
#define HASH_SIZE_PER_PAGE 8


int *status, *x, *y, *xOrder, *yOrder;


/////////////////////////////////////////////
///
/// reads the matrix from file matrixFName into 2 integer arrays: x and y
/// and finds the x-order of these points.
/// Points are already written in y-order in the matrix file. Therefore, 
/// there is no need to find the x-order.
int readMatrix(const char matrixFName[])
{
  FILE *mfp;
  int numPts, i, *tmpy, bc, ws;

  printf("reading Match Table\n");

  x = (int*)malloc(sizeof(int)* MAX_NUM_PTS);
  y = (int*)malloc(sizeof(int)* MAX_NUM_PTS);

  // read matrix
  mfp = fopen(matrixFName,"r");
  fscanf(mfp,"%d %d",&bc,&ws);
  numPts = 0;
  while (fscanf(mfp,"%d %d", &x[numPts], &y[numPts]) > 0)
    numPts++;
  fclose(mfp);

  xOrder = (int*)malloc(sizeof(int)* numPts);
  yOrder = (int*)malloc(sizeof(int)* numPts);

  // initialize x and y orders
  for (i=0; i<numPts; i++){
    xOrder[i]=yOrder[i]=i;
  }

  tmpy = (int*)malloc(sizeof(int)* numPts);
  for (i=0; i<numPts; i++)  tmpy[i] = y[i];
  QuickSort(tmpy, yOrder, 0, numPts-1);

  // check order
  for (i=1; i<numPts; i++){
    tmpy[i]=0;
    if (x[xOrder[i-1]] > x[xOrder[i]]){
      printf("Error in x-order\n");
      printf("i= %d, xOrder[i-1]= %d, xOrder[i]= %d, x[xOrder[i-1]]= %d, x[xOrder[i]]= %d\n",i,yOrder[i-1],yOrder[i],y[yOrder[i-1]],y[yOrder[i]]);      exit(0);
    }
    if (y[yOrder[i-1]] > y[yOrder[i]]){
      printf("Error in y-order\n");
      printf("i= %d, yOrder[i-1]= %d, yOrder[i]= %d, y[yOrder[i-1]]= %d, y[yOrder[i]]= %d\n",i,yOrder[i-1],yOrder[i],y[yOrder[i-1]],y[yOrder[i]]);
      exit(0);
    }
  }
  for (i=0; i<numPts; i++)
    tmpy[yOrder[i]]++;
  for (i=0; i<numPts; i++){
    if (tmpy[i] != 1){
      printf("Error in y-Order: <%d >\n", i);
    }
  }

  free(tmpy);

  printf("Match Table read successfully\n");

  return numPts;
} // readMatrix


/////////////////////////////////////////////////////
///  Partitions the Match Table into smaller pieces such 
///  that each piece fits into buffer and the total I/O 
///  cost is minimal.
///
void mapSearch(const char matrixFName[], int bufferSize)
{
  int numPts, bufferAvail, xCur, yCur, oldxCur, oldyCur, numX, numY, 
    xMark, yMark, i, numUniqueX, numUniqueY, xStart, yStart, 
    CPUhashTableConstruct, CPUprocessSeed, totalIO;

  numPts = readMatrix(matrixFName); 

  status = (int*)malloc(sizeof(int)* numPts);
  for (i=0; i<numPts; i++){ status[i]=UNASSIGNED;} // initialize status
  CPUhashTableConstruct = CPUprocessSeed = totalIO = 0;

  while (CPUprocessSeed < numPts){

    bufferAvail = 1;
    numUniqueX=numUniqueY=0;
    xCur = yCur = -1;
    for (i=0; i<numPts; i++){ // find the number of unique x & y values 
      if ((status[xOrder[i]] == UNASSIGNED) && (x[xOrder[i]] > xCur)){
	xCur = x[xOrder[i]];
	numUniqueX++;
      }
      if ((status[yOrder[i]] == UNASSIGNED) && (y[yOrder[i]] > yCur)){
	yCur = y[yOrder[i]];
	numUniqueY++;
      }
    }

    if (numUniqueX > numUniqueY){  // horizontal partition
      yStart=numX=numY=0;
      while (bufferAvail){
	oldyCur = yCur;
	for (i=yStart; i<numPts; i++){   // find the next marked row
	  if (status[yOrder[i]] == UNASSIGNED){ 
	    yCur = y[yOrder[i]];
	    break;
	  }
	}
	while ((i<numPts) && (y[yOrder[i]] == yCur)){ // mark all the "UNASSIGNED" entries in this row
	  if (status[yOrder[i]] == UNASSIGNED) 
	    status[yOrder[i]] = CANDIDATE;
	  i++;
	}
	numY++;
	yMark = i-1;  // store the current index on y

	xCur = -1;
	numUniqueX=0;
	for (i=0; i<numPts; i++){ // find the number of unique x values in this row 
	  if ((status[xOrder[i]] == CANDIDATE) && (x[xOrder[i]] > xCur)){
	    xCur = x[xOrder[i]];
	    numUniqueX++;
	  }
	}
	if (numUniqueX*HASH_SIZE_PER_PAGE <= bufferSize){ // this row fits into buffer
	  numX = numUniqueX;
	  if (yCur == oldyCur){ // if there is no more row, process and quit
	    totalIO += numX+numY;
	    CPUhashTableConstruct += numX;
	    i = yMark;
	    while (i>=0){
	      if (status[yOrder[i]] == CANDIDATE){
		status[yOrder[i]] = PROCESSED;
		CPUprocessSeed++;
	      }
	      i--;
	    }
	    bufferAvail = 0;
	  }
	}
	else{  // row does not fit into buffer
	  if (numY == 1){  // this is the only row. So we have to incur multiple random I/Os 

	    for (i=0; i<numPts; i++){ // mark the candidate pages as "PROCESSED" 
	      if (status[i] == CANDIDATE)
		status[i] = PROCESSED;
	    }
	    totalIO += numUniqueX + ceil((numUniqueX*HASH_SIZE_PER_PAGE)/bufferSize);
	    CPUhashTableConstruct += numUniqueX;
	    CPUprocessSeed += numUniqueX;
	    bufferAvail = 0;
	  }
	  else{ // Previous rows fit but this one does not. 
	        // So step back and eliminate this row for this iteration.
	    i = yMark;
	    while (i>=0){
	      if (status[yOrder[i]] == CANDIDATE){
		if (y[yOrder[i]] == yCur){
		  status[yOrder[i]] = UNASSIGNED;
		}
		else{
		  status[yOrder[i]] = PROCESSED;
		  CPUprocessSeed++;
		}
	      }
	      i--;
	    }
	    numY--;
	    totalIO += numX+numY;
	    CPUhashTableConstruct += numX;
	    bufferAvail = 0;
	  }
	}

      }
    }

    else{ // vertical partition

      xStart=numX=numY=0;
      while (bufferAvail){
	oldxCur = xCur;
	for (i=xStart; i<numPts; i++){   // find the next marked column
	  if (status[xOrder[i]] == UNASSIGNED){ 
	    xCur = x[xOrder[i]];
	    break;
	  }
	}
	while ((i<numPts) && (x[xOrder[i]] == xCur)){// mark all the "UNASSIGNED" entries in this column
	  if (status[xOrder[i]] == UNASSIGNED) 
	    status[xOrder[i]] = CANDIDATE;
	  i++;
	}
	numX++;
	xMark = i-1;  // store the current index on x

	yCur = -1;
	numUniqueY=0;
	for (i=0; i<numPts; i++){ // find the number of unique x values in this column 
	  if ((status[yOrder[i]] == CANDIDATE) && (y[yOrder[i]] > yCur)){
	    yCur = y[yOrder[i]];
	    numUniqueY++;
	  }
	}
	if (numUniqueY*HASH_SIZE_PER_PAGE <= bufferSize){ // this column fits into buffer
	  numY = numUniqueY;
	  if (xCur == oldxCur){ // if there is no more column, process and quit
	    totalIO += numX+numY;
	    CPUhashTableConstruct += numY;
	    i = xMark;
	    while (i>=0){
	      if (status[xOrder[i]] == CANDIDATE){
		status[xOrder[i]] = PROCESSED;
		CPUprocessSeed++;
	      }
	      i--;
	    }
	    bufferAvail = 0;
	  }
	}
	else{  // column does not fit into buffer
	  if (numX == 1){// this is the only column. So we have to incur multiple random I/Os 

	    for (i=0; i<numPts; i++){ // mark the candidate pages as "PROCESSED" 
	      if (status[i] == CANDIDATE)
		status[i] = PROCESSED;
	    }
	    totalIO += numUniqueY + ceil((numUniqueY*HASH_SIZE_PER_PAGE)/bufferSize);
	    CPUhashTableConstruct += numUniqueY;
	    CPUprocessSeed += numUniqueY;
	    bufferAvail = 0;
	  }
	  else{ // Previous columns fit but this one does not. 
	        // So step back and eliminate this column for this iteration.
	    i = xMark;
	    while (i>=0){
	      if (status[xOrder[i]] == CANDIDATE){
		if (x[xOrder[i]] == xCur){
		  status[xOrder[i]] = UNASSIGNED;
		}
		else{
		  status[xOrder[i]] = PROCESSED;
		  CPUprocessSeed++;
		}
	      }
	      i--;
	    }
	    numX--;
	    totalIO += numX+numY;
	    CPUhashTableConstruct += numY;
	    bufferAvail = 0;
	  }
	}

      }

    }

    // printf("%d %d %d %d\n",totalIO,CPUhashTableConstruct,CPUprocessSeed,numPts);
  }

    printf("%d %d %d %d\n",totalIO,CPUhashTableConstruct,CPUprocessSeed,numPts);

}