package binaryTree.visitor;

import binaryTree.BiTree;

/**
* Inserts an Integer 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" (denoted by ===)
and "totally ordered" with an order relation called "less or equal to" (denoted by <=).
Let's define "less than" (denoted by <) 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
* @since 11/12/99 Copyright 1999 - All rights reserved.
*/
public class BSTInserter implements IVisitor
{
	public final static BSTInserter Singleton = new BSTInserter ();

	private BSTInserter()
	{
   }

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

	/**
	 * @param host satisfies BSTP.
	 * @param input an Integer.
	 * @return Boolean.FALSE if the host already contains the input, otherwise Boolean.TRUE.
	 */
	public Object nonNullCase(BiTree host, Object input)
	{
      int rootVal = ((Integer)host.getRootDat()).intValue ();
      int inputVal = ((Integer)input).intValue ();
      return
      inputVal < rootVal?
        host.getLeftSubTree().execute(this, input):
        rootVal < inputVal?
          host.getRightSubTree().execute (this, input):
		    Boolean.FALSE;
	}
}