|
|
Boost-Commit : |
From: mariano.consoni_at_[hidden]
Date: 2008-06-17 10:26:36
Author: mconsoni
Date: 2008-06-17 10:26:35 EDT (Tue, 17 Jun 2008)
New Revision: 46447
URL: http://svn.boost.org/trac/boost/changeset/46447
Log:
- Moved the m_ and M_ to the rtree main structure.
Text files modified:
sandbox/SOC/2008/spacial_indexing/boost/spatial_index/rtree.hpp | 24 +++++++++++-------------
sandbox/SOC/2008/spacial_indexing/boost/spatial_index/rtree_leaf.hpp | 18 ++++--------------
sandbox/SOC/2008/spacial_indexing/boost/spatial_index/rtree_node.hpp | 26 ++++----------------------
3 files changed, 19 insertions(+), 49 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-17 10:26:35 EDT (Tue, 17 Jun 2008)
@@ -23,8 +23,6 @@
private:
unsigned int element_count;
- // maximum number of elements per leaf
- unsigned int L_;
// minimum number of elements per node
unsigned int m_;
// maximum number of elements per node
@@ -34,16 +32,15 @@
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>(boost::shared_ptr< rtree_node<Point,Value> >(), 1, m, 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_, L));
+ 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'
- /// TODO: implement
virtual void remove(const geometry::box<Point> &k)
{
try {
@@ -69,6 +66,7 @@
void condense_tree(const boost::shared_ptr<rtree_node<Point,Value> > &l)
{
std::cerr << "Condensing tree." << std::endl;
+ /// TODO: implement
}
virtual void print(void) const
@@ -85,14 +83,14 @@
{
boost::shared_ptr<rtree_node<Point, Value> > l(choose_leaf(e));
- if(l->is_full()) {
+ if(l->elements() >= M_) {
// std::cerr << "Node full. Split." << std::endl;
l->insert(e, v);
// split!
- boost::shared_ptr< rtree_node<Point, Value> > n1(new rtree_leaf<Point,Value>(l->get_parent(), l->get_capacity()));
- boost::shared_ptr< rtree_node<Point, Value> > n2(new rtree_leaf<Point,Value>(l->get_parent(), l->get_capacity()));
+ boost::shared_ptr< rtree_node<Point, Value> > n1(new rtree_leaf<Point,Value>(l->get_parent()));
+ boost::shared_ptr< rtree_node<Point, Value> > n2(new rtree_leaf<Point,Value>(l->get_parent()));
split_node(l, n1, n2);
// std::cerr << "Node splited." << std::endl;
@@ -170,7 +168,7 @@
boost::shared_ptr<rtree_node<Point,Value> > NN = n2;
if(l->is_root()) {
// 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, m_, M_));
+ 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();
new_root->add_node(n1->compute_box(), n1);
new_root->add_node(n2->compute_box(), n2);
@@ -179,12 +177,12 @@
}
boost::shared_ptr<rtree_node<Point,Value> > parent = l->get_parent();
parent->replace_node(l, n1);
- if(parent->is_full()) {
+ if(parent->elements() >= M_) {
parent->add_node(n2->compute_box(), n2);
// std::cerr << "parent is full" << std::endl;
- boost::shared_ptr< rtree_node<Point, Value> > p1(new rtree_node<Point,Value>(parent->get_parent(), parent->get_level(), m_, M_));
- boost::shared_ptr< rtree_node<Point, Value> > p2(new rtree_node<Point,Value>(parent->get_parent(), parent->get_level(), m_, M_));
+ boost::shared_ptr< rtree_node<Point, Value> > p1(new rtree_node<Point,Value>(parent->get_parent(), parent->get_level()));
+ boost::shared_ptr< rtree_node<Point, Value> > p2(new rtree_node<Point,Value>(parent->get_parent(), parent->get_level()));
split_node(parent, p1, p2);
adjust_tree(parent, p1, p2);
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-17 10:26:35 EDT (Tue, 17 Jun 2008)
@@ -24,9 +24,9 @@
typedef std::vector< std::pair< geometry::box<Point>, Value > > leaves_map;
public:
- rtree_leaf(void) : L_(8), 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) {}
+ rtree_leaf(void) : level_(0) {}
+ rtree_leaf(const boost::shared_ptr< rtree_node<Point,Value> > &parent)
+ : rtree_node<Point,Value>(parent, 0), level_(0) {}
/// query method
virtual void find(const geometry::box<Point> &e, std::deque<Value> &r)
@@ -57,8 +57,6 @@
/// yes, we are a leaf
virtual bool is_leaf(void) const { return true; }
- virtual bool is_full(void) const { return nodes_.size() >= L_; }
-
/// element count
virtual unsigned int elements(void) const
{
@@ -90,11 +88,6 @@
nodes_.clear();
}
- virtual unsigned int get_capacity(void) const
- {
- return L_;
- }
-
virtual Value get_value(const unsigned int i) const { return nodes_[i].second; }
@@ -125,7 +118,7 @@
virtual void print(void) const
{
std::cerr << " --> Leaf --------" << std::endl;
- std::cerr << " Size / Capacity: " << nodes_.size() << " / " << L_ << std::endl;
+ std::cerr << " Size: " << nodes_.size() << std::endl;
for(typename leaves_map::const_iterator it = nodes_.begin(); it != nodes_.end(); ++it) {
std::cerr << " | ";
std::cerr << "( " << geometry::get<0>(it->first.min()) << " , " << geometry::get<1>(it->first.min()) << " ) x " ;
@@ -142,9 +135,6 @@
private:
- // maximum number of elements per leaf
- unsigned int L_;
-
// level of this node
unsigned int level_;
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-17 10:26:35 EDT (Tue, 17 Jun 2008)
@@ -29,14 +29,11 @@
public:
/// default constructor (needed for the containers)
- rtree_node(void) : m_(4), M_(8), root_(false) {}
+ rtree_node(void) : root_(false) {}
/// normal constructor
- 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), root_(false) {}
-
- /// true if the node is full
- virtual bool is_full(void) const { return nodes_.size() >= M_; }
+ rtree_node(const boost::shared_ptr<rtree_node<Point, Value> > &parent, const unsigned int &level)
+ : parent_(parent), level_(level), root_(false) {}
/// level projector
virtual unsigned int get_level(void) const { return level_; }
@@ -107,12 +104,6 @@
std::cerr << "Insert in node!" << std::endl;
}
- /// projector for the node capacity
- virtual unsigned int get_capacity(void) const
- {
- return M_;
- }
-
/// get the envelopes of a node
virtual std::vector< geometry::box<Point> > get_boxes(void) const
{
@@ -242,7 +233,7 @@
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 << " Size: " << nodes_.size() << 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 " ;
@@ -271,21 +262,12 @@
// level of this node
unsigned int level_;
- // minimum number of elements per node
- unsigned int m_;
-
- // maximum number of elements per node
- unsigned int M_;
-
// true if it is the root
bool root_;
-
/// child nodes
node_map nodes_;
- private:
-
};
/// given two boxes, create the minimal box that contains them
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