/*
 * From C:\Dropbox\InClass15q3\cs2852_prep\class8_2_BinarySearchTree_051_prep
 * Yoder
 */
package class10_1_TreeRotations_start;

import edu.msoe.se1010.winPlotter.WinPlotter;

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

/**
 * 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;
    }

    /**
     *
     * @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;
        }
    }

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

    public boolean contains(Object o) {
        E e;
        try {
            e = (E) o;
        } catch (ClassCastException ex) {
            return false; // cannot be equal if wrong type given.
        }
        return find(root, e) != null;
    }

    /**
     * Rotate the tree around the given node.
     * If e is null, rotates around the root.
     * @param e
     */
    public void rotateLeft(E e) {
        Node rootsParent;
        Node subRoot;
        if(e == null) {
            rootsParent = null;
            subRoot = root;
        } else {
            rootsParent = findParent(null, root, e);
            if (rootsParent == null) {
                subRoot = find(root, e);
            } else if (rootsParent.left != null
                    && rootsParent.left.value.equals(e)) {
                subRoot = rootsParent.left;
            } else if (rootsParent.right != null
                    && rootsParent.right.value.equals(e)) {
                subRoot = rootsParent.right;
            } else {
                throw new UnsupportedOperationException("Node could not be found: " + e);
                // TODO: Node could not be found?
            }
        }
        if(root == null || root.right == null) {
            throw new IllegalArgumentException("Must select a node in the tree that has a right " +
                    "child.");
        }
        rotateLeft(subRoot,rootsParent);
    }

    private void rotateLeft(Node subRoot, Node rootsParent) {
        // 0. Save middle
        Node middle = subRoot.right.left;
        // 1. Root becomes right child's left child
        subRoot.right.left = subRoot;
        // 2. Former right child becomes root.
        if(rootsParent == null) {
            this.root = subRoot.right;
        } else if(rootsParent.left == subRoot) {
            rootsParent.left = subRoot.right;
        } else { // rootsParent.right == subRoot
            rootsParent.right = subRoot.right;
        }
        // 3. Former right child's left child
        //    becomes former root's right child
        subRoot.right = middle;
    }

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

    /**
     * Note subtle change:
     * @param subRoot root of subtree to search
     * @param e element to search for
     * @return NOW RETURNS NODE, not VALUE
     */
    private Node find(Node subRoot, E e) {
        if(subRoot == null) {
            return null;
        } else if(e.compareTo(subRoot.value) == 0) {
            return subRoot;
        }
        if(e.compareTo(subRoot.value) < 0) {
            return find(subRoot.left,e);
        } else {
            return find(subRoot.right,e);
        }
    }

    @Override
    public void clear() {
        root = null;
    }

    /**
     * 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) {
        E e;
        try {
            e = (E) o;
        } catch (ClassCastException ex) {
            return false; // cannot be equal if wrong type given.
        }
        return false;
    }

//    private boolean remove(Node curr, E e) {
//        if()
//        int direction = .compareTo()
//        if()
//    }

    //-------- BELOW THIS LINE ARE PRINTING/DISPLAYING methods -----
    // useful for debugging
    //--------------------------------------------------------------

    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 = 5;
    /**
     * 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 = 7;
    private static final int WINDOW_WIDTH = 600;
    private static final int WINDOW_HEIGHT = 300;  //480;
    private static final int PIXELS_PER_UNIT = 100;

    public void draw(WinPlotter plotter) {
        int depth = DEFAULT_DEPTH;
        plotter.erase();
        double maxX = WINDOW_WIDTH / PIXELS_PER_UNIT;
        double maxY = WINDOW_HEIGHT / PIXELS_PER_UNIT;
        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);
    }


    //------------------------------------
    // BELOW THIS LINE ARE UNIMPLEMENTED METHODS
    //------------------------------------

    @Override
    public Iterator<E> iterator() {
        return null;
    }

    @Override
    public Object[] toArray() {
        return new Object[0];
    }

    @Override
    public <T> T[] toArray(T[] a) {
        return null;
    }

    @Override
    public boolean containsAll(Collection<?> c) {
        return false;
    }

    @Override
    public boolean addAll(Collection<? extends E> c) {
        return false;
    }

    @Override
    public boolean retainAll(Collection<?> c) {
        return false;
    }

    @Override
    public boolean removeAll(Collection<?> c) {
        return false;
    }

    @Override
    public Spliterator<E> spliterator() {
        return null;
    }
}