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 { | 20 struct DataRect { |
21 SkIRect rect; | 21 SkRect rect; |
22 void* data; | 22 void* data; |
23 }; | 23 }; |
24 | 24 |
25 static SkIRect random_rect(SkRandom& rand) { | 25 static SkRect random_rect(SkRandom& rand) { |
26 SkIRect rect = {0,0,0,0}; | 26 SkRect rect = {0,0,0,0}; |
27 while (rect.isEmpty()) { | 27 while (rect.isEmpty()) { |
28 rect.fLeft = rand.nextS() % 1000; | 28 rect.fLeft = rand.nextRangeF(0, 1000); |
29 rect.fRight = rand.nextS() % 1000; | 29 rect.fRight = rand.nextRangeF(0, 1000); |
30 rect.fTop = rand.nextS() % 1000; | 30 rect.fTop = rand.nextRangeF(0, 1000); |
31 rect.fBottom = rand.nextS() % 1000; | 31 rect.fBottom = rand.nextRangeF(0, 1000); |
32 rect.sort(); | 32 rect.sort(); |
33 } | 33 } |
34 return rect; | 34 return rect; |
35 } | 35 } |
36 | 36 |
37 static void random_data_rects(SkRandom& rand, DataRect out[], int n) { | 37 static void random_data_rects(SkRandom& rand, DataRect out[], int n) { |
38 for (int i = 0; i < n; ++i) { | 38 for (int i = 0; i < n; ++i) { |
39 out[i].rect = random_rect(rand); | 39 out[i].rect = random_rect(rand); |
40 out[i].data = reinterpret_cast<void*>(i); | 40 out[i].data = reinterpret_cast<void*>(i); |
41 } | 41 } |
42 } | 42 } |
43 | 43 |
44 static bool verify_query(SkIRect query, DataRect rects[], | 44 static bool verify_query(SkRect query, DataRect rects[], |
45 SkTDArray<void*>& found) { | 45 SkTDArray<void*>& found) { |
| 46 // TODO(mtklein): no need to do this after everything's SkRects |
| 47 query.roundOut(); |
| 48 |
46 SkTDArray<void*> expected; | 49 SkTDArray<void*> expected; |
| 50 |
47 // manually intersect with every rectangle | 51 // manually intersect with every rectangle |
48 for (int i = 0; i < NUM_RECTS; ++i) { | 52 for (int i = 0; i < NUM_RECTS; ++i) { |
49 if (SkIRect::IntersectsNoEmptyCheck(query, rects[i].rect)) { | 53 if (SkRect::Intersects(query, rects[i].rect)) { |
50 expected.push(rects[i].data); | 54 expected.push(rects[i].data); |
51 } | 55 } |
52 } | 56 } |
53 | 57 |
54 if (expected.count() != found.count()) { | 58 if (expected.count() != found.count()) { |
55 return false; | 59 return false; |
56 } | 60 } |
57 | 61 |
58 if (0 == expected.count()) { | 62 if (0 == expected.count()) { |
59 return true; | 63 return true; |
60 } | 64 } |
61 | 65 |
62 // Just cast to long since sorting by the value of the void*'s was being pro
blematic... | 66 // Just cast to long since sorting by the value of the void*'s was being pro
blematic... |
63 SkTQSort(reinterpret_cast<long*>(expected.begin()), | 67 SkTQSort(reinterpret_cast<long*>(expected.begin()), |
64 reinterpret_cast<long*>(expected.end() - 1)); | 68 reinterpret_cast<long*>(expected.end() - 1)); |
65 SkTQSort(reinterpret_cast<long*>(found.begin()), | 69 SkTQSort(reinterpret_cast<long*>(found.begin()), |
66 reinterpret_cast<long*>(found.end() - 1)); | 70 reinterpret_cast<long*>(found.end() - 1)); |
67 return found == expected; | 71 return found == expected; |
68 } | 72 } |
69 | 73 |
70 static void run_queries(skiatest::Reporter* reporter, SkRandom& rand, DataRect r
ects[], | 74 static void run_queries(skiatest::Reporter* reporter, SkRandom& rand, DataRect r
ects[], |
71 SkRTree& tree) { | 75 SkRTree& tree) { |
72 for (size_t i = 0; i < NUM_QUERIES; ++i) { | 76 for (size_t i = 0; i < NUM_QUERIES; ++i) { |
73 SkTDArray<void*> hits; | 77 SkTDArray<void*> hits; |
74 SkIRect query = random_rect(rand); | 78 SkRect query = random_rect(rand); |
75 tree.search(query, &hits); | 79 tree.search(query, &hits); |
76 REPORTER_ASSERT(reporter, verify_query(query, rects, hits)); | 80 REPORTER_ASSERT(reporter, verify_query(query, rects, hits)); |
77 } | 81 } |
78 } | 82 } |
79 | 83 |
80 static void rtree_test_main(SkRTree* rtree, skiatest::Reporter* reporter) { | 84 static void rtree_test_main(SkRTree* rtree, skiatest::Reporter* reporter) { |
81 DataRect rects[NUM_RECTS]; | 85 DataRect rects[NUM_RECTS]; |
82 SkRandom rand; | 86 SkRandom rand; |
83 REPORTER_ASSERT(reporter, NULL != rtree); | 87 REPORTER_ASSERT(reporter, NULL != rtree); |
84 | 88 |
(...skipping 56 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
141 DEF_TEST(RTree, reporter) { | 145 DEF_TEST(RTree, reporter) { |
142 SkRTree* rtree = SkRTree::Create(MIN_CHILDREN, MAX_CHILDREN); | 146 SkRTree* rtree = SkRTree::Create(MIN_CHILDREN, MAX_CHILDREN); |
143 SkAutoUnref au(rtree); | 147 SkAutoUnref au(rtree); |
144 rtree_test_main(rtree, reporter); | 148 rtree_test_main(rtree, reporter); |
145 | 149 |
146 // Rtree that orders input rectangles on deferred insert. | 150 // Rtree that orders input rectangles on deferred insert. |
147 SkRTree* unsortedRtree = SkRTree::Create(MIN_CHILDREN, MAX_CHILDREN, 1, fals
e); | 151 SkRTree* unsortedRtree = SkRTree::Create(MIN_CHILDREN, MAX_CHILDREN, 1, fals
e); |
148 SkAutoUnref auo(unsortedRtree); | 152 SkAutoUnref auo(unsortedRtree); |
149 rtree_test_main(unsortedRtree, reporter); | 153 rtree_test_main(unsortedRtree, reporter); |
150 } | 154 } |
OLD | NEW |