/* BSTexercise.cpp */

#include <iostream.h>
#include "BST.h"

void TreeExer( BST &Tree);   // Note reference parameter

int main ( void )            // Begin TINY main
{
   {  BST Tree;

      TreeExer(Tree);
   }                         // Extra scope to see destruction of Tree
   return 0;
}                            // END TINY MAIN

// NOTE:  nonmember function to exercise a binary search tree
void TreeExer( BST &Tree)    // Note reference parameter
{  BaseCell *TreePtr;             // Find returns a cell pointer
   char    LineIn[255];           // getline used for user interaction
   int     Value;                 // decoded via "atoi"

   cout << "\nBuilding the binary search tree\n";
   while (1)                      // Will break out on input of 666
   {  cout << "Value (666 exits):  " << flush;
      cin.getline(LineIn, 255);
      Value = atoi(LineIn);
      if (Value == 666)
         break;
      Tree.Insert(Value);
      Value = Tree.Size();   // For debugging convenience.
      cout << "Tree (size " << Value << ") after insert:\n";
      Tree.Walk();
   }

   cout << "\nExercising non-recursive tree traversals\n";
   cout << "\nWeiss'  pre-order traversal:\n";
   Tree.TstNR(1);
   cout << "\nCarrano's  in-order traversal:\n";
   Tree.TstNR(2);
   cout << "\nWeiss' post-order traversal:\n";
   Tree.TstNR(3);
   cout << "\nPress <ENTER> to continue: " << flush;
   cin.ignore(255, '\n');

   cout << "\nExercising Find and Delete on the tree\n";
   while (1)                      // Will break out on input of 666
   {  cout << "Value (666 exits):  " << flush;
      cin.getline(LineIn, 255);
      Value = atoi(LineIn);
      if (Value == 666)
         break;
      TreePtr = Tree.Find(Value);
      if (TreePtr)
      {  cout << "Found";
         if (TreePtr->Left)
            cout << " left child " << TreePtr->Left->Data;
         else
            cout << " no left child";
         if (TreePtr->Right)
            cout << " right child " << TreePtr->Right->Data;
         else
            cout << " no right child";
         cout.put('\n');

         cout << "Do you wish it deleted?  (Y/N) " << flush;
         LineIn[0] = cin.get();
         cin.getline(LineIn+1, 254);   // Rest of the line
         if ( toupper(*LineIn) == 'Y' )
         {  Tree.Delete(Value);
            Value = Tree.Size();
            cout << "Tree (size " << Value << ") after delete:\n";
            Tree.Walk();
         }
      }
      else
         cout << "Not found in the tree" << endl;
   }
   cout << "\nAverage depth of nodes:  " << Tree.AvgDepth()
        << "\n           Tree height:  " << Tree.Height() << endl;
   Tree.Empty();
   cout << "\nTree has been emptied:"
        << "\nAverage depth of nodes:  " << Tree.AvgDepth()
        << "\n           Tree height:  " << Tree.Height() << endl;
   cout << "\nPress ENTER to exit.\t";  cin.ignore(255, '\n');
}