From: mariano.consoni_at_[hidden]
Date: 2008-06-24 17:25:03
Author: mconsoni
Date: 2008-06-24 17:25:03 EDT (Tue, 24 Jun 2008)
New Revision: 46663
URL: http://svn.boost.org/trac/boost/changeset/46663
Log:
- Complete removal test working.
Text files modified:
sandbox/SOC/2008/spacial_indexing/boost/spatial_index/quadtree.hpp | 16 ++++-
sandbox/SOC/2008/spacial_indexing/boost/spatial_index/quadtree_node.hpp | 107 +++++++++++++++++++++++++++++++++++++--
sandbox/SOC/2008/spacial_indexing/boost/spatial_index/rtree.hpp | 4
sandbox/SOC/2008/spacial_indexing/boost/spatial_index/spatial_index.hpp | 4
sandbox/SOC/2008/spacial_indexing/libs/spatial_index/test/performance_test.cpp | 44 ++++++++++-----
5 files changed, 144 insertions(+), 31 deletions(-)
Modified: sandbox/SOC/2008/spacial_indexing/boost/spatial_index/quadtree.hpp
==============================================================================
--- sandbox/SOC/2008/spacial_indexing/boost/spatial_index/quadtree.hpp (original)
+++ sandbox/SOC/2008/spacial_indexing/boost/spatial_index/quadtree.hpp 2008-06-24 17:25:03 EDT (Tue, 24 Jun 2008)
@@ -30,15 +30,14 @@
: root(r, 1), element_count(0), node_size_(1) {}
/// remove the element with key 'k'
- /// TODO: implement
virtual void remove(const Point &k)
{
root.remove(k);
+ // root.clean();
element_count--;
}
/// remove data with key 'k'
- /// TODO: implement
virtual void remove(const geometry::box<Point> &k)
{
std::cerr << "Boxes not implemented in quadtrees." << std::endl;
@@ -51,9 +50,12 @@
root.insert(k, v);
}
- virtual void print(void) const
+ virtual void print(void)
{
- std::cerr << "Not implemented." << std::endl;
+ std::cerr << "=================================" << std::endl;
+ std::cerr << "Elements: " << elements() << std::endl;
+ root.print();
+ std::cerr << "=================================" << std::endl;
}
/// insert data with envelope 'e' with key 'k'
@@ -102,8 +104,12 @@
return result;
}
+ void clean(void)
+ {
+ root.clean();
+ }
- virtual unsigned int elements(void) { return element_count; }
+ virtual unsigned int elements(void) const { return element_count; }
virtual ~quadtree() {}
};
Modified: sandbox/SOC/2008/spacial_indexing/boost/spatial_index/quadtree_node.hpp
==============================================================================
--- sandbox/SOC/2008/spacial_indexing/boost/spatial_index/quadtree_node.hpp (original)
+++ sandbox/SOC/2008/spacial_indexing/boost/spatial_index/quadtree_node.hpp 2008-06-24 17:25:03 EDT (Tue, 24 Jun 2008)
@@ -78,14 +78,51 @@
// "min_x: " << min_x << " min_y: " << min_y << " max_x: " << max_x << " max_y " << max_y << std::endl;
}
- void remove(const Point &k)
+
+ void clean(void)
{
- typename std::map<Point, Value>::iterator it = m_.find(k);
- if(it != m_.end()) {
- m_.erase(it);
- return;
+ if(nw_ != boost::shared_ptr<quadtree_node>()) {
+ if(nw_->empty_leaf()) {
+ nw_ = boost::shared_ptr<quadtree_node>();
+ } else {
+ nw_->clean();
+ }
+ }
+
+ if(sw_ != boost::shared_ptr<quadtree_node>()) {
+ if(sw_->empty_leaf()) {
+ sw_ = boost::shared_ptr<quadtree_node>();
+ } else {
+ sw_->clean();
+ }
+ }
+
+ if(se_ != boost::shared_ptr<quadtree_node>()) {
+ if(se_->empty_leaf()) {
+ se_ = boost::shared_ptr<quadtree_node>();
+ } else {
+ se_->clean();
+ }
+ }
+
+ if(ne_ != boost::shared_ptr<quadtree_node>()) {
+ if(ne_->empty_leaf()) {
+ ne_ = boost::shared_ptr<quadtree_node>();
+ } else {
+ ne_->clean();
}
- recursive_remove(k);
+ }
+
+ }
+
+ bool empty_leaf(void) const
+ {
+ return (m_.size() == 0) &&
+ (ne_ == boost::shared_ptr<quadtree_node>()) &&
+ (se_ == boost::shared_ptr<quadtree_node>()) &&
+ (nw_ == boost::shared_ptr<quadtree_node>()) &&
+ (sw_ == boost::shared_ptr<quadtree_node>())
+ ;
}
void insert(const Point &k, const Value &v)
@@ -228,6 +265,16 @@
return Value();
}
+ void remove(const Point &k)
+ {
+ typename std::map<Point, Value>::iterator it = m_.find(k);
+ if(it != m_.end()) {
+ m_.erase(it);
+ return;
+ }
+ recursive_remove(k);
+ }
+
void recursive_remove(const Point &k)
{
// std::cerr << "Recursive_remove" << std::endl;
@@ -241,9 +288,13 @@
geometry::box<Point> ne_box, sw_box, se_box, nw_box;
divide_quadrants(ne_box, sw_box, se_box, nw_box);
+
if(geometry::within(k, ne_box)) {
if(ne_ != boost::shared_ptr<quadtree_node>()) {
ne_->remove(k);
+ if(ne_->empty_leaf()) {
+ ne_ = boost::shared_ptr<quadtree_node>();
+ }
return;
} else {
throw std::logic_error("Not found");
@@ -252,6 +303,9 @@
if(geometry::within(k, se_box)) {
if(se_ != boost::shared_ptr<quadtree_node>()) {
se_->remove(k);
+ if(se_->empty_leaf()) {
+ se_ = boost::shared_ptr<quadtree_node>();
+ }
return;
} else {
throw std::logic_error("Not found");
@@ -260,6 +314,9 @@
if(geometry::within(k, nw_box)) {
if(nw_ != boost::shared_ptr<quadtree_node>()) {
nw_->remove(k);
+ if(nw_->empty_leaf()) {
+ nw_ = boost::shared_ptr<quadtree_node>();
+ }
return;
} else {
throw std::logic_error("Not found");
@@ -268,6 +325,9 @@
if(geometry::within(k, sw_box)) {
if(sw_ != boost::shared_ptr<quadtree_node>()) {
sw_->remove(k);
+ if(sw_->empty_leaf()) {
+ sw_ = boost::shared_ptr<quadtree_node>();
+ }
return;
} else {
throw std::logic_error("Not found");
@@ -276,6 +336,41 @@
}
+ void print(void) const
+ {
+ std::cerr << "--------------------------------------" << std::endl;
+ std::cerr << " [ ";
+ for(typename std::map<Point,Value>::const_iterator it = m_.begin(); it != m_.end(); ++it) {
+ std::cerr << it->second << " ";
+ }
+ std::cerr << " ] " << std::endl;;
+
+ if(sw_.get() != 0) {
+ sw_->print();
+ } else {
+ std::cerr << "SW not defined" << std::endl;
+ }
+
+ if(nw_.get() != 0) {
+ nw_->print();
+ } else {
+ std::cerr << "NW not defined" << std::endl;
+ }
+
+ if(se_.get() != 0) {
+ se_->print();
+ } else {
+ std::cerr << "SE not defined" << std::endl;
+ }
+
+ if(ne_.get() != 0) {
+ ne_->print();
+ } else {
+ std::cerr << "NE not defined" << std::endl;
+ }
+ std::cerr << "--------------------------------------" << std::endl;
+ }
+
};
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 17:25:03 EDT (Tue, 24 Jun 2008)
@@ -111,9 +111,9 @@
}
}
- virtual unsigned int elements(void) { return element_count_; }
+ virtual unsigned int elements(void) const { return element_count_; }
- virtual void print(void) const
+ virtual void print(void)
{
std::cerr << "===================================" << std::endl;
std::cerr << " Min/Max: " << m_ << " / " << M_ << std::endl;
Modified: sandbox/SOC/2008/spacial_indexing/boost/spatial_index/spatial_index.hpp
==============================================================================
--- sandbox/SOC/2008/spacial_indexing/boost/spatial_index/spatial_index.hpp (original)
+++ sandbox/SOC/2008/spacial_indexing/boost/spatial_index/spatial_index.hpp 2008-06-24 17:25:03 EDT (Tue, 24 Jun 2008)
@@ -46,10 +46,10 @@
virtual std::deque<Value> find(const geometry::box<Point> &r) = 0;
/// element count in the index
- virtual unsigned int elements(void) = 0;
+ virtual unsigned int elements(void) const = 0;
/// debug print
- virtual void print(void) const = 0;
+ virtual void print(void) = 0;
/// destructor
virtual ~spatial_index(void) {}
Modified: sandbox/SOC/2008/spacial_indexing/libs/spatial_index/test/performance_test.cpp
==============================================================================
--- sandbox/SOC/2008/spacial_indexing/libs/spatial_index/test/performance_test.cpp (original)
+++ sandbox/SOC/2008/spacial_indexing/libs/spatial_index/test/performance_test.cpp 2008-06-24 17:25:03 EDT (Tue, 24 Jun 2008)
@@ -151,22 +151,34 @@
std::cerr << "Retrieve time: " << time(NULL) - start << " seconds." << std::endl;
- std::cerr << " --> removal tests" << std::endl;
- for(unsigned int j=0; j < find_count/1000; j++) {
- std::cerr << "Removal: " << j << std::endl;
- q->remove(search_positions[j]);
-// std::cerr << "Elements: " << q->elements() << std::endl;
- }
- std::cerr << std::endl;
-
- std::cerr << " --> requery test" << std::endl;
- 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;
- BOOST_CHECK_EQUAL(i, 0u);
- }
- std::cerr << "Removal time: " << time(NULL) - start << " seconds." << std::endl;
+ std::cerr << " --> removal tests" << std::endl;
+ for(unsigned int j=0; j < find_count/1000; j++) {
+ std::cerr << "Removal: " << j << std::endl;
+ q->remove(search_positions[j]);
+ // std::cerr << "Elements: " << q->elements() << std::endl;
+ }
+ std::cerr << std::endl;
+
+ std::cerr << " --> requery test" << std::endl;
+ 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;
+ 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(points[total-j-1]);
+// BOOST_CHECK_EQUAL(e, q->elements()+1);
+// // std::cerr << "Elements: " << e << std::endl;
+// }
+// q->print();
+// std::cerr << "Elements: " << q->elements() << std::endl;
+ // std::cerr << std::endl;
return 0;
}