Boost logo

Boost-Commit :

From: mariano.consoni_at_[hidden]
Date: 2008-07-08 15:13:59


Author: mconsoni
Date: 2008-07-08 15:13:58 EDT (Tue, 08 Jul 2008)
New Revision: 47247
URL: http://svn.boost.org/trac/boost/changeset/47247

Log:
- More cleanups.

Text files modified:
   sandbox/SOC/2008/spacial_indexing/boost/spatial_index/quadtree.hpp | 13 +++----
   sandbox/SOC/2008/spacial_indexing/boost/spatial_index/quadtree_node.hpp | 66 ++++-----------------------------------
   sandbox/SOC/2008/spacial_indexing/boost/spatial_index/rtree.hpp | 25 +++++++++-----
   sandbox/SOC/2008/spacial_indexing/boost/spatial_index/rtree_leaf.hpp | 3 -
   sandbox/SOC/2008/spacial_indexing/boost/spatial_index/rtree_node.hpp | 66 ++++++++++-----------------------------
   5 files changed, 47 insertions(+), 126 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-07-08 15:13:58 EDT (Tue, 08 Jul 2008)
@@ -1,7 +1,12 @@
+//
+// Spatial Index - QuadTree
+//
+//
 // 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_QUADTREE_HPP
@@ -33,7 +38,6 @@
   virtual void remove(const Point &k)
   {
     root.remove(k);
- // root.clean();
     element_count--;
   }
 
@@ -61,7 +65,7 @@
   /// insert data with envelope 'e' with key 'k'
   virtual void insert(const geometry::box<Point> &e, const Value &v)
   {
- std::cerr << "Box insertion not implemented." << std::endl;
+ throw std::logic_error("Box insertion not implemented.");
   }
 
 
@@ -104,11 +108,6 @@
     return result;
   }
 
- void clean(void)
- {
- root.clean();
- }
-
   virtual unsigned int elements(void) const { return element_count; }
         
   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-07-08 15:13:58 EDT (Tue, 08 Jul 2008)
@@ -1,7 +1,12 @@
+//
+// Spatial Index - QuadTree Node
+//
+//
 // 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_QUADTREE_NODE_HPP
@@ -74,47 +79,9 @@
   quadtree_node(const geometry::box<Point> &r, const unsigned int node_size)
     : bounding_rectangle_(r), node_size_(node_size)
   {
- // std::cerr << "Creating quadtree_node with " <<
- // "min_x: " << min_x << " min_y: " << min_y << " max_x: " << max_x << " max_y " << max_y << std::endl;
   }
 
 
- void clean(void)
- {
- if(nw_ != boost::shared_ptr<quadtree_node>()) {
- if(nw_->empty_leaf()) {
- nw_ = boost::shared_ptr<quadtree_node>();
- } else {
- nw_->clean();
- }
- }
-
- if(sw_ != boost::shared_ptr<quadtree_node>()) {
- if(sw_->empty_leaf()) {
- sw_ = boost::shared_ptr<quadtree_node>();
- } else {
- sw_->clean();
- }
- }
-
- if(se_ != boost::shared_ptr<quadtree_node>()) {
- if(se_->empty_leaf()) {
- se_ = boost::shared_ptr<quadtree_node>();
- } else {
- se_->clean();
- }
- }
-
- if(ne_ != boost::shared_ptr<quadtree_node>()) {
- if(ne_->empty_leaf()) {
- ne_ = boost::shared_ptr<quadtree_node>();
- } else {
- ne_->clean();
- }
- }
-
- }
-
   bool empty_leaf(void) const
   {
     return (m_.size() == 0) &&
@@ -128,15 +95,8 @@
   void insert(const Point &k, const Value &v)
   {
     if(m_.size() < node_size_) {
-// std::cerr << "Empty quadtree_node --> inserting (" << v << ")" << std::endl;
       m_[k] = v;
     } else {
- // std::cerr << "Quadtree_Node division: ";
- // // quadtree_node division
- // std::cerr << " (" << k.first << ", " << k.second << ")" ;
- // std::cerr << " in (" << min_x_ << ", " << min_y_ << ")";
- // std::cerr << " x (" << max_x_ << ", " << max_y_ << ")" << std::endl;
-
       // 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);
@@ -176,21 +136,15 @@
   void find(std::deque<Value> &result, const geometry::box<Point> &r)
   {
     if(m_.size() != 0) {
- // std::cerr << "Node: X1:" << min_x_ << " X2:" << max_x_ << " Y1:" << min_y_ << " Y2: " << max_y_ << std::endl;
- // std::cerr << "Query: X1:" << x1 << " X2:" << x2 << " Y1:" << y1 << " Y2: " << y2 << std::endl;
 
       if(geometry::get<0>(r.min()) > geometry::get<0>(bounding_rectangle_.max())
          || geometry::get<0>(r.max()) < geometry::get<0>(bounding_rectangle_.min())
          || geometry::get<1>(r.min()) > geometry::get<1>(bounding_rectangle_.max())
          || geometry::get<1>(r.max()) < geometry::get<1>(bounding_rectangle_.min())) {
- // 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;
         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);
@@ -209,8 +163,6 @@
       if(sw_ != boost::shared_ptr<quadtree_node>()) {
         sw_->find(result, r);
       }
-
- // std::cerr << std::endl;
     }
   }
 
@@ -265,6 +217,7 @@
     return Value();
   }
 
+
   void remove(const Point &k)
   {
     typename std::map<Point, Value>::iterator it = m_.find(k);
@@ -275,14 +228,9 @@
     recursive_remove(k);
   }
 
+
   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;

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 15:13:58 EDT (Tue, 08 Jul 2008)
@@ -1,7 +1,12 @@
+//
+// Spatial Index - rTree
+//
+//
 // 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
@@ -36,7 +41,7 @@
     }
 
 
- /// remove the element with key 'k'
+ /// remove elements inside the box 'k'
     virtual void remove(const geometry::box<Point> &k)
     {
       try {
@@ -184,7 +189,7 @@
 
 
   private:
- /// cached number of elements
+ /// number of elements
     unsigned int element_count_;
 
     /// minimum number of elements per node
@@ -291,8 +296,6 @@
                     boost::shared_ptr<rtree_node<Point, Value> > &n1,
                     boost::shared_ptr<rtree_node<Point, Value> > &n2) const
     {
- // TODO: unify
-
       unsigned int seed1, seed2;
       std::vector< geometry::box<Point> > boxes = n->get_boxes();
 
@@ -304,11 +307,18 @@
       if(n->is_leaf()) {
          n1->add_value(boxes[seed1], n->get_value(seed1));
         n2->add_value(boxes[seed2], n->get_value(seed2));
+ } else {
+ n1->add_node(boxes[seed1], n->get_node(seed1));
+ n2->add_node(boxes[seed2], n->get_node(seed2));
+ }
+
+ unsigned int index = 0;
 
- unsigned int index = 0;
+ if(n->is_leaf()) {
         typename rtree_leaf<Point,Value>::leaves_map nodes = n->get_leaves();
         unsigned int remaining = nodes.size()-2;
         for(typename rtree_leaf<Point,Value>::leaves_map::const_iterator it = nodes.begin(); it != nodes.end(); ++it, index++) {
+
           if(index != seed1 && index != seed2) {
             if(n1->elements() + remaining == m_) {
               n1->add_value(it->first, it->second);
@@ -362,13 +372,10 @@
           }
         }
       } else {
- n1->add_node(boxes[seed1], n->get_node(seed1));
- n2->add_node(boxes[seed2], n->get_node(seed2));
-
- unsigned int index = 0;
         typename rtree_node<Point,Value>::node_map nodes = n->get_nodes();
         unsigned int remaining = nodes.size()-2;
         for(typename rtree_node<Point,Value>::node_map::const_iterator it = nodes.begin(); it != nodes.end(); ++it, index++) {
+
           if(index != seed1 && index != seed2) {
 
             if(n1->elements() + remaining == m_) {

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-07-08 15:13:58 EDT (Tue, 08 Jul 2008)
@@ -72,7 +72,6 @@
     virtual void insert(const geometry::box<Point> &e, const Value &v)
     {
       nodes_.push_back(std::make_pair(e, v));
-// std::cerr << "Node size: " << nodes_.size() << std::endl;
     }
 
     virtual std::vector< std::pair< geometry::box<Point>, Value > > get_leaves(void) const
@@ -102,7 +101,6 @@
 
       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;
           nodes_.erase(it);
           return;
         }
@@ -137,7 +135,6 @@
     }
 
   private:
-
     leaves_map nodes_;
   };
 

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 15:13:58 EDT (Tue, 08 Jul 2008)
@@ -25,13 +25,14 @@
   {
   public:
     /// type for the node map
- typedef std::vector< std::pair<geometry::box<Point>, boost::shared_ptr<rtree_node<Point, Value> > > > node_map;
+ typedef std::vector< std::pair<geometry::box<Point>,
+ boost::shared_ptr<rtree_node<Point, Value> > > > node_map;
 
   public:
     /// default constructor (needed for the containers)
     rtree_node(void) {}
 
- /// normal constructor
+ /// standard constructor
     rtree_node(const boost::shared_ptr<rtree_node<Point, Value> > &parent, const unsigned int &level)
       : parent_(parent), level_(level) {}
 
@@ -69,19 +70,10 @@
       }
     }
 
- void find_leaves(const geometry::box<Point> &e, typename std::vector<boost::shared_ptr<rtree_node<Point,Value> > > &result) const
+ void find_leaves(const geometry::box<Point> &e,
+ typename std::vector<boost::shared_ptr<rtree_node<Point,Value> > > &result) const
     {
-// std::cerr << "find_leaves\n";
-
       for(typename node_map::const_iterator it = nodes_.begin(); it != nodes_.end(); ++it) {
-
- // std::cerr << "e: ( " << geometry::get<0>(e.min()) << " , " << geometry::get<1>(e.min()) << " ) x " ;
- // std::cerr << "( " << geometry::get<0>(e.max()) << " , " << geometry::get<1>(e.max()) << " )" ;
-
-
- // std::cerr << "it: ( " << geometry::get<0>(it->first.min()) << " , " << geometry::get<1>(it->first.min()) << " ) x " ;
- // std::cerr << "( " << geometry::get<0>(it->first.max()) << " , " << geometry::get<1>(it->first.max()) << " )" ;
-
         if(overlaps(it->first, e)) {
           if(it->second->is_leaf()) {
             result.push_back(it->second);
@@ -92,7 +84,6 @@
       }
     }
 
-
     /// compute bounding box for this leaf
     virtual geometry::box<Point> compute_box(void) const
     {
@@ -112,7 +103,7 @@
     /// insert a value (not allowed for a node)
     virtual void insert(const geometry::box<Point> &e, const Value &v)
     {
- std::cerr << "Insert in node!" << std::endl;
+ throw std::logic_error("Insert in node!");
     }
 
     /// get the envelopes of a node
@@ -131,26 +122,16 @@
       unsigned int index = 0;
       for(typename node_map::iterator it = nodes_.begin(); it != nodes_.end(); ++it, index++) {
         if(it->second.get() == n.get()) {
-// std::cerr << "---------------------------------------->" << std::endl;
-// std::cerr << "Node found!" << std::endl;
-// std::cerr << "Box: " << geometry::get<0>(n->compute_box().min()) << " , " <<geometry::get<1>(n->compute_box().min()) << std::endl;
-// std::cerr << "Box: " << geometry::get<0>(n->compute_box().max()) << " , " <<geometry::get<1>(n->compute_box().max()) << std::endl;
- if(it->second->get_parent().get() != n->get_parent().get()) {
- std::cerr << "ERR" << std::endl;
- }
           nodes_[index] = std::make_pair(n->compute_box(), n);
-// std::cerr << "---------------------------------------->" << std::endl;
           return;
         }
       }
-// std::cerr << "adjust_node: node not found." << std::endl;
     }
 
     virtual void remove(const geometry::box<Point> &k)
     {
       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;
           nodes_.erase(it);
           return;
         }
@@ -158,22 +139,23 @@
     }
 
     /// replace the node in the nodes_ vector and recompute the box
- void replace_node(const boost::shared_ptr<rtree_node<Point, Value> > &l, boost::shared_ptr<rtree_node<Point, Value> > &new_l)
+ void replace_node(const boost::shared_ptr<rtree_node<Point, Value> > &l,
+ boost::shared_ptr<rtree_node<Point, Value> > &new_l)
     {
       unsigned int index = 0;
       for(typename node_map::iterator it = nodes_.begin(); it != nodes_.end(); ++it, index++) {
         if(it->second.get() == l.get()) {
-// std::cerr << "Node found!" << std::endl;
           nodes_[index] = std::make_pair(new_l->compute_box(), new_l);
           new_l->update_parent(new_l);
           return;
         }
       }
- std::cerr << "replace_node: node not found." << std::endl;
+ throw std::logic_error("Node not found.");
     }
 
     /// add a node
- virtual void add_node(const geometry::box<Point> &b, const boost::shared_ptr<rtree_node<Point, Value> > &n)
+ virtual void add_node(const geometry::box<Point> &b,
+ const boost::shared_ptr<rtree_node<Point, Value> > &n)
     {
       nodes_.push_back(std::make_pair(b, n));
       n->update_parent(n);
@@ -202,6 +184,7 @@
       double min_diff_area;
       boost::shared_ptr<rtree_node<Point,Value> > chosen_node;
 
+ // check for the least enlargement
       for(typename node_map::const_iterator it = nodes_.begin(); it != nodes_.end(); ++it) {
 
         double diff_area = compute_union_area(e, it->first) - geometry::area(it->first);
@@ -230,7 +213,6 @@
 
         }
       }
-// std::cerr << "We have a node." << std::endl;
       return chosen_node;
     }
 
@@ -244,7 +226,7 @@
       return parent_;
     }
 
- // update the parent of all the childs
+ /// update the parent of all the childs
     void update_parent(const boost::shared_ptr<rtree_node<Point,Value> > &p)
     {
       for(typename node_map::iterator it = nodes_.begin(); it != nodes_.end(); ++it) {
@@ -252,7 +234,7 @@
       }
     }
 
- // setter for parent
+ /// set parent
     void set_parent(const boost::shared_ptr<rtree_node<Point,Value> > &p)
     {
        parent_ = p;
@@ -275,7 +257,6 @@
       throw std::logic_error("Node not found");
     }
 
-
     /// value projector for the nodes
     node_map get_nodes(void) const { return nodes_; }
 
@@ -288,8 +269,11 @@
       for(typename node_map::const_iterator it = nodes_.begin(); it != nodes_.end(); ++it) {
         typename std::vector< std::pair< geometry::box<Point>, Value > > this_leaves = it->second->get_leaves();
 
- for(typename std::vector<std::pair<geometry::box<Point>, Value> >::iterator it_leaf = this_leaves.begin(); it_leaf != this_leaves.end(); ++it_leaf) {
+ for(typename std::vector<std::pair<geometry::box<Point>, Value> >::iterator it_leaf = this_leaves.begin();
+ it_leaf != this_leaves.end(); ++it_leaf) {
+
           l.push_back(*it_leaf);
+
         }
 
       }
@@ -325,22 +309,11 @@
       }
     }
 
-// boost::shared_ptr<rtree_node<Point, Value> > get_node(const geometry::box<Point> &e) const
-// {
-// for(typename node_map::const_iterator it = nodes_.begin(); it != nodes_.end(); ++it) {
-// if(it->first.max() == e.max() && it->first.min() == e.min()) {
-// return it->second;
-// }
-// }
-
-// }
-
     /// destructor (virtual because we have virtual functions)
     virtual ~rtree_node(void) {}
 
   private:
 
-
     // parent node
     boost::shared_ptr< rtree_node<Point, Value> > parent_;
 
@@ -352,10 +325,7 @@
 
   };
 
-
-
 } // namespace spatial_index
 } // namespace boost
 
 #endif // BOOST_SPATIAL_INDEX_RTREE_NODE_HPP
-


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