import java.util.Comparator;

/**
 * A binary search tree implementation.In a BST, all nodes to the left of the
 * root are smaller than the root, and all nodes to the right of the root are
 * larger than the root. Also, every sub-tree is a BST.
 *
 * @author Mark Young (A00000000)
 * @param <E> the base type for this BST
 */
public class BinarySearchTree<E extends Comparable<? super E>> {

    private BSTNode root;
    private Comparator<? super E> comp;
    private int numInTree;

    /**
     * Create a BST using the natural ordering of the base class.
     */
    public BinarySearchTree() {
        this((o1, o2) -> o1.compareTo(o2));
    }

    /**
     * Create a BST using a custom Comparator.
     *
     * @param reqComp the comparator to order this tree with.
     */
    public BinarySearchTree(Comparator<? super E> reqComp) {
        root = null;
        numInTree = 0;
        comp = reqComp;
    }

    /**
     * Returns whether this BST contains the given item.
     *
     * @param item the item to test for.
     * @return true if {@code item} is in this BST; false otherwise.
     */
    public boolean contains(E item) {
        BSTNode cur = root;
        while (cur != null) {
            int diff = comp.compare(item, cur.data);
            if (diff < 0) { // item < root
                cur = cur.left;
            } else if (diff > 0) { // item > root
                cur = cur.right;
            } else { // item == root
                return true;
            }
        }

        // item not found
        return false;
    }

    /**
     * Adds the given item to this BST.
     *
     * @param anItem the item to add.
     * @return true if the item was added; false otherwise.
     */
    public boolean insert(E anItem) {
        int oldCount = numInTree;
        root = insertNode(anItem, root);
        return numInTree > oldCount;
    }

    /**
     * Remove the given item from this BST.
     *
     * @param anItem the item to remove.
     * @return true if {@code anItem} was deleted; false otherwise.
     */
    public boolean delete(E anItem) {
        int oldCount = numInTree;
        root = deleteNode(anItem, root);
        return numInTree < oldCount;
    }

    /**
     * Creates a String representation of this BST. The string is a diagram of
     * the tree, rotated 90 degrees counter-clockwise.
     *
     * @return a String diagram of this BST.
     */
    @Override
    public String toString() {
        return nodeToString(2, root);
    }

    /**
     * Inserts a new Node containing anItem in the BST rooted at cur, unless
     * there's already one there.
     *
     * @param anItem the value being inserted into this BST.
     * @param cur the root of the sub-tree anItem must be in.
     * @return the root of the sub-tree resulting from the insertion.
     */
    private BSTNode insertNode(E anItem, BSTNode cur) {
        // current subtree is empty
        if (cur == null) {
            // this item is new to the tree
            ++numInTree;
            // create a new node and return it
            return new BSTNode(anItem);
        }

        // find which subtree (if either) this item belongs in
        int diff = comp.compare(anItem, cur.data);
        if (diff < 0) { // anItem < cur.data
            // insert to the left
            cur.left = insertNode(anItem, cur.left);
        } else if (diff > 0) { // anItem > cur.data
            // insert to the right
            cur.right = insertNode(anItem, cur.right);
        } // else anItem == cur.data, so item already present (nothing to do)

        // return the root of this subtree
        return cur;
    }

    /**
     * Removes the Node containing anItem from the BST rooted at cur, if it's
     * there.
     *
     * @param anItem the value being inserted into this BST.
     * @param cur the root of the sub-tree anItem must be in.
     * @return the root of the sub-tree resulting from the insertion.
     */
    private BSTNode deleteNode(E anItem, BSTNode cur) {
        // if cur == null then the item was not in the tree,
        // so there's nothing to do!
        if (cur != null) {
            // find which side of the root the item should be on
            int diff = comp.compare(anItem, cur.data);
            if (diff < 0) { // anItem < cur.data
                // delete from the left subtree
                cur.left = deleteNode(anItem, cur.left);
            } else if (diff > 0) { // anItem > cur.data
                // delete from the right subtree
                cur.right = deleteNode(anItem, cur.right);
            } else { // anItem == cur.data
                // deleting the value at this node
                if (cur.left == null) { // this node has no smaller children
                    // replace this node with its right child
                    cur = cur.right;
                    --numInTree;
                } else if (cur.right == null) { // ... has no larger children
                    // replce this node with its left child
                    cur = cur.left;
                    --numInTree;
                } else { // this node has smaller AND larger children
                    // replace this node's data with smallest value on right
                    cur.data = minRight(cur.right);
                    // delete that value from the tree on the right
                    cur.right = deleteNode(cur.data, cur.right);
                }
            }
        }

        // return the root of this subtree
        return cur;
    }

    /**
     * Finds the smallest value on the right (larger) side of the given node.
     *
     * @param cur the root of the sub-tree to search.
     * @return the smallest value in that sub-tree.
     */
    private E minRight(BSTNode cur) {
        // while this node has smaller children...
        while (cur.left != null) {
            // go left
            cur = cur.left;
        }

        // return the data in this node with no smaller children
        return cur.data;
    }

    private static final int EXTRA_INDENT = 6;

    /**
     * Make a diagram of a rooted part of this BST.
     *
     * @param indent how many spaces the root node should be indented.
     * @param root the root node of this sub-tree.
     * @return a String representing this sub-tree.
     */
    private String nodeToString(int indent, BSTNode root) {
        if (root == null) { // subtree is empty
            // end recursion, return indented String representing empty tree
            return String.format("%" + indent + "s%s", "", "--");
        }

        // non-empty subtree
        return String.format(
                // right subtree, new line, spaces, root, new line, left subtree
                "%s%n%" + indent + "s%s%n%s",
                // the right subtree, indented another 4 spaces
                nodeToString(indent + EXTRA_INDENT, root.right),
                // the root, indented the given number of spaces
                "",
                root.data.toString(),
                // the left subtree, indented another four spaces
                nodeToString(indent + EXTRA_INDENT, root.left));
    }

    /**
     * A class to hold the data plus links for left and right children/subtrees.
     */
    private class BSTNode {

        E data;
        BSTNode right, left;

        /**
         * Create a new Node not linked into the structure.
         *
         * @param reqData the data for the new node.
         */
        public BSTNode(E reqData) {
            this(reqData, null, null);
        }

        /**
         * Create a new Node linked into the structure.
         *
         * @param reqData the data for the new node.
         * @param reqLeft the root of the left sub-tree.
         * @param reqRight the root of the right sub-tree.
         */
        public BSTNode(E reqData, BSTNode reqLeft, BSTNode reqRight) {
            data = reqData;
            left = reqLeft;
            right = reqRight;
        }
    }

}