package DataStructures;

import java.util.Enumeration;
import java.util.Iterator;
import java.util.NoSuchElementException;

/**
 * <p>A class implementing binary search trees for elements of type E.
 * </p>
 * <p>
 * Elements of type E must implement the Comparable interface 
 * in their defining class or in some superclass.
 * </p>
 *
 * <p>Trees are created empty using
 * <pre>
 *   SearchTree&ltInteger&gt t = new SearchTree&ltInteger&gt();
 * </pre>
 * Items can be added by
 * <pre>
 *   t.add(item);
 * </pre>
 * where <code>item</code> is an element of type E .</p>
 *
 * <p>Elements of type E can be removed by</p>
 * <pre>
 *   t.remove(item);
 * </pre>
 * </p>
 *
 * Trees can be traversed in order using an iteration, 
 * for example for an Integer tree:
 * <pre>
 *   for (Integer i : t) {
 *       System.out.println(i);
 *   }
 * </pre>
 * @see <a href="http://java.sun.com/products/j2se/1.5/docs/api/java/lang/Comparable.html">Comparable</a>
 * @see <a href="http://java.sun.com/products/j2se/1.5/docs/api/java/lang/Iterable.html">Iterable</a>
 * @see <a href="http://java.sun.com/products/j2se/1.5/docs/api/java/util/Iterator.html">Iterator</a>
 * @see <a href="http://java.sun.com/products/j2se/1.5/docs/api/java/util/Enumeration.html">Enumeration</a>
 *
 * @param <E> the type of elements held in this tree
 * @author Peter Williams
 */

public class SearchTree<E extends Comparable<? super E>> implements Iterable<E> {

    private Tree<E> t;

    /**
     * Constructs an empty tree suitable for holding comparable elements of type E
     */
    public SearchTree() {
        t = new EmptyTree<E>();
    }
    
    /**
     * Tests if the tree is empty.
     * @return the status of the tree.
     */
    public boolean isEmpty() {
	return t.isEmpty();
    }

    /**
     * Counts the number of nodes in the tree.
     * @return the number of nodes in the tree.
     */
    public int nrNodes() {
	return t.nrNodes();
    }

    /**
     * Tests whether the item is present in the tree.
     * @param item the item to search for.
     * @return <tt>true</tt> if the tree contains this item, 
     <tt>false</tt> otherwise
    */
    public boolean contains(E item) {
	return t.contains(item);
    }

    /**
     * Adds an item into the tree, preserving the ordering property.
     * @param item the item to add.
     */
    public void add(E item) {
	t = t.add(item);
    }

    /**
     * Removes an item from the tree, preserving the ordering property.
     * @param item the item to remove.
     */
    public void remove(E item) {
	t = t.remove(item);
    }

    /**
     * Provides an enumeration of the elements of the tree in level order.
     * @return the enumeration
     * @exception NoSuchElementException if the <tt>nextElement</tt> method
     *            is called when there is no next element
     */
    public Enumeration<E> elementsLevelOrder() {
	return t.elementsLevelOrder();
    }

    /**
     * Iterates over the items in the tree using the in-order sequence.
     * @return the iterator.
     * @exception NoSuchElementException if the <tt>next</tt> method
     *            is called when there is no next element
     * @exception IllegalStateException if the <tt>next</tt> method has not
     *            yet been called, or the <tt>remove</tt> method has already
     *            been called after the last call to the <tt>next</tt>
     *            method.
     */
    public Iterator<E> iterator() {
        return new Iterator<E>() {
	    private Enumeration<E> e = t.elementsInOrder();
            private E current = null;
	    public boolean hasNext() {
		return e.hasMoreElements();
	    }
	    public E next() {
		current = e.nextElement();
		return current;
	    }
	    public void remove() {
		if (current == null) {
		    throw new IllegalStateException();
		} else {
		    t = t.remove(current);
		    current = null;
		}
	    }
	};
    }
    
    /**
     * Converts the tree to a string.
     * @return the string representation.
     */
    public String toString() {
	return t.toString();
    }

}

/* An abstract class to represent the union of an EmptyTree and a NodeTree
 */
abstract class Tree<E extends Comparable<? super E>> {
    abstract boolean isEmpty();
    abstract int nrNodes();
    abstract boolean contains(E item);
    abstract Tree<E> add(E item);
    abstract Tree<E> remove(E item);
    abstract Enumeration<E> elementsInOrder();
    abstract Enumeration<E> elementsLevelOrder();
    public abstract String toString(); 

}

/* A subclass of Tree representing the empty tree.
 */
class EmptyTree<E extends Comparable<? super E>> extends Tree<E> {

    EmptyTree() {}
  
    boolean isEmpty() {
        return true;
    }

    int nrNodes() {
        return 0;
    }

    boolean contains(E item) {
        return false;
    }

    Tree<E> add(E item) {
        return new NodeTree<E>(item);
    }

    Tree<E> remove(E item) {
        return this;
    }

    Enumeration<E> elementsInOrder() {
        return new EmptyEnumeration<E>();
    }

    Enumeration<E> elementsLevelOrder() {
        return new EmptyEnumeration<E>();
    }

    public String toString() {
        return "";
    }

}

/* A subclass of Tree representing a non-empty tree.
 */
class NodeTree<E extends Comparable<? super E>> extends Tree<E> {

    private E data;  // the data item at the root
    private Tree<E> left;  // the left subtree
    private Tree<E> right; // the right subtree

    private static final Tree EMPTY_TREE = new EmptyTree(); 
    // the empty tree (immutable) - we only want one of these
  
    NodeTree(E item) {
        data = item;
        left = EMPTY_TREE;
        right = EMPTY_TREE;
    }
  
    boolean isEmpty() {
        return false;
    }

    int nrNodes() {
        return left.nrNodes() + right.nrNodes() + 1;
    }

    boolean contains(E item) {
        int compare = item.compareTo(data);
        if (compare < 0) {
            return left.contains(item);
        } else if (compare > 0) {
            return right.contains(item);
        } else {
            return true;
        }
    }
  
    Tree<E> add(E item) {
        int compare = item.compareTo(data);
        if (compare < 0) {
            left = left.add(item);
        } else if (compare > 0) {
            right = right.add(item);
        }
        return this;
    }
  
    /* private method for use in method <remove>
     * returns largest item in non-empty tree
     */
    private E findMax() {
        if (right.isEmpty()) {
            return data;
        } else {
            return ((NodeTree<E>) right).findMax();
        }
    }
  
    /* private method for use in method <remove>  
     * removes node containing largest item in non-empty tree
     */
    private Tree<E> removeMax() {
        if (right.isEmpty()) {
            return left; 
        } else {
            right = ((NodeTree<E>) right).removeMax();
            return this;
        }
    }

    public Tree<E> remove(E item) {
        int compare = item.compareTo(data);
        if (compare == 0 && left.isEmpty()) {
            return right;
        } else {
            if (compare < 0) {
                left = left.remove(item);
            } else if (compare > 0) {
                right = right.remove(item);
            } else { // compare == 0 and !left.isEmpty()
                data = ((NodeTree<E>) left).findMax();
                left = ((NodeTree<E>) left).removeMax();
            }
            return this;
        }
    }
  
    public Enumeration<E> elementsLevelOrder() {
        return new Enumeration<E>() {
            private Queue<NodeTree<E>> q = new QueueArray<NodeTree<E>>();
            { // initialise the queue
                q.enqueue(NodeTree.this);
            }
            public boolean hasMoreElements() {
                return !q.isEmpty();
            }
            public E nextElement() {
                NodeTree<E> root = q.dequeue();
                if (!root.left.isEmpty()) {
                    q.enqueue((NodeTree<E>) root.left);
                }
                if (!root.right.isEmpty()) {
                    q.enqueue((NodeTree<E>) root.right);
                }
                return root.data;
            }
        };
    }
  
    // a class of objects to stack for in-order traversals
    // would also serve for PreOrder and PostOrder if required
    private class StackItem<E extends Comparable<? super E>> {
        NodeTree<E> root; // the subtree we are currently processing
        boolean ready; // whether we are ready to return its root data
        StackItem(NodeTree<E> root, boolean ready) {
            this.root = root;
            this.ready = ready;
        }
    }
  
    Enumeration<E> elementsInOrder() {
        return new Enumeration<E>() {
            private Stack<StackItem<E>> s = new StackArray<StackItem<E>>();
            { // initialise the stack       
                s.push(new StackItem<E>(NodeTree.this, false));
            }
	    public boolean hasMoreElements() {
		return !s.isEmpty();
	    }
	    public E nextElement() {
		StackItem<E> next = s.pop();
		while (!next.ready) {
		    NodeTree<E> root = next.root;
		    if (!root.right.isEmpty()) {
			s.push(new StackItem<E>((NodeTree<E>) root.right, false));
		    }
		    // relocate the next line to get PreOrder or PostOrder
		    s.push(new StackItem<E>(root, true));
		    if (!root.left.isEmpty()) {
			s.push(new StackItem<E>((NodeTree<E>) root.left, false));
		    }
		    next = s.pop();
		}
		return next.root.data;
	    }
	};
    }

    public String toString() {
	String string = "";
	if (!left.isEmpty() && !right.isEmpty()) {
	    string += "(" + left + " " + data + " " + right + ")";
	} else if (!left.isEmpty()) {
	    string += "(" + left + " " + data + " .)";
	} else if (!right.isEmpty()) {
	    string += "(. " + data + " " + right + ")";
	} else {
	    string += data;
	}
	return string;
    }

}