package brs.visitor;

import brs.*;
import ordering.*;

/**
* Deletes the given input from the host tree.
* <Pre>
   <B>Invariant:</B> host contains unique objects and satisfies the BST 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/06/01 Copyright 2000 - All rights reserved.
*/
public class BSTDeleter implements IVisitor {
    private AOrder _order;

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

    /**
    * Returns null.
    * @param host is empty and obviously satisfies the BST Property.
    * @param input not used
    * @return null
    */
    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 non-empty and 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);
    }
}