OLD | NEW |
1 | 1 |
2 /* | 2 /* |
3 * Copyright 2012 Google Inc. | 3 * Copyright 2012 Google Inc. |
4 * | 4 * |
5 * Use of this source code is governed by a BSD-style license that can be | 5 * Use of this source code is governed by a BSD-style license that can be |
6 * found in the LICENSE file. | 6 * found in the LICENSE file. |
7 */ | 7 */ |
8 | 8 |
9 #include "Test.h" | 9 #include "Test.h" |
10 #include "SkRandom.h" | 10 #include "SkRandom.h" |
11 #include "SkRTree.h" | 11 #include "SkRTree.h" |
12 #include "SkTSort.h" | 12 #include "SkTSort.h" |
13 | 13 |
14 static const size_t MIN_CHILDREN = 6; | 14 static const size_t MIN_CHILDREN = 6; |
15 static const size_t MAX_CHILDREN = 11; | 15 static const size_t MAX_CHILDREN = 11; |
16 | 16 |
17 static const int NUM_RECTS = 200; | 17 static const int NUM_RECTS = 200; |
18 static const size_t NUM_ITERATIONS = 100; | 18 static const size_t NUM_ITERATIONS = 100; |
19 static const size_t NUM_QUERIES = 50; | 19 static const size_t NUM_QUERIES = 50; |
20 | 20 |
21 struct DataRect { | 21 struct DataRect { |
22 SkIRect rect; | 22 SkIRect rect; |
23 void* data; | 23 void* data; |
24 }; | 24 }; |
25 | 25 |
26 static SkIRect random_rect(SkMWCRandom& rand) { | 26 static SkIRect random_rect(SkRandom& rand) { |
27 SkIRect rect = {0,0,0,0}; | 27 SkIRect rect = {0,0,0,0}; |
28 while (rect.isEmpty()) { | 28 while (rect.isEmpty()) { |
29 rect.fLeft = rand.nextS() % 1000; | 29 rect.fLeft = rand.nextS() % 1000; |
30 rect.fRight = rand.nextS() % 1000; | 30 rect.fRight = rand.nextS() % 1000; |
31 rect.fTop = rand.nextS() % 1000; | 31 rect.fTop = rand.nextS() % 1000; |
32 rect.fBottom = rand.nextS() % 1000; | 32 rect.fBottom = rand.nextS() % 1000; |
33 rect.sort(); | 33 rect.sort(); |
34 } | 34 } |
35 return rect; | 35 return rect; |
36 } | 36 } |
37 | 37 |
38 static void random_data_rects(SkMWCRandom& rand, DataRect out[], int n) { | 38 static void random_data_rects(SkRandom& rand, DataRect out[], int n) { |
39 for (int i = 0; i < n; ++i) { | 39 for (int i = 0; i < n; ++i) { |
40 out[i].rect = random_rect(rand); | 40 out[i].rect = random_rect(rand); |
41 out[i].data = reinterpret_cast<void*>(i); | 41 out[i].data = reinterpret_cast<void*>(i); |
42 } | 42 } |
43 } | 43 } |
44 | 44 |
45 static bool verify_query(SkIRect query, DataRect rects[], | 45 static bool verify_query(SkIRect query, DataRect rects[], |
46 SkTDArray<void*>& found) { | 46 SkTDArray<void*>& found) { |
47 SkTDArray<void*> expected; | 47 SkTDArray<void*> expected; |
48 // manually intersect with every rectangle | 48 // manually intersect with every rectangle |
(...skipping 12 matching lines...) Expand all Loading... |
61 } | 61 } |
62 | 62 |
63 // Just cast to long since sorting by the value of the void*'s was being pro
blematic... | 63 // Just cast to long since sorting by the value of the void*'s was being pro
blematic... |
64 SkTQSort(reinterpret_cast<long*>(expected.begin()), | 64 SkTQSort(reinterpret_cast<long*>(expected.begin()), |
65 reinterpret_cast<long*>(expected.end() - 1)); | 65 reinterpret_cast<long*>(expected.end() - 1)); |
66 SkTQSort(reinterpret_cast<long*>(found.begin()), | 66 SkTQSort(reinterpret_cast<long*>(found.begin()), |
67 reinterpret_cast<long*>(found.end() - 1)); | 67 reinterpret_cast<long*>(found.end() - 1)); |
68 return found == expected; | 68 return found == expected; |
69 } | 69 } |
70 | 70 |
71 static void run_queries(skiatest::Reporter* reporter, SkMWCRandom& rand, DataRec
t rects[], | 71 static void run_queries(skiatest::Reporter* reporter, SkRandom& rand, DataRect r
ects[], |
72 SkRTree& tree) { | 72 SkRTree& tree) { |
73 for (size_t i = 0; i < NUM_QUERIES; ++i) { | 73 for (size_t i = 0; i < NUM_QUERIES; ++i) { |
74 SkTDArray<void*> hits; | 74 SkTDArray<void*> hits; |
75 SkIRect query = random_rect(rand); | 75 SkIRect query = random_rect(rand); |
76 tree.search(query, &hits); | 76 tree.search(query, &hits); |
77 REPORTER_ASSERT(reporter, verify_query(query, rects, hits)); | 77 REPORTER_ASSERT(reporter, verify_query(query, rects, hits)); |
78 } | 78 } |
79 } | 79 } |
80 | 80 |
81 static void rtree_test_main(SkRTree* rtree, skiatest::Reporter* reporter) { | 81 static void rtree_test_main(SkRTree* rtree, skiatest::Reporter* reporter) { |
82 DataRect rects[NUM_RECTS]; | 82 DataRect rects[NUM_RECTS]; |
83 SkMWCRandom rand; | 83 SkRandom rand; |
84 REPORTER_ASSERT(reporter, NULL != rtree); | 84 REPORTER_ASSERT(reporter, NULL != rtree); |
85 | 85 |
86 int expectedDepthMin = -1; | 86 int expectedDepthMin = -1; |
87 int expectedDepthMax = -1; | 87 int expectedDepthMax = -1; |
88 | 88 |
89 int tmp = NUM_RECTS; | 89 int tmp = NUM_RECTS; |
90 while (tmp > 0) { | 90 while (tmp > 0) { |
91 tmp -= static_cast<int>(pow(static_cast<double>(MAX_CHILDREN), | 91 tmp -= static_cast<int>(pow(static_cast<double>(MAX_CHILDREN), |
92 static_cast<double>(expectedDepthMin + 1))); | 92 static_cast<double>(expectedDepthMin + 1))); |
93 ++expectedDepthMin; | 93 ++expectedDepthMin; |
(...skipping 52 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
146 | 146 |
147 // Rtree that orders input rectangles on deferred insert. | 147 // Rtree that orders input rectangles on deferred insert. |
148 SkRTree* unsortedRtree = SkRTree::Create(MIN_CHILDREN, MAX_CHILDREN, 1, fals
e); | 148 SkRTree* unsortedRtree = SkRTree::Create(MIN_CHILDREN, MAX_CHILDREN, 1, fals
e); |
149 SkAutoUnref auo(unsortedRtree); | 149 SkAutoUnref auo(unsortedRtree); |
150 rtree_test_main(unsortedRtree, reporter); | 150 rtree_test_main(unsortedRtree, reporter); |
151 } | 151 } |
152 | 152 |
153 | 153 |
154 #include "TestClassDef.h" | 154 #include "TestClassDef.h" |
155 DEFINE_TESTCLASS("RTree", RTreeTestClass, test_rtree) | 155 DEFINE_TESTCLASS("RTree", RTreeTestClass, test_rtree) |
OLD | NEW |