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

From: mariano.consoni_at_[hidden]
Date: 2008-06-23 07:08:46

Author: mconsoni
Date: 2008-06-23 07:08:44 EDT (Mon, 23 Jun 2008)
New Revision: 46623
URL: http://svn.boost.org/trac/boost/changeset/46623

Log:

- Remove algorithm for quadtree and tests.

Text files modified: 
   sandbox/SOC/2008/spacial_indexing/boost/spatial_index/quadtree.hpp                   |    29 ++++----                                
   sandbox/SOC/2008/spacial_indexing/boost/spatial_index/quadtree_node.hpp              |   126 ++++++++++++++++++++++++++++----------- 
   sandbox/SOC/2008/spacial_indexing/boost/spatial_index/rtree.hpp                      |     6 +                                       
   sandbox/SOC/2008/spacial_indexing/boost/spatial_index/spatial_index.hpp              |     3                                         
   sandbox/SOC/2008/spacial_indexing/libs/spatial_index/test/performance_test.cpp       |    18 +++++                                   
   sandbox/SOC/2008/spacial_indexing/libs/spatial_index/test/performance_test_rtree.cpp |     2                                         
   6 files changed, 134 insertions(+), 50 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-23 07:08:44 EDT (Mon, 23 Jun 2008)
@@ -19,11 +19,11 @@
 class quadtree : public spatial_index<Point, Value>
 {
 private:
-	quadtree_node<Point,Value> root;
-	unsigned int element_count;
+  quadtree_node<Point,Value> root;
+  unsigned int element_count;
 
-	// number of points in each node
-	unsigned int node_size_;
+  // number of points in each node
+  unsigned int node_size_;
 
 public:
   quadtree(const geometry::box<Point> &r)
@@ -33,14 +33,15 @@
   /// TODO: implement
   virtual void remove(const Point &k)
   {
-    std::cerr << "Not implemented yet." << std::endl;
+    root.remove(k);
+    element_count--;
   }
 
   /// remove data with key 'k'
   /// TODO: implement
   virtual void remove(const geometry::box<Point> &k)
   {
-    std::cerr << "Not implemented yet." << std::endl;
+    std::cerr << "Boxes not implemented in quadtrees." << std::endl;
   }
 
           
@@ -94,17 +95,17 @@
     return root.find(k);
   }
 
- 	virtual std::deque<Value> find(const geometry::box<Point> &r)
-	{
-		std::deque<Value> result;
-		root.find(result, r);
-		return result;
-	}
+  virtual std::deque<Value> find(const geometry::box<Point> &r)
+  {
+    std::deque<Value> result;
+    root.find(result, r);
+    return result;
+  }
 
 
-	virtual unsigned int elements(void) { return element_count; }
+  virtual unsigned int elements(void) { return element_count; }
         
-	virtual ~quadtree() {}
+  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-23 07:08:44 EDT (Mon, 23 Jun 2008)
@@ -78,6 +78,15 @@
     // "min_x: " << min_x << " min_y: " << min_y << " max_x: " << max_x << " max_y " << max_y << std::endl;
   }
 
+  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 insert(const Point &k, const Value &v)
   {
@@ -140,10 +149,11 @@
         // std::cerr << "Not Inside" << std::endl;
         return;
       }
+
       // std::cerr << "Inside" << std::endl;
 
       for(typename std::map<Point,Value>::const_iterator it = m_.begin(); it != m_.end(); ++it) {
-	std::cerr << "Checking: (" << geometry::get<0>(it->first) << "," << geometry::get<1>(it->first) << ")" << std::endl;
+// 	std::cerr << "Checking: (" << geometry::get<0>(it->first) << "," << geometry::get<1>(it->first) << ")" << std::endl;
         if(geometry::get<0>(it->first) >= geometry::get<0>(r.min()) && geometry::get<0>(it->first) <= geometry::get<0>(r.max()) && 
            geometry::get<1>(it->first) >= geometry::get<1>(r.min()) && geometry::get<1>(it->first) <= geometry::get<1>(r.max())) {
           result.push_back(it->second);
@@ -170,56 +180,102 @@
 
   Value find(const Point &k)
   {
-    if(m_.size() == 0) {
-      return Value();
-    } else {
-      // std::cerr << "compare: " << k_.first << " with " << k.first;
-      // std::cerr << " " << k_.second << " with " << k.second << std::endl;
       typename std::map<Point, Value>::const_iterator it = m_.find(k);
       if(it != m_.end()) {
-	// std::cerr << "ok" << std::endl;
         return it->second;
       }
+      return recursive_search(k);
+  }
 
 
-      // IMP: maybe this could be done only one time at node creation
-      geometry::box<Point> ne_box, sw_box, se_box, nw_box;
-      divide_quadrants(ne_box, sw_box, se_box, nw_box);
+  Value recursive_search(const Point &k)
+  {
+    // IMP: maybe this could be done only one time at node creation
+    // but it will consume more memory...
 
-      // TODO: replace with algorithm
-      if(geometry::within(k, ne_box)) {
-	if(ne_ != boost::shared_ptr<quadtree_node>()) {
-	  return ne_->find(k);
-	} else {
-	  return Value();
-	}
+    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>()) {
+	return ne_->find(k);
+      } else {
+	return Value();
       }
-      if(geometry::within(k, se_box)) {
-	if(se_ != boost::shared_ptr<quadtree_node>()) {
-	  return se_->find(k);
-	} else {
-	  return Value();
-	}
+    }
+    if(geometry::within(k, se_box)) {
+      if(se_ != boost::shared_ptr<quadtree_node>()) {
+	return se_->find(k);
+      } else {
+	return Value();
       }
-      if(geometry::within(k, nw_box)) {
-	if(nw_ != boost::shared_ptr<quadtree_node>()) {
-	  return nw_->find(k);
-	} else {
-	  return Value();
-	}
+    }
+    if(geometry::within(k, nw_box)) {
+      if(nw_ != boost::shared_ptr<quadtree_node>()) {
+	return nw_->find(k);
+      } else {
+	return Value();
       }
-      if(geometry::within(k, sw_box)) {
-	if(sw_ != boost::shared_ptr<quadtree_node>()) {
-	  return sw_->find(k);
-	} else {
-	  return Value();
-	}
+    }
+    if(geometry::within(k, sw_box)) {
+      if(sw_ != boost::shared_ptr<quadtree_node>()) {
+	return sw_->find(k);
+      } else {
+	return Value();
       }
     }
     // never reached
     return Value();
   }
 
+  void recursive_remove(const Point &k)
+  {
+//     std::cerr << "Recursive_remove" << std::endl;
+
+//     std::cerr << "Checking: (" << geometry::get<0>(k) << "," << geometry::get<1>(k) << ")" << std::endl;
+//     std::cerr << "in : (" << geometry::get<0>(bounding_rectangle_.min()) << "," << geometry::get<1>(bounding_rectangle_.min()) << ") x ";
+//     std::cerr << "(" << geometry::get<0>(bounding_rectangle_.max()) << "," << geometry::get<1>(bounding_rectangle_.max()) << ")" << std::endl;
+
+    // IMP: maybe this could be done only one time at node creation
+    // but it will consume more memory...
+    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);
+	return;
+      } else {
+	throw std::logic_error("Not found");
+      }
+    }
+    if(geometry::within(k, se_box)) {
+      if(se_ != boost::shared_ptr<quadtree_node>()) {
+	se_->remove(k);
+	return;
+      } else {
+	throw std::logic_error("Not found");
+      }
+    }
+    if(geometry::within(k, nw_box)) {
+      if(nw_ != boost::shared_ptr<quadtree_node>()) {
+	nw_->remove(k);
+	return;
+      } else {
+	throw std::logic_error("Not found");
+      }
+    }
+    if(geometry::within(k, sw_box)) {
+      if(sw_ != boost::shared_ptr<quadtree_node>()) {
+	sw_->remove(k);
+	return;
+      } else {
+	throw std::logic_error("Not found");
+      }
+    }
+  }
+
+
 };
 
 

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-23 07:08:44 EDT (Mon, 23 Jun 2008)
@@ -39,6 +39,12 @@
     }
 
     /// remove the element with key 'k'
+    virtual void remove(const Point &k)
+    {
+      this->remove(geometry::box<Point>(k, k));
+    }
+
+    /// remove the element with key 'k'
     virtual void remove(const geometry::box<Point> &k)
     {
       try {

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-23 07:08:44 EDT (Mon, 23 Jun 2008)
@@ -30,6 +30,9 @@
   virtual void insert(const geometry::box<Point> &e, const Value &v) = 0;
 
   /// remove data with key 'k'
+  virtual void remove(const Point &k) = 0;
+
+  /// remove data with key 'k'
   virtual void remove(const geometry::box<Point> &k) = 0;
         
   /// bulk insert data from values

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-23 07:08:44 EDT (Mon, 23 Jun 2008)
@@ -150,6 +150,24 @@
       }
       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;
+
       return 0;
 }
 

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-23 07:08:44 EDT (Mon, 23 Jun 2008)
@@ -165,7 +165,7 @@
 // 	std::cerr << "Prev. Value: " << search_data[j] << std::endl;
         BOOST_CHECK_EQUAL(i, 0u);
       }
-      std::cerr << "Retrieve time: " << time(NULL) - start << " seconds." << std::endl;
+      std::cerr << "Removal time: " << time(NULL) - start << " seconds." << std::endl;
 
       return 0;
 }