[ceph.git] / ceph / src / boost / libs / geometry / include / boost / geometry / index / detail / rtree / quadratic / redistribute_elements.hpp

// Boost.Geometry Index
//
// R-tree quadratic split algorithm implementation
//
// 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)

#ifndef BOOST_GEOMETRY_INDEX_DETAIL_RTREE_QUADRATIC_REDISTRIBUTE_ELEMENTS_HPP
#define BOOST_GEOMETRY_INDEX_DETAIL_RTREE_QUADRATIC_REDISTRIBUTE_ELEMENTS_HPP

#include <algorithm>

#include <boost/geometry/index/detail/algorithms/content.hpp>
#include <boost/geometry/index/detail/algorithms/union_content.hpp>

#include <boost/geometry/index/detail/bounded_view.hpp>

#include <boost/geometry/index/detail/rtree/node/node.hpp>
#include <boost/geometry/index/detail/rtree/visitors/insert.hpp>
#include <boost/geometry/index/detail/rtree/visitors/is_leaf.hpp>

namespace boost { namespace geometry { namespace index {

namespace detail { namespace rtree {

namespace quadratic {

template <typename Box, typename Elements, typename Parameters, typename Translator>
inline void pick_seeds(Elements const& elements,
                       Parameters const& parameters,
                       Translator const& tr,
                       size_t & seed1,
                       size_t & seed2)
{
    typedef typename Elements::value_type element_type;
    typedef typename rtree::element_indexable_type<element_type, Translator>::type indexable_type;
    typedef Box box_type;
    typedef typename index::detail::default_content_result<box_type>::type content_type;
    typedef index::detail::bounded_view<indexable_type, box_type> bounded_indexable_view;

    const size_t elements_count = parameters.get_max_elements() + 1;
    BOOST_GEOMETRY_INDEX_ASSERT(elements.size() == elements_count, "wrong number of elements");
    BOOST_GEOMETRY_INDEX_ASSERT(2 <= elements_count, "unexpected number of elements");

    content_type greatest_free_content = 0;
    seed1 = 0;
    seed2 = 1;

    for ( size_t i = 0 ; i < elements_count - 1 ; ++i )
    {
        for ( size_t j = i + 1 ; j < elements_count ; ++j )
        {
            indexable_type const& ind1 = rtree::element_indexable(elements[i], tr);
            indexable_type const& ind2 = rtree::element_indexable(elements[j], tr);

            box_type enlarged_box;
            detail::bounds(ind1, enlarged_box);
            geometry::expand(enlarged_box, ind2);

            bounded_indexable_view bounded_ind1(ind1);
            bounded_indexable_view bounded_ind2(ind2);
            content_type free_content = ( index::detail::content(enlarged_box)
                                            - index::detail::content(bounded_ind1) )
                                                - index::detail::content(bounded_ind2);
                
            if ( greatest_free_content < free_content )
            {
                greatest_free_content = free_content;
                seed1 = i;
                seed2 = j;
            }
        }
    }

    ::boost::ignore_unused_variable_warning(parameters);
}

} // namespace quadratic

template <typename Value, typename Options, typename Translator, typename Box, typename Allocators>
struct redistribute_elements<Value, Options, Translator, Box, Allocators, quadratic_tag>
{
    typedef typename Options::parameters_type parameters_type;

    typedef typename rtree::node<Value, parameters_type, Box, Allocators, typename Options::node_tag>::type node;
    typedef typename rtree::internal_node<Value, parameters_type, Box, Allocators, typename Options::node_tag>::type internal_node;
    typedef typename rtree::leaf<Value, parameters_type, Box, Allocators, typename Options::node_tag>::type leaf;

    typedef typename index::detail::default_content_result<Box>::type content_type;

    template <typename Node>
    static inline void apply(Node & n,
                             Node & second_node,
                             Box & box1,
                             Box & box2,
                             parameters_type const& parameters,
                             Translator const& translator,
                             Allocators & allocators)
    {
        typedef typename rtree::elements_type<Node>::type elements_type;
        typedef typename elements_type::value_type element_type;
        typedef typename rtree::element_indexable_type<element_type, Translator>::type indexable_type;

        elements_type & elements1 = rtree::elements(n);
        elements_type & elements2 = rtree::elements(second_node);
        
        BOOST_GEOMETRY_INDEX_ASSERT(elements1.size() == parameters.get_max_elements() + 1, "unexpected elements number");

        // copy original elements - use in-memory storage (std::allocator)
        // TODO: move if noexcept
        typedef typename rtree::container_from_elements_type<elements_type, element_type>::type
            container_type;
        container_type elements_copy(elements1.begin(), elements1.end());                                   // MAY THROW, STRONG (alloc, copy)
        container_type elements_backup(elements1.begin(), elements1.end());                                 // MAY THROW, STRONG (alloc, copy)
        
        // calculate initial seeds
        size_t seed1 = 0;
        size_t seed2 = 0;
        quadratic::pick_seeds<Box>(elements_copy, parameters, translator, seed1, seed2);

        // prepare nodes' elements containers
        elements1.clear();
        BOOST_GEOMETRY_INDEX_ASSERT(elements2.empty(), "second node's elements container should be empty");

        BOOST_TRY
        {
            // add seeds
            elements1.push_back(elements_copy[seed1]);                                                      // MAY THROW, STRONG (copy)
            elements2.push_back(elements_copy[seed2]);                                                      // MAY THROW, STRONG (alloc, copy)

            // calculate boxes
            detail::bounds(rtree::element_indexable(elements_copy[seed1], translator), box1);
            detail::bounds(rtree::element_indexable(elements_copy[seed2], translator), box2);

            // remove seeds
            if (seed1 < seed2)
            {
                rtree::move_from_back(elements_copy, elements_copy.begin() + seed2);                        // MAY THROW, STRONG (copy)
                elements_copy.pop_back();
                rtree::move_from_back(elements_copy, elements_copy.begin() + seed1);                        // MAY THROW, STRONG (copy)
                elements_copy.pop_back();
            }
            else
            {
                rtree::move_from_back(elements_copy, elements_copy.begin() + seed1);                        // MAY THROW, STRONG (copy)
                elements_copy.pop_back();
                rtree::move_from_back(elements_copy, elements_copy.begin() + seed2);                        // MAY THROW, STRONG (copy)
                elements_copy.pop_back();
            }

            // initialize areas
            content_type content1 = index::detail::content(box1);
            content_type content2 = index::detail::content(box2);

            size_t remaining = elements_copy.size();

            // redistribute the rest of the elements
            while ( !elements_copy.empty() )
            {
                typename container_type::reverse_iterator el_it = elements_copy.rbegin();
                bool insert_into_group1 = false;

                size_t elements1_count = elements1.size();
                size_t elements2_count = elements2.size();

                // if there is small number of elements left and the number of elements in node is lesser than min_elems
                // just insert them to this node
                if ( elements1_count + remaining <= parameters.get_min_elements() )
                {
                    insert_into_group1 = true;
                }
                else if ( elements2_count + remaining <= parameters.get_min_elements() )
                {
                    insert_into_group1 = false;
                }
                // insert the best element
                else
                {
                    // find element with minimum groups areas increses differences
                    content_type content_increase1 = 0;
                    content_type content_increase2 = 0;
                    el_it = pick_next(elements_copy.rbegin(), elements_copy.rend(),
                                      box1, box2, content1, content2, translator,
                                      content_increase1, content_increase2);

                    if ( content_increase1 < content_increase2 ||
                         ( content_increase1 == content_increase2 && ( content1 < content2 ||
                           ( content1 == content2 && elements1_count <= elements2_count ) )
                         ) )
                    {
                        insert_into_group1 = true;
                    }
                    else
                    {
                        insert_into_group1 = false;
                    }
                }

                // move element to the choosen group
                element_type const& elem = *el_it;
                indexable_type const& indexable = rtree::element_indexable(elem, translator);

                if ( insert_into_group1 )
                {
                    elements1.push_back(elem);                                                              // MAY THROW, STRONG (copy)
                    geometry::expand(box1, indexable);
                    content1 = index::detail::content(box1);
                }
                else
                {
                    elements2.push_back(elem);                                                              // MAY THROW, STRONG (alloc, copy)
                    geometry::expand(box2, indexable);
                    content2 = index::detail::content(box2);
                }

                BOOST_GEOMETRY_INDEX_ASSERT(!elements_copy.empty(), "expected more elements");
                typename container_type::iterator el_it_base = el_it.base();
                rtree::move_from_back(elements_copy, --el_it_base);                                         // MAY THROW, STRONG (copy)
                elements_copy.pop_back();

                BOOST_GEOMETRY_INDEX_ASSERT(0 < remaining, "expected more remaining elements");
                --remaining;
            }
        }
        BOOST_CATCH(...)
        {
            //elements_copy.clear();
            elements1.clear();
            elements2.clear();

            rtree::destroy_elements<Value, Options, Translator, Box, Allocators>::apply(elements_backup, allocators);
            //elements_backup.clear();

            BOOST_RETHROW                                                                                     // RETHROW, BASIC
        }
        BOOST_CATCH_END
    }

    // TODO: awulkiew - change following function to static member of the pick_next class?

    template <typename It>
    static inline It pick_next(It first, It last,
                               Box const& box1, Box const& box2,
                               content_type const& content1, content_type const& content2,
                               Translator const& translator,
                               content_type & out_content_increase1, content_type & out_content_increase2)
    {
        typedef typename boost::iterator_value<It>::type element_type;
        typedef typename rtree::element_indexable_type<element_type, Translator>::type indexable_type;

        content_type greatest_content_incrase_diff = 0;
        It out_it = first;
        out_content_increase1 = 0;
        out_content_increase2 = 0;
        
        // find element with greatest difference between increased group's boxes areas
        for ( It el_it = first ; el_it != last ; ++el_it )
        {
            indexable_type const& indexable = rtree::element_indexable(*el_it, translator);

            // calculate enlarged boxes and areas
            Box enlarged_box1(box1);
            Box enlarged_box2(box2);
            geometry::expand(enlarged_box1, indexable);
            geometry::expand(enlarged_box2, indexable);
            content_type enlarged_content1 = index::detail::content(enlarged_box1);
            content_type enlarged_content2 = index::detail::content(enlarged_box2);

            content_type content_incrase1 = (enlarged_content1 - content1);
            content_type content_incrase2 = (enlarged_content2 - content2);

            content_type content_incrase_diff = content_incrase1 < content_incrase2 ?
                content_incrase2 - content_incrase1 : content_incrase1 - content_incrase2;

            if ( greatest_content_incrase_diff < content_incrase_diff )
            {
                greatest_content_incrase_diff = content_incrase_diff;
                out_it = el_it;
                out_content_increase1 = content_incrase1;
                out_content_increase2 = content_incrase2;
            }
        }

        return out_it;
    }
};

}} // namespace detail::rtree

}}} // namespace boost::geometry::index

#endif // BOOST_GEOMETRY_INDEX_DETAIL_RTREE_QUADRATIC_REDISTRIBUTE_ELEMENTS_HPP
Commit	Line	Data
7c673cae FG	1	// Boost.Geometry Index
	2	//
	3	// R-tree quadratic split algorithm implementation
	4	//
	5	// Copyright (c) 2011-2015 Adam Wulkiewicz, Lodz, Poland.
	6	//
	7	// Use, modification and distribution is subject to the Boost Software License,
	8	// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
	9	// http://www.boost.org/LICENSE_1_0.txt)
	10
	11	#ifndef BOOST_GEOMETRY_INDEX_DETAIL_RTREE_QUADRATIC_REDISTRIBUTE_ELEMENTS_HPP
	12	#define BOOST_GEOMETRY_INDEX_DETAIL_RTREE_QUADRATIC_REDISTRIBUTE_ELEMENTS_HPP
	13
	14	#include <algorithm>
	15
	16	#include <boost/geometry/index/detail/algorithms/content.hpp>
	17	#include <boost/geometry/index/detail/algorithms/union_content.hpp>
	18
	19	#include <boost/geometry/index/detail/bounded_view.hpp>
	20
	21	#include <boost/geometry/index/detail/rtree/node/node.hpp>
	22	#include <boost/geometry/index/detail/rtree/visitors/insert.hpp>
	23	#include <boost/geometry/index/detail/rtree/visitors/is_leaf.hpp>
	24
	25	namespace boost { namespace geometry { namespace index {
	26
	27	namespace detail { namespace rtree {
	28
	29	namespace quadratic {
	30
	31	template <typename Box, typename Elements, typename Parameters, typename Translator>
	32	inline void pick_seeds(Elements const& elements,
	33	Parameters const& parameters,
	34	Translator const& tr,
	35	size_t & seed1,
	36	size_t & seed2)
	37	{
	38	typedef typename Elements::value_type element_type;
	39	typedef typename rtree::element_indexable_type<element_type, Translator>::type indexable_type;
	40	typedef Box box_type;
	41	typedef typename index::detail::default_content_result<box_type>::type content_type;
	42	typedef index::detail::bounded_view<indexable_type, box_type> bounded_indexable_view;
	43
	44	const size_t elements_count = parameters.get_max_elements() + 1;
	45	BOOST_GEOMETRY_INDEX_ASSERT(elements.size() == elements_count, "wrong number of elements");
	46	BOOST_GEOMETRY_INDEX_ASSERT(2 <= elements_count, "unexpected number of elements");
	47
	48	content_type greatest_free_content = 0;
	49	seed1 = 0;
	50	seed2 = 1;
	51
	52	for ( size_t i = 0 ; i < elements_count - 1 ; ++i )
	53	{
	54	for ( size_t j = i + 1 ; j < elements_count ; ++j )
	55	{
	56	indexable_type const& ind1 = rtree::element_indexable(elements[i], tr);
	57	indexable_type const& ind2 = rtree::element_indexable(elements[j], tr);
	58
	59	box_type enlarged_box;
	60	detail::bounds(ind1, enlarged_box);
	61	geometry::expand(enlarged_box, ind2);
	62
	63	bounded_indexable_view bounded_ind1(ind1);
	64	bounded_indexable_view bounded_ind2(ind2);
65	content_type free_content = ( index::detail::content(enlarged_box)
66	- index::detail::content(bounded_ind1) )
67	- index::detail::content(bounded_ind2);
68
69	if ( greatest_free_content < free_content )
70	{
71	greatest_free_content = free_content;
72	seed1 = i;
73	seed2 = j;
74	}
75	}
76	}
77
78	::boost::ignore_unused_variable_warning(parameters);
79	}
80
81	} // namespace quadratic
82
83	template <typename Value, typename Options, typename Translator, typename Box, typename Allocators>
84	struct redistribute_elements<Value, Options, Translator, Box, Allocators, quadratic_tag>
85	{
86	typedef typename Options::parameters_type parameters_type;
87
88	typedef typename rtree::node<Value, parameters_type, Box, Allocators, typename Options::node_tag>::type node;
89	typedef typename rtree::internal_node<Value, parameters_type, Box, Allocators, typename Options::node_tag>::type internal_node;
90	typedef typename rtree::leaf<Value, parameters_type, Box, Allocators, typename Options::node_tag>::type leaf;
91
92	typedef typename index::detail::default_content_result<Box>::type content_type;
93
94	template <typename Node>
95	static inline void apply(Node & n,
96	Node & second_node,
97	Box & box1,
98	Box & box2,
99	parameters_type const& parameters,
100	Translator const& translator,
101	Allocators & allocators)
102	{
103	typedef typename rtree::elements_type<Node>::type elements_type;
104	typedef typename elements_type::value_type element_type;
105	typedef typename rtree::element_indexable_type<element_type, Translator>::type indexable_type;
106
107	elements_type & elements1 = rtree::elements(n);
108	elements_type & elements2 = rtree::elements(second_node);
109
110	BOOST_GEOMETRY_INDEX_ASSERT(elements1.size() == parameters.get_max_elements() + 1, "unexpected elements number");
111
112	// copy original elements - use in-memory storage (std::allocator)
113	// TODO: move if noexcept
114	typedef typename rtree::container_from_elements_type<elements_type, element_type>::type
115	container_type;
116	container_type elements_copy(elements1.begin(), elements1.end()); // MAY THROW, STRONG (alloc, copy)
117	container_type elements_backup(elements1.begin(), elements1.end()); // MAY THROW, STRONG (alloc, copy)
118
119	// calculate initial seeds
120	size_t seed1 = 0;
121	size_t seed2 = 0;
122	quadratic::pick_seeds<Box>(elements_copy, parameters, translator, seed1, seed2);
123
124	// prepare nodes' elements containers
125	elements1.clear();
126	BOOST_GEOMETRY_INDEX_ASSERT(elements2.empty(), "second node's elements container should be empty");
127
128	BOOST_TRY
129	{
130	// add seeds
131	elements1.push_back(elements_copy[seed1]); // MAY THROW, STRONG (copy)
132	elements2.push_back(elements_copy[seed2]); // MAY THROW, STRONG (alloc, copy)
133
134	// calculate boxes
135	detail::bounds(rtree::element_indexable(elements_copy[seed1], translator), box1);
136	detail::bounds(rtree::element_indexable(elements_copy[seed2], translator), box2);
137
138	// remove seeds
139	if (seed1 < seed2)
140	{
141	rtree::move_from_back(elements_copy, elements_copy.begin() + seed2); // MAY THROW, STRONG (copy)
142	elements_copy.pop_back();
143	rtree::move_from_back(elements_copy, elements_copy.begin() + seed1); // MAY THROW, STRONG (copy)
144	elements_copy.pop_back();
145	}
146	else
147	{
148	rtree::move_from_back(elements_copy, elements_copy.begin() + seed1); // MAY THROW, STRONG (copy)
149	elements_copy.pop_back();
150	rtree::move_from_back(elements_copy, elements_copy.begin() + seed2); // MAY THROW, STRONG (copy)
151	elements_copy.pop_back();
152	}
153
154	// initialize areas
155	content_type content1 = index::detail::content(box1);
156	content_type content2 = index::detail::content(box2);
157
158	size_t remaining = elements_copy.size();
159
160	// redistribute the rest of the elements
161	while ( !elements_copy.empty() )
162	{
163	typename container_type::reverse_iterator el_it = elements_copy.rbegin();
164	bool insert_into_group1 = false;
165
166	size_t elements1_count = elements1.size();
167	size_t elements2_count = elements2.size();
168
169	// if there is small number of elements left and the number of elements in node is lesser than min_elems
170	// just insert them to this node
171	if ( elements1_count + remaining <= parameters.get_min_elements() )
172	{
173	insert_into_group1 = true;
174	}
175	else if ( elements2_count + remaining <= parameters.get_min_elements() )
176	{
177	insert_into_group1 = false;
178	}
179	// insert the best element
180	else
181	{
182	// find element with minimum groups areas increses differences
183	content_type content_increase1 = 0;
184	content_type content_increase2 = 0;
185	el_it = pick_next(elements_copy.rbegin(), elements_copy.rend(),
186	box1, box2, content1, content2, translator,
187	content_increase1, content_increase2);
188
189	if ( content_increase1 < content_increase2 \|\|
190	( content_increase1 == content_increase2 && ( content1 < content2 \|\|
191	( content1 == content2 && elements1_count <= elements2_count ) )
192	) )
193	{
194	insert_into_group1 = true;
195	}
196	else
197	{
198	insert_into_group1 = false;
199	}
200	}
201
202	// move element to the choosen group
203	element_type const& elem = *el_it;
204	indexable_type const& indexable = rtree::element_indexable(elem, translator);
205
206	if ( insert_into_group1 )
207	{
208	elements1.push_back(elem); // MAY THROW, STRONG (copy)
209	geometry::expand(box1, indexable);
210	content1 = index::detail::content(box1);
211	}
212	else
213	{
214	elements2.push_back(elem); // MAY THROW, STRONG (alloc, copy)
215	geometry::expand(box2, indexable);
216	content2 = index::detail::content(box2);
217	}
218
219	BOOST_GEOMETRY_INDEX_ASSERT(!elements_copy.empty(), "expected more elements");
220	typename container_type::iterator el_it_base = el_it.base();
221	rtree::move_from_back(elements_copy, --el_it_base); // MAY THROW, STRONG (copy)
222	elements_copy.pop_back();
223
224	BOOST_GEOMETRY_INDEX_ASSERT(0 < remaining, "expected more remaining elements");
225	--remaining;
226	}
227	}
228	BOOST_CATCH(...)
229	{
230	//elements_copy.clear();
231	elements1.clear();
232	elements2.clear();
233
234	rtree::destroy_elements<Value, Options, Translator, Box, Allocators>::apply(elements_backup, allocators);
235	//elements_backup.clear();
236
237	BOOST_RETHROW // RETHROW, BASIC
238	}
239	BOOST_CATCH_END
240	}
241
242	// TODO: awulkiew - change following function to static member of the pick_next class?
243
244	template <typename It>
245	static inline It pick_next(It first, It last,
246	Box const& box1, Box const& box2,
247	content_type const& content1, content_type const& content2,
248	Translator const& translator,
249	content_type & out_content_increase1, content_type & out_content_increase2)
250	{
251	typedef typename boost::iterator_value<It>::type element_type;
252	typedef typename rtree::element_indexable_type<element_type, Translator>::type indexable_type;
253
254	content_type greatest_content_incrase_diff = 0;
255	It out_it = first;
256	out_content_increase1 = 0;
257	out_content_increase2 = 0;
258
259	// find element with greatest difference between increased group's boxes areas
260	for ( It el_it = first ; el_it != last ; ++el_it )
261	{
262	indexable_type const& indexable = rtree::element_indexable(*el_it, translator);
263
264	// calculate enlarged boxes and areas
265	Box enlarged_box1(box1);
266	Box enlarged_box2(box2);
267	geometry::expand(enlarged_box1, indexable);
268	geometry::expand(enlarged_box2, indexable);
269	content_type enlarged_content1 = index::detail::content(enlarged_box1);
270	content_type enlarged_content2 = index::detail::content(enlarged_box2);
271
272	content_type content_incrase1 = (enlarged_content1 - content1);
273	content_type content_incrase2 = (enlarged_content2 - content2);
274
275	content_type content_incrase_diff = content_incrase1 < content_incrase2 ?
276	content_incrase2 - content_incrase1 : content_incrase1 - content_incrase2;
277
278	if ( greatest_content_incrase_diff < content_incrase_diff )
279	{
280	greatest_content_incrase_diff = content_incrase_diff;
281	out_it = el_it;
282	out_content_increase1 = content_incrase1;
283	out_content_increase2 = content_incrase2;
284	}
285	}
286
287	return out_it;
288	}
289	};
290
291	}} // namespace detail::rtree
292
293	}}} // namespace boost::geometry::index
294
295	#endif // BOOST_GEOMETRY_INDEX_DETAIL_RTREE_QUADRATIC_REDISTRIBUTE_ELEMENTS_HPP