/* BST.cpp */

/* Binary Search Tree class

   Author:  Timothy Rolfe

   Data Organization (struct)
      Data area  --- implemented here as a minimal single integer
      Left link  --- left subtree
      Right link --- right subtree

      Note:  constructor and destructor also declared for the struct

   Data Structure (class) BST --- binary search tree

      public member functions:

      constructor --- for the list/tree itself
      destructor  --- ditto
      Walk        --- traverse the data structure, showing the values
                      in increasing order.
      Insert      --- insert one cell into the data structure
      Find        --- find, based on data value; returns pointer to cell
      Delete      --- remove one cell from the data structure
      AvgDepth    --- average depth of all tree nodes
      Height      --- height of the entire tree

   NOTE:  in light of future use of this class, it has been designed
          to RECYCLE tree nodes:  rather than deleting them, they are
   entered into a "Free" list (maintained as a stack throug the Right
   link).  Consequently, when a node is inserted, it is taken from
   that Free list unless it is empty (in which case it is explicitly
   constructed).
*/

#include <iostream.h>
#include <iomanip.h>    // uses setw
#include <stdlib.h>     // uses atoi
#include <ctype.h>      // uses toupper
#include <assert.h>
#include "BST.h"        // NOTE:  Defines the structs and classes

//////////////////////////////////////////////////////////////////

BaseCell::~BaseCell (void)   // Traversal to delete done by BST
{/*cout << "Deleting " << Data << endl;*/}

//////////////////////////////////////////////////////////////////

// Generate a node, either re-using from the Free list or constructed
BasePtr BST::Build( int D, BasePtr P, BasePtr L, BasePtr R )
{  BasePtr Rtn;

   if (Free == NULL)
   {  Rtn = new BaseCell (D, P, L, R);
      if ( Rtn == NULL )
      {  cout << "Out of heap space.  Aborting execution." << endl;
         exit(7);
      }
   }
   else
   {  Rtn = Free;
      Free = Free->Right;
      Rtn->Data = D; 
      Rtn->Parent = P; Rtn->Left = L; Rtn->Right = R;
   }
   if ( L || R )        // Non-null subtree(s):  compute values
   {  Rtn->Height = NewHt(Rtn);  Rtn->Size = NewSize(Rtn);  }
   else                 // Leaf:  size and height are both one
      Rtn->Height = Rtn->Size = 1;
   return Rtn;
}

// Push Node onto Free list, then set to NULL
void BST::Recycle( BasePtr &Node )
{  Node->Right = Free;
   Free = Node;
   Node = NULL;
#ifdef DEBUG
   cout << "Recycling " << Free->Data << endl;
#endif
}

//////////////////////////////////////////////////////////////////

BST::~BST(void)      // Destructor
{  Autumn(Root);             // Traverse, deleting cells
   while (Free)              // Then empty out the Free list
   {  BasePtr Node = Free;
      Free = Free->Right;
      delete Node;           // Finally do an explicit delete
   }
}

void BST::Empty(void)      // Empty out a tree
{  Autumn(Root);  }     // Unlike ~BST, though, the tree remains

// In-order tree traversal to delete cells.  Called by ~BST.
void BST::Autumn(BasePtr &Node)
{  if (Node)
   {//Note:  Node->Right may be lost on the "delete Node"
      BasePtr Hold = Node->Right;

      Autumn(Node->Left);
      Recycle(Node);    // Note that this NULLs out Node
      Autumn(Hold);
   }
}

/******************* Recursive traversal *******************/

// Walk through the tree; display is to be ascending order
void BST::Walk(void)
{  if (Root)
   {  Nitems = 0;
      InOrder(Root);
      if (Nitems % 10)
         cout.put('\n');
   }
}

// To get ascending order, do an in-order traversal of the tree
void BST::InOrder(BasePtr Item)
{  if ( !Item ) return;                // I.e., NULL tree

   InOrder(Item->Left);                // Process Left sub-tree
   cout << setw(4) << Item->Data       // Process this node
        << '(' << Item->Height << ')';
   if ( ++Nitems % 10 == 0 )
      cout.put('\n');
   InOrder(Item->Right);               // Process Right sub-tree
}

/******************* Simple Find *******************/

// Find the cell with the data field corresponding to Value
BaseCell* BST::Find(int Value)
{  Current = Root;
   while ( Current != NULL && Current->Data != Value )
   {  if (Value < Current->Data)
         Current = Current->Left;
      else
         Current = Current->Right;
   }

   return Current;
}

/******************* Insertion *******************/

// Insert the Value into its proper place in the binary search tree
void BST::Insert(int Value)
{  Insert(Root, Value);  }

void BST::Insert(BasePtr Node, int Value)
{  if ( Node == NULL )
      Root = Build (Value, Node);
   else
      while(1)     // breaks on node creation
      {  if ( Value < Node->Data )
            if ( Node->Left != NULL )
               Node = Node->Left;
            else
            {  Node = Node->Left = Build (Value, Node);
               break;
            }
         else if ( Value > Node->Data )     
            if ( Node->Right != NULL )
               Node = Node->Right;
            else
            {  Node = Node->Right = Build (Value, Node);
               break;
            }
         else
         {  cerr << "Equal keys forbidden." << endl; break;  }
      }
   Adjust(Node);
}

/******************* Deletion *******************/

// Delete the node with the Value passed
void BST::Delete(int Value)
{  Delete(Root, Value);  }

void BST::Delete(BasePtr Node, int Value)
{  cerr << "STUB FUNCTION:  delete is currently not implemented." 
        << endl;
}

/******************* Utility functions *******************/

// Something has potentially changed node height and subtree size
void BST::Adjust(BasePtr Node)
{  while (Node)    // Follow Parent pointers all the way back
   {  Node->Height = NewHt(Node);
      Node->Size = NewSize(Node);
      Node = Node->Parent;
   }
}

// Little in-line function used in height adjustment
inline max ( int L, int R )
{ return L > R ? L : R ; }

// Return the height based on the children; Node must NOT be NULL.
int BST::NewHt ( BasePtr Node )
{  BasePtr L = Node->Left,
           R = Node->Right;

   if ( !L && !R )           // Leaf node is height 1
      return 1;
   else if (!L)
      return 1 + R->Height;  // Half node cases
   else if (!R)
      return 1 + L->Height;
   else                      // Full node --- need max
      return 1 + max(L->Height, R->Height);
}

// Return the size based on the children; Node must NOT be NULL.
int BST::NewSize( BasePtr Node )
{  BasePtr L = Node->Left,
           R = Node->Right;

   if ( !L && !R )           // Leaf node has size 1
      return 1;
   else if (!L)
      return 1 + R->Size;    // Half node cases
   else if (!R)
      return 1 + L->Size;
   else                      // Full node --- need max
      return 1 + L->Size + R->Size;
}

/******************* Miscellaneous other *******************/

// Average depth of nodes within the tree:
double BST::AvgDepth(BasePtr Node)
{  double SigmaD = 0;
   long   Nnodes = 0;

   if (Node == NULL) return 0;

// Root is at depth 1
   DepthStats (Node, 1, Nnodes, SigmaD);
   return SigmaD / Nnodes;
}

// Total number of nodes and depth of each node
void BST::DepthStats(BasePtr Node, int Deep, long &N, double &Sigma)
{  if ( Node != NULL )
   {  DepthStats(Node->Left, Deep+1, N, Sigma);
      DepthStats(Node->Right, Deep+1, N, Sigma);
      N++;
      Sigma += Deep;
   }
}