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 "Test.h"
      9 #include "TestClassDef.h"
     10 #include "SkRandom.h"
     11 #include "SkRTree.h"
     12 #include "SkTSort.h"
     13 
     14 static const size_t MIN_CHILDREN = 6;
     15 static const size_t MAX_CHILDREN = 11;
     16 
     17 static const int NUM_RECTS = 200;
     18 static const size_t NUM_ITERATIONS = 100;
     19 static const size_t NUM_QUERIES = 50;
     20 
     21 struct DataRect {
     22     SkIRect rect;
     23     void* data;
     24 };
     25 
     26 static SkIRect random_rect(SkRandom& 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 
     38 static void random_data_rects(SkRandom& 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 
     45 static 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 
     71 static void run_queries(skiatest::Reporter* reporter, SkRandom& 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 
     81 static void rtree_test_main(SkRTree* rtree, skiatest::Reporter* reporter) {
     82     DataRect rects[NUM_RECTS];
     83     SkRandom 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 
    142 DEF_TEST(RTree, 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