/******************************************************************************
    Ordered Binary Tree
----------------------------------------------------
Copyright (c) Gunnar Gotshalks. All Rights Reserved.

Permission to use, copy, modify, and distribute this software
and its documentation for NON-COMMERCIAL purposes and
without fee is hereby granted. 
*******************************************************************************/

package FlexOr.container;

/** 
<P>
@author Gunnar Gotshalks
@version 1.0 1999 Jan 15
*/

public class OrderedBinaryTree extends BinaryTree {

/** Define an empty binary tree.

@param orderComparison defines how nodes are compared when
deciding which branch to take.
@param equalComparison defines how nodes
are checked for equality.
*/

  public OrderedBinaryTree(BinaryPredicate orderComparison,
                           BinaryPredicate equalComparison) {
    comparison = orderComparison;
    equalTo = equalComparison;
    
  }

/** Defines how to compare data for add and remove. */

  private BinaryPredicate comparison;

/** Defines what equal node data means.  Could mean only part of the data
are equal, for example keys but not the value associated with a key. */

  private BinaryPredicate equalTo;

/** Adds <CODE>obj</CODE> at the leaf level such that<BR>
comparison.execute(obj, node.datum) = true<BR>
means go down the left subtree
else go down the right subtree.  An inorder traversal of the tree will give
the elements from low to high or high to low, depending upon whether the
comparison is lessThan or greaterThan.  If <CODE>obj</CODE> is already in the
tree based upon equalTo (which could be partiol equality) then datum is
replaced with obj.

<P><PRE><B>Requires:</B> True
<B>Ensures:</B> contains(obj) = true
            old contains(obj) = false => size = old size + 1
            old contains(obj) = true => size = old size
</PRE>
*/
  synchronized public void add(final Object obj) {
    Node newNode = new Node(obj);
    if (tree == null) { tree = newNode; }
    else { Node current = tree;
      while (true) {
        if (equalTo.execute(obj, current.datum)) {
          current.datum = obj; return;
        }
        if (comparison.execute(obj, current.datum)) {
          if (current.left == null) { current.left = newNode; break; }
          else current = current.left;
        }
        else {
          if (current.right == null) { current.right = newNode; break; }
          else current = current.right;
        }
      }
    }
    count++;
  }

/** Remove the specified element.
<P><PRE><B>Requires:</B> size >= 0
<B>Ensures:</B> 
    old binaryTree.contains(obj) =>
        binaryTree = old binaryTree / obj and result = true 
not old binaryTree.contains(obj) =>
        binaryTree = old binaryTree and result = false
</PRE>
@exception ContainerEmptyException when removing from an empty container.
*/

  synchronized public boolean remove(Object obj) {
    if (tree == null) return false;
    if (equalTo.execute(tree.datum,obj)) {
       tree = removeRootSubTree(tree);
       return true;
    }
    
    Node previous = tree, current;
    while (previous != null) {
      if (comparison.execute(obj, previous.datum)) {
        current = previous.left;
        if (current != null && equalTo.execute(obj, current.datum)) {
          previous.left = removeRootSubTree(current);
          return true;
        }
      }
      else { current = previous.right;
         if (current != null && equalTo.execute(obj, current.datum)) {
           previous.right = removeRootSubTree(current);
           return true;
         }
      }
      previous = current;
    }    
    return false;
  }

/** Remove the root of the tree starting at root and return the root of the
new subtree.
*/

  private Node removeRootSubTree(Node root) {
    count--;
    if (root.left == null) return root.right;
    if (root.left == null) return root.left;
    if (root.right.left == null) {
      root.right.left = root.left;
      return root.right;
    }
    if (root.left.right == null) {
      root.left.right = root.right;
      return root.left;
    }
    
    Node previous = root.left;
    Node current = previous.right;
    while (current.right != null) {
      previous = current; current = current.right;
    }
    previous.right = current.left;
    root.datum = current.datum;
    return root;
  }
  
/** Determines whether an element is in the tree.

<P><PRE><B>Requires:</B> True
<B>Ensures:</B> contains(obj) => result = true
            not contains(obj) => result = false
</PRE>
*/

  synchronized public boolean contains(Object obj) {
    if (tree == null) return false;
    Node current = tree;
    while (current != null) {
      if (equalTo.execute(obj, current.datum)) return true;
      if (comparison.execute(obj, current.datum)) current = current.left;
      else current = current.right;
    }
    return false;
  }
 
/** Return a copy of the container that points to the same objects
as in the original container.  Part way between a shallow and deep copy.  This is
equivalent to how a Vector is cloned.
<P><PRE><B>Requires:</B> True
<B>Ensures:</B> result = copy of BinaryTree
</PRE>
*/

  synchronized public Object clone() {
    OrderedBinaryTree bt = new OrderedBinaryTree(comparison, equalTo);
    bt.count = count;
    if (tree != null) bt.tree = (Node) tree.clone();
    return bt;
  }
 
}