package class9_3_BinarySearchTree_withRemove;

import edu.msoe.se1010.winPlotter.WinPlotter;

import java.util.Collection;
import java.util.Iterator;
import java.util.Set;

/**
 * This class is a super-cool combination
 * of a SortedArrayList and a LinkedList.
 *
 * Like the SortedArrayList, the elements are always sorted.
 * Like the LinkedList, once we find where something should be,
 * we can insert it in O(1) time just by editing a few links.
 *
 * @param <E> the type of the contained obects
 */
public class BinarySearchTree<E extends Comparable<E>> extends Object implements Set<E> {
    private Node root;

    private class Node {
        private Node left;
        private Node right;
        private E value;

        private Node(Node left, Node right, E value) {
            this.left = left;
            this.right = right;
            this.value = value;
        }
    }

    public boolean isEmpty() {
        return root == null;
    }

    public int size() {
        return size(root);
    }

    private int size(Node current) {
        if(current == null) {
            return 0;
        } else {
            return 1 + size(current.left) + size(current.right);
        }
    }

    public boolean add(E e) {
//        E value = root.value;
//        if(value.compareTo(e) < 0) /*...*/;
        if(root == null) {
            root = new Node(null, null, e);
        } else {
            add(root, e);
        }
        return true; // TODO: Should return false if present.
    }

    /**
     *
     * @param subRoot root of sub-tree (MUST NOT BE NULL)
     * @param e objce t to add
     */
    private void add(Node subRoot, E e) {
        if(e.compareTo(subRoot.value) < 0) {
            if(subRoot.left == null) {
                subRoot.left = new Node(null, null, e);
            } else {
                add(subRoot.left, e);
            }
        } else if(e.compareTo(subRoot.value) > 0) {
            if(subRoot.right == null) {
                subRoot.right = new Node(null, null, e);
            } else {
                add(subRoot.right, e);
            }
        } else {
            System.err.println("Warning: Replacing existing node");
            System.err.println("(Duplicate add)");
            subRoot.value = e;
        }
    }

    /**
     * Does NOT rebalance. (Of course, neither does add...)
     *
     * Removes the specified element from this set if it is present
     * (optional operation).  More formally, removes an element <tt>e</tt>
     * such that
     * <tt>(o==null&nbsp;?&nbsp;e==null&nbsp;:&nbsp;o.equals(e))</tt>, if
     * this set contains such an element.  Returns <tt>true</tt> if this set
     * contained the element (or equivalently, if this set changed as a
     * result of the call).  (This set will not contain the element once the
     * call returns.)
     *
     * @param o object to be removed from this set, if present
     * @return <tt>true</tt> if this set contained the specified element
     * @throws ClassCastException            if the type of the specified element
     *                                       is incompatible with this set
     *                                       (<a href="Collection.html#optional-restrictions">optional</a>)
     * @throws NullPointerException          if the specified element is null and this
     *                                       set does not permit null elements
     *                                       (<a href="Collection.html#optional-restrictions">optional</a>)
     * @throws UnsupportedOperationException if the <tt>remove</tt> operation
     *                                       is not supported by this set
     */
    @Override
    public boolean remove(Object o) {
        if(o == null) {
            throw new NullPointerException("This tree doesn't allow null elements. Null search key provided.");
        }

        E e;
        try {
            e = (E)o;
        } catch (ClassCastException ex) {
            return false;
        }
        if(root == null) {
            return false;
        }
        // find node.
        if(root.value.equals(e)) {
            throw new UnsupportedOperationException("I don't remove the root -- but it is similar to other cases.");
        }
        // Edge cases are handled.
        // No more early returns after this point in the method.

        // Find the node.  But don't walk off of the parent.
        // preconditions on loop: current points to a parent of the node, if the node is in the tree.
        // current is not null, and does not point to a node equal to the target.
        Node current = root;
        while((e.compareTo(current.value) < 0 && current.left != null && !current.left.value.equals(e)) ||
                (e.compareTo(current.value) >= 0 && current.right != null && !current.right.value.equals(e))) {
            if(e.compareTo(current.value) < 0) {
                current = current.left;
            } else {
                current = current.right;
            }
        }
        boolean isFound = true;
        if(e.compareTo(current.value) < 0) {
            throw new UnsupportedOperationException("I don't remove a node that is on the left of it's parent. But this case is symmetric with the right.");
        } else {
            if(current.right == null) {
                isFound = false;
            } else {
                /* Now we remove the node! */
                // easy cases
                Node parent = current;
                Node target = parent.right;


                // TODO: Complete
            }
        }

        return isFound;
    }




    public E find(E e) {
        return find(root,e).value;
    }

    /**
     * Returns <tt>true</tt> if this set contains the specified element.
     * More formally, returns <tt>true</tt> if and only if this set
     * contains an element <tt>e</tt> such that
     * <tt>(o==null&nbsp;?&nbsp;e==null&nbsp;:&nbsp;o.equals(e))</tt>.
     *
     * @param o element whose presence in this set is to be tested
     * @return <tt>true</tt> if this set contains the specified element
     * @throws ClassCastException   if the type of the specified element
     *                              is incompatible with this set
     *                              (<a href="Collection.html#optional-restrictions">optional</a>)
     * @throws NullPointerException if the specified element is null and this
     *                              set does not permit null elements
     *                              (<a href="Collection.html#optional-restrictions">optional</a>)
     */
    @Override
    public boolean contains(Object o) {
        E e;
        try {
            e  = (E)o;
        } catch (ClassCastException ex) {
            return false;
        }
        return find(root,e)!=null;
    }

    private Node find(Node subRoot, E e) {
        if(subRoot == null) {
            return null;
        } else if(e.compareTo(subRoot.value) == 0) {
            return subRoot;
        }
        if(e.compareTo(root.value) < 0) {
            return find(root.left,e);
        } else {
            return find(root.right,e);
        }
    }


    public void print() {
        printTree(root, 0);
    }

    private void printTree(Node current, int depth) {
        if(current != null) {
            printTree(current.left,depth+1);
            for(int i=0;i<depth;i++) {
                System.out.print(" ");
            }
            System.out.println(current.value);
            printTree(current.right,depth+1);
        }
    }

    /* --- BELOW THIS LINE ---- */
    /*  support for the draw method */
    /* ------------------------ */
    /**
     * The maximum depth to draw for the tree.
     * Actual tree may be taller or shorter than this.
     */
    private static final int DEFAULT_DEPTH = 4;
    /**
     * The margin as a fraction of the height of the box.
     * Node will be drawn with height AVAILABLE*(1-2*MARGIN_FRACTION)
     */
    private static final double MARGIN_FRACTION = 0.1;

    /**
     * Fudge factor to center strings
     */
    private static final int PIXELS_PER_CHAR = 6;
    private static final int WINDOW_WIDTH = 640;
    private static final int WINDOW_HEIGHT = 480;

    public void draw(WinPlotter plotter) {
        int depth = DEFAULT_DEPTH;
        plotter.erase();
        double maxX = 0.64;
        double maxY = 0.48;
        plotter.setPlotBoundaries(0,0,maxX,maxY);
        plotter.setWindowSize(WINDOW_WIDTH,WINDOW_HEIGHT);
        plotter.setVisible(true);

        drawSubtree(plotter,root,1,depth,0,0,maxX,maxY);
    }

    /**
     * Draw the sub-tree with the given root.
     * @param plotter plotter to draw on
     * @param root root of the subtree to draw, or null to not draw anything.
     * @param rootDepth depth of the root in the original tree (as path length from original root, PLUS ONE)
     * @param maxLeafDepth depth of the maximum leaf that can be drawn. (this subtree may have more or less depth)
     * @param minX bounds on area to draw in
     * @param minY bounds on area to draw in
     * @param maxX bounds on area to draw in
     * @param maxY bounds on area to draw in
     */
    private void drawSubtree(WinPlotter plotter, Node root, int rootDepth, int maxLeafDepth,
                             double minX, double minY, double maxX, double maxY) {
        if(root == null) {
            /* Don't draw empty sub-tree */
            return;
        }

        int levelsThisSubtree = maxLeafDepth - (rootDepth-1);
        double treeHeight = maxY - minY;
        double nodeHeight = treeHeight/levelsThisSubtree; // double division.
        double margin = nodeHeight * MARGIN_FRACTION;
        double boxTop = maxY - margin;
        double boxBottom = maxY - nodeHeight + margin;
        double boxHeight = boxTop - boxBottom;
        double centerX = (minX+maxX)/2;
        double boxLeft = centerX - boxHeight/2;
        double boxRight = centerX + boxHeight/2;
        drawBox(plotter, boxLeft, boxTop, boxRight, boxBottom);
        String text = root.value.toString();
        double textX = centerX-text.length()*(maxX-minX)*PIXELS_PER_CHAR/
                ((double)WINDOW_WIDTH)*Math.pow(2,rootDepth-2); // TODO: This is ugly. Make beautiful.

        plotter.printAt(textX,(boxBottom+boxTop)/2,text);

        if(root.left != null) {
            plotter.moveTo(centerX,boxBottom);
            double leftCenterX = minX+(centerX-minX)/2;
            plotter.drawTo(leftCenterX,boxBottom-2*margin);
            drawSubtree(plotter, root.left, rootDepth + 1, maxLeafDepth, minX, minY, (minX + maxX) / 2, maxY - nodeHeight);
        }
        if(root.right != null) {
            plotter.moveTo(centerX,boxBottom);
            double rightCenterX = minX+(3*(centerX-minX)/2);
            plotter.drawTo(rightCenterX,boxBottom-2*margin);
            drawSubtree(plotter, root.left, rootDepth + 1, maxLeafDepth, minX, minY, (minX + maxX) / 2, maxY - nodeHeight);
        }
        drawSubtree(plotter,root.right,rootDepth+1,maxLeafDepth,(minX+maxX)/2,minY,maxX,maxY-nodeHeight);
    }

    /**
     * Draw box bounded by the variables below, in plotting units.
     * @param plotter WinPlotter to draw on
     * @param leftX top-left x
     * @param topY top-left y
     * @param rightX bottom-right x
     * @param bottomY bottom-right y
     */
    private void drawBox(WinPlotter plotter, double leftX, double topY, double rightX, double bottomY) {
        plotter.setPenColor(0,0,0);
        plotter.moveTo(leftX,topY);
        plotter.drawTo(rightX,topY);
        plotter.drawTo(rightX,bottomY);
        plotter.drawTo(leftX,bottomY);
        plotter.drawTo(leftX,topY);
    }

    //---------------------------
    // METHODS BEYOND THIS POINT NOT IMPLEMENTED
    //----------------------------

    /**
     * Returns an iterator over the elements in this set.  The elements are
     * returned in no particular order (unless this set is an instance of some
     * class that provides a guarantee).
     *
     * @return an iterator over the elements in this set
     */
    @Override
    public Iterator<E> iterator() {
        return null;
    }

    /**
     * Returns an array containing all of the elements in this set.
     * If this set makes any guarantees as to what order its elements
     * are returned by its iterator, this method must return the
     * elements in the same order.
     * <p>
     * <p>The returned array will be "safe" in that no references to it
     * are maintained by this set.  (In other words, this method must
     * allocate a new array even if this set is backed by an array).
     * The caller is thus free to modify the returned array.
     * <p>
     * <p>This method acts as bridge between array-based and collection-based
     * APIs.
     *
     * @return an array containing all the elements in this set
     */
    @Override
    public Object[] toArray() {
        return new Object[0];
    }

    /**
     * Returns an array containing all of the elements in this set; the
     * runtime type of the returned array is that of the specified array.
     * If the set fits in the specified array, it is returned therein.
     * Otherwise, a new array is allocated with the runtime type of the
     * specified array and the size of this set.
     * <p>
     * <p>If this set fits in the specified array with room to spare
     * (i.e., the array has more elements than this set), the element in
     * the array immediately following the end of the set is set to
     * <tt>null</tt>.  (This is useful in determining the length of this
     * set <i>only</i> if the caller knows that this set does not contain
     * any null elements.)
     * <p>
     * <p>If this set makes any guarantees as to what order its elements
     * are returned by its iterator, this method must return the elements
     * in the same order.
     * <p>
     * <p>Like the {@link #toArray()} method, this method acts as bridge between
     * array-based and collection-based APIs.  Further, this method allows
     * precise control over the runtime type of the output array, and may,
     * under certain circumstances, be used to save allocation costs.
     * <p>
     * <p>Suppose <tt>x</tt> is a set known to contain only strings.
     * The following code can be used to dump the set into a newly allocated
     * array of <tt>String</tt>:
     * <p>
     * <pre>
     *     String[] y = x.toArray(new String[0]);</pre>
     *
     * Note that <tt>toArray(new Object[0])</tt> is identical in function to
     * <tt>toArray()</tt>.
     *
     * @param a the array into which the elements of this set are to be
     *          stored, if it is big enough; otherwise, a new array of the same
     *          runtime type is allocated for this purpose.
     * @return an array containing all the elements in this set
     * @throws ArrayStoreException  if the runtime type of the specified array
     *                              is not a supertype of the runtime type of every element in this
     *                              set
     * @throws NullPointerException if the specified array is null
     */
    @Override
    public <T> T[] toArray(T[] a) {
        return null;
    }

    /**
     * Returns <tt>true</tt> if this set contains all of the elements of the
     * specified collection.  If the specified collection is also a set, this
     * method returns <tt>true</tt> if it is a <i>subset</i> of this set.
     *
     * @param c collection to be checked for containment in this set
     * @return <tt>true</tt> if this set contains all of the elements of the
     * specified collection
     * @throws ClassCastException   if the types of one or more elements
     *                              in the specified collection are incompatible with this
     *                              set
     *                              (<a href="Collection.html#optional-restrictions">optional</a>)
     * @throws NullPointerException if the specified collection contains one
     *                              or more null elements and this set does not permit null
     *                              elements
     *                              (<a href="Collection.html#optional-restrictions">optional</a>),
     *                              or if the specified collection is null
     * @see #contains(Object)
     */
    @Override
    public boolean containsAll(Collection<?> c) {
        return false;
    }

    /**
     * Adds all of the elements in the specified collection to this set if
     * they're not already present (optional operation).  If the specified
     * collection is also a set, the <tt>addAll</tt> operation effectively
     * modifies this set so that its value is the <i>union</i> of the two
     * sets.  The behavior of this operation is undefined if the specified
     * collection is modified while the operation is in progress.
     *
     * @param c collection containing elements to be added to this set
     * @return <tt>true</tt> if this set changed as a result of the call
     * @throws UnsupportedOperationException if the <tt>addAll</tt> operation
     *                                       is not supported by this set
     * @throws ClassCastException            if the class of an element of the
     *                                       specified collection prevents it from being added to this set
     * @throws NullPointerException          if the specified collection contains one
     *                                       or more null elements and this set does not permit null
     *                                       elements, or if the specified collection is null
     * @throws IllegalArgumentException      if some property of an element of the
     *                                       specified collection prevents it from being added to this set
     * @see #add(Object)
     */
    @Override
    public boolean addAll(Collection<? extends E> c) {
        return false;
    }

    /**
     * Retains only the elements in this set that are contained in the
     * specified collection (optional operation).  In other words, removes
     * from this set all of its elements that are not contained in the
     * specified collection.  If the specified collection is also a set, this
     * operation effectively modifies this set so that its value is the
     * <i>intersection</i> of the two sets.
     *
     * @param c collection containing elements to be retained in this set
     * @return <tt>true</tt> if this set changed as a result of the call
     * @throws UnsupportedOperationException if the <tt>retainAll</tt> operation
     *                                       is not supported by this set
     * @throws ClassCastException            if the class of an element of this set
     *                                       is incompatible with the specified collection
     *                                       (<a href="Collection.html#optional-restrictions">optional</a>)
     * @throws NullPointerException          if this set contains a null element and the
     *                                       specified collection does not permit null elements
     *                                       (<a href="Collection.html#optional-restrictions">optional</a>),
     *                                       or if the specified collection is null
     * @see #remove(Object)
     */
    @Override
    public boolean retainAll(Collection<?> c) {
        return false;
    }

    /**
     * Removes from this set all of its elements that are contained in the
     * specified collection (optional operation).  If the specified
     * collection is also a set, this operation effectively modifies this
     * set so that its value is the <i>asymmetric set difference</i> of
     * the two sets.
     *
     * @param c collection containing elements to be removed from this set
     * @return <tt>true</tt> if this set changed as a result of the call
     * @throws UnsupportedOperationException if the <tt>removeAll</tt> operation
     *                                       is not supported by this set
     * @throws ClassCastException            if the class of an element of this set
     *                                       is incompatible with the specified collection
     *                                       (<a href="Collection.html#optional-restrictions">optional</a>)
     * @throws NullPointerException          if this set contains a null element and the
     *                                       specified collection does not permit null elements
     *                                       (<a href="Collection.html#optional-restrictions">optional</a>),
     *                                       or if the specified collection is null
     * @see #remove(Object)
     * @see #contains(Object)
     */
    @Override
    public boolean removeAll(Collection<?> c) {
        return false;
    }

    /**
     * Removes all of the elements from this set (optional operation).
     * The set will be empty after this call returns.
     *
     * @throws UnsupportedOperationException if the <tt>clear</tt> method
     *                                       is not supported by this set
     */
    @Override
    public void clear() {

    }
}