package binaryTree.visitor;

import binaryTree.*;
import ordering.*;

/**
* Deletes the given input from the host tree.
* <Pre>
   <B>Invariant:</B> host contains unique objects and satisfies the binary search tree property.
   <I>Post:</I> host does not contains the input.
   <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" because it checks for the emptiness
   of the subtrees.  BSTDeleter below is a more OO algorithm.  It asks the subtrees to help do the job instead.
* @author Dung X. Nguyen
* @since 11/22/00 Copyright 2000 - All rights reserved.
*/
public class BSTDeleter implements IVisitor
{
   private AOrder _order;

	public BSTDeleter (AOrder order)
	{
      _order = order;
   }

	/**
   * Returns null.
	 * @param host an empty binary tree (which obviously satisfies the Binary Search Tree Property).
	 * @param input not used
	 * @return
	 */
	public Object emptyCase(BiTree host, Object input)
	{
		return null;
	}

	/**
   * <Pre>
  	   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)
  	      pass the host to its left subtree and ask it to help to remove the host's root;
      </Pre>
	 * @param host satifies BST property
	 * @param input object to be deleted from the host.
    * @return null.
	 */
	public Object nonEmptyCase(BiTree host, Object input)
	{
      Object root = host.getRootDat();
      if (_order.lt (input, root))
      {
         return host.getLeftSubTree().execute (this, input);
      }
      if (_order.eq (input, root))
      {
         return host.getLeftSubTree().execute (new LeftDeleter (host, this), null);
      }
      return host.getRightSubTree().execute (this, input);
	}
}