1 // Boost.Geometry Index 2 // 3 // R-tree removing visitor implementation 4 // 5 // Copyright (c) 2011-2017 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/detail/covered_by/interface.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: remove(node_pointer & root,size_type & leafs_level,Value const & value,parameters_type const & parameters,Translator const & translator,Allocators & allocators)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 operator ()(internal_node & n)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 operator ()(leaf & n)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 is_value_removed() const178 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 traverse_apply_visitor(internal_node & n,internal_size_type choosen_node_index)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 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)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 is_leaf(node const & n)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 reinsert_removed_nodes_elements()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> reinsert_node_elements(Node & n,size_type node_relative_level)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 345