/************************************************************
  FILE: mergetest.cc
  K.Becker
  September 27 2000

  Program to compare polyphase merge against cascade

  WARNING: input error checking is minimal

  Expected arguments:
  1: -n N :: the order of the merge [# devices = n+1]

  2: -f F :: the file size in bytes [default = 1 GB]

  3: -m M :: amount of available memory [default = 10 MB]
  
  4: -r R :: size of one record [default = 1000 bytes]

  5: -k K :: the number of initial runs [can be calculated]
  
  6: (optional) debug flag: -d 1 | 2 | 3
        [0] no trace (default)
	[1] minimal 
	[2] medium
	[3] full trace

**********************************************************/

#include <stdio.h>
#include <iostream.h>
#include <iomanip.h>
#include <stdlib.h>
#include <fstream.h>
#include <string.h>

int debug = 0;

const int MAXR    = 25;      // maximum number of rows
int       maxR    = 25;      // max number of useful rows
    // these numbers can get big so we watch for overflow

//----------------------------------------------------------------------
// my own includes

#include "Device.h"

/*********************************************************/
/***** admin stuff  **************************************/
/*********************************************************/

void help( )
{
  cout << "MERGE TEST:" << endl;
  cout << "Program to compare polyphase merge against cascade\n" << endl;
  cout << "Usage: mergetest -n N {-f F -m M -r R -k K -d D}\n" << endl;
  cout << "WARNING: input error checking is minimal" << endl;
  cout << endl;
  cout << "  Expected arguments:" << endl;
  cout << "     -n N :: the order of the merge [# devices = n+1]" << endl;
  cout << endl;
  cout << "     -f F :: the file size in bytes [default = 1 GB]" << endl;
  cout << endl;
  cout << "     -m M :: amount of available memory [default = 10 MB]" << endl;
  cout << endl;
  cout << "     -r R :: size of one record [default = 1000 bytes]" << endl;
  cout << endl;
  cout << "     -k K :: the number of initial runs [can be calculated]" << endl;
  cout << endl;
  cout << "   (optional) debug flag: -d 1 | 2 | 3" << endl;
  cout << "     [0] no trace (default)" << endl;
  cout << "     [1] minimal" << endl;
  cout << "     [2] moderate" << endl;
  cout << "     [3] full trace" << endl;
  cout << endl;

} // help

//-------------------------------------------------------//
//-------  getargs    -----------------------------------//
//-------------------------------------------------------//
void getargs (int argc, char* argv[], 
	      int& order, 
	      long int& fsize, 
	      long int& memsize, 
	      long int& recsize, 
	      long int& nruns )
{
  int cur = 1;

  while (cur < argc)
    {
      if (argv[cur][0] == '-')
	{
	  switch (argv[cur][1]) {
	    
	  case 'n': // ORDER
	  case 'o':
	    order = atoi( argv[cur+1] );
	    cur += 2;
	    break;

	  case 'f': // FILE SIZE
	    fsize = atoi( argv[cur+1] );
	    cur += 2;
	    break;

	  case 'm': // MEMORY SIZE
	    memsize = atoi( argv[cur+1] );
	    cur += 2;
	    break;

	  case 'r': // RECORD SIZE
	    recsize = atoi( argv[cur+1] );
	    cur += 2;
	    break;

	  case 'k': // NUMBER OF RUNS
	    nruns = atoi( argv[cur+1] );
	    cur += 2;
	    break;

	  case 'd': // DEBUG CODE
	    debug = atoi( argv[cur+1] );
	    cur += 2;
	    break;

	  default:
	    cout << "ERROR: Unknown argument: "
		 << argv[cur] << endl;
	    cur += 2;
	  } // end case
	} // end if
    } // end while

  return;
} // getargs


//-------------------------------------------------------//
//----------  displaytable ------------------------------//
//-------------------------------------------------------//
void displaytable( char str[], long int** p, int rows, int cols )
{
  // NOTE: 'cols' doesn't count the "totals" column

  int i,j;

  for (i = 0; i < cols+1; i++)
    cout << "--------------";
  cout << endl;
  cout << str << ':' << endl;
  
  for (i = 0; i < rows; i++ )
    {
      cout << setw(2) << i << ':';
      for (j = 0; j < cols+1; j++)
	cout << setw(12) << p[i][j] << "  ";
      cout << endl;
    }
  cout << endl;

  return;
} // displaytable

//-------------------------------------------------------//
//--- genpoly -------------------------------------------//
//-------------------------------------------------------//
long int** genpoly( int cols, int& maxR )
{
  // generate poyphase merge table
  // NOTE: 'cols' doesn't include the 'totals' column

  long int **p;
  int i,j;
  maxR = MAXR;

  int rows = maxR;

  p = new long int*[rows];
  for (i = 0; i < rows; i++)
    p[i] = new long int[cols+1];
  
  // set first row
  p[0][0] = 1; p[0][cols] = 1;
  for ( i = 1; i < cols; i++ )
    p[0][i] = 0;
  
  // generate the rest
  for (i = 1; i < rows; i++)
    {
      // last value in row is same as first from previous
      p[i][cols-1] = p[i-1][0];
      p[i][cols] = p[i][cols-1]; // for the sum
      
      for (j = 0; j < cols-1; j++)
	{
	  p[i][j] = p[i-1][0] + p[i-1][j+1];
	  p[i][cols] += p[i][j];
	}
      
      // watch out for overflow
      if (p[i][cols] < 0)
	{
	  maxR = i;
	  break;
	}
    }

  return(p);
} // genpoly

//-------------------------------------------------------//
//---- gencascade   -------------------------------------//
//-------------------------------------------------------//
long int** gencascade( int cols, int& maxR )
{
  // generate cascade merge table
  // NOTE: 'cols' doesn't include the 'totals' column

  long int **p;
  long int sum;
  int i,j;

  maxR = MAXR;
  int rows = maxR;

  p = new long int*[rows];
  for (i = 0; i < rows; i++)
    p[i] = new long int[cols+1];
  
  // set first row
  p[0][0] = 1; p[0][cols] = 1;
  for ( i = 1; i < cols; i++ )
    p[0][i] = 0;

  // generate the rest
  for (i = 1; i < rows; i++)
    {
      // last value in row is same as first from previous
      p[i][cols-1] = p[i-1][0];
      p[i][cols] = p[i][cols-1]; // for the sum
      sum = p[i][cols];
      
      for (j = 1; j < cols; j++)
	{
	  p[i][cols] += p[i-1][j]; // works like running total
	  p[i][cols-j-1] = p[i][cols];
	  sum += p[i][cols];
	}
      p[i][cols] = sum;
      
      // watch out for overflow
      if (sum < 0)
	{
	  maxR = i;
	  break;
	}
    }

  return(p);
} // gencascade

//-------------------------------------------------------//
//----  SetUp       -------------------------------------//
//-------------------------------------------------------//
void SetUp( long int** table, // polyphase/cascade merge table
	    int order,
	    int nruns,
	    int runsize,
	    Device* devices[], Device* sources[], Device*& dest )
{
  int i;
  long int* initial_dist;  // initial distribution
  long int* dummy_list;    // distribution of dummies

  int      dist;      // location in table of correct distribution
  long int numruns;
  long int numdum;    // number of dummy runs
  long int dumper;    // number of dummy runs per device
  long int leftover;  // remainder

  initial_dist = new long int [order+1];
  dummy_list = new long int [order+1];
  for (i = 0; i < order; i++)
    dummy_list[i] = 0;

  // find the appropriate row of the table

  dist = 0;
  while((dist <= maxR) && (table[dist][order] < nruns))
    dist++;

  // calculate how many dummy runs we need
  numdum = table[dist][order] - nruns;

  // REPORT:
  if (debug >= 1) // initial distribution:
    {
      cout << "======================================================" << endl;
      cout << "RUNS: " << nruns 
	   << " DUMMIES: " << numdum 
	   << " TOTAL: " << table[dist][order] << endl;      
    }

  if (numdum)
    {
      // distribute dummies evenly EXCEPT TO LAST DEVICE
      dummy_list[order] = 0;
      dumper = int( numdum / (order-1) );
      if (numdum)
	leftover = numdum % (order-1);
      else 
	leftover = 0;
      for (i = 0; i < order-1; i++)
	dummy_list[i] = dumper;
      
      i = 0;
      while(leftover)
	{
	  dummy_list[i]++;
	  leftover--;
	  i++;
	}
    }

  // save initial distribution of existing runs
  for (i = 0; i < order; i++)
    initial_dist[i] = table[dist][i] - dummy_list[i];

  /*****/
  // REPORT:
  if (debug >= 2) // initial distribution:
    {
      cout << "RUNS:    ";
      for (i = 0; i < order; i++)
	cout << initial_dist[i] << "  ";
      cout << endl;
      cout << "DUMMIES: ";
      for (i = 0; i < order; i++)
	cout << dummy_list[i] << "  ";
      cout << endl << endl;
      
    }
  /*****/

  // setting up the devices
  // loading runs and dummies onto devices
  // the destination device:
  devices[order] = new Device( nruns ); // maximum size; empty
  for (i=0; i < order; i++)
    devices[i] = new Device ( initial_dist[i], dummy_list[i], runsize );
  dest = devices[order];       // last one is destination
  for (i=0; i < order; i++)    // the rest are sources
    sources[i] = devices[i];

  delete [] initial_dist;
  delete [] dummy_list;

} // end SetUp

//-------------------------------------------------------//
//----  do_round    -------------------------------------//
//-------------------------------------------------------//
void do_round( Device* sources[], Device* dest, 
	       int order, 
	       long int rps,       // records per seek
	       long int& totseeks, 
	       long int& whos_empty,
	       bool& done )
{
  // collect 1 run from each device to merge to destination

  int i;
  long int newrun = 0;
  long int thisrun = 0;
  long int seeks;
  long int setseeks;

  setseeks = 0; // seeks for this set
  /*****/ // REPORT
  if (debug >= 3)
    cout << "SET: ";
  /*****/

  for (i=0; i < order; i++)
    {
      /*****/ // REPORT
      if (debug >= 3)
	cout << "D" << i << ": ";
      /*****/
      // make sure it's available
      if (sources[i]->IsAvailable())
	{
	  thisrun = sources[i]->Gives(); // grab the run

	  if (sources[i]->IsEmpty()) // is this device empty now?
	    {
	      done = true;
	      whos_empty = i;
	    }
	  newrun += thisrun; // 'merge' it
	  seeks = thisrun / rps; // count the seeks for this run
	  setseeks += seeks;

	  /*****/ // REPORT
	  if (debug >= 2)
	    {
	      if (sources[i]->IsEmpty()) // is this device empty now?
		cout << seeks << "sk [" << setw(3) << thisrun << "]" 
		   << "empty file ";
	      else
		{
		  cout << seeks << "sk [" << setw(3) << thisrun << "]."; 
		  cout.fill('.');
		  cout << setw(3) << sources[i]->Size() << " Files ";
		  cout.fill(' ');
		}
	    }
	  /*****/
	}
      else
	{
	  /*****/ // REPORT
	  if (debug >= 3)
	    cout << "D" << i << " ----- ";
	  /*****/
	}

    }// end for

  // 'write' the new run to the destination
  dest->Gets(newrun);
  totseeks += setseeks; // add the seeks for the set just finished
  /*****/ // REPORT
  if (debug >= 2)
    {
      cout << "TOTAL: " << setseeks;
      cout << "  Run: " << newrun << endl << endl;
    }
  /*****/


} // end do_round

//-------------------------------------------------------//
//----  polyphase   -------------------------------------//
//-------------------------------------------------------//
void polyphase ( Device* sources[], Device*& dest, int order, int memsize )
{
  // does N-way merge each time (phase) where N is the order of the merge
  // For each phase:
  //   collect 1 run from each source into 1 new run
  //   when one source goes empty this phase is done
  //   put the new run into dest
  //
  // After each phase:
  //   switch dest and the source that went empty
  //   check 1 other source: if it's empty too, we're done
  //     we'll check source[0] unless that's the one that went empty
  //       in which case we can check source[1]
  //
  
  long int setseeks;                   // seeks per set
  long int totseeks, grandtotal;       // seeks per phase; merge
  long int recs_per_seek;              // how many records we get for one seek
  long int whos_empty;                 // remembers which source went empty

  bool     done, alldone;              // flags for phase, merge

  Device*  t;                          // for switching

  int      i;

  recs_per_seek = memsize / order;
  grandtotal = 0;
  alldone = false;

  /*****/ // REPORT
  if (debug >= 2)
    cout << "Polyphase: " << endl;
  /*****/

  while (!alldone)
    {
      totseeks = 0; // for this phase
      /*****/ // REPORT
      if (debug >= 3)
	{
	  cout << "Phase...:" << endl;
	  for (i = 0; i < order; i++)
	    {
	      cout << i << "[" << setw(3) << sources[i]->Size() << "] ";
	    }
	  cout  << endl << endl;

	}
      /*****/
      done = false;
      whos_empty = 0;
      
      while (!(done))
	{

	  // collect 1 run from each device
	  do_round( sources, dest, order, recs_per_seek, 
		    totseeks, whos_empty, done);

	} // while !done

      /*****/ // REPORT
      if (debug >= 2)
	cout << "TOTAL THIS PHASE: " << totseeks << endl;
      /*****/

      grandtotal += totseeks;

      // switch empty source and dest
      t = dest;
      dest = sources[whos_empty];
      sources[whos_empty] = t;

      // check another source to see if >1 empty
      // if >1 empty; all MUST be empty so we're done
      if (whos_empty != 0)
	{
	  if (sources[0]->IsEmpty())
	    alldone = true;
	}
      else
	{
	  if (sources[1]->IsEmpty())
	    alldone = true;
	}
    } // end while !done

  cout << "Total seeks for Polyphase Merge: "
       << grandtotal << endl << endl;

} // end polyphase

//-------------------------------------------------------//
//----  cascade     -------------------------------------//
//-------------------------------------------------------//
void cascade ( Device* sources[], Device*& dest, int order, int memsize )
{
  // does N-way merge, then N-1 way, then N-2 way...
  //   where N is the order of the merge
  // For each phase: (count is N-1 = #rounds)
  //    For each round:
  //      collect 1 run from each source into 1 new run
  //      when one source goes empty this round is done
  //      - move 'dest' to holding
  //      - make 'empty' source unavailable 
  //      - count down
  // After each phase:
  //    - move all "holdings" back to the empty sources (count them)
  //    - if count of "holdings" is 1 we're done
  //
  //
  
  long int setseeks, phaseseeks;       // seeks per set, phase
  long int totseeks, grandtotal;       // seeks per phase; merge
  long int recs_per_seek = 0;          // how many records we get for one seek
                                       // changes from round to round since 
                                       // we're dealing with different order
                                       // merges each time
  long int whos_empty;                 // remembers which source went empty

  bool     done, done_round, done_phase, alldone; 
                                       // flags for phase, merge
  Device** holding;
  int      holding_count = 0;
  int      round_count = 0;

  int      i,j;

  grandtotal = 0;
  alldone = false;
  holding = new Device*[order+1];
  for (i = 0; i < order; i++)
    holding[i] = new Device(100); // ****UNSAFE*****

  /*****/ // REPORT
  if (debug >= 2)
    cout << "Cascade: " << endl;
  /*****/

  while (!alldone) // phase by phase
    {
      /*****/ // REPORT
      if (debug >= 3)
	{
	  cout << "Phase...:" << endl;
	  for (i = 0; i < order; i++)
	    {
	      cout << i << "[" << setw(3) << sources[i]->Size() << "] ";
	    }
	  cout  << endl << endl;

	}
      /*****/

      phaseseeks = 0; // for this phase
      round_count = order;
      holding_count = 0;
      
      while (round_count > 1) // round by round
	{
	  done = false;
	  whos_empty = 0;
	  totseeks = 0;
	  // will be different each round
	  recs_per_seek = memsize / round_count; 
	  while (!(done)) // set by set
	    {
	      // collect 1 run from each available device
	      do_round( sources, dest, order, recs_per_seek, 
			totseeks, whos_empty, done);
	      
	    } // while !done
	  
	  // move the destination to holding
	  while (!dest->IsEmpty())
	    dest->MoveTo(holding[holding_count]);
	  holding_count++;
	  sources[whos_empty]->Unavailable(); // now unavailable
	  round_count--;
	      
	  phaseseeks += totseeks;
	  /*****/ // REPORT
	  if (debug >= 2)
	    {
	      cout << "TOTAL THIS ROUND: " << totseeks << "  HOLDING: ";
	      for (i = 0; i < holding_count; i++)
		{
		  cout << i << "[" << setw(3) << holding[i]->Size() << "] ";
		}
		cout  << endl << endl;
	    }
	  /*****/

	  // if all devices are unavailable or empty, we're done
	  j = 0;
	  for (i = 0; i < order; i++)
	    {
	      if ((!sources[i]->IsAvailable()) || (sources[i]->IsEmpty()))
		j++;
	      /*****/ // REPORT
	      if (debug >= 4)
		{
		  cout << "checking " << i << " j is " << j << endl;
		  if (sources[i]->IsAvailable()) 
		    cout << sources[i]->IsEmpty() << endl;
		}
	      /*****/
	    }
	  if (j == order)
	    {
	      alldone = true;
	      round_count = 1;
	    }

	} // end rounds

      grandtotal += phaseseeks;
      
      /*****/ // REPORT
      if (debug >= 2)
	cout << "TOTAL THIS PHASE: " << phaseseeks << endl << endl;
      /*****/

      if (holding_count <= 1)
	alldone = true;

      // move all "holdings" back to sources
      j = 0;
      for ( i=0; i < order; i++)
	{
	  if (!sources[i]->IsAvailable())
	    {
	      sources[i]->MakeAvailable();
	      while( !holding[j]->IsEmpty() )
		holding[j]->MoveTo(sources[i]);
	      j++;
	      holding_count--;
	    }
	}

    } // end while !alldone

  cout << "Total seeks Cascade Merge: "
       << grandtotal << endl << endl;

  delete [] holding;

} // end cascade

/*********************************************************/
/***** MAIN **********************************************/
/*********************************************************/
int main( int argc, char* argv[] )
{
  long int** polytable;
  long int** cascadetable;
  
  int        order   = 0;                 // order of merge
  long int   fsize   = 1000000000;        // file size: 1 GB
  long int   memsize = 10000000;          // available memory: 10 MB
  long int   recsize = 1000;              // size of one record
  long int   nruns   = 0;                 // number of runs to merge

  long int   recmem  = 0;                 // # of records that fit in memory
  // in the beginning this is the same as the size of one run
  long int   nrecs   = 0;                 // # of records in file
  long int   rpr     = 0;                 // number of records per run

  Device** devices = NULL;      // the devices used for this merge
  Device** sources = NULL;      // which devices serve as sources for this phase
  Device* dest = NULL;         // which devoice is the destination this phase?

  int i,k; // for indexing

  // get args - set flags
  if (argc <= 1)
    {
      help();
      exit(0);
    }

  getargs ( argc, argv, order, fsize, memsize, recsize, nruns );
  if (!order) // NOT OPTIONAL
    {
      cout << endl;
      cout << "ERROR: Order of Merge NOT optional. Quit." << endl;
      help();
      exit(0);
    }

  // calc what's left
  recmem = int( memsize / recsize );
  nrecs  = int( fsize / recsize );

  if (!nruns)
    nruns = int( nrecs / recmem );

  rpr = int( nrecs / nruns );

  // REPORT:
  cout << endl;
  cout << "Order of merge....................." << order << endl;
  cout << "File Size.........................." << fsize << endl;
  cout << "Available Memory..................." << memsize << endl;
  cout << "Size of one record................." << recsize << endl;
  cout << "Number of Runs....................." << nruns << endl;
  cout << "Number records in Memory..........." << recmem << endl;
  cout << "Number Records in Original File...." << nrecs << endl;
  cout << "Number of Records per Run.........." << rpr << endl;

  cout << "Debug Switch = " << debug << endl;

  polytable =  genpoly( order, maxR );
  cascadetable = gencascade( order, maxR );

  devices = new Device* [order+1];
  sources = new Device* [order];

  /*****/
  if (debug >= 3) // display tables:
    {
      displaytable( "Polyphase", polytable, maxR, order );
      displaytable( "Cascade", cascadetable, maxR, order );
    }
  /*****/
  
  /*****/
  if (debug >= 3) // 
    {
      cout << "MAIN: setting up initial distribution: " << endl;
    }
  /*****/
  
  SetUp( polytable, order, nruns, rpr, devices, sources, dest );

  /*****/
  if (debug >= 3) // 
    {
      cout << endl;
      cout << "MAIN: PolyPhase Merge-Sort: " << endl;
    }
  /*****/
  polyphase( sources, dest, order, recmem );

  delete [] devices;

  SetUp( cascadetable, order, nruns, rpr, devices, sources, dest );
  /*****/
  if (debug >= 3) // 
    {
      cout << endl;
      cout << "MAIN: Cascade Merge-Sort: " << endl;
    }
  /*****/

  cascade( sources, dest, order, recmem );
  

  cout << "Done." << endl;

}
//-------------------------------------------------------------------------
//------------ end mergetest.cc -------------------------------------------
//-------------------------------------------------------------------------