|
|
Boost-Commit : |
From: mariano.consoni_at_[hidden]
Date: 2008-06-13 16:12:51
Author: mconsoni
Date: 2008-06-13 16:12:51 EDT (Fri, 13 Jun 2008)
New Revision: 46379
URL: http://svn.boost.org/trac/boost/changeset/46379
Log:
- Insertion finished. Shold be cleaned and tested but its code is finished.
Text files modified:
sandbox/SOC/2008/spacial_indexing/boost/spatial_index/rtree.hpp | 67 ++++++++++++++++++++++++++++-----------
sandbox/SOC/2008/spacial_indexing/boost/spatial_index/rtree_node.hpp | 8 ++--
sandbox/SOC/2008/spacial_indexing/libs/spatial_index/test/simple_test_rtree.cpp | 12 +++++++
3 files changed, 64 insertions(+), 23 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-13 16:12:51 EDT (Fri, 13 Jun 2008)
@@ -55,7 +55,7 @@
boost::shared_ptr<rtree_node<Point, Value> > l(choose_leaf(e));
if(l->is_full()) {
- std::cerr << "Node full. Split." << std::endl;
+// std::cerr << "Node full. Split." << std::endl;
l->insert(e, v);
@@ -64,9 +64,9 @@
boost::shared_ptr< rtree_node<Point, Value> > n2(new rtree_leaf<Point,Value>(l->get_parent(), l->get_capacity()));
split_node(l, n1, n2);
- std::cerr << "Node splited." << std::endl;
- n1->print();
- n2->print();
+// std::cerr << "Node splited." << std::endl;
+// n1->print();
+// n2->print();
adjust_tree(l, n1, n2);
} else {
@@ -119,7 +119,7 @@
boost::shared_ptr<rtree_node<Point,Value> > N = n1;
boost::shared_ptr<rtree_node<Point,Value> > NN = n2;
if(l->is_root()) {
- std::cerr << "Root ---------> split."<< std::endl;
+// 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_));
new_root->set_root();
new_root->add_node(n1->compute_box(), n1);
@@ -131,7 +131,7 @@
parent->replace_node(l, n1);
if(parent->is_full()) {
parent->add_node(n2->compute_box(), n2);
- std::cerr << "parent is full" << std::endl;
+// 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_));
@@ -149,7 +149,7 @@
, boost::shared_ptr<rtree_node<Point, Value> > &n2) const
{
// TODO: unify
- std::cerr << "Split Node." << std::endl;
+// std::cerr << "Split Node." << std::endl;
unsigned int seed1, seed2;
std::vector< geometry::box<Point> > boxes = n->get_boxes();
@@ -166,6 +166,22 @@
if(index != seed1 && index != seed2) {
// TODO: check if the remaining elements should be in one group because of the minimum
+ unsigned int remaining = nodes.size() - index; // 2 because of the seeds
+
+ std::cerr << "Remaining: " << remaining;
+ std::cerr << " n1: " << n1->elements();
+ std::cerr << " n2: " << n2->elements();
+ std::cerr << std::endl;
+
+ if(n1->elements() + remaining == m_) {
+ n1->add_value(it->first, it->second);
+ continue;
+ }
+ if(n2->elements() + remaining == m_) {
+ n2->add_value(it->first, it->second);
+ continue;
+ }
+
/// current boxes of each group
geometry::box<Point> b1, b2;
@@ -217,7 +233,21 @@
if(index != seed1 && index != seed2) {
// TODO: check if the remaining elements should be in one group because of the minimum
- std::cerr << "1" << std::endl;
+ unsigned int remaining = nodes.size() - index; // 2 because of the seeds
+
+ std::cerr << "Remaining: " << remaining;
+ std::cerr << " n1: " << n1->elements();
+ std::cerr << " n2: " << n2->elements();
+ std::cerr << std::endl;
+ if(n1->elements() + remaining == m_) {
+ n1->add_node(it->first, it->second);
+ continue;
+ }
+ if(n2->elements() + remaining == m_) {
+ n2->add_node(it->first, it->second);
+ continue;
+ }
+
/// current boxes of each group
geometry::box<Point> b1, b2;
@@ -259,7 +289,6 @@
}
}
- std::cerr << "s" << std::endl;
}
}
@@ -268,7 +297,7 @@
unsigned int &seed1,
unsigned int &seed2) const
{
- std::cerr << "Linear Pick Seeds." << std::endl;
+// std::cerr << "Linear Pick Seeds." << std::endl;
// get boxes from the node
std::vector< geometry::box<Point> > boxes = n->get_boxes();
@@ -286,8 +315,8 @@
find_normalized_separations<0u>(boxes, separation_x, first_x, second_x);
find_normalized_separations<1u>(boxes, separation_y, first_y, second_y);
- std::cout << "Separation X: " << separation_x << " between " << first_x << " and " << second_x << std::endl;
- std::cout << "Separation Y: " << separation_y << " between " << first_y << " and " << second_y << std::endl;
+// std::cerr << "Separation X: " << separation_x << " between " << first_x << " and " << second_x << std::endl;
+// std::cerr << "Separation Y: " << separation_y << " between " << first_y << " and " << second_y << std::endl;
if(separation_x > separation_y) {
seed1 = first_x;
@@ -302,7 +331,7 @@
void find_normalized_separations(const std::vector< geometry::box<Point> > &boxes, double &separation, unsigned int &first, unsigned int &second) const
{
- std::cout << "Boxes: " << boxes.size() << std::endl;
+// std::cerr << "Boxes: " << boxes.size() << std::endl;
// find the lowest high
typename std::vector< geometry::box<Point> >::const_iterator it = boxes.begin();
@@ -318,7 +347,7 @@
}
index++;
}
- std::cerr << "Lowest High: " << lowest_high << " Index: " << lowest_high_index << std::endl;
+// std::cerr << "Lowest High: " << lowest_high << " Index: " << lowest_high_index << std::endl;
// find the lowest low
it = boxes.begin();
@@ -354,14 +383,14 @@
}
index++;
}
- std::cerr << "Highest Low: " << highest_low << " Index: " << highest_low_index << std::endl;
+// std::cerr << "Highest Low: " << highest_low << " Index: " << highest_low_index << std::endl;
double width = highest_high - lowest_low;
- std::cerr << "HH: " << highest_high << " LL: " << lowest_low << std::endl;
+// std::cerr << "HH: " << highest_high << " LL: " << lowest_low << std::endl;
- std::cerr << "Width: " << width << std::endl;
+// std::cerr << "Width: " << width << std::endl;
separation = (highest_low - lowest_high) / width;
first = highest_low_index;
@@ -373,11 +402,11 @@
{
boost::shared_ptr< rtree_node<Point, Value> > N = root_;
- std::cerr << "Choosing." << std::endl;
+// std::cerr << "Choosing." << std::endl;
while(!N->is_leaf()) {
/// traverse N's map to see which node we should select
- std::cerr << "Not a leaf." << std::endl;
+// 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-06-13 16:12:51 EDT (Fri, 13 Jun 2008)
@@ -109,7 +109,7 @@
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 << "Node found!" << std::endl;
+// std::cerr << "Node found!" << std::endl;
nodes_[index] = std::make_pair(n->compute_box(), n);
return;
}
@@ -123,7 +123,7 @@
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;
+// std::cerr << "Node found!" << std::endl;
nodes_[index] = std::make_pair(new_l->compute_box(), new_l);
return;
}
@@ -152,7 +152,7 @@
/// insertion algorithm choose node
boost::shared_ptr<rtree_node<Point, Value> > choose_node(const geometry::box<Point> e)
{
- std::cerr << "Choose node" << std::endl;
+// std::cerr << "Choose node" << std::endl;
if(nodes_.size() == 0) {
throw std::logic_error("Empty node trying to choose the least enlargment node.");
@@ -190,7 +190,7 @@
}
}
- std::cerr << "We have a node." << std::endl;
+// std::cerr << "We have a node." << std::endl;
return chosen_node;
}
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-13 16:12:51 EDT (Fri, 13 Jun 2008)
@@ -61,6 +61,12 @@
geometry::box<geometry::point_xy<double> > e10(geometry::point_xy<double>(1.5, 1.0), geometry::point_xy<double>(2.5, 3.0));
geometry::box<geometry::point_xy<double> > e11(geometry::point_xy<double>(1.0, 0.0), geometry::point_xy<double>(2.0, 3.0));
+ geometry::box<geometry::point_xy<double> > e12(geometry::point_xy<double>(10.0, 10.0), geometry::point_xy<double>(12.0, 13.0));
+ geometry::box<geometry::point_xy<double> > e13(geometry::point_xy<double>(10.0, 12.0), geometry::point_xy<double>(13.0, 13.0));
+ geometry::box<geometry::point_xy<double> > e14(geometry::point_xy<double>(10.0, 13.0), geometry::point_xy<double>(12.0, 13.5));
+ geometry::box<geometry::point_xy<double> > e15(geometry::point_xy<double>(10.0, 13.0), geometry::point_xy<double>(12.0, 14.0));
+
+
std::cerr << " --> insert env" << std::endl;
q->insert(e1, 1);
q->insert(e2, 2);
@@ -79,6 +85,12 @@
q->insert(e11, 11);
q->print();
+ q->insert(e12, 12);
+ q->insert(e13, 13);
+ q->insert(e14, 14);
+ q->insert(e15, 15);
+ q->print();
+
// std::cerr << " --> insert" << std::endl;
// q->insert(geometry::point_xy<double>(1.0,1.0), it++);
// std::cerr << " --> insert" << std::endl;
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