Home | History | Annotate | Download | only in core 
      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 #include "SkTInternalSList.h"
     15 #include "SkTObjectPool.h"
     16 
     17 /**
     18  * A QuadTree implementation. In short, it is a tree containing a hierarchy of bounding rectangles
     19  * in which each internal node has exactly four children.
     20  *
     21  * For more details see:
     22  *
     23  * http://en.wikipedia.org/wiki/Quadtree
     24  */
     25 class SkQuadTree : public SkBBoxHierarchy {
     26 public:
     27     SK_DECLARE_INST_COUNT(SkQuadTree)
     28 
     29     /**
     30      * Quad tree constructor.
     31      * @param bounds The bounding box for the root of the quad tree.
     32      *               giving the quad tree bounds that fall outside the root
     33      *               bounds may result in pathological but correct behavior.
     34      */
     35     SkQuadTree(const SkIRect& bounds);
     36 
     37     virtual ~SkQuadTree();
     38 
     39     /**
     40      * Insert a node, consisting of bounds and a data value into the tree, if we don't immediately
     41      * need to use the tree; we may allow the insert to be deferred (this can allow us to bulk-load
     42      * a large batch of nodes at once, which tends to be faster and produce a better tree).
     43      *  @param data The data value
     44      *  @param bounds The corresponding bounding box
     45      *  @param defer Can this insert be deferred? (this may be ignored)
     46      */
     47     virtual void insert(void* data, const SkIRect& bounds, bool defer = false) SK_OVERRIDE;
     48 
     49     /**
     50      * If any inserts have been deferred, this will add them into the tree
     51      */
     52     virtual void flushDeferredInserts() SK_OVERRIDE;
     53 
     54     /**
     55      * Given a query rectangle, populates the passed-in array with the elements it intersects
     56      */
     57     virtual void search(const SkIRect& query, SkTDArray<void*>* results) SK_OVERRIDE;
     58 
     59     virtual void clear() SK_OVERRIDE;
     60 
     61     /**
     62      * Gets the depth of the tree structure
     63      */
     64     virtual int getDepth() const SK_OVERRIDE;
     65 
     66     /**
     67      * This gets the insertion count (rather than the node count)
     68      */
     69     virtual int getCount() const SK_OVERRIDE {
     70         return fEntryPool.allocated() - fEntryPool.available();
     71     }
     72 
     73     virtual void rewindInserts() SK_OVERRIDE;
     74 
     75 private:
     76     struct Entry {
     77         Entry() : fData(NULL) {}
     78         SkIRect fBounds;
     79         void* fData;
     80         SK_DECLARE_INTERNAL_SLIST_INTERFACE(Entry);
     81     };
     82 
     83     static const int kChildCount = 4;
     84 
     85     struct Node {
     86         Node() {
     87             for (int index=0; index<kChildCount; ++index) {
     88                 fChildren[index] = NULL;
     89             }
     90         }
     91         SkTInternalSList<Entry> fEntries;
     92         SkIRect fBounds;
     93         SkIPoint fSplitPoint; // Only valid if the node has children.
     94         Node* fChildren[kChildCount];
     95         SK_DECLARE_INTERNAL_SLIST_ADAPTER(Node, fChildren[0]);
     96     };
     97 
     98     SkTObjectPool<Entry> fEntryPool;
     99     SkTObjectPool<Node> fNodePool;
    100     Node* fRoot;
    101     SkIRect fRootBounds;
    102     SkTInternalSList<Entry> fDeferred;
    103 
    104     void insert(Node* node, Entry* entry);
    105     void split(Node* node);
    106     void search(Node* node, const SkIRect& query, SkTDArray<void*>* results) const;
    107     void clear(Node* node);
    108     int getDepth(Node* node) const;
    109 
    110     typedef SkBBoxHierarchy INHERITED;
    111 };
    112 
    113 #endif
    114