package binaryTree.visitor;

import binaryTree.*;
import ordering.*;

/**
* Deletes the given input IOrdered from the host tree.
* <Pre>
   <B>Invariant:</B> host contains unique IOrdered objects and satisfies the binary search tree property.
   <I>Post:</I> host does not contains the input IOrdered.
   <U>Algorithm:</U>
   Case host is empty:
      returns null because there is nothing to remove.
   Case host is not empty:
  	   if input < root
  	      ask the host's left subtree to delete the input;
  	   else if root < input
  	      ask the host's right subtree to delete the input
  	   else (at this point, input == root)
      if host is a leaf
  	      ask the host to remove its root;
  	   else if host's left subtree is empty (i.e. right subtree is NOT empty)
  	   {
  	      ask host to replace the root with the minimum value of its right subtree;
         ask host's right subtree to delete this minimum value;
  	   }
  	   else (at this point, the left subtree must NOT be empty)
  	   {
  	      ask host to replace the root with the maximum value of its left subtree;
         ask host's right subtree to delete this maximum value;
  	   }
   </Pre>
   <P><B>NOTE:</B> The above algorithm is not "object-oriented" enough.  Can you think
   of a more OO way?  Hint: Think of the OO algorithm to check for a leaf.
* @author Dung X. Nguyen
* @since 11/12/99 Copyright 1999 - All rights reserved.
*/
public class BSTDeleter implements IVisitor
{
	public final static BSTDeleter Singleton = new BSTDeleter ();

	private BSTDeleter()
	{
   }

	/**
   * Returns null.
	 * @param host satifies BST property
	 * @param input an IOrdered.
	 */
	public Object emptyCase(BiTree host, Object input)
	{
		return null; // there is nothing to delete.
	}

	/**
    * Returns input if host contains input, otherwise returns null.
	 * @param host satifies BST property
	 * @param input an IOrdered.
	 */
	public Object nonEmptyCase(BiTree host, Object input)
	{
      IOrdered root = (IOrdered)host.getRootDat();
      IOrdered inp = (IOrdered)input;
      int inpCompRoot = inp.compare (root);
      if (inpCompRoot == IOrdered.LESS)
      {
         return host.getLeftSubTree ().execute(this, input);
      }
      else if (inpCompRoot == IOrdered.GREATER)
      {
         return host.getRightSubTree ().execute(this, input);
      }
      // At this point, root == inp.  Why?
		boolean isLeftEmpty
      = ((Boolean)host.getLeftSubTree ().execute(EmptyChecker.Singleton, this)).booleanValue ();
		boolean isRightEmpty
      = ((Boolean)host.getRightSubTree ().execute(EmptyChecker.Singleton, this)).booleanValue ();
      if (isLeftEmpty && isRightEmpty)
      {
         return host.remRoot ();
      }
      // At this point, at least one of the subtrees is not empty. Why?
      BiTree minTree = (BiTree)(isLeftEmpty?
                          host.getRightSubTree ().execute (MinTreeFinder.Singleton, null)
                        : host.getLeftSubTree ().execute (MaxTreeFinder.Singleton, null));
      Object min = minTree.getRootDat();
      host.setRootDat (min);
      minTree.execute (this, min);
      return input;
	}
}