From: mariano.consoni_at_[hidden]
Date: 2008-06-20 08:52:34
Author: mconsoni
Date: 2008-06-20 08:52:33 EDT (Fri, 20 Jun 2008)
New Revision: 46554
URL: http://svn.boost.org/trac/boost/changeset/46554
Log:
- Remove test working.
- Removed debug cerr.
- Random test for rTree.
Added:
sandbox/SOC/2008/spacial_indexing/libs/spatial_index/test/random_test_rtree.cpp (contents, props changed)
Text files modified:
sandbox/SOC/2008/spacial_indexing/boost/spatial_index/rtree.hpp | 12 ++++++------
sandbox/SOC/2008/spacial_indexing/boost/spatial_index/rtree_leaf.hpp | 4 +---
sandbox/SOC/2008/spacial_indexing/boost/spatial_index/rtree_node.hpp | 2 +-
sandbox/SOC/2008/spacial_indexing/libs/spatial_index/test/Jamfile | 1 +
sandbox/SOC/2008/spacial_indexing/libs/spatial_index/test/performance_test_rtree.cpp | 25 +++++++++++++++++--------
5 files changed, 26 insertions(+), 18 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-20 08:52:33 EDT (Fri, 20 Jun 2008)
@@ -48,7 +48,7 @@
l->remove(k);
if(l->elements() < m_) {
- std::cerr << "Few elements in Node." << std::endl;
+// std::cerr << "Few elements in Node." << std::endl;
q_leaves = l->get_leaves();
@@ -71,7 +71,7 @@
for(typename std::vector<std::pair<geometry::box<Point>, Value> >::const_iterator it = s.begin(); it != s.end(); ++it) {
- std::cerr << "Inserting " << it->second << std::endl;
+// std::cerr << "Inserting " << it->second << std::endl;
insert(it->first, it->second);
}
@@ -81,7 +81,7 @@
root_->set_root();
}
- std::cerr << "Reinserting leaves " << q_leaves.size() << std::endl;
+// std::cerr << "Reinserting leaves " << q_leaves.size() << std::endl;
for(typename rtree_leaf<Point,Value>::leaves_map::const_iterator it = q_leaves.begin(); it != q_leaves.end(); ++it) {
insert(it->first, it->second);
@@ -203,7 +203,7 @@
void condense_tree(const boost::shared_ptr<rtree_node<Point,Value> > &l, typename rtree_node<Point,Value>::node_map &q_nodes)
{
- std::cerr << "Condensing tree." << std::endl;
+// std::cerr << "Condensing tree." << std::endl;
if(l->is_root()) {
// if it's the root we are done
@@ -219,10 +219,10 @@
return;
}
- std::cerr << "condense_node: underfull node (" << parent.get() << ")" << std::endl;
+// std::cerr << "condense_node: underfull node (" << parent.get() << ")" << std::endl;
typename rtree_node<Point,Value>::node_map this_nodes = parent->get_nodes();
- std::cerr << "Storing nodes (" << this_nodes.size() << ")" << std::endl;
+// std::cerr << "Storing nodes (" << this_nodes.size() << ")" << std::endl;
for(typename rtree_node<Point,Value>::node_map::const_iterator it = this_nodes.begin(); it != this_nodes.end(); ++it) {
q_nodes.push_back(*it);
}
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-20 08:52:33 EDT (Fri, 20 Jun 2008)
@@ -106,14 +106,12 @@
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;
+// std::cerr << "Erasing node." << std::endl;
nodes_.erase(it);
return;
}
}
std::cerr << "remove: node not found" << std::endl;
- print();
- std::cerr << "remove: node not found" << std::endl;
}
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-20 08:52:33 EDT (Fri, 20 Jun 2008)
@@ -146,7 +146,7 @@
{
for(typename node_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;
+// std::cerr << "Erasing node." << std::endl;
nodes_.erase(it);
return;
}
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-20 08:52:33 EDT (Fri, 20 Jun 2008)
@@ -16,5 +16,6 @@
run simple_test_rtree.cpp ;
run custom_point_test.cpp ;
run random_test.cpp ;
+run random_test_rtree.cpp ;
run performance_test.cpp ;
run performance_test_rtree.cpp ;
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-20 08:52:33 EDT (Fri, 20 Jun 2008)
@@ -84,8 +84,8 @@
std::vector< geometry::point_xy<double> > points = read_data();
// -- wait to check memory
-// std::cerr << "check memory --> After Reading Data." << std::endl;
-// sleep(5);
+ // std::cerr << "check memory --> After Reading Data." << std::endl;
+ // sleep(5);
// -- wait to check memory
// start time
@@ -117,8 +117,8 @@
std::cerr << "Insertion time: " << time(NULL) - start << " seconds." << std::endl;
// -- wait to check memory
-// std::cerr << "check memory --> After Building Index." << std::endl;
-// sleep(5);
+ // std::cerr << "check memory --> After Building Index." << std::endl;
+ // sleep(5);
// -- wait to check memory
// search
@@ -152,11 +152,20 @@
std::cerr << " --> removal tests" << std::endl;
+ for(unsigned int j=0; j < find_count/1000; j++) {
+ q->remove(geometry::box<geometry::point_xy<double> >(search_positions[j], 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 << "Retrieve time: " << time(NULL) - start << " seconds." << std::endl;
return 0;
}
-
-
-
Added: sandbox/SOC/2008/spacial_indexing/libs/spatial_index/test/random_test_rtree.cpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/spacial_indexing/libs/spatial_index/test/random_test_rtree.cpp 2008-06-20 08:52:33 EDT (Fri, 20 Jun 2008)
@@ -0,0 +1,98 @@
+// 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 <vector>
+#include <string>
+
+
+#include <sys/time.h>
+
+#define MAX_X 2000.0
+#define MAX_Y 2000.0
+
+
+double drandom(unsigned int upper_bound)
+{
+ double r; /* random value in range [0,1) */
+ long int M; /* user supplied upper boundary */
+
+ struct timeval tv;
+ struct timezone tz;
+ gettimeofday(&tv, &tz);
+ srand(tv.tv_usec);
+
+ M = upper_bound; /* Choose M. Upper bound */
+ r = ( (double)rand() / ((double)(RAND_MAX)+(double)(1)) );
+
+ return r * M;
+}
+
+
+int test_main(int, char* [])
+{
+ // data and indexed points
+ std::vector<unsigned int> ids;
+ std::vector<geometry::point_xy<double> > points;
+
+ // plane
+ geometry::box<geometry::point_xy<double> > plane(geometry::point_xy<double>(0.0, 0.0), geometry::point_xy<double>(MAX_X, MAX_Y));
+
+ // number of points
+ const unsigned int points_count = 500;
+
+ // number of points to find on the search phase
+ const unsigned int find_count = 50;
+
+ boost::shared_ptr< boost::spatial_index::spatial_index< geometry::point_xy<double> , unsigned int > >
+ q(new boost::spatial_index::rtree<geometry::point_xy<double>, unsigned int>(plane, 8, 4));
+
+ // generate random data
+ for(unsigned int i = 0; i < points_count; i++) {
+ double x = drandom((int) MAX_X);
+ double y = drandom((int) MAX_Y);
+
+ ids.push_back(i);
+ points.push_back(geometry::point_xy<double>(x, y));
+
+ // std::cerr << "insert " << i << " -> (" << x << ", " << y << ")" << std::endl;
+ }
+
+ // insert data
+ std::cerr << " --> bulk insert" << std::endl;
+ // std::vector<unsigned int>::iterator b, e;
+ // b = ids.begin();
+ // e = ids.end();
+ q->bulk_insert(ids, points);
+
+ // search
+ std::vector<geometry::point_xy<double> > search_positions;
+ std::vector<unsigned int> search_data;
+
+ // compute random positions to do the searches, store the data
+ for(unsigned int j=0; j < find_count; j++) {
+ unsigned int pos = (int) drandom(points_count);
+ search_positions.push_back(points[pos]);
+ search_data.push_back(pos);
+ }
+
+ // search data and compare
+ for(unsigned int j=0; j < find_count; j++) {
+ unsigned int i = q->find(search_positions[j]);
+ std::cout << search_data[j]
+ << " - found in (" << geometry::get<0>(search_positions[j]) << "," << geometry::get<1>(search_positions[j])
+ << ") --> " << i << std::endl;
+
+ // check if the retrieved data is equal to the stored data
+ BOOST_CHECK_EQUAL(i, search_data[j]);
+ }
+
+ return 0;
+}