comparison DEPENDENCIES/generic/include/boost/geometry/index/detail/rtree/pack_create.hpp @ 101:c530137014c0

Update Boost headers (1.58.0)

 // Boost.Geometry Index
 //
 // R-tree initial packing
 //
-// Copyright (c) 2011-2013 Adam Wulkiewicz, Lodz, Poland.
+// Copyright (c) 2011-2015 Adam Wulkiewicz, Lodz, Poland.
 //
 // Use, modification and distribution is subject to the Boost Software License,
 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
 // http://www.boost.org/LICENSE_1_0.txt)
 

         return geometry::get<I>(e1.first) < geometry::get<I>(e2.first);
     }
 };
 
 template <std::size_t I, std::size_t Dimension>
-struct partial_sort_and_half_boxes
+struct nth_element_and_half_boxes
 {
     template <typename EIt, typename Box>
     static inline void apply(EIt first, EIt median, EIt last, Box const& box, Box & left, Box & right, std::size_t dim_index)
     {
         if ( I == dim_index )
         {
-            std::partial_sort(first, median, last, point_entries_comparer<I>());
+            std::nth_element(first, median, last, point_entries_comparer<I>());
 
             geometry::convert(box, left);
             geometry::convert(box, right);
             typename coordinate_type<Box>::type edge_len
                 = geometry::get<max_corner, I>(box) - geometry::get<min_corner, I>(box);

                 = geometry::get<min_corner, I>(box) + edge_len / 2;
             geometry::set<max_corner, I>(left, median);
             geometry::set<min_corner, I>(right, median);
         }
         else
-            partial_sort_and_half_boxes<I+1, Dimension>::apply(first, median, last, box, left, right, dim_index);
+            nth_element_and_half_boxes<I+1, Dimension>::apply(first, median, last, box, left, right, dim_index);
     }
 };
 
 template <std::size_t Dimension>
-struct partial_sort_and_half_boxes<Dimension, Dimension>
+struct nth_element_and_half_boxes<Dimension, Dimension>
 {
     template <typename EIt, typename Box>
     static inline void apply(EIt , EIt , EIt , Box const& , Box & , Box & , std::size_t ) {}
 };
 

     typedef typename rtree::node<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type node;
     typedef typename rtree::internal_node<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type internal_node;
     typedef typename rtree::leaf<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type leaf;
 
     typedef typename Allocators::node_pointer node_pointer;
-    typedef rtree::node_auto_ptr<Value, Options, Translator, Box, Allocators> node_auto_ptr;
+    typedef rtree::subtree_destroyer<Value, Options, Translator, Box, Allocators> subtree_destroyer;
     typedef typename Allocators::size_type size_type;
 
-    typedef typename traits::point_type<Box>::type point_type;
-    typedef typename traits::coordinate_type<point_type>::type coordinate_type;
+    typedef typename geometry::point_type<Box>::type point_type;
+    typedef typename geometry::coordinate_type<point_type>::type coordinate_type;
     typedef typename detail::default_content_result<Box>::type content_type;
     typedef typename Options::parameters_type parameters_type;
-    static const std::size_t dimension = traits::dimension<point_type>::value;
+    static const std::size_t dimension = geometry::dimension<point_type>::value;
 
     typedef typename rtree::container_from_elements_type<
         typename rtree::elements_type<leaf>::type,
         std::size_t
     >::type values_counts_container;

         
         Box hint_box;
         geometry::assign_inverse(hint_box);
         for ( ; first != last ; ++first )
         {
-            geometry::expand(hint_box, translator(*first));
+            // NOTE: support for iterators not returning true references adapted
+            // to Geometry concept and default translator returning true reference
+            // An alternative would be to dereference the iterator and translate
+            // in one expression each time the indexable was needed.
+            typename std::iterator_traits<InIt>::reference in_ref = *first;
+            typename Translator::result_type indexable = translator(in_ref);
+
+            // NOTE: added for consistency with insert()
+            // CONSIDER: alternative - ignore invalid indexable or throw an exception
+            BOOST_GEOMETRY_INDEX_ASSERT(detail::is_valid(indexable), "Indexable is invalid");
+
+            geometry::expand(hint_box, indexable);
 
             point_type pt;
-            geometry::centroid(translator(*first), pt);
+            geometry::centroid(indexable, pt);
             entries.push_back(std::make_pair(pt, first));
         }
 
         subtree_elements_counts subtree_counts = calculate_subtree_elements_counts(values_count, parameters, leafs_level);
         internal_element el = per_level(entries.begin(), entries.end(), hint_box, values_count, subtree_counts,

 
     template <typename EIt> inline static
     internal_element per_level(EIt first, EIt last, Box const& hint_box, std::size_t values_count, subtree_elements_counts const& subtree_counts,
                                parameters_type const& parameters, Translator const& translator, Allocators & allocators)
     {
-        BOOST_ASSERT(0 < std::distance(first, last) && static_cast<std::size_t>(std::distance(first, last)) == values_count);
+        BOOST_GEOMETRY_INDEX_ASSERT(0 < std::distance(first, last) && static_cast<std::size_t>(std::distance(first, last)) == values_count,
+                                    "unexpected parameters");
 
         if ( subtree_counts.maxc <= 1 )
         {
             // ROOT or LEAF
-            BOOST_ASSERT(values_count <= parameters.get_max_elements());
+            BOOST_GEOMETRY_INDEX_ASSERT(values_count <= parameters.get_max_elements(),
+                                        "too big number of elements");
             // if !root check m_parameters.get_min_elements() <= count
 
             // create new leaf node
             node_pointer n = rtree::create_node<Allocators, leaf>::apply(allocators);                       // MAY THROW (A)
-            node_auto_ptr auto_remover(n, allocators);
+            subtree_destroyer auto_remover(n, allocators);
             leaf & l = rtree::get<leaf>(*n);
 
             // reserve space for values
             rtree::elements(l).reserve(values_count);                                                       // MAY THROW (A)
             // calculate values box and copy values
             Box elements_box;
             geometry::assign_inverse(elements_box);
             for ( ; first != last ; ++first )
             {
+                // NOTE: push_back() must be called at the end in order to support move_iterator.
+                //       The iterator is dereferenced 2x (no temporary reference) to support
+                //       non-true reference types and move_iterator without boost::forward<>.
+                geometry::expand(elements_box, translator(*(first->second)));
                 rtree::elements(l).push_back(*(first->second));                                             // MAY THROW (A?,C)
-                geometry::expand(elements_box, translator(*(first->second)));
             }
 
             auto_remover.release();
             return internal_element(elements_box, n);
         }

         next_subtree_counts.maxc /= parameters.get_max_elements();
         next_subtree_counts.minc /= parameters.get_max_elements();
 
         // create new internal node
         node_pointer n = rtree::create_node<Allocators, internal_node>::apply(allocators);                  // MAY THROW (A)
-        node_auto_ptr auto_remover(n, allocators);
+        subtree_destroyer auto_remover(n, allocators);
         internal_node & in = rtree::get<internal_node>(*n);
 
         // reserve space for values
         std::size_t nodes_count = calculate_nodes_count(values_count, subtree_counts);
         rtree::elements(in).reserve(nodes_count);                                                           // MAY THROW (A)

                            subtree_elements_counts const& subtree_counts,
                            subtree_elements_counts const& next_subtree_counts,
                            internal_elements & elements, Box & elements_box,
                            parameters_type const& parameters, Translator const& translator, Allocators & allocators)
     {
-        BOOST_ASSERT(0 < std::distance(first, last) && static_cast<std::size_t>(std::distance(first, last)) == values_count);
-
-        BOOST_ASSERT_MSG( subtree_counts.minc <= values_count, "too small number of elements");
+        BOOST_GEOMETRY_INDEX_ASSERT(0 < std::distance(first, last) && static_cast<std::size_t>(std::distance(first, last)) == values_count,
+                                    "unexpected parameters");
+
+        BOOST_GEOMETRY_INDEX_ASSERT(subtree_counts.minc <= values_count,
+                                    "too small number of elements");
 
         // only one packet
         if ( values_count <= subtree_counts.maxc )
         {
             // the end, move to the next level

                                             parameters, translator, allocators);
 
             // in case if push_back() do throw here
             // and even if this is not probable (previously reserved memory, nonthrowing pairs copy)
             // this case is also tested by exceptions test.
-            node_auto_ptr auto_remover(el.second, allocators);
+            subtree_destroyer auto_remover(el.second, allocators);
             // this container should have memory allocated, reserve() called outside
             elements.push_back(el);                                                 // MAY THROW (A?,C) - however in normal conditions shouldn't
             auto_remover.release();
 
             geometry::expand(elements_box, el.first);

 
         coordinate_type greatest_length;
         std::size_t greatest_dim_index = 0;
         pack_utils::biggest_edge<dimension>::apply(hint_box, greatest_length, greatest_dim_index);
         Box left, right;
-        pack_utils::partial_sort_and_half_boxes<0, dimension>
+        pack_utils::nth_element_and_half_boxes<0, dimension>
             ::apply(first, median, last, hint_box, left, right, greatest_dim_index);
         
         per_level_packets(first, median, left,
                           median_count, subtree_counts, next_subtree_counts,
                           elements, elements_box,

     }
 
     inline static
     subtree_elements_counts calculate_subtree_elements_counts(std::size_t elements_count, parameters_type const& parameters, size_type & leafs_level)
     {
-        (void)parameters;
+        boost::ignore_unused_variable_warning(parameters);
 
         subtree_elements_counts res(1, 1);
         leafs_level = 0;
 
         std::size_t smax = parameters.get_max_elements();

 
         if ( 0 != r ) // e.g. 0 != 2
         {
             if ( subtree_counts.minc <= r ) // e.g. 10 <= 2 == false
             {
-                //BOOST_ASSERT_MSG(0 < n, "unexpected value");
+                //BOOST_GEOMETRY_INDEX_ASSERT(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");
+                    //BOOST_GEOMETRY_INDEX_ASSERT(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