package DataStructures;

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

/**
  * <p>A class implementing binary search trees. </p>
  *
  * <p>Trees are created using the <code>empty</code> and 
  * <code>add</code> methods, for example:
  * <pre>
  *   SearchTree t = SearchTree.empty();
  *   t = t.add(item);
  * </pre>
  * where <code>item</code> belongs to a class implementing the
  * <code>Comparable</code> interface.</p>  
  *
  * <p>Elements can be removed by</p>
  * <pre>
  *   t = t.remove(item);
  * </pre>
  *
  * Trees can be traversed using an enumeration, for example:
  * <pre>
  *   for (Enumeration e = t.elementsInOrder(); e.hasMoreElements();) {
  *       System.out.println(e.nextElement());
  *   }
  * </pre>
 * @see <a href="http://java.sun.com/products/j2se/1.4/docs/api/java/util/Enumeration.html">Enumeration</a>
  *
  * @author Peter Williams
  */

public abstract class SearchTree {
    /**
     * Returns an empty tree.
     */
    public static SearchTree empty() {
        return new EmptyTree();
    }
    
    /**
     * Tests if the tree is empty.
     * @return the status of the tree.
     */
    public abstract boolean isEmpty();

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

    /**
     * Tests whether the item is present in the tree.
     * @param item the item to search for.
     */
    public abstract boolean contains(Comparable item);

    /**
     * Adds an item into the tree, preserving the ordering property.
     * @param item the item to add.
     * @return a tree with the item added
     */
    public abstract SearchTree add(Comparable item);

    /**
     * Removes an item from the tree, preserving the ordering property.
     * @param item the item to remove.
     * @return a tree with the item removed
     */
    public abstract SearchTree remove(Comparable item);

    /**
     * Provides an enumeration of the elements of the tree in order.
     * @return the enumeration
     */
    public abstract Enumeration elementsInOrder();

    /**
     * Provides an enumeration of the elements of the tree in level order.
     * @return the enumeration
     */
    public abstract Enumeration elementsLevelOrder();

    /**
     * Converts the tree to a string.
     * @return the string representation.
     */
    public abstract String toString(); 

}

/* A subclass of SearchTree representing the empty tree.
 */
class EmptyTree extends SearchTree {
    /**
     * This class ought not to be instantiated directly
     */
    protected EmptyTree() {}
  
    public boolean isEmpty() {
        return true;
    }
    public int nrNodes() {
        return 0;
    }
    public boolean contains(Comparable item) {
        return false;
    }
    public SearchTree add(Comparable item) {
        return new NodeTree(item);
    }
    public SearchTree remove(Comparable item) {
        return this;
    }
    private static Enumeration theEmptyEnumeration =
        new Enumeration() {
            public boolean hasMoreElements() {
                return false;
            }
            public Object nextElement() {
                throw new NoSuchElementException();
            }
        };
    public Enumeration elementsInOrder() {
        return theEmptyEnumeration;
    }
    public Enumeration elementsLevelOrder() {
        return theEmptyEnumeration;
    }
    public String toString() {
        return "";
    }
}

/* A subclass of SearchTree representing a non-empty tree.
 */
class NodeTree extends SearchTree {

    private Comparable data;  // the data item at the root
    private SearchTree left;  // the left subtree
    private SearchTree right; // the right subtree
  
    private static SearchTree empty = empty();
  
    /**
     * This class ought not to be instantiated directly
     */
    protected NodeTree(Comparable item) {
        data = item;
        left = empty;
        right = empty;
    }
  
    public boolean isEmpty() {
        return false;
    }

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

    public boolean contains(Comparable item) {
        int compare = item.compareTo(data);
        if (compare < 0) {
            return left.contains(item);
        } else if (compare > 0) {
            return right.contains(item);
        } else {
            return true;
        }
    }
  
    public SearchTree add(Comparable 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 public method <remove>
     * returns smallest item in non-empty tree
     */
    private Comparable findMin() {
        if (left.isEmpty()) {
            return data;
        } else {
            return ((NodeTree) left).findMin();
        }
    }
  
    /* private method for use in public method <remove>  
     * removes node containing smallest item in non-empty tree
     */
    private SearchTree removeMin() {
        if (left.isEmpty()) {
            return right; 
        } else {
            left = ((NodeTree) left).removeMin();
            return this;
        }
    }
  
    public SearchTree remove(Comparable item) {
        int compare = item.compareTo(data);
        if (compare == 0 && right.isEmpty()) {
            return left;
        } else {
            if (compare < 0) {
                left = left.remove(item);
            } else if (compare > 0) {
                right = right.remove(item);
            } else { // compare == 0 and !right.isEmpty()
                data = ((NodeTree) right).findMin();
                right = ((NodeTree) right).removeMin();
            }
            return this;
        }
    }
  
    public Enumeration elementsLevelOrder() {
        return new Enumeration() {
            private Queue q = new QueueArray();
            { // initialise the queue
                q.enqueue(NodeTree.this);
            }
            public boolean hasMoreElements() {
                return !q.isEmpty();
            }
            public Object nextElement() {
                NodeTree root = (NodeTree) q.dequeue();
                if (!root.left.isEmpty()) {
                    q.enqueue(root.left);
                }
                if (!root.right.isEmpty()) {
                    q.enqueue(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 {
        NodeTree root; // the subtree we are currently processing
        boolean ready; // whether we are ready to return its root data
        StackItem(NodeTree root, boolean ready) {
            this.root = root;
            this.ready = ready;
        }
    }
  
    public Enumeration elementsInOrder() {
        return new Enumeration() {
            private Stack s = new StackArray();
            { // initialise the stack       
                s.push(new StackItem(NodeTree.this, false));
            }
            public boolean hasMoreElements() {
                return !s.isEmpty();
            }
            public Object nextElement() {
                StackItem next = (StackItem) s.pop();
                while (!next.ready) {
                    NodeTree root = next.root;
                    if (!root.right.isEmpty()) {
                        s.push(new StackItem((NodeTree) root.right, false));
                    }
                    // relocate the next line to get PreOrder or PostOrder
                    s.push(new StackItem(root, true));
                    if (!root.left.isEmpty()) {
                        s.push(new StackItem((NodeTree) root.left, false));
                    }
                    next = (StackItem) s.pop();
                }
                return next.root.data;
            }
        };
    }

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

}