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}