package Examples;

/**
 * A class implementing unbalanced binary search tree.  Note that all
 * "matching" is based on the compareTo method. 
 *
 * <p>Adapted from original code by Mark Weiss.
 *
 * <p>Is this class correct....?
 *
 * @author Mark Allen Weiss
 *
 */

// ******************PUBLIC OPERATIONS*********************
// void insert( x )   --> Insert x
// void remove( x )   --> Remove x
// Comparable find( x )   --> Return item that matches x
// Comparable findMin( )  --> Return smallest item
// Comparable findMax( )  --> Return largest item
// boolean isEmpty( ) --> Return true if empty; else false
// void makeEmpty( )  --> Remove all items
// void printTree( )  --> Print tree in sorted order
public class BinarySearchTree {

    /**
     * Construct the tree.
     */
    public BinarySearchTree() {
        root = null;
    }

    /**
     * Insert x into the tree; duplicates are ignored.
     * @param x the item to insert.
     */
    public void insert(Comparable x) {
        // System.out.println(".") ;
        root = insert(x, root);
    }

    /**
     * A specification for insert, saying that after insert(x) x
     * should be in the tree.
     */
    public void insert_spec(Comparable x) {
        insert(x);
        assert (find(x) != null) : "POST";
    }

    /**
     * Remove from the tree. Nothing is done if x is not found.
     * @param x the item to remove.
     */
    public void remove(Comparable x) {
        root = remove(x, root);
    }

    /**
     * a specification for remove, saying that after the remove x
     * should no longer be in the tree.
     */
    public void remove_spec(Comparable x) {
        remove(x);
        assert (find(x) == null) : "POST";
    }

    /**
     * Find the smallest item in the tree.
     * @return smallest item or null if empty.
     */
    public Comparable findMin() {
        return elementAt(findMin(root));
    }

    /**
     * A partial spec of findMin, saying that the returned value, if not
     * null, should be an element of the tree.
     */
    public void findMin_spec() {
        boolean wasEmpty = isEmpty();
        Comparable x = findMin();
        assert (wasEmpty || find(x) == x) : "POST";
    }

    /**
     * Find the largest item in the tree.
     * @return the largest item of null if empty.
     */
    public Comparable findMax() {
        return elementAt(findMax(root));
    }

     /**
     * A partial spec of findMax, saying that the returned value, if not
     * null, should be an element of the tree.
     */
    public void findMax_spec() {
        boolean wasEmpty = isEmpty();
        Comparable x = findMax();
        assert (wasEmpty || find(x) == x) : "POST";
    }
    
    /**
     * Find an item in the tree.
     * @param x the item to search for.
     * @return the matching item or null if not found.
     */
    @Sequenic.T2.T2annotation.exclude
    public Comparable find(Comparable x) {
        return elementAt(find(x, root));
    }

    /**
     * Make the tree logically empty.
     */
    public void makeEmpty() {
        root = null;
    }

    public void makeEmpty_spec() {
        makeEmpty();
        assert isEmpty() ;
    }
    
    /**
     * Test if the tree is logically empty.
     * @return true if empty, false otherwise.
     */
    @Sequenic.T2.T2annotation.exclude
    public boolean isEmpty() {
        return root == null;
    }

    /**
     * Print the tree contents in sorted order.
     */
    /*
    private void printTree( ) {
    if( isEmpty( ) )
    System.out.println( "Empty tree" );
    else
    printTree( root );
    }
     */
    /**
     * Internal method to get element field.
     * @param t the node.
     * @return the element field or null if t is null.
     */
    private Comparable elementAt(BinaryNode t) {
        return t == null ? null : t.element;
    }

    /**
     * Internal method to insert into a subtree.
     * @param x the item to insert.
     * @param t the node that roots the tree.
     * @return the new root.
     */
    private BinaryNode insert(Comparable x, BinaryNode t) {
        /* 1*/ if (t == null) /* 2*/ {
            t = new BinaryNode(x, null, null);
        /* 3*/ } else if (x.compareTo(t.element) < 0) /* 4*/ {
            t.left = insert(x, t.left);
        /* 5*/ } else if (x.compareTo(t.element) > 0) /* 6*/ {
            t.right = insert(x, t.right);
        /* 7*/ } else /* 8*/;  // Duplicate; do nothing
		/* 9*/ return t;
    }

    class BinaryNode {

        Comparable element;
        BinaryNode left;
        BinaryNode right;

        BinaryNode(Comparable x, BinaryNode u, BinaryNode v) {
            element = x;
            left = u;
            right = v;
        }
    }

    /**
     * Internal method to remove from a subtree.
     * @param x the item to remove.
     * @param t the node that roots the tree.
     * @return the new root.
     */
    private BinaryNode remove(Comparable x, BinaryNode t) {
        if (t == null) {
            return t;   // Item not found; do nothing

        }
        if (x.compareTo(t.element) < 0) {
            t.left = remove(x, t.left);
        } else if (x.compareTo(t.element) > 0) {
            t.right = remove(x, t.right);
        } else if (t.left != null && t.right != null) // Two children
        {
            t.element = findMin(t.right).element;
            t.right = remove(t.element, t.right);
        } else {
            t = (t.left != null) ? t.left : t.right;
        }
        return t;
    }

    /**
     * Internal method to find the smallest item in a subtree.
     * @param t the node that roots the tree.
     * @return node containing the smallest item.
     */
    private BinaryNode findMin(BinaryNode t) {
        if (t == null) {
            return null;
        } else if (t.left == null) {
            return t;
        }
        return findMin(t.left);
    }

    /**
     * Internal method to find the largest item in a subtree.
     * @param t the node that roots the tree.
     * @return node containing the largest item.
     */
    private BinaryNode findMax(BinaryNode t) {
        if (t != null) {
            while (t.right != null) {
                t = t.right;
            }
        }
        return t;
    }

    /**
     * Internal method to find an item in a subtree.
     * @param x is item to search for.
     * @param t the node that roots the tree.
     * @return node containing the matched item.
     */
    private BinaryNode find(Comparable x, BinaryNode t) {
        if (t == null) {
            return null;
        }
        if (x.compareTo(t.element) < 0) {
            return find(x, t.left);
        } else if (x.compareTo(t.element) > 0) {
            return find(x, t.right);
        } else {
            return t;// Match
        }
    }
    /**
     * Internal method to print a subtree in sorted order.
     * @param t the node that roots the tree.
     */
    /*
    private void printTree( BinaryNode t )
    {
    if( t != null )
    {
    printTree( t.left );
    System.out.println( t.element );
    printTree( t.right );
    }
    }
     */
    /** The tree root. */
    private BinaryNode root;
    
    static public void main(String[] args) {
        // Calling T2 from here; see how it finds the mistake:
        Sequenic.T2.Main.main(BinarySearchTree.class.getName() + " --nmax=20000 --lenexec=7");
    }
    
}