package binaryTree.visitor;

import binaryTree.*;
import ordering.*;

/**
* Inserts an IOrdered into the host maintaining the host's binary search tree property.
* Duplication is not allowed.
<P>
Suppose we have a set of objects that can be compared for equality with "equal to"
and "totally ordered" with an order relation called "less or equal to" .
Let's define "less than" to mean "less or equal to" AND "not equal to".
Let T be a BiTree structure that stores such totally ordered objects.
<Pre>
<B>Definition:</B> T is said to satisfy the binary search tree property (BSTP) if
  T is empty, or
  in the case T is not empty, the left and right subtrees of T both satisfy BSTP, and
  all elements in the left subtree of T are less than the root of T, and
  the root of T is less than all elements in the right subtree of T.
</Pre>

* @author Dung X. Nguyen - Copyright 2000 - All rights reserved.
*/
public class BSTInserter implements IVisitor
{
	public final static BSTInserter Singleton = new BSTInserter ();

	private BSTInserter()
	{
   }

	/**
	 * @param host satisfies BSTP.
	 * @param input an IOrdered.
	 * @return Boolean.TRUE.
	 */
	public Object emptyCase(BiTree host, Object input)
	{
      host.insertRoot (input);
		return Boolean.TRUE;
	}

	/**
	 * @param host satisfies BSTP.
	 * @param input an IOrdered.
	 * @return Boolean.FALSE if the host already contains the input, otherwise Boolean.TRUE.
	 */
	public Object nonEmptyCase(BiTree host, Object input)
	{
      IOrdered root = (IOrdered)host.getRootDat();
      IOrdered inp = (IOrdered)input;
      int inpCompRoot = inp.compare (root);
      return
       inpCompRoot == IOrdered.LESS?
        host.getLeftSubTree().execute(this, input):
        inpCompRoot == IOrdered.GREATER?
          host.getRightSubTree().execute (this, input):
		    Boolean.FALSE;
	}
}