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