package bearmaps;

import java.util.List;

public class KDTree {
    /* @source <a href = "https://www.youtube.com/watch?v=irkJ4gczM0I&feature=youtu.be">
    Project 2b Walkthrough </a>
     */

    //Enum
    private static final boolean HORIZONTAL = false;
    private static final boolean VERTICAL = true;

    //Declaration of private class
    private class Node {
        private Point p;
        private boolean orientation;
        private Node leftChild;
        private Node rightChild;

        Node(Point p, boolean orientation) {
            this.p = p;
            this.orientation = orientation;
        }

        //Returns this Node's point
        public Point getPoint() {
            return this.p;
        }

        //Calculates distance between this and parameter Point other
        public double getDistanceBetween(Point other) {
            double diffInX = p.getX() - other.getX();
            double diffInY = p.getY() - other.getY();
            return Math.sqrt(Math.pow(diffInX, 2) + Math.pow(diffInY, 2));
        }
    }

    //Declaration of instance variables
    private Node root;

    /* Basic Constructor */
    public KDTree(List<Point> points) {
        for (Point p: points) {
            root = add(p, root, HORIZONTAL);
        }
    }

    //Insert method
    private Node add(Point p, Node n, boolean orientation) {
        if (n == null) {
            return new Node(p, orientation);
        }
        if (p.equals(n.p)) {
            return n;
        }

        int compare = comparePoints(p, n.getPoint(), orientation);
        if (compare < 0) {
            n.leftChild = add(p, n.leftChild, !orientation);
        } else {
            n.rightChild = add(p, n.rightChild, !orientation);
        }
        return n;
    }

    /* Compare two points with a given orientation */
    private int comparePoints(Point a, Point b, boolean orientation) {
        if (orientation == HORIZONTAL) {
            return Double.compare(a.getX(), b.getX());
        } else {
            return Double.compare(a.getY(), b.getY());
        }
    }
    /* Returns the closest point to the inputted coordinates.
    This should take O(logN) time on average, where N is the number of points.
     */
    public Point nearest(double x, double y) {
        Point goal = new Point(x, y);
        return nearestHelper(root, goal, root, HORIZONTAL).getPoint();
    }

    //Helper method for nearest
    private Node nearestHelper(Node n, Point goal, Node best, boolean orientation) {
        if (n == null) {
            return best;
        }
        if (n.getDistanceBetween(goal) < best.getDistanceBetween(goal)) {
            best = n;
        }
        Node goodSide = null;
        Node badSide = null;
        if (comparePoints(goal, n.getPoint(), orientation) < 0) {
            goodSide = n.leftChild;
            badSide = n.rightChild;
        } else {
            goodSide = n.rightChild;
            badSide = n.leftChild;
        }

        //Determine best pont on bad side
        Point bestBadSidePoint = null;
        if (orientation == HORIZONTAL) {
            bestBadSidePoint = new Point(n.getPoint().getX(), goal.getY());
        } else {
            bestBadSidePoint = new Point(goal.getX(), n.getPoint().getY());
        }
        best = nearestHelper(goodSide, goal, best, !orientation);

        //Pruning rule
        if (Point.distance(bestBadSidePoint, goal) < Point.distance(best.getPoint(), goal)) {
            best = nearestHelper(badSide, goal, best, !orientation);
        }
        return best;
    }
}