From: mariano.consoni_at_[hidden]
Date: 2008-06-18 10:35:18
Author: mconsoni
Date: 2008-06-18 10:35:18 EDT (Wed, 18 Jun 2008)
New Revision: 46478
URL: http://svn.boost.org/trac/boost/changeset/46478
Log:
- Insert bug fixed when split was expanded to parent nodes.
Text files modified:
sandbox/SOC/2008/spacial_indexing/boost/spatial_index/rtree.hpp | 131 ++++++++++++++++++++++++++++++---------
sandbox/SOC/2008/spacial_indexing/boost/spatial_index/rtree_leaf.hpp | 15 ++--
sandbox/SOC/2008/spacial_indexing/boost/spatial_index/rtree_node.hpp | 33 +++++++++
sandbox/SOC/2008/spacial_indexing/libs/spatial_index/test/simple_test_rtree.cpp | 83 ++++++++++++++++++++----
4 files changed, 208 insertions(+), 54 deletions(-)
Modified: sandbox/SOC/2008/spacial_indexing/boost/spatial_index/rtree.hpp
==============================================================================
--- sandbox/SOC/2008/spacial_indexing/boost/spatial_index/rtree.hpp (original)
+++ sandbox/SOC/2008/spacial_indexing/boost/spatial_index/rtree.hpp 2008-06-18 10:35:18 EDT (Wed, 18 Jun 2008)
@@ -46,9 +46,19 @@
{
try {
boost::shared_ptr<rtree_node<Point, Value> > l(choose_leaf(k));
+ typename rtree_leaf<Point,Value>::leaves_map q_leaves;
l->remove(k);
+ if(l->elements() < m_) {
+ std::cerr << "Few elements in Node." << std::endl;
+
+ q_leaves = l->get_leaves();
+
+ // we remove the leaf_node in the parent node because now it's empty
+ l->get_parent()->remove(l->get_parent()->get_box(l));
+ }
+
condense_tree(l);
// if the root has only one child, make it the root
@@ -57,9 +67,16 @@
root_->set_root();
}
+ std::cerr << "Reinserting leaves " << q_leaves.size() << std::endl;
+
+ for(typename rtree_leaf<Point,Value>::leaves_map::const_iterator it = q_leaves.begin(); it != q_leaves.end(); ++it) {
+ insert(it->first, it->second);
+ }
+
element_count--;
} catch(std::logic_error &e) {
// not found
+ std::cerr << e.what() << std::endl;
return;
}
}
@@ -82,7 +99,7 @@
boost::shared_ptr<rtree_node<Point, Value> > l(choose_leaf(e));
if(l->elements() >= M_) {
-// std::cerr << "Node full. Split." << std::endl;
+ std::cerr << "Node full. Split." << std::endl;
l->insert(e, v);
@@ -91,25 +108,25 @@
boost::shared_ptr< rtree_node<Point, Value> > n2(new rtree_leaf<Point,Value>(l->get_parent()));
split_node(l, n1, n2);
- std::cerr << std::endl;
- std::cerr << std::endl;
- std::cerr << std::endl;
- std::cerr << "Node splited." << std::endl;
+// std::cerr << std::endl;
+// std::cerr << std::endl;
+// std::cerr << std::endl;
+// std::cerr << "Node splited." << std::endl;
- std::cerr << "ORIG" << std::endl;
- l->print();
+// std::cerr << "ORIG" << std::endl;
+// l->print();
- std::cerr << "N1" << std::endl;
- n1->print();
- std::cerr << "N2" << std::endl;
- n2->print();
+// std::cerr << "N1" << std::endl;
+// n1->print();
+// std::cerr << "N2" << std::endl;
+// n2->print();
- std::cerr << "L parent." << std::endl;
- l->get_parent()->print();
+// std::cerr << "L parent." << std::endl;
+// l->get_parent()->print();
adjust_tree(l, n1, n2);
} else {
- std::cerr << "Insert without split" << std::endl;
+// std::cerr << "Insert without split" << std::endl;
l->insert(e, v);
adjust_tree(l);
}
@@ -161,6 +178,8 @@
{
std::cerr << "Condensing tree." << std::endl;
+ typename rtree_node<Point,Value>::node_map q_nodes;
+
if(l->is_root()) {
// if it's the root we are done
return;
@@ -170,6 +189,21 @@
boost::shared_ptr<rtree_node<Point,Value> > parent = l->get_parent();
parent->adjust_box(l);
+
+ if(parent->elements() < m_) {
+ std::cerr << "condense_node: underfull node" << std::endl;
+
+ q_nodes = parent->get_nodes();
+
+ if(parent->is_root()) {
+ std::cerr << "The underfull node is the root, returning." << std::endl;
+ return;
+ } else {
+ // we remove the node in the parent node because now it should be re inserted
+ parent->get_parent()->remove(parent->get_parent()->get_box(parent));
+ }
+ }
+
condense_tree(parent);
}
@@ -205,32 +239,60 @@
n1->update_parent(n1);
n2->update_parent(n2);
- std::cerr << "Adjust tree N1: " << std::endl;
- n1->get_parent()->print();
+// std::cerr << "Adjust tree N1: " << std::endl;
+// n1->get_parent()->print();
root_ = new_root;
return;
}
boost::shared_ptr<rtree_node<Point,Value> > parent = l->get_parent();
+// std::cerr << std::endl;
+// std::cerr << "1";
+// parent->print();
+// std::cerr << std::endl;
+// std::cerr << std::endl;
+
parent->replace_node(l, n1);
- if(parent->elements() >= M_) {
- parent->add_node(n2->compute_box(), n2);
- std::cerr << "L Parent with the split added"<< std::endl;
- parent->print();
- std::cerr << "parent is full" << std::endl;
+
+// std::cerr << "l parent" << l->get_parent().get() << std::endl;
+// std::cerr << "n1 parent" << n1->get_parent().get() << std::endl;
+// std::cerr << "l" << l.get() << std::endl;
+// std::cerr << "n1" << n1.get() << std::endl;
+// std::cerr << "n2" << n2.get() << std::endl;
+
+
+// std::cerr << std::endl;
+// std::cerr << "2";
+// parent->print();
+// std::cerr << std::endl;
+// std::cerr << std::endl;
+
+
+ parent->add_node(n2->compute_box(), n2);
+
+// std::cerr << std::endl;
+// std::cerr << "3";
+// parent->print();
+// std::cerr << std::endl;
+// std::cerr << std::endl;
+
+
+ if(parent->elements() > M_) {
+// std::cerr << "parent is full" << std::endl;
boost::shared_ptr< rtree_node<Point, Value> > p1(new rtree_node<Point,Value>(parent->get_parent(), parent->get_level()));
boost::shared_ptr< rtree_node<Point, Value> > p2(new rtree_node<Point,Value>(parent->get_parent(), parent->get_level()));
split_node(parent, p1, p2);
- std::cerr << "P1: " << std::endl;
- p1->print();
- std::cerr << "P2: " << std::endl;
- p2->print();
+// std::cerr << "P1: " << std::endl;
+// p1->print();
+// std::cerr << "P2: " << std::endl;
+// p2->print();
adjust_tree(parent, p1, p2);
} else {
- parent->add_node(n2->compute_box(), n2);
+// std::cerr << "parent is not full." << std::endl;
+// parent->print();
adjust_tree(parent);
}
}
@@ -256,20 +318,29 @@
unsigned int index = 0;
typename rtree_leaf<Point,Value>::leaves_map nodes = n->get_leaves();
+ unsigned int remaining = nodes.size()-2;
for(typename rtree_leaf<Point,Value>::leaves_map::const_iterator it = nodes.begin(); it != nodes.end(); ++it, index++) {
if(index != seed1 && index != seed2) {
- unsigned int remaining = nodes.size() - index; // 2 because of the seeds
+// std::cerr << "n1.elements: " << n1->elements() << std::endl;
+// std::cerr << "n2.elements: " << n2->elements() << std::endl;
+// std::cerr << "size: " << nodes.size() << std::endl;
+// std::cerr << "index: " << index << std::endl;
+// std::cerr << "remaining: " << remaining << std::endl;
if(n1->elements() + remaining == m_) {
+// std::cerr << "Adding to n1 because few elements" << std::endl;
n1->add_value(it->first, it->second);
continue;
}
if(n2->elements() + remaining == m_) {
+// std::cerr << "Adding to n2 because few elements" << std::endl;
n2->add_value(it->first, it->second);
continue;
}
+ remaining--;
+
/// current boxes of each group
geometry::box<Point> b1, b2;
@@ -308,7 +379,6 @@
}
}
}
-
}
}
} else {
@@ -317,11 +387,10 @@
unsigned int index = 0;
typename rtree_node<Point,Value>::node_map nodes = n->get_nodes();
+ unsigned int remaining = nodes.size()-2;
for(typename rtree_node<Point,Value>::node_map::const_iterator it = nodes.begin(); it != nodes.end(); ++it, index++) {
if(index != seed1 && index != seed2) {
- unsigned int remaining = nodes.size() - index; // 2 because of the seeds
-
if(n1->elements() + remaining == m_) {
n1->add_node(it->first, it->second);
continue;
@@ -331,6 +400,8 @@
continue;
}
+ remaining--;
+
/// current boxes of each group
geometry::box<Point> b1, b2;
Modified: sandbox/SOC/2008/spacial_indexing/boost/spatial_index/rtree_leaf.hpp
==============================================================================
--- sandbox/SOC/2008/spacial_indexing/boost/spatial_index/rtree_leaf.hpp (original)
+++ sandbox/SOC/2008/spacial_indexing/boost/spatial_index/rtree_leaf.hpp 2008-06-18 10:35:18 EDT (Wed, 18 Jun 2008)
@@ -90,6 +90,9 @@
virtual Value get_value(const unsigned int i) const { return nodes_[i].second; }
+ /// box projector for leaf
+ virtual geometry::box<Point> get_box(const unsigned int i) const { return nodes_[i].first; }
+
/// remove value with key 'k' in this leaf
virtual void remove(const geometry::box<Point> &k)
@@ -117,20 +120,18 @@
virtual void print(void) const
{
- std::cerr << " --> Leaf --------" << std::endl;
- std::cerr << " Size: " << nodes_.size() << std::endl;
+ std::cerr << "\t" << " --> Leaf --------" << std::endl;
+ std::cerr << "\t" << " Size: " << nodes_.size() << std::endl;
for(typename leaves_map::const_iterator it = nodes_.begin(); it != nodes_.end(); ++it) {
- std::cerr << " | ";
+
+ std::cerr << "\t" << " | ";
std::cerr << "( " << geometry::get<0>(it->first.min()) << " , " << geometry::get<1>(it->first.min()) << " ) x " ;
std::cerr << "( " << geometry::get<0>(it->first.max()) << " , " << geometry::get<1>(it->first.max()) << " )" ;
std::cerr << " -> ";
std::cerr << it->second;
std::cerr << " | " << std::endl;;
-
-
}
- std::cerr << std::endl;
- std::cerr << " --< Leaf --------" << std::endl;
+ std::cerr << "\t" << " --< Leaf --------" << std::endl;
}
private:
Modified: sandbox/SOC/2008/spacial_indexing/boost/spatial_index/rtree_node.hpp
==============================================================================
--- sandbox/SOC/2008/spacial_indexing/boost/spatial_index/rtree_node.hpp (original)
+++ sandbox/SOC/2008/spacial_indexing/boost/spatial_index/rtree_node.hpp 2008-06-18 10:35:18 EDT (Wed, 18 Jun 2008)
@@ -132,12 +132,18 @@
return;
}
}
- std::cerr << "adjust_node: node not found." << std::endl;
+// std::cerr << "adjust_node: node not found." << std::endl;
}
virtual void remove(const geometry::box<Point> &k)
{
- throw std::logic_error("Remove from a node, not a leaf");
+ for(typename node_map::iterator it = nodes_.begin(); it != nodes_.end(); ++it) {
+ if(it->first.min() == k.min() && it->first.max() == k.max()) {
+ std::cerr << "Erasing node." << std::endl;
+ nodes_.erase(it);
+ return;
+ }
+ }
}
/// replace the node in the nodes_ vector and recompute the box
@@ -148,6 +154,7 @@
if(it->second.get() == l.get()) {
// std::cerr << "Node found!" << std::endl;
nodes_[index] = std::make_pair(new_l->compute_box(), new_l);
+ new_l->update_parent(new_l);
return;
}
}
@@ -158,6 +165,7 @@
virtual void add_node(const geometry::box<Point> &b, const boost::shared_ptr<rtree_node<Point, Value> > &n)
{
nodes_.push_back(std::make_pair(b, n));
+ n->update_parent(n);
}
/// add a value (not allowed in nodes)
@@ -244,6 +252,21 @@
/// value projector for leaf_node (not allowed here)
virtual Value get_value(const unsigned int i) const { throw std::logic_error("No values in a non-leaf node."); }
+ /// box projector for node
+ virtual geometry::box<Point> get_box(const unsigned int i) const { return nodes_[i].first; }
+
+ /// box projector for node
+ virtual geometry::box<Point> get_box(const boost::shared_ptr<rtree_node<Point, Value> > &l) const
+ {
+ for(typename node_map::const_iterator it = nodes_.begin(); it != nodes_.end(); ++it) {
+ if(it->second.get() == l.get()) {
+ return it->first;
+ }
+ }
+ throw std::logic_error("Node not found");
+ }
+
+
/// value projector for the nodes
node_map get_nodes(void) const { return nodes_; }
@@ -251,11 +274,17 @@
virtual void print(void) const
{
std::cerr << " --> Node --------" << std::endl;
+ std::cerr << " Address: " << this << std::endl;
std::cerr << " Is Root: " << is_root() << std::endl;
std::cerr << " Level: " << level_ << std::endl;
std::cerr << " Size: " << nodes_.size() << std::endl;
std::cerr << " | ";
for(typename node_map::const_iterator it = nodes_.begin(); it != nodes_.end(); ++it) {
+
+ if(it->second->get_parent().get() != this) {
+ std::cerr << "ERROR - " << this << " is not " <<it->second->get_parent().get() << " ";
+ }
+
std::cerr << "( " << geometry::get<0>(it->first.min()) << " , " << geometry::get<1>(it->first.min()) << " ) x " ;
std::cerr << "( " << geometry::get<0>(it->first.max()) << " , " << geometry::get<1>(it->first.max()) << " )" ;
std::cerr << " | ";
Modified: sandbox/SOC/2008/spacial_indexing/libs/spatial_index/test/simple_test_rtree.cpp
==============================================================================
--- sandbox/SOC/2008/spacial_indexing/libs/spatial_index/test/simple_test_rtree.cpp (original)
+++ sandbox/SOC/2008/spacial_indexing/libs/spatial_index/test/simple_test_rtree.cpp 2008-06-18 10:35:18 EDT (Wed, 18 Jun 2008)
@@ -76,6 +76,17 @@
geometry::box<geometry::point_xy<double> > e14(geometry::point_xy<double>(10.0, 13.0), geometry::point_xy<double>(10.0, 13.0));
geometry::box<geometry::point_xy<double> > e15(geometry::point_xy<double>(10.0, 13.0), geometry::point_xy<double>(12.0, 14.0));
+ geometry::box<geometry::point_xy<double> > e16(geometry::point_xy<double>(7.0, 7.0), geometry::point_xy<double>(8.8,8.8));
+ geometry::box<geometry::point_xy<double> > e17(geometry::point_xy<double>(8.0, 9.0), geometry::point_xy<double>(9.0,10.0));
+ geometry::box<geometry::point_xy<double> > e18(geometry::point_xy<double>(10.0, 10.0), geometry::point_xy<double>(11.0,11.0));
+ geometry::box<geometry::point_xy<double> > e19(geometry::point_xy<double>(10.0, 11.0), geometry::point_xy<double>(12.0,12.5));
+ geometry::box<geometry::point_xy<double> > e20(geometry::point_xy<double>(11.0, 10.0), geometry::point_xy<double>(14.0,14.0));
+ geometry::box<geometry::point_xy<double> > e21(geometry::point_xy<double>(12.0, 12.0), geometry::point_xy<double>(14.0,14.0));
+ geometry::box<geometry::point_xy<double> > e22(geometry::point_xy<double>(12.0, 12.0), geometry::point_xy<double>(12.5,12.5));
+ geometry::box<geometry::point_xy<double> > e23(geometry::point_xy<double>(13.0, 11.0), geometry::point_xy<double>(13.5,11.5));
+ geometry::box<geometry::point_xy<double> > e24(geometry::point_xy<double>(13.0, 12.0), geometry::point_xy<double>(13.5,12.5));
+ geometry::box<geometry::point_xy<double> > e25(geometry::point_xy<double>(13.0, 13.0), geometry::point_xy<double>(13.5,13.5));
+
std::cerr << " --> insert env" << std::endl;
q->insert(e1, 1);
@@ -83,25 +94,63 @@
q->insert(e3, 3);
q->insert(e4, 4);
q->insert(e5, 5);
-// q->print();
+// q->print();
- q->insert(e6, 6);
- q->insert(e7, 7);
-// q->print();
-
- q->insert(e8, 8);
- q->insert(e9, 9);
- q->insert(e10, 10);
- q->insert(e11, 11);
+ q->insert(e6, 6);
+ q->insert(e7, 7);
// q->print();
- q->insert(e12, 12);
- q->insert(e13, 13);
- q->print();
- q->insert(e14, 14);
+ q->insert(e8, 8);
+ q->insert(e9, 9);
+ q->insert(e10, 10);
+ q->insert(e11, 11);
+
+ q->insert(e12, 12);
+ q->insert(e13, 13);
+ q->insert(e14, 14);
+ q->insert(e15, 15);
+
+// q->print();
+
+ q->insert(e16, 16);
+ q->insert(e17, 17);
+ q->insert(e18, 18);
+ q->insert(e19, 19);
+ q->insert(e20, 20);
+
q->print();
- q->insert(e15, 15);
+
+ q->insert(e21, 21);
+
q->print();
+ return 0;
+
+ q->insert(e22, 22);
+ q->insert(e23, 23);
+
+
+
+// q->insert(e24, 24);
+// q->insert(e25, 25);
+
+// q->print();
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
/// find everything overlaping with an envelope
std::cerr << " --> find in envelope" << std::endl;
@@ -142,7 +191,11 @@
std::cerr << " --> remove" << std::endl;
q->remove(geometry::box<geometry::point_xy<double> >(geometry::point_xy<double>(10.0,10.0), geometry::point_xy<double>(12.0,13.0)));
- q->print();
+ std::cerr << " --> remove" << std::endl;
+// q->print();
+ q->remove(geometry::box<geometry::point_xy<double> >(geometry::point_xy<double>(7.0,4.0), geometry::point_xy<double>(12.0,7.0)));
+// q->print();
+
return 0;
};