[Boost-commit] svn:boost r84087 - in trunk/boost/geometry/index: . detail/rtree/rstar detail/rtree/visitors

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