[ceph.git] / ceph / src / boost / boost / geometry / index / detail / rtree / pack_create.hpp

// Boost.Geometry Index
//
// R-tree initial packing
//
// Copyright (c) 2011-2017 Adam Wulkiewicz, Lodz, Poland.
// Copyright (c) 2020 Caian Benedicto, Campinas, Brazil.
//
// This file was modified by Oracle on 2019.
// Modifications copyright (c) 2019 Oracle and/or its affiliates.
// Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
//
// 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)

#ifndef BOOST_GEOMETRY_INDEX_DETAIL_RTREE_PACK_CREATE_HPP
#define BOOST_GEOMETRY_INDEX_DETAIL_RTREE_PACK_CREATE_HPP

#include <boost/core/ignore_unused.hpp>

#include <boost/geometry/algorithms/expand.hpp>
#include <boost/geometry/index/detail/algorithms/bounds.hpp>
#include <boost/geometry/index/detail/algorithms/nth_element.hpp>
#include <boost/geometry/index/detail/rtree/node/subtree_destroyer.hpp>

#include <boost/geometry/algorithms/detail/expand_by_epsilon.hpp>

namespace boost { namespace geometry { namespace index { namespace detail { namespace rtree {

namespace pack_utils {

template <std::size_t Dimension>
struct biggest_edge
{
    BOOST_STATIC_ASSERT(0 < Dimension);
    template <typename Box>
    static inline void apply(Box const& box, typename coordinate_type<Box>::type & length, std::size_t & dim_index)
    {
        biggest_edge<Dimension-1>::apply(box, length, dim_index);
        typename coordinate_type<Box>::type curr
            = geometry::get<max_corner, Dimension-1>(box) - geometry::get<min_corner, Dimension-1>(box);
        if ( length < curr )
        {
            dim_index = Dimension - 1;
            length = curr;
        }
    }
};

template <>
struct biggest_edge<1>
{
    template <typename Box>
    static inline void apply(Box const& box, typename coordinate_type<Box>::type & length, std::size_t & dim_index)
    {
        dim_index = 0;
        length = geometry::get<max_corner, 0>(box) - geometry::get<min_corner, 0>(box);
    }
};

template <std::size_t I>
struct point_entries_comparer
{
    template <typename PointEntry>
    bool operator()(PointEntry const& e1, PointEntry const& e2) const
    {
        return geometry::get<I>(e1.first) < geometry::get<I>(e2.first);
    }
};

template <std::size_t I, std::size_t Dimension>
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 )
        {
            index::detail::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);
            typename coordinate_type<Box>::type median
                = geometry::get<min_corner, I>(box) + edge_len / 2;
            geometry::set<max_corner, I>(left, median);
            geometry::set<min_corner, I>(right, median);
        }
        else
            nth_element_and_half_boxes<I+1, Dimension>::apply(first, median, last, box, left, right, dim_index);
    }
};

template <std::size_t 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 ) {}
};

} // namespace pack_utils

// STR leafs number are calculated as rcount/max
// and the number of splitting planes for each dimension as (count/max)^(1/dimension)
// <-> for dimension==2 -> sqrt(count/max)
//
// The main flaw of this algorithm is that the resulting tree will have bad structure for:
// 1. non-uniformly distributed elements
//      Statistic check could be performed, e.g. based on variance of lengths of elements edges for each dimension
// 2. elements distributed mainly along one axis
//      Calculate bounding box of all elements and then number of dividing planes for a dimension
//      from the length of BB edge for this dimension (more or less assuming that elements are uniformly-distributed squares)
//
// Another thing is that the last node may have less elements than Max or even Min.
// The number of splitting planes must be chosen more carefully than count/max
//
// This algorithm is something between STR and TGS
// it is more similar to the top-down recursive kd-tree creation algorithm
// using object median split and split axis of greatest BB edge
// BB is only used as a hint (assuming objects are distributed uniformly)
//
// Implemented algorithm guarantees that the number of elements in nodes will be between Min and Max
// and that nodes are packed as tightly as possible
// e.g. for 177 values Max = 5 and Min = 2 it will construct the following tree:
// ROOT                 177
// L1          125               52
// L2  25  25  25  25  25   25  17    10
// L3  5x5 5x5 5x5 5x5 5x5  5x5 3x5+2 2x5

template <typename MembersHolder>
class pack
{
    typedef typename MembersHolder::node node;
    typedef typename MembersHolder::internal_node internal_node;
    typedef typename MembersHolder::leaf leaf;

    typedef typename MembersHolder::node_pointer node_pointer;
    typedef typename MembersHolder::size_type size_type;
    typedef typename MembersHolder::parameters_type parameters_type;
    typedef typename MembersHolder::translator_type translator_type;
    typedef typename MembersHolder::allocators_type allocators_type;

    typedef typename MembersHolder::box_type box_type;
    typedef typename geometry::point_type<box_type>::type point_type;
    typedef typename geometry::coordinate_type<point_type>::type coordinate_type;
    typedef typename detail::default_content_result<box_type>::type content_type;
    typedef typename detail::strategy_type<parameters_type>::type strategy_type;
    static const std::size_t dimension = geometry::dimension<point_type>::value;

    typedef typename rtree::container_from_elements_type<
        typename rtree::elements_type<leaf>::type,
        size_type
    >::type values_counts_container;

    typedef typename rtree::elements_type<internal_node>::type internal_elements;
    typedef typename internal_elements::value_type internal_element;

    typedef rtree::subtree_destroyer<MembersHolder> subtree_destroyer;

public:
    // Arbitrary iterators
    template <typename InIt> inline static
    node_pointer apply(InIt first, InIt last,
                       size_type & values_count,
                       size_type & leafs_level,
                       parameters_type const& parameters,
                       translator_type const& translator,
                       allocators_type & allocators)
    {
        return apply(first, last, values_count, leafs_level, parameters, translator,
                     allocators, boost::container::new_allocator<void>());
    }

    template <typename InIt, typename TmpAlloc> inline static
    node_pointer apply(InIt first, InIt last,
                       size_type & values_count,
                       size_type & leafs_level,
                       parameters_type const& parameters,
                       translator_type const& translator,
                       allocators_type & allocators,
                       TmpAlloc const& temp_allocator)
    {
        typedef typename std::iterator_traits<InIt>::difference_type diff_type;
            
        diff_type diff = std::distance(first, last);
        if ( diff <= 0 )
            return node_pointer(0);

        typedef std::pair<point_type, InIt> entry_type;
        typedef typename boost::container::allocator_traits<TmpAlloc>::
            template rebind_alloc<entry_type> temp_entry_allocator_type;

        temp_entry_allocator_type temp_entry_allocator(temp_allocator);
        boost::container::vector<entry_type, temp_entry_allocator_type> entries(temp_entry_allocator);

        values_count = static_cast<size_type>(diff);
        entries.reserve(values_count);
        
        expandable_box<box_type, strategy_type> hint_box(detail::get_strategy(parameters));
        for ( ; first != last ; ++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_type::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");

            hint_box.expand(indexable);

            point_type 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.get(), values_count, subtree_counts,
                                        parameters, translator, allocators);

        return el.second;
    }

private:
    template <typename BoxType, typename Strategy>
    class expandable_box
    {
    public:
        explicit expandable_box(Strategy const& strategy)
            : m_strategy(strategy), m_initialized(false)
        {}

        template <typename Indexable>
        explicit expandable_box(Indexable const& indexable, Strategy const& strategy)
            : m_strategy(strategy), m_initialized(true)
        {
            detail::bounds(indexable, m_box, m_strategy);
        }

        template <typename Indexable>
        void expand(Indexable const& indexable)
        {
            if ( !m_initialized )
            {
                // it's guaranteed that the Box will be initialized
                // only for Points, Boxes and Segments but that's ok
                // since only those Geometries can be stored
                detail::bounds(indexable, m_box, m_strategy);
                m_initialized = true;
            }
            else
            {
                detail::expand(m_box, indexable, m_strategy);
            }
        }

        void expand_by_epsilon()
        {
            geometry::detail::expand_by_epsilon(m_box);
        }

        BoxType const& get() const
        {
            BOOST_GEOMETRY_INDEX_ASSERT(m_initialized, "uninitialized envelope accessed");
            return m_box;
        }

    private:
        BoxType m_box;
        Strategy m_strategy;
        bool m_initialized;
    };

    struct subtree_elements_counts
    {
        subtree_elements_counts(size_type ma, size_type mi) : maxc(ma), minc(mi) {}
        size_type maxc;
        size_type minc;
    };

    template <typename EIt> inline static
    internal_element per_level(EIt first, EIt last,
                               box_type const& hint_box,
                               size_type values_count,
                               subtree_elements_counts const& subtree_counts,
                               parameters_type const& parameters,
                               translator_type const& translator,
                               allocators_type & allocators)
    {
        BOOST_GEOMETRY_INDEX_ASSERT(0 < std::distance(first, last) && static_cast<size_type>(std::distance(first, last)) == values_count,
                                    "unexpected parameters");

        if ( subtree_counts.maxc <= 1 )
        {
            // ROOT or LEAF
            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_type, leaf>::apply(allocators);                       // MAY THROW (A)
            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
            //   initialize the box explicitly to avoid GCC-4.4 uninitialized variable warnings with O2
            expandable_box<box_type, strategy_type> elements_box(translator(*(first->second)),
                                                                 detail::get_strategy(parameters));
            rtree::elements(l).push_back(*(first->second));                                                 // MAY THROW (A?,C)
            for ( ++first ; 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<>.
                elements_box.expand(translator(*(first->second)));
                rtree::elements(l).push_back(*(first->second));                                             // MAY THROW (A?,C)
            }

#ifdef BOOST_GEOMETRY_INDEX_EXPERIMENTAL_ENLARGE_BY_EPSILON
            // Enlarge bounds of a leaf node.
            // It's because Points and Segments are compared WRT machine epsilon
            // This ensures that leafs bounds correspond to the stored elements
            // NOTE: this is done only if the Indexable is a different kind of Geometry
            //   than the bounds (only Box for now). Spatial predicates are checked
            //   the same way for Geometry of the same kind.
            if ( BOOST_GEOMETRY_CONDITION((
                    ! index::detail::is_bounding_geometry
                        <
                            typename indexable_type<translator_type>::type
                        >::value )) )
            {
                elements_box.expand_by_epsilon();
            }
#endif

            auto_remover.release();
            return internal_element(elements_box.get(), n);
        }

        // calculate next max and min subtree counts
        subtree_elements_counts next_subtree_counts = subtree_counts;
        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_type, internal_node>::apply(allocators);                  // MAY THROW (A)
        subtree_destroyer auto_remover(n, allocators);
        internal_node & in = rtree::get<internal_node>(*n);

        // reserve space for values
        size_type nodes_count = calculate_nodes_count(values_count, subtree_counts);
        rtree::elements(in).reserve(nodes_count);                                                           // MAY THROW (A)
        // calculate values box and copy values
        expandable_box<box_type, strategy_type> elements_box(detail::get_strategy(parameters));
        
        per_level_packets(first, last, hint_box, values_count, subtree_counts, next_subtree_counts,
                          rtree::elements(in), elements_box,
                          parameters, translator, allocators);

        auto_remover.release();
        return internal_element(elements_box.get(), n);
    }

    template <typename EIt, typename ExpandableBox> inline static
    void per_level_packets(EIt first, EIt last,
                           box_type const& hint_box,
                           size_type values_count,
                           subtree_elements_counts const& subtree_counts,
                           subtree_elements_counts const& next_subtree_counts,
                           internal_elements & elements,
                           ExpandableBox & elements_box,
                           parameters_type const& parameters,
                           translator_type const& translator,
                           allocators_type & allocators)
    {
        BOOST_GEOMETRY_INDEX_ASSERT(0 < std::distance(first, last) && static_cast<size_type>(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
            internal_element el = per_level(first, last, hint_box, values_count, next_subtree_counts,
                                            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.
            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();

            elements_box.expand(el.first);
            return;
        }
        
        size_type median_count = calculate_median_count(values_count, subtree_counts);
        EIt median = first + median_count;

        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_type left, right;
        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,
                          parameters, translator, allocators);
        per_level_packets(median, last, right,
                          values_count - median_count, subtree_counts, next_subtree_counts,
                          elements, elements_box,
                          parameters, translator, allocators);
    }

    inline static
    subtree_elements_counts calculate_subtree_elements_counts(size_type elements_count, parameters_type const& parameters, size_type & leafs_level)
    {
        boost::ignore_unused(parameters);

        subtree_elements_counts res(1, 1);
        leafs_level = 0;

        size_type smax = parameters.get_max_elements();
        for ( ; smax < elements_count ; smax *= parameters.get_max_elements(), ++leafs_level )
            res.maxc = smax;

        res.minc = parameters.get_min_elements() * (res.maxc / parameters.get_max_elements());

        return res;
    }

    inline static
    size_type calculate_nodes_count(size_type count,
                                    subtree_elements_counts const& subtree_counts)
    {
        size_type n = count / subtree_counts.maxc;
        size_type r = count % subtree_counts.maxc;

        if ( 0 < r && r < subtree_counts.minc )
        {
            size_type count_minus_min = count - subtree_counts.minc;
            n = count_minus_min / subtree_counts.maxc;
            r = count_minus_min % subtree_counts.maxc;
            ++n;
        }

        if ( 0 < r )
            ++n;

        return n;
    }

    inline static
    size_type calculate_median_count(size_type count,
                                     subtree_elements_counts const& subtree_counts)
    {
        // e.g. for max = 5, min = 2, count = 52, subtree_max = 25, subtree_min = 10

        size_type n = count / subtree_counts.maxc; // e.g. 52 / 25 = 2
        size_type r = count % subtree_counts.maxc; // e.g. 52 % 25 = 2
        size_type median_count = (n / 2) * subtree_counts.maxc; // e.g. 2 / 2 * 25 = 25

        if ( 0 != r ) // e.g. 0 != 2
        {
            if ( subtree_counts.minc <= r ) // e.g. 10 <= 2 == false
            {
                //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
            {
                size_type 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_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
                        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
                }
            }
        }

        return median_count;
    }
};

}}}}} // namespace boost::geometry::index::detail::rtree

#endif // BOOST_GEOMETRY_INDEX_DETAIL_RTREE_PACK_CREATE_HPP
Commit	Line	Data
7c673cae FG	1	// Boost.Geometry Index
	2	//
	3	// R-tree initial packing
	4	//
b32b8144	5	// Copyright (c) 2011-2017 Adam Wulkiewicz, Lodz, Poland.
20effc67	6	// Copyright (c) 2020 Caian Benedicto, Campinas, Brazil.
7c673cae	7	//
92f5a8d4 TL	8	// This file was modified by Oracle on 2019.
	9	// Modifications copyright (c) 2019 Oracle and/or its affiliates.
	10	// Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
	11	//
7c673cae FG	12	// Use, modification and distribution is subject to the Boost Software License,
	13	// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
	14	// http://www.boost.org/LICENSE_1_0.txt)
	15
	16	#ifndef BOOST_GEOMETRY_INDEX_DETAIL_RTREE_PACK_CREATE_HPP
	17	#define BOOST_GEOMETRY_INDEX_DETAIL_RTREE_PACK_CREATE_HPP
	18
92f5a8d4 TL	19	#include <boost/core/ignore_unused.hpp>
92f5a8d4 TL	20
7c673cae FG	21	#include <boost/geometry/algorithms/expand.hpp>
7c673cae FG	22	#include <boost/geometry/index/detail/algorithms/bounds.hpp>
b32b8144	23	#include <boost/geometry/index/detail/algorithms/nth_element.hpp>
f67539c2	24	#include <boost/geometry/index/detail/rtree/node/subtree_destroyer.hpp>
7c673cae FG	25
	26	#include <boost/geometry/algorithms/detail/expand_by_epsilon.hpp>
	27
	28	namespace boost { namespace geometry { namespace index { namespace detail { namespace rtree {
	29
	30	namespace pack_utils {
	31
	32	template <std::size_t Dimension>
	33	struct biggest_edge
	34	{
	35	BOOST_STATIC_ASSERT(0 < Dimension);
	36	template <typename Box>
	37	static inline void apply(Box const& box, typename coordinate_type<Box>::type & length, std::size_t & dim_index)
	38	{
	39	biggest_edge<Dimension-1>::apply(box, length, dim_index);
	40	typename coordinate_type<Box>::type curr
	41	= geometry::get<max_corner, Dimension-1>(box) - geometry::get<min_corner, Dimension-1>(box);
	42	if ( length < curr )
	43	{
	44	dim_index = Dimension - 1;
	45	length = curr;
	46	}
	47	}
	48	};
	49
	50	template <>
	51	struct biggest_edge<1>
	52	{
	53	template <typename Box>
	54	static inline void apply(Box const& box, typename coordinate_type<Box>::type & length, std::size_t & dim_index)
	55	{
	56	dim_index = 0;
	57	length = geometry::get<max_corner, 0>(box) - geometry::get<min_corner, 0>(box);
	58	}
	59	};
	60
	61	template <std::size_t I>
	62	struct point_entries_comparer
	63	{
	64	template <typename PointEntry>
	65	bool operator()(PointEntry const& e1, PointEntry const& e2) const
	66	{
	67	return geometry::get<I>(e1.first) < geometry::get<I>(e2.first);
	68	}
	69	};
	70
	71	template <std::size_t I, std::size_t Dimension>
	72	struct nth_element_and_half_boxes
	73	{
	74	template <typename EIt, typename Box>
	75	static inline void apply(EIt first, EIt median, EIt last, Box const& box, Box & left, Box & right, std::size_t dim_index)
	76	{
	77	if ( I == dim_index )
	78	{
b32b8144	79	index::detail::nth_element(first, median, last, point_entries_comparer<I>());
7c673cae FG	80
	81	geometry::convert(box, left);
	82	geometry::convert(box, right);
	83	typename coordinate_type<Box>::type edge_len
	84	= geometry::get<max_corner, I>(box) - geometry::get<min_corner, I>(box);
	85	typename coordinate_type<Box>::type median
	86	= geometry::get<min_corner, I>(box) + edge_len / 2;
	87	geometry::set<max_corner, I>(left, median);
	88	geometry::set<min_corner, I>(right, median);
	89	}
	90	else
	91	nth_element_and_half_boxes<I+1, Dimension>::apply(first, median, last, box, left, right, dim_index);
	92	}
	93	};
	94
	95	template <std::size_t Dimension>
	96	struct nth_element_and_half_boxes<Dimension, Dimension>
	97	{
	98	template <typename EIt, typename Box>
	99	static inline void apply(EIt , EIt , EIt , Box const& , Box & , Box & , std::size_t ) {}
	100	};
	101
	102	} // namespace pack_utils
	103
	104	// STR leafs number are calculated as rcount/max
	105	// and the number of splitting planes for each dimension as (count/max)^(1/dimension)
	106	// <-> for dimension==2 -> sqrt(count/max)
	107	//
	108	// The main flaw of this algorithm is that the resulting tree will have bad structure for:
	109	// 1. non-uniformly distributed elements
	110	// Statistic check could be performed, e.g. based on variance of lengths of elements edges for each dimension
	111	// 2. elements distributed mainly along one axis
	112	// Calculate bounding box of all elements and then number of dividing planes for a dimension
	113	// from the length of BB edge for this dimension (more or less assuming that elements are uniformly-distributed squares)
	114	//
	115	// Another thing is that the last node may have less elements than Max or even Min.
	116	// The number of splitting planes must be chosen more carefully than count/max
	117	//
	118	// This algorithm is something between STR and TGS
	119	// it is more similar to the top-down recursive kd-tree creation algorithm
	120	// using object median split and split axis of greatest BB edge
	121	// BB is only used as a hint (assuming objects are distributed uniformly)
	122	//
	123	// Implemented algorithm guarantees that the number of elements in nodes will be between Min and Max
	124	// and that nodes are packed as tightly as possible
	125	// e.g. for 177 values Max = 5 and Min = 2 it will construct the following tree:
	126	// ROOT 177
	127	// L1 125 52
	128	// L2 25 25 25 25 25 25 17 10
	129	// L3 5x5 5x5 5x5 5x5 5x5 5x5 3x5+2 2x5
	130
f67539c2	131	template <typename MembersHolder>
7c673cae FG	132	class pack
7c673cae FG	133	{
f67539c2 TL	134	typedef typename MembersHolder::node node;
	135	typedef typename MembersHolder::internal_node internal_node;
	136	typedef typename MembersHolder::leaf leaf;
	137
	138	typedef typename MembersHolder::node_pointer node_pointer;
	139	typedef typename MembersHolder::size_type size_type;
	140	typedef typename MembersHolder::parameters_type parameters_type;
	141	typedef typename MembersHolder::translator_type translator_type;
	142	typedef typename MembersHolder::allocators_type allocators_type;
	143
	144	typedef typename MembersHolder::box_type box_type;
	145	typedef typename geometry::point_type<box_type>::type point_type;
7c673cae	146	typedef typename geometry::coordinate_type<point_type>::type coordinate_type;
f67539c2	147	typedef typename detail::default_content_result<box_type>::type content_type;
92f5a8d4	148	typedef typename detail::strategy_type<parameters_type>::type strategy_type;
7c673cae FG	149	static const std::size_t dimension = geometry::dimension<point_type>::value;
	150
	151	typedef typename rtree::container_from_elements_type<
	152	typename rtree::elements_type<leaf>::type,
f67539c2	153	size_type
7c673cae FG	154	>::type values_counts_container;
	155
	156	typedef typename rtree::elements_type<internal_node>::type internal_elements;
	157	typedef typename internal_elements::value_type internal_element;
	158
f67539c2 TL	159	typedef rtree::subtree_destroyer<MembersHolder> subtree_destroyer;
f67539c2 TL	160
7c673cae FG	161	public:
	162	// Arbitrary iterators
	163	template <typename InIt> inline static
f67539c2 TL	164	node_pointer apply(InIt first, InIt last,
	165	size_type & values_count,
	166	size_type & leafs_level,
	167	parameters_type const& parameters,
	168	translator_type const& translator,
	169	allocators_type & allocators)
20effc67 TL	170	{
	171	return apply(first, last, values_count, leafs_level, parameters, translator,
	172	allocators, boost::container::new_allocator<void>());
	173	}
	174
	175	template <typename InIt, typename TmpAlloc> inline static
	176	node_pointer apply(InIt first, InIt last,
	177	size_type & values_count,
	178	size_type & leafs_level,
	179	parameters_type const& parameters,
	180	translator_type const& translator,
	181	allocators_type & allocators,
	182	TmpAlloc const& temp_allocator)
7c673cae FG	183	{
	184	typedef typename std::iterator_traits<InIt>::difference_type diff_type;
	185
	186	diff_type diff = std::distance(first, last);
	187	if ( diff <= 0 )
	188	return node_pointer(0);
	189
	190	typedef std::pair<point_type, InIt> entry_type;
20effc67 TL	191	typedef typename boost::container::allocator_traits<TmpAlloc>::
	192	template rebind_alloc<entry_type> temp_entry_allocator_type;
	193
	194	temp_entry_allocator_type temp_entry_allocator(temp_allocator);
	195	boost::container::vector<entry_type, temp_entry_allocator_type> entries(temp_entry_allocator);
7c673cae FG	196
	197	values_count = static_cast<size_type>(diff);
	198	entries.reserve(values_count);
	199
f67539c2	200	expandable_box<box_type, strategy_type> hint_box(detail::get_strategy(parameters));
7c673cae FG	201	for ( ; first != last ; ++first )
	202	{
	203	// NOTE: support for iterators not returning true references adapted
	204	// to Geometry concept and default translator returning true reference
	205	// An alternative would be to dereference the iterator and translate
	206	// in one expression each time the indexable was needed.
	207	typename std::iterator_traits<InIt>::reference in_ref = *first;
f67539c2	208	typename translator_type::result_type indexable = translator(in_ref);
7c673cae FG	209
	210	// NOTE: added for consistency with insert()
	211	// CONSIDER: alternative - ignore invalid indexable or throw an exception
	212	BOOST_GEOMETRY_INDEX_ASSERT(detail::is_valid(indexable), "Indexable is invalid");
	213
	214	hint_box.expand(indexable);
	215
	216	point_type pt;
	217	geometry::centroid(indexable, pt);
	218	entries.push_back(std::make_pair(pt, first));
	219	}
	220
	221	subtree_elements_counts subtree_counts = calculate_subtree_elements_counts(values_count, parameters, leafs_level);
	222	internal_element el = per_level(entries.begin(), entries.end(), hint_box.get(), values_count, subtree_counts,
	223	parameters, translator, allocators);
	224
	225	return el.second;
	226	}
	227
	228	private:
92f5a8d4	229	template <typename BoxType, typename Strategy>
7c673cae FG	230	class expandable_box
	231	{
	232	public:
92f5a8d4 TL	233	explicit expandable_box(Strategy const& strategy)
92f5a8d4 TL	234	: m_strategy(strategy), m_initialized(false)
7c673cae FG	235	{}
	236
	237	template <typename Indexable>
92f5a8d4 TL	238	explicit expandable_box(Indexable const& indexable, Strategy const& strategy)
92f5a8d4 TL	239	: m_strategy(strategy), m_initialized(true)
7c673cae	240	{
92f5a8d4	241	detail::bounds(indexable, m_box, m_strategy);
7c673cae FG	242	}
	243
	244	template <typename Indexable>
	245	void expand(Indexable const& indexable)
	246	{
	247	if ( !m_initialized )
	248	{
	249	// it's guaranteed that the Box will be initialized
	250	// only for Points, Boxes and Segments but that's ok
	251	// since only those Geometries can be stored
92f5a8d4	252	detail::bounds(indexable, m_box, m_strategy);
7c673cae FG	253	m_initialized = true;
	254	}
	255	else
	256	{
92f5a8d4	257	detail::expand(m_box, indexable, m_strategy);
7c673cae FG	258	}
	259	}
	260
	261	void expand_by_epsilon()
	262	{
	263	geometry::detail::expand_by_epsilon(m_box);
	264	}
	265
	266	BoxType const& get() const
	267	{
	268	BOOST_GEOMETRY_INDEX_ASSERT(m_initialized, "uninitialized envelope accessed");
	269	return m_box;
	270	}
	271
	272	private:
7c673cae	273	BoxType m_box;
92f5a8d4 TL	274	Strategy m_strategy;
92f5a8d4 TL	275	bool m_initialized;
7c673cae FG	276	};
	277
	278	struct subtree_elements_counts
	279	{
f67539c2 TL	280	subtree_elements_counts(size_type ma, size_type mi) : maxc(ma), minc(mi) {}
	281	size_type maxc;
	282	size_type minc;
7c673cae FG	283	};
	284
	285	template <typename EIt> inline static
f67539c2 TL	286	internal_element per_level(EIt first, EIt last,
	287	box_type const& hint_box,
	288	size_type values_count,
	289	subtree_elements_counts const& subtree_counts,
	290	parameters_type const& parameters,
	291	translator_type const& translator,
	292	allocators_type & allocators)
7c673cae	293	{
f67539c2	294	BOOST_GEOMETRY_INDEX_ASSERT(0 < std::distance(first, last) && static_cast<size_type>(std::distance(first, last)) == values_count,
7c673cae FG	295	"unexpected parameters");
	296
	297	if ( subtree_counts.maxc <= 1 )
	298	{
	299	// ROOT or LEAF
	300	BOOST_GEOMETRY_INDEX_ASSERT(values_count <= parameters.get_max_elements(),
	301	"too big number of elements");
	302	// if !root check m_parameters.get_min_elements() <= count
	303
	304	// create new leaf node
f67539c2	305	node_pointer n = rtree::create_node<allocators_type, leaf>::apply(allocators); // MAY THROW (A)
7c673cae FG	306	subtree_destroyer auto_remover(n, allocators);
	307	leaf & l = rtree::get<leaf>(*n);
	308
	309	// reserve space for values
	310	rtree::elements(l).reserve(values_count); // MAY THROW (A)
	311
	312	// calculate values box and copy values
	313	// initialize the box explicitly to avoid GCC-4.4 uninitialized variable warnings with O2
f67539c2 TL	314	expandable_box<box_type, strategy_type> elements_box(translator(*(first->second)),
f67539c2 TL	315	detail::get_strategy(parameters));
7c673cae FG	316	rtree::elements(l).push_back(*(first->second)); // MAY THROW (A?,C)
	317	for ( ++first ; first != last ; ++first )
	318	{
	319	// NOTE: push_back() must be called at the end in order to support move_iterator.
	320	// The iterator is dereferenced 2x (no temporary reference) to support
	321	// non-true reference types and move_iterator without boost::forward<>.
	322	elements_box.expand(translator(*(first->second)));
	323	rtree::elements(l).push_back(*(first->second)); // MAY THROW (A?,C)
	324	}
	325
	326	#ifdef BOOST_GEOMETRY_INDEX_EXPERIMENTAL_ENLARGE_BY_EPSILON
	327	// Enlarge bounds of a leaf node.
	328	// It's because Points and Segments are compared WRT machine epsilon
	329	// This ensures that leafs bounds correspond to the stored elements
	330	// NOTE: this is done only if the Indexable is a different kind of Geometry
	331	// than the bounds (only Box for now). Spatial predicates are checked
	332	// the same way for Geometry of the same kind.
	333	if ( BOOST_GEOMETRY_CONDITION((
	334	! index::detail::is_bounding_geometry
	335	<
f67539c2	336	typename indexable_type<translator_type>::type
7c673cae FG	337	>::value )) )
	338	{
	339	elements_box.expand_by_epsilon();
	340	}
	341	#endif
	342
	343	auto_remover.release();
	344	return internal_element(elements_box.get(), n);
	345	}
	346
	347	// calculate next max and min subtree counts
	348	subtree_elements_counts next_subtree_counts = subtree_counts;
	349	next_subtree_counts.maxc /= parameters.get_max_elements();
	350	next_subtree_counts.minc /= parameters.get_max_elements();
	351
	352	// create new internal node
f67539c2	353	node_pointer n = rtree::create_node<allocators_type, internal_node>::apply(allocators); // MAY THROW (A)
7c673cae FG	354	subtree_destroyer auto_remover(n, allocators);
	355	internal_node & in = rtree::get<internal_node>(*n);
	356
	357	// reserve space for values
f67539c2	358	size_type nodes_count = calculate_nodes_count(values_count, subtree_counts);
7c673cae FG	359	rtree::elements(in).reserve(nodes_count); // MAY THROW (A)
7c673cae FG	360	// calculate values box and copy values
f67539c2	361	expandable_box<box_type, strategy_type> elements_box(detail::get_strategy(parameters));
7c673cae FG	362
	363	per_level_packets(first, last, hint_box, values_count, subtree_counts, next_subtree_counts,
	364	rtree::elements(in), elements_box,
	365	parameters, translator, allocators);
	366
	367	auto_remover.release();
	368	return internal_element(elements_box.get(), n);
	369	}
	370
	371	template <typename EIt, typename ExpandableBox> inline static
f67539c2 TL	372	void per_level_packets(EIt first, EIt last,
	373	box_type const& hint_box,
	374	size_type values_count,
7c673cae FG	375	subtree_elements_counts const& subtree_counts,
7c673cae FG	376	subtree_elements_counts const& next_subtree_counts,
f67539c2 TL	377	internal_elements & elements,
	378	ExpandableBox & elements_box,
	379	parameters_type const& parameters,
	380	translator_type const& translator,
	381	allocators_type & allocators)
7c673cae	382	{
f67539c2	383	BOOST_GEOMETRY_INDEX_ASSERT(0 < std::distance(first, last) && static_cast<size_type>(std::distance(first, last)) == values_count,
7c673cae FG	384	"unexpected parameters");
	385
	386	BOOST_GEOMETRY_INDEX_ASSERT(subtree_counts.minc <= values_count,
	387	"too small number of elements");
	388
	389	// only one packet
	390	if ( values_count <= subtree_counts.maxc )
	391	{
	392	// the end, move to the next level
	393	internal_element el = per_level(first, last, hint_box, values_count, next_subtree_counts,
	394	parameters, translator, allocators);
	395
	396	// in case if push_back() do throw here
	397	// and even if this is not probable (previously reserved memory, nonthrowing pairs copy)
	398	// this case is also tested by exceptions test.
	399	subtree_destroyer auto_remover(el.second, allocators);
	400	// this container should have memory allocated, reserve() called outside
	401	elements.push_back(el); // MAY THROW (A?,C) - however in normal conditions shouldn't
	402	auto_remover.release();
	403
	404	elements_box.expand(el.first);
	405	return;
	406	}
	407
f67539c2	408	size_type median_count = calculate_median_count(values_count, subtree_counts);
7c673cae FG	409	EIt median = first + median_count;
	410
	411	coordinate_type greatest_length;
	412	std::size_t greatest_dim_index = 0;
	413	pack_utils::biggest_edge<dimension>::apply(hint_box, greatest_length, greatest_dim_index);
f67539c2	414	box_type left, right;
7c673cae FG	415	pack_utils::nth_element_and_half_boxes<0, dimension>
	416	::apply(first, median, last, hint_box, left, right, greatest_dim_index);
	417
	418	per_level_packets(first, median, left,
	419	median_count, subtree_counts, next_subtree_counts,
	420	elements, elements_box,
	421	parameters, translator, allocators);
	422	per_level_packets(median, last, right,
	423	values_count - median_count, subtree_counts, next_subtree_counts,
	424	elements, elements_box,
	425	parameters, translator, allocators);
	426	}
	427
	428	inline static
f67539c2	429	subtree_elements_counts calculate_subtree_elements_counts(size_type elements_count, parameters_type const& parameters, size_type & leafs_level)
7c673cae	430	{
92f5a8d4	431	boost::ignore_unused(parameters);
7c673cae FG	432
	433	subtree_elements_counts res(1, 1);
	434	leafs_level = 0;
	435
f67539c2	436	size_type smax = parameters.get_max_elements();
7c673cae FG	437	for ( ; smax < elements_count ; smax *= parameters.get_max_elements(), ++leafs_level )
	438	res.maxc = smax;
	439
	440	res.minc = parameters.get_min_elements() * (res.maxc / parameters.get_max_elements());
	441
	442	return res;
	443	}
	444
	445	inline static
f67539c2 TL	446	size_type calculate_nodes_count(size_type count,
f67539c2 TL	447	subtree_elements_counts const& subtree_counts)
7c673cae	448	{
f67539c2 TL	449	size_type n = count / subtree_counts.maxc;
f67539c2 TL	450	size_type r = count % subtree_counts.maxc;
7c673cae FG	451
	452	if ( 0 < r && r < subtree_counts.minc )
	453	{
f67539c2	454	size_type count_minus_min = count - subtree_counts.minc;
7c673cae FG	455	n = count_minus_min / subtree_counts.maxc;
	456	r = count_minus_min % subtree_counts.maxc;
	457	++n;
	458	}
	459
	460	if ( 0 < r )
	461	++n;
	462
	463	return n;
	464	}
	465
	466	inline static
f67539c2 TL	467	size_type calculate_median_count(size_type count,
f67539c2 TL	468	subtree_elements_counts const& subtree_counts)
7c673cae FG	469	{
	470	// e.g. for max = 5, min = 2, count = 52, subtree_max = 25, subtree_min = 10
	471
f67539c2 TL	472	size_type n = count / subtree_counts.maxc; // e.g. 52 / 25 = 2
	473	size_type r = count % subtree_counts.maxc; // e.g. 52 % 25 = 2
	474	size_type median_count = (n / 2) * subtree_counts.maxc; // e.g. 2 / 2 * 25 = 25
7c673cae FG	475
	476	if ( 0 != r ) // e.g. 0 != 2
	477	{
	478	if ( subtree_counts.minc <= r ) // e.g. 10 <= 2 == false
	479	{
	480	//BOOST_GEOMETRY_INDEX_ASSERT(0 < n, "unexpected value");
	481	median_count = ((n+1)/2) * subtree_counts.maxc; // if calculated ((2+1)/2) * 25 which would be ok, but not in all cases
	482	}
	483	else // r < subtree_counts.second // e.g. 2 < 10 == true
	484	{
f67539c2	485	size_type count_minus_min = count - subtree_counts.minc; // e.g. 52 - 10 = 42
7c673cae FG	486	n = count_minus_min / subtree_counts.maxc; // e.g. 42 / 25 = 1
	487	r = count_minus_min % subtree_counts.maxc; // e.g. 42 % 25 = 17
	488	if ( r == 0 ) // e.g. false
	489	{
	490	// n can't be equal to 0 because then there wouldn't be any element in the other node
	491	//BOOST_GEOMETRY_INDEX_ASSERT(0 < n, "unexpected value");
	492	median_count = ((n+1)/2) * subtree_counts.maxc; // if calculated ((1+1)/2) * 25 which would be ok, but not in all cases
	493	}
	494	else
	495	{
	496	if ( n == 0 ) // e.g. false
	497	median_count = r; // if calculated -> 17 which is wrong!
	498	else
	499	median_count = ((n+2)/2) * subtree_counts.maxc; // e.g. ((1+2)/2) * 25 = 25
	500	}
	501	}
	502	}
	503
	504	return median_count;
	505	}
	506	};
	507
	508	}}}}} // namespace boost::geometry::index::detail::rtree
	509
	510	#endif // BOOST_GEOMETRY_INDEX_DETAIL_RTREE_PACK_CREATE_HPP