Home | History | Annotate | Download | only in tests 
      1 
      2 /*
      3  * Copyright 2012 Google Inc.
      4  *
      5  * Use of this source code is governed by a BSD-style license that can be
      6  * found in the LICENSE file.
      7  */
      8 
      9 #include "Test.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(SkMWCRandom& 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(SkMWCRandom& 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 runQueries(skiatest::Reporter* reporter, SkMWCRandom& 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 TestRTree(skiatest::Reporter* reporter) {
     82     DataRect rects[NUM_RECTS];
     83     SkMWCRandom rand;
     84     SkRTree* rtree = SkRTree::Create(MIN_CHILDREN, MAX_CHILDREN);
     85     SkAutoUnref au(rtree);
     86     REPORTER_ASSERT(reporter, NULL != rtree);
     87 
     88     int expectedDepthMin = -1;
     89     int expectedDepthMax = -1;
     90 
     91     int tmp = NUM_RECTS;
     92     while (tmp > 0) {
     93         tmp -= static_cast<int>(pow(static_cast<double>(MAX_CHILDREN),
     94                                 static_cast<double>(expectedDepthMin + 1)));
     95         ++expectedDepthMin;
     96     }
     97 
     98     tmp = NUM_RECTS;
     99     while (tmp > 0) {
    100         tmp -= static_cast<int>(pow(static_cast<double>(MIN_CHILDREN),
    101                                 static_cast<double>(expectedDepthMax + 1)));
    102         ++expectedDepthMax;
    103     }
    104 
    105     for (size_t i = 0; i < NUM_ITERATIONS; ++i) {
    106         random_data_rects(rand, rects, NUM_RECTS);
    107 
    108         // First try bulk-loaded inserts
    109         for (int i = 0; i < NUM_RECTS; ++i) {
    110             rtree->insert(rects[i].data, rects[i].rect, true);
    111         }
    112         rtree->flushDeferredInserts();
    113         runQueries(reporter, rand, rects, *rtree);
    114         REPORTER_ASSERT(reporter, NUM_RECTS == rtree->getCount());
    115         REPORTER_ASSERT(reporter, expectedDepthMin <= rtree->getDepth() &&
    116                                   expectedDepthMax >= rtree->getDepth());
    117         rtree->clear();
    118         REPORTER_ASSERT(reporter, 0 == rtree->getCount());
    119 
    120         // Then try immediate inserts
    121         for (int i = 0; i < NUM_RECTS; ++i) {
    122             rtree->insert(rects[i].data, rects[i].rect);
    123         }
    124         runQueries(reporter, rand, rects, *rtree);
    125         REPORTER_ASSERT(reporter, NUM_RECTS == rtree->getCount());
    126         REPORTER_ASSERT(reporter, expectedDepthMin <= rtree->getDepth() &&
    127                                   expectedDepthMax >= rtree->getDepth());
    128         rtree->clear();
    129         REPORTER_ASSERT(reporter, 0 == rtree->getCount());
    130 
    131         // And for good measure try immediate inserts, but in reversed order
    132         for (int i = NUM_RECTS - 1; i >= 0; --i) {
    133             rtree->insert(rects[i].data, rects[i].rect);
    134         }
    135         runQueries(reporter, rand, rects, *rtree);
    136         REPORTER_ASSERT(reporter, NUM_RECTS == rtree->getCount());
    137         REPORTER_ASSERT(reporter, expectedDepthMin <= rtree->getDepth() &&
    138                                   expectedDepthMax >= rtree->getDepth());
    139         rtree->clear();
    140         REPORTER_ASSERT(reporter, 0 == rtree->getCount());
    141     }
    142 }
    143 
    144 #include "TestClassDef.h"
    145 DEFINE_TESTCLASS("RTree", RTreeTestClass, TestRTree)
    146