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