Fast implementation of QuadTree

tests/BBoxHierarchyTest.cpp

 /*
  * Copyright 2012 Google Inc.
  *
  * Use of this source code is governed by a BSD-style license that can be
  * found in the LICENSE file.
  */
 
 #include "Test.h"
 #include "SkRandom.h"
 #include "SkQuadTree.h"
 #include "SkRTree.h"
 #include "SkTSort.h"
 
 static const size_t RTREE_MIN_CHILDREN = 6;
 static const size_t RTREE_MAX_CHILDREN = 11;
-static const size_t QUADTREE_MIN_CHILDREN = 4;
+static const size_t QUADTREE_MIN_CHILDREN = 0;
 static const size_t QUADTREE_MAX_CHILDREN = 0; // No hard limit for quadtree
 
 static const int NUM_RECTS = 200;
 static const size_t NUM_ITERATIONS = 100;
 static const size_t NUM_QUERIES = 50;
 
 static const int MAX_SIZE = 1000;
 
 struct DataRect {
     SkIRect rect;
@@ skipping 92 matching lines @@
         tree->flushDeferredInserts();
         run_queries(reporter, rand, rects, *tree);
         REPORTER_ASSERT(reporter, NUM_RECTS == tree->getCount());
         REPORTER_ASSERT(reporter,
             ((expectedDepthMin <= 0) || (expectedDepthMin <= tree->getDepth())) &&
             ((expectedDepthMax <= 0) || (expectedDepthMax >= tree->getDepth())));
         tree->clear();
         REPORTER_ASSERT(reporter, 0 == tree->getCount());
 
         // Then try immediate inserts
-        for (int i = 0; i < NUM_RECTS; ++i) {
+        tree->insert(rects[0].data, rects[0].rect);
+        tree->flushDeferredInserts();
+        for (int i = 1; i < NUM_RECTS; ++i) {
             tree->insert(rects[i].data, rects[i].rect);
         }
         run_queries(reporter, rand, rects, *tree);
         REPORTER_ASSERT(reporter, NUM_RECTS == tree->getCount());
         REPORTER_ASSERT(reporter,
             ((expectedDepthMin <= 0) || (expectedDepthMin <= tree->getDepth())) &&
             ((expectedDepthMax <= 0) || (expectedDepthMax >= tree->getDepth())));
         tree->clear();
         REPORTER_ASSERT(reporter, 0 == tree->getCount());
 
         // And for good measure try immediate inserts, but in reversed order
-        for (int i = NUM_RECTS - 1; i >= 0; --i) {
+        tree->insert(rects[NUM_RECTS - 1].data, rects[NUM_RECTS - 1].rect);
+        tree->flushDeferredInserts();
+        for (int i = NUM_RECTS - 2; i >= 0; --i) {
             tree->insert(rects[i].data, rects[i].rect);
         }
         run_queries(reporter, rand, rects, *tree);
         REPORTER_ASSERT(reporter, NUM_RECTS == tree->getCount());
         REPORTER_ASSERT(reporter,
             ((expectedDepthMin < 0) || (expectedDepthMin <= tree->getDepth())) &&
             ((expectedDepthMax < 0) || (expectedDepthMax >= tree->getDepth())));
         tree->clear();
         REPORTER_ASSERT(reporter, 0 == tree->getCount());
     }
 }
 
 DEF_TEST(BBoxHierarchy, reporter) {
     // RTree
     {
         SkRTree* rtree = SkRTree::Create(RTREE_MIN_CHILDREN, RTREE_MAX_CHILDREN);
         SkAutoUnref au(rtree);
         tree_test_main(rtree, RTREE_MIN_CHILDREN, RTREE_MAX_CHILDREN, reporter);
 
         // Rtree that orders input rectangles on deferred insert.
         SkRTree* unsortedRtree = SkRTree::Create(RTREE_MIN_CHILDREN, RTREE_MAX_CHILDREN, 1, false);
         SkAutoUnref auo(unsortedRtree);
         tree_test_main(unsortedRtree, RTREE_MIN_CHILDREN, RTREE_MAX_CHILDREN, reporter);
     }
 
     // QuadTree
     {
-        SkQuadTree* quadtree = SkQuadTree::Create(
-            SkIRect::MakeLTRB(-MAX_SIZE, -MAX_SIZE, MAX_SIZE, MAX_SIZE));
+        SkQuadTree* quadtree = SkNEW_ARGS(SkQuadTree, (
+            SkIRect::MakeLTRB(-MAX_SIZE, -MAX_SIZE, MAX_SIZE, MAX_SIZE)));
         SkAutoUnref au(quadtree);
         tree_test_main(quadtree, QUADTREE_MIN_CHILDREN, QUADTREE_MAX_CHILDREN, reporter);
 
         // QuadTree that orders input rectangles on deferred insert.
-        SkQuadTree* unsortedQuadTree = SkQuadTree::Create(
-            SkIRect::MakeLTRB(-MAX_SIZE, -MAX_SIZE, MAX_SIZE, MAX_SIZE));
+        SkQuadTree* unsortedQuadTree = SkNEW_ARGS(SkQuadTree, (
+            SkIRect::MakeLTRB(-MAX_SIZE, -MAX_SIZE, MAX_SIZE, MAX_SIZE)));
         SkAutoUnref auo(unsortedQuadTree);
         tree_test_main(unsortedQuadTree, QUADTREE_MIN_CHILDREN, QUADTREE_MAX_CHILDREN, reporter);
     }
 }