Subject: [Boost-commit] svn:boost r80827 - in sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree: rstar visitors
From: adam.wulkiewicz_at_[hidden]
Date: 2012-10-03 14:10:29
Author: awulkiew
Date: 2012-10-03 14:10:29 EDT (Wed, 03 Oct 2012)
New Revision: 80827
URL: http://svn.boost.org/trac/boost/changeset/80827
Log:
Data changing in traversing process moved to separate structure.
Text files modified:
sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/rstar/insert.hpp | 44 ++++++++++++--------
sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/visitors/insert.hpp | 85 +++++++++++++++++++++++++++------------
2 files changed, 84 insertions(+), 45 deletions(-)
Modified: sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/rstar/insert.hpp
==============================================================================
--- sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/rstar/insert.hpp (original)
+++ sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/rstar/insert.hpp 2012-10-03 14:10:29 EDT (Wed, 03 Oct 2012)
@@ -153,17 +153,17 @@
{
BOOST_GEOMETRY_INDEX_ASSERT(result_elements.empty(), "reinsert should be handled only once for level");
- result_relative_level = base::m_leafs_level - base::m_current_level;
+ result_relative_level = base::m_leafs_level - base::m_traverse_data.current_level;
// overflow
if ( base::m_parameters.get_max_elements() < rtree::elements(n).size() )
{
// node isn't root node
- if ( base::m_parent )
+ if ( !base::m_traverse_data.current_is_root() )
{
rstar::remove_elements_to_reinsert<Value, Options, Translator, Box, Allocators>::apply(
result_elements, n,
- base::m_parent, base::m_current_child_index,
+ base::m_traverse_data.parent, base::m_traverse_data.current_child_index,
base::m_parameters, base::m_translator);
}
// node is root node
@@ -188,10 +188,10 @@
template <typename Node>
inline void recalculate_aabb_if_necessary(Node &n) const
{
- if ( !result_elements.empty() && base::m_parent )
+ if ( !result_elements.empty() && !base::m_traverse_data.current_is_root() )
{
// calulate node's new box
- rtree::elements(*base::m_parent)[base::m_current_child_index].first =
+ base::m_traverse_data.current_element().first =
elements_box<Box>(rtree::elements(n).begin(), rtree::elements(n).end(), base::m_translator);
}
}
@@ -223,9 +223,9 @@
inline void operator()(internal_node & n)
{
- BOOST_GEOMETRY_INDEX_ASSERT(base::m_current_level < base::m_leafs_level, "unexpected level");
+ BOOST_GEOMETRY_INDEX_ASSERT(base::m_traverse_data.current_level < base::m_leafs_level, "unexpected level");
- if ( base::m_current_level < base::m_level )
+ if ( base::m_traverse_data.current_level < base::m_level )
{
// next traversing step
base::traverse(*this, n);
@@ -235,7 +235,7 @@
{
BOOST_GEOMETRY_INDEX_ASSERT(0 < base::m_level, "illegal level value, level shouldn't be the root level for 0 < InsertIndex");
- if ( base::m_current_level == base::m_level - 1 )
+ if ( base::m_traverse_data.current_level == base::m_level - 1 )
{
base::handle_possible_reinsert_or_split_of_root(n);
}
@@ -243,7 +243,7 @@
}
else
{
- BOOST_GEOMETRY_INDEX_ASSERT(base::m_level == base::m_current_level, "unexpected level");
+ BOOST_GEOMETRY_INDEX_ASSERT(base::m_level == base::m_traverse_data.current_level, "unexpected level");
// push new child node
rtree::elements(n).push_back(base::m_element);
@@ -292,15 +292,15 @@
inline void operator()(internal_node & n)
{
- BOOST_GEOMETRY_INDEX_ASSERT(base::m_current_level < base::m_leafs_level, "unexpected level");
- BOOST_GEOMETRY_INDEX_ASSERT(base::m_current_level < base::m_level, "unexpected level");
+ BOOST_GEOMETRY_INDEX_ASSERT(base::m_traverse_data.current_level < base::m_leafs_level, "unexpected level");
+ BOOST_GEOMETRY_INDEX_ASSERT(base::m_traverse_data.current_level < base::m_level, "unexpected level");
// next traversing step
base::traverse(*this, n);
BOOST_GEOMETRY_INDEX_ASSERT(0 < base::m_level, "illegal level value, level shouldn't be the root level for 0 < InsertIndex");
- if ( base::m_current_level == base::m_level - 1 )
+ if ( base::m_traverse_data.current_level == base::m_level - 1 )
{
base::handle_possible_reinsert_or_split_of_root(n);
}
@@ -310,8 +310,11 @@
inline void operator()(leaf & n)
{
- BOOST_GEOMETRY_INDEX_ASSERT(base::m_current_level == base::m_leafs_level, "unexpected level");
- BOOST_GEOMETRY_INDEX_ASSERT(base::m_level == base::m_current_level || base::m_level == (std::numeric_limits<size_t>::max)(), "unexpected level");
+ BOOST_GEOMETRY_INDEX_ASSERT(base::m_traverse_data.current_level == base::m_leafs_level,
+ "unexpected level");
+ BOOST_GEOMETRY_INDEX_ASSERT(base::m_level == base::m_traverse_data.current_level ||
+ base::m_level == (std::numeric_limits<size_t>::max)(),
+ "unexpected level");
rtree::elements(n).push_back(base::m_element);
@@ -342,8 +345,10 @@
inline void operator()(internal_node & n)
{
- BOOST_GEOMETRY_INDEX_ASSERT(base::m_current_level < base::m_leafs_level, "unexpected level");
- BOOST_GEOMETRY_INDEX_ASSERT(base::m_current_level < base::m_level, "unexpected level");
+ BOOST_GEOMETRY_INDEX_ASSERT(base::m_traverse_data.current_level < base::m_leafs_level,
+ "unexpected level");
+ BOOST_GEOMETRY_INDEX_ASSERT(base::m_traverse_data.current_level < base::m_level,
+ "unexpected level");
// next traversing step
base::traverse(*this, n);
@@ -353,8 +358,11 @@
inline void operator()(leaf & n)
{
- BOOST_GEOMETRY_INDEX_ASSERT(base::m_current_level == base::m_leafs_level, "unexpected level");
- BOOST_GEOMETRY_INDEX_ASSERT(base::m_level == base::m_current_level || base::m_level == (std::numeric_limits<size_t>::max)(), "unexpected level");
+ BOOST_GEOMETRY_INDEX_ASSERT(base::m_traverse_data.current_level == base::m_leafs_level,
+ "unexpected level");
+ BOOST_GEOMETRY_INDEX_ASSERT(base::m_level == base::m_traverse_data.current_level ||
+ base::m_level == (std::numeric_limits<size_t>::max)(),
+ "unexpected level");
rtree::elements(n).push_back(base::m_element);
Modified: sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/visitors/insert.hpp
==============================================================================
--- sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/visitors/insert.hpp (original)
+++ sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/visitors/insert.hpp 2012-10-03 14:10:29 EDT (Wed, 03 Oct 2012)
@@ -152,6 +152,45 @@
// ----------------------------------------------------------------------- //
+template <typename InternalNode>
+struct insert_traverse_data
+{
+ typedef typename rtree::elements_type<InternalNode>::type elements_type;
+ typedef typename elements_type::value_type element_type;
+
+ insert_traverse_data()
+ : parent(0), current_child_index(0), current_level(0)
+ {}
+
+ void move_to_next_level(InternalNode * new_parent, size_t new_child_index)
+ {
+ parent = new_parent;
+ current_child_index = new_child_index;
+ ++current_level;
+ }
+
+ bool current_is_root() const
+ {
+ return 0 == parent;
+ }
+
+ elements_type & parent_elements() const
+ {
+ BOOST_GEOMETRY_INDEX_ASSERT(parent, "null pointer");
+ return rtree::elements(*parent);
+ }
+
+ element_type & current_element() const
+ {
+ BOOST_GEOMETRY_INDEX_ASSERT(parent, "null pointer");
+ return rtree::elements(*parent)[current_child_index];
+ }
+
+ InternalNode * parent;
+ size_t current_child_index;
+ size_t current_level;
+};
+
// Default insert visitor
template <typename Element, typename Value, typename Options, typename Translator, typename Box, typename Allocators>
class insert
@@ -180,9 +219,7 @@
, m_level(leafs_level - relative_level)
, m_root_node(root)
, m_leafs_level(leafs_level)
- , m_parent(0)
- , m_current_child_index(0)
- , m_current_level(0)
+ , m_traverse_data()
, m_allocators(allocators)
{
BOOST_GEOMETRY_INDEX_ASSERT(m_relative_level <= leafs_level, "unexpected level value");
@@ -197,7 +234,7 @@
{
// choose next node
size_t choosen_node_index = detail::choose_next_node<Value, Options, Box, Allocators, typename Options::choose_next_node_tag>::
- apply(n, rtree::element_indexable(m_element, m_translator), m_parameters, m_leafs_level - m_current_level);
+ apply(n, rtree::element_indexable(m_element, m_translator), m_parameters, m_leafs_level - m_traverse_data.current_level);
// expand the node to contain value
geometry::expand(
@@ -213,7 +250,8 @@
template <typename Node>
inline void post_traverse(Node &n)
{
- BOOST_GEOMETRY_INDEX_ASSERT(0 == m_parent || &n == rtree::get<Node>(rtree::elements(*m_parent)[m_current_child_index].second),
+ BOOST_GEOMETRY_INDEX_ASSERT(m_traverse_data.current_is_root() ||
+ &n == rtree::get<Node>(m_traverse_data.current_element().second),
"if node isn't the root current_child_index should be valid");
// handle overflow
@@ -227,22 +265,16 @@
inline void traverse_apply_visitor(Visitor & visitor, internal_node &n, size_t choosen_node_index)
{
// save previous traverse inputs and set new ones
- internal_node * parent_bckup = m_parent;
- size_t current_child_index_bckup = m_current_child_index;
- size_t current_level_bckup = m_current_level;
+ insert_traverse_data<internal_node> backup_traverse_data = m_traverse_data;
// calculate new traverse inputs
- m_parent = &n;
- m_current_child_index = choosen_node_index;
- ++m_current_level;
+ m_traverse_data.move_to_next_level(&n, choosen_node_index);
// next traversing step
rtree::apply_visitor(visitor, *rtree::elements(n)[choosen_node_index].second);
// restore previous traverse inputs
- m_parent = parent_bckup;
- m_current_child_index = current_child_index_bckup;
- m_current_level = current_level_bckup;
+ m_traverse_data = backup_traverse_data;
}
// TODO: consider - split result returned as OutIter is faster than reference to the container. Why?
@@ -269,12 +301,12 @@
// Implement template <node_tag> struct node_element_type or something like that
// node is not the root - just add the new node
- if ( m_parent != 0 )
+ if ( !m_traverse_data.current_is_root() )
{
// update old node's box
- rtree::elements(*m_parent)[m_current_child_index].first = n_box;
+ m_traverse_data.current_element().first = n_box;
// add new node to the parent's children
- rtree::elements(*m_parent).push_back(additional_nodes[0]);
+ m_traverse_data.parent_elements().push_back(additional_nodes[0]);
}
// node is the root - add level
else
@@ -304,9 +336,7 @@
size_t & m_leafs_level;
// traversing input parameters
- internal_node *m_parent;
- size_t m_current_child_index;
- size_t m_current_level;
+ insert_traverse_data<internal_node> m_traverse_data;
Allocators & m_allocators;
};
@@ -342,16 +372,16 @@
inline void operator()(internal_node & n)
{
- BOOST_GEOMETRY_INDEX_ASSERT(base::m_current_level < base::m_leafs_level, "unexpected level");
+ BOOST_GEOMETRY_INDEX_ASSERT(base::m_traverse_data.current_level < base::m_leafs_level, "unexpected level");
- if ( base::m_current_level < base::m_level )
+ if ( base::m_traverse_data.current_level < base::m_level )
{
// next traversing step
base::traverse(*this, n);
}
else
{
- BOOST_GEOMETRY_INDEX_ASSERT(base::m_level == base::m_current_level, "unexpected level");
+ BOOST_GEOMETRY_INDEX_ASSERT(base::m_level == base::m_traverse_data.current_level, "unexpected level");
// push new child node
rtree::elements(n).push_back(base::m_element);
@@ -391,8 +421,8 @@
inline void operator()(internal_node & n)
{
- BOOST_GEOMETRY_INDEX_ASSERT(base::m_current_level < base::m_leafs_level, "unexpected level");
- BOOST_GEOMETRY_INDEX_ASSERT(base::m_current_level < base::m_level, "unexpected level");
+ BOOST_GEOMETRY_INDEX_ASSERT(base::m_traverse_data.current_level < base::m_leafs_level, "unexpected level");
+ BOOST_GEOMETRY_INDEX_ASSERT(base::m_traverse_data.current_level < base::m_level, "unexpected level");
// next traversing step
base::traverse(*this, n);
@@ -402,8 +432,9 @@
inline void operator()(leaf & n)
{
- BOOST_GEOMETRY_INDEX_ASSERT(base::m_current_level == base::m_leafs_level, "unexpected level");
- BOOST_GEOMETRY_INDEX_ASSERT(base::m_level == base::m_current_level || base::m_level == (std::numeric_limits<size_t>::max)(), "unexpected level");
+ BOOST_GEOMETRY_INDEX_ASSERT(base::m_traverse_data.current_level == base::m_leafs_level, "unexpected level");
+ BOOST_GEOMETRY_INDEX_ASSERT(base::m_level == base::m_traverse_data.current_level ||
+ base::m_level == (std::numeric_limits<size_t>::max)(), "unexpected level");
rtree::elements(n).push_back(base::m_element);