// example_main.C
//
// A program to collect timing data about Insert and Merge operations
// on array-based binary heaps, and pointer-based leftist heaps
//
// Author: Paul Kube kube@cs.ucsd.edu copyright (c) 1996
//

#include <iostream.h>           // for cin, cout, cerr
#include <stdlib.h>             // for exit()
#include <time.h>               // for clock()
#include <iomanip.h>            // for setw()
#include "heaps.h"              // for AHeap and LHeap classes


void Usage(char * progname) 
{
  cerr << "Usage: " << endl;
  cerr << '\t' << progname << " N [M] < intfile" << endl;
  cerr << "Where N is the size of the heaps to test," << endl;
  cerr << "intfile is the name of a file containing at least 2N integers," << endl;
  cerr << "M is optional (default 0) number of heap elements to check at end." << endl;
  exit(-1);

}
  

int main(int argc, char* argv[])
{

  if (argc < 2) Usage(argv[0]);


  // get heapsize from the first command line argument
  int Heapsize = atoi(argv[1]);

  cout << "Comparing performance of array-based binary heaps (AH)\n"
       << "with pointer-based leftist heaps (LH), using " << Heapsize << " elements.\n";
  cout << "For this test, we will read " << 2 * Heapsize << "  integers from stdin.\n";




  // create some empty array-based binary heaps
  AHeap ah1(2*Heapsize), ah2(Heapsize);
  
  // create some empty leftist heaps
  LHeap lh1, lh2;

  // create two arrays, each holding Heapsize integers
  int* ints1 = new int[Heapsize];
  int* ints2 = new int[Heapsize];
  
  int i;                        // handy index variable
  
  // get the integers from stdin
  for(i=0; i<Heapsize; i++) {
    cin >> ints1[i];
    if (cin.fail()) {
      cerr << "Hey, I needed " << 2*Heapsize << " ints, only got " << i << endl;
      Usage(argv[0]);
      
    }
  }
  for(i=0; i<Heapsize; i++) {
    cin >> ints2[i];
    if (cin.fail()) {
      cerr << "Hey, I needed " << 2*Heapsize << " ints, only got " << Heapsize + i << endl;
      Usage(argv[0]);

    }
  }
  
  // do some timing, in seconds
  double time1, time2;
  clock();                      // start clock, see man 3 clock
  time1 = clock()/double(CLOCKS_PER_SEC); // read clock
  
  // build an array-based binary heap, inserting elements from ints1[] into ah1
  for(i=0; i< Heapsize; i++) {
    ah1.Insert(ints1[i]);
  }
  time2 = clock()/double(CLOCKS_PER_SEC);         // read clock
  cout << "Building an AH with "
       << Heapsize << " elements takes " << time2-time1 << " s." << endl;
  time1 = time2;
  
  // do it again, inserting elements from ints2[] into ah2
  for(i=0; i< Heapsize; i++) {
    ah2.Insert(ints2[i]);       
  }
  time2 = clock()/double(CLOCKS_PER_SEC);         // read clock
  cout << "Building an AH with "
       << Heapsize << " elements takes " << time2-time1 << " s." << endl;
  time1 = time2;
  
  // now merge them... ah1 must be big enough to hold both!
  ah1.Merge(ah2);
  time2 = clock()/double(CLOCKS_PER_SEC);         // read clock
  cout << "Merging two AH's with "
       << Heapsize << " elements takes " << time2-time1 << " s." << endl;
  time1 = time2;


  // build a leftist heap, inserting elements from ints1[]
  for(i=0; i< Heapsize; i++) {
    lh1.Insert(ints1[i]);
  }
  time2 = clock()/double(CLOCKS_PER_SEC);         // read clock
  cout << "Building an LH with "
       << Heapsize << " elements takes " << time2-time1 << " s." << endl;
  time1 = time2;
  
  // do it again, inserting elements from ints2[]
  for(i=0; i< Heapsize; i++) {
    lh2.Insert(ints2[i]);
  }
  time2 = clock()/double(CLOCKS_PER_SEC);         // read clock
  cout << "Building an LH with "
       << Heapsize << " elements takes " << time2-time1 << " s." << endl;
  time1 = time2;
  
  // now merge them
  lh1.Merge(lh2);
  time2 = clock()/double(CLOCKS_PER_SEC);         // read clock
  cout << "Merging two LH's with "
       << Heapsize << " elements takes " << time2-time1 << " s." << endl;
  time1 = time2;
  
  
  // Check that the heaps are really merged correctly
  // by printing out the result of some successive DeleteMin's.

  int NtoTest = argc < 3 ? 0 : atoi(argv[2]);

    cout << "Result of merging:  top elements in the heap\n";
    cout << "Array-based Heap        Leftist Heap\n";
    cout << "----------------       ----------------\n";
    for(i=0; i<Heapsize && i<NtoTest; i++) {
      cout << setw(16) << ah1.DeleteMin() << "       "
           << setw(16) << lh1.DeleteMin() << endl;
    }

  
  // okay, that's enough

  // clean up
  delete [] ints1;
  delete [] ints2;
  
  return 0;
  
}