/**
 * Generic class that implements a binary search tree, building upon the 
 * existing BinaryTree class.
 *   @param <E> the type of value stored, must be Comparable<E>
 *   @author Dave Reed 
 *   @version 2/15/16
 */
public class BinarySearchTree<E extends Comparable<? super E>> extends BinaryTree<E> {
    /**
     * Overrides the super.add method to add according to the BST property.
     *   @param value the value to be added to the tree
     */
    public void add(E value) {
        this.root = this.add(this.root, value);
    }
    private TreeNode<E> add(TreeNode<E> current, E value) {
        if (current == null) {
            return new TreeNode<E>(value, null, null);
        }

        if (value.compareTo(current.getData()) <= 0) {
            current.setLeft(this.add(current.getLeft(), value));
        }
        else {
            current.setRight(this.add(current.getRight(), value));
        }
        return current;
    }

    /**
     * Overrides the super.contains method to take advantage of binary search.
     *   @param value the value to be searched for
     *   @return true if that value is in the tree, otherwise false
     */
    public boolean contains(E value) {
        return this.contains(this.root, value);
    }
    private boolean contains(TreeNode<E> current, E value) {
        if (current == null) {
            return false;
        }
        else if (value.equals(current.getData())) {
                return true;
        }
        else if (value.compareTo(current.getData()) < 0) {
            return this.contains(current.getLeft(), value);
        }
        else {
            return this.contains(current.getRight(), value);
        }
    }

    /**
     * Selects the specified rank value from a binary search tree.
     *   @param rank the index for the desired value (0 <= rank < list size)
     *   @return the rank value, i.e., that value would appear in 
     *            index rank of a sorted list of tree values
     */
    public E select(int rank) throws IndexOutOfBoundsException {
        if (rank >= this.size()) {
            throw new IndexOutOfBoundsException();
        }
        return this.asList().get(rank);
    }

    /**
     * Finds the rank of a particular value from the binary search tree.
     *   @param value the value to be found
     *   @return the rank of that value in the tree, -1 if not found
     */
    public int rank(E value)  {
        return this.asList().indexOf(value);
    }
    
    public static void main(String[] args) {
        BinarySearchTree<Integer> tree = new BinarySearchTree<Integer>();
        tree.add(7);
        tree.add(2);
        tree.add(12);
        tree.add(1);
        tree.add(5);
        tree.add(6);
        tree.add(99);
        tree.add(88);
        System.out.println(tree);
        
        System.out.println("size = " + tree.size());
        System.out.println(tree.contains(2) + " " + tree.contains(7)
                                            + " " + tree.contains(8));

        tree.remove(99);
        tree.remove(7);
        System.out.println(tree);
        System.out.println("size = " + tree.size());
        System.out.println(tree.contains(2) + " " + tree.contains(7)
                                            + " " + tree.contains(8));
        
        for (int i = 0; i < tree.size(); i++) {
            int value = tree.select(i);
            System.out.println(i + ": " + value + " " + tree.rank(value));
        }
    }
}