src/third_party/skia/src/core/SkQuadTree.h

   1 /*
   2  * Copyright 2014 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 #ifndef SkQuadTree_DEFINED
   9 #define SkQuadTree_DEFINED
  10
  11 #include "SkRect.h"
  12 #include "SkTDArray.h"
  13 #include "SkBBoxHierarchy.h"
  14
  15 /**
  16  * An QuadTree implementation. In short, it is a tree containing a hierarchy of bounding rectangles
  17  * in which each internal node has exactly four children.
  18  *
  19  * For more details see:
  20  *
  21  * http://en.wikipedia.org/wiki/Quadtree
  22  */
  23 class SkQuadTree : public SkBBoxHierarchy {
  24 public:
  25     SK_DECLARE_INST_COUNT(SkQuadTree)
  26
  27     /**
  28      * Create a new QuadTree
  29      */
  30     static SkQuadTree* Create(const SkIRect& bounds);
  31     virtual ~SkQuadTree();
  32
  33     /**
  34      * Insert a node, consisting of bounds and a data value into the tree, if we don't immediately
  35      * need to use the tree; we may allow the insert to be deferred (this can allow us to bulk-load
  36      * a large batch of nodes at once, which tends to be faster and produce a better tree).
  37      *  @param data The data value
  38      *  @param bounds The corresponding bounding box
  39      *  @param defer Can this insert be deferred? (this may be ignored)
  40      */
  41     virtual void insert(void* data, const SkIRect& bounds, bool defer = false) SK_OVERRIDE;
  42
  43     /**
  44      * If any inserts have been deferred, this will add them into the tree
  45      */
  46     virtual void flushDeferredInserts() SK_OVERRIDE {}
  47
  48     /**
  49      * Given a query rectangle, populates the passed-in array with the elements it intersects
  50      */
  51     virtual void search(const SkIRect& query, SkTDArray<void*>* results) SK_OVERRIDE;
  52
  53     virtual void clear() SK_OVERRIDE;
  54
  55     /**
  56      * Gets the depth of the tree structure
  57      */
  58     virtual int getDepth() const SK_OVERRIDE;
  59
  60     /**
  61      * This gets the insertion count (rather than the node count)
  62      */
  63     virtual int getCount() const SK_OVERRIDE { return fCount; }
  64
  65     virtual void rewindInserts() SK_OVERRIDE;
  66
  67 private:
  68     class QuadTreeNode;
  69
  70     SkQuadTree(const SkIRect& bounds);
  71
  72     // This is the count of data elements (rather than total nodes in the tree)
  73     int fCount;
  74
  75     QuadTreeNode* fRoot;
  76
  77     typedef SkBBoxHierarchy INHERITED;
  78 };
  79
  80 #endif