All tests passing

atoader · Jan 12, 2015 · 9e248f2 · 9e248f2
1 parent cc9612a
commit 9e248f2
Show file tree

Hide file tree

Showing 8 changed files with 206 additions and 150 deletions.
diff --git a/src/Constants.hh b/src/Constants.hh
@@ -8,8 +8,8 @@
 #ifndef HRTREE_SRC_CONSTANTS_HH_
 #define HRTREE_SRC_CONSTANTS_HH_
 
-const unsigned long MAX_NODE_ENTRIES = 3; //Maximum number of entries in a node
-const unsigned long MIN_NODE_ENTRIES = 2;
+const unsigned long MAX_NODE_ENTRIES = 100; //Maximum number of entries in a node
+const unsigned long MIN_NODE_ENTRIES = 20;
 const unsigned long SIBLINGS_NO = 2; //Number of siblings required for a split
 
 #endif /* HRTREE_SRC_CONSTANTS_HH_ */
diff --git a/src/Node.cc b/src/Node.cc
@@ -129,54 +129,59 @@ void Node::insertNonLeafEntry(const boost::shared_ptr<NonLeafEntry> &entry)
 
     //If the element was inserted in the beginning, we have to search for the sibling
     //in the previous node
-    if(it==this->entries.begin())
+    if(!entry->getNode()->getPrevSibling())
     {
-        if(this->prevSibling!=NULL && this->prevSibling->entries.size()>0)
+        if(it==this->entries.begin())
         {
-            EntryIterator prevIt = this->prevSibling->entries.end();
+            if(this->prevSibling!=NULL && this->prevSibling->entries.size()>0)
+            {
+                EntryIterator prevIt = this->prevSibling->entries.end();
+                prevIt--;
+                prevSib = boost::dynamic_pointer_cast<NonLeafEntry>(*prevIt)->getNode();
+            }
+        }
+        else
+        {
+            EntryIterator prevIt =it;
             prevIt--;
             prevSib = boost::dynamic_pointer_cast<NonLeafEntry>(*prevIt)->getNode();
         }
-    }
-    else
-    {
-        EntryIterator prevIt =it;
-        prevIt--;
-        prevSib = boost::dynamic_pointer_cast<NonLeafEntry>(*prevIt)->getNode();
+        entry->getNode()->prevSibling = prevSib;
+        if(prevSib!=NULL)
+        {
+            prevSib->nextSibling = boost::dynamic_pointer_cast<NonLeafEntry>(entry)->getNode();
+            assert(entry->getNode()->leaf == prevSib->leaf);
+        }
     }
 
-    entry->getNode()->prevSibling = prevSib;
-    if(prevSib!=NULL)
+    if(!entry->getNode()->getNextSibling())
     {
-        prevSib->nextSibling = boost::dynamic_pointer_cast<NonLeafEntry>(entry)->getNode();
-        assert(entry->getNode()->leaf == prevSib->leaf);
-    }
+        //Set the next sibling of the entry
+        aux = this->entries.end();
+        aux--;
 
-    //Set the next sibling of the entry
-    aux = this->entries.end();
-    aux--;
-
-    if(it==aux)
-    {
-        //The inserted element is the last in the list
-        //try to find a sibling in the list of the sibling node.
-        if(this->nextSibling!=NULL && this->nextSibling->entries.size()>0)
+        if(it==aux)
+        {
+            //The inserted element is the last in the list
+            //try to find a sibling in the list of the sibling node.
+            if(this->nextSibling!=NULL && this->nextSibling->entries.size()>0)
+            {
+                nextSib = boost::dynamic_pointer_cast<NonLeafEntry>(*this->nextSibling->entries.begin())->getNode();
+            }
+        }
+        else
         {
-            nextSib = boost::dynamic_pointer_cast<NonLeafEntry>(*this->nextSibling->entries.begin())->getNode();
+            EntryIterator nextIt  = it;
+            nextIt++;
+            nextSib = boost::dynamic_pointer_cast<NonLeafEntry>(*nextIt)->getNode();
         }
-    }
-    else
-    {
-        EntryIterator nextIt  = it;
-        nextIt++;
-        nextSib = boost::dynamic_pointer_cast<NonLeafEntry>(*nextIt)->getNode();
-    }
 
-    entry->getNode()->nextSibling = nextSib;
-    if(nextSib!=NULL)
-    {
-        nextSib->prevSibling = boost::dynamic_pointer_cast<NonLeafEntry>(entry)->getNode();
-        assert(entry->getNode()->leaf == nextSib->leaf);
+        entry->getNode()->nextSibling = nextSib;
+        if(nextSib!=NULL)
+        {
+            nextSib->prevSibling = boost::dynamic_pointer_cast<NonLeafEntry>(entry)->getNode();
+            assert(entry->getNode()->leaf == nextSib->leaf);
+        }
     }
 }
 
@@ -285,11 +290,11 @@ std::list<Node *> Node::getSiblings(boost::uint32_t siblingsNo)
     //The node is already part of the list of cooperating siblings
     result.push_back(this);
 
-    while(result.size() < siblingsNo && left!=NULL)
-    {
-        result.push_front(left);
-        left = left->prevSibling;
-    }
+//    while(result.size() < siblingsNo && left!=NULL)
+//    {
+//        result.push_front(left);
+//        left = left->prevSibling;
+//    }
 
     while(result.size() < siblingsNo && right!=NULL)
     {
@@ -308,4 +313,7 @@ const EntryMultiSet &Node::getEntries() const
 void Node::resetEntriesSet()
 {
     this->entries.clear();
+
+    this->lhv.reset();
+    this->mbr.reset();
 }
diff --git a/src/RTree.cc b/src/RTree.cc
@@ -27,16 +27,20 @@ RTree::~RTree()
     delete this->root;
 }
 
-std::list<boost::shared_ptr<NodeEntry> > RTree::search(const boost::shared_ptr<Rectangle> &rect)
+std::list<boost::shared_ptr<NodeEntry> > RTree::search(const boost::shared_ptr<Rectangle> &query)
 {
-    return RTreeHelper::search(this->root, rect);
+    return RTreeHelper::search(this->root, query);
 }
 
 void RTree::insert(const boost::shared_ptr<Rectangle> &rect)
 {
     //Compute the hilbert value of the center of the rectangle
     boost::shared_ptr<HilbertValue> h(new HilbertValue(rect->getCenter()));
 
+    //List which contains:
+    //1. The leaf into which the new entry was inserted
+    //2. The siblings of the leaf node (if an overflow happened)
+    //3. The newly created node(if one was created)
     std::list<Node*> out_siblings;
 
     //Create a new entry to insert
@@ -48,21 +52,23 @@ void RTree::insert(const boost::shared_ptr<Rectangle> &rect)
     //Find a leaf into which we can insert this value
     Node* L = RTreeHelper::chooseLeaf(this->root, h);
 
-    //if the leaf is full
+    //if the leaf is not full, we can simply insert the value in this node
     if(!L->isOverflowing())
     {
-        //If there is room in the leaf, insert the entry
         L->insertLeafEntry(newEntry);
+        //After insertion, we must adjust the LHV and the MBR
+        L->adjustLHV();
+        L->adjustMBR();
+        //The siblings list will only contain L.
         out_siblings.push_back(L);
-
     }
     else
     {
-        //Handle the overflow of the new node.
+        //Handle the overflow of the node
         NN =  RTreeHelper::handleOverflow(L, newEntry, out_siblings);
     }
 
-    this->root = RTreeHelper::adjustTreeForInsert(this->root,L, NN, out_siblings);
+    this->root = RTreeHelper::adjustTreeForInsert(this->root, L, NN, out_siblings);
 }
 
 void RTree::remove(const boost::shared_ptr<Rectangle> &rect)

diff --git a/src/RTree.hh b/src/RTree.hh
@@ -25,18 +25,22 @@ public:
     virtual ~RTree();
 
     /**
-     * @brief search Search the R-tree for a entries that are intersected by the
+     * @brief search Search the R-tree for entries that are intersected by the
      * given rectangle.
-     * @param rect
+     * This is just a sample implementation of the search method that only retrieves the
+     * list of nodes entries instead of a list of data items.
+     * In a real implementation, this method would return a list of data objects
+     * @param query
      * @return A list of NodeEntry items that contain rectangles that are intersected
      * by the query rectangle
      */
-    std::list<boost::shared_ptr<NodeEntry> >  search(const boost::shared_ptr<Rectangle>& rect);
+    std::list<boost::shared_ptr<NodeEntry> >  search(const boost::shared_ptr<Rectangle>& query);
 
     /**
      * @brief insert Insert a new data item with the given bounding box into the tree.
+     * In this implementation, only the rectangle is inserted, but in a real implementation,
+     * additional data (pointer to disk page etc) should be inserted.
      * @param rect The bounding box to insert
-     * @param data The data item to insert. The RTree becomes the owner of this item.
      */
     void insert(const boost::shared_ptr<Rectangle>& rect);