Initial QuadTree implementation

src/core/SkRTree.h

 
 /*
  * Copyright 2012 Google Inc.
  *
  * Use of this source code is governed by a BSD-style license that can be
  * found in the LICENSE file.
  */
 
 #ifndef SkRTree_DEFINED
 #define SkRTree_DEFINED
@@ skipping 49 matching lines @@
     virtual ~SkRTree();
 
     /**
      * 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);
+    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();
+    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);
+    virtual void search(const SkIRect& query, SkTDArray<void*>* results) SK_OVERRIDE;
 
-    virtual void clear();
+    virtual void clear() SK_OVERRIDE;
     bool isEmpty() const { return 0 == fCount; }
-    int getDepth() const { return this->isEmpty() ? 0 : fRoot.fChild.subtree->fLevel + 1; }
+
+    /**
+     * Gets the depth of the tree structure
+     */
+    virtual int getDepth() const SK_OVERRIDE {
+        return this->isEmpty() ? 0 : fRoot.fChild.subtree->fLevel + 1;
+    }
 
     /**
      * This gets the insertion count (rather than the node count)
      */
-    virtual int getCount() const { return fCount; }
+    virtual int getCount() const SK_OVERRIDE { return fCount; }
 
     virtual void rewindInserts() SK_OVERRIDE;
 
 private:
 
     struct Node;
 
     /**
      * A branch of the tree, this may contain a pointer to another interior node, or a data value
      */
@@ skipping 86 matching lines @@
     SkTDArray<Branch> fDeferredInserts;
     SkScalar fAspectRatio;
     bool fSortWhenBulkLoading;
 
     Node* allocateNode(uint16_t level);
 
     typedef SkBBoxHierarchy INHERITED;
 };
 
 #endif