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