|
|
Boost-Commit : |
From: mariano.consoni_at_[hidden]
Date: 2008-06-11 10:08:09
Author: mconsoni
Date: 2008-06-11 10:08:09 EDT (Wed, 11 Jun 2008)
New Revision: 46329
URL: http://svn.boost.org/trac/boost/changeset/46329
Log:
- More improvements in Rtree insertion code.
Text files modified:
sandbox/SOC/2008/spacial_indexing/boost/spatial_index/rtree.hpp | 102 ++++++++++++++++++++++++++++++++-------
sandbox/SOC/2008/spacial_indexing/boost/spatial_index/spatial_index.hpp | 3 +
sandbox/SOC/2008/spacial_indexing/libs/spatial_index/test/simple_test_rtree.cpp | 21 +++++--
3 files changed, 101 insertions(+), 25 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-11 10:08:09 EDT (Wed, 11 Jun 2008)
@@ -24,13 +24,17 @@
{
public:
rtree_node(void) : m_(4), M_(8) {}
- rtree_node(const unsigned int &level, const unsigned int &m, const unsigned int &M)
- : level_(level), m_(m), M_(M) {}
+ rtree_node(const boost::shared_ptr<rtree_node<Point, Value> > &parent, const unsigned int &level, const unsigned int &m, const unsigned int &M)
+ : parent_(parent), level_(level), m_(m), M_(M) {}
- virtual bool is_full(void) const { return nodes_.size() == M_; }
+ virtual bool is_full(void) const { return nodes_.size() >= M_; }
/// true if it is a leaf node
- virtual bool is_leaf(void) { return false; }
+ virtual bool is_leaf(void) const { return false; }
+
+ /// true if it is the root
+ bool is_root(void) const { return root_; }
+ void set_root(void) { root_ = true; }
virtual void insert(const geometry::box<Point> &e, const Value &v)
{
@@ -42,7 +46,7 @@
{
if(nodes_.size() < M_) {
- nodes_[b] = l;
+ nodes_.push_back(std::make_pair(b, l));
} else {
// split
}
@@ -93,10 +97,40 @@
return chosen_node;
}
+ virtual void print(void) const
+ {
+ std::cerr << " --> Node --------" << std::endl;
+ std::cerr << " Is Root: " << is_root() << std::endl;
+ std::cerr << " Level: " << level_ << std::endl;
+ std::cerr << " Size / Min / Max: " << nodes_.size() << " / " << m_ << " / " << M_ << std::endl;
+ std::cerr << " | ";
+ for(typename node_map::const_iterator it = nodes_.begin(); it != nodes_.end(); ++it) {
+ std::cerr << "( " << 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()) << " )" ;
+ std::cerr << " | ";
+ }
+ std::cerr << std::endl;
+ std::cerr << " --< Node --------" << std::endl;
+
+ // print child nodes
+ std::cerr << " Children: " << std::endl;
+ for(typename node_map::const_iterator it = nodes_.begin(); it != nodes_.end(); ++it) {
+ it->second->print();
+ }
+ }
+
virtual ~rtree_node(void) {}
+ private:
+
+ // true if it is the root
+ bool root_;
+
+ // parent node
+ boost::shared_ptr< rtree_node<Point, Value> > parent_;
+
// level of this node
unsigned int level_;
@@ -105,11 +139,12 @@
// maximum number of elements per node
unsigned int M_;
- typedef std::map<geometry::box<Point>, boost::shared_ptr<rtree_node> > node_map;
+ typedef std::vector< std::pair<geometry::box<Point>, boost::shared_ptr<rtree_node> > > node_map;
node_map nodes_;
private:
+
geometry::box<Point> enlarge_box(const geometry::box<Point> &b1, const geometry::box<Point> &b2) const
{
Point min(
@@ -140,16 +175,36 @@
{
public:
rtree_leaf(void) : L_(8), level_(0) {}
- rtree_leaf(const unsigned int &L) : L_(L), level_(0) {}
+ rtree_leaf(const boost::shared_ptr< rtree_node<Point,Value> > &parent, const unsigned int &L)
+ : rtree_node<Point,Value>(parent, 0, 0, 0), L_(L), level_(0) {}
/// yes, we are a leaf
- virtual bool is_leaf(void) { return true; }
+ virtual bool is_leaf(void) const { return true; }
- virtual bool is_full(void) const { return nodes_.size() == L_; }
+ virtual bool is_full(void) const { return nodes_.size() >= L_; }
virtual void insert(const geometry::box<Point> &e, const Value &v)
{
- nodes_[e] = v;
+ nodes_.push_back(std::make_pair(e, v));
+// std::cerr << "Node size: " << nodes_.size() << std::endl;
+ }
+
+ virtual void print(void) const
+ {
+ std::cerr << " --> Leaf --------" << std::endl;
+ std::cerr << " Size / Capacity: " << nodes_.size() << " / " << L_ << std::endl;
+ std::cerr << " | ";
+ for(typename leaves_map::const_iterator it = nodes_.begin(); it != nodes_.end(); ++it) {
+ std::cerr << "( " << 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()) << " )" ;
+ std::cerr << " -> ";
+ std::cerr << it->second;
+ std::cerr << " | ";
+
+
+ }
+ std::cerr << std::endl;
+ std::cerr << " --< Leaf --------" << std::endl;
}
private:
@@ -160,7 +215,7 @@
// level of this node
unsigned int level_;
- typedef std::map<geometry::box<Point>, Value > leaves_map;
+ typedef std::vector< std::pair< geometry::box<Point>, Value > > leaves_map;
leaves_map nodes_;
};
@@ -183,30 +238,35 @@
public:
rtree(const geometry::box<Point> &initial_box, const unsigned int &L, const unsigned int &m, const unsigned int &M)
: element_count(0), L_(L), m_(m), M_(M),
- root_(new rtree_node<Point, Value>(1, m, M))
+ root_(new rtree_node<Point, Value>(boost::shared_ptr< rtree_node<Point,Value> >(), 1, m, M))
{
- boost::shared_ptr< rtree_leaf<Point, Value> > new_leaf(new rtree_leaf<Point, Value>(L));
+ root_->set_root();
+ boost::shared_ptr< rtree_leaf<Point, Value> > new_leaf(new rtree_leaf<Point, Value>(root_, L));
root_->add_leaf_node(initial_box, new_leaf);
}
-
+
virtual void insert(const Point &k, const Value &v)
{
element_count++;
}
- // TODO: do private
-
+ virtual void print(void) const
+ {
+ root_->print();
+ }
void insert(const geometry::box<Point> &e, const Value &v)
{
boost::shared_ptr<rtree_node<Point, Value> > l(choose_leaf(e));
if(l->is_full()) {
+ std::cerr << "Node full. Split." << std::endl;
+
// split!
- } else {
- l->insert(e, v);
}
+ l->insert(e, v);
+
adjust_tree(l);
element_count++;
@@ -237,7 +297,11 @@
void adjust_tree(boost::shared_ptr<rtree_node<Point, Value> > &l)
{
-
+ boost::shared_ptr<rtree_node<Point,Value> > N = l;
+ if(N->is_root()) {
+ return;
+ }
+
}
boost::shared_ptr<rtree_node<Point, Value> > choose_leaf(const geometry::box<Point> e)
Modified: sandbox/SOC/2008/spacial_indexing/boost/spatial_index/spatial_index.hpp
==============================================================================
--- sandbox/SOC/2008/spacial_indexing/boost/spatial_index/spatial_index.hpp (original)
+++ sandbox/SOC/2008/spacial_indexing/boost/spatial_index/spatial_index.hpp 2008-06-11 10:08:09 EDT (Wed, 11 Jun 2008)
@@ -50,6 +50,9 @@
/// element count in the index
virtual unsigned int elements(void) = 0;
+
+ /// debug print
+ virtual void print(void) const = 0;
/// destructor
virtual ~spatial_index(void) {}
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-06-11 10:08:09 EDT (Wed, 11 Jun 2008)
@@ -35,8 +35,8 @@
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 >(b, 8, 4, 8));
+ 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, 4));
// std::cerr << " --> bulk insert" << std::endl;
// std::vector<std::string>::iterator b, e;
@@ -44,12 +44,21 @@
// e = data.end();
// q->bulk_insert(b,e, points);
- std::vector<std::string>::iterator it = data.begin();
+// std::vector<std::string>::iterator it = data.begin();
-
- geometry::box<geometry::point_xy<double> > e(geometry::point_xy<double>(2.0, 2.0), geometry::point_xy<double>(4.0, 4.0));
+ 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));
+ geometry::box<geometry::point_xy<double> > e3(geometry::point_xy<double>(5.0, 4.0), geometry::point_xy<double>(6.0, 6.0));
+ geometry::box<geometry::point_xy<double> > e4(geometry::point_xy<double>(5.0, 5.0), geometry::point_xy<double>(8.0, 8.0));
+ geometry::box<geometry::point_xy<double> > e5(geometry::point_xy<double>(7.0, 4.0), geometry::point_xy<double>(12.0, 7.0));
std::cerr << " --> insert env" << std::endl;
- q->insert(e, it++);
+ q->insert(e1, 1);
+ q->insert(e2, 2);
+ q->insert(e3, 3);
+ q->insert(e4, 4);
+ q->insert(e5, 5);
+
+ q->print();
// std::cerr << " --> insert" << std::endl;
// q->insert(geometry::point_xy<double>(1.0,1.0), it++);
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