| 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 "Test.h" | 10 #include "Test.h" |
| 11 | 11 |
| 12 static const int NUM_RECTS = 200; | 12 static const int NUM_RECTS = 200; |
| 13 static const size_t NUM_ITERATIONS = 100; | 13 static const size_t NUM_ITERATIONS = 100; |
| 14 static const size_t NUM_QUERIES = 50; | 14 static const size_t NUM_QUERIES = 50; |
| 15 | 15 |
| 16 static SkRect random_rect(SkRandom& rand) { | 16 static SkRect random_rect(SkRandom& rand) { |
| 17 SkRect rect = {0,0,0,0}; | 17 SkRect rect = {0,0,0,0}; |
| 18 while (rect.isEmpty()) { | 18 while (rect.isEmpty()) { |
| 19 rect.fLeft = rand.nextRangeF(0, 1000); | 19 rect.fLeft = rand.nextRangeF(0, 1000); |
| 20 rect.fRight = rand.nextRangeF(0, 1000); | 20 rect.fRight = rand.nextRangeF(0, 1000); |
| 21 rect.fTop = rand.nextRangeF(0, 1000); | 21 rect.fTop = rand.nextRangeF(0, 1000); |
| 22 rect.fBottom = rand.nextRangeF(0, 1000); | 22 rect.fBottom = rand.nextRangeF(0, 1000); |
| 23 rect.sort(); | 23 rect.sort(); |
| 24 } | 24 } |
| 25 return rect; | 25 return rect; |
| 26 } | 26 } |
| 27 | 27 |
| 28 static bool verify_query(SkRect query, SkRect rects[], SkTDArray<unsigned>& foun
d) { | 28 static bool verify_query(SkRect query, SkRect rects[], SkTDArray<int>& found) { |
| 29 SkTDArray<unsigned> expected; | 29 SkTDArray<int> expected; |
| 30 // manually intersect with every rectangle | 30 // manually intersect with every rectangle |
| 31 for (int i = 0; i < NUM_RECTS; ++i) { | 31 for (int i = 0; i < NUM_RECTS; ++i) { |
| 32 if (SkRect::Intersects(query, rects[i])) { | 32 if (SkRect::Intersects(query, rects[i])) { |
| 33 expected.push(i); | 33 expected.push(i); |
| 34 } | 34 } |
| 35 } | 35 } |
| 36 | 36 |
| 37 if (expected.count() != found.count()) { | 37 if (expected.count() != found.count()) { |
| 38 return false; | 38 return false; |
| 39 } | 39 } |
| 40 if (0 == expected.count()) { | 40 if (0 == expected.count()) { |
| 41 return true; | 41 return true; |
| 42 } | 42 } |
| 43 return found == expected; | 43 return found == expected; |
| 44 } | 44 } |
| 45 | 45 |
| 46 static void run_queries(skiatest::Reporter* reporter, SkRandom& rand, SkRect rec
ts[], | 46 static void run_queries(skiatest::Reporter* reporter, SkRandom& rand, SkRect rec
ts[], |
| 47 const SkRTree& tree) { | 47 const SkRTree& tree) { |
| 48 for (size_t i = 0; i < NUM_QUERIES; ++i) { | 48 for (size_t i = 0; i < NUM_QUERIES; ++i) { |
| 49 SkTDArray<unsigned> hits; | 49 SkTDArray<int> hits; |
| 50 SkRect query = random_rect(rand); | 50 SkRect query = random_rect(rand); |
| 51 tree.search(query, &hits); | 51 tree.search(query, &hits); |
| 52 REPORTER_ASSERT(reporter, verify_query(query, rects, hits)); | 52 REPORTER_ASSERT(reporter, verify_query(query, rects, hits)); |
| 53 } | 53 } |
| 54 } | 54 } |
| 55 | 55 |
| 56 DEF_TEST(RTree, reporter) { | 56 DEF_TEST(RTree, reporter) { |
| 57 int expectedDepthMin = -1; | 57 int expectedDepthMin = -1; |
| 58 int tmp = NUM_RECTS; | 58 int tmp = NUM_RECTS; |
| 59 while (tmp > 0) { | 59 while (tmp > 0) { |
| (...skipping 22 matching lines...) Expand all Loading... |
| 82 | 82 |
| 83 rtree.insert(rects.get(), NUM_RECTS); | 83 rtree.insert(rects.get(), NUM_RECTS); |
| 84 SkASSERT(rects); // SkRTree doesn't take ownership of rects. | 84 SkASSERT(rects); // SkRTree doesn't take ownership of rects. |
| 85 | 85 |
| 86 run_queries(reporter, rand, rects, rtree); | 86 run_queries(reporter, rand, rects, rtree); |
| 87 REPORTER_ASSERT(reporter, NUM_RECTS == rtree.getCount()); | 87 REPORTER_ASSERT(reporter, NUM_RECTS == rtree.getCount()); |
| 88 REPORTER_ASSERT(reporter, expectedDepthMin <= rtree.getDepth() && | 88 REPORTER_ASSERT(reporter, expectedDepthMin <= rtree.getDepth() && |
| 89 expectedDepthMax >= rtree.getDepth()); | 89 expectedDepthMax >= rtree.getDepth()); |
| 90 } | 90 } |
| 91 } | 91 } |
| OLD | NEW |