#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)
   {  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 Find and Delete on the tree\n";
   while (1)
   {  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 << endl
        << "Average depth of nodes:  " << Tree.AvgDepth() << endl
        << "           Tree height:  " << Tree.Height() << endl;
   Tree.Empty();
   cout << "\nTree has been emptied:\n"
        << "Average depth of nodes:  " << Tree.AvgDepth() << endl
        << "           Tree height:  " << Tree.Height() << endl;
}