blob: 0e063378f5a52361727166452d63099fbaeba6da [file] [log] [blame]
rileya@google.com1f45e932012-09-05 16:10:59 +00001
2/*
3 * Copyright 2012 Google Inc.
4 *
5 * Use of this source code is governed by a BSD-style license that can be
6 * found in the LICENSE file.
7 */
8
9#include "Test.h"
10#include "SkRandom.h"
11#include "SkRTree.h"
12#include "SkTSort.h"
13
14static const size_t MIN_CHILDREN = 6;
15static const size_t MAX_CHILDREN = 11;
16
17static const size_t NUM_RECTS = 200;
18static const size_t NUM_ITERATIONS = 100;
19static const size_t NUM_QUERIES = 50;
20
21struct DataRect {
22 SkIRect rect;
23 void* data;
24};
25
26static SkIRect random_rect(SkRandom& rand) {
27 SkIRect rect = {0,0,0,0};
28 while (rect.isEmpty()) {
29 rect.fLeft = rand.nextS() % 1000;
30 rect.fRight = rand.nextS() % 1000;
31 rect.fTop = rand.nextS() % 1000;
32 rect.fBottom = rand.nextS() % 1000;
33 rect.sort();
34 }
35 return rect;
36}
37
38static void random_data_rects(SkRandom& rand, DataRect out[], int n) {
39 for (int i = 0; i < n; ++i) {
40 out[i].rect = random_rect(rand);
41 out[i].data = reinterpret_cast<void*>(i);
42 }
43}
44
skia.committer@gmail.com6c778162012-09-06 02:01:13 +000045static bool verify_query(SkIRect query, DataRect rects[],
rileya@google.com1f45e932012-09-05 16:10:59 +000046 SkTDArray<void*>& found) {
47 SkTDArray<void*> expected;
48 // manually intersect with every rectangle
robertphillips@google.com178a2672012-09-13 13:25:30 +000049 for (size_t i = 0; i < NUM_RECTS; ++i) {
rileya@google.com1f45e932012-09-05 16:10:59 +000050 if (SkIRect::IntersectsNoEmptyCheck(query, rects[i].rect)) {
51 expected.push(rects[i].data);
52 }
53 }
54
skia.committer@gmail.com6c778162012-09-06 02:01:13 +000055 if (expected.count() != found.count()) {
56 return false;
57 }
58
rileya@google.com1f45e932012-09-05 16:10:59 +000059 if (0 == expected.count()) {
60 return true;
61 }
62
63 // Just cast to long since sorting by the value of the void*'s was being problematic...
skia.committer@gmail.com6c778162012-09-06 02:01:13 +000064 SkTQSort(reinterpret_cast<long*>(expected.begin()),
rileya@google.com1f45e932012-09-05 16:10:59 +000065 reinterpret_cast<long*>(expected.end() - 1));
skia.committer@gmail.com6c778162012-09-06 02:01:13 +000066 SkTQSort(reinterpret_cast<long*>(found.begin()),
rileya@google.com1f45e932012-09-05 16:10:59 +000067 reinterpret_cast<long*>(found.end() - 1));
68 return found == expected;
69}
70
skia.committer@gmail.com6c778162012-09-06 02:01:13 +000071static void runQueries(skiatest::Reporter* reporter, SkRandom& rand, DataRect rects[],
rileya@google.com1f45e932012-09-05 16:10:59 +000072 SkRTree& tree) {
robertphillips@google.com178a2672012-09-13 13:25:30 +000073 for (size_t i = 0; i < NUM_QUERIES; ++i) {
rileya@google.com1f45e932012-09-05 16:10:59 +000074 SkTDArray<void*> hits;
75 SkIRect query = random_rect(rand);
76 tree.search(query, &hits);
77 REPORTER_ASSERT(reporter, verify_query(query, rects, hits));
78 }
79}
80
81static void TestRTree(skiatest::Reporter* reporter) {
82 DataRect rects[NUM_RECTS];
83 SkRandom rand;
84 SkRTree* rtree = SkRTree::Create(MIN_CHILDREN, MAX_CHILDREN);
rileya@google.com48134582012-09-11 15:41:50 +000085 SkAutoUnref au(rtree);
rileya@google.com1f45e932012-09-05 16:10:59 +000086 REPORTER_ASSERT(reporter, NULL != rtree);
87
88 int expectedDepthMin = -1;
89 int expectedDepthMax = -1;
90
91 int tmp = NUM_RECTS;
92 while (tmp > 0) {
skia.committer@gmail.com6c778162012-09-06 02:01:13 +000093 tmp -= static_cast<int>(pow(static_cast<double>(MAX_CHILDREN),
rileya@google.com1f45e932012-09-05 16:10:59 +000094 static_cast<double>(expectedDepthMin + 1)));
95 ++expectedDepthMin;
96 }
97
98 tmp = NUM_RECTS;
99 while (tmp > 0) {
100 tmp -= static_cast<int>(pow(static_cast<double>(MIN_CHILDREN),
101 static_cast<double>(expectedDepthMax + 1)));
102 ++expectedDepthMax;
103 }
104
robertphillips@google.com178a2672012-09-13 13:25:30 +0000105 for (size_t i = 0; i < NUM_ITERATIONS; ++i) {
rileya@google.com1f45e932012-09-05 16:10:59 +0000106 random_data_rects(rand, rects, NUM_RECTS);
107
108 // First try bulk-loaded inserts
robertphillips@google.com178a2672012-09-13 13:25:30 +0000109 for (size_t i = 0; i < NUM_RECTS; ++i) {
rileya@google.com1f45e932012-09-05 16:10:59 +0000110 rtree->insert(rects[i].data, rects[i].rect, true);
111 }
112 rtree->flushDeferredInserts();
113 runQueries(reporter, rand, rects, *rtree);
114 REPORTER_ASSERT(reporter, NUM_RECTS == rtree->getCount());
115 REPORTER_ASSERT(reporter, expectedDepthMin <= rtree->getDepth() &&
116 expectedDepthMax >= rtree->getDepth());
117 rtree->clear();
118 REPORTER_ASSERT(reporter, 0 == rtree->getCount());
119
120 // Then try immediate inserts
robertphillips@google.com178a2672012-09-13 13:25:30 +0000121 for (size_t i = 0; i < NUM_RECTS; ++i) {
rileya@google.com1f45e932012-09-05 16:10:59 +0000122 rtree->insert(rects[i].data, rects[i].rect);
123 }
124 runQueries(reporter, rand, rects, *rtree);
125 REPORTER_ASSERT(reporter, NUM_RECTS == rtree->getCount());
126 REPORTER_ASSERT(reporter, expectedDepthMin <= rtree->getDepth() &&
127 expectedDepthMax >= rtree->getDepth());
128 rtree->clear();
129 REPORTER_ASSERT(reporter, 0 == rtree->getCount());
130
131 // And for good measure try immediate inserts, but in reversed order
132 for (int i = NUM_RECTS - 1; i >= 0; --i) {
133 rtree->insert(rects[i].data, rects[i].rect);
134 }
135 runQueries(reporter, rand, rects, *rtree);
136 REPORTER_ASSERT(reporter, NUM_RECTS == rtree->getCount());
137 REPORTER_ASSERT(reporter, expectedDepthMin <= rtree->getDepth() &&
138 expectedDepthMax >= rtree->getDepth());
139 rtree->clear();
140 REPORTER_ASSERT(reporter, 0 == rtree->getCount());
141 }
142}
143
144#include "TestClassDef.h"
145DEFINE_TESTCLASS("RTree", RTreeTestClass, TestRTree)