aboutsummaryrefslogtreecommitdiffhomepage
path: root/src/core/SkQuadTree.h
blob: bf1bc8ebbac3f6960be7b0a6243ca957952cdd1b (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
/*
 * Copyright 2014 Google Inc.
 *
 * Use of this source code is governed by a BSD-style license that can be
 * found in the LICENSE file.
 */

#ifndef SkQuadTree_DEFINED
#define SkQuadTree_DEFINED

#include "SkRect.h"
#include "SkTDArray.h"
#include "SkBBoxHierarchy.h"
#include "SkTInternalSList.h"
#include "SkTObjectPool.h"

/**
 * A QuadTree implementation. In short, it is a tree containing a hierarchy of bounding rectangles
 * in which each internal node has exactly four children.
 *
 * For more details see:
 *
 * http://en.wikipedia.org/wiki/Quadtree
 */
class SkQuadTree : public SkBBoxHierarchy {
public:
    SK_DECLARE_INST_COUNT(SkQuadTree)

    /**
     * Quad tree constructor.
     * @param bounds The bounding box for the root of the quad tree.
     *               giving the quad tree bounds that fall outside the root
     *               bounds may result in pathological but correct behavior.
     */
    SkQuadTree(const SkIRect& bounds);

    virtual ~SkQuadTree();

    /**
     * Insert a node, consisting of bounds and a data value into the tree, if we don't immediately
     * need to use the tree; we may allow the insert to be deferred (this can allow us to bulk-load
     * a large batch of nodes at once, which tends to be faster and produce a better tree).
     *  @param data The data value
     *  @param bounds The corresponding bounding box
     *  @param defer Can this insert be deferred? (this may be ignored)
     */
    virtual void insert(void* data, const SkIRect& bounds, bool defer = false) SK_OVERRIDE;

    /**
     * If any inserts have been deferred, this will add them into the tree
     */
    virtual void flushDeferredInserts() SK_OVERRIDE;

    /**
     * Given a query rectangle, populates the passed-in array with the elements it intersects
     */
    virtual void search(const SkIRect& query, SkTDArray<void*>* results) SK_OVERRIDE;

    virtual void clear() SK_OVERRIDE;

    /**
     * Gets the depth of the tree structure
     */
    virtual int getDepth() const SK_OVERRIDE;

    /**
     * This gets the insertion count (rather than the node count)
     */
    virtual int getCount() const SK_OVERRIDE {
        return fEntryPool.allocated() - fEntryPool.available();
    }

    virtual void rewindInserts() SK_OVERRIDE;

private:
    struct Entry {
        Entry() : fData(NULL) {}
        SkIRect fBounds;
        void* fData;
        SK_DECLARE_INTERNAL_SLIST_INTERFACE(Entry);
    };

    static const int kChildCount = 4;

    struct Node {
        Node() {
            for (int index=0; index<kChildCount; ++index) {
                fChildren[index] = NULL;
            }
        }
        SkTInternalSList<Entry> fEntries;
        SkIRect fBounds;
        SkIPoint fSplitPoint; // Only valid if the node has children.
        Node* fChildren[kChildCount];
        SK_DECLARE_INTERNAL_SLIST_ADAPTER(Node, fChildren[0]);
    };

    SkTObjectPool<Entry> fEntryPool;
    SkTObjectPool<Node> fNodePool;
    Node* fRoot;
    SkIRect fRootBounds;
    SkTInternalSList<Entry> fDeferred;

    void insert(Node* node, Entry* entry);
    void split(Node* node);
    void search(Node* node, const SkIRect& query, SkTDArray<void*>* results) const;
    void clear(Node* node);
    int getDepth(Node* node) const;

    typedef SkBBoxHierarchy INHERITED;
};

#endif