|
|
Boost-Commit : |
From: mariano.consoni_at_[hidden]
Date: 2008-06-17 15:42:03
Author: mconsoni
Date: 2008-06-17 15:42:02 EDT (Tue, 17 Jun 2008)
New Revision: 46456
URL: http://svn.boost.org/trac/boost/changeset/46456
Log:
- parent pointer bug.
Text files modified:
sandbox/SOC/2008/spacial_indexing/boost/spatial_index/rtree.hpp | 59 ++++++++++++++++++++++++++++++++++-----
sandbox/SOC/2008/spacial_indexing/boost/spatial_index/rtree_node.hpp | 23 ++++++++++++++
sandbox/SOC/2008/spacial_indexing/libs/spatial_index/test/simple_test_rtree.cpp | 20 +++++++------
3 files changed, 84 insertions(+), 18 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-17 15:42:02 EDT (Tue, 17 Jun 2008)
@@ -91,12 +91,25 @@
boost::shared_ptr< rtree_node<Point, Value> > n2(new rtree_leaf<Point,Value>(l->get_parent()));
split_node(l, n1, n2);
-// std::cerr << "Node splited." << std::endl;
-// n1->print();
-// n2->print();
- adjust_tree(l, n1, n2);
+ 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 << "N1" << std::endl;
+ n1->print();
+ std::cerr << "N2" << std::endl;
+ n2->print();
+
+ std::cerr << "L parent." << std::endl;
+ l->get_parent()->print();
+ adjust_tree(l, n1, n2);
} else {
+ std::cerr << "Insert without split" << std::endl;
l->insert(e, v);
adjust_tree(l);
}
@@ -147,7 +160,17 @@
void condense_tree(const boost::shared_ptr<rtree_node<Point,Value> > &l)
{
std::cerr << "Condensing tree." << std::endl;
+
+ if(l->is_root()) {
+ // if it's the root we are done
+ return;
+ }
+
/// TODO: implement
+
+ boost::shared_ptr<rtree_node<Point,Value> > parent = l->get_parent();
+ parent->adjust_box(l);
+ condense_tree(parent);
}
@@ -155,11 +178,13 @@
{
if(n->is_root()) {
// we finished the adjust
+ std::cerr << "It's the root" << std::endl;
return;
}
// as there are no splits just adjust the box of the parent and go on
boost::shared_ptr<rtree_node<Point,Value> > parent = n->get_parent();
parent->adjust_box(n);
+// parent->print();
adjust_tree(parent);
}
@@ -167,14 +192,21 @@
boost::shared_ptr<rtree_node<Point, Value> > &n1,
boost::shared_ptr<rtree_node<Point, Value> > &n2)
{
- boost::shared_ptr<rtree_node<Point,Value> > N = n1;
- boost::shared_ptr<rtree_node<Point,Value> > NN = n2;
if(l->is_root()) {
-// std::cerr << "Root ---------> split."<< std::endl;
+ std::cerr << "Root ---------> split."<< std::endl;
boost::shared_ptr< rtree_node<Point,Value> > new_root(new rtree_node<Point,Value>(boost::shared_ptr<rtree_node<Point,Value> >(), l->get_level()+1));
new_root->set_root();
new_root->add_node(n1->compute_box(), n1);
new_root->add_node(n2->compute_box(), n2);
+
+ n1->set_parent(new_root);
+ n2->set_parent(new_root);
+
+ n1->update_parent(n1);
+ n2->update_parent(n2);
+
+ std::cerr << "Adjust tree N1: " << std::endl;
+ n1->get_parent()->print();
root_ = new_root;
return;
}
@@ -182,12 +214,20 @@
parent->replace_node(l, n1);
if(parent->elements() >= M_) {
parent->add_node(n2->compute_box(), n2);
-// std::cerr << "parent is full" << std::endl;
+ std::cerr << "L Parent with the split added"<< std::endl;
+ parent->print();
+ 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();
+
adjust_tree(parent, p1, p2);
} else {
parent->add_node(n2->compute_box(), n2);
@@ -205,6 +245,9 @@
unsigned int seed1, seed2;
std::vector< geometry::box<Point> > boxes = n->get_boxes();
+ n1->set_parent(n->get_parent());
+ n2->set_parent(n->get_parent());
+
linear_pick_seeds(n, seed1, seed2);
if(n->is_leaf()) {
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-17 15:42:02 EDT (Tue, 17 Jun 2008)
@@ -120,8 +120,15 @@
unsigned int index = 0;
for(typename node_map::iterator it = nodes_.begin(); it != nodes_.end(); ++it, index++) {
if(it->second.get() == n.get()) {
-// std::cerr << "Node found!" << std::endl;
+ std::cerr << "---------------------------------------->" << std::endl;
+ std::cerr << "Node found!" << std::endl;
+ std::cerr << "Box: " << geometry::get<0>(n->compute_box().min()) << " , " <<geometry::get<1>(n->compute_box().min()) << std::endl;
+ std::cerr << "Box: " << geometry::get<0>(n->compute_box().max()) << " , " <<geometry::get<1>(n->compute_box().max()) << std::endl;
+ if(it->second->get_parent().get() != n->get_parent().get()) {
+ std::cerr << "ERR" << std::endl;
+ }
nodes_[index] = std::make_pair(n->compute_box(), n);
+ std::cerr << "---------------------------------------->" << std::endl;
return;
}
}
@@ -220,6 +227,20 @@
return parent_;
}
+ // update the parent of all the childs
+ void update_parent(const boost::shared_ptr<rtree_node<Point,Value> > &p)
+ {
+ for(typename node_map::iterator it = nodes_.begin(); it != nodes_.end(); ++it) {
+ it->second->set_parent(p);
+ }
+ }
+
+ // setter for parent
+ void set_parent(const boost::shared_ptr<rtree_node<Point,Value> > &p)
+ {
+ parent_ = p;
+ }
+
/// 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."); }
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-17 15:42:02 EDT (Tue, 17 Jun 2008)
@@ -43,7 +43,7 @@
q->bulk_insert(data, points);
- q->print();
+// q->print();
}
std::cerr << std::endl;
@@ -83,23 +83,25 @@
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->print();
q->insert(e8, 8);
q->insert(e9, 9);
q->insert(e10, 10);
q->insert(e11, 11);
- q->print();
+// q->print();
q->insert(e12, 12);
q->insert(e13, 13);
+ q->print();
q->insert(e14, 14);
- q->insert(e15, 15);
- q->print();
+ q->print();
+ q->insert(e15, 15);
+ q->print();
/// find everything overlaping with an envelope
std::cerr << " --> find in envelope" << std::endl;
@@ -137,10 +139,10 @@
}
// remove test
- 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)));
+// 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();
+// q->print();
return 0;
};
Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk