From: mariano.consoni_at_[hidden]
Date: 2008-06-16 10:39:38
Author: mconsoni
Date: 2008-06-16 10:39:38 EDT (Mon, 16 Jun 2008)
New Revision: 46425
URL: http://svn.boost.org/trac/boost/changeset/46425
Log:
- More on remove.
Text files modified:
sandbox/SOC/2008/spacial_indexing/boost/spatial_index/rtree.hpp | 26 ++++++++++++++++++++++++--
sandbox/SOC/2008/spacial_indexing/boost/spatial_index/rtree_leaf.hpp | 16 ++++++++++++++++
sandbox/SOC/2008/spacial_indexing/boost/spatial_index/rtree_node.hpp | 15 +++++++++++++++
sandbox/SOC/2008/spacial_indexing/boost/spatial_index/spatial_index.hpp | 2 +-
sandbox/SOC/2008/spacial_indexing/libs/spatial_index/test/simple_test_rtree.cpp | 6 ++++++
5 files changed, 62 insertions(+), 3 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-16 10:39:38 EDT (Mon, 16 Jun 2008)
@@ -44,9 +44,31 @@
/// remove the element with key 'k'
/// TODO: implement
- virtual void remove(const Point &k)
+ virtual void remove(const geometry::box<Point> &k)
{
- std::cerr << "Not implemented yet." << std::endl;
+ try {
+ boost::shared_ptr<rtree_node<Point, Value> > l(choose_leaf(k));
+
+ l->remove(k);
+
+ condense_tree(l);
+
+ // if the root has only one child, make it the root
+ if(root_->elements() == 1) {
+ root_ = root_->first_element();
+ root_->set_root();
+ }
+
+ element_count--;
+ } catch(std::logic_error &e) {
+ // not found
+ return;
+ }
+ }
+
+ void condense_tree(const boost::shared_ptr<rtree_node<Point,Value> > &l)
+ {
+ std::cerr << "Condensing tree." << std::endl;
}
virtual void print(void) const
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-16 10:39:38 EDT (Mon, 16 Jun 2008)
@@ -97,6 +97,22 @@
virtual Value get_value(const unsigned int i) const { return nodes_[i].second; }
+
+ /// remove value with key 'k' in this leaf
+ virtual void remove(const geometry::box<Point> &k)
+ {
+
+ for(typename leaves_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;
+ }
+ }
+
+ }
+
+
virtual std::vector< geometry::box<Point> > get_boxes(void) const
{
std::vector< geometry::box<Point> > r;
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-16 10:39:38 EDT (Mon, 16 Jun 2008)
@@ -47,6 +47,15 @@
return nodes_.size();
}
+ /// first element, to replace root in case of condensing
+ boost::shared_ptr<rtree_node<Point, Value> > first_element(void) const
+ {
+ if(nodes_.size() == 0) {
+ throw std::logic_error("first_element in empty node");
+ }
+ return nodes_.begin()->second;
+ }
+
/// true if it is a leaf node
virtual bool is_leaf(void) const { return false; }
@@ -128,6 +137,12 @@
std::cerr << "adjust_node: node not found." << std::endl;
}
+ virtual void remove(const geometry::box<Point> &k)
+ {
+ // TODO
+ }
+
+
/// replace the node in the nodes_ vector and recompute the box
void replace_node(const boost::shared_ptr<rtree_node<Point, Value> > &l, boost::shared_ptr<rtree_node<Point, Value> > &new_l)
{
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-16 10:39:38 EDT (Mon, 16 Jun 2008)
@@ -30,7 +30,7 @@
virtual void insert(const geometry::box<Point> &e, const Value &v) = 0;
/// remove data with key 'k'
- virtual void remove(const Point &k) = 0;
+ virtual void remove(const geometry::box<Point> &k) = 0;
/// bulk insert data from values
virtual void bulk_insert(std::vector<Value> &values, std::vector<Point> &points) = 0;
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-16 10:39:38 EDT (Mon, 16 Jun 2008)
@@ -136,5 +136,11 @@
std::cout << "Value: " << v << std::endl;
}
+ // 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)));
+
+ q->print();
+
return 0;
};