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

  BS_Tree.java

  (P) 1998 Laurentiu Cristofor

  implementation
  of a heterogeneous 
  binary search tree

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

class BS_Tree
{
  // Private instance variables

  private Comparison cmp;

  private BST_Node root;

  private int bst_size;

  // Package methods

  // this function returns the node that contains the next value
  // in increasing order relative to the value of current.
  BST_Node next(BST_Node current)
  {
    if (current == null)
      return null;

    BST_Node next = current;

    // next node can be below and to the right
    if (next.right != null)
      {
	next = next.right;
	while (next.left != null)
	  next = next.left;
      }
    // or above
    else
      {
	BST_Node walk = root;

	next = null;

	// Go down and look for current.
	// remember last node from which you
	// went to the left. That will be
	// the next node.
	while (walk != null)
	  {
	    if (cmp.compare(current.value, walk.value) < 0)
	      {
		next = walk;
		walk = walk.left;
	      }
	    else 
	      {
		walk = walk.right;
	      }
	  }

	// next contains the next node if such
	// node exists, otherwise it will contain null
      }

    return next;
  }

  // Public methods
  
  public BS_Tree(Comparison cmp)
  {
    root      = null;
    bst_size  = 0;
    this.cmp  = cmp;
  }
  
  public int size()
  {
    return bst_size;
  }

  public boolean empty()
  {
    return bst_size == 0;
  }

  /*-------------------------------------------------------
    simple algorithm for insertion in a binary search tree 
    -------------------------------------------------------*/
  public void insert(Object value)
  {
    BST_Node parent  = root;
    BST_Node current = root;

    // the following remembers if
    // current is left child of parent
    boolean toLeft = true;

    ++bst_size;

    if (root == null)
      {
	root = new BST_Node(value);
	return;
      }

    while (current != null)
      {
	parent = current;
	  
	if (cmp.compare(value, current.value) < 0)
	  {
	    current = current.left;
	    toLeft  = true; 
	  }
	else
	  {
	    current = current.right;
	    toLeft  = false;
	  }
      }

    if (toLeft)
      parent.left  = new BST_Node(value);
    else
      parent.right = new BST_Node(value);
  }

  /*---------------------------------------------------
    The algorithm used for removing values from
    a binary search tree is the one described by
    Robert Sedgewick in his book: "Algorithms in C++".
    
    Since my root node is implemented a little 
    differently than in the book, I had to treat
    the removal of the root node as a special case.
    ---------------------------------------------------*/
  public boolean remove(Object value)
  {
    BST_Node parent    = root;
    BST_Node current   = root;
    BST_Node condemned = null;

    // the following remembers if
    // current is left child of parent
    boolean toLeft = true;
  
    // first look for node containing value
    while (current != null && cmp.compare(value, current.value) != 0)
      {
	parent = current;
	  
	if (cmp.compare(value, current.value) < 0)
	  {
	    current = current.left;
	    toLeft  = true; 
	  }
	else
	  {
	    current = current.right;
	    toLeft  = false;
	  }
      }

    // node not found
    if (current == null)
      return false;

    --bst_size;

    // store node that has to be deleted
    condemned = current;

    // treat root as a special case
    if (condemned == root)
      {
	if (condemned.right == null)
	  root = condemned.left;
	else if (condemned.right.left == null)
	  {
	    root      = condemned.right;
	    root.left = condemned.left;
	  }
	// we have to deal with the hard case, the plan is:
	// we'll look for the leftmost child
	// in the right subtree of the condemned node
	// and move it in the place of condemned node.
	else
	  {
	    current = condemned.right;
	  
	    while (current.left.left != null)
	      current = current.left;

	    // current is now pointing to the
	    // parent of the leftmost node
	  
	    root         = current.left;
	    current.left = current.left.right;
	    root.left    = condemned.left;
	    root.right   = condemned.right;
	  }
      }
    else
      {
	if (condemned.right == null)
	  {
	    if (toLeft)
	      parent.left  = condemned.left;
	    else
	      parent.right = condemned.left;
	  }
	else if (condemned.right.left == null)
	  {
	    current = condemned.right;
	  
	    if (toLeft)
	      parent.left  = condemned.right;
	    else
	      parent.right = condemned.right;
	  
	    current.left = condemned.left;
	  }
	else
	  {
	    current = condemned.right;
	  
	    while (current.left.left != null)
	      current = current.left;
	  
	    if (toLeft)
	      {
		parent.left   = current.left;
		current.left  = current.left.right;
	      
		current       = parent.left;
		current.left  = condemned.left;
		current.right = condemned.right;
	      }
	    else
	      {
		parent.right  = current.left;
		current.left  = current.left.right;
	      
		current       = parent.right;
		current.left  = condemned.left;
		current.right = condemned.right;
	      }
	  }
      }
  
    // final act
    condemned = null;

    return true;
  }

  public BST_Iterator find(Object value)
  {
    BST_Node current = root;

    // Go down and look for current_node.
    // remember last node from which you
    // went to the left. That will be
    // the next node.
    while (current != null && cmp.compare(value, current.value) != 0)
      {
	if (cmp.compare(value, current.value) < 0)
	  {
	    current = current.left;
	  }
	else 
	  {
	    current = current.right;
	  }
      }

    return new BST_Iterator(this, current);
  }

  public BST_Iterator iterator()
  {
    BST_Node current = root;

    if (current != null) 
      while (current.left != null)
	current = current.left;

    return new BST_Iterator(this, current);
  }
}