New R-Tree implementation

Change-Id: If46f35856279ab2a356cb7f99671fcd15f4ddf37
(cherry picked from commit 19d56fe70a9ea33c3ce2ad4f0b547e35453aeafd)

4 files changed, 651 insertions, 1626 deletions

diff --git a/Source/WebCore/Android.mk b/Source/WebCore/Android.mk
index f4f9bca..a1914c5 100644
--- a/Source/WebCore/Android.mk
+++ b/Source/WebCore/Android.mk
@@ -646,6 +646,7 @@ LOCAL_SRC_FILES := $(LOCAL_SRC_FILES) \
 	platform/graphics/android/context/PlatformGraphicsContext.cpp \
 	platform/graphics/android/context/PlatformGraphicsContextRecording.cpp \
 	platform/graphics/android/context/PlatformGraphicsContextSkia.cpp \
+	platform/graphics/android/context/RTree.cpp \
 	\
 	platform/graphics/android/fonts/FontAndroid.cpp \
 	platform/graphics/android/fonts/FontCacheAndroid.cpp \
diff --git a/Source/WebCore/platform/graphics/android/context/PlatformGraphicsContextRecording.cpp b/Source/WebCore/platform/graphics/android/context/PlatformGraphicsContextRecording.cpp
index 532a36d..001e1de 100644
--- a/Source/WebCore/platform/graphics/android/context/PlatformGraphicsContextRecording.cpp
+++ b/Source/WebCore/platform/graphics/android/context/PlatformGraphicsContextRecording.cpp
@@ -36,21 +36,6 @@ public:
     static const bool safeToCompareToEmptyOrDeleted = false;
 };
 
-class RecordingData {
-public:
-    RecordingData(GraphicsOperation::Operation* ops, int orderBy)
-        : m_orderBy(orderBy)
-        , m_operation(ops)
-    {}
-    ~RecordingData() {
-        delete m_operation;
-    }
-
-    unsigned int m_orderBy;
-    GraphicsOperation::Operation* m_operation;
-};
-
-typedef RTree<RecordingData*, float, 2> RecordingTree;
 typedef HashSet<PlatformGraphicsContext::State*, StateHash> StateHashSet;
 
 class RecordingImpl {
@@ -61,7 +46,6 @@ public:
     }
 
     ~RecordingImpl() {
-        clearTree();
         clearStates();
         clearMatrixes();
     }
@@ -81,19 +65,10 @@ public:
         return m_matrixes.last();
     }
 
-    RecordingTree m_tree;
+    RTree::RTree m_tree;
     int m_nodeCount;
 
 private:
-    void clearTree() {
-        RecordingTree::Iterator it;
-        for (m_tree.GetFirst(it); !m_tree.IsNull(it); m_tree.GetNext(it)) {
-            RecordingData* removeElem = m_tree.GetAt(it);
-            if (removeElem)
-                delete removeElem;
-        }
-        m_tree.RemoveAll();
-    }
 
     void clearStates() {
         StateHashSet::iterator end = m_states.end();
@@ -118,12 +93,6 @@ Recording::~Recording()
     delete m_recording;
 }
 
-static bool GatherSearchResults(RecordingData* data, void* context)
-{
-    ((Vector<RecordingData*>*)context)->append(data);
-    return true;
-}
-
 static bool CompareRecordingDataOrder(const RecordingData* a, const RecordingData* b)
 {
     return a->m_orderBy < b->m_orderBy;
@@ -141,9 +110,10 @@ void Recording::draw(SkCanvas* canvas)
         return;
     }
     Vector<RecordingData*> nodes;
-    float searchMin[] = {clip.fLeft, clip.fTop};
-    float searchMax[] = {clip.fRight, clip.fBottom};
-    m_recording->m_tree.Search(searchMin, searchMax, GatherSearchResults, &nodes);
+
+    WebCore::IntRect iclip = enclosingIntRect(clip);
+    m_recording->m_tree.search(iclip, nodes);
+
     size_t count = nodes.size();
     ALOGV("Drawing %d nodes out of %d (state storage=%d)", count,
           m_recording->m_nodeCount, sizeof(PlatformGraphicsContext::State) * m_recording->m_states.size());
@@ -624,9 +594,9 @@ void PlatformGraphicsContextRecording::appendDrawingOperation(
     operation->m_state = mOperationState;
     operation->m_matrix = mOperationMatrix;
     RecordingData* data = new RecordingData(operation, mRecording->recording()->m_nodeCount++);
-    float min[] = {bounds.fLeft, bounds.fTop};
-    float max[] = {bounds.fRight, bounds.fBottom};
-    mRecording->recording()->m_tree.Insert(min, max, data);
+
+    WebCore::IntRect ibounds = enclosingIntRect(bounds);
+    mRecording->recording()->m_tree.insert(ibounds, data);
 }
 
 void PlatformGraphicsContextRecording::appendStateOperation(GraphicsOperation::Operation* operation)
diff --git a/Source/WebCore/platform/graphics/android/context/RTree.cpp b/Source/WebCore/platform/graphics/android/context/RTree.cpp
new file mode 100644
index 0000000..d2bc839
--- /dev/null
+++ b/Source/WebCore/platform/graphics/android/context/RTree.cpp
@@ -0,0 +1,479 @@
+/*
+ * Copyright 2012, The Android Open Source Project
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *  * Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ *  * Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT OWNER OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#define LOG_TAG "RTree"
+#define LOG_NDEBUG 1
+
+#include "config.h"
+
+#include "RTree.h"
+#include "AndroidLog.h"
+
+namespace RTree {
+
+static unsigned gID = 0;
+
+class Element;
+
+//////////////////////////////////////////////////////////////////////
+// utility functions used by ElementList and Node
+
+static void recomputeBounds(int& minx, int& miny,
+                            int& maxx, int& maxy,
+                            unsigned& nbChildren,
+                            Node**& children, int* area)
+{
+    // compute the bounds
+
+    if (nbChildren) {
+        minx = children[0]->minx;
+        miny = children[0]->miny;
+        maxx = children[0]->maxx;
+        maxy = children[0]->maxy;
+    }
+
+    for (unsigned int i = 1; i < nbChildren; i++)
+    {
+        minx = std::min(minx, children[i]->minx);
+        miny = std::min(miny, children[i]->miny);
+        maxx = std::max(maxx, children[i]->maxx);
+        maxy = std::max(maxy, children[i]->maxy);
+    }
+
+    if (area) {
+        int w = maxx - minx;
+        int h = maxy - miny;
+        *area = w * h;
+    }
+}
+
+int computeDeltaArea(Node* n, int& minx, int& miny,
+                     int& maxx, int& maxy)
+{
+    int newMinX = std::min(minx, n->minx);
+    int newMinY = std::min(miny, n->miny);
+    int newMaxX = std::max(maxx, n->maxx);
+    int newMaxY = std::max(maxy, n->maxy);
+    int w = newMaxX - newMinX;
+    int h = newMaxY - newMinY;
+    return w * h;
+}
+
+//////////////////////////////////////////////////////////////////////
+// RTree
+
+RTree::RTree(int M)
+{
+    maxChildren = M;
+    listA = new ElementList(M);
+    listB = new ElementList(M);
+    root = new Node(this);
+}
+
+RTree::~RTree()
+{
+    delete listA;
+    delete listB;
+    delete root;
+}
+
+void RTree::insert(WebCore::IntRect& bounds, WebCore::RecordingData* payload)
+{
+    Element* e = new Element(this, bounds.x(), bounds.y(),
+                             bounds.maxX(), bounds.maxY(), payload);
+    root->insert(e);
+}
+
+void RTree::search(WebCore::IntRect& clip, Vector<WebCore::RecordingData*>&list)
+{
+    root->search(clip.x(), clip.y(), clip.maxX(), clip.maxY(), list);
+}
+
+void RTree::display()
+{
+    root->drawTree();
+}
+
+//////////////////////////////////////////////////////////////////////
+// ElementList
+
+ElementList::ElementList(int size)
+    : nbChildren(0)
+    , minx(0)
+    , maxx(0)
+    , miny(0)
+    , maxy(0)
+    , area(0)
+{
+    children = new Node*[size];
+}
+
+ElementList::~ElementList()
+{
+    delete[] children;
+}
+
+void ElementList::add(Node* n, bool doTighten)
+{
+    children[nbChildren] = n;
+    nbChildren++;
+    if (doTighten)
+        tighten();
+}
+
+void ElementList::tighten()
+{
+    recomputeBounds(minx, miny, maxx, maxy,
+                    nbChildren, children, &area);
+}
+
+int ElementList::delta(Node* n)
+{
+    return computeDeltaArea(n, minx, miny, maxx, maxy);
+}
+
+void ElementList::removeAll()
+{
+    nbChildren = 0;
+    minx = 0;
+    maxx = 0;
+    miny = 0;
+    maxy = 0;
+    area = 0;
+}
+
+void ElementList::display() {
+    for (unsigned int i = 0; i < nbChildren; i++)
+        children[i]->display(0);
+}
+
+//////////////////////////////////////////////////////////////////////
+// Node
+
+Node::Node(RTree* t)
+    : tree(t)
+    , parent(0)
+    , children(0)
+    , nbChildren(0)
+    , minx(0)
+    , miny(0)
+    , maxx(0)
+    , maxy(0)
+#ifdef DEBUG
+    , tid(gID++)
+#endif
+{
+#ifdef DEBUG
+    ALOGV("-> New Node %d", tid);
+#endif
+}
+
+Node::~Node()
+{
+    delete[] children;
+}
+
+void Node::setParent(Node* node)
+{
+    parent = node;
+}
+
+void Node::insert(Node* node)
+{
+    Node* N = findNode(node);
+    ALOGV("-> Insert Node %d (%d, %d) in node %d",
+          node->tid, node->minx, node->miny, N->tid);
+    N->add(node);
+}
+
+Node* Node::findNode(Node* node)
+{
+    if (nbChildren == 0)
+        return parent ? parent : this;
+
+    // pick the child whose bounds will be extended least
+
+    Node* pick = children[0];
+    int minIncrease = pick->delta(node);
+    for (unsigned int i = 1; i < nbChildren; i++) {
+        int increase = children[i]->delta(node);
+        if (increase < minIncrease) {
+            minIncrease = increase;
+            pick = children[i];
+        }
+    }
+
+    return pick->findNode(node);
+}
+
+void Node::tighten()
+{
+    recomputeBounds(minx, miny, maxx, maxy,
+                    nbChildren, children, 0);
+}
+
+int Node::delta(Node* node)
+{
+    return computeDeltaArea(node, minx, miny, maxx, maxy);
+}
+
+void Node::add(Node* node)
+{
+    node->setParent(this);
+    if (!children)
+        children = new Node*[tree->maxChildren + 1];
+    children[nbChildren] = node;
+    nbChildren++;
+    Node* NN = 0;
+    if (nbChildren > tree->maxChildren)
+        NN = split();
+    adjustTree(this, NN);
+    tighten();
+}
+
+void Node::remove(Node* node)
+{
+    int nodeIndex = -1;
+    for (unsigned int i = 0; i < nbChildren; i++) {
+        if (children[i] == node) {
+            nodeIndex = i;
+            break;
+        }
+    }
+    if (nodeIndex == -1)
+        return;
+
+    // compact
+    for (unsigned int i = nodeIndex; i < nbChildren-1; i++)
+        children[i] = children[i+1];
+    nbChildren--;
+}
+
+void Node::removeAll()
+{
+    nbChildren = 0;
+}
+
+Node* Node::split()
+{
+    // First, let's get the seeds
+    // The idea is to get elements as distant as possible
+    // as we can, so that the resulting splitted lists
+    // will be more likely to not overlap.
+    Node* minElementX = children[0];
+    Node* maxElementX = children[0];
+    Node* minElementY = children[0];
+    Node* maxElementY = children[0];
+    for (unsigned int i = 1; i < nbChildren; i++) {
+        if (children[i]->minx < minElementX->minx)
+            minElementX = children[i];
+        if (children[i]->miny < minElementY->miny)
+            minElementY = children[i];
+        if (children[i]->maxx >= maxElementX->maxx)
+            maxElementX = children[i];
+        if (children[i]->maxy >= maxElementY->maxy)
+            maxElementY = children[i];
+    }
+
+    int dx = maxElementX->maxx - minElementX->minx;
+    int dy = maxElementY->maxy - minElementY->miny;
+
+    // assign the two seeds...
+    Node* elementA = minElementX;
+    Node* elementB = maxElementX;
+
+    if (dx < dy) {
+        elementA = minElementY;
+        elementB = maxElementY;
+    }
+
+    // If we get the same element, just get the first and
+    // last element inserted...
+    if (elementA == elementB) {
+        elementA = children[0];
+        elementB = children[nbChildren-1];
+    }
+    ALOGV("split Node %d, dx: %d dy: %d elem A is %d, elem B is %d",
+        tid, dx, dy, elementA->tid, elementB->tid);
+
+    // Let's use some temporary lists to do the split
+    ElementList* listA = tree->listA;
+    ElementList* listB = tree->listB;
+    listA->removeAll();
+    listB->removeAll();
+
+    listA->add(elementA);
+    listB->add(elementB);
+
+    remove(elementA);
+    remove(elementB);
+
+    // For any remaining elements, insert it into the list
+    // resulting in the smallest growth
+    for (unsigned int i = 0; i < nbChildren; i++) {
+        Node* node = children[i];
+        int dA = listA->delta(node);
+        int dB = listB->delta(node);
+
+        if (dA < dB && listA->nbChildren < tree->maxChildren)
+            listA->add(node);
+        else if (dB < dA && listB->nbChildren < tree->maxChildren)
+            listB->add(node);
+        else {
+            ElementList* smallestList =
+                listA->nbChildren > listB->nbChildren ? listB : listA;
+            smallestList->add(node);
+        }
+    }
+
+    // Use the list to rebuild the nodes
+    removeAll();
+    for (unsigned int i = 0; i < listA->nbChildren; i++)
+        add(listA->children[i]);
+
+    Node* NN = new Node(tree);
+    for (unsigned int i = 0; i < listB->nbChildren; i++)
+        NN->add(listB->children[i]);
+
+    return NN;
+}
+
+bool Node::isRoot()
+{
+    return tree->root == this;
+}
+
+void Node::adjustTree(Node* N, Node* NN)
+{
+    if (N->isRoot() && NN) {
+        // build new root
+        Node* root = new Node(tree);
+        ALOGV("-> node %d created as new root", root->tid);
+        root->add(N);
+        root->add(NN);
+        tree->root = root;
+        return;
+    }
+    if (N->isRoot())
+        return;
+
+    if (NN && N->parent)
+        N->parent->add(NN);
+}
+
+#ifdef DEBUG
+static int gMaxLevel = 0;
+static int gNbNodes = 0;
+static int gNbElements = 0;
+#endif
+
+void Node::drawTree(int level)
+{
+    if (level == 0) {
+        ALOGV("\n*** show tree ***\n");
+#ifdef DEBUG
+        gMaxLevel = 0;
+        gNbNodes = 0;
+        gNbElements = 0;
+#endif
+    }
+
+    display(level);
+    for (unsigned int i = 0; i < nbChildren; i++)
+    {
+        children[i]->drawTree(level+1);
+    }
+
+#ifdef DEBUG
+    if (gMaxLevel < level)
+        gMaxLevel = level;
+
+    if (!nbChildren)
+        gNbElements++;
+    else
+        gNbNodes++;
+
+    if (level == 0) {
+        ALOGV("********************\n");
+        ALOGV("Depth level %d, total bytes: %d, %d nodes, %d bytes (%d bytes/node), %d elements, %d bytes (%d bytes/node)",
+               gMaxLevel, gNbNodes * sizeof(Node) + gNbElements * sizeof(Element),
+               gNbNodes, gNbNodes * sizeof(Node), sizeof(Node),
+               gNbElements, gNbElements * sizeof(Element), sizeof(Element));
+    }
+#endif
+}
+
+void Node::display(int level)
+{
+    ALOGV("%*sNode %d - %d, %d, %d, %d (%d x %d)",
+      2*level, "", tid, minx, miny, maxx, maxy, maxx - minx, maxy - miny);
+}
+
+bool Node::overlap(int pminx, int pminy, int pmaxx, int pmaxy)
+{
+    return ! (pminx > maxx
+           || pmaxx < minx
+           || pmaxy < miny
+           || pminy > maxy);
+}
+
+void Node::search(int minx, int miny, int maxx, int maxy, Vector<WebCore::RecordingData*>& list)
+{
+    if (isElement() && overlap(minx, miny, maxx, maxy))
+        list.append(((Element*)this)->payload);
+
+    for (unsigned int i = 0; i < nbChildren; i++) {
+        if (children[i]->overlap(minx, miny, maxx, maxy))
+            children[i]->search(minx, miny, maxx, maxy, list);
+    }
+}
+
+//////////////////////////////////////////////////////////////////////
+// Element
+
+Element::Element(RTree* tree, int pminx, int pminy, int pmaxx, int pmaxy, WebCore::RecordingData* p)
+    : Node(tree)
+    , payload(p)
+{
+    minx = pminx;
+    miny = pminy;
+    maxx = pmaxx;
+    maxy = pmaxy;
+    ALOGV("-> New element %d (%d, %d) - (%d x %d)",
+          tid, minx, miny, maxx-minx, maxy-miny);
+}
+
+Element::~Element()
+{
+    delete payload;
+}
+
+void Element::display(int level)
+{
+    ALOGV("%*selement %d (%d, %d, %d, %d) - (%d x %d)", 2*level, "",
+          tid, minx, miny, maxx, maxy, maxx-minx, maxy-miny);
+}
+
+}
diff --git a/Source/WebCore/platform/graphics/android/context/RTree.h b/Source/WebCore/platform/graphics/android/context/RTree.h
index cc4c856..75704cb 100644
--- a/Source/WebCore/platform/graphics/android/context/RTree.h
+++ b/Source/WebCore/platform/graphics/android/context/RTree.h
@@ -1,1588 +1,163 @@
-#ifndef RTREE_H

-#define RTREE_H

-

-// NOTE This file compiles under MSVC 6 SP5 and MSVC .Net 2003 it may not work on other compilers without modification.

-

-// NOTE These next few lines may be win32 specific, you may need to modify them to compile on other platform

-#include <stdio.h>

-#include <math.h>

-#include <assert.h>

-#include <stdlib.h>

-

-#ifndef Min

-  #define Min(a,b) (((a)<(b))?(a):(b))

-#endif //Min

-#ifndef Max

-  #define Max(a,b) (((a)>(b))?(a):(b))

-#endif //Max

-

-//

-// RTree.h

-//

-

-#define RTREE_TEMPLATE template<class DATATYPE, class ELEMTYPE, int NUMDIMS, class ELEMTYPEREAL, int TMAXNODES, int TMINNODES>

-#define RTREE_QUAL RTree<DATATYPE, ELEMTYPE, NUMDIMS, ELEMTYPEREAL, TMAXNODES, TMINNODES>

-

-#define RTREE_DONT_USE_MEMPOOLS // This version does not contain a fixed memory allocator, fill in lines with EXAMPLE to implement one.

-#define RTREE_USE_SPHERICAL_VOLUME // Better split classification, may be slower on some systems

-

-// Fwd decl

-class RTFileStream;  // File I/O helper class, look below for implementation and notes.

-

-/// \class RTree

-/// Implementation of RTree, a multidimensional bounding rectangle tree.

-/// Example usage: For a 3-dimensional tree use RTree<Object*, float, 3> myTree;

-///

-/// This modified, templated C++ version by Greg Douglas at Auran (http://www.auran.com)

-///

-/// DATATYPE Referenced data, should be int, void*, obj* etc. no larger than sizeof<void*> and simple type

-/// ELEMTYPE Type of element such as int or float

-/// NUMDIMS Number of dimensions such as 2 or 3

-/// ELEMTYPEREAL Type of element that allows fractional and large values such as float or double, for use in volume calcs

-///

-/// NOTES: Inserting and removing data requires the knowledge of its constant Minimal Bounding Rectangle.

-///        This version uses new/delete for nodes, I recommend using a fixed size allocator for efficiency.

-///        Instead of using a callback function for returned results, I recommend and efficient pre-sized, grow-only memory

-///        array similar to MFC CArray or STL Vector for returning search query result.

-///

-template<class DATATYPE, class ELEMTYPE, int NUMDIMS, 

-         class ELEMTYPEREAL = ELEMTYPE, int TMAXNODES = 8, int TMINNODES = TMAXNODES / 2>

-class RTree

-{

-protected: 

-

-  struct Node;  // Fwd decl.  Used by other internal structs and iterator

-

-public:

-

-  // These constant must be declared after Branch and before Node struct

-  // Stuck up here for MSVC 6 compiler.  NSVC .NET 2003 is much happier.

-  enum

-  {

-    MAXNODES = TMAXNODES,                         ///< Max elements in node

-    MINNODES = TMINNODES,                         ///< Min elements in node

-  };

-

-

-public:

-

-  RTree();

-  virtual ~RTree();

-  

-  /// Insert entry

-  /// \param a_min Min of bounding rect

-  /// \param a_max Max of bounding rect

-  /// \param a_dataId Positive Id of data.  Maybe zero, but negative numbers not allowed.

-  void Insert(const ELEMTYPE a_min[NUMDIMS], const ELEMTYPE a_max[NUMDIMS], const DATATYPE& a_dataId);

-  

-  /// Remove entry

-  /// \param a_min Min of bounding rect

-  /// \param a_max Max of bounding rect

-  /// \param a_dataId Positive Id of data.  Maybe zero, but negative numbers not allowed.

-  void Remove(const ELEMTYPE a_min[NUMDIMS], const ELEMTYPE a_max[NUMDIMS], const DATATYPE& a_dataId);

-  

-  /// Find all within search rectangle

-  /// \param a_min Min of search bounding rect

-  /// \param a_max Max of search bounding rect

-  /// \param a_searchResult Search result array.  Caller should set grow size. Function will reset, not append to array.

-  /// \param a_resultCallback Callback function to return result.  Callback should return 'true' to continue searching

-  /// \param a_context User context to pass as parameter to a_resultCallback

-  /// \return Returns the number of entries found

-  int Search(const ELEMTYPE a_min[NUMDIMS], const ELEMTYPE a_max[NUMDIMS], bool a_resultCallback(DATATYPE a_data, void* a_context), void* a_context);

-  

-  /// Remove all entries from tree

-  void RemoveAll();

-

-  /// Count the data elements in this container.  This is slow as no internal counter is maintained.

-  int Count();

-

-  /// Load tree contents from file

-  bool Load(const char* a_fileName);

-  /// Load tree contents from stream

-  bool Load(RTFileStream& a_stream);

-

-  

-  /// Save tree contents to file

-  bool Save(const char* a_fileName);

-  /// Save tree contents to stream

-  bool Save(RTFileStream& a_stream);

-

-  /// Iterator is not remove safe.

-  class Iterator

-  {

-  private:

-  

-    enum { MAX_STACK = 32 }; //  Max stack size. Allows almost n^32 where n is number of branches in node

-    

-    struct StackElement

-    {

-      Node* m_node;

-      int m_branchIndex;

-    };

-    

-  public:

-  

-    Iterator()                                    { Init(); }

-

-    ~Iterator()                                   { }

-    

-    /// Is iterator invalid

-    bool IsNull()                                 { return (m_tos <= 0); }

-

-    /// Is iterator pointing to valid data

-    bool IsNotNull()                              { return (m_tos > 0); }

-

-    /// Access the current data element. Caller must be sure iterator is not NULL first.

-    DATATYPE& operator*()

-    {

-      ASSERT(IsNotNull());

-      StackElement& curTos = m_stack[m_tos - 1];

-      return curTos.m_node->m_branch[curTos.m_branchIndex].m_data;

-    } 

-

-    /// Access the current data element. Caller must be sure iterator is not NULL first.

-    const DATATYPE& operator*() const

-    {

-      ASSERT(IsNotNull());

-      StackElement& curTos = m_stack[m_tos - 1];

-      return curTos.m_node->m_branch[curTos.m_branchIndex].m_data;

-    } 

-

-    /// Find the next data element

-    bool operator++()                             { return FindNextData(); }

-

-    /// Get the bounds for this node

-    void GetBounds(ELEMTYPE a_min[NUMDIMS], ELEMTYPE a_max[NUMDIMS])

-    {

-      ASSERT(IsNotNull());

-      StackElement& curTos = m_stack[m_tos - 1];

-      Branch& curBranch = curTos.m_node->m_branch[curTos.m_branchIndex];

-      

-      for(int index = 0; index < NUMDIMS; ++index)

-      {

-        a_min[index] = curBranch.m_rect.m_min[index];

-        a_max[index] = curBranch.m_rect.m_max[index];

-      }

-    }

-

-    /// Reset iterator

-    void Init()                                   { m_tos = 0; }

-

-    /// Find the next data element in the tree (For internal use only)

-    bool FindNextData()

-    {

-      for(;;)

-      {

-        if(m_tos <= 0)

-        {

-          return false;

-        }

-        StackElement curTos = Pop(); // Copy stack top cause it may change as we use it

-

-        if(curTos.m_node->IsLeaf())

-        {

-          // Keep walking through data while we can

-          if(curTos.m_branchIndex+1 < curTos.m_node->m_count)

-          {

-            // There is more data, just point to the next one

-            Push(curTos.m_node, curTos.m_branchIndex + 1);

-            return true;

-          }

-          // No more data, so it will fall back to previous level

-        }

-        else

-        {

-          if(curTos.m_branchIndex+1 < curTos.m_node->m_count)

-          {

-            // Push sibling on for future tree walk

-            // This is the 'fall back' node when we finish with the current level

-            Push(curTos.m_node, curTos.m_branchIndex + 1);

-          }

-          // Since cur node is not a leaf, push first of next level to get deeper into the tree

-          Node* nextLevelnode = curTos.m_node->m_branch[curTos.m_branchIndex].m_child;

-          Push(nextLevelnode, 0);

-          

-          // If we pushed on a new leaf, exit as the data is ready at TOS

-          if(nextLevelnode->IsLeaf())

-          {

-            return true;

-          }

-        }

-      }

-    }

-

-    /// Push node and branch onto iteration stack (For internal use only)

-    void Push(Node* a_node, int a_branchIndex)

-    {

-      m_stack[m_tos].m_node = a_node;

-      m_stack[m_tos].m_branchIndex = a_branchIndex;

-      ++m_tos;

-      ASSERT(m_tos <= MAX_STACK);

-    }

-    

-    /// Pop element off iteration stack (For internal use only)

-    StackElement& Pop()

-    {

-      ASSERT(m_tos > 0);

-      --m_tos;

-      return m_stack[m_tos];

-    }

-

-    StackElement m_stack[MAX_STACK];              ///< Stack as we are doing iteration instead of recursion

-    int m_tos;                                    ///< Top Of Stack index

-  

-  };

-

-  /// Get 'first' for iteration

-  void GetFirst(Iterator& a_it)

-  {

-    a_it.Init();

-    Node* first = m_root;

-    while(first)

-    {

-      if(first->IsInternalNode() && first->m_count > 1)

-      {

-        a_it.Push(first, 1); // Descend sibling branch later

-      }

-      else if(first->IsLeaf())

-      {

-        if(first->m_count)

-        {

-          a_it.Push(first, 0);

-        }

-        break;

-      }

-      first = first->m_branch[0].m_child;

-    }

-  }  

-

-  /// Get Next for iteration

-  void GetNext(Iterator& a_it)                    { ++a_it; }

-

-  /// Is iterator NULL, or at end?

-  bool IsNull(Iterator& a_it)                     { return a_it.IsNull(); }

-

-  /// Get object at iterator position

-  DATATYPE& GetAt(Iterator& a_it)                 { return *a_it; }

-

-protected:

-

-  /// Minimal bounding rectangle (n-dimensional)

-  struct Rect

-  {

-    ELEMTYPE m_min[NUMDIMS];                      ///< Min dimensions of bounding box 

-    ELEMTYPE m_max[NUMDIMS];                      ///< Max dimensions of bounding box 

-  };

-

-  /// May be data or may be another subtree

-  /// The parents level determines this.

-  /// If the parents level is 0, then this is data

-  struct Branch

-  {

-    Rect m_rect;                                  ///< Bounds

-    union

-    {

-      Node* m_child;                              ///< Child node

-      DATATYPE m_data;                            ///< Data Id or Ptr

-    };

-  };

-

-  /// Node for each branch level

-  struct Node

-  {

-    bool IsInternalNode()                         { return (m_level > 0); } // Not a leaf, but a internal node

-    bool IsLeaf()                                 { return (m_level == 0); } // A leaf, contains data

-    

-    int m_count;                                  ///< Count

-    int m_level;                                  ///< Leaf is zero, others positive

-    Branch m_branch[MAXNODES];                    ///< Branch

-  };

-  

-  /// A link list of nodes for reinsertion after a delete operation

-  struct ListNode

-  {

-    ListNode* m_next;                             ///< Next in list

-    Node* m_node;                                 ///< Node

-  };

-

-  /// Variables for finding a split partition

-  struct PartitionVars

-  {

-    int m_partition[MAXNODES+1];

-    int m_total;

-    int m_minFill;

-    int m_taken[MAXNODES+1];

-    int m_count[2];

-    Rect m_cover[2];

-    ELEMTYPEREAL m_area[2];

-

-    Branch m_branchBuf[MAXNODES+1];

-    int m_branchCount;

-    Rect m_coverSplit;

-    ELEMTYPEREAL m_coverSplitArea;

-  }; 

- 

-  Node* AllocNode();

-  void FreeNode(Node* a_node);

-  void InitNode(Node* a_node);

-  void InitRect(Rect* a_rect);

-  bool InsertRectRec(Rect* a_rect, const DATATYPE& a_id, Node* a_node, Node** a_newNode, int a_level);

-  bool InsertRect(Rect* a_rect, const DATATYPE& a_id, Node** a_root, int a_level);

-  Rect NodeCover(Node* a_node);

-  bool AddBranch(Branch* a_branch, Node* a_node, Node** a_newNode);

-  void DisconnectBranch(Node* a_node, int a_index);

-  int PickBranch(Rect* a_rect, Node* a_node);

-  Rect CombineRect(Rect* a_rectA, Rect* a_rectB);

-  void SplitNode(Node* a_node, Branch* a_branch, Node** a_newNode);

-  ELEMTYPEREAL RectSphericalVolume(Rect* a_rect);

-  ELEMTYPEREAL RectVolume(Rect* a_rect);

-  ELEMTYPEREAL CalcRectVolume(Rect* a_rect);

-  void GetBranches(Node* a_node, Branch* a_branch, PartitionVars* a_parVars);

-  void ChoosePartition(PartitionVars* a_parVars, int a_minFill);

-  void LoadNodes(Node* a_nodeA, Node* a_nodeB, PartitionVars* a_parVars);

-  void InitParVars(PartitionVars* a_parVars, int a_maxRects, int a_minFill);

-  void PickSeeds(PartitionVars* a_parVars);

-  void Classify(int a_index, int a_group, PartitionVars* a_parVars);

-  bool RemoveRect(Rect* a_rect, const DATATYPE& a_id, Node** a_root);

-  bool RemoveRectRec(Rect* a_rect, const DATATYPE& a_id, Node* a_node, ListNode** a_listNode);

-  ListNode* AllocListNode();

-  void FreeListNode(ListNode* a_listNode);

-  bool Overlap(Rect* a_rectA, Rect* a_rectB);

-  void ReInsert(Node* a_node, ListNode** a_listNode);

-  bool Search(Node* a_node, Rect* a_rect, int& a_foundCount, bool a_resultCallback(DATATYPE a_data, void* a_context), void* a_context);

-  void RemoveAllRec(Node* a_node);

-  void Reset();

-  void CountRec(Node* a_node, int& a_count);

-

-  bool SaveRec(Node* a_node, RTFileStream& a_stream);

-  bool LoadRec(Node* a_node, RTFileStream& a_stream);

-  

-  Node* m_root;                                    ///< Root of tree

-  ELEMTYPEREAL m_unitSphereVolume;                 ///< Unit sphere constant for required number of dimensions

-};

-

-

-// Because there is not stream support, this is a quick and dirty file I/O helper.

-// Users will likely replace its usage with a Stream implementation from their favorite API.

-class RTFileStream

-{

-  FILE* m_file;

-

-public:

-

-  

-  RTFileStream()

-  {

-    m_file = NULL;

-  }

-

-  ~RTFileStream()

-  {

-    Close();

-  }

-

-  bool OpenRead(const char* a_fileName)

-  {

-    m_file = fopen(a_fileName, "rb");

-    if(!m_file)

-    {

-      return false;

-    }

-    return true;

-  }

-

-  bool OpenWrite(const char* a_fileName)

-  {

-    m_file = fopen(a_fileName, "wb");

-    if(!m_file)

-    {

-      return false;

-    }

-    return true;

-  }

-

-  void Close()

-  {

-    if(m_file)

-    {

-      fclose(m_file);

-      m_file = NULL;

-    }

-  }

-

-  template< typename TYPE >

-  size_t Write(const TYPE& a_value)

-  {

-    ASSERT(m_file);

-    return fwrite((void*)&a_value, sizeof(a_value), 1, m_file);

-  }

-

-  template< typename TYPE >

-  size_t WriteArray(const TYPE* a_array, int a_count)

-  {

-    ASSERT(m_file);

-    return fwrite((void*)a_array, sizeof(TYPE) * a_count, 1, m_file);

-  }

-

-  template< typename TYPE >

-  size_t Read(TYPE& a_value)

-  {

-    ASSERT(m_file);

-    return fread((void*)&a_value, sizeof(a_value), 1, m_file);

-  }

-

-  template< typename TYPE >

-  size_t ReadArray(TYPE* a_array, int a_count)

-  {

-    ASSERT(m_file);

-    return fread((void*)a_array, sizeof(TYPE) * a_count, 1, m_file);

-  }

-};

-

-

-RTREE_TEMPLATE

-RTREE_QUAL::RTree()

-{

-  ASSERT(MAXNODES > MINNODES);

-  ASSERT(MINNODES > 0);

-

-

-  // We only support machine word size simple data type eg. integer index or object pointer.

-  // Since we are storing as union with non data branch

-  ASSERT(sizeof(DATATYPE) == sizeof(void*) || sizeof(DATATYPE) == sizeof(int));

-

-  // Precomputed volumes of the unit spheres for the first few dimensions

-  const float UNIT_SPHERE_VOLUMES[] = {

-    0.000000f, 2.000000f, 3.141593f, // Dimension  0,1,2

-    4.188790f, 4.934802f, 5.263789f, // Dimension  3,4,5

-    5.167713f, 4.724766f, 4.058712f, // Dimension  6,7,8

-    3.298509f, 2.550164f, 1.884104f, // Dimension  9,10,11

-    1.335263f, 0.910629f, 0.599265f, // Dimension  12,13,14

-    0.381443f, 0.235331f, 0.140981f, // Dimension  15,16,17

-    0.082146f, 0.046622f, 0.025807f, // Dimension  18,19,20 

-  };

-

-  m_root = AllocNode();

-  m_root->m_level = 0;

-  m_unitSphereVolume = (ELEMTYPEREAL)UNIT_SPHERE_VOLUMES[NUMDIMS];

-}

-

-

-RTREE_TEMPLATE

-RTREE_QUAL::~RTree()

-{

-  Reset(); // Free, or reset node memory

-}

-

-

-RTREE_TEMPLATE

-void RTREE_QUAL::Insert(const ELEMTYPE a_min[NUMDIMS], const ELEMTYPE a_max[NUMDIMS], const DATATYPE& a_dataId)

-{

-#ifdef _DEBUG

-  for(int index=0; index<NUMDIMS; ++index)

-  {

-    ASSERT(a_min[index] <= a_max[index]);

-  }

-#endif //_DEBUG

-

-  Rect rect;

-  

-  for(int axis=0; axis<NUMDIMS; ++axis)

-  {

-    rect.m_min[axis] = a_min[axis];

-    rect.m_max[axis] = a_max[axis];

-  }

-  

-  InsertRect(&rect, a_dataId, &m_root, 0);

-}

-

-

-RTREE_TEMPLATE

-void RTREE_QUAL::Remove(const ELEMTYPE a_min[NUMDIMS], const ELEMTYPE a_max[NUMDIMS], const DATATYPE& a_dataId)

-{

-#ifdef _DEBUG

-  for(int index=0; index<NUMDIMS; ++index)

-  {

-    ASSERT(a_min[index] <= a_max[index]);

-  }

-#endif //_DEBUG

-

-  Rect rect;

-  

-  for(int axis=0; axis<NUMDIMS; ++axis)

-  {

-    rect.m_min[axis] = a_min[axis];

-    rect.m_max[axis] = a_max[axis];

-  }

-

-  RemoveRect(&rect, a_dataId, &m_root);

-}

-

-

-RTREE_TEMPLATE

-int RTREE_QUAL::Search(const ELEMTYPE a_min[NUMDIMS], const ELEMTYPE a_max[NUMDIMS], bool a_resultCallback(DATATYPE a_data, void* a_context), void* a_context)

-{

-#ifdef _DEBUG

-  for(int index=0; index<NUMDIMS; ++index)

-  {

-    ASSERT(a_min[index] <= a_max[index]);

-  }

-#endif //_DEBUG

-

-  Rect rect;

-  

-  for(int axis=0; axis<NUMDIMS; ++axis)

-  {

-    rect.m_min[axis] = a_min[axis];

-    rect.m_max[axis] = a_max[axis];

-  }

-

-  // NOTE: May want to return search result another way, perhaps returning the number of found elements here.

-

-  int foundCount = 0;

-  Search(m_root, &rect, foundCount, a_resultCallback, a_context);

-

-  return foundCount;

-}

-

-

-RTREE_TEMPLATE

-int RTREE_QUAL::Count()

-{

-  int count = 0;

-  CountRec(m_root, count);

-  

-  return count;

-}

-

-

-

-RTREE_TEMPLATE

-void RTREE_QUAL::CountRec(Node* a_node, int& a_count)

-{

-  if(a_node->IsInternalNode())  // not a leaf node

-  {

-    for(int index = 0; index < a_node->m_count; ++index)

-    {

-      CountRec(a_node->m_branch[index].m_child, a_count);

-    }

-  }

-  else // A leaf node

-  {

-    a_count += a_node->m_count;

-  }

-}

-

-

-RTREE_TEMPLATE

-bool RTREE_QUAL::Load(const char* a_fileName)

-{

-  RemoveAll(); // Clear existing tree

-

-  RTFileStream stream;

-  if(!stream.OpenRead(a_fileName))

-  {

-    return false;

-  }

-

-  bool result = Load(stream);

-  

-  stream.Close();

-

-  return result;

-};

-

-

-

-RTREE_TEMPLATE

-bool RTREE_QUAL::Load(RTFileStream& a_stream)

-{

-  // Write some kind of header

-  int _dataFileId = ('R'<<0)|('T'<<8)|('R'<<16)|('E'<<24);

-  int _dataSize = sizeof(DATATYPE);

-  int _dataNumDims = NUMDIMS;

-  int _dataElemSize = sizeof(ELEMTYPE);

-  int _dataElemRealSize = sizeof(ELEMTYPEREAL);

-  int _dataMaxNodes = TMAXNODES;

-  int _dataMinNodes = TMINNODES;

-

-  int dataFileId = 0;

-  int dataSize = 0;

-  int dataNumDims = 0;

-  int dataElemSize = 0;

-  int dataElemRealSize = 0;

-  int dataMaxNodes = 0;

-  int dataMinNodes = 0;

-

-  a_stream.Read(dataFileId);

-  a_stream.Read(dataSize);

-  a_stream.Read(dataNumDims);

-  a_stream.Read(dataElemSize);

-  a_stream.Read(dataElemRealSize);

-  a_stream.Read(dataMaxNodes);

-  a_stream.Read(dataMinNodes);

-

-  bool result = false;

-

-  // Test if header was valid and compatible

-  if(    (dataFileId == _dataFileId) 

-      && (dataSize == _dataSize) 

-      && (dataNumDims == _dataNumDims) 

-      && (dataElemSize == _dataElemSize) 

-      && (dataElemRealSize == _dataElemRealSize) 

-      && (dataMaxNodes == _dataMaxNodes) 

-      && (dataMinNodes == _dataMinNodes) 

-    )

-  {

-    // Recursively load tree

-    result = LoadRec(m_root, a_stream);

-  }

-

-  return result;

-}

-

-

-RTREE_TEMPLATE

-bool RTREE_QUAL::LoadRec(Node* a_node, RTFileStream& a_stream)

-{

-  a_stream.Read(a_node->m_level);

-  a_stream.Read(a_node->m_count);

-

-  if(a_node->IsInternalNode())  // not a leaf node

-  {

-    for(int index = 0; index < a_node->m_count; ++index)

-    {

-      Branch* curBranch = &a_node->m_branch[index];

-

-      a_stream.ReadArray(curBranch->m_rect.m_min, NUMDIMS);

-      a_stream.ReadArray(curBranch->m_rect.m_max, NUMDIMS);

-

-      curBranch->m_child = AllocNode();

-      LoadRec(curBranch->m_child, a_stream);

-    }

-  }

-  else // A leaf node

-  {

-    for(int index = 0; index < a_node->m_count; ++index)

-    {

-      Branch* curBranch = &a_node->m_branch[index];

-

-      a_stream.ReadArray(curBranch->m_rect.m_min, NUMDIMS);

-      a_stream.ReadArray(curBranch->m_rect.m_max, NUMDIMS);

-

-      a_stream.Read(curBranch->m_data);

-    }

-  }

-

-  return true; // Should do more error checking on I/O operations

-}

-

-

-RTREE_TEMPLATE

-bool RTREE_QUAL::Save(const char* a_fileName)

-{

-  RTFileStream stream;

-  if(!stream.OpenWrite(a_fileName))

-  {

-    return false;

-  }

-

-  bool result = Save(stream);

-

-  stream.Close();

-

-  return result;

-}

-

-

-RTREE_TEMPLATE

-bool RTREE_QUAL::Save(RTFileStream& a_stream)

-{

-  // Write some kind of header

-  int dataFileId = ('R'<<0)|('T'<<8)|('R'<<16)|('E'<<24);

-  int dataSize = sizeof(DATATYPE);

-  int dataNumDims = NUMDIMS;

-  int dataElemSize = sizeof(ELEMTYPE);

-  int dataElemRealSize = sizeof(ELEMTYPEREAL);

-  int dataMaxNodes = TMAXNODES;

-  int dataMinNodes = TMINNODES;

-

-  a_stream.Write(dataFileId);

-  a_stream.Write(dataSize);

-  a_stream.Write(dataNumDims);

-  a_stream.Write(dataElemSize);

-  a_stream.Write(dataElemRealSize);

-  a_stream.Write(dataMaxNodes);

-  a_stream.Write(dataMinNodes);

-

-  // Recursively save tree

-  bool result = SaveRec(m_root, a_stream);

-  

-  return result;

-}

-

-

-RTREE_TEMPLATE

-bool RTREE_QUAL::SaveRec(Node* a_node, RTFileStream& a_stream)

-{

-  a_stream.Write(a_node->m_level);

-  a_stream.Write(a_node->m_count);

-

-  if(a_node->IsInternalNode())  // not a leaf node

-  {

-    for(int index = 0; index < a_node->m_count; ++index)

-    {

-      Branch* curBranch = &a_node->m_branch[index];

-

-      a_stream.WriteArray(curBranch->m_rect.m_min, NUMDIMS);

-      a_stream.WriteArray(curBranch->m_rect.m_max, NUMDIMS);

-

-      SaveRec(curBranch->m_child, a_stream);

-    }

-  }

-  else // A leaf node

-  {

-    for(int index = 0; index < a_node->m_count; ++index)

-    {

-      Branch* curBranch = &a_node->m_branch[index];

-

-      a_stream.WriteArray(curBranch->m_rect.m_min, NUMDIMS);

-      a_stream.WriteArray(curBranch->m_rect.m_max, NUMDIMS);

-

-      a_stream.Write(curBranch->m_data);

-    }

-  }

-

-  return true; // Should do more error checking on I/O operations

-}

-

-

-RTREE_TEMPLATE

-void RTREE_QUAL::RemoveAll()

-{

-  // Delete all existing nodes

-  Reset();

-

-  m_root = AllocNode();

-  m_root->m_level = 0;

-}

-

-

-RTREE_TEMPLATE

-void RTREE_QUAL::Reset()

-{

-#ifdef RTREE_DONT_USE_MEMPOOLS

-  // Delete all existing nodes

-  RemoveAllRec(m_root);

-#else // RTREE_DONT_USE_MEMPOOLS

-  // Just reset memory pools.  We are not using complex types

-  // EXAMPLE

-#endif // RTREE_DONT_USE_MEMPOOLS

-}

-

-

-RTREE_TEMPLATE

-void RTREE_QUAL::RemoveAllRec(Node* a_node)

-{

-  ASSERT(a_node);

-  ASSERT(a_node->m_level >= 0);

-

-  if(a_node->IsInternalNode()) // This is an internal node in the tree

-  {

-    for(int index=0; index < a_node->m_count; ++index)

-    {

-      RemoveAllRec(a_node->m_branch[index].m_child);

-    }

-  }

-  FreeNode(a_node); 

-}

-

-

-RTREE_TEMPLATE

-typename RTREE_QUAL::Node* RTREE_QUAL::AllocNode()

-{

-  Node* newNode;

-#ifdef RTREE_DONT_USE_MEMPOOLS

-  newNode = new Node;

-#else // RTREE_DONT_USE_MEMPOOLS

-  // EXAMPLE

-#endif // RTREE_DONT_USE_MEMPOOLS

-  InitNode(newNode);

-  return newNode;

-}

-

-

-RTREE_TEMPLATE

-void RTREE_QUAL::FreeNode(Node* a_node)

-{

-  ASSERT(a_node);

-

-#ifdef RTREE_DONT_USE_MEMPOOLS

-  delete a_node;

-#else // RTREE_DONT_USE_MEMPOOLS

-  // EXAMPLE

-#endif // RTREE_DONT_USE_MEMPOOLS

-}

-

-

-// Allocate space for a node in the list used in DeletRect to

-// store Nodes that are too empty.

-RTREE_TEMPLATE

-typename RTREE_QUAL::ListNode* RTREE_QUAL::AllocListNode()

-{

-#ifdef RTREE_DONT_USE_MEMPOOLS

-  return new ListNode;

-#else // RTREE_DONT_USE_MEMPOOLS

-  // EXAMPLE

-#endif // RTREE_DONT_USE_MEMPOOLS

-}

-

-

-RTREE_TEMPLATE

-void RTREE_QUAL::FreeListNode(ListNode* a_listNode)

-{

-#ifdef RTREE_DONT_USE_MEMPOOLS

-  delete a_listNode;

-#else // RTREE_DONT_USE_MEMPOOLS

-  // EXAMPLE

-#endif // RTREE_DONT_USE_MEMPOOLS

-}

-

-

-RTREE_TEMPLATE

-void RTREE_QUAL::InitNode(Node* a_node)

-{

-  a_node->m_count = 0;

-  a_node->m_level = -1;

-}

-

-

-RTREE_TEMPLATE

-void RTREE_QUAL::InitRect(Rect* a_rect)

-{

-  for(int index = 0; index < NUMDIMS; ++index)

-  {

-    a_rect->m_min[index] = (ELEMTYPE)0;

-    a_rect->m_max[index] = (ELEMTYPE)0;

-  }

-}

-

-

-// Inserts a new data rectangle into the index structure.

-// Recursively descends tree, propagates splits back up.

-// Returns 0 if node was not split.  Old node updated.

-// If node was split, returns 1 and sets the pointer pointed to by

-// new_node to point to the new node.  Old node updated to become one of two.

-// The level argument specifies the number of steps up from the leaf

-// level to insert; e.g. a data rectangle goes in at level = 0.

-RTREE_TEMPLATE

-bool RTREE_QUAL::InsertRectRec(Rect* a_rect, const DATATYPE& a_id, Node* a_node, Node** a_newNode, int a_level)

-{

-  ASSERT(a_rect && a_node && a_newNode);

-  ASSERT(a_level >= 0 && a_level <= a_node->m_level);

-

-  int index;

-  Branch branch;

-  Node* otherNode;

-

-  // Still above level for insertion, go down tree recursively

-  if(a_node->m_level > a_level)

-  {

-    index = PickBranch(a_rect, a_node);

-    if (!InsertRectRec(a_rect, a_id, a_node->m_branch[index].m_child, &otherNode, a_level))

-    {

-      // Child was not split

-      a_node->m_branch[index].m_rect = CombineRect(a_rect, &(a_node->m_branch[index].m_rect));

-      return false;

-    }

-    else // Child was split

-    {

-      a_node->m_branch[index].m_rect = NodeCover(a_node->m_branch[index].m_child);

-      branch.m_child = otherNode;

-      branch.m_rect = NodeCover(otherNode);

-      return AddBranch(&branch, a_node, a_newNode);

-    }

-  }

-  else if(a_node->m_level == a_level) // Have reached level for insertion. Add rect, split if necessary

-  {

-    branch.m_rect = *a_rect;

-    branch.m_child = (Node*) a_id;

-    // Child field of leaves contains id of data record

-    return AddBranch(&branch, a_node, a_newNode);

-  }

-  else

-  {

-    // Should never occur

-    ASSERT(0);

-    return false;

-  }

-}

-

-

-// Insert a data rectangle into an index structure.

-// InsertRect provides for splitting the root;

-// returns 1 if root was split, 0 if it was not.

-// The level argument specifies the number of steps up from the leaf

-// level to insert; e.g. a data rectangle goes in at level = 0.

-// InsertRect2 does the recursion.

-//

-RTREE_TEMPLATE

-bool RTREE_QUAL::InsertRect(Rect* a_rect, const DATATYPE& a_id, Node** a_root, int a_level)

-{

-  ASSERT(a_rect && a_root);

-  ASSERT(a_level >= 0 && a_level <= (*a_root)->m_level);

-#ifdef _DEBUG

-  for(int index=0; index < NUMDIMS; ++index)

-  {

-    ASSERT(a_rect->m_min[index] <= a_rect->m_max[index]);

-  }

-#endif //_DEBUG  

-

-  Node* newRoot;

-  Node* newNode;

-  Branch branch;

-

-  if(InsertRectRec(a_rect, a_id, *a_root, &newNode, a_level))  // Root split

-  {

-    newRoot = AllocNode();  // Grow tree taller and new root

-    newRoot->m_level = (*a_root)->m_level + 1;

-    branch.m_rect = NodeCover(*a_root);

-    branch.m_child = *a_root;

-    AddBranch(&branch, newRoot, NULL);

-    branch.m_rect = NodeCover(newNode);

-    branch.m_child = newNode;

-    AddBranch(&branch, newRoot, NULL);

-    *a_root = newRoot;

-    return true;

-  }

-

-  return false;

-}

-

-

-// Find the smallest rectangle that includes all rectangles in branches of a node.

-RTREE_TEMPLATE

-typename RTREE_QUAL::Rect RTREE_QUAL::NodeCover(Node* a_node)

-{

-  ASSERT(a_node);

-  

-  int firstTime = true;

-  Rect rect;

-  InitRect(&rect);

-  

-  for(int index = 0; index < a_node->m_count; ++index)

-  {

-    if(firstTime)

-    {

-      rect = a_node->m_branch[index].m_rect;

-      firstTime = false;

-    }

-    else

-    {

-      rect = CombineRect(&rect, &(a_node->m_branch[index].m_rect));

-    }

-  }

-  

-  return rect;

-}

-

-

-// Add a branch to a node.  Split the node if necessary.

-// Returns 0 if node not split.  Old node updated.

-// Returns 1 if node split, sets *new_node to address of new node.

-// Old node updated, becomes one of two.

-RTREE_TEMPLATE

-bool RTREE_QUAL::AddBranch(Branch* a_branch, Node* a_node, Node** a_newNode)

-{

-  ASSERT(a_branch);

-  ASSERT(a_node);

-

-  if(a_node->m_count < MAXNODES)  // Split won't be necessary

-  {

-    a_node->m_branch[a_node->m_count] = *a_branch;

-    ++a_node->m_count;

-

-    return false;

-  }

-  else

-  {

-    ASSERT(a_newNode);

-    

-    SplitNode(a_node, a_branch, a_newNode);

-    return true;

-  }

-}

-

-

-// Disconnect a dependent node.

-// Caller must return (or stop using iteration index) after this as count has changed

-RTREE_TEMPLATE

-void RTREE_QUAL::DisconnectBranch(Node* a_node, int a_index)

-{

-  ASSERT(a_node && (a_index >= 0) && (a_index < MAXNODES));

-  ASSERT(a_node->m_count > 0);

-

-  // Remove element by swapping with the last element to prevent gaps in array

-  a_node->m_branch[a_index] = a_node->m_branch[a_node->m_count - 1];

-  

-  --a_node->m_count;

-}

-

-

-// Pick a branch.  Pick the one that will need the smallest increase

-// in area to accomodate the new rectangle.  This will result in the

-// least total area for the covering rectangles in the current node.

-// In case of a tie, pick the one which was smaller before, to get

-// the best resolution when searching.

-RTREE_TEMPLATE

-int RTREE_QUAL::PickBranch(Rect* a_rect, Node* a_node)

-{

-  ASSERT(a_rect && a_node);

-  

-  bool firstTime = true;

-  ELEMTYPEREAL increase;

-  ELEMTYPEREAL bestIncr = (ELEMTYPEREAL)-1;

-  ELEMTYPEREAL area;

-  ELEMTYPEREAL bestArea;

-  int best;

-  Rect tempRect;

-

-  for(int index=0; index < a_node->m_count; ++index)

-  {

-    Rect* curRect = &a_node->m_branch[index].m_rect;

-    area = CalcRectVolume(curRect);

-    tempRect = CombineRect(a_rect, curRect);

-    increase = CalcRectVolume(&tempRect) - area;

-    if((increase < bestIncr) || firstTime)

-    {

-      best = index;

-      bestArea = area;

-      bestIncr = increase;

-      firstTime = false;

-    }

-    else if((increase == bestIncr) && (area < bestArea))

-    {

-      best = index;

-      bestArea = area;

-      bestIncr = increase;

-    }

-  }

-  return best;

-}

-

-

-// Combine two rectangles into larger one containing both

-RTREE_TEMPLATE

-typename RTREE_QUAL::Rect RTREE_QUAL::CombineRect(Rect* a_rectA, Rect* a_rectB)

-{

-  ASSERT(a_rectA && a_rectB);

-

-  Rect newRect;

-

-  for(int index = 0; index < NUMDIMS; ++index)

-  {

-    newRect.m_min[index] = Min(a_rectA->m_min[index], a_rectB->m_min[index]);

-    newRect.m_max[index] = Max(a_rectA->m_max[index], a_rectB->m_max[index]);

-  }

-

-  return newRect;

-}

-

-

-

-// Split a node.

-// Divides the nodes branches and the extra one between two nodes.

-// Old node is one of the new ones, and one really new one is created.

-// Tries more than one method for choosing a partition, uses best result.

-RTREE_TEMPLATE

-void RTREE_QUAL::SplitNode(Node* a_node, Branch* a_branch, Node** a_newNode)

-{

-  ASSERT(a_node);

-  ASSERT(a_branch);

-

-  // Could just use local here, but member or external is faster since it is reused

-  PartitionVars localVars;

-  PartitionVars* parVars = &localVars;

-  int level;

-

-  // Load all the branches into a buffer, initialize old node

-  level = a_node->m_level;

-  GetBranches(a_node, a_branch, parVars);

-

-  // Find partition

-  ChoosePartition(parVars, MINNODES);

-

-  // Put branches from buffer into 2 nodes according to chosen partition

-  *a_newNode = AllocNode();

-  (*a_newNode)->m_level = a_node->m_level = level;

-  LoadNodes(a_node, *a_newNode, parVars);

-  

-  ASSERT((a_node->m_count + (*a_newNode)->m_count) == parVars->m_total);

-}

-

-

-// Calculate the n-dimensional volume of a rectangle

-RTREE_TEMPLATE

-ELEMTYPEREAL RTREE_QUAL::RectVolume(Rect* a_rect)

-{

-  ASSERT(a_rect);

-  

-  ELEMTYPEREAL volume = (ELEMTYPEREAL)1;

-

-  for(int index=0; index<NUMDIMS; ++index)

-  {

-    volume *= a_rect->m_max[index] - a_rect->m_min[index];

-  }

-  

-  ASSERT(volume >= (ELEMTYPEREAL)0);

-  

-  return volume;

-}

-

-

-// The exact volume of the bounding sphere for the given Rect

-RTREE_TEMPLATE

-ELEMTYPEREAL RTREE_QUAL::RectSphericalVolume(Rect* a_rect)

-{

-  ASSERT(a_rect);

-   

-  ELEMTYPEREAL sumOfSquares = (ELEMTYPEREAL)0;

-  ELEMTYPEREAL radius;

-

-  for(int index=0; index < NUMDIMS; ++index) 

-  {

-    ELEMTYPEREAL halfExtent = ((ELEMTYPEREAL)a_rect->m_max[index] - (ELEMTYPEREAL)a_rect->m_min[index]) * 0.5f;

-    sumOfSquares += halfExtent * halfExtent;

-  }

-

-  radius = (ELEMTYPEREAL)sqrt(sumOfSquares);

-  

-  // Pow maybe slow, so test for common dims like 2,3 and just use x*x, x*x*x.

-  if(NUMDIMS == 3)

-  {

-    return (radius * radius * radius * m_unitSphereVolume);

-  }

-  else if(NUMDIMS == 2)

-  {

-    return (radius * radius * m_unitSphereVolume);

-  }

-  else

-  {

-    return (ELEMTYPEREAL)(pow(radius, NUMDIMS) * m_unitSphereVolume);

-  }

-}

-

-

-// Use one of the methods to calculate retangle volume

-RTREE_TEMPLATE

-ELEMTYPEREAL RTREE_QUAL::CalcRectVolume(Rect* a_rect)

-{

-#ifdef RTREE_USE_SPHERICAL_VOLUME

-  return RectSphericalVolume(a_rect); // Slower but helps certain merge cases

-#else // RTREE_USE_SPHERICAL_VOLUME

-  return RectVolume(a_rect); // Faster but can cause poor merges

-#endif // RTREE_USE_SPHERICAL_VOLUME  

-}

-

-

-// Load branch buffer with branches from full node plus the extra branch.

-RTREE_TEMPLATE

-void RTREE_QUAL::GetBranches(Node* a_node, Branch* a_branch, PartitionVars* a_parVars)

-{

-  ASSERT(a_node);

-  ASSERT(a_branch);

-

-  ASSERT(a_node->m_count == MAXNODES);

-    

-  // Load the branch buffer

-  for(int index=0; index < MAXNODES; ++index)

-  {

-    a_parVars->m_branchBuf[index] = a_node->m_branch[index];

-  }

-  a_parVars->m_branchBuf[MAXNODES] = *a_branch;

-  a_parVars->m_branchCount = MAXNODES + 1;

-

-  // Calculate rect containing all in the set

-  a_parVars->m_coverSplit = a_parVars->m_branchBuf[0].m_rect;

-  for(int index=1; index < MAXNODES+1; ++index)

-  {

-    a_parVars->m_coverSplit = CombineRect(&a_parVars->m_coverSplit, &a_parVars->m_branchBuf[index].m_rect);

-  }

-  a_parVars->m_coverSplitArea = CalcRectVolume(&a_parVars->m_coverSplit);

-

-  InitNode(a_node);

-}

-

-

-// Method #0 for choosing a partition:

-// As the seeds for the two groups, pick the two rects that would waste the

-// most area if covered by a single rectangle, i.e. evidently the worst pair

-// to have in the same group.

-// Of the remaining, one at a time is chosen to be put in one of the two groups.

-// The one chosen is the one with the greatest difference in area expansion

-// depending on which group - the rect most strongly attracted to one group

-// and repelled from the other.

-// If one group gets too full (more would force other group to violate min

-// fill requirement) then other group gets the rest.

-// These last are the ones that can go in either group most easily.

-RTREE_TEMPLATE

-void RTREE_QUAL::ChoosePartition(PartitionVars* a_parVars, int a_minFill)

-{

-  ASSERT(a_parVars);

-  

-  ELEMTYPEREAL biggestDiff;

-  int group, chosen, betterGroup;

-  

-  InitParVars(a_parVars, a_parVars->m_branchCount, a_minFill);

-  PickSeeds(a_parVars);

-

-  while (((a_parVars->m_count[0] + a_parVars->m_count[1]) < a_parVars->m_total)

-       && (a_parVars->m_count[0] < (a_parVars->m_total - a_parVars->m_minFill))

-       && (a_parVars->m_count[1] < (a_parVars->m_total - a_parVars->m_minFill)))

-  {

-    biggestDiff = (ELEMTYPEREAL) -1;

-    for(int index=0; index<a_parVars->m_total; ++index)

-    {

-      if(!a_parVars->m_taken[index])

-      {

-        Rect* curRect = &a_parVars->m_branchBuf[index].m_rect;

-        Rect rect0 = CombineRect(curRect, &a_parVars->m_cover[0]);

-        Rect rect1 = CombineRect(curRect, &a_parVars->m_cover[1]);

-        ELEMTYPEREAL growth0 = CalcRectVolume(&rect0) - a_parVars->m_area[0];

-        ELEMTYPEREAL growth1 = CalcRectVolume(&rect1) - a_parVars->m_area[1];

-        ELEMTYPEREAL diff = growth1 - growth0;

-        if(diff >= 0)

-        {

-          group = 0;

-        }

-        else

-        {

-          group = 1;

-          diff = -diff;

-        }

-

-        if(diff > biggestDiff)

-        {

-          biggestDiff = diff;

-          chosen = index;

-          betterGroup = group;

-        }

-        else if((diff == biggestDiff) && (a_parVars->m_count[group] < a_parVars->m_count[betterGroup]))

-        {

-          chosen = index;

-          betterGroup = group;

-        }

-      }

-    }

-    Classify(chosen, betterGroup, a_parVars);

-  }

-

-  // If one group too full, put remaining rects in the other

-  if((a_parVars->m_count[0] + a_parVars->m_count[1]) < a_parVars->m_total)

-  {

-    if(a_parVars->m_count[0] >= a_parVars->m_total - a_parVars->m_minFill)

-    {

-      group = 1;

-    }

-    else

-    {

-      group = 0;

-    }

-    for(int index=0; index<a_parVars->m_total; ++index)

-    {

-      if(!a_parVars->m_taken[index])

-      {

-        Classify(index, group, a_parVars);

-      }

-    }

-  }

-

-  ASSERT((a_parVars->m_count[0] + a_parVars->m_count[1]) == a_parVars->m_total);

-  ASSERT((a_parVars->m_count[0] >= a_parVars->m_minFill) && 

-        (a_parVars->m_count[1] >= a_parVars->m_minFill));

-}

-

-

-// Copy branches from the buffer into two nodes according to the partition.

-RTREE_TEMPLATE

-void RTREE_QUAL::LoadNodes(Node* a_nodeA, Node* a_nodeB, PartitionVars* a_parVars)

-{

-  ASSERT(a_nodeA);

-  ASSERT(a_nodeB);

-  ASSERT(a_parVars);

-

-  for(int index=0; index < a_parVars->m_total; ++index)

-  {

-    ASSERT(a_parVars->m_partition[index] == 0 || a_parVars->m_partition[index] == 1);

-    

-    if(a_parVars->m_partition[index] == 0)

-    {

-      AddBranch(&a_parVars->m_branchBuf[index], a_nodeA, NULL);

-    }

-    else if(a_parVars->m_partition[index] == 1)

-    {

-      AddBranch(&a_parVars->m_branchBuf[index], a_nodeB, NULL);

-    }

-  }

-}

-

-

-// Initialize a PartitionVars structure.

-RTREE_TEMPLATE

-void RTREE_QUAL::InitParVars(PartitionVars* a_parVars, int a_maxRects, int a_minFill)

-{

-  ASSERT(a_parVars);

-

-  a_parVars->m_count[0] = a_parVars->m_count[1] = 0;

-  a_parVars->m_area[0] = a_parVars->m_area[1] = (ELEMTYPEREAL)0;

-  a_parVars->m_total = a_maxRects;

-  a_parVars->m_minFill = a_minFill;

-  for(int index=0; index < a_maxRects; ++index)

-  {

-    a_parVars->m_taken[index] = false;

-    a_parVars->m_partition[index] = -1;

-  }

-}

-

-

-RTREE_TEMPLATE

-void RTREE_QUAL::PickSeeds(PartitionVars* a_parVars)

-{

-  int seed0, seed1;

-  ELEMTYPEREAL worst, waste;

-  ELEMTYPEREAL area[MAXNODES+1];

-

-  for(int index=0; index<a_parVars->m_total; ++index)

-  {

-    area[index] = CalcRectVolume(&a_parVars->m_branchBuf[index].m_rect);

-  }

-

-  worst = -a_parVars->m_coverSplitArea - 1;

-  for(int indexA=0; indexA < a_parVars->m_total-1; ++indexA)

-  {

-    for(int indexB = indexA+1; indexB < a_parVars->m_total; ++indexB)

-    {

-      Rect oneRect = CombineRect(&a_parVars->m_branchBuf[indexA].m_rect, &a_parVars->m_branchBuf[indexB].m_rect);

-      waste = CalcRectVolume(&oneRect) - area[indexA] - area[indexB];

-      if(waste > worst)

-      {

-        worst = waste;

-        seed0 = indexA;

-        seed1 = indexB;

-      }

-    }

-  }

-  Classify(seed0, 0, a_parVars);

-  Classify(seed1, 1, a_parVars);

-}

-

-

-// Put a branch in one of the groups.

-RTREE_TEMPLATE

-void RTREE_QUAL::Classify(int a_index, int a_group, PartitionVars* a_parVars)

-{

-  ASSERT(a_parVars);

-  ASSERT(!a_parVars->m_taken[a_index]);

-

-  a_parVars->m_partition[a_index] = a_group;

-  a_parVars->m_taken[a_index] = true;

-

-  if (a_parVars->m_count[a_group] == 0)

-  {

-    a_parVars->m_cover[a_group] = a_parVars->m_branchBuf[a_index].m_rect;

-  }

-  else

-  {

-    a_parVars->m_cover[a_group] = CombineRect(&a_parVars->m_branchBuf[a_index].m_rect, &a_parVars->m_cover[a_group]);

-  }

-  a_parVars->m_area[a_group] = CalcRectVolume(&a_parVars->m_cover[a_group]);

-  ++a_parVars->m_count[a_group];

-}

-

-

-// Delete a data rectangle from an index structure.

-// Pass in a pointer to a Rect, the tid of the record, ptr to ptr to root node.

-// Returns 1 if record not found, 0 if success.

-// RemoveRect provides for eliminating the root.

-RTREE_TEMPLATE

-bool RTREE_QUAL::RemoveRect(Rect* a_rect, const DATATYPE& a_id, Node** a_root)

-{

-  ASSERT(a_rect && a_root);

-  ASSERT(*a_root);

-

-  Node* tempNode;

-  ListNode* reInsertList = NULL;

-

-  if(!RemoveRectRec(a_rect, a_id, *a_root, &reInsertList))

-  {

-    // Found and deleted a data item

-    // Reinsert any branches from eliminated nodes

-    while(reInsertList)

-    {

-      tempNode = reInsertList->m_node;

-

-      for(int index = 0; index < tempNode->m_count; ++index)

-      {

-        InsertRect(&(tempNode->m_branch[index].m_rect),

-                   tempNode->m_branch[index].m_data,

-                   a_root,

-                   tempNode->m_level);

-      }

-      

-      ListNode* remLNode = reInsertList;

-      reInsertList = reInsertList->m_next;

-      

-      FreeNode(remLNode->m_node);

-      FreeListNode(remLNode);

-    }

-    

-    // Check for redundant root (not leaf, 1 child) and eliminate

-    if((*a_root)->m_count == 1 && (*a_root)->IsInternalNode())

-    {

-      tempNode = (*a_root)->m_branch[0].m_child;

-      

-      ASSERT(tempNode);

-      FreeNode(*a_root);

-      *a_root = tempNode;

-    }

-    return false;

-  }

-  else

-  {

-    return true;

-  }

-}

-

-

-// Delete a rectangle from non-root part of an index structure.

-// Called by RemoveRect.  Descends tree recursively,

-// merges branches on the way back up.

-// Returns 1 if record not found, 0 if success.

-RTREE_TEMPLATE

-bool RTREE_QUAL::RemoveRectRec(Rect* a_rect, const DATATYPE& a_id, Node* a_node, ListNode** a_listNode)

-{

-  ASSERT(a_rect && a_node && a_listNode);

-  ASSERT(a_node->m_level >= 0);

-

-  if(a_node->IsInternalNode())  // not a leaf node

-  {

-    for(int index = 0; index < a_node->m_count; ++index)

-    {

-      if(Overlap(a_rect, &(a_node->m_branch[index].m_rect)))

-      {

-        if(!RemoveRectRec(a_rect, a_id, a_node->m_branch[index].m_child, a_listNode))

-        {

-          if(a_node->m_branch[index].m_child->m_count >= MINNODES)

-          {

-            // child removed, just resize parent rect

-            a_node->m_branch[index].m_rect = NodeCover(a_node->m_branch[index].m_child);

-          }

-          else

-          {

-            // child removed, not enough entries in node, eliminate node

-            ReInsert(a_node->m_branch[index].m_child, a_listNode);

-            DisconnectBranch(a_node, index); // Must return after this call as count has changed

-          }

-          return false;

-        }

-      }

-    }

-    return true;

-  }

-  else // A leaf node

-  {

-    for(int index = 0; index < a_node->m_count; ++index)

-    {

-      if(a_node->m_branch[index].m_child == (Node*)a_id)

-      {

-        DisconnectBranch(a_node, index); // Must return after this call as count has changed

-        return false;

-      }

-    }

-    return true;

-  }

-}

-

-

-// Decide whether two rectangles overlap.

-RTREE_TEMPLATE

-bool RTREE_QUAL::Overlap(Rect* a_rectA, Rect* a_rectB)

-{

-  ASSERT(a_rectA && a_rectB);

-

-  for(int index=0; index < NUMDIMS; ++index)

-  {

-    if (a_rectA->m_min[index] > a_rectB->m_max[index] ||

-        a_rectB->m_min[index] > a_rectA->m_max[index])

-    {

-      return false;

-    }

-  }

-  return true;

-}

-

-

-// Add a node to the reinsertion list.  All its branches will later

-// be reinserted into the index structure.

-RTREE_TEMPLATE

-void RTREE_QUAL::ReInsert(Node* a_node, ListNode** a_listNode)

-{

-  ListNode* newListNode;

-

-  newListNode = AllocListNode();

-  newListNode->m_node = a_node;

-  newListNode->m_next = *a_listNode;

-  *a_listNode = newListNode;

-}

-

-

-// Search in an index tree or subtree for all data retangles that overlap the argument rectangle.

-RTREE_TEMPLATE

-bool RTREE_QUAL::Search(Node* a_node, Rect* a_rect, int& a_foundCount, bool a_resultCallback(DATATYPE a_data, void* a_context), void* a_context)

-{

-  ASSERT(a_node);

-  ASSERT(a_node->m_level >= 0);

-  ASSERT(a_rect);

-

-  if(a_node->IsInternalNode()) // This is an internal node in the tree

-  {

-    for(int index=0; index < a_node->m_count; ++index)

-    {

-      if(Overlap(a_rect, &a_node->m_branch[index].m_rect))

-      {

-        if(!Search(a_node->m_branch[index].m_child, a_rect, a_foundCount, a_resultCallback, a_context))

-        {

-          return false; // Don't continue searching

-        }

-      }

-    }

-  }

-  else // This is a leaf node

-  {

-    for(int index=0; index < a_node->m_count; ++index)

-    {

-      if(Overlap(a_rect, &a_node->m_branch[index].m_rect))

-      {

-        DATATYPE& id = a_node->m_branch[index].m_data;

-        

-        // NOTE: There are different ways to return results.  Here's where to modify

-        if(a_resultCallback)

-        {

-          ++a_foundCount;

-          if(!a_resultCallback(id, a_context))

-          {

-            return false; // Don't continue searching

-          }

-        }

-      }

-    }

-  }

-

-  return true; // Continue searching

-}

-

-

-#undef RTREE_TEMPLATE

-#undef RTREE_QUAL

-

-#endif //RTREE_H

+/*
+ * Copyright 2012, The Android Open Source Project
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *  * Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ *  * Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT OWNER OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#ifndef RTree_h
+#define RTree_h
+
+#include <Vector.h>
+#include "IntRect.h"
+#include "GraphicsOperation.h"
+
+namespace WebCore {
+
+class RecordingData {
+public:
+    RecordingData(GraphicsOperation::Operation* ops, int orderBy)
+        : m_orderBy(orderBy)
+        , m_operation(ops)
+    {}
+    ~RecordingData() {
+        delete m_operation;
+    }
+
+    unsigned int m_orderBy;
+    GraphicsOperation::Operation* m_operation;
+};
+
+}
+
+namespace RTree {
+
+class ElementList;
+class Node;
+
+class RTree {
+public:
+    // M -- max number of children per node
+    RTree(int M = 10);
+    ~RTree();
+
+    void insert(WebCore::IntRect& bounds, WebCore::RecordingData* payload);
+    // Does an overlap search
+    void search(WebCore::IntRect& clip, Vector<WebCore::RecordingData*>& list);
+    void display();
+
+private:
+
+    Node* root;
+    unsigned maxChildren;
+    ElementList* listA;
+    ElementList* listB;
+
+    friend class Node;
+};
+
+class ElementList {
+public:
+
+    ElementList(int size);
+    ~ElementList();
+    void add(Node* n, bool doTighten = true);
+    void tighten();
+    int delta(Node* n);
+    void removeAll();
+    void display();
+
+    Node** children;
+    unsigned nbChildren;
+
+private:
+
+    int minx;
+    int maxx;
+    int miny;
+    int maxy;
+    int area;
+};
+
+class Node {
+public:
+    static Node* gRoot;
+
+    Node(RTree* t);
+    virtual ~Node();
+
+    void insert(Node* n);
+    void search(int minx, int miny, int maxx, int maxy, Vector<WebCore::RecordingData*>& list);
+    void drawTree(int level = 0);
+    virtual void display(int level = 0);
+
+private:
+
+    void setParent(Node* n);
+    Node* findNode(Node* n);
+    void add(Node* n);
+    void remove(Node* n);
+    void removeAll();
+    Node* split();
+    void adjustTree(Node* N, Node* NN);
+    void tighten();
+    int delta(Node* n);
+
+    bool overlap(int minx, int miny, int maxx, int maxy);
+
+    virtual bool isElement() { return false; }
+    bool isRoot();
+
+private:
+
+    RTree* tree;
+    Node* parent;
+
+    Node** children;
+    unsigned nbChildren;
+
+public:
+
+    int minx;
+    int miny;
+    int maxx;
+    int maxy;
+
+#ifdef DEBUG
+    unsigned tid;
+#endif
+};
+
+class Element : public Node {
+public:
+
+    Element(RTree* tree, int minx, int miny, int maxx, int maxy, WebCore::RecordingData* payload);
+    virtual ~Element();
+    virtual bool isElement() { return true; }
+
+    virtual void display(int level = 0);
+
+    WebCore::RecordingData* payload;
+};
+
+}
+
+#endif // RTree_h