package class7_1_BinarySearchTree_021;

import edu.msoe.se1010.winPlotter.WinPlotter;

/**
 * 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>> {
    private Node root;

    public void add(E element) {
        if(root == null) {
            root = new Node(null,null,element);
        } else {
            add(root, element);
        }
    }

    private void add(Node subRoot, E element) {
        if(subRoot.value.compareTo(element) < 0) {
            if(subRoot.left == null) {
                subRoot.left = new Node(null, null, element);
            } else {
                add(subRoot.left, element);
            }
        } else if(subRoot.value.compareTo(element) > 0) {
            if(subRoot.right == null) {
                subRoot.right = new Node(null,null,element);
            } else {
                add(subRoot.right, element);
            }
        } else { // the two are equal
            System.err.println("Warning: attempt to add an existing node");
            System.err.println("Overwriting previous value");
            subRoot.value = element;
        }
    }


    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 subTreeRoot) {
        if(subTreeRoot == null) {
            return 0;
        } else {
            return 1+size(subTreeRoot.left)
                    +size(subTreeRoot.right);
        }
    }

    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);
    }
}