rtree/visitors/remove.hpp

0001 // Boost.Geometry Index
0002 //
0003 // R-tree removing visitor implementation
0004 //
0005 // Copyright (c) 2011-2017 Adam Wulkiewicz, Lodz, Poland.
0006 //
0007 // This file was modified by Oracle on 2019-2023.
0008 // Modifications copyright (c) 2019-2023 Oracle and/or its affiliates.
0009 // Contributed and/or modified by Vissarion Fysikopoulos, on behalf of Oracle
0010 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
0011 //
0012 // Use, modification and distribution is subject to the Boost Software License,
0013 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
0014 // http://www.boost.org/LICENSE_1_0.txt)
0015
0016 #ifndef BOOST_GEOMETRY_INDEX_DETAIL_RTREE_VISITORS_REMOVE_HPP
0017 #define BOOST_GEOMETRY_INDEX_DETAIL_RTREE_VISITORS_REMOVE_HPP
0018
0019 #include <boost/geometry/algorithms/detail/covered_by/interface.hpp>
0020
0021 #include <boost/geometry/index/parameters.hpp>
0022 #include <boost/geometry/index/detail/algorithms/bounds.hpp>
0023 #include <boost/geometry/index/detail/rtree/node/node.hpp>
0024 #include <boost/geometry/index/detail/rtree/node/node_elements.hpp>
0025 #include <boost/geometry/index/detail/rtree/node/subtree_destroyer.hpp>
0026 #include <boost/geometry/index/detail/rtree/visitors/destroy.hpp>
0027 #include <boost/geometry/index/detail/rtree/visitors/insert.hpp>
0028 #include <boost/geometry/index/detail/rtree/visitors/is_leaf.hpp>
0029
0030 namespace boost { namespace geometry { namespace index {
0031
0032 namespace detail { namespace rtree { namespace visitors {
0033
0034 // Default remove algorithm
0035 template <typename MembersHolder>
0036 class remove
0037     : public MembersHolder::visitor
0038 {
0039     typedef typename MembersHolder::box_type box_type;
0040     typedef typename MembersHolder::value_type value_type;
0041     typedef typename MembersHolder::parameters_type parameters_type;
0042     typedef typename MembersHolder::translator_type translator_type;
0043     typedef typename MembersHolder::allocators_type allocators_type;
0044
0045     typedef typename MembersHolder::node node;
0046     typedef typename MembersHolder::internal_node internal_node;
0047     typedef typename MembersHolder::leaf leaf;
0048
0049     typedef rtree::subtree_destroyer<MembersHolder> subtree_destroyer;
0050     typedef typename allocators_type::node_pointer node_pointer;
0051     typedef typename allocators_type::size_type size_type;
0052
0053     typedef typename rtree::elements_type<internal_node>::type::size_type internal_size_type;
0054
0055     //typedef typename Allocators::internal_node_pointer internal_node_pointer;
0056     typedef internal_node * internal_node_pointer;
0057
0058 public:
0059     inline remove(node_pointer & root,
0060                   size_type & leafs_level,
0061                   value_type const& value,
0062                   parameters_type const& parameters,
0063                   translator_type const& translator,
0064                   allocators_type & allocators)
0065         : m_value(value)
0066         , m_parameters(parameters)
0067         , m_translator(translator)
0068         , m_allocators(allocators)
0069         , m_root_node(root)
0070         , m_leafs_level(leafs_level)
0071         , m_is_value_removed(false)
0072         , m_parent(0)
0073         , m_current_child_index(0)
0074         , m_current_level(0)
0075         , m_is_underflow(false)
0076     {
0077         // TODO
0078         // assert - check if Value/Box is correct
0079     }
0080
0081     inline void operator()(internal_node & n)
0082     {
0083         typedef typename rtree::elements_type<internal_node>::type children_type;
0084         children_type & children = rtree::elements(n);
0085
0086         // traverse children which boxes intersects value's box
0087         internal_size_type child_node_index = 0;
0088         for ( ; child_node_index < children.size() ; ++child_node_index )
0089         {
0090             if ( index::detail::covered_by_bounds(m_translator(m_value),
0091                                                   children[child_node_index].first,
0092                                                   index::detail::get_strategy(m_parameters)) )
0093             {
0094                 // next traversing step
0095                 traverse_apply_visitor(n, child_node_index);                                                            // MAY THROW
0096
0097                 if ( m_is_value_removed )
0098                     break;
0099             }
0100         }
0101
0102         // value was found and removed
0103         if ( m_is_value_removed )
0104         {
0105             typedef typename rtree::elements_type<internal_node>::type elements_type;
0106             typedef typename elements_type::iterator element_iterator;
0107             elements_type & elements = rtree::elements(n);
0108
0109             // underflow occured - child node should be removed
0110             if ( m_is_underflow )
0111             {
0112                 element_iterator underfl_el_it = elements.begin() + child_node_index;
0113                 size_type relative_level = m_leafs_level - m_current_level;
0114
0115                 // move node to the container - store node's relative level as well and return new underflow state
0116                 // NOTE: if the min elements number is 1, then after an underflow
0117                 //       here the child elements count is 0, so it's not required to store this node,
0118                 //       it could just be destroyed
0119                 m_is_underflow = store_underflowed_node(elements, underfl_el_it, relative_level);                       // MAY THROW (E: alloc, copy)
0120             }
0121
0122             // n is not root - adjust aabb
0123             if ( 0 != m_parent )
0124             {
0125                 // underflow state should be ok here
0126                 // note that there may be less than min_elems elements in root
0127                 // so this condition should be checked only here
0128                 BOOST_GEOMETRY_INDEX_ASSERT((elements.size() < m_parameters.get_min_elements()) == m_is_underflow, "unexpected state");
0129
0130                 rtree::elements(*m_parent)[m_current_child_index].first
0131                     = rtree::elements_box<box_type>(elements.begin(), elements.end(), m_translator,
0132                                                     index::detail::get_strategy(m_parameters));
0133             }
0134             // n is root node
0135             else
0136             {
0137                 BOOST_GEOMETRY_INDEX_ASSERT(&n == &rtree::get<internal_node>(*m_root_node), "node must be the root");
0138
0139                 // reinsert elements from removed nodes (underflows)
0140                 reinsert_removed_nodes_elements();                                                                  // MAY THROW (V, E: alloc, copy, N: alloc)
0141
0142                 // shorten the tree
0143                 // NOTE: if the min elements number is 1, then after underflow
0144                 //       here the number of elements may be equal to 0
0145                 //       this can occur only for the last removed element
0146                 if ( rtree::elements(n).size() <= 1 )
0147                 {
0148                     node_pointer root_to_destroy = m_root_node;
0149                     if ( rtree::elements(n).size() == 0 )
0150                         m_root_node = 0;
0151                     else
0152                         m_root_node = rtree::elements(n)[0].second;
0153                     --m_leafs_level;
0154
0155                     rtree::destroy_node<allocators_type, internal_node>::apply(m_allocators, root_to_destroy);
0156                 }
0157             }
0158         }
0159     }
0160
0161     inline void operator()(leaf & n)
0162     {
0163         typedef typename rtree::elements_type<leaf>::type elements_type;
0164         elements_type & elements = rtree::elements(n);
0165
0166         // find value and remove it
0167         for ( typename elements_type::iterator it = elements.begin() ; it != elements.end() ; ++it )
0168         {
0169             if ( m_translator.equals(*it, m_value, index::detail::get_strategy(m_parameters)) )
0170             {
0171                 rtree::move_from_back(elements, it);                                                           // MAY THROW (V: copy)
0172                 elements.pop_back();
0173                 m_is_value_removed = true;
0174                 break;
0175             }
0176         }
0177
0178         // if value was removed
0179         if ( m_is_value_removed )
0180         {
0181             BOOST_GEOMETRY_INDEX_ASSERT(0 < m_parameters.get_min_elements(), "min number of elements is too small");
0182
0183             // calc underflow
0184             m_is_underflow = elements.size() < m_parameters.get_min_elements();
0185
0186             // n is not root - adjust aabb
0187             if ( 0 != m_parent )
0188             {
0189                 rtree::elements(*m_parent)[m_current_child_index].first
0190                     = rtree::values_box<box_type>(elements.begin(), elements.end(), m_translator,
0191                                                   index::detail::get_strategy(m_parameters));
0192             }
0193         }
0194     }
0195
0196     bool is_value_removed() const
0197     {
0198         return m_is_value_removed;
0199     }
0200
0201 private:
0202
0203     typedef std::vector< std::pair<size_type, node_pointer> > underflow_nodes;
0204
0205     void traverse_apply_visitor(internal_node &n, internal_size_type choosen_node_index)
0206     {
0207         // save previous traverse inputs and set new ones
0208         internal_node_pointer parent_bckup = m_parent;
0209         internal_size_type current_child_index_bckup = m_current_child_index;
0210         size_type current_level_bckup = m_current_level;
0211
0212         m_parent = &n;
0213         m_current_child_index = choosen_node_index;
0214         ++m_current_level;
0215
0216         // next traversing step
0217         rtree::apply_visitor(*this, *rtree::elements(n)[choosen_node_index].second);                    // MAY THROW (V, E: alloc, copy, N: alloc)
0218
0219         // restore previous traverse inputs
0220         m_parent = parent_bckup;
0221         m_current_child_index = current_child_index_bckup;
0222         m_current_level = current_level_bckup;
0223     }
0224
0225     bool store_underflowed_node(
0226             typename rtree::elements_type<internal_node>::type & elements,
0227             typename rtree::elements_type<internal_node>::type::iterator underfl_el_it,
0228             size_type relative_level)
0229     {
0230         // move node to the container - store node's relative level as well
0231         m_underflowed_nodes.push_back(std::make_pair(relative_level, underfl_el_it->second));           // MAY THROW (E: alloc, copy)
0232
0233         BOOST_TRY
0234         {
0235             // NOTE: those are elements of the internal node which means that copy/move shouldn't throw
0236             // Though it's safer in case if the pointer type could throw in copy ctor.
0237             // In the future this try-catch block could be removed.
0238             rtree::move_from_back(elements, underfl_el_it);                                             // MAY THROW (E: copy)
0239             elements.pop_back();
0240         }
0241         BOOST_CATCH(...)
0242         {
0243             m_underflowed_nodes.pop_back();
0244             BOOST_RETHROW                                                                                 // RETHROW
0245         }
0246         BOOST_CATCH_END
0247
0248         // calc underflow
0249         return elements.size() < m_parameters.get_min_elements();
0250     }
0251
0252     static inline bool is_leaf(node const& n)
0253     {
0254         visitors::is_leaf<MembersHolder> ilv;
0255         rtree::apply_visitor(ilv, n);
0256         return ilv.result;
0257     }
0258
0259     void reinsert_removed_nodes_elements()
0260     {
0261         typename underflow_nodes::reverse_iterator it = m_underflowed_nodes.rbegin();
0262
0263         BOOST_TRY
0264         {
0265             // reinsert elements from removed nodes
0266             // begin with levels closer to the root
0267             for ( ; it != m_underflowed_nodes.rend() ; ++it )
0268             {
0269                 // it->first is an index of a level of a node, not children
0270                 // counted from the leafs level
0271                 bool const node_is_leaf = it->first == 1;
0272                 BOOST_GEOMETRY_INDEX_ASSERT(node_is_leaf == is_leaf(*it->second), "unexpected condition");
0273                 if ( node_is_leaf )
0274                 {
0275                     reinsert_node_elements(rtree::get<leaf>(*it->second), it->first);                        // MAY THROW (V, E: alloc, copy, N: alloc)
0276
0277                     rtree::destroy_node<allocators_type, leaf>::apply(m_allocators, it->second);
0278                 }
0279                 else
0280                 {
0281                     reinsert_node_elements(rtree::get<internal_node>(*it->second), it->first);               // MAY THROW (V, E: alloc, copy, N: alloc)
0282
0283                     rtree::destroy_node<allocators_type, internal_node>::apply(m_allocators, it->second);
0284                 }
0285             }
0286
0287             //m_underflowed_nodes.clear();
0288         }
0289         BOOST_CATCH(...)
0290         {
0291             // destroy current and remaining nodes
0292             for ( ; it != m_underflowed_nodes.rend() ; ++it )
0293             {
0294                 rtree::visitors::destroy<MembersHolder>::apply(it->second, m_allocators);
0295             }
0296
0297             //m_underflowed_nodes.clear();
0298
0299             BOOST_RETHROW                                                                                      // RETHROW
0300         }
0301         BOOST_CATCH_END
0302     }
0303
0304     template <typename Node>
0305     void reinsert_node_elements(Node &n, size_type node_relative_level)
0306     {
0307         typedef typename rtree::elements_type<Node>::type elements_type;
0308         elements_type & elements = rtree::elements(n);
0309
0310         typename elements_type::iterator it = elements.begin();
0311         BOOST_TRY
0312         {
0313             for ( ; it != elements.end() ; ++it )
0314             {
0315                 visitors::insert<typename elements_type::value_type, MembersHolder>
0316                     insert_v(m_root_node, m_leafs_level, *it,
0317                              m_parameters, m_translator, m_allocators,
0318                              node_relative_level - 1);
0319
0320                 rtree::apply_visitor(insert_v, *m_root_node);                                               // MAY THROW (V, E: alloc, copy, N: alloc)
0321             }
0322         }
0323         BOOST_CATCH(...)
0324         {
0325             ++it;
0326             rtree::destroy_elements<MembersHolder>::apply(it, elements.end(), m_allocators);
0327             elements.clear();
0328             BOOST_RETHROW                                                                                     // RETHROW
0329         }
0330         BOOST_CATCH_END
0331     }
0332
0333     value_type const& m_value;
0334     parameters_type const& m_parameters;
0335     translator_type const& m_translator;
0336     allocators_type & m_allocators;
0337
0338     node_pointer & m_root_node;
0339     size_type & m_leafs_level;
0340
0341     bool m_is_value_removed;
0342     underflow_nodes m_underflowed_nodes;
0343
0344     // traversing input parameters
0345     internal_node_pointer m_parent;
0346     internal_size_type m_current_child_index;
0347     size_type m_current_level;
0348
0349     // traversing output parameters
0350     bool m_is_underflow;
0351 };
0352
0353 }}} // namespace detail::rtree::visitors
0354
0355 }}} // namespace boost::geometry::index
0356
0357 #endif // BOOST_GEOMETRY_INDEX_DETAIL_RTREE_VISITORS_REMOVE_HPP