text: /*
   * Copyright 2012 Google Inc.
   *
   * Use of this source code is governed by a BSD-style license that can be
   * found in the LICENSE file.
   */
  
  #include "Benchmark.h"
  #include "SkCanvas.h"
  #include "SkRTree.h"
  #include "SkRandom.h"
  #include "SkString.h"
  
  // confine rectangles to a smallish area, so queries generally hit something, and overlap occurs:
  static const SkScalar GENERATE_EXTENTS = 1000.0f;
  static const int NUM_BUILD_RECTS = 500;
  static const int NUM_QUERY_RECTS = 5000;
  static const int GRID_WIDTH = 100;
  
  typedef SkRect (*MakeRectProc)(SkRandom&, int, int);
  
  // Time how long it takes to build an R-Tree.
  class RTreeBuildBench : public Benchmark {
  public:
      RTreeBuildBench(const char* name, MakeRectProc proc) : fProc(proc) {
          fName.printf("rtree_%s_build", name);
      }
  
      virtual bool isSuitableFor(Backend backend) SK_OVERRIDE {
          return backend == kNonRendering_Backend;
      }
  
  protected:
      virtual const char* onGetName() SK_OVERRIDE {
          return fName.c_str();
      }
      virtual void onDraw(const int loops, SkCanvas* canvas) SK_OVERRIDE {
          SkRandom rand;
          SkAutoTMalloc<SkRect> rects(NUM_BUILD_RECTS);
          for (int i = 0; i < NUM_BUILD_RECTS; ++i) {
              rects[i] = fProc(rand, i, NUM_BUILD_RECTS);
          }
  
          for (int i = 0; i < loops; ++i) {
              SkRTree tree;
              tree.insert(&rects, NUM_BUILD_RECTS);
              SkASSERT(rects != NULL);  // It'd break this bench if the tree took ownership of rects.
          }
      }
  private:
      MakeRectProc fProc;
      SkString fName;
      typedef Benchmark INHERITED;
  };
  
  // Time how long it takes to perform queries on an R-Tree.
  class RTreeQueryBench : public Benchmark {
  public:
      RTreeQueryBench(const char* name, MakeRectProc proc) : fProc(proc) {
          fName.printf("rtree_%s_query", name);
      }
  
      virtual bool isSuitableFor(Backend backend) SK_OVERRIDE {
          return backend == kNonRendering_Backend;
      }
  protected:
      virtual const char* onGetName() SK_OVERRIDE {
          return fName.c_str();
      }
      virtual void onPreDraw() SK_OVERRIDE {
          SkRandom rand;
          SkAutoTMalloc<SkRect> rects(NUM_QUERY_RECTS);
          for (int i = 0; i < NUM_QUERY_RECTS; ++i) {
              rects[i] = fProc(rand, i, NUM_QUERY_RECTS);
          }
          fTree.insert(&rects, NUM_QUERY_RECTS);
      }
  
      virtual void onDraw(const int loops, SkCanvas* canvas) SK_OVERRIDE {
          SkRandom rand;
          for (int i = 0; i < loops; ++i) {
              SkTDArray<unsigned> hits;
              SkRect query;
              query.fLeft   = rand.nextRangeF(0, GENERATE_EXTENTS);
              query.fTop    = rand.nextRangeF(0, GENERATE_EXTENTS);
              query.fRight  = query.fLeft + 1 + rand.nextRangeF(0, GENERATE_EXTENTS/2);
              query.fBottom = query.fTop  + 1 + rand.nextRangeF(0, GENERATE_EXTENTS/2);
              fTree.search(query, &hits);
          }
      }
  private:
      SkRTree fTree;
      MakeRectProc fProc;
      SkString fName;
      typedef Benchmark INHERITED;
  };
  
  static inline SkRect make_XYordered_rects(SkRandom& rand, int index, int numRects) {
      SkRect out;
      out.fLeft   = SkIntToScalar(index % GRID_WIDTH);
      out.fTop    = SkIntToScalar(index / GRID_WIDTH);
      out.fRight  = out.fLeft + 1 + rand.nextRangeF(0, GENERATE_EXTENTS/3);
      out.fBottom = out.fTop  + 1 + rand.nextRangeF(0, GENERATE_EXTENTS/3);
      return out;
  }
  static inline SkRect make_YXordered_rects(SkRandom& rand, int index, int numRects) {
      SkRect out;
      out.fLeft   = SkIntToScalar(index / GRID_WIDTH);
      out.fTop    = SkIntToScalar(index % GRID_WIDTH);
      out.fRight  = out.fLeft + 1 + rand.nextRangeF(0, GENERATE_EXTENTS/3);
      out.fBottom = out.fTop  + 1 + rand.nextRangeF(0, GENERATE_EXTENTS/3);
      return out;
  }
  
  static inline SkRect make_random_rects(SkRandom& rand, int index, int numRects) {
      SkRect out;
      out.fLeft   = rand.nextRangeF(0, GENERATE_EXTENTS);
      out.fTop    = rand.nextRangeF(0, GENERATE_EXTENTS);
      out.fRight  = out.fLeft + 1 + rand.nextRangeF(0, GENERATE_EXTENTS/5);
      out.fBottom = out.fTop  + 1 + rand.nextRangeF(0, GENERATE_EXTENTS/5);
      return out;
  }
  
  static inline SkRect make_concentric_rects(SkRandom&, int index, int numRects) {
      return SkRect::MakeWH(SkIntToScalar(index+1), SkIntToScalar(index+1));
  }
  
  ///////////////////////////////////////////////////////////////////////////////
  
  DEF_BENCH(return SkNEW_ARGS(RTreeBuildBench, ("XY",         &make_XYordered_rects)));
  DEF_BENCH(return SkNEW_ARGS(RTreeBuildBench, ("YX",         &make_YXordered_rects)));
  DEF_BENCH(return SkNEW_ARGS(RTreeBuildBench, ("random",     &make_random_rects)));
  DEF_BENCH(return SkNEW_ARGS(RTreeBuildBench, ("concentric", &make_concentric_rects)));
  
  DEF_BENCH(return SkNEW_ARGS(RTreeQueryBench, ("XY",         &make_XYordered_rects)));
  DEF_BENCH(return SkNEW_ARGS(RTreeQueryBench, ("YX",         &make_YXordered_rects)));
  DEF_BENCH(return SkNEW_ARGS(RTreeQueryBench, ("random",     &make_random_rects)));
  DEF_BENCH(return SkNEW_ARGS(RTreeQueryBench, ("concentric", &make_concentric_rects)));
  