package algs32.kdtree;
import algs12.Point2D;
import algs13.Queue;
import stdlib.*;

public class NearestNeighborCorrectnessTest {

  static int NUM_TARGETS = 1000;
  static int NUM_SIZES = 12;
  static int NUM_TESTS = 200;
  static int NUM_POSSIBLE_INIT = 1;
  static int TREE_SIZE_INIT = 0;
  static boolean ALLOW_DUPLICATES = true;
  static boolean SHOW_TREE_ON_FAILURE = true;
  static boolean STOP_AFTER_FIRST_FAILURE = true;
  static boolean CATCH_EXCEPTIONS = false;
  private static boolean passed = true;

  protected static Point2D nearest (KdTree kdtree, Point2D target) {
    if (!CATCH_EXCEPTIONS) {
      return kdtree.nearest (target);
    } else {
      try {
        return kdtree.nearest (target);
      } catch (Throwable e) {
        if (passed) {
          passed = false;
          e.printStackTrace ();
        }
        return new Point2D (666, 666);
      }
    }
  }
  private static boolean showInsertionException = true;
  protected static boolean insert (KdTree kdtree, Point2D p) {
    if (!CATCH_EXCEPTIONS) {
      kdtree.insert (p);
      return true;
    } else {
      try {
        kdtree.insert (p);
        return true;
      } catch (Throwable e) {
        if (showInsertionException) {
          showInsertionException = false;
          e.printStackTrace ();
        }
        passed = false;
        return false;
      }
    }
  }
  private static double random(int numPossible) {
    return StdRandom.uniform (numPossible)/(double)numPossible;
  }
  public static void main(String[] args) {
    //StdRandom.setSeed (0); // uncomment to get the same results over and over

    Queue<Point2D> queue = new Queue<> ();
    for (int i=0; i<NUM_TARGETS; i++)
      queue.enqueue(new Point2D(random(1000), random(1000)));

    // treeSize and numPossible vary each time around the test loop
    // trying small trees with few possible values for points to start
    // doubling the treeSize each time
    // keeping numPossible a power of 10 so that decimal fractions print nicely
    int numPossible = NUM_POSSIBLE_INIT;
    int treeSize = TREE_SIZE_INIT;
    int numTested = 0;
    int numPassed = 0;
    int numTreesAttempted = 0;
    int numTreesCreated = 0;
    test: for (int numsize=0; numsize<NUM_SIZES; numsize++) {
      StdOut.format ("trying treeSize %d\n", treeSize);
      for (int numtest=0; numtest<NUM_TESTS; numtest++) {
        PointSET brute = new PointSET();
        KdTree kdtree = new KdTree();

        boolean treeCreated = true;
        for (int i=0; i<treeSize; i++) {
          Point2D p = new Point2D(random (numPossible), random (numPossible));
          if (ALLOW_DUPLICATES || !brute.contains (p)) {
            if (!insert(kdtree, p)) treeCreated = false;
            brute.insert(p);
          }
        }
        numTreesAttempted ++;
        if (treeCreated) numTreesCreated ++;
        point: for (Point2D p : queue) {
          numTested ++;
          Point2D b = brute.nearest(p);
          Point2D k = nearest (kdtree, p);
          if (b==null) {
            if (k!=null) {
              printError (treeSize, brute, kdtree, p);
              if (STOP_AFTER_FIRST_FAILURE) break test; else continue point;
            }
          } else if (k==null) {
            printError (treeSize, brute, kdtree, p);
            if (STOP_AFTER_FIRST_FAILURE) break test; else continue test;
          } else if (p.distanceTo(b) - p.distanceTo (k) != 0.0) {
            printError (treeSize, brute, kdtree, p);
            if (STOP_AFTER_FIRST_FAILURE) break test; else continue point;
          }
          numPassed ++;
        }
      }
      treeSize += (treeSize==0) ? 1 : treeSize;
      if (numsize % 4==0) numPossible *= 10;
    }
    StdOut.format ("#NearestNeighbor %s: %d/%d passed, %d/%d trees created without thrown exception\n", passed ? "passed" : "failed", numPassed, numTested, numTreesCreated, numTreesAttempted);

  }
  private static void printError (int treeSize, PointSET brute, KdTree kdtree, Point2D p) {
    if (passed) {
      passed = false;
      StdOut.println ("Error!");
      //StdOut.println ("  treeSize should be " + treeSize);
      //if (brute.size() != treeSize) StdOut.println ("  duplicate points");
      StdOut.println ("  PointSET         = " + brute);
      StdOut.println ("  KdTree           = " + kdtree);
      StdOut.println ("  target           = " + p);
      StdOut.println ("  PointSET nearest = " + brute.nearest(p));
      StdOut.println ("  KdTree nearest   = " + nearest(kdtree, p));
      if (SHOW_TREE_ON_FAILURE) {
        kdtree.toGraphviz ();
        kdtree.draw ();
      }
    }
  }
}