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

From: mariano.consoni_at_[hidden]
Date: 2008-06-09 15:43:42

Author: mconsoni
Date: 2008-06-09 15:43:41 EDT (Mon, 09 Jun 2008)
New Revision: 46281
URL: http://svn.boost.org/trac/boost/changeset/46281

Log:

- Initial structure for the rTree.
- Initial test to test-driven development for the rTree.

Added:
   sandbox/SOC/2008/spacial_indexing/boost/spatial_index/rtree.hpp   (contents, props changed)
   sandbox/SOC/2008/spacial_indexing/libs/spatial_index/test/simple_test_rtree.cpp   (contents, props changed)
Text files modified: 
   sandbox/SOC/2008/spacial_indexing/boost/spatial_index.hpp         |     1 +                                       
   sandbox/SOC/2008/spacial_indexing/libs/spatial_index/test/Jamfile |     1 +                                       
   2 files changed, 2 insertions(+), 0 deletions(-)

Modified: sandbox/SOC/2008/spacial_indexing/boost/spatial_index.hpp
==============================================================================
--- sandbox/SOC/2008/spacial_indexing/boost/spatial_index.hpp	(original)
+++ sandbox/SOC/2008/spacial_indexing/boost/spatial_index.hpp	2008-06-09 15:43:41 EDT (Mon, 09 Jun 2008)
@@ -10,6 +10,7 @@
 #include <boost/spatial_index/spatial_index.hpp>
 
 #include <boost/spatial_index/quadtree.hpp>
+#include <boost/spatial_index/rtree.hpp>
 
 #endif // BOOST_SPATIAL_INDEX_HPP
 

Added: sandbox/SOC/2008/spacial_indexing/boost/spatial_index/rtree.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/spacial_indexing/boost/spatial_index/rtree.hpp	2008-06-09 15:43:41 EDT (Mon, 09 Jun 2008)
@@ -0,0 +1,70 @@
+// Copyright 2008 Federico J. Fernandez.
+// Distributed under the Boost Software License, Version 1.0. (See
+// accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+
+#ifndef BOOST_SPATIAL_INDEX_RTREE_HPP
+#define BOOST_SPATIAL_INDEX_RTREE_HPP
+
+// #include "quadtree_node.hpp"
+
+// #include <boost/thread/xtime.hpp>
+
+namespace boost {
+namespace spatial_index {
+
+  template<typename Point, typename Value>
+  class rtree_node
+  {
+  };
+
+
+    template<typename Point, typename Value>
+    class rtree : public spatial_index<Point, Value>
+    {
+    private:
+      rtree_node<Point,Value> root;
+      unsigned int element_count;
+
+      // minimum number of points in each node
+      unsigned int m_;
+      // maximum number of points in each node
+      unsigned int M_;
+
+    public:
+      rtree(const unsigned int &m, const unsigned int &M) : element_count(0), m_(m), M_(M) {}
+      
+      virtual void insert(const Point &k, const Value &v)
+      {
+	element_count++;
+      }
+
+      virtual void bulk_insert(Value &v_begin, Value &v_end, std::vector<Point> &v)
+      {
+      }
+
+      virtual Value find(const Point &k)
+      {
+	return Value();
+      }
+
+
+      virtual std::deque<Value> find(const geometry::box<Point> &r)
+      {
+	std::deque<Value> result;
+	return result;
+      }
+
+      virtual unsigned int elements(void) { return element_count; }
+
+
+      virtual ~rtree() {}
+    };
+
+
+} // namespace spatial_index
+} // namespace boost
+
+#endif // BOOST_SPATIAL_INDEX_RTREE_HPP
+

Modified: sandbox/SOC/2008/spacial_indexing/libs/spatial_index/test/Jamfile
==============================================================================
--- sandbox/SOC/2008/spacial_indexing/libs/spatial_index/test/Jamfile	(original)
+++ sandbox/SOC/2008/spacial_indexing/libs/spatial_index/test/Jamfile	2008-06-09 15:43:41 EDT (Mon, 09 Jun 2008)
@@ -13,6 +13,7 @@
     ;
 
 run simple_test.cpp ;
+run simple_test_rtree.cpp ;
 run custom_point_test.cpp ;
 run random_test.cpp ;
 run performance_test.cpp ;

Added: sandbox/SOC/2008/spacial_indexing/libs/spatial_index/test/simple_test_rtree.cpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/spacial_indexing/libs/spatial_index/test/simple_test_rtree.cpp	2008-06-09 15:43:41 EDT (Mon, 09 Jun 2008)
@@ -0,0 +1,96 @@
+// Copyright 2008 Federico J. Fernandez.
+// Distributed under the Boost Software License, Version 1.0. (See
+// accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+
+#include <boost/spatial_index.hpp>
+
+#include <boost/test/included/test_exec_monitor.hpp>
+#include <boost/shared_ptr.hpp>
+
+#include <geometry/geometry.hpp>
+
+#include <vector>
+#include <string>
+
+int test_main(int, char* [])
+{
+	std::vector<std::string> data;
+	std::vector< geometry::point_xy<double> > points;	
+
+	data.push_back("test0");
+	data.push_back("test1");
+	data.push_back("test2");
+	data.push_back("test3");
+	data.push_back("test4");
+	data.push_back("test5");
+
+	points.push_back(geometry::point_xy<double>(1.0,1.0));
+	points.push_back(geometry::point_xy<double>(2.0,1.0));
+	points.push_back(geometry::point_xy<double>(5.0,5.0));
+	points.push_back(geometry::point_xy<double>(1.0,6.0));
+	points.push_back(geometry::point_xy<double>(9.0,9.0));
+	points.push_back(geometry::point_xy<double>(9.0,8.0));
+
+	geometry::box<geometry::point_xy<double> > b(geometry::point_xy<double>(0.0, 0.0), geometry::point_xy<double>(20.0, 20.0));
+
+	boost::shared_ptr< boost::spatial_index::spatial_index< geometry::point_xy<double> , std::vector<std::string>::iterator > > 
+	  q(new boost::spatial_index::rtree< geometry::point_xy<double> , std::vector<std::string>::iterator >(4, 8));
+
+// 	std::cerr << " --> bulk insert" << std::endl;
+// 	std::vector<std::string>::iterator b, e;
+// 	b = data.begin();
+// 	e = data.end();
+// 	q->bulk_insert(b,e, points);
+
+ 	std::vector<std::string>::iterator it = data.begin();
+
+ 	std::cerr << " --> insert" << std::endl;
+ 	q->insert(geometry::point_xy<double>(1.0,1.0), it++);
+ 	std::cerr << " --> insert" << std::endl;
+ 	q->insert(geometry::point_xy<double>(2.0,1.0), it++);
+ 	std::cerr << " --> insert" << std::endl;
+ 	q->insert(geometry::point_xy<double>(5.0,5.0), it++);
+ 	std::cerr << " --> insert" << std::endl;
+ 	q->insert(geometry::point_xy<double>(1.0,6.0), it++);
+ 	std::cerr << " --> insert" << std::endl;
+ 	q->insert(geometry::point_xy<double>(9.0,9.0), it++);
+ 	std::cerr << " --> insert" << std::endl;
+ 	q->insert(geometry::point_xy<double>(9.0,8.0), it++);
+
+
+// 	std::vector<std::string>::iterator it1;
+
+// 	std::cerr << " --> find" << std::endl;
+// 	it1 = q->find(geometry::point_xy<double>(9.0,9.0));
+// 	BOOST_CHECK_EQUAL(*it1, "test4");
+// 	std::cout << "  " << *it1 << std::endl;
+
+// 	std::cerr << " --> find" << std::endl;
+// 	it1 = q->find(geometry::point_xy<double>(5.0,5.0));
+// 	BOOST_CHECK_EQUAL(*it1, "test2");
+// 	std::cout << "  " << *it1 << std::endl;
+
+// 	// expected result
+// 	std::vector<std::string> res;
+// 	res.push_back("test0");
+// 	res.push_back("test1");
+// 	res.push_back("test2");
+
+// 	std::cerr << "Elements: " << q->elements() << std::endl;
+// 	BOOST_CHECK_EQUAL(q->elements(), 6u);
+
+// 	std::cerr << " --> find rectangle" << std::endl;
+// 	geometry::box<geometry::point_xy<double> > query_box(geometry::point_xy<double>(0.0, 0.0), geometry::point_xy<double>(5.0, 5.0));
+// 	std::deque< std::vector<std::string>::iterator > d = q->find(query_box);
+// 	BOOST_CHECK_EQUAL(d.size(), 3u);
+// 	unsigned int i = 0;
+// 	for(std::deque< std::vector<std::string>::iterator >::const_iterator dit = d.begin(); dit != d.end(); ++dit) {
+// 		std::cerr << "Value: " << *(*dit) << std::endl;
+// 		BOOST_CHECK_EQUAL(*(*dit), res[i++]);
+// 	}
+
+
+	return 0;
+};