// COMP102
// Example 16: Static Methods to Support Ordered Binary Trees
//             for Record Storage.
//
// Paul E. Dunne 2/12/99
//
import BinaryTree;
import Compare;
public class RecordTree
  {
  //*******************************************************//
  // Compare the given key with the root of this Binary    //
  // Tree, using a numeric comparison if both are Number   //
  // instances, and String comparison otherwise.           //
  // Returns true of Key is `less than' Root               //
  //*******************************************************//
  public static boolean IsBeforeRoot ( Object Key, BinaryTree T )
    {
    if (T.IsEmpty())
      return false;
    else 
      return Compare.IsBefore(Key,T.GetRoot());
    }
  //*******************************************************//
  // Similarly, comparison method that returns true if    *//
  // the given Key is 'greater than' the Root.            *//
  //*******************************************************//
  public static boolean IsAfterRoot ( Object Key, BinaryTree T )
    {
    if (T.IsEmpty())
      return false;
    else 
      return Compare.IsBefore(T.GetRoot(),Key);
    }
  //*******************************************************//
  // Test whether the given Key occurs as a node Object   *//
  // in the BinaryTree T.                                 *//
  //*******************************************************//
  public static boolean IsMemberOf( Object Key, BinaryTree T )
    {
    if (T.IsEmpty())
      return false;
    else if (IsBeforeRoot(Key,T))
      return IsMemberOf(Key,T.GetLeft());
    else if (IsAfterRoot(Key,T))
      return IsMemberOf(Key,T.GetRight());
    else
      return true;
   };
  //*********************************************//
  // Insert a new Object into T, maintaining a  *//
  // Sorted ordering                            *//
  //*********************************************//
  public static void InsertKey(Object Key, BinaryTree T)
    {
    if (T.IsEmpty())
      {
      T.SetRoot(Key);
      T.SetLeft(new BinaryTree());
      T.SetRight(new BinaryTree());
      }
    else if ( IsBeforeRoot(Key,T) )
      InsertKey(Key,T.GetLeft());
    else if ( IsAfterRoot(Key,T) )
      InsertKey(Key,T.GetRight());
    }
  //******************************************************//
  // Insert a SubTree Add into T, maintaining a          *//
  // Sorted ordering (and avoiding item duplication)     *//
  //******************************************************//
  public static BinaryTree InsertTree(BinaryTree Add, BinaryTree T)
    {
    BinaryTree temp = T;
    if (Add.IsEmpty())
      return temp;
    else
      {
      InsertKey(Add.GetRoot(),temp);
      InsertTree(Add.GetLeft(),temp);
      InsertTree(Add.GetRight(),temp);
      return temp;
      };
    }
  //*******************************************************//
  // Return the Binary Tree that results by deleting       //
  // the given Key from the tree structure.                //
  //*******************************************************//
  public static BinaryTree DeleteKey(Object Key, BinaryTree T)
    {
    BinaryTree temp=new BinaryTree();
    if ( !IsMemberOf(Key,T) )
      return T;                     // Key not in T, so T is unchanged.
    else if (IsBeforeRoot(Key,T))   // Key is in T.Left, so delete recursively.
      {
      temp.SetRoot(T.GetRoot());
      temp.SetRight(T.GetRight());
      temp.SetLeft(DeleteKey(Key,T.GetLeft()));
      return temp;
      }
    else if (IsAfterRoot(Key,T))    // Key is in T.Right, delete recursively.
      {
      temp.SetRoot(T.GetRoot());
      temp.SetLeft(T.GetLeft());
      temp.SetRight( DeleteKey(Key,T.GetRight()) );
      return temp;
      }                            // Key must be the current Root node;
    else if (BinaryTree.SizeOf(T)==1)      
      {
      temp = new BinaryTree();       // If T has only one node, the empty tree remains
      return temp;                   // after deleting this.
      }
    else if (T.GetLeft().IsEmpty())  // If T.Left is empty, then after deleting T.Root,
      {
      temp = T.GetRight();           // the updated tree contains T.Right.
      return temp;
      }
    else if (T.GetRight().IsEmpty()) // If T.Right is empty, then after deleting T.Root,
      {
      temp = T.GetLeft();            // the updated tree contains T.Left.
      return temp;
      }
    else                             // By this stage: T.Root=Key and T.Left and
      {                              // and T.Right are both non-empty.
      //***********************************************************************
      // The update `sorted' tree is built by inserting T.Right into the Tree *
      // Tree T.Left: this must preserve the correct `ordering' since every   *
      // Object in T.Right must succeed every Object in T.Left.               *
      //***********************************************************************
      temp = InsertTree(T.GetRight(),
                        InsertTree(T.GetLeft(), 
                                   new BinaryTree()));
      return temp;
      };
    }
  //*************************************************
  // Delete sub-tree with root Key from T           *
  //*************************************************
  public static BinaryTree DeleteTree (Object Key, BinaryTree T)
    {
    BinaryTree temp=new BinaryTree();
    if (!IsMemberOf(Key,T))
      {
      temp=T;
      return temp;
      }
    else if (IsBeforeRoot(Key,T))
      {
      temp.SetRoot(T.GetRoot());
      temp.SetRight(T.GetRight());
      temp.SetLeft(DeleteTree(Key,T.GetLeft()));
      return temp;
      }
    else if (IsAfterRoot(Key,T))
      {
      temp.SetRoot(T.GetRoot());
      temp.SetLeft(T.GetLeft());
      temp.SetRight(DeleteTree(Key,T.GetRight()));
      return temp;
      }
    else
      return temp;    // Key=T.Root, so deleting T.Root leaves the empty tree.
   }
  //*************************************************
  // Return the BinaryTree whose sub-tree has its   *
  // Root field equal to Key.                       *
  // If Key does not occur in T returns the empty   *
  // BinaryTree.                                    *
  //*************************************************
  public static BinaryTree GetTree (Object Key, BinaryTree T)
    {
    BinaryTree result;
    if (!IsMemberOf(Key,T))
      result=new BinaryTree();
    else if (IsBeforeRoot(Key,T))       // Key in T.Left
      result = GetTree(Key,T.GetLeft());
    else if (IsAfterRoot(Key,T))        // Key in T.Right
      result = GetTree(Key,T.GetRight());
    else
      result = T;                       // Key=T.Root
    return result;
    }
  //*************************************************
  // Return the Object which occurs first in a      *
  // PreOrder traversal: i.e. the `first' Object    *
  // in the tree ordering.                          *
  // Error will be raised if T is empty.            *
  //*************************************************
  public static Object PreOrderFirst(BinaryTree T)
    {
    if (T.GetLeft().IsEmpty())
      return T.GetRoot();
    else
      return PreOrderFirst(T.GetLeft());
    }
  //*************************************************
  // Return the Object which occurs first in a      *
  // PostOrder traversal: i.e. the `last' Object    *
  // in the tree ordering.                          *
  // Error will be raised if T is empty.            *
  //*************************************************
  public static Object PostOrderFirst(BinaryTree T)
    {
    if (T.GetRight().IsEmpty())
      return T.GetRoot();
    else
      return PostOrderFirst(T.GetRight());
    }
  }