Subject: [Boost-commit] svn:boost r84087 - in trunk/boost/geometry/index: . detail/rtree/rstar detail/rtree/visitors
From: adam.wulkiewicz_at_[hidden]
Date: 2013-04-29 16:50:02
Author: awulkiew
Date: 2013-04-29 16:50:00 EDT (Mon, 29 Apr 2013)
New Revision: 84087
URL: http://svn.boost.org/trac/boost/changeset/84087
Log:
geometry.index: edge values of some parameters handled more safely, changed order of rstar parameters.
Text files modified:
trunk/boost/geometry/index/detail/rtree/rstar/insert.hpp | 44 ++++++++++++++++++++++-------
trunk/boost/geometry/index/detail/rtree/visitors/insert.hpp | 2
trunk/boost/geometry/index/detail/rtree/visitors/remove.hpp | 4 ++
trunk/boost/geometry/index/parameters.hpp | 58 ++++++++++++++++++++++-----------------
4 files changed, 70 insertions(+), 38 deletions(-)
Modified: trunk/boost/geometry/index/detail/rtree/rstar/insert.hpp
==============================================================================
--- trunk/boost/geometry/index/detail/rtree/rstar/insert.hpp (original)
+++ trunk/boost/geometry/index/detail/rtree/rstar/insert.hpp 2013-04-29 16:50:00 EDT (Mon, 29 Apr 2013)
@@ -48,7 +48,7 @@
elements_type & elements = rtree::elements(n);
const size_t elements_count = parameters.get_max_elements() + 1;
- const size_t reinserted_elements_count = parameters.get_reinserted_elements();
+ const size_t reinserted_elements_count = (::std::min)(parameters.get_reinserted_elements(), elements_count - parameters.get_min_elements());
BOOST_GEOMETRY_INDEX_ASSERT(parent, "node shouldn't be the root node");
BOOST_GEOMETRY_INDEX_ASSERT(elements.size() == elements_count, "unexpected elements number");
@@ -466,14 +466,25 @@
{
BOOST_GEOMETRY_INDEX_ASSERT(&n == &rtree::get<internal_node>(*m_root), "current node should be the root");
- rstar::level_insert<0, Element, Value, Options, Translator, Box, Allocators> lins_v(
- m_root, m_leafs_level, m_element, m_parameters, m_translator, m_allocators, m_relative_level);
+ // Distinguish between situation when reinserts are required and use adequate visitor, otherwise use default one
+ if ( m_parameters.get_reinserted_elements() > 0 )
+ {
+ rstar::level_insert<0, Element, Value, Options, Translator, Box, Allocators> lins_v(
+ m_root, m_leafs_level, m_element, m_parameters, m_translator, m_allocators, m_relative_level);
- rtree::apply_visitor(lins_v, *m_root); // MAY THROW (V, E: alloc, copy, N: alloc)
+ rtree::apply_visitor(lins_v, *m_root); // MAY THROW (V, E: alloc, copy, N: alloc)
- if ( !lins_v.result_elements.empty() )
+ if ( !lins_v.result_elements.empty() )
+ {
+ recursive_reinsert(lins_v.result_elements, lins_v.result_relative_level); // MAY THROW (V, E: alloc, copy, N: alloc)
+ }
+ }
+ else
{
- recursive_reinsert(lins_v.result_elements, lins_v.result_relative_level); // MAY THROW (V, E: alloc, copy, N: alloc)
+ visitors::insert<Element, Value, Options, Translator, Box, Allocators, insert_default_tag> ins_v(
+ m_root, m_leafs_level, m_element, m_parameters, m_translator, m_allocators, m_relative_level);
+
+ rtree::apply_visitor(ins_v, *m_root);
}
}
@@ -481,13 +492,24 @@
{
BOOST_GEOMETRY_INDEX_ASSERT(&n == &rtree::get<leaf>(*m_root), "current node should be the root");
- rstar::level_insert<0, Element, Value, Options, Translator, Box, Allocators> lins_v(
- m_root, m_leafs_level, m_element, m_parameters, m_translator, m_allocators, m_relative_level);
+ // Distinguish between situation when reinserts are required and use adequate visitor, otherwise use default one
+ if ( m_parameters.get_reinserted_elements() > 0 )
+ {
+ rstar::level_insert<0, Element, Value, Options, Translator, Box, Allocators> lins_v(
+ m_root, m_leafs_level, m_element, m_parameters, m_translator, m_allocators, m_relative_level);
+
+ rtree::apply_visitor(lins_v, *m_root); // MAY THROW (V, E: alloc, copy, N: alloc)
- rtree::apply_visitor(lins_v, *m_root); // MAY THROW (V, E: alloc, copy, N: alloc)
+ // we're in the root, so root should be split and there should be no elements to reinsert
+ BOOST_GEOMETRY_INDEX_ASSERT(lins_v.result_elements.empty(), "unexpected state");
+ }
+ else
+ {
+ visitors::insert<Element, Value, Options, Translator, Box, Allocators, insert_default_tag> ins_v(
+ m_root, m_leafs_level, m_element, m_parameters, m_translator, m_allocators, m_relative_level);
- // we're in the root, so root should be split and there should be no elements to reinsert
- BOOST_GEOMETRY_INDEX_ASSERT(lins_v.result_elements.empty(), "unexpected state");
+ rtree::apply_visitor(ins_v, *m_root);
+ }
}
private:
Modified: trunk/boost/geometry/index/detail/rtree/visitors/insert.hpp
==============================================================================
--- trunk/boost/geometry/index/detail/rtree/visitors/insert.hpp (original)
+++ trunk/boost/geometry/index/detail/rtree/visitors/insert.hpp 2013-04-29 16:50:00 EDT (Mon, 29 Apr 2013)
@@ -413,7 +413,7 @@
inline insert(node_pointer & root,
size_t & leafs_level,
- Element & element,
+ Element const& element,
parameters_type const& parameters,
Translator const& translator,
Allocators & allocators,
Modified: trunk/boost/geometry/index/detail/rtree/visitors/remove.hpp
==============================================================================
--- trunk/boost/geometry/index/detail/rtree/visitors/remove.hpp (original)
+++ trunk/boost/geometry/index/detail/rtree/visitors/remove.hpp 2013-04-29 16:50:00 EDT (Mon, 29 Apr 2013)
@@ -145,8 +145,10 @@
// if value was removed
if ( m_is_value_removed )
{
+ BOOST_ASSERT_MSG(0 < m_parameters.get_min_elements(), "min number of elements is too small");
+
// calc underflow
- m_is_underflow = elements.size() < m_parameters.get_min_elements();
+ m_is_underflow = elements.size() < m_parameters.get_min_elements();
// n is not root - adjust aabb
if ( 0 != m_parent )
Modified: trunk/boost/geometry/index/parameters.hpp
==============================================================================
--- trunk/boost/geometry/index/parameters.hpp (original)
+++ trunk/boost/geometry/index/parameters.hpp 2013-04-29 16:50:00 EDT (Mon, 29 Apr 2013)
@@ -15,11 +15,13 @@
namespace boost { namespace geometry { namespace index {
-// TODO: awulkiew - implement those:
-//if ( m_min_elems_per_node < 1 )
-// m_min_elems_per_node = 1;
-//if ( m_max_elems_per_node < 2 )
-// m_max_elems_per_node = 2;
+// TODO: awulkiew - add asserts or exceptions?
+// 0 < MIN
+// 2 * MIN <= MAX
+// or rather MIN <= (MAX + 1) / 2 for classic variants
+// assuming that MAX is the number of elements without overflowing ones
+// and something like MIN <= (MAX + OVERFLOWING_NODES) / K for cR-tree
+// this implies 2 <= MAX for classic variants
/*!
\brief Linear r-tree creation algorithm parameters.
@@ -68,27 +70,30 @@
\tparam MaxElements Maximum number of elements in nodes.
\tparam MinElements Minimum number of elements in nodes.
-\tparam OverlapCostThreshold The number of leaf node children elements above which
- nearly minimum overlap cost is calculated instead of minimum
- overlap cost. If 0 minimum overlap cost is always calculated.
-\tparam ReinsertedElements Number of elements reinserted by forced reinsertions algorithm.
+\tparam ReinsertedElements The number of elements reinserted by forced reinsertions algorithm.
+ If 0 forced reinsertions are disabled. Maximum value is Max-Min+1.
+ Greater values are truncated.
+\tparam OverlapCostThreshold The number of most suitable leafs taken into account while choosing
+ the leaf node to which currently inserted value will be added. If
+ value is in range (0, MaxElements) - the algorithm calculates
+ nearly minimum overlap cost, otherwise all leafs are analyzed
+ and true minimum overlap cost is calculated.
*/
template <size_t MaxElements,
size_t MinElements,
- size_t OverlapCostThreshold = 0,
- size_t ReinsertedElements = detail::default_rstar_reinserted_elements_s<MaxElements>::value
- >
+ size_t ReinsertedElements = detail::default_rstar_reinserted_elements_s<MaxElements>::value,
+ size_t OverlapCostThreshold = 32>
struct rstar
{
static const size_t max_elements = MaxElements;
static const size_t min_elements = MinElements;
- static const size_t overlap_cost_threshold = OverlapCostThreshold;
static const size_t reinserted_elements = ReinsertedElements;
+ static const size_t overlap_cost_threshold = OverlapCostThreshold;
static size_t get_max_elements() { return MaxElements; }
static size_t get_min_elements() { return MinElements; }
- static size_t get_overlap_cost_threshold() { return OverlapCostThreshold; }
static size_t get_reinserted_elements() { return ReinsertedElements; }
+ static size_t get_overlap_cost_threshold() { return OverlapCostThreshold; }
};
//template <size_t MaxElements, size_t MinElements>
@@ -168,35 +173,38 @@
\param max_elements Maximum number of elements in nodes.
\param min_elements Minimum number of elements in nodes.
- \param overlap_cost_threshold The number of leaf node children elements above which
- nearly minimum overlap cost is calculated instead of minimum
- overlap cost. If 0 minimum overlap cost is always calculated.
- \param reinserted_elements Number of elements reinserted by forced reinsertions algorithm.
+ \param reinserted_elements The number of elements reinserted by forced reinsertions algorithm.
+ If 0 forced reinsertions are disabled. Maximum value is Max-Min+1.
+ Greater values are truncated.
+ \param overlap_cost_threshold The number of most suitable leafs taken into account while choosing
+ the leaf node to which currently inserted value will be added. If
+ value is in range (0, MaxElements) - the algorithm calculates
+ nearly minimum overlap cost, otherwise all leafs are analyzed
+ and true minimum overlap cost is calculated.
*/
dynamic_rstar(size_t max_elements,
size_t min_elements,
- size_t overlap_cost_threshold = 0,
- size_t reinserted_elements = detail::default_rstar_reinserted_elements_d())
+ size_t reinserted_elements = detail::default_rstar_reinserted_elements_d(),
+ size_t overlap_cost_threshold = 32)
: m_max_elements(max_elements)
, m_min_elements(min_elements)
- , m_overlap_cost_threshold(overlap_cost_threshold)
, m_reinserted_elements(
detail::default_rstar_reinserted_elements_d() == reinserted_elements ?
(max_elements * 3) / 10 :
- reinserted_elements
- )
+ reinserted_elements )
+ , m_overlap_cost_threshold(overlap_cost_threshold)
{}
size_t get_max_elements() const { return m_max_elements; }
size_t get_min_elements() const { return m_min_elements; }
- size_t get_overlap_cost_threshold() const { return m_overlap_cost_threshold; }
size_t get_reinserted_elements() const { return m_reinserted_elements; }
+ size_t get_overlap_cost_threshold() const { return m_overlap_cost_threshold; }
private:
size_t m_max_elements;
size_t m_min_elements;
- size_t m_overlap_cost_threshold;
size_t m_reinserted_elements;
+ size_t m_overlap_cost_threshold;
};
}}} // namespace boost::geometry::index