package exercise1;

import java.util.ArrayList;
import java.util.Iterator;

/**
 * A linked implementation of a binary search tree.
 * Duplicates of elements are not allowed in the tree.
 *
 * @author mlch
 */
public class LinkedBinarySearchTree<E extends Comparable<E>> implements BinarySearchTree<E>,
		Iterable<E>
{
	private BinaryTree<E> tree = new LinkedBinaryTree<E>();
	private int internalCount; //count of internal nodes in the binary search tree

	/**
	 * Creates a new empty LinkedBinarySearchTree
	 * (that is, a tree with one external node).
	 */
	public LinkedBinarySearchTree()
	{
		tree.addRoot(null);
		internalCount = 0;
	}

	/**
	 * Returns the count of elements in the binary search tree
	 * (that is, the count of internal nodes in the tree).
	 */
	@Override
	public int size()
	{
		return internalCount;
	}

	/**
	 * Returns whether the binary search tree is empty
	 * (that is, whether it has any internal nodes).
	 */
	@Override
	public boolean isEmpty()
	{
		return internalCount == 0;
	}

	//Returns the position of the element in the (sub)tree rooted at the specified position.
	//If the element is not found, the external position, where the element should be
	//inserted in the binary search tree, is returned.
	//Requires: The position is valid.
	private Position<E> treeSearch(E e, Position<E> p)
	{
		if (tree.isExternal(p))
			return p;

		if (p.element().compareTo(e) == 0)
			return p;
		else if (p.element().compareTo(e) < 0)
			return treeSearch(e, tree.right(p));
		else
			return treeSearch(e, tree.left(p));
	}

	/**
	 * Inserts the element in the binary search tree
	 * (but only if the element is not in the tree already).
	 * @param e - the element to be inserted
	 */
	@Override
	public void insert(E e)
	{
		Position<E> p = treeSearch(e, tree.root());
		if (tree.isExternal(p)) {
			tree.replace(p, e);
			tree.insertLeft(p, null);
			tree.insertRight(p, null);
			internalCount++;
		}
	}

	/**
	 * Removes the element from the binary search tree
	 * (if the element is in the tree).
	 * @param e - the element to be removed
	 */
	@Override
	public void remove(E e)
	{
		Position<E> remPos = treeSearch(e, tree.root());
		if (tree.isInternal(remPos)) {
			if (tree.isExternal(tree.left(remPos))) {
				remPos = tree.left(remPos);
			}
			else if (tree.isExternal(tree.right(remPos))) {
				remPos = tree.right(remPos);
			}
			else {
				Position<E> swapPos = remPos;
				remPos = tree.right(remPos);
				while (tree.isInternal(tree.left(remPos))) {
					remPos = tree.left(remPos);
				}
				tree.replace(swapPos, remPos.element());
				remPos = tree.left(remPos);
			}
			removeExternal(remPos);
		}
	}

	/**
	 * Returns the smallest element in the binary search tree.
	 * If the tree is empty, null is returned
	 */
	public E findMin() {
		if (isEmpty()) {
			return null;
		}

		Position<E> min = tree.root();

		while (tree.hasLeft(tree.left(min))) {
			min = tree.left(min);
		}

		return min.element();
	}

	/**
	 * Removes and returns the smallest element in the binary search tree.
	 * If the tree is empty, null is returned.
	 */
	public E removeMin() {
		E e = findMin();
		remove(e);
		return e;
	}

	//Removes the node and the parent above the node,
	//replacing the parent with the node's sibling.
	//Requires: The node is an external node.
	private void removeExternal(Position<E> p)
	{
		if (!tree.isExternal(p))
			throw new RuntimeException("The node is not external.");

		Position<E> parent = tree.parent(p);
		tree.remove(p);
		tree.remove(parent);
		internalCount--;
	}

	/**
	 * Returns the position of the element in the binary search tree.
	 * If the element is not found, null is returned.
	 * @param e - the element to find the position of
	 */
	@Override
	public Position<E> search(E e)
	{
		Position<E> p = treeSearch(e, tree.root());
		if (tree.isInternal(p))
			return p;
		else
			return null;
	}

	/**
	 * Returns an iterator on the binary search tree.
	 */
	@Override
	public Iterator<E> iterator()
	{
		ArrayList<E> list = new ArrayList<E>();
		for (E e : tree) {
			if (e != null)
				list.add(e);
		}
		return list.iterator();
	}

}