Initial QuadTree implementation

src/core/SkQuadTree.h

+/*
+ * 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"
+
+/**
+ * An 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)
+
+    /**
+     * Create a new QuadTree
+     */
+    static SkQuadTree* Create(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 fCount; }
+
+    virtual void rewindInserts() SK_OVERRIDE {}

[Justin Novosad, 2014/01/28 21:26:13]

This needs to be implemented, otherwise there will we bugs with peephole
optimizations.

[sugoi1, 2014/01/29 15:29:08]

Done.

+
+private:
+    
+    class QuadTree;
+    struct Data {
+        Data(const SkIRect& bounds, void* data) : fBounds(bounds), fInnerBounds(bounds), fData(data) {}
+        SkIRect fBounds;
+        SkIRect fInnerBounds;
+        void* fData;
+    };
+
+    SkQuadTree(const SkIRect& bounds);
+
+    // This is the count of data elements (rather than total nodes in the tree)
+    int fCount;
+
+    QuadTree* fQuadTree;
+
+    typedef SkBBoxHierarchy INHERITED;
+};
+
+#endif