/* This file contains the definition of class BST.

------------------------------------------------------------------*/

#include "BST.h"

/*-----------------------------------------------------------------
   This function inserts a BinTreeElement into a BST.

   Receive: Elem, the BinTreeElement being inserted
   Return:  The BST containing this function,
            with Elem inserted in the appropriate BST position
------------------------------------------------------------------*/

void BST::Insert(const BinTreeElement& Elem)
{
   if (Root == 0)            // is the BST empty?
      Root = new Node(Elem); //   yes - create a root node
   else
      Root->Insert(Elem);    //   no - pass the buck to Node::Insert()
}

/*-----------------------------------------------------------------
   This function inserts a BinTreeElement into a Node.

   Receive: Elem, the BinTreeElement being inserted
   Return:  The Node containing this function, with Elem
              inserted in the appropriate subtree position
------------------------------------------------------------------*/

void BST::Node::Insert(const BinTreeElement& Elem)
{
   if (Elem < Data)             // if Elem belongs in left subtree
      if (Left == 0)            //   if left subtree is empty
         Left = new Node(Elem); //     make Elem root of left subtree
      else                      //   else
         Left->Insert(Elem);    //     pass the buck to root of
                                //       left subtree
   else if (Elem > Data)        // if Elem belongs in right subtree
      if (Right == 0)           //   if right subtree is empty
         Right = new Node(Elem);//     make Elem root of right subtree
      else                      //   else
         Right->Insert(Elem);   //     pass the buck to root of
                                //       right subtree
   else                         // else, Elem already is in the BST
      cerr << "\n*** Insert: " << Elem
           << " is already in this tree!\n";
}

/*-----------------------------------------------------------------
   This function displays a BST.

   Receive: An ostream and a BST
	Output:  The values of the BST onto the ostream
	Return:  The ostream
----------------------------------------------------------------*/

ostream& operator<<(ostream& Out, const BST& Tree)
{
   if (Tree.Root != 0)
      Out << *(Tree.Root);

   return Out;
}

/*-----------------------------------------------------------------
   This function recursively displays a Node (and its subtrees),
   using the inorder traversal pattern.

   Receive: An ostream and a Node
   Output:  The values from the left subtree, the Node, and its
            right subtree onto the ostream, in ascending order
   Return:  The ostream
----------------------------------------------------------------*/

ostream& operator<<(ostream& Out, const BST::Node& N)
{
   if (N.Left != 0)
      Out << *(N.Left);

   Out << N.Data << ' ';

   if (N.Right != 0)
      Out << *(N.Right);

   return Out;
}

/*-----------------------------------------------------------------
   This function searches a BST for a BinTreeElement.

   Receive: Elem, the BinTreeElement being sought
   Return:  True, if Elem is in the BST containing this function,
            False, otherwise
------------------------------------------------------------------*/

Boolean BST::Search(const BinTreeElement& Elem) const
{
   if (Root == 0)                 // if the tree is empty
      return False;               //    Elem is not in it
   else                           // otherwise
      return Root->Search(Elem);  //    have Node::Search() look
}

/*-----------------------------------------------------------------
   This function recursively searches the Nodes of a BST for a
   BinTreeElement.

   Receive: Elem, the BinTreeElement being sough.
   Return:  True if Elem is in the Node containing this function
               or in either of its subtrees
            False, otherwise
------------------------------------------------------------------*/

Boolean BST::Node::Search(const BinTreeElement& Elem) const
{
   if (Elem == Data)                  // if this node contains Elem
      return True;                    //   success!

   else if (Elem < Data)              // else if Elem belongs left
      if (Left == 0)                  //   if left subtree is empty
         return False;                //      not in tree!
      else                            //   else
         return Left->Search(Elem);   //      search left subtree

   else                               // else (Elem belongs right)
      if (Right == 0)                 //   if right subtree is empty
         return False;                //      not in tree!
      else                            //   else
         return Right->Search(Elem);  //      search the right subtree
}

/*-----------------------------------------------------------------
   This function deletes a BinTreeElement from a BST.

   Receive: Elem, the BinTreeElement being deleted
   Return:  The BST containing this function with Elem deleted
            True if and only if the operation is successful
------------------------------------------------------------------*/

Boolean BST::Delete(const BinTreeElement& Elem)
{
   if (Root == 0)                      // is the BST empty?
      return False;                    //   value is not in the tree
   else
      return Root->Delete(Elem, Root); //   have Node::Delete() do it
}

/*-----------------------------------------------------------------
   This function recursively deletes a value from the Nodes of a BST.

   Receive: Elem, the BinTreeElement being deleted
            AccessPtr, a (reference) to the pointer by which the Node
               containing this function was reached
   Return:  The BST containing this function, with the Node
              containing Elem deleted
            True if and only if the operation succeeds.
------------------------------------------------------------------*/

Boolean BST::Node::Delete
                 (const BinTreeElement& Elem, BST::NodePtr& AccessPtr)
{
   if (Data == Elem)                      // if current node = Elem
   {
      DelNode(AccessPtr);                 //   delete that node
      return True;                        //   indicate success
   }

   else if (Elem < Data)                  // else if Elem belongs left
      if (Left == 0)                      //   if empty left subtree
         return False;                    //     indicate failure
      else                                //   else
         return Left->Delete(Elem, Left); //     check left subtree

   else                                   // else (Elem belongs right)
      if (Right == 0)                     //   if empty right subtree
         return False;                    //     indicate failure
      else                                //   else
        return Right->Delete(Elem, Right);//      check right subtree

}

/*-----------------------------------------------------------------
   This function deletes a Node from a binary search tree.

   Receive: AccessPtr, a pointer to the Node from its parent (if
               there is one)
   Return:  The BST of which this node is a part, but with this
               Node removed
--------------------------------------------------------------------*/

void DelNode(BST::NodePtr& AccessPtr)
{
   BST::NodePtr
      TempPtr;

   if (AccessPtr != 0)                      // just in case...
      if ((AccessPtr->Left == 0) &&
         (AccessPtr->Right == 0))           // it's a leaf
      {
         delete AccessPtr;                  //   delete the node
         AccessPtr = 0;                     //   set the ptr to NULL
      }
      else if (AccessPtr->Left == 0)        // right subtree not empty
      {
         TempPtr = AccessPtr;               //   save node address 
         AccessPtr = AccessPtr->Right;      //   replace with right 
         TempPtr->Right = 0;                //   detach node
         delete TempPtr;                    //   delete node
      }
      else if (AccessPtr->Right == 0)       // left subtree not empty
      {
         TempPtr = AccessPtr;               //   save node address
         AccessPtr = AccessPtr->Left;       //   replace with left
         TempPtr->Left = 0;                 //   detach node
         delete TempPtr;                    //   delete node
      }
      else                                  // both subtrees nonempty
         AccessPtr->Data =                  //   replace Data with
            LeftMostValue(AccessPtr->Right);//     leftmost value in
}                                           //     the right subtree

/*-----------------------------------------------------------------
   This function finds the leftmost value in a given subtree,
   deletes the node containing that value, and returns the value.

   Receive: NPtr, the pointer by which this Node was accessed
   Return:  The value from the deleted Node
            The BST of which this node is the root, with its
               leftmost Node deleted
-----------------------------------------------------------------*/

BinTreeElement LeftMostValue(BST::NodePtr& NPtr)
{
   if (NPtr->Left == 0)                // if this is leftmost node,
   {                                   // then it has no left subtree
      BinTreeElement
         ReturnValue = NPtr->Data;     //   save its Data value
      BST::NodePtr
         TempPtr = NPtr;               //   save its address

      NPtr = NPtr->Right;              //   replace it with its
                                       //     right subtree
      TempPtr->Right = 0;              //   detach the node
      delete TempPtr;                  //   deallocate the node

      return ReturnValue;              //   return the saved value
   }
   else
      return LeftMostValue(NPtr->Left);// move left & down
                                       //   recursively
}

/*-----------------------------------------------------------------
   This function makes a copy of a binary search tree.

   Precondition:  A copy of a BST is needed by the compiler.
   Receive:       OTree, reference to the original BST (being copied)
   Postcondition: The BST containing this function is a copy of OTree.
--------------------------------------------------------------------*/

BST::BST(const BST& OTree)
{
   if (OTree.Root == 0)                // if the tree is empty
      Root = 0;                        //   that's the easy case
   else                                // otherwise call the Node
      Root = new Node(*(OTree.Root));  //   copy constructor, and
}                                      //   pass it the Root node

/*-----------------------------------------------------------------
   This function recursively copies any binary subtree.

   Precondition:  A copy of a subtree is needed by the compiler.
   Receive:       ONode, a reference to the root of the subtree
                     being copied
   Postcondition: The Node containing this function is a copy of
                    ONode, and the subtrees of this Node are
                    copies as well.
------------------------------------------------------------------*/

BST::Node::Node(const Node& ONode)
{                                     // COPY THE DATA MEMBER
  Data = ONode.Data;
                                      // COPY THE LEFT SUBTREE:
  if (ONode.Left != 0)                //  if it's not empty,
     Left = new Node(*(ONode.Left));  //    make a copy of it
  else                                //  otherwise
     Left = 0;                        //    indicate emptiness
                                      // COPY THE RIGHT SUBTREE:
  if (ONode.Right != 0)               //  if it's not empty,
     Right = new Node(*(ONode.Right));//    make a copy of it
  else                                //  otherwise
     Right = 0;                       //    indicate emptiness
}