/* Monte Carlo program for Binary Search Tree with random insert/deletes

   Author:  Timothy Rolfe
            Experimentally determining a quantity
            requested by Steve Simmons

   Generate an initial random binary search tree of given size.

   Perform random delete/insert operations in pairs, tracking the
   root height as a function of time.
*/
#include <iostream.h>
#include <fstream.h>    // uses an ofstream
#include <iomanip.h>    // uses setw
#include <stdlib.h>     // uses rand (through ran0)
#include <string.h>     // strcpy
#include <time.h>       // and srand will use time
#include <math.h>       // uses log
#include "BST.h"        // NOTE:  Defines the structs and classes

//#define PRETTY          // Pretty print depends on ANSI.SYS
#ifdef __TURBOC__
#include <conio.h>
#else
void gotoxy(int X, int Y)
{
   cout << "\033[" << Y << ';' << X << 'H' << flush;
}

void clrscr()
{
   gotoxy(1,1);
   cout << "\033[J" << flush;
}
#endif    // ifdef __TURBOC__

//#define DEBUG           // Enable to watch the individual permutations

// Open an output file --- given initial trial file name
void OpenOutput (ofstream &Fout, char Name[]);

// Generate a screen snap-shot (updated bar graph)
void Snap (int Ht);

// Generate a random vector of values (of length n)
void RandVect(int  *v, int n);

void Simulate (ofstream &, BST &, int Nnodes,
               int *Entries, long Npasses);

// Adjusted random number generator from Numerical Recipes
float ran0( long int &idum );

void main ( int argc, char* argv[] )
{
   int  Nnodes,    // Tree size: initial, and after a delete/insert pair
        Idx,       // Loop variable for building the tree
        Ntrees;    // Total number of trees to run
   int *Entries;   // Keep array of values in the tree for deletes
   long Npasses;
   BST  Tree;      // Pass from main to routines
   char OutFile[80];
   ofstream Fout;

   srand(time(NULL));

   clrscr();       // either from conio.h or ANSIterm.h

   cout << "Tracking the root height of a BST as a function of the\n"
        << "number of random delete/insert operations performed.\n"
        << "Output file formatted for spreadsheet use (.CSV)\n\n";

   cout << "Initial tree size:  ";
   if (argc < 2)
      cin  >> Nnodes;
   else
   {  Nnodes = atoi(argv[1]); cout << Nnodes << endl; }
   cout << " # insert/deletes:  ";
   if (argc < 3)
      cin  >> Npasses;
   else
   {  Npasses = atol(argv[2]); cout << Npasses << endl;  }
   cout << "   # trees to run:  ";
   if (argc < 4)
   {  cin  >> Ntrees; cin.ignore(255, '\n'); }
   else
   {  Ntrees = atoi(argv[2]); cout << Ntrees << endl;  }
   if (cin.fail())
   {  cerr << "Illegal input.  Bye!" << endl; exit(-9); }
   cout << " Output file name:  ";
   if (argc < 5)
      cin.getline(OutFile, 80);
   else
   {  strcpy(OutFile, argv[4]); cout << argv[4] << endl; }

   OpenOutput (Fout, OutFile);

// Header information in the .CSV file
   Fout << "Tree size:," << Nnodes
        << ", N. ins/del pairs," << Npasses << endl << endl
        << "Index, In.Ht.,In.Dpth,Fin.Ht,Fin.Dpth" << endl;

   Entries = new int [Nnodes];    // Allocate space for entry list

   for (Idx = 0; Idx < Ntrees; Idx++)
   {
      Fout << setw(9) << Idx+1 << ",";
      Simulate (Fout, Tree, Nnodes, Entries, Npasses);
   }

   Fout.close();

   gotoxy (1, 23);
   cout << "Press ENTER to exit:  ";
   cin.ignore(255, '\n');
}

// Open an output file --- given initial trial file name
void OpenOutput (ofstream &Fout, char Name[])
{
   Fout.open (Name);

   while ( Fout.fail() )
   {
      Fout.clear();
      cout << "Open failed for " << Name << " --- Try again.\n"
           << "Output file name:  " << flush;
      cin.getline(Name, 80);
      Fout.open (Name);
   }
}

void Pause()
{
   clock_t Nxt = clock() + CLOCKS_PER_SEC/8;

   while ( clock() < Nxt )
      ;
}

// Generate a screen snap-shot whenever the Ht changes
void Snap (int Ht)
{
   static long Pass = 1;
   static int Nd;
   int Idx;        // Bar graph update loop

// Initialization call
   if ( Ht < 0 )
   {
      clrscr();
      Pass = 1;
      Nd = 10;
      return;
   }

   Ht = Ht + 10;   // Adjust column position

   if (Ht > Nd)
   {
      gotoxy (1, 12);
      cout << setw(8) << Pass
           << "\nHt." << setw(5) << Ht;

      gotoxy(Nd, 12);

      while ( ++Nd <= Ht )
         cout.put('*');
      cout.flush();
      Pause();
   }
   else if (Ht < Nd)
   {
      gotoxy (1, 12);
      cout << setw(8) << Pass
           << "\nHt." << setw(5) << Ht;

      gotoxy(Ht, 12);
      for ( Idx = Ht ; Idx <= Nd ; Idx++ )
         cout.put(' ');
      cout.flush();
      Nd = Ht;
      Pause();
   }

   Pass++;
}

// Generate a random vector of values (of length n)
void RandVect(int  *v, int n)
{
// First call will initialize the random number system
   static long idum = -time(NULL);
   int Idx;

   for (Idx = 0; Idx < n; Idx++)
      *v++ = int(ran0(idum) * (n << 3));    // n*8 should make dup.s unlikely
}

void Simulate (ofstream &Fout, BST &Tree, int Nnodes,
               int *Entries, long Npasses)
{
   int Idx;
   long dmy = -time(NULL);   // required by ran0

   RandVect (Entries, Nnodes);    // Fill with random values.

// Build the initial tree.
   for (Idx = 0; Idx < Nnodes; Idx++)
      Tree.Insert(Entries[Idx]);

#ifdef PRETTY
   Snap(-1);       // Initialize the snap-shot generator
#endif

   Fout << setw(4) << Tree.Height() << ","
        << setw(6) << Tree.AvgDepth() << flush;

   while ( Npasses-- )
   {
      Idx = int(ran0(dmy) * Nnodes);
      if (Idx >= Nnodes) Idx = Nnodes - 1;  // SHOULDN'T need this
      Tree.Delete(Entries[Idx]);
//    Nnodes*8 should make duplicates unlikely
      Entries[Idx] = int(ran0(dmy) * (Nnodes << 3));
      Tree.Insert(Entries[Idx]);
#ifdef PRETTY
      Snap (Tree.Height());
#endif
   }

   Fout.precision(3);
   Fout.setf(ios::fixed | ios::showpoint);

   Fout << "," << setw(4) << Tree.Height()
        << "," << setw(6) << Tree.AvgDepth() << endl;

   Tree.Empty();
}


/* The following code is taken (with some alterations/revisions) from
   Numerical Recipes --- specifically the section on random numbers.
*/
enum {N_SLOTS = 97};

float ran0( long int &idum )
{
   static double y, maxran, v[N_SLOTS];
   static int iff=0;
   int j;
   void nrerror();

   if (idum < 0 || iff == 0)
   {
      iff = 1;
      maxran = 1.0 + RAND_MAX;
//      srand(idum);             NOTE:  Done by the main.  Do NOT do here
      idum = 1;
      for (j=0; j<N_SLOTS; j++) y    = rand();   // Discard first batch
      for (j=0; j<N_SLOTS; j++) v[j] = rand();
      y = rand();
   }
   j = int(N_SLOTS*y / maxran);
// Enforce the range 0 not quite to 97:  avoid minor hiccups!  --- tjr
   j = (j >= N_SLOTS ? N_SLOTS-1 : (j > 0 ? j : 0));
   y=v[j];
   v[j] = rand();
   return float(y/maxran);
}