1 /* 2 * Copyright 2012 Google Inc. 3 * 4 * Use of this source code is governed by a BSD-style license that can be 5 * found in the LICENSE file. 6 */ 7 8 #include "SkRTree.h" 9 #include "SkRandom.h" 10 #include "SkTSort.h" 11 #include "Test.h" 12 13 static const size_t MIN_CHILDREN = 6; 14 static const size_t MAX_CHILDREN = 11; 15 16 static const int NUM_RECTS = 200; 17 static const size_t NUM_ITERATIONS = 100; 18 static const size_t NUM_QUERIES = 50; 19 20 struct DataRect { 21 SkRect rect; 22 void* data; 23 }; 24 25 static SkRect random_rect(SkRandom& rand) { 26 SkRect rect = {0,0,0,0}; 27 while (rect.isEmpty()) { 28 rect.fLeft = rand.nextRangeF(0, 1000); 29 rect.fRight = rand.nextRangeF(0, 1000); 30 rect.fTop = rand.nextRangeF(0, 1000); 31 rect.fBottom = rand.nextRangeF(0, 1000); 32 rect.sort(); 33 } 34 return rect; 35 } 36 37 static void random_data_rects(SkRandom& rand, DataRect out[], int n) { 38 for (int i = 0; i < n; ++i) { 39 out[i].rect = random_rect(rand); 40 out[i].data = reinterpret_cast<void*>(i); 41 } 42 } 43 44 static bool verify_query(SkRect query, DataRect rects[], 45 SkTDArray<void*>& found) { 46 // TODO(mtklein): no need to do this after everything's SkRects 47 query.roundOut(); 48 49 SkTDArray<void*> expected; 50 51 // manually intersect with every rectangle 52 for (int i = 0; i < NUM_RECTS; ++i) { 53 if (SkRect::Intersects(query, rects[i].rect)) { 54 expected.push(rects[i].data); 55 } 56 } 57 58 if (expected.count() != found.count()) { 59 return false; 60 } 61 62 if (0 == expected.count()) { 63 return true; 64 } 65 66 // Just cast to long since sorting by the value of the void*'s was being problematic... 67 SkTQSort(reinterpret_cast<long*>(expected.begin()), 68 reinterpret_cast<long*>(expected.end() - 1)); 69 SkTQSort(reinterpret_cast<long*>(found.begin()), 70 reinterpret_cast<long*>(found.end() - 1)); 71 return found == expected; 72 } 73 74 static void run_queries(skiatest::Reporter* reporter, SkRandom& rand, DataRect rects[], 75 SkRTree& tree) { 76 for (size_t i = 0; i < NUM_QUERIES; ++i) { 77 SkTDArray<void*> hits; 78 SkRect query = random_rect(rand); 79 tree.search(query, &hits); 80 REPORTER_ASSERT(reporter, verify_query(query, rects, hits)); 81 } 82 } 83 84 static void rtree_test_main(SkRTree* rtree, skiatest::Reporter* reporter) { 85 DataRect rects[NUM_RECTS]; 86 SkRandom rand; 87 REPORTER_ASSERT(reporter, rtree); 88 89 int expectedDepthMin = -1; 90 int expectedDepthMax = -1; 91 92 int tmp = NUM_RECTS; 93 while (tmp > 0) { 94 tmp -= static_cast<int>(pow(static_cast<double>(MAX_CHILDREN), 95 static_cast<double>(expectedDepthMin + 1))); 96 ++expectedDepthMin; 97 } 98 99 tmp = NUM_RECTS; 100 while (tmp > 0) { 101 tmp -= static_cast<int>(pow(static_cast<double>(MIN_CHILDREN), 102 static_cast<double>(expectedDepthMax + 1))); 103 ++expectedDepthMax; 104 } 105 106 for (size_t i = 0; i < NUM_ITERATIONS; ++i) { 107 random_data_rects(rand, rects, NUM_RECTS); 108 109 // First try bulk-loaded inserts 110 for (int i = 0; i < NUM_RECTS; ++i) { 111 rtree->insert(rects[i].data, rects[i].rect, true); 112 } 113 rtree->flushDeferredInserts(); 114 run_queries(reporter, rand, rects, *rtree); 115 REPORTER_ASSERT(reporter, NUM_RECTS == rtree->getCount()); 116 REPORTER_ASSERT(reporter, expectedDepthMin <= rtree->getDepth() && 117 expectedDepthMax >= rtree->getDepth()); 118 rtree->clear(); 119 REPORTER_ASSERT(reporter, 0 == rtree->getCount()); 120 121 // Then try immediate inserts 122 for (int i = 0; i < NUM_RECTS; ++i) { 123 rtree->insert(rects[i].data, rects[i].rect); 124 } 125 run_queries(reporter, rand, rects, *rtree); 126 REPORTER_ASSERT(reporter, NUM_RECTS == rtree->getCount()); 127 REPORTER_ASSERT(reporter, expectedDepthMin <= rtree->getDepth() && 128 expectedDepthMax >= rtree->getDepth()); 129 rtree->clear(); 130 REPORTER_ASSERT(reporter, 0 == rtree->getCount()); 131 132 // And for good measure try immediate inserts, but in reversed order 133 for (int i = NUM_RECTS - 1; i >= 0; --i) { 134 rtree->insert(rects[i].data, rects[i].rect); 135 } 136 run_queries(reporter, rand, rects, *rtree); 137 REPORTER_ASSERT(reporter, NUM_RECTS == rtree->getCount()); 138 REPORTER_ASSERT(reporter, expectedDepthMin <= rtree->getDepth() && 139 expectedDepthMax >= rtree->getDepth()); 140 rtree->clear(); 141 REPORTER_ASSERT(reporter, 0 == rtree->getCount()); 142 } 143 } 144 145 DEF_TEST(RTree, reporter) { 146 SkRTree* rtree = SkRTree::Create(MIN_CHILDREN, MAX_CHILDREN); 147 SkAutoUnref au(rtree); 148 rtree_test_main(rtree, reporter); 149 150 // Rtree that orders input rectangles on deferred insert. 151 SkRTree* unsortedRtree = SkRTree::Create(MIN_CHILDREN, MAX_CHILDREN, 1, false); 152 SkAutoUnref auo(unsortedRtree); 153 rtree_test_main(unsortedRtree, reporter); 154 } 155
