package binaryTree.visitor;

import binaryTree.BiTree;

/**
* Deletes the given input Integer from the host tree.
* <Pre>
   <B>Invariant:</B> host contains unique Integer objects and satisfies the binary search tree property.
   <I>Post:</I> host does not contains the input Integer.
   <U>Algorithm:</U>
   Case host is empty:
      do nothing 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()
	{
		}

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

	/**
	 * @param host satifies BST property
	 * @param input an Integer.
	 * @return null.
	 */
	public Object nonNullCase(BiTree host, Object input)
	{
      int rootVal = ((Integer)host.getRootDat ()).intValue ();
      int inputVal = ((Integer)input).intValue ();
      if (inputVal < rootVal)
      {
         return host.getLeftSubTree ().execute(this, input);
      }
      else if (rootVal < inputVal)
      {
         return host.getRightSubTree ().execute(this, input);
      }
      // At this point, rootVal == inputVal.  Why?
		boolean isLeftEmpty
      = ((Boolean)host.getLeftSubTree ().execute(EmptyChecker.Singleton, this)).booleanValue ();
		boolean isRightEmpty
      = ((Boolean)host.getRightSubTree ().execute(EmptyChecker.Singleton, this)).booleanValue ();
      if (isLeftEmpty && isRightEmpty)
      {
         host.remRoot ();
         return null;
      }
      // 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 (MinTreeFinder.Singleton, null));
      host.setRootDat (minTree.getRootDat ());
      minTree.remRoot ();
      return null;
	}
}