001package algs32.kdtree; 002import java.util.TreeSet; 003import algs12.Point2D; 004import algs13.Queue; 005import stdlib.*; 006 007public class RangeSearchCorrectnessTest { 008 009 static int NUM_TARGETS = 1000; 010 static int NUM_SIZES = 12; 011 static int NUM_TESTS = 200; 012 static int NUM_POSSIBLE_INIT = 1; 013 static int TREE_SIZE_INIT = 0; 014 static boolean ALLOW_DUPLICATES = true; 015 static boolean SHOW_TREE_ON_FAILURE = true; 016 static boolean STOP_AFTER_FIRST_FAILURE = true; 017 static boolean CATCH_EXCEPTIONS = false; 018 private static boolean passed = true; 019 020 protected static Iterable<Point2D> range(KdTree kdtree, RectHV target) { 021 if (!CATCH_EXCEPTIONS) { 022 return kdtree.range (target); 023 } else { 024 try { 025 return kdtree.range (target); 026 } catch (Throwable e) { 027 if (passed) { 028 passed = false; 029 e.printStackTrace (); 030 } 031 return null; 032 } 033 } 034 } 035 private static boolean showInsertionException = true; 036 protected static boolean insert(KdTree kdtree, Point2D p) { 037 if (!CATCH_EXCEPTIONS) { 038 kdtree.insert (p); 039 return true; 040 } else { 041 try { 042 kdtree.insert (p); 043 return true; 044 } catch (Throwable e) { 045 if (showInsertionException) { 046 showInsertionException = false; 047 e.printStackTrace (); 048 } 049 passed = false; 050 return false; 051 } 052 } 053 } 054 private static double random(int numPossible) { 055 return StdRandom.uniform (numPossible)/(double)numPossible; 056 } 057 public static void main(String[] args) { 058 //StdRandom.setSeed (0); // uncomment to get the same results over and over 059 060 Queue<RectHV> queue = new Queue<> (); 061 while (queue.size () < NUM_TARGETS) { 062 double x1 = random (1000); 063 double x2 = random (1000); 064 double y1 = random (1000); 065 double y2 = random (1000); 066 double xmin = Math.min (x1, x2); 067 double xmax = Math.max (x1, x2); 068 double ymin = Math.min (y1, y2); 069 double ymax = Math.max (y1, y2); 070 RectHV rect = new RectHV (xmin, ymin, xmax, ymax); 071 if (rect.width () * rect.height () > 0.25) 072 continue; // rectangle is too large 073 queue.enqueue(rect); 074 } 075 076 // treeSize and numPossible vary each time around the test loop 077 // trying small trees with few possible values for points to start 078 // doubling the treeSize each time 079 // keeping numPossible a power of 10 so that decimal fractions print nicely 080 int numPossible = NUM_POSSIBLE_INIT; 081 int treeSize = TREE_SIZE_INIT; 082 int numTested = 0; 083 int numPassed = 0; 084 int numTreesAttempted = 0; 085 int numTreesCreated = 0; 086 test: for (int numsize=0; numsize<NUM_SIZES; numsize++) { 087 StdOut.format ("trying treeSize %d\n", treeSize); 088 for (int numtest=0; numtest<NUM_TESTS; numtest++) { 089 PointSET brute = new PointSET(); 090 KdTree kdtree = new KdTree(); 091 092 boolean treeCreated = true; 093 for (int i=0; i<treeSize; i++) { 094 Point2D p = new Point2D(random (numPossible), random (numPossible)); 095 if (ALLOW_DUPLICATES || !brute.contains (p)) { 096 if (!insert(kdtree, p)) treeCreated = false; 097 brute.insert(p); 098 } 099 } 100 numTreesAttempted ++; 101 if (treeCreated) numTreesCreated ++; 102 rect: for (RectHV r : queue) { 103 numTested ++; 104 // check to see that the results are the same 105 TreeSet<Point2D> set = new TreeSet<> (); 106 for (Point2D p : brute.range(r)) 107 set.add (p); 108 Iterable<Point2D> kdtreeRange = range (kdtree, r); 109 if (kdtreeRange == null) { 110 printError (treeSize, brute, kdtree, r); 111 if (STOP_AFTER_FIRST_FAILURE) break test; else continue rect; 112 } 113 for (Point2D p : kdtreeRange) 114 if (! set.remove (p)) { 115 if (passed) StdOut.format ("KdTree range has extra %s\n", p); 116 printError (treeSize, brute, kdtree, r); 117 if (STOP_AFTER_FIRST_FAILURE) break test; else continue rect; 118 } 119 for (Point2D p : set) { 120 if (passed) StdOut.format ("KdTree range missed %s\n", p); 121 printError (treeSize, brute, kdtree, r); 122 if (STOP_AFTER_FIRST_FAILURE) break test; else continue rect; 123 } 124 numPassed ++; 125 } 126 } 127 treeSize += (treeSize==0) ? 1 : treeSize; 128 if (numsize % 4==0) numPossible *= 10; 129 } 130 StdOut.format ("#RangeSearch %s: %d/%d passed, %d/%d trees created without thrown exception\n", passed ? "passed" : "failed", numPassed, numTested, numTreesCreated, numTreesAttempted); 131 } 132 private static void printError (int treeSize, PointSET brute, KdTree kdtree, RectHV r) { 133 if (passed) { 134 passed = false; 135 StdOut.println ("Error!"); 136 StdOut.println (" treeSize should be " + treeSize); 137 //if (brute.size() != treeSize) StdOut.println (" duplicate points"); 138 StdOut.println (" PointSET = " + brute); 139 StdOut.println (" KdTree = " + kdtree); 140 StdOut.println (" target = " + r); 141 StdOut.println (" PointSET range = " + brute.range(r)); 142 StdOut.println (" KdTree range = " + range (kdtree, r)); 143 if (SHOW_TREE_ON_FAILURE) { 144 kdtree.toGraphviz (); 145 kdtree.draw (); 146 } 147 } 148 } 149}