[Boost-commit] svn:boost r46425 - in sandbox/SOC/2008/spacial_indexing: boost/spatial_index libs/spatial_index/test

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;
 };