RTreeTest.cpp revision ffb71f2dd5f1cdc905c483737bb56080adc56cc9 
1
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 int 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(SkMWCRandom& 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(SkMWCRandom& 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
45static bool verify_query(SkIRect query, DataRect rects[],
46                         SkTDArray<void*>& found) {
47    SkTDArray<void*> expected;
48    // manually intersect with every rectangle
49    for (int i = 0; i < NUM_RECTS; ++i) {
50        if (SkIRect::IntersectsNoEmptyCheck(query, rects[i].rect)) {
51            expected.push(rects[i].data);
52        }
53    }
54
55    if (expected.count() != found.count()) {
56        return false;
57    }
58
59    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...
64    SkTQSort(reinterpret_cast<long*>(expected.begin()),
65             reinterpret_cast<long*>(expected.end() - 1));
66    SkTQSort(reinterpret_cast<long*>(found.begin()),
67             reinterpret_cast<long*>(found.end() - 1));
68    return found == expected;
69}
70
71static void run_queries(skiatest::Reporter* reporter, SkMWCRandom& rand, DataRect rects[],
72                       SkRTree& tree) {
73    for (size_t i = 0; i < NUM_QUERIES; ++i) {
74        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 rtree_test_main(SkRTree* rtree, skiatest::Reporter* reporter) {
82    DataRect rects[NUM_RECTS];
83    SkMWCRandom rand;
84    REPORTER_ASSERT(reporter, NULL != rtree);
85
86    int expectedDepthMin = -1;
87    int expectedDepthMax = -1;
88
89    int tmp = NUM_RECTS;
90    while (tmp > 0) {
91        tmp -= static_cast<int>(pow(static_cast<double>(MAX_CHILDREN),
92                                static_cast<double>(expectedDepthMin + 1)));
93        ++expectedDepthMin;
94    }
95
96    tmp = NUM_RECTS;
97    while (tmp > 0) {
98        tmp -= static_cast<int>(pow(static_cast<double>(MIN_CHILDREN),
99                                static_cast<double>(expectedDepthMax + 1)));
100        ++expectedDepthMax;
101    }
102
103    for (size_t i = 0; i < NUM_ITERATIONS; ++i) {
104        random_data_rects(rand, rects, NUM_RECTS);
105
106        // First try bulk-loaded inserts
107        for (int i = 0; i < NUM_RECTS; ++i) {
108            rtree->insert(rects[i].data, rects[i].rect, true);
109        }
110        rtree->flushDeferredInserts();
111        run_queries(reporter, rand, rects, *rtree);
112        REPORTER_ASSERT(reporter, NUM_RECTS == rtree->getCount());
113        REPORTER_ASSERT(reporter, expectedDepthMin <= rtree->getDepth() &&
114                                  expectedDepthMax >= rtree->getDepth());
115        rtree->clear();
116        REPORTER_ASSERT(reporter, 0 == rtree->getCount());
117
118        // Then try immediate inserts
119        for (int i = 0; i < NUM_RECTS; ++i) {
120            rtree->insert(rects[i].data, rects[i].rect);
121        }
122        run_queries(reporter, rand, rects, *rtree);
123        REPORTER_ASSERT(reporter, NUM_RECTS == rtree->getCount());
124        REPORTER_ASSERT(reporter, expectedDepthMin <= rtree->getDepth() &&
125                                  expectedDepthMax >= rtree->getDepth());
126        rtree->clear();
127        REPORTER_ASSERT(reporter, 0 == rtree->getCount());
128
129        // And for good measure try immediate inserts, but in reversed order
130        for (int i = NUM_RECTS - 1; i >= 0; --i) {
131            rtree->insert(rects[i].data, rects[i].rect);
132        }
133        run_queries(reporter, rand, rects, *rtree);
134        REPORTER_ASSERT(reporter, NUM_RECTS == rtree->getCount());
135        REPORTER_ASSERT(reporter, expectedDepthMin <= rtree->getDepth() &&
136                                  expectedDepthMax >= rtree->getDepth());
137        rtree->clear();
138        REPORTER_ASSERT(reporter, 0 == rtree->getCount());
139    }
140}
141
142static void test_rtree(skiatest::Reporter* reporter) {
143    SkRTree* rtree = SkRTree::Create(MIN_CHILDREN, MAX_CHILDREN);
144    SkAutoUnref au(rtree);
145    rtree_test_main(rtree, reporter);
146
147    // Rtree that orders input rectangles on deferred insert.
148    SkRTree* unsortedRtree = SkRTree::Create(MIN_CHILDREN, MAX_CHILDREN, 1, false);
149    SkAutoUnref auo(unsortedRtree);
150    rtree_test_main(unsortedRtree, reporter);
151}
152
153
154#include "TestClassDef.h"
155DEFINE_TESTCLASS("RTree", RTreeTestClass, test_rtree)
156