Home | History | Annotate | Download | only in tests 
      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 
     13 static const size_t MIN_CHILDREN = 6;
     14 static const size_t MAX_CHILDREN = 11;
     15 
     16 static const int NUM_RECTS = 200;
     17 static const size_t NUM_ITERATIONS = 100;
     18 static const size_t NUM_QUERIES = 50;
     19 
     20 struct DataRect {
     21     SkIRect rect;
     22     void* data;
     23 };
     24 
     25 static SkIRect random_rect(SkRandom& rand) {
     26     SkIRect rect = {0,0,0,0};
     27     while (rect.isEmpty()) {
     28         rect.fLeft   = rand.nextS() % 1000;
     29         rect.fRight  = rand.nextS() % 1000;
     30         rect.fTop    = rand.nextS() % 1000;
     31         rect.fBottom = rand.nextS() % 1000;
     32         rect.sort();
     33     }
     34     return rect;
     35 }
     36 
     37 static 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 
     44 static bool verify_query(SkIRect query, DataRect rects[],
     45                          SkTDArray<void*>& found) {
     46     SkTDArray<void*> expected;
     47     // manually intersect with every rectangle
     48     for (int i = 0; i < NUM_RECTS; ++i) {
     49         if (SkIRect::IntersectsNoEmptyCheck(query, rects[i].rect)) {
     50             expected.push(rects[i].data);
     51         }
     52     }
     53 
     54     if (expected.count() != found.count()) {
     55         return false;
     56     }
     57 
     58     if (0 == expected.count()) {
     59         return true;
     60     }
     61 
     62     // Just cast to long since sorting by the value of the void*'s was being problematic...
     63     SkTQSort(reinterpret_cast<long*>(expected.begin()),
     64              reinterpret_cast<long*>(expected.end() - 1));
     65     SkTQSort(reinterpret_cast<long*>(found.begin()),
     66              reinterpret_cast<long*>(found.end() - 1));
     67     return found == expected;
     68 }
     69 
     70 static void run_queries(skiatest::Reporter* reporter, SkRandom& rand, DataRect rects[],
     71                        SkRTree& tree) {
     72     for (size_t i = 0; i < NUM_QUERIES; ++i) {
     73         SkTDArray<void*> hits;
     74         SkIRect query = random_rect(rand);
     75         tree.search(query, &hits);
     76         REPORTER_ASSERT(reporter, verify_query(query, rects, hits));
     77     }
     78 }
     79 
     80 static void rtree_test_main(SkRTree* rtree, skiatest::Reporter* reporter) {
     81     DataRect rects[NUM_RECTS];
     82     SkRandom rand;
     83     REPORTER_ASSERT(reporter, NULL != rtree);
     84 
     85     int expectedDepthMin = -1;
     86     int expectedDepthMax = -1;
     87 
     88     int tmp = NUM_RECTS;
     89     while (tmp > 0) {
     90         tmp -= static_cast<int>(pow(static_cast<double>(MAX_CHILDREN),
     91                                 static_cast<double>(expectedDepthMin + 1)));
     92         ++expectedDepthMin;
     93     }
     94 
     95     tmp = NUM_RECTS;
     96     while (tmp > 0) {
     97         tmp -= static_cast<int>(pow(static_cast<double>(MIN_CHILDREN),
     98                                 static_cast<double>(expectedDepthMax + 1)));
     99         ++expectedDepthMax;
    100     }
    101 
    102     for (size_t i = 0; i < NUM_ITERATIONS; ++i) {
    103         random_data_rects(rand, rects, NUM_RECTS);
    104 
    105         // First try bulk-loaded inserts
    106         for (int i = 0; i < NUM_RECTS; ++i) {
    107             rtree->insert(rects[i].data, rects[i].rect, true);
    108         }
    109         rtree->flushDeferredInserts();
    110         run_queries(reporter, rand, rects, *rtree);
    111         REPORTER_ASSERT(reporter, NUM_RECTS == rtree->getCount());
    112         REPORTER_ASSERT(reporter, expectedDepthMin <= rtree->getDepth() &&
    113                                   expectedDepthMax >= rtree->getDepth());
    114         rtree->clear();
    115         REPORTER_ASSERT(reporter, 0 == rtree->getCount());
    116 
    117         // Then try immediate inserts
    118         for (int i = 0; i < NUM_RECTS; ++i) {
    119             rtree->insert(rects[i].data, rects[i].rect);
    120         }
    121         run_queries(reporter, rand, rects, *rtree);
    122         REPORTER_ASSERT(reporter, NUM_RECTS == rtree->getCount());
    123         REPORTER_ASSERT(reporter, expectedDepthMin <= rtree->getDepth() &&
    124                                   expectedDepthMax >= rtree->getDepth());
    125         rtree->clear();
    126         REPORTER_ASSERT(reporter, 0 == rtree->getCount());
    127 
    128         // And for good measure try immediate inserts, but in reversed order
    129         for (int i = NUM_RECTS - 1; i >= 0; --i) {
    130             rtree->insert(rects[i].data, rects[i].rect);
    131         }
    132         run_queries(reporter, rand, rects, *rtree);
    133         REPORTER_ASSERT(reporter, NUM_RECTS == rtree->getCount());
    134         REPORTER_ASSERT(reporter, expectedDepthMin <= rtree->getDepth() &&
    135                                   expectedDepthMax >= rtree->getDepth());
    136         rtree->clear();
    137         REPORTER_ASSERT(reporter, 0 == rtree->getCount());
    138     }
    139 }
    140 
    141 DEF_TEST(RTree, reporter) {
    142     SkRTree* rtree = SkRTree::Create(MIN_CHILDREN, MAX_CHILDREN);
    143     SkAutoUnref au(rtree);
    144     rtree_test_main(rtree, reporter);
    145 
    146     // Rtree that orders input rectangles on deferred insert.
    147     SkRTree* unsortedRtree = SkRTree::Create(MIN_CHILDREN, MAX_CHILDREN, 1, false);
    148     SkAutoUnref auo(unsortedRtree);
    149     rtree_test_main(unsortedRtree, reporter);
    150 }
    151