[ceph.git] / ceph / src / boost / libs / geometry / include / boost / geometry / index / detail / rtree / visitors / remove.hpp

// Boost.Geometry Index
//
// R-tree removing visitor 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_VISITORS_REMOVE_HPP
#define BOOST_GEOMETRY_INDEX_DETAIL_RTREE_VISITORS_REMOVE_HPP

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

#include <boost/geometry/algorithms/covered_by.hpp>

namespace boost { namespace geometry { namespace index {

namespace detail { namespace rtree { namespace visitors {

// Default remove algorithm
template <typename Value, typename Options, typename Translator, typename Box, typename Allocators>
class remove
    : public rtree::visitor<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag, false>::type
{
    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 rtree::subtree_destroyer<Value, Options, Translator, Box, Allocators> subtree_destroyer;
    typedef typename Allocators::node_pointer node_pointer;
    typedef typename Allocators::size_type size_type;

    typedef typename rtree::elements_type<internal_node>::type::size_type internal_size_type;

    //typedef typename Allocators::internal_node_pointer internal_node_pointer;
    typedef internal_node * internal_node_pointer;

public:
    inline remove(node_pointer & root,
                  size_type & leafs_level,
                  Value const& value,
                  parameters_type const& parameters,
                  Translator const& translator,
                  Allocators & allocators)
        : m_value(value)
        , m_parameters(parameters)
        , m_translator(translator)
        , m_allocators(allocators)
        , m_root_node(root)
        , m_leafs_level(leafs_level)
        , m_is_value_removed(false)
        , m_parent(0)
        , m_current_child_index(0)
        , m_current_level(0)
        , m_is_underflow(false)
    {
        // TODO
        // assert - check if Value/Box is correct
    }

    inline void operator()(internal_node & n)
    {
        typedef typename rtree::elements_type<internal_node>::type children_type;
        children_type & children = rtree::elements(n);

        // traverse children which boxes intersects value's box
        internal_size_type child_node_index = 0;
        for ( ; child_node_index < children.size() ; ++child_node_index )
        {
            if ( geometry::covered_by(
                    return_ref_or_bounds(m_translator(m_value)),
                    children[child_node_index].first) )
            {
                // next traversing step
                traverse_apply_visitor(n, child_node_index);                                                            // MAY THROW

                if ( m_is_value_removed )
                    break;
            }
        }

        // value was found and removed
        if ( m_is_value_removed )
        {
            typedef typename rtree::elements_type<internal_node>::type elements_type;
            typedef typename elements_type::iterator element_iterator;
            elements_type & elements = rtree::elements(n);

            // underflow occured - child node should be removed
            if ( m_is_underflow )
            {
                element_iterator underfl_el_it = elements.begin() + child_node_index;
                size_type relative_level = m_leafs_level - m_current_level;

                // move node to the container - store node's relative level as well and return new underflow state
                // NOTE: if the min elements number is 1, then after an underflow
                //       here the child elements count is 0, so it's not required to store this node,
                //       it could just be destroyed
                m_is_underflow = store_underflowed_node(elements, underfl_el_it, relative_level);                       // MAY THROW (E: alloc, copy)
            }

            // n is not root - adjust aabb
            if ( 0 != m_parent )
            {
                // underflow state should be ok here
                // note that there may be less than min_elems elements in root
                // so this condition should be checked only here
                BOOST_GEOMETRY_INDEX_ASSERT((elements.size() < m_parameters.get_min_elements()) == m_is_underflow, "unexpected state");

                rtree::elements(*m_parent)[m_current_child_index].first
                    = rtree::elements_box<Box>(elements.begin(), elements.end(), m_translator);
            }
            // n is root node
            else
            {
                BOOST_GEOMETRY_INDEX_ASSERT(&n == &rtree::get<internal_node>(*m_root_node), "node must be the root");

                // reinsert elements from removed nodes (underflows)
                reinsert_removed_nodes_elements();                                                                  // MAY THROW (V, E: alloc, copy, N: alloc)

                // shorten the tree
                // NOTE: if the min elements number is 1, then after underflow
                //       here the number of elements may be equal to 0
                //       this can occur only for the last removed element
                if ( rtree::elements(n).size() <= 1 )
                {
                    node_pointer root_to_destroy = m_root_node;
                    if ( rtree::elements(n).size() == 0 )
                        m_root_node = 0;
                    else
                        m_root_node = rtree::elements(n)[0].second;
                    --m_leafs_level;

                    rtree::destroy_node<Allocators, internal_node>::apply(m_allocators, root_to_destroy);
                }
            }
        }
    }

    inline void operator()(leaf & n)
    {
        typedef typename rtree::elements_type<leaf>::type elements_type;
        elements_type & elements = rtree::elements(n);

        // find value and remove it
        for ( typename elements_type::iterator it = elements.begin() ; it != elements.end() ; ++it )
        {
            if ( m_translator.equals(*it, m_value) )
            {
                rtree::move_from_back(elements, it);                                                           // MAY THROW (V: copy)
                elements.pop_back();
                m_is_value_removed = true;
                break;
            }
        }

        // if value was removed
        if ( m_is_value_removed )
        {
            BOOST_GEOMETRY_INDEX_ASSERT(0 < m_parameters.get_min_elements(), "min number of elements is too small");

            // calc underflow
            m_is_underflow = elements.size() < m_parameters.get_min_elements();

            // n is not root - adjust aabb
            if ( 0 != m_parent )
            {
                rtree::elements(*m_parent)[m_current_child_index].first
                    = rtree::values_box<Box>(elements.begin(), elements.end(), m_translator);
            }
        }
    }

    bool is_value_removed() const
    {
        return m_is_value_removed;
    }

private:

    typedef std::vector< std::pair<size_type, node_pointer> > UnderflowNodes;

    void traverse_apply_visitor(internal_node &n, internal_size_type choosen_node_index)
    {
        // save previous traverse inputs and set new ones
        internal_node_pointer parent_bckup = m_parent;
        internal_size_type current_child_index_bckup = m_current_child_index;
        size_type current_level_bckup = m_current_level;

        m_parent = &n;
        m_current_child_index = choosen_node_index;
        ++m_current_level;

        // next traversing step
        rtree::apply_visitor(*this, *rtree::elements(n)[choosen_node_index].second);                    // MAY THROW (V, E: alloc, copy, N: alloc)

        // restore previous traverse inputs
        m_parent = parent_bckup;
        m_current_child_index = current_child_index_bckup;
        m_current_level = current_level_bckup;
    }

    bool store_underflowed_node(
            typename rtree::elements_type<internal_node>::type & elements,
            typename rtree::elements_type<internal_node>::type::iterator underfl_el_it,
            size_type relative_level)
    {
        // move node to the container - store node's relative level as well
        m_underflowed_nodes.push_back(std::make_pair(relative_level, underfl_el_it->second));           // MAY THROW (E: alloc, copy)

        BOOST_TRY
        {
            // NOTE: those are elements of the internal node which means that copy/move shouldn't throw
            // Though it's safer in case if the pointer type could throw in copy ctor.
            // In the future this try-catch block could be removed.
            rtree::move_from_back(elements, underfl_el_it);                                             // MAY THROW (E: copy)
            elements.pop_back();
        }
        BOOST_CATCH(...)
        {
            m_underflowed_nodes.pop_back();
            BOOST_RETHROW                                                                                 // RETHROW
        }
        BOOST_CATCH_END

        // calc underflow
        return elements.size() < m_parameters.get_min_elements();
    }

    static inline bool is_leaf(node const& n)
    {
        visitors::is_leaf<Value, Options, Box, Allocators> ilv;
        rtree::apply_visitor(ilv, n);
        return ilv.result;
    }

    void reinsert_removed_nodes_elements()
    {
        typename UnderflowNodes::reverse_iterator it = m_underflowed_nodes.rbegin();

        BOOST_TRY
        {
            // reinsert elements from removed nodes
            // begin with levels closer to the root
            for ( ; it != m_underflowed_nodes.rend() ; ++it )
            {
                // it->first is an index of a level of a node, not children
                // counted from the leafs level
                bool const node_is_leaf = it->first == 1;
                BOOST_GEOMETRY_INDEX_ASSERT(node_is_leaf == is_leaf(*it->second), "unexpected condition");
                if ( node_is_leaf )
                {
                    reinsert_node_elements(rtree::get<leaf>(*it->second), it->first);                        // MAY THROW (V, E: alloc, copy, N: alloc)

                    rtree::destroy_node<Allocators, leaf>::apply(m_allocators, it->second);
                }
                else
                {
                    reinsert_node_elements(rtree::get<internal_node>(*it->second), it->first);               // MAY THROW (V, E: alloc, copy, N: alloc)

                    rtree::destroy_node<Allocators, internal_node>::apply(m_allocators, it->second);
                }
            }

            //m_underflowed_nodes.clear();
        }
        BOOST_CATCH(...)
        {
            // destroy current and remaining nodes
            for ( ; it != m_underflowed_nodes.rend() ; ++it )
            {
                subtree_destroyer dummy(it->second, m_allocators);
            }

            //m_underflowed_nodes.clear();

            BOOST_RETHROW                                                                                      // RETHROW
        }
        BOOST_CATCH_END
    }

    template <typename Node>
    void reinsert_node_elements(Node &n, size_type node_relative_level)
    {
        typedef typename rtree::elements_type<Node>::type elements_type;
        elements_type & elements = rtree::elements(n);

        typename elements_type::iterator it = elements.begin();
        BOOST_TRY
        {
            for ( ; it != elements.end() ; ++it )
            {
                visitors::insert<
                    typename elements_type::value_type,
                    Value, Options, Translator, Box, Allocators,
                    typename Options::insert_tag
                > insert_v(
                    m_root_node, m_leafs_level, *it,
                    m_parameters, m_translator, m_allocators,
                    node_relative_level - 1);

                rtree::apply_visitor(insert_v, *m_root_node);                                               // MAY THROW (V, E: alloc, copy, N: alloc)
            }
        }
        BOOST_CATCH(...)
        {
            ++it;
            rtree::destroy_elements<Value, Options, Translator, Box, Allocators>
                ::apply(it, elements.end(), m_allocators);
            elements.clear();
            BOOST_RETHROW                                                                                     // RETHROW
        }
        BOOST_CATCH_END
    }

    Value const& m_value;
    parameters_type const& m_parameters;
    Translator const& m_translator;
    Allocators & m_allocators;

    node_pointer & m_root_node;
    size_type & m_leafs_level;

    bool m_is_value_removed;
    UnderflowNodes m_underflowed_nodes;

    // traversing input parameters
    internal_node_pointer m_parent;
    internal_size_type m_current_child_index;
    size_type m_current_level;

    // traversing output parameters
    bool m_is_underflow;
};

}}} // namespace detail::rtree::visitors

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

#endif // BOOST_GEOMETRY_INDEX_DETAIL_RTREE_VISITORS_REMOVE_HPP
Commit	Line	Data
7c673cae FG	1	// Boost.Geometry Index
	2	//
	3	// R-tree removing visitor 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_VISITORS_REMOVE_HPP
	12	#define BOOST_GEOMETRY_INDEX_DETAIL_RTREE_VISITORS_REMOVE_HPP
	13
	14	#include <boost/geometry/index/detail/rtree/visitors/is_leaf.hpp>
	15
	16	#include <boost/geometry/algorithms/covered_by.hpp>
	17
	18	namespace boost { namespace geometry { namespace index {
	19
	20	namespace detail { namespace rtree { namespace visitors {
	21
	22	// Default remove algorithm
	23	template <typename Value, typename Options, typename Translator, typename Box, typename Allocators>
	24	class remove
	25	: public rtree::visitor<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag, false>::type
	26	{
	27	typedef typename Options::parameters_type parameters_type;
	28
	29	typedef typename rtree::node<Value, parameters_type, Box, Allocators, typename Options::node_tag>::type node;
	30	typedef typename rtree::internal_node<Value, parameters_type, Box, Allocators, typename Options::node_tag>::type internal_node;
	31	typedef typename rtree::leaf<Value, parameters_type, Box, Allocators, typename Options::node_tag>::type leaf;
	32
	33	typedef rtree::subtree_destroyer<Value, Options, Translator, Box, Allocators> subtree_destroyer;
	34	typedef typename Allocators::node_pointer node_pointer;
	35	typedef typename Allocators::size_type size_type;
	36
	37	typedef typename rtree::elements_type<internal_node>::type::size_type internal_size_type;
	38
	39	//typedef typename Allocators::internal_node_pointer internal_node_pointer;
	40	typedef internal_node * internal_node_pointer;
	41
	42	public:
	43	inline remove(node_pointer & root,
	44	size_type & leafs_level,
	45	Value const& value,
	46	parameters_type const& parameters,
	47	Translator const& translator,
	48	Allocators & allocators)
	49	: m_value(value)
	50	, m_parameters(parameters)
	51	, m_translator(translator)
	52	, m_allocators(allocators)
	53	, m_root_node(root)
	54	, m_leafs_level(leafs_level)
	55	, m_is_value_removed(false)
	56	, m_parent(0)
	57	, m_current_child_index(0)
	58	, m_current_level(0)
	59	, m_is_underflow(false)
	60	{
	61	// TODO
	62	// assert - check if Value/Box is correct
	63	}
	64
65	inline void operator()(internal_node & n)
66	{
67	typedef typename rtree::elements_type<internal_node>::type children_type;
68	children_type & children = rtree::elements(n);
69
70	// traverse children which boxes intersects value's box
71	internal_size_type child_node_index = 0;
72	for ( ; child_node_index < children.size() ; ++child_node_index )
73	{
74	if ( geometry::covered_by(
75	return_ref_or_bounds(m_translator(m_value)),
76	children[child_node_index].first) )
77	{
78	// next traversing step
79	traverse_apply_visitor(n, child_node_index); // MAY THROW
80
81	if ( m_is_value_removed )
82	break;
83	}
84	}
85
86	// value was found and removed
87	if ( m_is_value_removed )
88	{
89	typedef typename rtree::elements_type<internal_node>::type elements_type;
90	typedef typename elements_type::iterator element_iterator;
91	elements_type & elements = rtree::elements(n);
92
93	// underflow occured - child node should be removed
94	if ( m_is_underflow )
95	{
96	element_iterator underfl_el_it = elements.begin() + child_node_index;
97	size_type relative_level = m_leafs_level - m_current_level;
98
99	// move node to the container - store node's relative level as well and return new underflow state
100	// NOTE: if the min elements number is 1, then after an underflow
101	// here the child elements count is 0, so it's not required to store this node,
102	// it could just be destroyed
103	m_is_underflow = store_underflowed_node(elements, underfl_el_it, relative_level); // MAY THROW (E: alloc, copy)
104	}
105
106	// n is not root - adjust aabb
107	if ( 0 != m_parent )
108	{
109	// underflow state should be ok here
110	// note that there may be less than min_elems elements in root
111	// so this condition should be checked only here
112	BOOST_GEOMETRY_INDEX_ASSERT((elements.size() < m_parameters.get_min_elements()) == m_is_underflow, "unexpected state");
113
114	rtree::elements(*m_parent)[m_current_child_index].first
115	= rtree::elements_box<Box>(elements.begin(), elements.end(), m_translator);
116	}
117	// n is root node
118	else
119	{
120	BOOST_GEOMETRY_INDEX_ASSERT(&n == &rtree::get<internal_node>(*m_root_node), "node must be the root");
121
122	// reinsert elements from removed nodes (underflows)
123	reinsert_removed_nodes_elements(); // MAY THROW (V, E: alloc, copy, N: alloc)
124
125	// shorten the tree
126	// NOTE: if the min elements number is 1, then after underflow
127	// here the number of elements may be equal to 0
128	// this can occur only for the last removed element
129	if ( rtree::elements(n).size() <= 1 )
130	{
131	node_pointer root_to_destroy = m_root_node;
132	if ( rtree::elements(n).size() == 0 )
133	m_root_node = 0;
134	else
135	m_root_node = rtree::elements(n)[0].second;
136	--m_leafs_level;
137
138	rtree::destroy_node<Allocators, internal_node>::apply(m_allocators, root_to_destroy);
139	}
140	}
141	}
142	}
143
144	inline void operator()(leaf & n)
145	{
146	typedef typename rtree::elements_type<leaf>::type elements_type;
147	elements_type & elements = rtree::elements(n);
148
149	// find value and remove it
150	for ( typename elements_type::iterator it = elements.begin() ; it != elements.end() ; ++it )
151	{
152	if ( m_translator.equals(*it, m_value) )
153	{
154	rtree::move_from_back(elements, it); // MAY THROW (V: copy)
155	elements.pop_back();
156	m_is_value_removed = true;
157	break;
158	}
159	}
160
161	// if value was removed
162	if ( m_is_value_removed )
163	{
164	BOOST_GEOMETRY_INDEX_ASSERT(0 < m_parameters.get_min_elements(), "min number of elements is too small");
165
166	// calc underflow
167	m_is_underflow = elements.size() < m_parameters.get_min_elements();
168
169	// n is not root - adjust aabb
170	if ( 0 != m_parent )
171	{
172	rtree::elements(*m_parent)[m_current_child_index].first
173	= rtree::values_box<Box>(elements.begin(), elements.end(), m_translator);
174	}
175	}
176	}
177
178	bool is_value_removed() const
179	{
180	return m_is_value_removed;
181	}
182
183	private:
184
185	typedef std::vector< std::pair<size_type, node_pointer> > UnderflowNodes;
186
187	void traverse_apply_visitor(internal_node &n, internal_size_type choosen_node_index)
188	{
189	// save previous traverse inputs and set new ones
190	internal_node_pointer parent_bckup = m_parent;
191	internal_size_type current_child_index_bckup = m_current_child_index;
192	size_type current_level_bckup = m_current_level;
193
194	m_parent = &n;
195	m_current_child_index = choosen_node_index;
196	++m_current_level;
197
198	// next traversing step
199	rtree::apply_visitor(this, rtree::elements(n)[choosen_node_index].second); // MAY THROW (V, E: alloc, copy, N: alloc)
200
201	// restore previous traverse inputs
202	m_parent = parent_bckup;
203	m_current_child_index = current_child_index_bckup;
204	m_current_level = current_level_bckup;
205	}
206
207	bool store_underflowed_node(
208	typename rtree::elements_type<internal_node>::type & elements,
209	typename rtree::elements_type<internal_node>::type::iterator underfl_el_it,
210	size_type relative_level)
211	{
212	// move node to the container - store node's relative level as well
213	m_underflowed_nodes.push_back(std::make_pair(relative_level, underfl_el_it->second)); // MAY THROW (E: alloc, copy)
214
215	BOOST_TRY
216	{
217	// NOTE: those are elements of the internal node which means that copy/move shouldn't throw
218	// Though it's safer in case if the pointer type could throw in copy ctor.
219	// In the future this try-catch block could be removed.
220	rtree::move_from_back(elements, underfl_el_it); // MAY THROW (E: copy)
221	elements.pop_back();
222	}
223	BOOST_CATCH(...)
224	{
225	m_underflowed_nodes.pop_back();
226	BOOST_RETHROW // RETHROW
227	}
228	BOOST_CATCH_END
229
230	// calc underflow
231	return elements.size() < m_parameters.get_min_elements();
232	}
233
234	static inline bool is_leaf(node const& n)
235	{
236	visitors::is_leaf<Value, Options, Box, Allocators> ilv;
237	rtree::apply_visitor(ilv, n);
238	return ilv.result;
239	}
240
241	void reinsert_removed_nodes_elements()
242	{
243	typename UnderflowNodes::reverse_iterator it = m_underflowed_nodes.rbegin();
244
245	BOOST_TRY
246	{
247	// reinsert elements from removed nodes
248	// begin with levels closer to the root
249	for ( ; it != m_underflowed_nodes.rend() ; ++it )
250	{
251	// it->first is an index of a level of a node, not children
252	// counted from the leafs level
253	bool const node_is_leaf = it->first == 1;
254	BOOST_GEOMETRY_INDEX_ASSERT(node_is_leaf == is_leaf(*it->second), "unexpected condition");
255	if ( node_is_leaf )
256	{
257	reinsert_node_elements(rtree::get<leaf>(*it->second), it->first); // MAY THROW (V, E: alloc, copy, N: alloc)
258
259	rtree::destroy_node<Allocators, leaf>::apply(m_allocators, it->second);
260	}
261	else
262	{
263	reinsert_node_elements(rtree::get<internal_node>(*it->second), it->first); // MAY THROW (V, E: alloc, copy, N: alloc)
264
265	rtree::destroy_node<Allocators, internal_node>::apply(m_allocators, it->second);
266	}
267	}
268
269	//m_underflowed_nodes.clear();
270	}
271	BOOST_CATCH(...)
272	{
273	// destroy current and remaining nodes
274	for ( ; it != m_underflowed_nodes.rend() ; ++it )
275	{
276	subtree_destroyer dummy(it->second, m_allocators);
277	}
278
279	//m_underflowed_nodes.clear();
280
281	BOOST_RETHROW // RETHROW
282	}
283	BOOST_CATCH_END
284	}
285
286	template <typename Node>
287	void reinsert_node_elements(Node &n, size_type node_relative_level)
288	{
289	typedef typename rtree::elements_type<Node>::type elements_type;
290	elements_type & elements = rtree::elements(n);
291
292	typename elements_type::iterator it = elements.begin();
293	BOOST_TRY
294	{
295	for ( ; it != elements.end() ; ++it )
296	{
297	visitors::insert<
298	typename elements_type::value_type,
299	Value, Options, Translator, Box, Allocators,
300	typename Options::insert_tag
301	> insert_v(
302	m_root_node, m_leafs_level, *it,
303	m_parameters, m_translator, m_allocators,
304	node_relative_level - 1);
305
306	rtree::apply_visitor(insert_v, *m_root_node); // MAY THROW (V, E: alloc, copy, N: alloc)
307	}
308	}
309	BOOST_CATCH(...)
310	{
311	++it;
312	rtree::destroy_elements<Value, Options, Translator, Box, Allocators>
313	::apply(it, elements.end(), m_allocators);
314	elements.clear();
315	BOOST_RETHROW // RETHROW
316	}
317	BOOST_CATCH_END
318	}
319
320	Value const& m_value;
321	parameters_type const& m_parameters;
322	Translator const& m_translator;
323	Allocators & m_allocators;
324
325	node_pointer & m_root_node;
326	size_type & m_leafs_level;
327
328	bool m_is_value_removed;
329	UnderflowNodes m_underflowed_nodes;
330
331	// traversing input parameters
332	internal_node_pointer m_parent;
333	internal_size_type m_current_child_index;
334	size_type m_current_level;
335
336	// traversing output parameters
337	bool m_is_underflow;
338	};
339
340	}}} // namespace detail::rtree::visitors
341
342	}}} // namespace boost::geometry::index
343
344	#endif // BOOST_GEOMETRY_INDEX_DETAIL_RTREE_VISITORS_REMOVE_HPP