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