//
//  File:    time_main.C
//  Author:  Chuck Stewart
//
//  Purpose: To experimentally compare unbalanced BST's,  AVL trees
//  and STL sets, which are implemented as red-black trees.   The
//  performance is similar for randomly ordered input but not for
//  increasing input. 
//  

#include <stdlib.h>

#include <algorithm>
#include <vector>
#include <set>
#include <iostream>
using namespace std;

#include "BSTree.h"

int 
main(int argc, char * argv[])
{
   int i, n;
   if ( argc != 2 ) {
     cerr << "\nUsage: " << argv[0] << " number of integers to insert.\n";
     return 0;
   }
   n = atoi( argv[1] );
   const int num_stars = 50;
   int increment = n/num_stars;

   vector<int> shuffled(n);
   for ( i=0; i<n; i++ ) shuffled[i] = i;
   random_shuffle( shuffled.begin(), shuffled.end() );

   BSTree<int> avl_int(true);
   BSTree<int> unbal_bst_int(false);
   set<int, less<int> > set_int;

   cout << "\nInserting " << n
	<< " randomly shuffled integers into an AVL tree,\n"
	<< "an STL set and a binary search tree with no balancing\n";

   cout << "AVL tree:        ";
   for ( i=0; i<n; i++ ) {
     if ( i%increment == 0 ) { cout << "*"; flush(cout); }
     avl_int.Insert( shuffled[i] );
   }

   cout << "\nSTL set:         ";
   for ( i=0; i<n; i++ ) {
     if ( i%increment == 0 ) { cout << "*"; flush(cout); }
     set_int.insert( shuffled[i] );
   }

   cout << "\nUnbalanced BST:  ";
   for ( i=0; i<n; i++ ) {
     if ( i%increment == 0 ) { cout << "*"; flush(cout); }
     unbal_bst_int.Insert( shuffled[i] );
   }
   cout << "\nDone" << endl;

   cout << "\nAfter emptying the data sets, " << n << " integers will be inserted\n"
	<< "in increasing order into an AVL tree, an STL set and a binary\n"
	<< "search tree with no balancing.\n";
   avl_int.Make_Empty();
   set_int.erase( set_int.begin(), set_int.end() );
   unbal_bst_int.Make_Empty();

   cout << "AVL tree:        ";
   for ( i=0; i<n; i++ ) {
     if ( i%increment == 0 ) { cout << "*"; flush(cout); }
     avl_int.Insert( i );
   }

   cout << "\nSTL set:         ";
   for ( i=0; i<n; i++ ) {
     if ( i%increment == 0 ) { cout << "*"; flush(cout); }
     set_int.insert( i );
   }

   cout << "\nUnbalanced BST:  ";
   for ( i=0; i<n; i++ ) {
     if ( i%increment == 0 ) { cout << "*"; flush(cout); }
     unbal_bst_int.Insert( i );
   }
   cout << "\nDone" << endl;
   return 0;
}