|
|
Boost-Commit : |
From: mariano.consoni_at_[hidden]
Date: 2008-07-08 13:53:49
Author: mconsoni
Date: 2008-07-08 13:53:49 EDT (Tue, 08 Jul 2008)
New Revision: 47241
URL: http://svn.boost.org/trac/boost/changeset/47241
Log:
- removed the initial plane because it wasn't needed.
- simplified is_root method.
Text files modified:
sandbox/SOC/2008/spacial_indexing/boost/spatial_index/rtree.hpp | 60 +++++++++++----------------------------
sandbox/SOC/2008/spacial_indexing/boost/spatial_index/rtree_node.hpp | 8 ----
sandbox/SOC/2008/spacial_indexing/libs/spatial_index/test/performance_test_rtree.cpp | 5 --
sandbox/SOC/2008/spacial_indexing/libs/spatial_index/test/random_test_rtree.cpp | 5 --
sandbox/SOC/2008/spacial_indexing/libs/spatial_index/test/simple_test_rtree.cpp | 7 ++--
5 files changed, 23 insertions(+), 62 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-07-08 13:53:49 EDT (Tue, 08 Jul 2008)
@@ -24,21 +24,19 @@
/// cached number of elements
unsigned int element_count_;
- // minimum number of elements per node
+ /// minimum number of elements per node
unsigned int m_;
- // maximum number of elements per node
+ /// maximum number of elements per node
unsigned int M_;
- // tree root
+ /// tree root
boost::shared_ptr< rtree_node<Point,Value> > root_;
public:
- rtree(const geometry::box<Point> &initial_box, const unsigned int &M, const unsigned int &m)
+ rtree(const unsigned int &M, const unsigned int &m)
: element_count_(0), m_(m), M_(M), root_(new rtree_node<Point, Value>(boost::shared_ptr< rtree_node<Point,Value> >(), 1))
{
root_->set_root();
- boost::shared_ptr< rtree_leaf<Point, Value> > new_leaf(new rtree_leaf<Point, Value>(root_));
- root_->add_leaf_node(initial_box, new_leaf);
}
/// remove the element with key 'k'
@@ -127,19 +125,14 @@
this->insert(geometry::box<Point>(k,k), v);
}
+
void insert(const geometry::box<Point> &e, const Value &v)
{
element_count_++;
boost::shared_ptr<rtree_node<Point, Value> > l(choose_leaf(e));
-// std::cerr << "Leaf: " << std::endl;
-// l->print();
-// std::cerr << std::endl;
-
if(l->elements() >= M_) {
-// std::cerr << "Node full. Split." << std::endl;
-
l->insert(e, v);
// split!
@@ -147,33 +140,14 @@
boost::shared_ptr< rtree_node<Point, Value> > n2(new rtree_leaf<Point,Value>(l->get_parent()));
split_node(l, n1, n2);
-// std::cerr << std::endl;
-// std::cerr << std::endl;
-// std::cerr << std::endl;
-// std::cerr << "Node splited." << std::endl;
-
-// std::cerr << "ORIG" << std::endl;
-// l->print();
-
-// std::cerr << "N1" << std::endl;
-// n1->print();
-// std::cerr << "N2" << std::endl;
-// n2->print();
-
-// std::cerr << "L parent." << std::endl;
-// l->get_parent()->print();
-
adjust_tree(l, n1, n2);
-
-
} else {
-// std::cerr << "Insert without split" << std::endl;
l->insert(e, v);
adjust_tree(l);
}
-
}
+
virtual void bulk_insert(std::vector<Value> &values, std::vector<Point> &points)
{
typename std::vector<Point>::iterator it_point;
@@ -225,7 +199,7 @@
{
// std::cerr << "Condensing tree." << std::endl;
- if(l->is_root()) {
+ if(l.get() == root_.get()) {
// if it's the root we are done
return;
}
@@ -234,7 +208,7 @@
parent->adjust_box(l);
if(parent->elements() < m_) {
- if(parent->is_root()) {
+ if(parent.get() == root_.get()) {
// if the parent is underfull and it's the root we just exit
return;
}
@@ -257,7 +231,7 @@
void adjust_tree(boost::shared_ptr<rtree_node<Point, Value> > &n)
{
- if(n->is_root()) {
+ if(n.get() == root_.get()) {
// we finished the adjust
// std::cerr << "It's the root" << std::endl;
return;
@@ -273,7 +247,7 @@
boost::shared_ptr<rtree_node<Point, Value> > &n1,
boost::shared_ptr<rtree_node<Point, Value> > &n2)
{
- if(l->is_root()) {
+ if(l.get() == root_.get()) {
// std::cerr << "Root ---------> split."<< std::endl;
boost::shared_ptr< rtree_node<Point,Value> > new_root(new rtree_node<Point,Value>(boost::shared_ptr<rtree_node<Point,Value> >(), l->get_level()+1));
new_root->set_root();
@@ -597,13 +571,8 @@
}
}
-
-
double width = highest_high - lowest_low;
- // std::cerr << "HH: " << highest_high << " LL: " << lowest_low << std::endl;
- // std::cerr << "Width: " << width << std::endl;
-
separation = (highest_low - lowest_high) / width;
first = highest_low_index;
second = lowest_high_index;
@@ -614,11 +583,16 @@
{
boost::shared_ptr< rtree_node<Point, Value> > N = root_;
-// std::cerr << "Choosing." << std::endl;
+ // if the tree is empty add an initial leaf
+ if(root_->elements() == 0) {
+ boost::shared_ptr< rtree_leaf<Point, Value> > new_leaf(new rtree_leaf<Point, Value>(root_));
+ root_->add_leaf_node(geometry::box<Point>(), new_leaf);
+
+ return new_leaf;
+ }
while(!N->is_leaf()) {
/// traverse N's map to see which node we should select
-// std::cerr << "Not a leaf." << std::endl;
N = N->choose_node(e);
}
return N;
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-07-08 13:53:49 EDT (Tue, 08 Jul 2008)
@@ -56,9 +56,6 @@
/// true if it is a leaf node
virtual bool is_leaf(void) const { return false; }
- /// true if it is the root
- bool is_root(void) const { return root_; }
-
/// define this node as the root
void set_root(void) { root_ = true; }
@@ -200,10 +197,8 @@
/// insertion algorithm choose node
boost::shared_ptr<rtree_node<Point, Value> > choose_node(const geometry::box<Point> e)
{
-// std::cerr << "Choose node" << std::endl;
-
if(nodes_.size() == 0) {
- throw std::logic_error("Empty node trying to choose the least enlargment node.");
+ throw std::logic_error("Empty node trying to choose the least enlargement node.");
}
bool first = true;
double min_area;
@@ -310,7 +305,6 @@
{
std::cerr << " --> Node --------" << std::endl;
std::cerr << " Address: " << this << std::endl;
- std::cerr << " Is Root: " << is_root() << std::endl;
std::cerr << " Level: " << level_ << std::endl;
std::cerr << " Size: " << nodes_.size() << std::endl;
std::cerr << " | ";
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-07-08 13:53:49 EDT (Tue, 08 Jul 2008)
@@ -92,9 +92,6 @@
// std::cerr << "Size: " << points.size() << std::endl;
- // plane
- geometry::box<geometry::point_xy<double> > plane(geometry::point_xy<double>(-130.0, 0.0), geometry::point_xy<double>(-60.0, 80.0));
-
// number of points to find on the search phase
const unsigned int find_count = 100000;
@@ -103,7 +100,7 @@
}
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, 16, 8));
+ q(new boost::spatial_index::rtree< geometry::point_xy<double>, unsigned int >(16, 8));
// load data
std::cerr << " --> bulk insert" << std::endl;
Modified: sandbox/SOC/2008/spacial_indexing/libs/spatial_index/test/random_test_rtree.cpp
==============================================================================
--- sandbox/SOC/2008/spacial_indexing/libs/spatial_index/test/random_test_rtree.cpp (original)
+++ sandbox/SOC/2008/spacial_indexing/libs/spatial_index/test/random_test_rtree.cpp 2008-07-08 13:53:49 EDT (Tue, 08 Jul 2008)
@@ -42,9 +42,6 @@
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;
@@ -52,7 +49,7 @@
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));
+ q(new boost::spatial_index::rtree<geometry::point_xy<double>, unsigned int>(8, 4));
// generate random data
for(unsigned int i = 0; i < points_count; i++) {
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-07-08 13:53:49 EDT (Tue, 08 Jul 2008)
@@ -14,13 +14,12 @@
#include <vector>
#include <string>
+
int test_main(int, char* [])
{
- 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> , unsigned int > >
- q(new boost::spatial_index::rtree< geometry::point_xy<double> , unsigned int >(b, 4, 2));
+ q(new boost::spatial_index::rtree< geometry::point_xy<double> , unsigned int >(4, 2));
std::cerr << std::endl;
std::cerr << " --> bulk insert" << std::endl;
@@ -54,7 +53,7 @@
/// insertion tests
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 >(b, 4, 2));
+ q(new boost::spatial_index::rtree< geometry::point_xy<double> , unsigned int >(4, 2));
geometry::box<geometry::point_xy<double> > e1(geometry::point_xy<double>(2.0, 2.0), geometry::point_xy<double>(4.0, 4.0));
geometry::box<geometry::point_xy<double> > e2(geometry::point_xy<double>(0.0, 1.0), geometry::point_xy<double>(2.0, 2.0));
Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk