/* Build AVL trees from a sampling of permutations of N items, and accumulate
   statistics.

   Author:  Timothy Rolfe

   Set up for some minimal parallel processing:  UNIX environment, with
   straight "fork" available.  The fork call comes after the files have
   been opened, so that the two processes share the same output file.
   Then the two processes alternate in the tree sizes being tested ---
   the child process does the even-offset trees from the start, the
   parent process does the odd-offset trees.  If the two processors
   have similar loading, the file should be generated in proper order.
   If it isn't, a simple sort based on the first field will get it
   into proper order.
*/
#include <iostream.h>
#include <fstream.h>    // ofstream
#include <stdlib.h>     // exit
#include <time.h>       // clock (timing statistics)
#include "AVL.h"        // AVL class --- use one with equal keys allowed

// If this is a dual-processor UNIX machine, we can actually use a
// simple fork and run two sets of experiments in parallel.
  
//#define DUAL_PROCESSOR  // UNIX environment, dual-processor computer

#ifdef DUAL_PROCESSOR
#include <unistd.h>     // fork (at least for Linux)
#endif

void main (int argc, char* argv[])
{
   AVL    Tree;
   int    k;            // Loop variable
   int    N,            // Number of nodes
          Nstep,        // Increment for N
          Nlim;         // Largest number to run
   long   Pass,         // Which pass in the Monte Carlo runs
          Npasses;      // Number of passes being averaged
   double SigmaHt,      // Total of tree heights
          SigmaDp;      // Total of tree average depths
   int    Height;       // Individual tree heights
   double AvgDepth;     // Individual tree average depths
   ofstream Fout("AVLstats.csv",ios::app);    // Accumulate statistics

   cout.precision(3);

   cout << "Initial number of nodes:  ";

   if ( argc > 1 )
   {
      N = atoi(argv[1]);
      cout << N << endl;
   }
   else
   {
      cin >> N;
   }

   cout << "Largest number of nodes:  ";

   if ( argc > 2 )
   {
      Nlim = atoi(argv[2]);
      cout << Nlim << endl;
   }
   else
   {
      cin >> Nlim;
   }

   cout << "Step size in generating BST statistics:  ";

   if ( argc > 3 )
   {
      Nstep = atoi(argv[3]);
      cout << Nstep << endl;
   }
   else
   {
      cin >> Nstep;
   }

   cout << "Number of Monte Carlo passes to average:  ";

   if ( argc > 4 )
   {
      Npasses = atoi(argv[4]);
      cout << Npasses << endl;
   }
   else
   {
      cin >> Npasses;
      cin.ignore(255, '\n');
   }

   Fout << "N,Avg.Ht.,Avg.Dp.,Time" << endl;
   cout << "N,Avg.Ht.,Avg.Dp.,Time" << endl;

#ifndef DUAL_PROCESSOR   
   srand(time(NULL));   // Get a chance start to rand() sequence
#else                   
// If it IS dual-processor, fork the second process, then start
// two different random sequences and arrange to alternate tree
// sizes during the simulation.
   pid_t Child = fork();
   if ( Child != 0 )    // I.e., if this is the parent process
      N += Nstep;       // Do the odd-offset ones
   Nstep += Nstep;      // Each process steps by twice as much

// Chance start to rand() sequence --- different for parent and child
   srand(time(NULL) + Child);
#endif

   for ( ; N <= Nlim ; N += Nstep )
   {
      clock_t Start = clock();
      double  CPUsecs;

      SigmaHt = SigmaDp = 0; // Start summation at zero

      for (Pass = 0; Pass < Npasses; Pass++)
      {
         for ( k = 0; k < N; k++ )
            Tree.Insert ( rand() );
         Height = Tree.Height();
         AvgDepth = Tree.AvgDepth();
         SigmaHt += Height;
         SigmaDp += AvgDepth;
         Tree.Empty();
      }

      CPUsecs = double(clock()-Start) / CLOCKS_PER_SEC;

      cout << N << ','
           << SigmaHt / Npasses << ','
           << SigmaDp / Npasses << ','
           << CPUsecs << endl;

      Fout << N << ','
           << SigmaHt / Npasses << ','
           << SigmaDp / Npasses << ','
           << CPUsecs << endl;
   }
}