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 */
25class SkQuadTree : public SkBBoxHierarchy {
26public:
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
75private:
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