| 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 |