| 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(SkRandom& rand) { | 26 static SkIRect random_rect(SkMWCRandom& 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(SkRandom& rand, DataRect out[], int n) { | 38 static void random_data_rects(SkMWCRandom& 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 runQueries(skiatest::Reporter* reporter, SkRandom& rand, DataRect re
cts[], | 71 static void runQueries(skiatest::Reporter* reporter, SkMWCRandom& rand, DataRect
rects[], |
| 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 TestRTree(skiatest::Reporter* reporter) { | 81 static void TestRTree(skiatest::Reporter* reporter) { |
| 82 DataRect rects[NUM_RECTS]; | 82 DataRect rects[NUM_RECTS]; |
| 83 SkRandom rand; | 83 SkMWCRandom rand; |
| 84 SkRTree* rtree = SkRTree::Create(MIN_CHILDREN, MAX_CHILDREN); | 84 SkRTree* rtree = SkRTree::Create(MIN_CHILDREN, MAX_CHILDREN); |
| 85 SkAutoUnref au(rtree); | 85 SkAutoUnref au(rtree); |
| 86 REPORTER_ASSERT(reporter, NULL != rtree); | 86 REPORTER_ASSERT(reporter, NULL != rtree); |
| 87 | 87 |
| 88 int expectedDepthMin = -1; | 88 int expectedDepthMin = -1; |
| 89 int expectedDepthMax = -1; | 89 int expectedDepthMax = -1; |
| 90 | 90 |
| 91 int tmp = NUM_RECTS; | 91 int tmp = NUM_RECTS; |
| 92 while (tmp > 0) { | 92 while (tmp > 0) { |
| 93 tmp -= static_cast<int>(pow(static_cast<double>(MAX_CHILDREN), | 93 tmp -= static_cast<int>(pow(static_cast<double>(MAX_CHILDREN), |
| (...skipping 42 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 136 REPORTER_ASSERT(reporter, NUM_RECTS == rtree->getCount()); | 136 REPORTER_ASSERT(reporter, NUM_RECTS == rtree->getCount()); |
| 137 REPORTER_ASSERT(reporter, expectedDepthMin <= rtree->getDepth() && | 137 REPORTER_ASSERT(reporter, expectedDepthMin <= rtree->getDepth() && |
| 138 expectedDepthMax >= rtree->getDepth()); | 138 expectedDepthMax >= rtree->getDepth()); |
| 139 rtree->clear(); | 139 rtree->clear(); |
| 140 REPORTER_ASSERT(reporter, 0 == rtree->getCount()); | 140 REPORTER_ASSERT(reporter, 0 == rtree->getCount()); |
| 141 } | 141 } |
| 142 } | 142 } |
| 143 | 143 |
| 144 #include "TestClassDef.h" | 144 #include "TestClassDef.h" |
| 145 DEFINE_TESTCLASS("RTree", RTreeTestClass, TestRTree) | 145 DEFINE_TESTCLASS("RTree", RTreeTestClass, TestRTree) |
| OLD | NEW |