Subject: [Boost-commit] svn:boost r82522 - in sandbox-branches/geometry/index: boost/geometry/extensions/index/rtree boost/geometry/extensions/index/rtree/visitors tests
From: adam.wulkiewicz_at_[hidden]
Date: 2013-01-17 09:37:41
Author: awulkiew
Date: 2013-01-17 09:37:40 EST (Thu, 17 Jan 2013)
New Revision: 82522
URL: http://svn.boost.org/trac/boost/changeset/82522
Log:
root box calculation after remove moved from rtree::raw_remove() to visitor::remove.
Text files modified:
sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/rtree.hpp | 20 ++---------------
sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/remove.hpp | 20 +++++++++++++++++
sandbox-branches/geometry/index/tests/additional_speed.cpp | 45 ++++++++++++++++++++-------------------
3 files changed, 46 insertions(+), 39 deletions(-)
Modified: sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/rtree.hpp
==============================================================================
--- sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/rtree.hpp (original)
+++ sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/rtree.hpp 2013-01-17 09:37:40 EST (Thu, 17 Jan 2013)
@@ -38,7 +38,6 @@
#include <boost/geometry/extensions/index/rtree/visitors/destroy.hpp>
#include <boost/geometry/extensions/index/rtree/visitors/spatial_query.hpp>
#include <boost/geometry/extensions/index/rtree/visitors/nearest_query.hpp>
-#include <boost/geometry/extensions/index/rtree/visitors/children_box.hpp>
#include <boost/geometry/extensions/index/rtree/visitors/count.hpp>
#include <boost/geometry/extensions/index/rtree/linear/linear.hpp>
@@ -1057,6 +1056,8 @@
BOOST_GEOMETRY_INDEX_ASSERT(m_root, "The root must exist");
BOOST_GEOMETRY_INDEX_ASSERT(index::is_valid(m_translator(value)), "Indexable is invalid");
+ geometry::expand(m_box, m_translator(value));
+
detail::rtree::visitors::insert<
value_type,
value_type, options_type, translator_type, box_type, allocators_type,
@@ -1072,8 +1073,6 @@
// TODO
// If exception is thrown, m_values_count may be invalid
++m_values_count;
-
- geometry::expand(m_box, m_translator(value));
}
/*!
@@ -1091,7 +1090,7 @@
detail::rtree::visitors::remove<
value_type, options_type, translator_type, box_type, allocators_type
- > remove_v(m_root, m_leafs_level, value, m_parameters, m_translator, m_allocators);
+ > remove_v(m_root, m_leafs_level, m_box, value, m_parameters, m_translator, m_allocators);
detail::rtree::apply_visitor(remove_v, *m_root);
@@ -1103,19 +1102,6 @@
--m_values_count;
- // Calculate new box
- if ( m_values_count == 0 )
- {
- geometry::assign_inverse(m_box);
- }
- else
- {
- detail::rtree::visitors::children_box<value_type, options_type, translator_type, box_type, allocators_type>
- children_box_v(m_box, m_translator);
-
- detail::rtree::apply_visitor(children_box_v, *m_root);
- }
-
return 1;
}
Modified: sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/remove.hpp
==============================================================================
--- sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/remove.hpp (original)
+++ sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/remove.hpp 2013-01-17 09:37:40 EST (Thu, 17 Jan 2013)
@@ -38,6 +38,7 @@
public:
inline remove(node* & root,
size_t & leafs_level,
+ Box & root_box,
Value const& value,
parameters_type const& parameters,
Translator const& translator,
@@ -47,6 +48,7 @@
, m_translator(translator)
, m_allocators(allocators)
, m_root_node(root)
+ , m_root_box(root_box)
, m_leafs_level(leafs_level)
, m_is_value_removed(false)
, m_parent(0)
@@ -110,6 +112,9 @@
{
BOOST_GEOMETRY_INDEX_ASSERT(&n == rtree::get<internal_node>(m_root_node), "node must be the root");
+ // assign new root's box
+ assign_root_box(elements);
+
// reinsert elements from removed nodes (underflows)
reinsert_removed_nodes_elements(); // MAY THROW (V, E: alloc, copy, N: alloc)
@@ -155,6 +160,10 @@
rtree::elements(*m_parent)[m_current_child_index].first
= rtree::elements_box<Box>(elements.begin(), elements.end(), m_translator);
}
+ else
+ {
+ assign_root_box(elements);
+ }
}
}
@@ -285,13 +294,24 @@
}
}
+ template <typename Elements>
+ void assign_root_box(Elements const& elements)
+ {
+ if ( elements.empty() )
+ geometry::assign_inverse(m_root_box);
+ else
+ m_root_box = rtree::elements_box<Box>(elements.begin(), elements.end(), m_translator);
+ }
+
Value const& m_value;
parameters_type const& m_parameters;
Translator const& m_translator;
Allocators & m_allocators;
node* & m_root_node;
+ Box & m_root_box;
size_t & m_leafs_level;
+
bool m_is_value_removed;
UnderflowNodes m_underflowed_nodes;
Modified: sandbox-branches/geometry/index/tests/additional_speed.cpp
==============================================================================
--- sandbox-branches/geometry/index/tests/additional_speed.cpp (original)
+++ sandbox-branches/geometry/index/tests/additional_speed.cpp 2013-01-17 09:37:40 EST (Thu, 17 Jan 2013)
@@ -71,8 +71,6 @@
// inserting test
{
- std::cout << "rtree inserting time test... ("
- << values_count << ")\n";
tim.restart();
for (size_t i = 0 ; i < values_count ; ++i )
{
@@ -82,14 +80,8 @@
t.insert(b);
}
- std::cout << "time: " << tim.elapsed() << "s\n";
- }
-
- {
- float x = coords[0].first;
- float y = coords[0].second;
- B b(P(x - 0.5f, y - 0.5f), P(x + 0.5f, y + 0.5f));
- t.remove(b);
+ double time = tim.elapsed();
+ std::cout << time << "s - insert " << values_count << '\n';
}
std::vector<B> result;
@@ -98,8 +90,6 @@
// query test
{
- std::cout << "query(B) searching time test... ("
- << queries_count << ")\n";
tim.restart();
size_t temp = 0;
for (size_t i = 0 ; i < queries_count ; ++i )
@@ -110,16 +100,14 @@
t.spatial_query(B(P(x - 10, y - 10), P(x + 10, y + 10)), std::back_inserter(result));
temp += result.size();
}
- std::cout << "time: " << tim.elapsed() << "s\n";
- std::cout << "found: " << temp << "\n";
+ double time = tim.elapsed();
+ std::cout << time << "s - spatial_query(B) " << queries_count << " found " << temp << '\n';
}
result.clear();
// searching test
{
- std::cout << "nearest 10 searching time test... ("
- << queries_count / 10 << ")\n";
tim.restart();
size_t temp = 0;
for (size_t i = 0 ; i < queries_count / 10 ; ++i )
@@ -129,13 +117,11 @@
result.clear();
temp += t.nearest_query(P(x, y), 5, std::back_inserter(result));
}
- std::cout << "time: " << tim.elapsed() << "s\n";
- std::cout << "found: " << temp << "\n";
+ double time = tim.elapsed();
+ std::cout << time << "s - nearest_query(P, 5) " << (queries_count / 10) << " found " << temp << '\n';
}
{
- std::cout << "nearest 1 searching time test... ("
- << queries_count / 10 << ")\n";
tim.restart();
size_t temp = 0;
for (size_t i = 0 ; i < queries_count / 10 ; ++i )
@@ -144,8 +130,23 @@
float y = coords[i].second + 100;
temp += t.nearest_query(P(x, y), result_one);
}
- std::cout << "time: " << tim.elapsed() << "s\n";
- std::cout << "found: " << temp << "\n";
+ double time = tim.elapsed();
+ std::cout << time << "s - nearest_query(P) " << (queries_count / 10) << " found " << temp << '\n';
+ }
+
+ // inserting test
+ {
+ tim.restart();
+ for (size_t i = 0 ; i < values_count / 10 ; ++i )
+ {
+ float x = coords[i].first;
+ float y = coords[i].second;
+ B b(P(x - 0.5f, y - 0.5f), P(x + 0.5f, y + 0.5f));
+
+ t.remove(b);
+ }
+ double time = tim.elapsed();
+ std::cout << time << "s - remove " << values_count / 10 << '\n';
}
}