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