/* BST.h */

/* Binary Search Tree class  ---  initial subset of later full class

   Author:  Timothy Rolfe

   Data Organization (struct)
      Data area   --- implemented here as a minimal single integer
      Height      --- height within the tree of THIS node
      Size        --- number of nodes in this (sub)tree
      Util        --- miscellaneous int value, should we every need it
      Parent link --- allow upward adjustment of heights
      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   **STUB**
      AvgDepth    --- average depth of all tree nodes
      Height      --- height of the entire tree
      Size        --- number of nodes in the 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).
*/

#ifndef BST_H  // Protect against multiple #include calls
#define BST_H

#include <stdlib.h>     // NULL definition
#include <iostream.h>   // ostream

typedef struct BaseCell*  BasePtr;
struct BaseCell    // Binary Search Tree
{  int     Data;   // Realistic case, this could be quite large
   int     Height; // Height of THIS NODE
   int     Size;   // Number of nodes in this (sub)tree
   int     Util;   // Generic utility area for an int value
   BasePtr Parent, // Sometimes need to move back to root
           Left, Right;   // "<" subtree and ">" subtree
   BaseCell ( int D = 0,
              BasePtr P = NULL, BasePtr L = NULL, BasePtr R = NULL )
   : Data(D), Parent(P), Left(L), Right(R), Height(1), Size(1)
   { /* nothing else! */ }
   ~BaseCell (void);    // Allow for debugging display
};

/* Binary search tree --- identical keys are forbidden.          */
class BST
{  public:
      BST(void) : Root(NULL), Free(NULL), Nitems(0)
      { /* Nothing else */ }

      void Empty(void);      // Empty out a tree
      ~BST(void);

      void    Walk(void);
      void    Insert(int);
      void    Delete(int);
      BasePtr Find(int);

      double  AvgDepth(void)
      {  return AvgDepth(Root); }
//    Height function is simple enough to implement here
      int     Height(void)   // Root = NULL means empty = 0
      {  return Root == NULL ? 0 : Root->Height;  }
//    Size function is simple enough to implement here
      int     Size(void)     // Root = NULL means empty = 0
      {  return Root == NULL ? 0 : Root->Size;  }

   protected:
//    Generate a node, either re-using from the Free list or constructed
      BasePtr Build( int D = 0, 
                     BasePtr P=NULL, BasePtr L=NULL, BasePtr R=NULL );

//    Push Node onto Free list, then set to NULL
      void Recycle( BasePtr &Node );
      void InOrder(BasePtr); // Called from Walk()

      void Autumn(BasePtr&); // In-order walk deleting nodes

      void Insert(BasePtr, int);     // Used by public Insert(int)

      void Delete(BasePtr, int);     // Used by public Delete(int)

//    Used after Insert and Delete --- which change height and size
      void Adjust(BasePtr);
      int  NewHt (BasePtr);          // Height based on child heights
      int  NewSize (BasePtr);        // Size based on child sizes

      double AvgDepth(BasePtr);

//    Total number of nodes and depth of each node
      void DepthStats(BasePtr, int, long&, double&);

      BasePtr Root,
              Current;
      int Nitems;                 // Used in the protected tree walk
      BasePtr Free;               // Nodes for re-use
};

#endif