1/*
2 * Copyright 2012 Google Inc.
3 *
4 * Use of this source code is governed by a BSD-style license that can be
5 * found in the LICENSE file.
6 */
7
8#include "SkRTree.h"
9#include "SkRandom.h"
10#include "SkTSort.h"
11#include "Test.h"
12
13static const size_t MIN_CHILDREN = 6;
14static const size_t MAX_CHILDREN = 11;
15
16static const int NUM_RECTS = 200;
17static const size_t NUM_ITERATIONS = 100;
18static const size_t NUM_QUERIES = 50;
19
20struct DataRect {
21    SkRect rect;
22    void* data;
23};
24
25static SkRect random_rect(SkRandom& rand) {
26    SkRect rect = {0,0,0,0};
27    while (rect.isEmpty()) {
28        rect.fLeft   = rand.nextRangeF(0, 1000);
29        rect.fRight  = rand.nextRangeF(0, 1000);
30        rect.fTop    = rand.nextRangeF(0, 1000);
31        rect.fBottom = rand.nextRangeF(0, 1000);
32        rect.sort();
33    }
34    return rect;
35}
36
37static void random_data_rects(SkRandom& rand, DataRect out[], int n) {
38    for (int i = 0; i < n; ++i) {
39        out[i].rect = random_rect(rand);
40        out[i].data = reinterpret_cast<void*>(i);
41    }
42}
43
44static bool verify_query(SkRect query, DataRect rects[],
45                         SkTDArray<void*>& found) {
46    // TODO(mtklein): no need to do this after everything's SkRects
47    query.roundOut();
48
49    SkTDArray<void*> expected;
50
51    // manually intersect with every rectangle
52    for (int i = 0; i < NUM_RECTS; ++i) {
53        if (SkRect::Intersects(query, rects[i].rect)) {
54            expected.push(rects[i].data);
55        }
56    }
57
58    if (expected.count() != found.count()) {
59        return false;
60    }
61
62    if (0 == expected.count()) {
63        return true;
64    }
65
66    // Just cast to long since sorting by the value of the void*'s was being problematic...
67    SkTQSort(reinterpret_cast<long*>(expected.begin()),
68             reinterpret_cast<long*>(expected.end() - 1));
69    SkTQSort(reinterpret_cast<long*>(found.begin()),
70             reinterpret_cast<long*>(found.end() - 1));
71    return found == expected;
72}
73
74static void run_queries(skiatest::Reporter* reporter, SkRandom& rand, DataRect rects[],
75                       SkRTree& tree) {
76    for (size_t i = 0; i < NUM_QUERIES; ++i) {
77        SkTDArray<void*> hits;
78        SkRect query = random_rect(rand);
79        tree.search(query, &hits);
80        REPORTER_ASSERT(reporter, verify_query(query, rects, hits));
81    }
82}
83
84static void rtree_test_main(SkRTree* rtree, skiatest::Reporter* reporter) {
85    DataRect rects[NUM_RECTS];
86    SkRandom rand;
87    REPORTER_ASSERT(reporter, rtree);
88
89    int expectedDepthMin = -1;
90    int expectedDepthMax = -1;
91
92    int tmp = NUM_RECTS;
93    while (tmp > 0) {
94        tmp -= static_cast<int>(pow(static_cast<double>(MAX_CHILDREN),
95                                static_cast<double>(expectedDepthMin + 1)));
96        ++expectedDepthMin;
97    }
98
99    tmp = NUM_RECTS;
100    while (tmp > 0) {
101        tmp -= static_cast<int>(pow(static_cast<double>(MIN_CHILDREN),
102                                static_cast<double>(expectedDepthMax + 1)));
103        ++expectedDepthMax;
104    }
105
106    for (size_t i = 0; i < NUM_ITERATIONS; ++i) {
107        random_data_rects(rand, rects, NUM_RECTS);
108
109        // First try bulk-loaded inserts
110        for (int i = 0; i < NUM_RECTS; ++i) {
111            rtree->insert(rects[i].data, rects[i].rect, true);
112        }
113        rtree->flushDeferredInserts();
114        run_queries(reporter, rand, rects, *rtree);
115        REPORTER_ASSERT(reporter, NUM_RECTS == rtree->getCount());
116        REPORTER_ASSERT(reporter, expectedDepthMin <= rtree->getDepth() &&
117                                  expectedDepthMax >= rtree->getDepth());
118        rtree->clear();
119        REPORTER_ASSERT(reporter, 0 == rtree->getCount());
120
121        // Then try immediate inserts
122        for (int i = 0; i < NUM_RECTS; ++i) {
123            rtree->insert(rects[i].data, rects[i].rect);
124        }
125        run_queries(reporter, rand, rects, *rtree);
126        REPORTER_ASSERT(reporter, NUM_RECTS == rtree->getCount());
127        REPORTER_ASSERT(reporter, expectedDepthMin <= rtree->getDepth() &&
128                                  expectedDepthMax >= rtree->getDepth());
129        rtree->clear();
130        REPORTER_ASSERT(reporter, 0 == rtree->getCount());
131
132        // And for good measure try immediate inserts, but in reversed order
133        for (int i = NUM_RECTS - 1; i >= 0; --i) {
134            rtree->insert(rects[i].data, rects[i].rect);
135        }
136        run_queries(reporter, rand, rects, *rtree);
137        REPORTER_ASSERT(reporter, NUM_RECTS == rtree->getCount());
138        REPORTER_ASSERT(reporter, expectedDepthMin <= rtree->getDepth() &&
139                                  expectedDepthMax >= rtree->getDepth());
140        rtree->clear();
141        REPORTER_ASSERT(reporter, 0 == rtree->getCount());
142    }
143}
144
145DEF_TEST(RTree, reporter) {
146    SkRTree* rtree = SkRTree::Create(MIN_CHILDREN, MAX_CHILDREN);
147    SkAutoUnref au(rtree);
148    rtree_test_main(rtree, reporter);
149
150    // Rtree that orders input rectangles on deferred insert.
151    SkRTree* unsortedRtree = SkRTree::Create(MIN_CHILDREN, MAX_CHILDREN, 1, false);
152    SkAutoUnref auo(unsortedRtree);
153    rtree_test_main(unsortedRtree, reporter);
154}
155