/**
 * 
 */
package zhstructures;

import java.util.Iterator;

/**
 * Abstract class implementing the ZHBinarySearchTree interface as a
 * ZHBinaryTreeStructure.
 * 
 * @author J. Andrew Holey
 * @version November 4, 2008
 */
public abstract class ZHAbstractBinarySearchTree
<ElementType extends Comparable<ElementType>,
 StructureType extends ZHAbstractBinarySearchTree<ElementType, StructureType>>
		extends ZHBinaryTreeStructure<ElementType, StructureType>
		implements ZHBinarySearchTree<ElementType> {

	/**
	 * Creates a new empty tree.
	 */
	public ZHAbstractBinarySearchTree() {
		super();
	}

	/* (non-Javadoc)
	 * @see zhstructures.ZHBinarySearchTree#add(java.lang.Comparable)
	 */
	@Override
	public boolean add(ElementType element) {
		StructureType target = this.find(element);
		if (target.isEmpty()) { // add the new element here
			target.element = element;
			target.leftChild = target.getEmptyStructure();
			target.rightChild = target.getEmptyStructure();
			target.state = ZHComponentState.NOT_EMPTY;
			return true;
		}
		else { // element is already in the tree
			return false;
		}
	}

	/* (non-Javadoc)
	 * @see zhstructures.ZHBinarySearchTree#iterator()
	 */
	@Override
	public Iterator<ElementType> iterator() {
		return this.inorderIterator();
	}

	/* (non-Javadoc)
	 * @see zhstructures.ZHBinarySearchTree#remove(java.lang.Comparable)
	 */
	@Override
	public boolean remove(ElementType element) {
		StructureType target = this.find(element);
		if (target.isEmpty()) {
			return false;
		}
		else if (target.leftChild.isEmpty()) {
			target.copyNodeToThis(target.rightChild);
		}
		else if (target.rightChild.isEmpty()) {
			target.copyNodeToThis(target.leftChild);
		}
		else { // both subtrees are non-empty
			StructureType nextRight = target.rightChild.findLeftmost();
			target.element = nextRight.element;
			nextRight.copyNodeToThis(nextRight.rightChild);
		}
		return true;
	}

	/**
	 * Returns a subtree with the specified element in its root if such a subtree exits;
	 * otherwise, returns the empty subtree in which the element would be placed if it
	 * were added..
	 * 
	 * @param element the element to search for
	 * @return a subtree with the specified element in its root if such a subtree exits;
	 * 		   otherwise, returns the appropriate empty subtree.
	 * @throws ClassCastException if this ZHBinaryTreeStructure is not an instance of
	 * 		   StructureType.
	 */
	@SuppressWarnings("unchecked")
	@Override
	protected StructureType find(ElementType element) {
		if (this.isEmpty()) {
			return (StructureType) this;
		}
		int comp = element.compareTo(this.element);
		if (comp == 0) {
			return (StructureType) this;
		}
		else if (comp < 0) {
			return this.leftChild.find(element);
		}
		else { // comp > 0
			return this.rightChild.find(element);
		}
	}

	/**
	 * Returns a new empty instance of the implementing type.
	 * 
	 * @return a new empty instance of the implementing type
	 */
	protected abstract StructureType getEmptyStructure();
	
	protected void copyNodeToThis(StructureType otherNode) {
		this.element = otherNode.element;
		this.leftChild = otherNode.leftChild;
		this.state = otherNode.state;
		this.rightChild = otherNode.rightChild;
	}
}