/* Driving main program to test the BST_K function Entry_k

   Author:  Timothy Rolfe

   Based on user input of a size N, the program generates a
   random BST containing the numbers 1 through N.  This BST
   is then used to test finding all N entries, plus two
   failure cases [entry -1 and entry N].
*/
#include <iostream.h>   // cout & co.
#include <iomanip.h>    // setw
#include <stdlib.h>     // atoi, srand, rand
#include <time.h>       // time for srand(time(NULL))
#include "BST_k.h"      // This will pull in "BST.h" itself

// Swap routine used in the shuffling module
inline void Swap ( int &p, int &q )
{  int t = p;  p = q;  q = t;  }

int main ( int argc, char* argv[] )
{  BST_k Tree;
   int Size = 0,   // Total size
       k,          // Loop variable
      *X = NULL;   // Array for random values

   cout << "Size:  " << flush;
// Allow for a command-line argument
   if ( argc > 1 )
   {  Size = atoi(argv[1]);  cout << Size << endl;  }
   else
   {  cin >> Size;  cin.ignore(255, '\n');  }

   while ( Size < 2 )
   {  if (cin.fail())
      {  cout << "Please enter a valid number:  ";
         cin.clear();
         cin.ignore(255, '\n');
      }
      else
         cout << Size << "is inappropriate.\n"
              << "Enter a number greater than 1:  ";
      cin  >> Size ;
   }

   X = new int[Size*3];
   if ( X == NULL )
   {  cout << "Memory failure.  Aborting." << endl;  exit(-1);  }

   for ( k = 0; k < Size*3 ; k++ )
      X[k] = k+1;                 // Fill with values 1 through Size

// Chance start to the rand() sequence.
   srand(time(NULL));
// Array shuffling module, with simultaneous BST generation
   for ( k = Size*3; k > Size*2; k-- ) // Final one does Tree.Insert(X[0]).
   {  int j = int ( double(k) * rand() / (1.0 + RAND_MAX) );
      Tree.Insert(X[j]);          // Insert into the BST
      Swap ( X[j], X[k-1] );      // Move out of the active array
   }
   delete [] X;                   // Return the space to the heap

   cout << "Random BST generated:\n";
   Tree.Walk();
// "BST_k.h" contains #define lines for OPT_1 and OPT_2 for extra credit
#if   defined(OPT_1)
   cout << "Extra credit option 1\n";
#elif defined(OPT_2)
   cout << "Extra credit option 2\n";
#else
   cout << "Base-case option\n";
#endif

// Module to test a failure case, all success cases, and a failure case
   for ( k = -1; k <= Size; k++ )
   {  BasePtr Node = Tree.Entry_k(k);

      cout << "Entry " << setw(2) << k << ":  ";
      if ( Node == NULL )
         cout << "NONE" << endl;
      else
         cout << Node->Data << endl;
   }
   cout << "Press <ENTER> to exit:  " << flush;
   cin.ignore(255, '\n');
   return 0;
}