Boost logo

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