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 "Test.h" 11 12 static const int NUM_RECTS = 200; 13 static const size_t NUM_ITERATIONS = 100; 14 static const size_t NUM_QUERIES = 50; 15 16 static SkRect random_rect(SkRandom& rand) { 17 SkRect rect = {0,0,0,0}; 18 while (rect.isEmpty()) { 19 rect.fLeft = rand.nextRangeF(0, 1000); 20 rect.fRight = rand.nextRangeF(0, 1000); 21 rect.fTop = rand.nextRangeF(0, 1000); 22 rect.fBottom = rand.nextRangeF(0, 1000); 23 rect.sort(); 24 } 25 return rect; 26 } 27 28 static bool verify_query(SkRect query, SkRect rects[], SkTDArray<int>& found) { 29 SkTDArray<int> expected; 30 // manually intersect with every rectangle 31 for (int i = 0; i < NUM_RECTS; ++i) { 32 if (SkRect::Intersects(query, rects[i])) { 33 expected.push(i); 34 } 35 } 36 37 if (expected.count() != found.count()) { 38 return false; 39 } 40 if (0 == expected.count()) { 41 return true; 42 } 43 return found == expected; 44 } 45 46 static void run_queries(skiatest::Reporter* reporter, SkRandom& rand, SkRect rects[], 47 const SkRTree& tree) { 48 for (size_t i = 0; i < NUM_QUERIES; ++i) { 49 SkTDArray<int> hits; 50 SkRect query = random_rect(rand); 51 tree.search(query, &hits); 52 REPORTER_ASSERT(reporter, verify_query(query, rects, hits)); 53 } 54 } 55 56 DEF_TEST(RTree, reporter) { 57 int expectedDepthMin = -1; 58 int tmp = NUM_RECTS; 59 while (tmp > 0) { 60 tmp -= static_cast<int>(pow(static_cast<double>(SkRTree::kMaxChildren), 61 static_cast<double>(expectedDepthMin + 1))); 62 ++expectedDepthMin; 63 } 64 65 int expectedDepthMax = -1; 66 tmp = NUM_RECTS; 67 while (tmp > 0) { 68 tmp -= static_cast<int>(pow(static_cast<double>(SkRTree::kMinChildren), 69 static_cast<double>(expectedDepthMax + 1))); 70 ++expectedDepthMax; 71 } 72 73 SkRandom rand; 74 SkAutoTMalloc<SkRect> rects(NUM_RECTS); 75 for (size_t i = 0; i < NUM_ITERATIONS; ++i) { 76 SkRTree rtree; 77 REPORTER_ASSERT(reporter, 0 == rtree.getCount()); 78 79 for (int j = 0; j < NUM_RECTS; j++) { 80 rects[j] = random_rect(rand); 81 } 82 83 rtree.insert(rects.get(), NUM_RECTS); 84 SkASSERT(rects); // SkRTree doesn't take ownership of rects. 85 86 run_queries(reporter, rand, rects, rtree); 87 REPORTER_ASSERT(reporter, NUM_RECTS == rtree.getCount()); 88 REPORTER_ASSERT(reporter, expectedDepthMin <= rtree.getDepth() && 89 expectedDepthMax >= rtree.getDepth()); 90 } 91 } 92
