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 |