// ------------------------------- //
// -------- Start of File -------- //
// ------------------------------- //
// ----------------------------------------------------------- // 
// C++ Source Code File Name: testprog.cpp
// Compiler Used: MSVC, BCC32, GCC, HPUX aCC, SOLARIS CC
// Produced By: glNET Software
// File Creation Date: 11/07/1996
// Date Last Modified: 08/22/2001
// Copyright (c) 2001 glNET Software
// ----------------------------------------------------------- // 
// ------------- Program description and details ------------- // 
// ----------------------------------------------------------- // 
/*
This library is free software; you can redistribute it and/or
modify it under the terms of the GNU Lesser General Public
License as published by the Free Software Foundation; either
version 2.1 of the License, or (at your option) any later version.
 
This library is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
Lesser General Public License for more details.

You should have received a copy of the GNU Lesser General Public
License along with this library; if not, write to the Free Software
Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  
USA

Test program for the generic binary search tree class.
*/
// ----------------------------------------------------------- // 
#include <iostream.h>
#include <stdio.h>
#include <time.h>
#include <fstream.h>
#include "gxbstree.h"
#include "bstreei.h"
#include "ustring.h"

#ifdef __MSVC_DEBUG__
#include "leaktest.h"
#endif

void InputData(UString &sbuf)
// Input a line of text from the console
{
  char buf[255];
  cout << "Input Data: ";
  cin.getline(buf, sizeof(buf));
  unsigned len = 0;
  sbuf = buf;
}

void ClearInputStream(istream &s)
// Used to clear istream
{
  char c;
  s.clear();
  while(s.get(c) && c != '\n') { ; }
}

int Quit()
// Terminate the program
{
  cout << "Exiting..." << endl;
  return 0;
}

void PausePrg()
// Pause the program 
{
  cout << endl;
  cout << "Press enter to continue..." << endl;
  cin.get();
}

void Menu(void)
// List the program options
{
  cout << "(A, a)    Add an item to the tree" << endl;
  cout << "(B, b)    Build a tree of strings" << endl;
  cout << "(C, c)    Clear the tree" << endl;
  cout << "(D, d)    Delete an item from the tree" << endl;
  cout << "(E, e)    Extract all the node in sort order" << endl;
  cout << "(F, f)    Find an item in the tree" << endl;
  cout << "(H, h, ?) Help (prints this menu)" << endl; 
  cout << "(I, i)    Import a dictionary file" << endl; 
  cout << "(L, l)    List tree items in order" << endl;
  cout << "(Q, q)    Quit this program" << endl;
  cout << "(S, s)    Display the tree statistics" << endl;
  cout << "(R, r)    Extract all the node in reverse order" << endl;
  cout << "(T, t)    Test tree insertion/deletion times" << endl;
}

unsigned TreeHeight(gxBStreeNode_t *node)
// Recursive function used to calculate the tree height based
// on the maximum of the height of right and left subtrees.
{
  unsigned height = 0;
  if(node != 0) {
    unsigned left_height = TreeHeight(node->left);
    unsigned right_height = TreeHeight(node->right);
    if(left_height > right_height) {
      height = left_height+1;
    }
    else {
      height = right_height+1;
    }
  }
  return height;
}

void NumNodes(gxBStreeNode_t *node, unsigned &num_nodes)
// Recursive function used to calculate the total number of nodes.
{
  while(node) {
    NumNodes(node->left, num_nodes);
    num_nodes++;
    node = node->right;
  }
}

void TreeStats(gxBStree<UString> &tree)
{
  cout << endl;
  cout << "----- Binary search tree statistics -----" << endl;
  cout << endl;
  if(tree.IsEmpty()) {
    cout << "The tree is empty" << endl;
    return;
  }
  unsigned num_nodes = 0;
  unsigned height = 0;

  NumNodes(tree.GetRoot(), num_nodes);
  height = TreeHeight(tree.GetRoot());
  
  cout << "Number of nodes =   " << num_nodes << endl;
  cout << "Height          =   " << height << endl;

  cout << endl;
  UString root, first, last;
  
  cout << "Root node = " << tree.GetRoot()->data << endl;
  if(tree.FindFirst(first))
    cout << "First key = " << first << endl;

  if(tree.FindLast(last))
    cout << "Last key  = " << last << endl;
  cout << endl;
}

void ImportDictionaryFile(gxBStree<UString> &tree)
// Import a list of words in sort order. This function demonstrates
// how unbalanced trees are degenerated when a sort ordered list of
// items are inserted into the tree.
{
  cout << endl;
  cout << "Importing a dictionary file." << endl;

  tree.Clear(); // Clear the tree before importing the file
  
  const int MaxLine = 255;
  char LineBuffer[MaxLine];
  int status, i, key_count = 0;
  UString key;
  UString FileName;
  
  cout << endl;
  cout << "Enter the name of the text file to import" << endl;
  InputData(FileName);

  // Open dictionary file file
#ifdef __BCC32__
  // The BCC 32 ios class does not have an enumeration for "nocreate"
  ifstream infile(FileName.c_str(), ios::in);
#else
  ifstream infile(FileName.c_str(), ios::in|ios::nocreate);
#endif
  if(!infile) { // Could not open the istream
    cout << "Could not open file: " << FileName << endl;
    return;
  } 
  
  cout << "Adding words..." << endl;

  // Get CPU clock cycles before entering loop
  clock_t begin = clock();

  while(!infile.eof()) {
    for(i = 0; i < MaxLine; i++) LineBuffer[i] = '\0';
    infile.getline(LineBuffer, MaxLine);
    
    for(i = 0; i < MaxLine; i++) { // Get rid of the end of line sequence
      if((LineBuffer[i] == '\r') || (LineBuffer[i] == '\n')) {
	LineBuffer[i] = '\0';
	break;
      }
    }
    
    if(infile.eof()) break; // Exit loop at EOF
    if(strcmp(LineBuffer, "") == 0) continue;

    key = LineBuffer;
    cout << key.c_str() << endl;
    status = tree.Insert(key);
    if(status != 1) {
      cout << endl << "Problem adding " << key << endl;
      return;
    }
    else {
      key_count++;
    }
  }
  
  // Get CPU clock cycles after loop is completed 
  clock_t end =clock();
  
  // Calculate the elapsed time in seconds. 
  double elapsed_time = (double)(end - begin) / CLOCKS_PER_SEC;
  cout.precision(3); 
  cout << "Added " << key_count << " words in " 
       << elapsed_time << " seconds" << endl;

  // Rewind the file
#ifdef __BCC32__
  infile.close();
  infile.open(FileName.c_str(), ios::in);
#else
  infile.seekg(0, ios::beg);
  infile.clear();
#endif

  cout << "Verifying the entries..." << endl;
  begin = clock();
  key_count = 0;
  double search_time = 0;

  while(1) {
    for(i = 0; i < MaxLine; i++) LineBuffer[i] = '\0';
    infile.getline(LineBuffer, MaxLine);
    
    for(i = 0; i < MaxLine; i++) { // Get rid of the end of line sequence
      if((LineBuffer[i] == '\r') || (LineBuffer[i] == '\n')) {
	LineBuffer[i] = '\0';
	break;
      }
    }
    
    if(infile.eof()) break; // Exit loop at EOF
    if(strcmp(LineBuffer, "") == 0) continue;

    key = LineBuffer;
    clock_t begin_search = clock();
    status = tree.Find(key);
    clock_t end_search = clock();
    search_time += (double)(end_search - begin_search) / CLOCKS_PER_SEC;

    if (status != 1) {
      cout << endl << "Problem finding " << key << endl;
      return;
    }
    else {
      key_count++;
    }
  }

  end =clock();
  elapsed_time = (double)(end - begin) / CLOCKS_PER_SEC;
  cout.precision(3);
  cout << "Verified " << key_count << " words in " 
       << elapsed_time << " seconds" << endl;
  double avg_search_time = (search_time/(double)key_count) * 1000;
  cout << "Average search time = " << avg_search_time << " milliseconds"
       << endl;
  PausePrg();

  // Rewind the file
#ifdef __BCC32__
  infile.close();
  infile.open(FileName.c_str(), ios::in);
#else
  infile.seekg(0, ios::beg);
  infile.clear();
#endif

  cout << "Deleting the entries..." << endl;
  begin = clock();
  key_count = 0;
  while(1) {
    for(i = 0; i < MaxLine; i++) LineBuffer[i] = '\0';
    infile.getline(LineBuffer, MaxLine);
    
    for(i = 0; i < MaxLine; i++) { // Get rid of the end of line sequence
      if((LineBuffer[i] == '\r') || (LineBuffer[i] == '\n')) {
	LineBuffer[i] = '\0';
	break;
      }
    }
    
    if(infile.eof()) break; // Exit loop at EOF
    if(strcmp(LineBuffer, "") == 0) continue;

    key = LineBuffer;
    status = tree.Delete(key);

    if (status != 1) {
      cout << endl << "Problem deleting " << key << endl;
      return;
    }
    else {
      key_count++;
    }
  }

  end =clock();
  cout.precision(3);
  elapsed_time = (double)(end - begin) / CLOCKS_PER_SEC;
  cout << "Deleted " << key_count << " words in " 
       << elapsed_time << " seconds" << endl;

  // Rewind the file
#ifdef __BCC32__
  infile.close();
  infile.open(FileName.c_str(), ios::in);
#else
  infile.seekg(0, ios::beg);
  infile.clear();
#endif

  cout << "Re-inserting all the words..." << endl;
  key_count = 0;
  begin = clock();

  while(1) {
    for(i = 0; i < MaxLine; i++) LineBuffer[i] = '\0';
    infile.getline(LineBuffer, MaxLine);
    
    for(i = 0; i < MaxLine; i++) { // Get rid of the end of line sequence
      if((LineBuffer[i] == '\r') || (LineBuffer[i] == '\n')) {
	LineBuffer[i] = '\0';
	break;
      }
    }
    
    if(infile.eof()) break; // Exit loop at EOF
    if(strcmp(LineBuffer, "") == 0) continue;

    key = LineBuffer;
    status = tree.Insert(key);
    
    if (status != 1) {
      cout << endl << "Problem adding " << key << endl;
      return;
    }
    else {
      key_count++;
    }
  }
  
  end =clock();
  cout.precision(3);
  elapsed_time = (double)(end - begin) / CLOCKS_PER_SEC;
  cout << "Added " << key_count << " words in " 
       << elapsed_time << " seconds" << endl;

  infile.close();
  return;
}

void BuildTree(gxBStree<UString> &tree)
// Build a tree of strings.
{
  char *aa1 = "dog";
  char *bb1 = "cat";
  char *cc1 = "fish";
  char *dd1 = "mouse";
  char *ee1 = "bird";
  char *ff1 = "pig";
  char *gg1 = "horse";
  char *hh1 = "lion";
  char *ii1 = "snake";
  char *jj1 = "cow";
  char *kk1 = "armadillo";
  char *ll1 = "grouper";
  char *mm1 = "rat";
  char *nn1 = "monkey";
  char *oo1 = "zebra";
  char *pp1 = "starfish";
  char *qq1 = "lizard";
  char *rr1 = "crab";
  char *ss1 = "snail";
  char *tt1 = "gorilla";
  char *uu1 = "lobster";
  char *vv1 = "turkey";
  char *ww1 = "beetle";
  char *xx1 = "shark";
  char *yy1 = "clam";
  char *zz1 = "oyster";

  const int NKEYS = 26;
  char *keys[26] = { aa1, bb1, cc1, dd1, ee1, ff1, gg1, hh1, ii1, jj1,
		     kk1, ll1, mm1, nn1, oo1, pp1, qq1, rr1, ss1, tt1,
		     uu1, vv1, ww1, xx1, yy1, zz1 };
  
  const int INSERTIONS = 26; // Number of keys to insert
  UString key;
  int i, status;

  tree.Clear();
  
  cout << "Inserting " << INSERTIONS << " keys..." << endl;
  for(i = 0; i < INSERTIONS; i++) {
    key = keys[i];  

    status = tree.Insert(key);
    
    if(status != 1) {
      cout << endl << "Problem adding " << keys[i] << " - " << i << endl;
      return;
    }
  }
  TreeStats(tree);
}

void TestTree(gxBStree<UString> &tree)
// Test the tree insertion and deletion times.
{
  // Adjust this number to set the number of insertions
  // const unsigned long INSERTIONS = 1 * 1000;       // 1K test
  // const unsigned long INSERTIONS = 10 * 1000;      // 10K test
  const unsigned long INSERTIONS = 100 * 1000;     // 100K test
  // const unsigned long INSERTIONS = 1000 * 1000;    // 1MEG test
  // const unsigned long INSERTIONS = 10000 * 1000;   // 10MEG test
  // const unsigned long INSERTIONS = 100000 * 1000;  // 100MEG test
  // const unsigned long INSERTIONS = 1000000 * 1000; // 1GIG test

  cout << "Inserting " << INSERTIONS << " keys..." << endl;
  unsigned long i, key_count = 0;
  unsigned long curr_count = 0;
  int status;
  int verify_deletions = 0; // Set to ture to verify all deletions
  double insert_time = 0;
  const char *name = "Item";
  char sbuf[255];
  UString key;
  
  // Get CPU clock cycles before entering loop
  clock_t begin = clock();

  for(i = 0; i < INSERTIONS; i++) {
    sprintf(sbuf, "%s %d", name, i);
    key = sbuf;
    clock_t begin_insert = clock();
    status = tree.Insert(key);
    clock_t end_insert = clock();
    insert_time += (double)(end_insert - begin_insert) / CLOCKS_PER_SEC;
    key_count++;
    curr_count++;

    if(status != 1) {
      cout << endl << "Problem adding key - " << key << endl;
      return;
    }
    if(curr_count == 10000) {
      curr_count = 0;
      cout << "Inserted " << i << " keys in " << insert_time
	   << " seconds" << endl;
    }

  }

  // Get CPU clock cycles after loop is completed 
  clock_t end =clock();

  // Calculate the elapsed time in seconds. 
  double elapsed_time = (double)(end - begin) / CLOCKS_PER_SEC;
  cout.precision(3); 
  cout << "Inserted " << key_count << " values in " 
       << elapsed_time << " seconds" << endl;
  double avg_insert_time = (insert_time/(double)key_count) * 1000;
  cout << "Average insert time = " << avg_insert_time << " milliseconds"  
       << endl; 

  key_count = 0;
  double search_time = 0;
  cout << "Verifying the insertions..." << endl;
  begin = clock();
  for(i = 0; i < INSERTIONS; i++) {
    sprintf(sbuf, "%s %d", name, i);
    key = sbuf;
    clock_t begin_search = clock();
    status = tree.Find(key);
    clock_t end_search = clock();
    key_count++;
    search_time += (double)(end_search - begin_search) / CLOCKS_PER_SEC;
    
    if(status != 1) {
      cout << "Error finding key - " << key << endl;
      return;
    }
  }

  end =clock();
  elapsed_time = (double)(end - begin) / CLOCKS_PER_SEC;
  cout.precision(3);
  cout << "Verified " << key_count << " values in " 
       << elapsed_time << " seconds" << endl;
  double avg_search_time = (search_time/(double)key_count) * 1000;
  cout << "Average search time = " << avg_search_time << " milliseconds"
       << endl;

  cout << "Deleting all the entries..." << endl;
  key_count = 0;
  double delete_time = 0;
  begin = clock();
  for(i = 0; i < INSERTIONS; i++) {
    sprintf(sbuf, "%s %d", name, i);
    key = sbuf;
    clock_t begin_delete = clock();
    status = tree.Delete(key);
    clock_t end_delete = clock();
    delete_time += (double)(end_delete - begin_delete) / CLOCKS_PER_SEC;
    key_count++;
    if(status != 1) {
      cout << "Error deleting key - " << key << endl;
      return;
    }

    if(verify_deletions) { // Verify the remaining key locations
      for(unsigned long j = INSERTIONS-1; j != i; j--) {
	sprintf(sbuf, "%s %d", name, j);
	key = sbuf;
	status = tree.Find(key);
	if(status != 1) {
	  cout << "Error finding key  - " << j << endl;
	  cout << "After deleting key - " << i << endl;
	  return;
	}
      }
    }
  }

  end =clock();
  cout.precision(3);
  elapsed_time = (double)(end - begin) / CLOCKS_PER_SEC;
  cout << "Deleted " << key_count << " values in " 
       << elapsed_time << " seconds" << endl;
  double avg_delete_time = (delete_time/(double)key_count) * 1000;
  cout << "Average delete time = " << avg_delete_time << " milliseconds"
       << endl;

  cout << "Re-inserting " << INSERTIONS << " keys..." << endl;
  key_count = 0;
  insert_time = 0;
  begin = clock();
  for(i = 0; i < INSERTIONS; i++) {
    sprintf(sbuf, "%s %d", name, i);
    key = sbuf;
    clock_t begin_insert = clock();
    status = tree.Insert(key);
    clock_t end_insert = clock();
    insert_time += (double)(end_insert - begin_insert) / CLOCKS_PER_SEC;
    key_count++;
    curr_count++;

    if(status != 1) {
      cout << endl << "Problem adding key - " << key << endl;
      return;
    }
  }
  end =clock();
  elapsed_time = (double)(end - begin) / CLOCKS_PER_SEC;
  cout.precision(3); 
  cout << "Inserted " << key_count << " values in " 
       << elapsed_time << " seconds" << endl;
  avg_insert_time = (insert_time/(double)key_count) * 1000;
  cout << "Average insert time = " << avg_insert_time << " milliseconds"  
       << endl; 
}

void ListInOrder(gxBStree<UString> &tree)
// List all the tree nodes using a tree iterator object.
{
  gxBStreeNode<UString> *node = tree.GetRoot();
  gxBStreeIterator tree_iterator(node);
  while((node = (gxBStreeNode<UString> *)tree_iterator.GetNext()) != 0) {
    cout << node->data << endl;
  }
  cout << endl;
}

void ExtractInOrder(gxBStree<UString> &tree)
// Extract all the tree nodes in sort order.
{
  UString key;
  while(!tree.IsEmpty()) {
    tree.ExtractFirst(key);
    cout << key << endl;
  }
}

void ExtractInReverseOrder(gxBStree<UString> &tree)
// Extract all the tree nodes in reverse order.
{
  UString key;
  while(!tree.IsEmpty()) {
    tree.ExtractLast(key);
    cout << key << endl;
  }
}

int main()
// Test program's main thread of execution
{
#ifdef __MSVC_DEBUG__
  InitLeakTest();
#endif

  Menu(); // Display the options menu
  
  char key;
  UString key_buf;
  gxBStree<UString> tree;
  int exists;
  int rv = 1;

  while(rv) {
    if (!cin) { 
       ClearInputStream(cin); 
       if (!cin) { 
          cout << "Input stream error" << endl;
          return 0;
       }
    }
    cout << '>';
    cin >> key;
    if (!cin) continue;
    switch(key) {
      case 'a' : case 'A' :
	ClearInputStream(cin);
	InputData(key_buf);
	tree.Insert(key_buf, &exists);
	if(exists) {
	  cout << "An entry for " << key_buf << " already exists" << endl;
	}
	break;

      case 'b' : case 'B' :
	ClearInputStream(cin);
	BuildTree(tree);
	break;

      case 'c' : case 'C' :
	ClearInputStream(cin);
	tree.Clear();
	break;

      case 'd' : case 'D' :
	ClearInputStream(cin);
	InputData(key_buf);
	if(tree.Delete(key_buf)) {
	  cout << "Removed " << key_buf << endl;
	}
	else {
	  cout << key_buf << " does not exists in the tree" << endl;
	}
	break;

      case 'e' : case 'E' :
	ClearInputStream(cin);
	ExtractInOrder(tree);
	break;

      case 'r' : case 'R' :
	ClearInputStream(cin);
	ExtractInReverseOrder(tree);
	break;

      case 'f' : case 'F' :
	ClearInputStream(cin);
	InputData(key_buf);
	if(tree.Find(key_buf)) {
	  cout << "Found entry " << key_buf << endl;
	}
	else {
	  cout << key_buf << " does not exists in the tree" << endl;
	}
	break;	
      case 'l' : case 'L' : 
	ClearInputStream(cin);
	ListInOrder(tree);
	break;	 

      case 's' : case 'S' :
	ClearInputStream(cin);
	TreeStats(tree);
	break;

      case 'i' : case 'I' :
	ClearInputStream(cin);
	ImportDictionaryFile(tree);
	break;

      case 'q' : case 'Q' :
	tree.Clear();
	rv = Quit();
	break;

      case 't' : case 'T' :
	ClearInputStream(cin);
	TestTree(tree);
	break;

      case '?' : case 'h' : case 'H' :
	ClearInputStream(cin);
	Menu();
	break;

      default:
        cout << "Unrecognized command" << endl;
    }
  }
  
  return 0;
}
// ----------------------------------------------------------- // 
// ------------------------------- //
// --------- End of File --------- //
// ------------------------------- //