package bearmaps;

import org.junit.Test;
import static org.junit.Assert.assertEquals;
import edu.princeton.cs.algs4.Stopwatch;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

public class KDTreeTest {

    /* Tests code from nearest slides */
    @Test
    public void testNearestLecture() {
        Point p1 = new Point(2, 3);
        Point p2 = new Point(4, 2);
        Point p3 = new Point(4, 5);
        Point p4 = new Point(3, 3);
        Point p5 = new Point(1, 5);
        Point p6 = new Point(4, 4);
        KDTree kd = new KDTree(List.of(p1, p2, p3, p4, p5, p6));

        Point actual = kd.nearest(0, 7);
        Point expected = new Point(1, 5);
        assertEquals(expected, actual);
    }

    //Smaller random test
    @Test
    public void testSmallRandom() {
        testNearestRandom(5000, 500);
        testTiming(5000, 500);
    }

    //Larger random test
    @Test
    public void testLargeRandom() {
        testNearestRandom(100000, 10000);
        testTiming(100000, 10000);
    }

    /* Test Randomly with a large number of points
    <a href="https://www.youtube.com/watch?v=lp80raQvE5c&feature=youtu.be">
    Project 2b Walkthrough </a>
     */
    private void testNearestRandom(int points, int queries) {
        List<Point> testPoints = createNPoints(points);
        NaivePointSet naive = new NaivePointSet(testPoints);
        KDTree kd = new KDTree(testPoints);

        List<Point> nearestPoints = createNPoints(queries);
        for (Point p: nearestPoints) {
            Point expected = naive.nearest(p.getX(), p.getY());
            Point actual = kd.nearest(p.getX(), p.getY());
            assertEquals(expected, actual);
        }
    }

    /* Test timings of naive vs kd tree
    <a href="https://www.youtube.com/watch?v=3IdQJm9tw6Y&feature=youtu.be">
    Project 2b Walkthrough </a>
     */
    private void testTiming(int points, int queries) {
        List<Point> testPoints = createNPoints(points);
        NaivePointSet naive = new NaivePointSet(testPoints);
        KDTree kd = new KDTree(testPoints);

        List<Point> nearestPoints = createNPoints(queries);

        //Naive timing
        Stopwatch sw = new Stopwatch();
        for (Point p: nearestPoints) {
            naive.nearest(p.getX(), p.getY());
        }
        double naiveTime = sw.elapsedTime();
        System.out.println("Naive implementation for " + points
                + " points and " + queries + " queries."
               + "\nTotal time elapsed: " + naiveTime);

        //KD tree timing
        sw = new Stopwatch();
        for (Point p: nearestPoints) {
            kd.nearest(p.getX(), p.getY());
        }
        double kdTime = sw.elapsedTime();
        System.out.println("KDTree implementation for " + points
               +  " points and " + queries + " queries."
              +  "\nTotal time elapsed: " + kdTime);
    }

    //Creates random list of points of size n
    private List<Point> createNPoints(int n) {
        List<Point> points = new ArrayList<>();
        Random r = new Random(500);
        for (int i = 0; i < 5000; i++) {
            Point temp = new Point(r.nextDouble(), r.nextDouble());
            points.add(temp);
        }
        return points;
    }
}