1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
|
/*
* Copyright 2012 Google Inc.
*
* Use of this source code is governed by a BSD-style license that can be
* found in the LICENSE file.
*/
#include "SkRTree.h"
#include "SkRandom.h"
#include "Test.h"
static const int NUM_RECTS = 200;
static const size_t NUM_ITERATIONS = 100;
static const size_t NUM_QUERIES = 50;
static SkRect random_rect(SkRandom& rand) {
SkRect rect = {0,0,0,0};
while (rect.isEmpty()) {
rect.fLeft = rand.nextRangeF(0, 1000);
rect.fRight = rand.nextRangeF(0, 1000);
rect.fTop = rand.nextRangeF(0, 1000);
rect.fBottom = rand.nextRangeF(0, 1000);
rect.sort();
}
return rect;
}
static bool verify_query(SkRect query, SkRect rects[], SkTDArray<unsigned>& found) {
SkTDArray<unsigned> expected;
// manually intersect with every rectangle
for (int i = 0; i < NUM_RECTS; ++i) {
if (SkRect::Intersects(query, rects[i])) {
expected.push(i);
}
}
if (expected.count() != found.count()) {
return false;
}
if (0 == expected.count()) {
return true;
}
return found == expected;
}
static void run_queries(skiatest::Reporter* reporter, SkRandom& rand, SkRect rects[],
const SkRTree& tree) {
for (size_t i = 0; i < NUM_QUERIES; ++i) {
SkTDArray<unsigned> hits;
SkRect query = random_rect(rand);
tree.search(query, &hits);
REPORTER_ASSERT(reporter, verify_query(query, rects, hits));
}
}
DEF_TEST(RTree, reporter) {
int expectedDepthMin = -1;
int tmp = NUM_RECTS;
while (tmp > 0) {
tmp -= static_cast<int>(pow(static_cast<double>(SkRTree::kMaxChildren),
static_cast<double>(expectedDepthMin + 1)));
++expectedDepthMin;
}
int expectedDepthMax = -1;
tmp = NUM_RECTS;
while (tmp > 0) {
tmp -= static_cast<int>(pow(static_cast<double>(SkRTree::kMinChildren),
static_cast<double>(expectedDepthMax + 1)));
++expectedDepthMax;
}
SkRandom rand;
SkAutoTMalloc<SkRect> rects(NUM_RECTS);
for (size_t i = 0; i < NUM_ITERATIONS; ++i) {
SkRTree rtree;
REPORTER_ASSERT(reporter, 0 == rtree.getCount());
for (int j = 0; j < NUM_RECTS; j++) {
rects[j] = random_rect(rand);
}
rtree.insert(&rects, NUM_RECTS);
SkASSERT(rects); // SkRTree doesn't take ownership of rects.
run_queries(reporter, rand, rects, rtree);
REPORTER_ASSERT(reporter, NUM_RECTS == rtree.getCount());
REPORTER_ASSERT(reporter, expectedDepthMin <= rtree.getDepth() &&
expectedDepthMax >= rtree.getDepth());
}
}
|
