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

   Author:  Timothy Rolfe

   Dual-processor option included.  The generated csv file will very
   possibly have entries a little jumbled, and so will need sorting.

   Since the program forks after the file has been opened, both
   processes share that file and can write to it.
*/
#include <iostream.h>
#include <fstream.h>    // ofstream
#include <stdlib.h>     // exit
#include <time.h>       // clock (timing statistics)
#include "AVL.h"        // AVL class, its base class and component struct
#include "PermLib.h"    // function PermGen (permutations of char.s
/*
#define  DUAL_PROCESSOR // Build in two parallel streams (thanks to fork)
*/
#ifdef DUAL_PROCESSOR   // Presuming a Unix-like environment (like Linux)
#include <unistd.h>     // fork stuff
#endif

void main (int argc, char* argv[])
{
   AVL    Tree;
   char  *List = NULL;  // Permutations generated here
   int    k;            // Loop variable
   int    N,            // Number of nodes
          Nlim;         // Largest number to run
   long   Nfact;        // Number of permutations of those nodes
   double SigmaHt,      // Total of tree heights
          SigmaDp;      // Total of tree average depths
   int    Height;       // Individual tree height
   double AvgDepth;     // Individual tree average depth
   ofstream Fout("AllPerms.csv");    // Accumulate statistics

   cout.precision(3);

   cout << "Largest number of nodes:  ";

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

   List = new char [Nlim+1];

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

// N=1 is trivial:  height and depth of zero
   Fout << "1,1,0,0,0" << endl;
   cout << "1,1,0,0,0" << endl;

#ifdef DUAL_PROCESSOR
   pid_t Child = fork();
#endif

   for ( N = 2, Nfact = 1; N <= Nlim; N++ )
   {
      clock_t Start = clock();
      double  CPUsecs;

      Nfact *= N;  // Build next value in N!

#ifdef DUAL_PROCESSOR   // Child does odds, parent does evens
      if ( (Child == 0) ^ (N & 1) )
         continue;      // I.e., skip this go-round
#endif

      SigmaHt = SigmaDp = 0;

      while ( PermGen (List, N) )
      {
         for ( k = 0; k < N; k++ )
            Tree.Insert ( int(List[k]) );
         Height = Tree.Height();
         AvgDepth = Tree.AvgDepth();
         SigmaHt += Height;
         SigmaDp += AvgDepth;
         Tree.Empty();
      }

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

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

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