[Boost-commit] svn:boost r84724 - trunk/boost/geometry/index/detail/rtree

Subject: [Boost-commit] svn:boost r84724 - trunk/boost/geometry/index/detail/rtree
From: adam.wulkiewicz_at_[hidden]
Date: 2013-06-10 09:53:08

Author: awulkiew
Date: 2013-06-10 09:53:07 EDT (Mon, 10 Jun 2013)
New Revision: 84724
URL: http://svn.boost.org/trac/boost/changeset/84724

Log:
geometry.index: packer - nodes counts container removed. counts are calculated when needed, subtree_counts pair replaced by struct with descriptive members and trivial copy.

Text files modified: 
   trunk/boost/geometry/index/detail/rtree/pack_create.hpp |   148 ++++++++++++++++++++++----------------- 
   1 files changed, 82 insertions(+), 66 deletions(-)

Modified: trunk/boost/geometry/index/detail/rtree/pack_create.hpp
==============================================================================
--- trunk/boost/geometry/index/detail/rtree/pack_create.hpp	Mon Jun 10 08:31:38 2013	(r84723)
+++ trunk/boost/geometry/index/detail/rtree/pack_create.hpp	2013-06-10 09:53:07 EDT (Mon, 10 Jun 2013)	(r84724)
@@ -156,19 +156,26 @@
             entries.push_back(std::make_pair(pt, first));
         }
 
-        std::pair<std::size_t, std::size_t> subtree_counts = subtree_elements_counts(count);
+        subtree_elements_counts subtree_counts = calculate_subtree_elements_counts(count);
         internal_element el = per_level(entries.begin(), entries.end(), hint_box, count, subtree_counts);
         return el.second;
     }
 
 private:
+    struct subtree_elements_counts
+    {
+        subtree_elements_counts(std::size_t ma, std::size_t mi) : maxc(ma), minc(mi) {}
+        std::size_t maxc;
+        std::size_t minc;
+    };
+
     template <typename EIt>
-    internal_element per_level(EIt first, EIt last, Box const& hint_box, std::size_t count, std::pair<std::size_t, std::size_t> const& subtree_counts)
+    internal_element per_level(EIt first, EIt last, Box const& hint_box, std::size_t count, subtree_elements_counts const& subtree_counts)
     {
         // remove it later
         BOOST_ASSERT(first <= last); BOOST_ASSERT(last - first == count);
 
-        if ( subtree_counts.first <= 1 )
+        if ( subtree_counts.maxc <= 1 )
         {
             // ROOT or LEAF
             BOOST_ASSERT(count <= m_parameters.get_max_elements());
@@ -190,57 +197,52 @@
             return internal_element(elements_box, n);
         }
 
-        // calculate numbers of values in subtrees
-        values_counts_container values_counts;
-        calculate_nodes_counts(values_counts, count, subtree_counts);                                       // MAY THROW (A)
-        BOOST_ASSERT(are_nodes_counts_ok(values_counts, count, subtree_counts));
-        
         // calculate next max and min subtree counts
-        std::pair<std::size_t, std::size_t> next_subtree_counts = subtree_counts;
-        next_subtree_counts.first /= m_parameters.get_max_elements();
-        next_subtree_counts.second /= m_parameters.get_max_elements();
+        subtree_elements_counts next_subtree_counts = subtree_counts;
+        next_subtree_counts.maxc /= m_parameters.get_max_elements();
+        next_subtree_counts.minc /= m_parameters.get_max_elements();
 
         // create new internal node
         node_pointer n = rtree::create_node<Allocators, internal_node>::apply(m_allocators);                // MAY THROW (A)
         internal_node & in = rtree::get<internal_node>(*n);
         // reserve space for values
-        rtree::elements(in).reserve(values_counts.size());                                                  // MAY THROW (A)
+        rtree::elements(in).reserve(calculate_nodes_count(count, subtree_counts));                          // MAY THROW (A)
         // calculate values box and copy values
         Box elements_box;
         geometry::assign_inverse(elements_box);
 
-        per_level_packets(first, last, values_counts.begin(), values_counts.end(),
-                          hint_box, next_subtree_counts,
+        per_level_packets(first, last,
+                          hint_box,
+                          subtree_counts,
+                          next_subtree_counts,
                           rtree::elements(in), elements_box);
 
         return internal_element(elements_box, n);
     }
 
-    template <typename EIt, typename CIt>
-    void per_level_packets(EIt first, EIt last, CIt counts_first, CIt counts_last,
+    template <typename EIt>
+    void per_level_packets(EIt first, EIt last,
                            Box const& hint_box,
-                           std::pair<std::size_t, std::size_t> const& next_subtree_counts,
+                           subtree_elements_counts const& subtree_counts,
+                           subtree_elements_counts const& next_subtree_counts,
                            internal_elements & elements, Box & elements_box)
     {
-        std::size_t packets_count = counts_last - counts_first;
+        std::size_t values_count = last - first;
 
-        BOOST_ASSERT( 0 < packets_count );
+        BOOST_ASSERT_MSG( subtree_counts.minc <= values_count );
 
-        if ( 1 == packets_count )
+        // only one packet
+        if ( values_count <= subtree_counts.maxc )
         {
             // the end, move to the next level
-            internal_element el = per_level(first, last, hint_box, *counts_first, next_subtree_counts);
+            internal_element el = per_level(first, last, hint_box, values_count, next_subtree_counts);
+            // this container should have memory allocated, reserve() called outside
             elements.push_back(el);                                                                         // SHOULDN'T THROW (C)
             geometry::expand(elements_box, el.first);
             return;
         }
         
-        CIt counts_median = counts_first + packets_count / 2;
-        std::size_t left_sum = 0;
-        for ( CIt it = counts_first ; it != counts_median ; ++it )
-            left_sum += *it;
-
-        EIt median = first + left_sum;
+        EIt median = first + calculate_median_count(values_count, subtree_counts);
 
         coordinate_type greatest_length;
         std::size_t greatest_dim_index = 0;
@@ -249,67 +251,81 @@
         pack_utils::partial_sort_and_half_boxes<0, dimension>
             ::apply(first, median, last, hint_box, left, right, greatest_dim_index);
         
-        per_level_packets(first, median, counts_first, counts_median, left, next_subtree_counts, elements, elements_box);
-        per_level_packets(median, last, counts_median, counts_last, right, next_subtree_counts, elements, elements_box);
+        per_level_packets(first, median, left, subtree_counts, next_subtree_counts, elements, elements_box);
+        per_level_packets(median, last, right, subtree_counts, next_subtree_counts, elements, elements_box);
     }
 
-    std::pair<std::size_t, std::size_t> subtree_elements_counts(std::size_t elements_count)
+    subtree_elements_counts calculate_subtree_elements_counts(std::size_t elements_count)
     {
-        std::pair<std::size_t, std::size_t> res = std::make_pair(1, 1);
+        subtree_elements_counts res(1, 1);
 
         std::size_t smax = m_parameters.get_max_elements();
-        std::size_t smin = m_parameters.get_min_elements();
+        for ( ; smax < elements_count ; smax *= m_parameters.get_max_elements() )
+            res.maxc = smax;
 
-        for ( ; smax < elements_count ; smax *= m_parameters.get_max_elements(), smin *= m_parameters.get_max_elements() )
-        {
-            res.first = smax;
-            res.second = smin;
-        }
+        res.minc = m_parameters.get_min_elements() * (res.maxc / m_parameters.get_max_elements());
 
         return res;
     }
 
-    void calculate_nodes_counts(values_counts_container & values_counts,
-                                std::size_t count,
-                                std::pair<std::size_t, std::size_t> const& subtree_counts)
+    std::size_t calculate_nodes_count(std::size_t count,
+                                      subtree_elements_counts const& subtree_counts)
     {
-        // e.g. for max = 5, min = 2, count = 52, subtree_max = 25, subtree_min = 10
-
-        std::size_t n = count / subtree_counts.first; // e.g. 52 / 25 = 2
-        std::size_t r = count % subtree_counts.first; // e.g. 52 % 25 = 2
-        bool is_min_node = false;
+        std::size_t n = count / subtree_counts.maxc;
+        std::size_t r = count % subtree_counts.maxc;
 
-        if ( 0 < r && r < subtree_counts.second ) // 2 < 10
+        if ( 0 < r && r < subtree_counts.minc )
         {
-            is_min_node = true;
-            std::size_t count_minus_min = count - subtree_counts.second; // e.g. 52 - 10 = 42
-            n = count_minus_min / subtree_counts.first; // e.g. 42 / 25 = 1
-            r = count_minus_min % subtree_counts.first; // e.g. 42 % 25 = 17
+            std::size_t count_minus_min = count - subtree_counts.minc;
+            n = count_minus_min / subtree_counts.maxc;
+            r = count_minus_min % subtree_counts.maxc;
+            ++n;
         }
 
-        values_counts.resize(n, subtree_counts.first);                                                          // MAY THROW (A)
         if ( 0 < r )
-            values_counts.push_back(r);                                                                         // MAY THROW (A)
-        if ( is_min_node )
-            values_counts.push_back(subtree_counts.second);                                                     // MAY THROW (A)
+            ++n;
+
+        return n;
     }
 
-    bool are_nodes_counts_ok(values_counts_container const& values_counts,
-                             std::size_t count,
-                             std::pair<std::size_t, std::size_t> const& subtree_counts)
+    std::size_t calculate_median_count(std::size_t count,
+                                       subtree_elements_counts const& subtree_counts)
     {
-        std::size_t sum = 0;
+        // e.g. for max = 5, min = 2, count = 52, subtree_max = 25, subtree_min = 10
 
-        for(std::size_t i = 0 ; i < values_counts.size() ; ++i )
+        std::size_t n = count / subtree_counts.maxc; // e.g. 52 / 25 = 2
+        std::size_t r = count % subtree_counts.maxc; // e.g. 52 % 25 = 2
+        std::size_t median_count = (n / 2) * subtree_counts.maxc; // e.g. 2 / 2 * 25 = 25
+
+        if ( 0 != r ) // e.g. 0 != 2
         {
-            std::size_t c = values_counts[i];
-            sum += c;
-            if ( c < subtree_counts.second || subtree_counts.first < c )
-                return false;
+            if ( subtree_counts.minc <= r ) // e.g. 10 <= 2 == false
+            {
+                //BOOST_ASSERT_MSG(0 < n, "unexpected value");
+                median_count = ((n+1)/2) * subtree_counts.maxc; // if calculated ((2+1)/2) * 25 which would be ok, but not in all cases
+            }
+            else // r < subtree_counts.second  // e.g. 2 < 10 == true
+            {
+                std::size_t count_minus_min = count - subtree_counts.minc; // e.g. 52 - 10 = 42
+                n = count_minus_min / subtree_counts.maxc; // e.g. 42 / 25 = 1
+                r = count_minus_min % subtree_counts.maxc; // e.g. 42 % 25 = 17
+                if ( r == 0 )                               // e.g. false
+                {
+                    // n can't be equal to 0 because then there wouldn't be any element in the other node
+                    //BOOST_ASSERT_MSG(0 < n, "unexpected value");
+                    median_count = ((n+1)/2) * subtree_counts.maxc;     // if calculated ((1+1)/2) * 25 which would be ok, but not in all cases
+                }
+                else
+                {
+                    if ( n == 0 )                                        // e.g. false
+                        median_count = r;                                // if calculated -> 17 which is wrong!
+                    else
+                        median_count = ((n+2)/2) * subtree_counts.maxc; // e.g. ((1+2)/2) * 25 = 25
+                }
+            }
         }
-        if ( sum != count )
-            return false;
-        return true;
+
+        return median_count;
     }
 
     parameters_type const& m_parameters;