Initial QuadTree implementation

src/core/SkQuadTree.cpp

+/*
+ * Copyright 2014 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+
+#include "SkQuadTree.h"
+#include "SkTSort.h"
+#include <stdio.h>
+#include <vector>
+
+class SkQuadTree::QuadTreeNode {
+public:
+    struct Data {
+        Data(const SkIRect& bounds, void* data) : fBounds(bounds), fInnerBounds(bounds), fData(data) {}
+        SkIRect fBounds;
+        SkIRect fInnerBounds;
+        void* fData;
+    };
+
+    QuadTreeNode(const SkIRect& bounds)
+     : fBounds(bounds)
+     , fTopLeft(NULL)
+     , fTopRight(NULL)
+     , fBottomLeft(NULL)
+     , fBottomRight(NULL)
+     , fCanSubdivide((fBounds.width() * fBounds.height()) > 0) {}
+
+    ~QuadTreeNode() {
+        clear();
+    }
+    
+    void clear() {
+        SkDELETE(fTopLeft);
+        fTopLeft = NULL;
+        SkDELETE(fTopRight);
+        fTopRight = NULL;
+        SkDELETE(fBottomLeft);
+        fBottomLeft = NULL;
+        SkDELETE(fBottomRight);
+        fBottomRight = NULL;
+        fData.reset();
+    }
+
+    const SkIRect& getBounds() const { return fBounds; }
+
+    // Insert data into the QuadTreeNode
+    bool insert(Data& data) {
+        // Ignore objects which do not belong in this quad tree
+        return data.fInnerBounds.intersect(fBounds) && doInsert(data);
+    }
+
+    // Find all data which appear within a range
+    void queryRange(const SkIRect& range, SkTDArray<void*>* dataInRange) const {
+        // Automatically abort if the range does not collide with this quad
+        if (!SkIRect::Intersects(fBounds, range)) {
+            return; // nothing added to the list
+        }
+
+        // Check objects at this quad level
+        for (int i = 0; i < fData.count(); ++i) {
+            if (SkIRect::Intersects(fData[i].fBounds, range)) {
+                dataInRange->push(fData[i].fData);
+            }
+        }
+
+        // Terminate here, if there are no children
+        if (!hasChildren()) {
+            return;
+        }
+
+        // Otherwise, add the data from the children
+        fTopLeft->queryRange(range, dataInRange);
+        fTopRight->queryRange(range, dataInRange);
+        fBottomLeft->queryRange(range, dataInRange);
+        fBottomRight->queryRange(range, dataInRange);
+    }
+
+    int getDepth(int i = 1) const {
+        if (hasChildren()) {
+            int depthTL = fTopLeft->getDepth(++i);
+            int depthTR = fTopRight->getDepth(i);
+            int depthBL = fBottomLeft->getDepth(i);
+            int depthBR = fBottomRight->getDepth(i);
+            return SkTMax(SkTMax(depthTL, depthTR), SkTMax(depthBL, depthBR));
+        }
+        return i;
+    }
+
+    void rewindInserts(SkBBoxHierarchyClient* client) {
+        for (int i = fData.count() - 1; i >= 0; --i) {
+            if (client->shouldRewind(fData[i].fData)) {
+                fData.remove(i);
+            }
+        }
+        if (hasChildren()) {
+            fTopLeft->rewindInserts(client);
+            fTopRight->rewindInserts(client);
+            fBottomLeft->rewindInserts(client);
+            fBottomRight->rewindInserts(client);
+        }
+    }
+
+private:
+    // create four children which fully divide this quad into four quads of equal area
+    void subdivide() {
+        if (!hasChildren() && fCanSubdivide) {
+            SkIPoint center = SkIPoint::Make(fBounds.centerX(), fBounds.centerY());
+            fTopLeft = SkNEW_ARGS(QuadTreeNode, (SkIRect::MakeLTRB(
+                fBounds.fLeft, fBounds.fTop, center.fX, center.fY)));
+            fTopRight = SkNEW_ARGS(QuadTreeNode, (SkIRect::MakeLTRB(
+                center.fX, fBounds.fTop, fBounds.fRight, center.fY)));
+            fBottomLeft = SkNEW_ARGS(QuadTreeNode, (SkIRect::MakeLTRB(
+                fBounds.fLeft, center.fY, center.fX, fBounds.fBottom)));
+            fBottomRight = SkNEW_ARGS(QuadTreeNode, (SkIRect::MakeLTRB(
+                center.fX, center.fY, fBounds.fRight, fBounds.fBottom)));
+
+            // If any of the data can fit entirely into a subregion, move it down now
+            for (int i = fData.count() - 1; i >= 0; --i) {
+                // If the data fits entirely into one of the 4 subregions, move that data
+                // down to that subregion.
+                if (fTopLeft->doInsert(fData[i]) ||
+                    fTopRight->doInsert(fData[i]) ||
+                    fBottomLeft->doInsert(fData[i]) ||
+                    fBottomRight->doInsert(fData[i])) {
+                    fData.remove(i);
+                }
+            }
+        }
+    }
+
+    bool doInsert(const Data& data) {
+        if (!fBounds.contains(data.fInnerBounds)) {
+            return false;
+        }
+
+        if (fData.count() > kQuadTreeNodeCapacity) {
+            subdivide();
+        }
+
+        // If there is space in this quad tree, add the object here
+        // If this quadtree can't be subdivided, we have no choice but to add it here
+        if ((fData.count() <= kQuadTreeNodeCapacity) || !fCanSubdivide) {
+            if (fData.isEmpty()) {
+                fData.setReserve(kQuadTreeNodeCapacity);
+            }
+            fData.push(data);
+        } else if (!fTopLeft->doInsert(data) && !fTopRight->doInsert(data) &&
+                   !fBottomLeft->doInsert(data) && !fBottomRight->doInsert(data)) {
+            // Can't be pushed down to children ? keep it here
+            fData.push(data);
+        }
+
+        return true;
+    }
+
+    bool hasChildren() const {
+        return (NULL != fTopLeft);
+    }
+
+    // Arbitrary constant to indicate how many elements can be stored in this quad tree node
+    enum { kQuadTreeNodeCapacity = 4 };
+
+    // Bounds of this quad tree
+    SkIRect fBounds;
+
+    // Data in this quad tree node
+    SkTDArray<Data> fData;
+
+    // Children
+    QuadTreeNode* fTopLeft;
+    QuadTreeNode* fTopRight;
+    QuadTreeNode* fBottomLeft;
+    QuadTreeNode* fBottomRight;
+
+    // Whether or not this node can have children
+    bool fCanSubdivide;
+};
+
+///////////////////////////////////////////////////////////////////////////////////////////////////
+
+SkQuadTree* SkQuadTree::Create(const SkIRect& bounds) {
+    return new SkQuadTree(bounds);
+}
+
+SkQuadTree::SkQuadTree(const SkIRect& bounds)
+    : fCount(0)
+    , fRoot(SkNEW_ARGS(QuadTreeNode, (bounds))) {
+    SkASSERT((bounds.width() * bounds.height()) > 0);
+}
+
+SkQuadTree::~SkQuadTree() {
+}
+
+void SkQuadTree::insert(void* data, const SkIRect& bounds, bool) {
+    if (bounds.isEmpty()) {
+        SkASSERT(false);
+        return;
+    }
+
+    QuadTreeNode::Data quadTreeData(bounds, data);
+    fRoot->insert(quadTreeData);
+    ++fCount;
+}
+
+void SkQuadTree::search(const SkIRect& query, SkTDArray<void*>* results) {
+    SkASSERT(NULL != results);
+    fRoot->queryRange(query, results);
+}
+
+void SkQuadTree::clear() {
+    fCount = 0;
+    fRoot->clear();
+}
+
+int SkQuadTree::getDepth() const {
+    return fRoot->getDepth();
+}
+
+void SkQuadTree::rewindInserts() {
+    SkASSERT(fClient);
+    fRoot->rewindInserts(fClient);
+}