|
|
Boost-Commit : |
From: mariano.consoni_at_[hidden]
Date: 2008-06-24 14:54:11
Author: mconsoni
Date: 2008-06-24 14:54:10 EDT (Tue, 24 Jun 2008)
New Revision: 46659
URL: http://svn.boost.org/trac/boost/changeset/46659
Log:
- Some bugs fixed that appeared with the complete remove test.
Text files modified:
sandbox/SOC/2008/spacial_indexing/boost/spatial_index/rtree.hpp | 53 +++++++++++++++++++++++++++------------
sandbox/SOC/2008/spacial_indexing/boost/spatial_index/rtree_leaf.hpp | 2
sandbox/SOC/2008/spacial_indexing/boost/spatial_index/rtree_node.hpp | 16 +++++++++--
sandbox/SOC/2008/spacial_indexing/libs/spatial_index/test/performance_test_rtree.cpp | 30 ++++++++++++++++++----
4 files changed, 74 insertions(+), 27 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-24 14:54:10 EDT (Tue, 24 Jun 2008)
@@ -21,6 +21,9 @@
class rtree : public spatial_index<Point, Value>
{
private:
+ /// cached number of elements
+ unsigned int element_count_;
+
// minimum number of elements per node
unsigned int m_;
// maximum number of elements per node
@@ -31,7 +34,7 @@
public:
rtree(const geometry::box<Point> &initial_box, const unsigned int &M, const unsigned int &m)
- : m_(m), M_(M), root_(new rtree_node<Point, Value>(boost::shared_ptr< rtree_node<Point,Value> >(), 1))
+ : element_count_(0), m_(m), M_(M), root_(new rtree_node<Point, Value>(boost::shared_ptr< rtree_node<Point,Value> >(), 1))
{
root_->set_root();
boost::shared_ptr< rtree_leaf<Point, Value> > new_leaf(new rtree_leaf<Point, Value>(root_));
@@ -53,12 +56,13 @@
l->remove(k);
- if(l->elements() < m_) {
-// std::cerr << "Few elements in Node." << std::endl;
+ if(l->elements() < m_ && 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
+// std::cerr << "Remove the leaf from the parent\n";
l->get_parent()->remove(l->get_parent()->get_box(l));
}
@@ -71,37 +75,43 @@
// reinserting leaves from nodes
for(typename rtree_leaf<Point,Value>::leaves_map::const_iterator itl = leaves.begin(); itl != leaves.end(); ++itl) {
+// std::cerr << "Reinserting from nodes.\n";
s.push_back(*itl);
}
}
-
for(typename std::vector<std::pair<geometry::box<Point>, Value> >::const_iterator it = s.begin(); it != s.end(); ++it) {
-// std::cerr << "Inserting " << it->second << std::endl;
- insert(it->first, it->second);
+// std::cerr << "Inserting (" << elements() << ")" << it->second << std::endl;
+ element_count_--;
+ insert(it->first, it->second);
}
- // if the root has only one child, make it the root
+ // if the root has only one child and the child is not a leaf, make it the root
if(root_->elements() == 1) {
- root_ = root_->first_element();
- root_->set_root();
+ if(!root_->first_element()->is_leaf()) {
+ root_ = root_->first_element();
+ 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) {
+ element_count_--;
insert(it->first, it->second);
}
+ element_count_--;
+
} catch(std::logic_error &e) {
// not found
+// print();
std::cerr << e.what() << std::endl;
return;
}
}
- virtual unsigned int elements(void) { return root_->get_leaves().size(); }
-
+ virtual unsigned int elements(void) { return element_count_; }
virtual void print(void) const
{
@@ -119,6 +129,8 @@
void insert(const geometry::box<Point> &e, const Value &v)
{
+ element_count_++;
+
boost::shared_ptr<rtree_node<Point, Value> > l(choose_leaf(e));
// std::cerr << "Leaf: " << std::endl;
@@ -152,6 +164,8 @@
// l->get_parent()->print();
adjust_tree(l, n1, n2);
+
+
} else {
// std::cerr << "Insert without split" << std::endl;
l->insert(e, v);
@@ -165,7 +179,7 @@
typename std::vector<Point>::iterator it_point;
typename std::vector<Value>::iterator it_value;
-// unsigned int count = 0;
+ // unsigned int count = 0;
it_point = points.begin();
it_value = values.begin();
@@ -175,12 +189,12 @@
it_point++;
it_value++;
-// count++;
+ // count++;
-// if(count % 1000 == 0) {
-// std::cerr << "Count: " << count << std::endl;
-// print();
-// }
+ // if(count % 1000 == 0) {
+ // std::cerr << "Count: " << count << std::endl;
+ // print();
+ // }
}
}
@@ -616,6 +630,8 @@
typename std::vector<boost::shared_ptr<rtree_node<Point,Value> > > nodes;
root_->find_leaves(e, nodes);
+// std::cerr << "Possible leaves: " << nodes.size() << std::endl;
+
// refine the result
for(typename std::vector<boost::shared_ptr<rtree_node<Point,Value> > >::const_iterator it = nodes.begin(); it != nodes.end(); ++it) {
@@ -627,6 +643,9 @@
}
}
+ // std::cerr << "Not found: ( " << geometry::get<0>(e.min()) << " , " << geometry::get<1>(e.min()) << " ) x " ;
+ // std::cerr << "( " << geometry::get<0>(e.max()) << " , " << geometry::get<1>(e.max()) << " )" ;
+
throw std::logic_error("not found");
}
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-24 14:54:10 EDT (Tue, 24 Jun 2008)
@@ -48,7 +48,7 @@
virtual geometry::box<Point> compute_box(void) const
{
if(nodes_.empty()) {
- throw std::logic_error("Compute box in an empty node.");
+ return geometry::box<Point>();
}
typename leaves_map::const_iterator it = nodes_.begin();
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-24 14:54:10 EDT (Tue, 24 Jun 2008)
@@ -77,7 +77,17 @@
void find_leaves(const geometry::box<Point> &e, typename std::vector<boost::shared_ptr<rtree_node<Point,Value> > > &result) const
{
+// std::cerr << "find_leaves\n";
+
for(typename node_map::const_iterator it = nodes_.begin(); it != nodes_.end(); ++it) {
+
+ // std::cerr << "e: ( " << geometry::get<0>(e.min()) << " , " << geometry::get<1>(e.min()) << " ) x " ;
+ // std::cerr << "( " << geometry::get<0>(e.max()) << " , " << geometry::get<1>(e.max()) << " )" ;
+
+
+ // std::cerr << "it: ( " << 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()) << " )" ;
+
if(overlaps(it->first, e)) {
if(it->second->is_leaf()) {
result.push_back(it->second);
@@ -92,9 +102,9 @@
/// compute bounding box for this leaf
virtual geometry::box<Point> compute_box(void) const
{
- if(nodes_.empty()) {
- throw std::logic_error("Compute box in an empty node.");
- }
+ if(nodes_.empty()) {
+ return geometry::box<Point>();
+ }
typename node_map::const_iterator it = nodes_.begin();
geometry::box<Point> r = it->first;
Modified: sandbox/SOC/2008/spacial_indexing/libs/spatial_index/test/performance_test_rtree.cpp
==============================================================================
--- sandbox/SOC/2008/spacial_indexing/libs/spatial_index/test/performance_test_rtree.cpp (original)
+++ sandbox/SOC/2008/spacial_indexing/libs/spatial_index/test/performance_test_rtree.cpp 2008-06-24 14:54:10 EDT (Tue, 24 Jun 2008)
@@ -50,8 +50,7 @@
data >> x;
data >> y;
- if(geometry::within(geometry::point_xy<double>(x,y), query_box)) {
- // std::cerr << "Rect: (" << x << "," << y << ")" << std::endl;
+ if(geometry::within(geometry::point_xy<double>(x,y), query_box)) {
rect_count++;
}
v.insert(geometry::point_xy<double>(x,y));
@@ -109,13 +108,17 @@
// load data
std::cerr << " --> bulk insert" << std::endl;
std::vector<unsigned int>::iterator b, e;
-// b = ids.begin();
-// e = ids.end();
+ // b = ids.begin();
+ // e = ids.end();
start = time(NULL);
q->bulk_insert(ids, points);
std::cerr << "Insertion time: " << time(NULL) - start << " seconds." << std::endl;
+// std::cerr << "Elements: " << q->elements() << std::endl;
+
+// q->print();
+
// -- wait to check memory
// std::cerr << "check memory --> After Building Index." << std::endl;
// sleep(5);
@@ -136,6 +139,9 @@
std::deque<unsigned int> d = q->find(query_box);
std::cerr << " --> find rectangle" << std::endl;
BOOST_CHECK_EQUAL(rect_count, d.size());
+// for(std::deque<unsigned int>::const_iterator it = d.begin(); it != d.end(); ++it) {
+// std::cerr << "r: " << *it << std::endl;
+// }
std::cerr << "Retrieve (rectangle with " << d.size() << " elements) time: " << time(NULL) - start << " seconds." << std::endl;
start = time(NULL);
@@ -154,7 +160,7 @@
std::cerr << " --> removal tests" << std::endl;
for(unsigned int j=0; j < find_count/1000; j++) {
q->remove(geometry::box<geometry::point_xy<double> >(search_positions[j], search_positions[j]));
-// std::cerr << "Elements: " << q->elements() << std::endl;
+ // std::cerr << "Elements: " << q->elements() << std::endl;
}
std::cerr << std::endl;
@@ -162,10 +168,22 @@
start = time(NULL);
for(unsigned int j=0; j < find_count/1000; j++) {
unsigned int i = q->find(search_positions[j]);
-// std::cerr << "Prev. Value: " << search_data[j] << std::endl;
+ // std::cerr << "Prev. Value: " << search_data[j] << std::endl;
BOOST_CHECK_EQUAL(i, 0u);
}
std::cerr << "Removal time: " << time(NULL) - start << " seconds." << std::endl;
+// std::cerr << " --> complete removal tests" << std::endl;
+// unsigned int total = q->elements();
+// for(unsigned int j=0; j < total; j++) {
+// // unsigned int e = q->elements();
+// q->remove(geometry::box<geometry::point_xy<double> >(points[j], points[j]));
+// // q->print();
+// // BOOST_CHECK_EQUAL(e, q->elements()+1);
+// // std::cerr << "Elements: " << e << std::endl;
+// }
+// std::cerr << std::endl;
+// 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