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