package class7_1_BinarySearchTree_051;

import edu.msoe.se1010.winPlotter.WinPlotter;

import java.util.Comparator;

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

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

    private E find(Node subRoot, E e) {
        if(subRoot == null) {
            return null;
        } else if(e.compareTo(subRoot.value) == 0) {
            return subRoot.value;
        }
        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);
    }
}