1 // Boost.Geometry Index
2 //
3 // R-tree implementation
4 //
5 // Copyright (c) 2008 Federico J. Fernandez.
6 // Copyright (c) 2011-2019 Adam Wulkiewicz, Lodz, Poland.
7 // Copyright (c) 2020 Caian Benedicto, Campinas, Brazil.
8 //
9 // This file was modified by Oracle on 2019-2020.
10 // Modifications copyright (c) 2019-2020 Oracle and/or its affiliates.
11 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
12 //
13 // Use, modification and distribution is subject to the Boost Software License,
14 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
15 // http://www.boost.org/LICENSE_1_0.txt)
16
17 #ifndef BOOST_GEOMETRY_INDEX_RTREE_HPP
18 #define BOOST_GEOMETRY_INDEX_RTREE_HPP
19
20 // STD
21 #include <algorithm>
22 #include <type_traits>
23
24 // Boost
25 #include <boost/container/new_allocator.hpp>
26 #include <boost/move/move.hpp>
27 #include <boost/tuple/tuple.hpp>
28
29 // Boost.Geometry
30 #include <boost/geometry/core/static_assert.hpp>
31
32 #include <boost/geometry/algorithms/detail/comparable_distance/interface.hpp>
33 #include <boost/geometry/algorithms/detail/covered_by/interface.hpp>
34 #include <boost/geometry/algorithms/detail/disjoint/interface.hpp>
35 #include <boost/geometry/algorithms/detail/equals/interface.hpp>
36 #include <boost/geometry/algorithms/detail/intersects/interface.hpp>
37 #include <boost/geometry/algorithms/detail/overlaps/interface.hpp>
38 #include <boost/geometry/algorithms/detail/touches/interface.hpp>
39 #include <boost/geometry/algorithms/detail/within/interface.hpp>
40 #include <boost/geometry/algorithms/centroid.hpp>
41
42 #include <boost/geometry/geometries/point.hpp>
43 #include <boost/geometry/geometries/box.hpp>
44
45 // Boost.Geometry.Index
46 #include <boost/geometry/index/detail/config_begin.hpp>
47
48 #include <boost/geometry/index/detail/assert.hpp>
49 #include <boost/geometry/index/detail/exception.hpp>
50
51 #include <boost/geometry/index/detail/rtree/options.hpp>
52
53 #include <boost/geometry/index/indexable.hpp>
54 #include <boost/geometry/index/equal_to.hpp>
55
56 #include <boost/geometry/index/detail/translator.hpp>
57
58 #include <boost/geometry/index/predicates.hpp>
59 #include <boost/geometry/index/distance_predicates.hpp>
60 #include <boost/geometry/index/detail/rtree/adaptors.hpp>
61
62 #include <boost/geometry/index/detail/meta.hpp>
63 #include <boost/geometry/index/detail/utilities.hpp>
64 #include <boost/geometry/index/detail/rtree/node/node.hpp>
65
66 #include <boost/geometry/index/detail/algorithms/is_valid.hpp>
67
68 #include <boost/geometry/index/detail/rtree/visitors/insert.hpp>
69 #include <boost/geometry/index/detail/rtree/visitors/iterator.hpp>
70 #include <boost/geometry/index/detail/rtree/visitors/remove.hpp>
71 #include <boost/geometry/index/detail/rtree/visitors/copy.hpp>
72 #include <boost/geometry/index/detail/rtree/visitors/destroy.hpp>
73 #include <boost/geometry/index/detail/rtree/visitors/spatial_query.hpp>
74 #include <boost/geometry/index/detail/rtree/visitors/distance_query.hpp>
75 #include <boost/geometry/index/detail/rtree/visitors/count.hpp>
76 #include <boost/geometry/index/detail/rtree/visitors/children_box.hpp>
77
78 #include <boost/geometry/index/detail/rtree/linear/linear.hpp>
79 #include <boost/geometry/index/detail/rtree/quadratic/quadratic.hpp>
80 #include <boost/geometry/index/detail/rtree/rstar/rstar.hpp>
81 //#include <boost/geometry/extensions/index/detail/rtree/kmeans/kmeans.hpp>
82
83 #include <boost/geometry/index/detail/rtree/pack_create.hpp>
84
85 #include <boost/geometry/index/inserter.hpp>
86
87 #include <boost/geometry/index/detail/rtree/utilities/view.hpp>
88
89 #include <boost/geometry/index/detail/rtree/iterators.hpp>
90 #include <boost/geometry/index/detail/rtree/query_iterators.hpp>
91
92 #ifdef BOOST_GEOMETRY_INDEX_DETAIL_EXPERIMENTAL
93 // serialization
94 #include <boost/geometry/index/detail/serialization.hpp>
95 #endif
96
97 #include <boost/geometry/util/range.hpp>
98 #include <boost/geometry/util/type_traits.hpp>
99
100 // TODO change the name to bounding_tree
101
102 /*!
103 \defgroup rtree_functions R-tree free functions (boost::geometry::index::)
104 */
105
106 namespace boost { namespace geometry { namespace index {
107
108 /*!
109 \brief The R-tree spatial index.
110
111 This is self-balancing spatial index capable to store various types of Values
112 and balancing algorithms.
113
114 \par Parameters
115 The user must pass a type defining the Parameters which will
116 be used in rtree creation process. This type is used e.g. to specify balancing
117 algorithm with specific parameters like min and max number of elements in node.
118
119 \par
120 Predefined algorithms with compile-time parameters are:
121 \li <tt>boost::geometry::index::linear</tt>,
122 \li <tt>boost::geometry::index::quadratic</tt>,
123 \li <tt>boost::geometry::index::rstar</tt>.
124
125 \par
126 Predefined algorithms with run-time parameters are:
127 \li \c boost::geometry::index::dynamic_linear,
128 \li \c boost::geometry::index::dynamic_quadratic,
129 \li \c boost::geometry::index::dynamic_rstar.
130
131 \par IndexableGetter
132 The object of IndexableGetter type translates from Value to Indexable each time
133 r-tree requires it. This means that this operation is done for each Value
134 access. Therefore the IndexableGetter should return the Indexable by
135 a reference type. The Indexable should not be calculated since it could harm
136 the performance. The default IndexableGetter can translate all types adapted
137 to Point, Box or Segment concepts (called Indexables). Furthermore, it can
138 handle <tt>std::pair<Indexable, T></tt>, <tt>std::tuple<Indexable, ...></tt>
139 and <tt>boost::tuple<Indexable, ...></tt>. For example, for Value
140 of type <tt>std::pair<Box, int></tt>, the default IndexableGetter translates
141 from <tt>std::pair<Box, int> const&</tt> to <tt>Box const&</tt>.
142
143 \par EqualTo
144 The object of EqualTo type compares Values and returns <tt>true</tt> if they
145 are equal. It's similar to <tt>std::equal_to<></tt>. The default EqualTo
146 returns the result of <tt>boost::geometry::equals()</tt> for types adapted to
147 some Geometry concept defined in Boost.Geometry and the result of
148 <tt>operator==</tt> for other types. Components of Pairs and Tuples are
149 compared left-to-right.
150
151 \tparam Value The type of objects stored in the container.
152 \tparam Parameters Compile-time parameters.
153 \tparam IndexableGetter The function object extracting Indexable from Value.
154 \tparam EqualTo The function object comparing objects of type Value.
155 \tparam Allocator The allocator used to allocate/deallocate memory,
156 construct/destroy nodes and Values.
157 */
158 template
159 <
160 typename Value,
161 typename Parameters,
162 typename IndexableGetter = index::indexable<Value>,
163 typename EqualTo = index::equal_to<Value>,
164 typename Allocator = boost::container::new_allocator<Value>
165 >
166 class rtree
167 {
168 BOOST_COPYABLE_AND_MOVABLE(rtree)
169
170 public:
171 /*! \brief The type of Value stored in the container. */
172 typedef Value value_type;
173 /*! \brief R-tree parameters type. */
174 typedef Parameters parameters_type;
175 /*! \brief The function object extracting Indexable from Value. */
176 typedef IndexableGetter indexable_getter;
177 /*! \brief The function object comparing objects of type Value. */
178 typedef EqualTo value_equal;
179 /*! \brief The type of allocator used by the container. */
180 typedef Allocator allocator_type;
181
182 // TODO: SHOULD THIS TYPE BE REMOVED?
183 /*! \brief The Indexable type to which Value is translated. */
184 typedef typename index::detail::indexable_type<
185 detail::translator<IndexableGetter, EqualTo>
186 >::type indexable_type;
187
188 /*! \brief The Box type used by the R-tree. */
189 typedef geometry::model::box<
190 geometry::model::point<
191 typename coordinate_type<indexable_type>::type,
192 dimension<indexable_type>::value,
193 typename coordinate_system<indexable_type>::type
194 >
195 >
196 bounds_type;
197
198 private:
199
200 typedef bounds_type box_type;
201
202 struct members_holder
203 : public detail::translator<IndexableGetter, EqualTo>
204 , public Parameters
205 , public detail::rtree::allocators
206 <
207 Allocator,
208 Value,
209 Parameters,
210 bounds_type,
211 typename detail::rtree::options_type<Parameters>::type::node_tag
212 >
213 {
214 typedef Value value_type;
215 typedef typename rtree::bounds_type bounds_type;
216 typedef Parameters parameters_type;
217 //typedef IndexableGetter indexable_getter;
218 //typedef EqualTo value_equal;
219 //typedef Allocator allocator_type;
220
221 typedef bounds_type box_type;
222 typedef detail::translator<IndexableGetter, EqualTo> translator_type;
223 typedef typename detail::rtree::options_type<Parameters>::type options_type;
224 typedef typename options_type::node_tag node_tag;
225 typedef detail::rtree::allocators
226 <
227 Allocator, Value, Parameters, bounds_type, node_tag
228 > allocators_type;
229
230 typedef typename detail::rtree::node
231 <
232 value_type, parameters_type, bounds_type, allocators_type, node_tag
233 >::type node;
234 typedef typename detail::rtree::internal_node
235 <
236 value_type, parameters_type, bounds_type, allocators_type, node_tag
237 >::type internal_node;
238 typedef typename detail::rtree::leaf
239 <
240 value_type, parameters_type, bounds_type, allocators_type, node_tag
241 >::type leaf;
242
243 // TODO: only one visitor type is needed
244 typedef typename detail::rtree::visitor
245 <
246 value_type, parameters_type, bounds_type, allocators_type, node_tag, false
247 >::type visitor;
248 typedef typename detail::rtree::visitor
249 <
250 value_type, parameters_type, bounds_type, allocators_type, node_tag, true
251 >::type visitor_const;
252
253 typedef typename allocators_type::node_pointer node_pointer;
254
255 typedef ::boost::container::allocator_traits<Allocator> allocator_traits_type;
256 typedef typename allocators_type::size_type size_type;
257
258 private:
259 members_holder(members_holder const&);
260 members_holder & operator=(members_holder const&);
261
262 public:
263 template <typename IndGet, typename ValEq, typename Alloc>
members_holderboost::geometry::index::rtree::members_holder264 members_holder(IndGet const& ind_get,
265 ValEq const& val_eq,
266 Parameters const& parameters,
267 BOOST_FWD_REF(Alloc) alloc)
268 : translator_type(ind_get, val_eq)
269 , Parameters(parameters)
270 , allocators_type(boost::forward<Alloc>(alloc))
271 , values_count(0)
272 , leafs_level(0)
273 , root(0)
274 {}
275
276 template <typename IndGet, typename ValEq>
members_holderboost::geometry::index::rtree::members_holder277 members_holder(IndGet const& ind_get,
278 ValEq const& val_eq,
279 Parameters const& parameters)
280 : translator_type(ind_get, val_eq)
281 , Parameters(parameters)
282 , allocators_type()
283 , values_count(0)
284 , leafs_level(0)
285 , root(0)
286 {}
287
translatorboost::geometry::index::rtree::members_holder288 translator_type const& translator() const { return *this; }
289
indexable_getterboost::geometry::index::rtree::members_holder290 IndexableGetter const& indexable_getter() const { return *this; }
indexable_getterboost::geometry::index::rtree::members_holder291 IndexableGetter & indexable_getter() { return *this; }
equal_toboost::geometry::index::rtree::members_holder292 EqualTo const& equal_to() const { return *this; }
equal_toboost::geometry::index::rtree::members_holder293 EqualTo & equal_to() { return *this; }
parametersboost::geometry::index::rtree::members_holder294 Parameters const& parameters() const { return *this; }
parametersboost::geometry::index::rtree::members_holder295 Parameters & parameters() { return *this; }
allocatorsboost::geometry::index::rtree::members_holder296 allocators_type const& allocators() const { return *this; }
allocatorsboost::geometry::index::rtree::members_holder297 allocators_type & allocators() { return *this; }
298
299 size_type values_count;
300 size_type leafs_level;
301 node_pointer root;
302 };
303
304 typedef typename members_holder::translator_type translator_type;
305 typedef typename members_holder::options_type options_type;
306 typedef typename members_holder::allocators_type allocators_type;
307 typedef typename members_holder::node node;
308 typedef typename members_holder::internal_node internal_node;
309 typedef typename members_holder::leaf leaf;
310
311 typedef typename members_holder::node_pointer node_pointer;
312 typedef typename members_holder::allocator_traits_type allocator_traits_type;
313
314 friend class detail::rtree::utilities::view<rtree>;
315 #ifdef BOOST_GEOMETRY_INDEX_DETAIL_EXPERIMENTAL
316 friend class detail::rtree::private_view<rtree>;
317 friend class detail::rtree::const_private_view<rtree>;
318 #endif
319
320 public:
321
322 /*! \brief Type of reference to Value. */
323 typedef typename allocators_type::reference reference;
324 /*! \brief Type of reference to const Value. */
325 typedef typename allocators_type::const_reference const_reference;
326 /*! \brief Type of pointer to Value. */
327 typedef typename allocators_type::pointer pointer;
328 /*! \brief Type of pointer to const Value. */
329 typedef typename allocators_type::const_pointer const_pointer;
330 /*! \brief Type of difference type. */
331 typedef typename allocators_type::difference_type difference_type;
332 /*! \brief Unsigned integral type used by the container. */
333 typedef typename allocators_type::size_type size_type;
334
335 /*! \brief Type of const iterator, category ForwardIterator. */
336 typedef index::detail::rtree::iterators::iterator
337 <
338 value_type, options_type, translator_type, box_type, allocators_type
339 > const_iterator;
340
341 /*! \brief Type of const query iterator, category ForwardIterator. */
342 typedef index::detail::rtree::iterators::query_iterator
343 <
344 value_type, allocators_type
345 > const_query_iterator;
346
347 public:
348
349 /*!
350 \brief The constructor.
351
352 \param parameters The parameters object.
353 \param getter The function object extracting Indexable from Value.
354 \param equal The function object comparing Values.
355
356 \par Throws
357 If allocator default constructor throws.
358 */
rtree(parameters_type const & parameters=parameters_type (),indexable_getter const & getter=indexable_getter (),value_equal const & equal=value_equal ())359 inline explicit rtree(parameters_type const& parameters = parameters_type(),
360 indexable_getter const& getter = indexable_getter(),
361 value_equal const& equal = value_equal())
362 : m_members(getter, equal, parameters)
363 {}
364
365 /*!
366 \brief The constructor.
367
368 \param parameters The parameters object.
369 \param getter The function object extracting Indexable from Value.
370 \param equal The function object comparing Values.
371 \param allocator The allocator object.
372
373 \par Throws
374 If allocator copy constructor throws.
375 */
rtree(parameters_type const & parameters,indexable_getter const & getter,value_equal const & equal,allocator_type const & allocator)376 inline rtree(parameters_type const& parameters,
377 indexable_getter const& getter,
378 value_equal const& equal,
379 allocator_type const& allocator)
380 : m_members(getter, equal, parameters, allocator)
381 {}
382
383 /*!
384 \brief The constructor.
385
386 The tree is created using packing algorithm.
387
388 \param first The beginning of the range of Values.
389 \param last The end of the range of Values.
390 \param parameters The parameters object.
391 \param getter The function object extracting Indexable from Value.
392 \param equal The function object comparing Values.
393 \param allocator The allocator object.
394
395 \par Throws
396 \li If allocator copy constructor throws.
397 \li If Value copy constructor or copy assignment throws.
398 \li If allocation throws or returns invalid value.
399 */
400 template<typename Iterator>
rtree(Iterator first,Iterator last,parameters_type const & parameters=parameters_type (),indexable_getter const & getter=indexable_getter (),value_equal const & equal=value_equal (),allocator_type const & allocator=allocator_type ())401 inline rtree(Iterator first, Iterator last,
402 parameters_type const& parameters = parameters_type(),
403 indexable_getter const& getter = indexable_getter(),
404 value_equal const& equal = value_equal(),
405 allocator_type const& allocator = allocator_type())
406 : m_members(getter, equal, parameters, allocator)
407 {
408 pack_construct(first, last, boost::container::new_allocator<void>());
409 }
410
411 /*!
412 \brief The constructor.
413
414 The tree is created using packing algorithm.
415
416 \param rng The range of Values.
417 \param parameters The parameters object.
418 \param getter The function object extracting Indexable from Value.
419 \param equal The function object comparing Values.
420 \param allocator The allocator object.
421
422 \par Throws
423 \li If allocator copy constructor throws.
424 \li If Value copy constructor or copy assignment throws.
425 \li If allocation throws or returns invalid value.
426 */
427 template<typename Range>
rtree(Range const & rng,parameters_type const & parameters=parameters_type (),indexable_getter const & getter=indexable_getter (),value_equal const & equal=value_equal (),allocator_type const & allocator=allocator_type ())428 inline explicit rtree(Range const& rng,
429 parameters_type const& parameters = parameters_type(),
430 indexable_getter const& getter = indexable_getter(),
431 value_equal const& equal = value_equal(),
432 allocator_type const& allocator = allocator_type())
433 : m_members(getter, equal, parameters, allocator)
434 {
435 pack_construct(::boost::begin(rng), ::boost::end(rng), boost::container::new_allocator<void>());
436 }
437
438 /*!
439 \brief The constructor.
440
441 The tree is created using packing algorithm and a temporary packing allocator.
442
443 \param first The beginning of the range of Values.
444 \param last The end of the range of Values.
445 \param parameters The parameters object.
446 \param getter The function object extracting Indexable from Value.
447 \param equal The function object comparing Values.
448 \param allocator The allocator object for persistent data in the tree.
449 \param temp_allocator The temporary allocator object used when packing.
450
451 \par Throws
452 \li If allocator copy constructor throws.
453 \li If Value copy constructor or copy assignment throws.
454 \li If allocation throws or returns invalid value.
455 */
456 template<typename Iterator, typename PackAlloc>
rtree(Iterator first,Iterator last,parameters_type const & parameters,indexable_getter const & getter,value_equal const & equal,allocator_type const & allocator,PackAlloc const & temp_allocator)457 inline rtree(Iterator first, Iterator last,
458 parameters_type const& parameters,
459 indexable_getter const& getter,
460 value_equal const& equal,
461 allocator_type const& allocator,
462 PackAlloc const& temp_allocator)
463 : m_members(getter, equal, parameters, allocator)
464 {
465 pack_construct(first, last, temp_allocator);
466 }
467
468 /*!
469 \brief The constructor.
470
471 The tree is created using packing algorithm and a temporary packing allocator.
472
473 \param rng The range of Values.
474 \param parameters The parameters object.
475 \param getter The function object extracting Indexable from Value.
476 \param equal The function object comparing Values.
477 \param allocator The allocator object for persistent data in the tree.
478 \param temp_allocator The temporary allocator object used when packing.
479
480 \par Throws
481 \li If allocator copy constructor throws.
482 \li If Value copy constructor or copy assignment throws.
483 \li If allocation throws or returns invalid value.
484 */
485 template<typename Range, typename PackAlloc>
rtree(Range const & rng,parameters_type const & parameters,indexable_getter const & getter,value_equal const & equal,allocator_type const & allocator,PackAlloc const & temp_allocator)486 inline explicit rtree(Range const& rng,
487 parameters_type const& parameters,
488 indexable_getter const& getter,
489 value_equal const& equal,
490 allocator_type const& allocator,
491 PackAlloc const& temp_allocator)
492 : m_members(getter, equal, parameters, allocator)
493 {
494 pack_construct(::boost::begin(rng), ::boost::end(rng), temp_allocator);
495 }
496
497 /*!
498 \brief The constructor.
499
500 The tree is created using packing algorithm and a temporary packing allocator.
501
502 \param first The beginning of the range of Values.
503 \param last The end of the range of Values.
504 \param allocator The allocator object for persistent data in the tree.
505
506 \par Throws
507 \li If allocator copy constructor throws.
508 \li If Value copy constructor or copy assignment throws.
509 \li If allocation throws or returns invalid value.
510 */
511 template<typename Iterator>
rtree(Iterator first,Iterator last,allocator_type const & allocator)512 inline rtree(Iterator first, Iterator last,
513 allocator_type const& allocator)
514 : m_members(indexable_getter(), value_equal(), parameters_type(), allocator)
515 {
516 pack_construct(first, last, boost::container::new_allocator<void>());
517 }
518
519 /*!
520 \brief The constructor.
521
522 The tree is created using packing algorithm and a temporary packing allocator.
523
524 \param rng The range of Values.
525 \param allocator The allocator object for persistent data in the tree.
526
527 \par Throws
528 \li If allocator copy constructor throws.
529 \li If Value copy constructor or copy assignment throws.
530 \li If allocation throws or returns invalid value.
531 */
532 template<typename Range>
rtree(Range const & rng,allocator_type const & allocator)533 inline explicit rtree(Range const& rng,
534 allocator_type const& allocator)
535 : m_members(indexable_getter(), value_equal(), parameters_type(), allocator)
536 {
537 pack_construct(::boost::begin(rng), ::boost::end(rng), boost::container::new_allocator<void>());
538 }
539
540 /*!
541 \brief The constructor.
542
543 The tree is created using packing algorithm and a temporary packing allocator.
544
545 \param first The beginning of the range of Values.
546 \param last The end of the range of Values.
547 \param allocator The allocator object for persistent data in the tree.
548 \param temp_allocator The temporary allocator object used when packing.
549
550 \par Throws
551 \li If allocator copy constructor throws.
552 \li If Value copy constructor or copy assignment throws.
553 \li If allocation throws or returns invalid value.
554 */
555 template<typename Iterator, typename PackAlloc>
rtree(Iterator first,Iterator last,allocator_type const & allocator,PackAlloc const & temp_allocator)556 inline rtree(Iterator first, Iterator last,
557 allocator_type const& allocator,
558 PackAlloc const& temp_allocator)
559 : m_members(indexable_getter(), value_equal(), parameters_type(), allocator)
560 {
561 pack_construct(first, last, temp_allocator);
562 }
563
564 /*!
565 \brief The constructor.
566
567 The tree is created using packing algorithm and a temporary packing allocator.
568
569 \param rng The range of Values.
570 \param allocator The allocator object for persistent data in the tree.
571 \param temp_allocator The temporary allocator object used when packing.
572
573 \par Throws
574 \li If allocator copy constructor throws.
575 \li If Value copy constructor or copy assignment throws.
576 \li If allocation throws or returns invalid value.
577 */
578 template<typename Range, typename PackAlloc>
rtree(Range const & rng,allocator_type const & allocator,PackAlloc const & temp_allocator)579 inline explicit rtree(Range const& rng,
580 allocator_type const& allocator,
581 PackAlloc const& temp_allocator)
582 : m_members(indexable_getter(), value_equal(), parameters_type(), allocator)
583 {
584 pack_construct(::boost::begin(rng), ::boost::end(rng), temp_allocator);
585 }
586
587 /*!
588 \brief The destructor.
589
590 \par Throws
591 Nothing.
592 */
~rtree()593 inline ~rtree()
594 {
595 this->raw_destroy(*this);
596 }
597
598 /*!
599 \brief The copy constructor.
600
601 It uses parameters, translator and allocator from the source tree.
602
603 \param src The rtree which content will be copied.
604
605 \par Throws
606 \li If allocator copy constructor throws.
607 \li If Value copy constructor throws.
608 \li If allocation throws or returns invalid value.
609 */
rtree(rtree const & src)610 inline rtree(rtree const& src)
611 : m_members(src.m_members.indexable_getter(),
612 src.m_members.equal_to(),
613 src.m_members.parameters(),
614 allocator_traits_type::select_on_container_copy_construction(src.get_allocator()))
615 {
616 this->raw_copy(src, *this, false);
617 }
618
619 /*!
620 \brief The copy constructor.
621
622 It uses Parameters and translator from the source tree.
623
624 \param src The rtree which content will be copied.
625 \param allocator The allocator which will be used.
626
627 \par Throws
628 \li If allocator copy constructor throws.
629 \li If Value copy constructor throws.
630 \li If allocation throws or returns invalid value.
631 */
rtree(rtree const & src,allocator_type const & allocator)632 inline rtree(rtree const& src, allocator_type const& allocator)
633 : m_members(src.m_members.indexable_getter(),
634 src.m_members.equal_to(),
635 src.m_members.parameters(), allocator)
636 {
637 this->raw_copy(src, *this, false);
638 }
639
640 /*!
641 \brief The moving constructor.
642
643 It uses parameters, translator and allocator from the source tree.
644
645 \param src The rtree which content will be moved.
646
647 \par Throws
648 Nothing.
649 */
rtree(BOOST_RV_REF (rtree)src)650 inline rtree(BOOST_RV_REF(rtree) src)
651 : m_members(src.m_members.indexable_getter(),
652 src.m_members.equal_to(),
653 src.m_members.parameters(),
654 boost::move(src.m_members.allocators()))
655 {
656 boost::swap(m_members.values_count, src.m_members.values_count);
657 boost::swap(m_members.leafs_level, src.m_members.leafs_level);
658 boost::swap(m_members.root, src.m_members.root);
659 }
660
661 /*!
662 \brief The moving constructor.
663
664 It uses parameters and translator from the source tree.
665
666 \param src The rtree which content will be moved.
667 \param allocator The allocator.
668
669 \par Throws
670 \li If allocator copy constructor throws.
671 \li If Value copy constructor throws (only if allocators aren't equal).
672 \li If allocation throws or returns invalid value (only if allocators aren't equal).
673 */
rtree(BOOST_RV_REF (rtree)src,allocator_type const & allocator)674 inline rtree(BOOST_RV_REF(rtree) src, allocator_type const& allocator)
675 : m_members(src.m_members.indexable_getter(),
676 src.m_members.equal_to(),
677 src.m_members.parameters(),
678 allocator)
679 {
680 if ( src.m_members.allocators() == allocator )
681 {
682 boost::swap(m_members.values_count, src.m_members.values_count);
683 boost::swap(m_members.leafs_level, src.m_members.leafs_level);
684 boost::swap(m_members.root, src.m_members.root);
685 }
686 else
687 {
688 this->raw_copy(src, *this, false);
689 }
690 }
691
692 /*!
693 \brief The assignment operator.
694
695 It uses parameters and translator from the source tree.
696
697 \param src The rtree which content will be copied.
698
699 \par Throws
700 \li If Value copy constructor throws.
701 \li If allocation throws.
702 \li If allocation throws or returns invalid value.
703 */
operator =(BOOST_COPY_ASSIGN_REF (rtree)src)704 inline rtree & operator=(BOOST_COPY_ASSIGN_REF(rtree) src)
705 {
706 if ( &src != this )
707 {
708 allocators_type & this_allocs = m_members.allocators();
709 allocators_type const& src_allocs = src.m_members.allocators();
710
711 // NOTE: if propagate is true for std allocators on darwin 4.2.1, glibc++
712 // (allocators stored as base classes of members_holder)
713 // copying them changes values_count, in this case it doesn't cause errors since data must be copied
714
715 typedef std::integral_constant<bool,
716 allocator_traits_type::propagate_on_container_copy_assignment::value
717 > propagate;
718
719 if ( propagate::value && !(this_allocs == src_allocs) )
720 this->raw_destroy(*this);
721 detail::assign_cond(this_allocs, src_allocs, propagate());
722
723 // It uses m_allocators
724 this->raw_copy(src, *this, true);
725 }
726
727 return *this;
728 }
729
730 /*!
731 \brief The moving assignment.
732
733 It uses parameters and translator from the source tree.
734
735 \param src The rtree which content will be moved.
736
737 \par Throws
738 Only if allocators aren't equal.
739 \li If Value copy constructor throws.
740 \li If allocation throws or returns invalid value.
741 */
operator =(BOOST_RV_REF (rtree)src)742 inline rtree & operator=(BOOST_RV_REF(rtree) src)
743 {
744 if ( &src != this )
745 {
746 allocators_type & this_allocs = m_members.allocators();
747 allocators_type & src_allocs = src.m_members.allocators();
748
749 if ( this_allocs == src_allocs )
750 {
751 this->raw_destroy(*this);
752
753 m_members.indexable_getter() = src.m_members.indexable_getter();
754 m_members.equal_to() = src.m_members.equal_to();
755 m_members.parameters() = src.m_members.parameters();
756
757 boost::swap(m_members.values_count, src.m_members.values_count);
758 boost::swap(m_members.leafs_level, src.m_members.leafs_level);
759 boost::swap(m_members.root, src.m_members.root);
760
761 // NOTE: if propagate is true for std allocators on darwin 4.2.1, glibc++
762 // (allocators stored as base classes of members_holder)
763 // moving them changes values_count
764
765 typedef std::integral_constant<bool,
766 allocator_traits_type::propagate_on_container_move_assignment::value
767 > propagate;
768 detail::move_cond(this_allocs, src_allocs, propagate());
769 }
770 else
771 {
772 // TODO - shouldn't here propagate_on_container_copy_assignment be checked like in operator=(const&)?
773
774 // It uses m_allocators
775 this->raw_copy(src, *this, true);
776 }
777 }
778
779 return *this;
780 }
781
782 /*!
783 \brief Swaps contents of two rtrees.
784
785 Parameters, translator and allocators are swapped as well.
786
787 \param other The rtree which content will be swapped with this rtree content.
788
789 \par Throws
790 If allocators swap throws.
791 */
swap(rtree & other)792 void swap(rtree & other)
793 {
794 boost::swap(m_members.indexable_getter(), other.m_members.indexable_getter());
795 boost::swap(m_members.equal_to(), other.m_members.equal_to());
796 boost::swap(m_members.parameters(), other.m_members.parameters());
797
798 // NOTE: if propagate is true for std allocators on darwin 4.2.1, glibc++
799 // (allocators stored as base classes of members_holder)
800 // swapping them changes values_count
801
802 typedef std::integral_constant<bool,
803 allocator_traits_type::propagate_on_container_swap::value
804 > propagate;
805 detail::swap_cond(m_members.allocators(), other.m_members.allocators(), propagate());
806
807 boost::swap(m_members.values_count, other.m_members.values_count);
808 boost::swap(m_members.leafs_level, other.m_members.leafs_level);
809 boost::swap(m_members.root, other.m_members.root);
810 }
811
812 /*!
813 \brief Insert a value to the index.
814
815 \param value The value which will be stored in the container.
816
817 \par Throws
818 \li If Value copy constructor or copy assignment throws.
819 \li If allocation throws or returns invalid value.
820
821 \warning
822 This operation only guarantees that there will be no memory leaks.
823 After an exception is thrown the R-tree may be left in an inconsistent state,
824 elements must not be inserted or removed. Other operations are allowed however
825 some of them may return invalid data.
826 */
insert(value_type const & value)827 inline void insert(value_type const& value)
828 {
829 if ( !m_members.root )
830 this->raw_create();
831
832 this->raw_insert(value);
833 }
834
835 /*!
836 \brief Insert a range of values to the index.
837
838 \param first The beginning of the range of values.
839 \param last The end of the range of values.
840
841 \par Throws
842 \li If Value copy constructor or copy assignment throws.
843 \li If allocation throws or returns invalid value.
844
845 \warning
846 This operation only guarantees that there will be no memory leaks.
847 After an exception is thrown the R-tree may be left in an inconsistent state,
848 elements must not be inserted or removed. Other operations are allowed however
849 some of them may return invalid data.
850 */
851 template <typename Iterator>
insert(Iterator first,Iterator last)852 inline void insert(Iterator first, Iterator last)
853 {
854 if ( !m_members.root )
855 this->raw_create();
856
857 for ( ; first != last ; ++first )
858 this->raw_insert(*first);
859 }
860
861 /*!
862 \brief Insert a value created using convertible object or a range of values to the index.
863
864 \param conv_or_rng An object of type convertible to value_type or a range of values.
865
866 \par Throws
867 \li If Value copy constructor or copy assignment throws.
868 \li If allocation throws or returns invalid value.
869
870 \warning
871 This operation only guarantees that there will be no memory leaks.
872 After an exception is thrown the R-tree may be left in an inconsistent state,
873 elements must not be inserted or removed. Other operations are allowed however
874 some of them may return invalid data.
875 */
876 template <typename ConvertibleOrRange>
insert(ConvertibleOrRange const & conv_or_rng)877 inline void insert(ConvertibleOrRange const& conv_or_rng)
878 {
879 if ( !m_members.root )
880 this->raw_create();
881
882 typedef std::is_convertible<ConvertibleOrRange, value_type> is_conv_t;
883 typedef range::detail::is_range<ConvertibleOrRange> is_range_t;
884 BOOST_GEOMETRY_STATIC_ASSERT((is_conv_t::value || is_range_t::value),
885 "The argument has to be convertible to Value type or be a Range.",
886 ConvertibleOrRange);
887
888 this->insert_dispatch(conv_or_rng, is_conv_t());
889 }
890
891 /*!
892 \brief Remove a value from the container.
893
894 In contrast to the \c std::set or <tt>std::map erase()</tt> method
895 this method removes only one value from the container.
896
897 \param value The value which will be removed from the container.
898
899 \return 1 if the value was removed, 0 otherwise.
900
901 \par Throws
902 \li If Value copy constructor or copy assignment throws.
903 \li If allocation throws or returns invalid value.
904
905 \warning
906 This operation only guarantees that there will be no memory leaks.
907 After an exception is thrown the R-tree may be left in an inconsistent state,
908 elements must not be inserted or removed. Other operations are allowed however
909 some of them may return invalid data.
910 */
remove(value_type const & value)911 inline size_type remove(value_type const& value)
912 {
913 if ( !m_members.root )
914 return 0;
915
916 return this->raw_remove(value);
917 }
918
919 /*!
920 \brief Remove a range of values from the container.
921
922 In contrast to the \c std::set or <tt>std::map erase()</tt> method
923 it doesn't take iterators pointing to values stored in this container. It removes values equal
924 to these passed as a range. Furthermore this method removes only one value for each one passed
925 in the range, not all equal values.
926
927 \param first The beginning of the range of values.
928 \param last The end of the range of values.
929
930 \return The number of removed values.
931
932 \par Throws
933 \li If Value copy constructor or copy assignment throws.
934 \li If allocation throws or returns invalid value.
935
936 \warning
937 This operation only guarantees that there will be no memory leaks.
938 After an exception is thrown the R-tree may be left in an inconsistent state,
939 elements must not be inserted or removed. Other operations are allowed however
940 some of them may return invalid data.
941 */
942 template <typename Iterator>
remove(Iterator first,Iterator last)943 inline size_type remove(Iterator first, Iterator last)
944 {
945 size_type result = 0;
946
947 if ( !m_members.root )
948 return result;
949
950 for ( ; first != last ; ++first )
951 result += this->raw_remove(*first);
952 return result;
953 }
954
955 /*!
956 \brief Remove value corresponding to an object convertible to it or a range of values from the container.
957
958 In contrast to the \c std::set or <tt>std::map erase()</tt> method
959 it removes values equal to these passed as a range. Furthermore, this method removes only
960 one value for each one passed in the range, not all equal values.
961
962 \param conv_or_rng The object of type convertible to value_type or a range of values.
963
964 \return The number of removed values.
965
966 \par Throws
967 \li If Value copy constructor or copy assignment throws.
968 \li If allocation throws or returns invalid value.
969
970 \warning
971 This operation only guarantees that there will be no memory leaks.
972 After an exception is thrown the R-tree may be left in an inconsistent state,
973 elements must not be inserted or removed. Other operations are allowed however
974 some of them may return invalid data.
975 */
976 template <typename ConvertibleOrRange>
remove(ConvertibleOrRange const & conv_or_rng)977 inline size_type remove(ConvertibleOrRange const& conv_or_rng)
978 {
979 if ( !m_members.root )
980 return 0;
981
982 typedef std::is_convertible<ConvertibleOrRange, value_type> is_conv_t;
983 typedef range::detail::is_range<ConvertibleOrRange> is_range_t;
984 BOOST_GEOMETRY_STATIC_ASSERT((is_conv_t::value || is_range_t::value),
985 "The argument has to be convertible to Value type or be a Range.",
986 ConvertibleOrRange);
987
988 return this->remove_dispatch(conv_or_rng, is_conv_t());
989 }
990
991 /*!
992 \brief Finds values meeting passed predicates e.g. nearest to some Point and/or intersecting some Box.
993
994 This query function performs spatial and k-nearest neighbor searches. It allows to pass a set of predicates.
995 Values will be returned only if all predicates are met.
996
997 <b>Spatial predicates</b>
998
999 Spatial predicates may be generated by one of the functions listed below:
1000 \li \c boost::geometry::index::contains(),
1001 \li \c boost::geometry::index::covered_by(),
1002 \li \c boost::geometry::index::covers(),
1003 \li \c boost::geometry::index::disjoint(),
1004 \li \c boost::geometry::index::intersects(),
1005 \li \c boost::geometry::index::overlaps(),
1006 \li \c boost::geometry::index::within(),
1007
1008 It is possible to negate spatial predicates:
1009 \li <tt>! boost::geometry::index::contains()</tt>,
1010 \li <tt>! boost::geometry::index::covered_by()</tt>,
1011 \li <tt>! boost::geometry::index::covers()</tt>,
1012 \li <tt>! boost::geometry::index::disjoint()</tt>,
1013 \li <tt>! boost::geometry::index::intersects()</tt>,
1014 \li <tt>! boost::geometry::index::overlaps()</tt>,
1015 \li <tt>! boost::geometry::index::within()</tt>
1016
1017 <b>Satisfies predicate</b>
1018
1019 This is a special kind of predicate which allows to pass a user-defined function or function object which checks
1020 if Value should be returned by the query. It's generated by:
1021 \li \c boost::geometry::index::satisfies().
1022
1023 <b>Nearest predicate</b>
1024
1025 If the nearest predicate is passed a k-nearest neighbor search will be performed. This query will result
1026 in returning k values to the output iterator. Only one nearest predicate may be passed to the query.
1027 It may be generated by:
1028 \li \c boost::geometry::index::nearest().
1029
1030 <b>Connecting predicates</b>
1031
1032 Predicates may be passed together connected with \c operator&&().
1033
1034 \par Example
1035 \verbatim
1036 // return elements intersecting box
1037 tree.query(bgi::intersects(box), std::back_inserter(result));
1038 // return elements intersecting poly but not within box
1039 tree.query(bgi::intersects(poly) && !bgi::within(box), std::back_inserter(result));
1040 // return elements overlapping box and meeting my_fun unary predicate
1041 tree.query(bgi::overlaps(box) && bgi::satisfies(my_fun), std::back_inserter(result));
1042 // return 5 elements nearest to pt and elements are intersecting box
1043 tree.query(bgi::nearest(pt, 5) && bgi::intersects(box), std::back_inserter(result));
1044
1045 // For each found value do_something (it is a type of function object)
1046 tree.query(bgi::intersects(box),
1047 boost::make_function_output_iterator(do_something()));
1048
1049 // For each value stored in the rtree do_something
1050 // always_true is a type of function object always returning true
1051 tree.query(bgi::satisfies(always_true()),
1052 boost::make_function_output_iterator(do_something()));
1053
1054 // C++11 (lambda expression)
1055 tree.query(bgi::intersects(box),
1056 boost::make_function_output_iterator([](value_type const& val){
1057 // do something
1058 }));
1059
1060 // C++14 (generic lambda expression)
1061 tree.query(bgi::intersects(box),
1062 boost::make_function_output_iterator([](auto const& val){
1063 // do something
1064 }));
1065 \endverbatim
1066
1067 \par Throws
1068 If Value copy constructor or copy assignment throws.
1069 If predicates copy throws.
1070
1071 \warning
1072 Only one \c nearest() predicate may be passed to the query. Passing more of them results in compile-time error.
1073
1074 \param predicates Predicates.
1075 \param out_it The output iterator, e.g. generated by std::back_inserter().
1076
1077 \return The number of values found.
1078 */
1079 template <typename Predicates, typename OutIter>
query(Predicates const & predicates,OutIter out_it) const1080 size_type query(Predicates const& predicates, OutIter out_it) const
1081 {
1082 if ( !m_members.root )
1083 return 0;
1084
1085 static const unsigned distance_predicates_count = detail::predicates_count_distance<Predicates>::value;
1086 static const bool is_distance_predicate = 0 < distance_predicates_count;
1087 BOOST_GEOMETRY_STATIC_ASSERT((distance_predicates_count <= 1),
1088 "Only one distance predicate can be passed.",
1089 Predicates);
1090
1091 return query_dispatch(predicates, out_it,
1092 std::integral_constant<bool, is_distance_predicate>());
1093 }
1094
1095 /*!
1096 \brief Returns a query iterator pointing at the begin of the query range.
1097
1098 This method returns an iterator which may be used to perform iterative queries.
1099 For the information about predicates which may be passed to this method see query().
1100
1101 \par Example
1102 \verbatim
1103 for ( Rtree::const_query_iterator it = tree.qbegin(bgi::nearest(pt, 10000)) ;
1104 it != tree.qend() ; ++it )
1105 {
1106 // do something with value
1107 if ( has_enough_nearest_values() )
1108 break;
1109 }
1110
1111 // C++11 (auto)
1112 for ( auto it = tree.qbegin(bgi::nearest(pt, 3)) ; it != tree.qend() ; ++it )
1113 {
1114 // do something with value
1115 }
1116
1117 // C++14 (generic lambda expression)
1118 std::for_each(tree.qbegin(bgi::nearest(pt, 3)), tree.qend(), [](auto const& val){
1119 // do something with value
1120 });
1121 \endverbatim
1122
1123 \par Iterator category
1124 ForwardIterator
1125
1126 \par Throws
1127 If predicates copy throws.
1128 If allocation throws.
1129
1130 \warning
1131 The modification of the rtree may invalidate the iterators.
1132
1133 \param predicates Predicates.
1134
1135 \return The iterator pointing at the begin of the query range.
1136 */
1137 template <typename Predicates>
qbegin(Predicates const & predicates) const1138 const_query_iterator qbegin(Predicates const& predicates) const
1139 {
1140 return const_query_iterator(qbegin_(predicates));
1141 }
1142
1143 /*!
1144 \brief Returns a query iterator pointing at the end of the query range.
1145
1146 This method returns an iterator which may be used to check if the query has ended.
1147
1148 \par Example
1149 \verbatim
1150 for ( Rtree::const_query_iterator it = tree.qbegin(bgi::nearest(pt, 10000)) ;
1151 it != tree.qend() ; ++it )
1152 {
1153 // do something with value
1154 if ( has_enough_nearest_values() )
1155 break;
1156 }
1157
1158 // C++11 (auto)
1159 for ( auto it = tree.qbegin(bgi::nearest(pt, 3)) ; it != tree.qend() ; ++it )
1160 {
1161 // do something with value
1162 }
1163
1164 // C++14 (generic lambda expression)
1165 std::for_each(tree.qbegin(bgi::nearest(pt, 3)), tree.qend(), [](auto const& val){
1166 // do something with value
1167 });
1168 \endverbatim
1169
1170 \par Iterator category
1171 ForwardIterator
1172
1173 \par Throws
1174 Nothing
1175
1176 \warning
1177 The modification of the rtree may invalidate the iterators.
1178
1179 \return The iterator pointing at the end of the query range.
1180 */
qend() const1181 const_query_iterator qend() const
1182 {
1183 return const_query_iterator();
1184 }
1185
1186 #ifndef BOOST_GEOMETRY_INDEX_DETAIL_EXPERIMENTAL
1187 private:
1188 #endif
1189 /*!
1190 \brief Returns a query iterator pointing at the begin of the query range.
1191
1192 This method returns an iterator which may be used to perform iterative queries.
1193 For the information about predicates which may be passed to this method see query().
1194
1195 The type of the returned iterator depends on the type of passed Predicates but the iterator of this type
1196 may be assigned to the variable of const_query_iterator type. If you'd like to use the type of the iterator
1197 returned by this method you may get the type e.g. by using C++11 decltype or Boost.Typeof library.
1198 This iterator may be compared with iterators returned by both versions of qend() method.
1199
1200 \par Example
1201 \verbatim
1202 // Store the result in the container using std::copy() - it requires both iterators of the same type
1203 std::copy(tree.qbegin_(bgi::intersects(box)), tree.qend_(bgi::intersects(box)), std::back_inserter(result));
1204
1205 // Store the result in the container using std::copy() and type-erased iterators
1206 Rtree::const_query_iterator first = tree.qbegin_(bgi::intersects(box));
1207 Rtree::const_query_iterator last = tree.qend_();
1208 std::copy(first, last, std::back_inserter(result));
1209
1210 // Boost.Typeof
1211 typedef BOOST_TYPEOF(tree.qbegin(bgi::nearest(pt, 10000))) Iter;
1212 for ( Iter it = tree.qbegin_(bgi::nearest(pt, 10000)) ; it != tree.qend_() ; ++it )
1213 {
1214 // do something with value
1215 if ( has_enough_nearest_values() )
1216 break;
1217 }
1218
1219 // C++11 (auto)
1220 for ( auto it = tree.qbegin_(bgi::nearest(pt, 10000)) ; it != tree.qend_() ; ++it )
1221 {
1222 // do something with value
1223 if ( has_enough_nearest_values() )
1224 break;
1225 }
1226 \endverbatim
1227
1228 \par Iterator category
1229 ForwardIterator
1230
1231 \par Throws
1232 If predicates copy throws.
1233 If allocation throws.
1234
1235 \warning
1236 The modification of the rtree may invalidate the iterators.
1237
1238 \param predicates Predicates.
1239
1240 \return The iterator pointing at the begin of the query range.
1241 */
1242 template <typename Predicates>
1243 std::conditional_t
1244 <
1245 detail::predicates_count_distance<Predicates>::value == 0,
1246 detail::rtree::iterators::spatial_query_iterator<members_holder, Predicates>,
1247 detail::rtree::iterators::distance_query_iterator
1248 <
1249 members_holder, Predicates,
1250 detail::predicates_find_distance<Predicates>::value
1251 >
1252 >
qbegin_(Predicates const & predicates) const1253 qbegin_(Predicates const& predicates) const
1254 {
1255 static const unsigned distance_predicates_count = detail::predicates_count_distance<Predicates>::value;
1256 BOOST_GEOMETRY_STATIC_ASSERT((distance_predicates_count <= 1),
1257 "Only one distance predicate can be passed.",
1258 Predicates);
1259
1260 typedef std::conditional_t
1261 <
1262 detail::predicates_count_distance<Predicates>::value == 0,
1263 detail::rtree::iterators::spatial_query_iterator<members_holder, Predicates>,
1264 detail::rtree::iterators::distance_query_iterator
1265 <
1266 members_holder, Predicates,
1267 detail::predicates_find_distance<Predicates>::value
1268 >
1269 > iterator_type;
1270
1271 if ( !m_members.root )
1272 return iterator_type(m_members.parameters(), m_members.translator(), predicates);
1273
1274 return iterator_type(m_members.root, m_members.parameters(), m_members.translator(), predicates);
1275 }
1276
1277 /*!
1278 \brief Returns the query iterator pointing at the end of the query range.
1279
1280 This method returns the iterator which may be used to perform iterative queries. For the information
1281 about the predicates which may be passed to this method see query().
1282
1283 The type of the returned iterator depends on the type of passed Predicates but the iterator of this type
1284 may be assigned to the variable of const_query_iterator type. If you'd like to use the type of the iterator
1285 returned by this method you may get the type e.g. by using C++11 decltype or Boost.Typeof library.
1286
1287 The type of the iterator returned by this method is the same as the one returned by qbegin() to which
1288 the same predicates were passed.
1289
1290 \par Example
1291 \verbatim
1292 // Store the result in the container using std::copy() - it requires both iterators of the same type
1293 std::copy(tree.qbegin_(bgi::intersects(box)), tree.qend_(bgi::intersects(box)), std::back_inserter(result));
1294 \endverbatim
1295
1296 \par Iterator category
1297 ForwardIterator
1298
1299 \par Throws
1300 If predicates copy throws.
1301
1302 \warning
1303 The modification of the rtree may invalidate the iterators.
1304
1305 \param predicates Predicates.
1306
1307 \return The iterator pointing at the end of the query range.
1308 */
1309 template <typename Predicates>
1310 std::conditional_t
1311 <
1312 detail::predicates_count_distance<Predicates>::value == 0,
1313 detail::rtree::iterators::spatial_query_iterator<members_holder, Predicates>,
1314 detail::rtree::iterators::distance_query_iterator
1315 <
1316 members_holder, Predicates,
1317 detail::predicates_find_distance<Predicates>::value
1318 >
1319 >
qend_(Predicates const & predicates) const1320 qend_(Predicates const& predicates) const
1321 {
1322 static const unsigned distance_predicates_count = detail::predicates_count_distance<Predicates>::value;
1323 BOOST_GEOMETRY_STATIC_ASSERT((distance_predicates_count <= 1),
1324 "Only one distance predicate can be passed.",
1325 Predicates);
1326
1327 typedef std::conditional_t
1328 <
1329 detail::predicates_count_distance<Predicates>::value == 0,
1330 detail::rtree::iterators::spatial_query_iterator<members_holder, Predicates>,
1331 detail::rtree::iterators::distance_query_iterator
1332 <
1333 members_holder, Predicates,
1334 detail::predicates_find_distance<Predicates>::value
1335 >
1336 > iterator_type;
1337
1338 return iterator_type(m_members.parameters(), m_members.translator(), predicates);
1339 }
1340
1341 /*!
1342 \brief Returns the query iterator pointing at the end of the query range.
1343
1344 This method returns the iterator which may be compared with the iterator returned by qbegin() in order to
1345 check if the query has ended.
1346
1347 The type of the returned iterator is different than the type returned by qbegin() but the iterator of this type
1348 may be assigned to the variable of const_query_iterator type. If you'd like to use the type of the iterator returned by this
1349 method, which most certainly will be faster than the type-erased iterator, you may get the type
1350 e.g. by using C++11 decltype or Boost.Typeof library.
1351
1352 The type of the iterator returned by this method is different than the type returned by qbegin().
1353
1354 \par Example
1355 \verbatim
1356 // Store the result in the container using std::copy() and type-erased iterators
1357 Rtree::const_query_iterator first = tree.qbegin_(bgi::intersects(box));
1358 Rtree::const_query_iterator last = tree.qend_();
1359 std::copy(first, last, std::back_inserter(result));
1360
1361 // Boost.Typeof
1362 typedef BOOST_TYPEOF(tree.qbegin(bgi::nearest(pt, 10000))) Iter;
1363 for ( Iter it = tree.qbegin_(bgi::nearest(pt, 10000)) ; it != tree.qend_() ; ++it )
1364 {
1365 // do something with value
1366 if ( has_enough_nearest_values() )
1367 break;
1368 }
1369
1370 // C++11 (auto)
1371 for ( auto it = tree.qbegin_(bgi::nearest(pt, 10000)) ; it != tree.qend_() ; ++it )
1372 {
1373 // do something with value
1374 if ( has_enough_nearest_values() )
1375 break;
1376 }
1377 \endverbatim
1378
1379 \par Iterator category
1380 ForwardIterator
1381
1382 \par Throws
1383 Nothing
1384
1385 \warning
1386 The modification of the rtree may invalidate the iterators.
1387
1388 \return The iterator pointing at the end of the query range.
1389 */
1390 detail::rtree::iterators::end_query_iterator<value_type, allocators_type>
qend_() const1391 qend_() const
1392 {
1393 return detail::rtree::iterators::end_query_iterator<value_type, allocators_type>();
1394 }
1395
1396 public:
1397
1398 /*!
1399 \brief Returns the iterator pointing at the begin of the rtree values range.
1400
1401 This method returns the iterator which may be used to iterate over all values
1402 stored in the rtree.
1403
1404 \par Example
1405 \verbatim
1406 // Copy all values into the vector
1407 std::copy(tree.begin(), tree.end(), std::back_inserter(vec));
1408
1409 for ( Rtree::const_iterator it = tree.begin() ; it != tree.end() ; ++it )
1410 {
1411 // do something with value
1412 }
1413
1414 // C++11 (auto)
1415 for ( auto it = tree.begin() ; it != tree.end() ; ++it )
1416 {
1417 // do something with value
1418 }
1419
1420 // C++14 (generic lambda expression)
1421 std::for_each(tree.begin(), tree.end(), [](auto const& val){
1422 // do something with value
1423 })
1424 \endverbatim
1425
1426 \par Iterator category
1427 ForwardIterator
1428
1429 \par Throws
1430 If allocation throws.
1431
1432 \warning
1433 The modification of the rtree may invalidate the iterators.
1434
1435 \return The iterator pointing at the begin of the range.
1436 */
begin() const1437 const_iterator begin() const
1438 {
1439 if ( !m_members.root )
1440 return const_iterator();
1441
1442 return const_iterator(m_members.root);
1443 }
1444
1445 /*!
1446 \brief Returns the iterator pointing at the end of the rtree values range.
1447
1448 This method returns the iterator which may be compared with the iterator returned by begin()
1449 in order to check if the iteration has ended.
1450
1451 \par Example
1452 \verbatim
1453 for ( Rtree::const_iterator it = tree.begin() ; it != tree.end() ; ++it )
1454 {
1455 // do something with value
1456 }
1457
1458 // C++11 (lambda expression)
1459 std::for_each(tree.begin(), tree.end(), [](value_type const& val){
1460 // do something with value
1461 })
1462 \endverbatim
1463
1464 \par Iterator category
1465 ForwardIterator
1466
1467 \par Throws
1468 Nothing.
1469
1470 \warning
1471 The modification of the rtree may invalidate the iterators.
1472
1473 \return The iterator pointing at the end of the range.
1474 */
end() const1475 const_iterator end() const
1476 {
1477 return const_iterator();
1478 }
1479
1480 /*!
1481 \brief Returns the number of stored values.
1482
1483 \return The number of stored values.
1484
1485 \par Throws
1486 Nothing.
1487 */
size() const1488 inline size_type size() const
1489 {
1490 return m_members.values_count;
1491 }
1492
1493 /*!
1494 \brief Query if the container is empty.
1495
1496 \return true if the container is empty.
1497
1498 \par Throws
1499 Nothing.
1500 */
empty() const1501 inline bool empty() const
1502 {
1503 return 0 == m_members.values_count;
1504 }
1505
1506 /*!
1507 \brief Removes all values stored in the container.
1508
1509 \par Throws
1510 Nothing.
1511 */
clear()1512 inline void clear()
1513 {
1514 this->raw_destroy(*this);
1515 }
1516
1517 /*!
1518 \brief Returns the box able to contain all values stored in the container.
1519
1520 Returns the box able to contain all values stored in the container.
1521 If the container is empty the result of \c geometry::assign_inverse() is returned.
1522
1523 \return The box able to contain all values stored in the container or an invalid box if
1524 there are no values in the container.
1525
1526 \par Throws
1527 Nothing.
1528 */
bounds() const1529 inline bounds_type bounds() const
1530 {
1531 bounds_type result;
1532 // in order to suppress the uninitialized variable warnings
1533 geometry::assign_inverse(result);
1534
1535 if ( m_members.root )
1536 {
1537 detail::rtree::visitors::children_box
1538 <
1539 members_holder
1540 > box_v(result, m_members.parameters(), m_members.translator());
1541 detail::rtree::apply_visitor(box_v, *m_members.root);
1542 }
1543
1544 return result;
1545 }
1546
1547 /*!
1548 \brief Count Values or Indexables stored in the container.
1549
1550 For indexable_type it returns the number of values which indexables equals the parameter.
1551 For value_type it returns the number of values which equals the parameter.
1552
1553 \param vori The value or indexable which will be counted.
1554
1555 \return The number of values found.
1556
1557 \par Throws
1558 Nothing.
1559 */
1560 template <typename ValueOrIndexable>
count(ValueOrIndexable const & vori) const1561 size_type count(ValueOrIndexable const& vori) const
1562 {
1563 if ( !m_members.root )
1564 return 0;
1565
1566 // the input should be convertible to Value or Indexable type
1567 typedef typename index::detail::convertible_type
1568 <
1569 ValueOrIndexable,
1570 value_type,
1571 indexable_type
1572 >::type value_or_indexable;
1573
1574 static const bool is_void = std::is_void<value_or_indexable>::value;
1575 BOOST_GEOMETRY_STATIC_ASSERT((! is_void),
1576 "The argument has to be convertible to Value or Indexable type.",
1577 ValueOrIndexable);
1578
1579 // NOTE: If an object of convertible but not the same type is passed
1580 // into the function, here a temporary will be created.
1581 return this->template raw_count<value_or_indexable>(vori);
1582 }
1583
1584 /*!
1585 \brief Returns parameters.
1586
1587 \return The parameters object.
1588
1589 \par Throws
1590 Nothing.
1591 */
parameters() const1592 inline parameters_type parameters() const
1593 {
1594 return m_members.parameters();
1595 }
1596
1597 /*!
1598 \brief Returns function retrieving Indexable from Value.
1599
1600 \return The indexable_getter object.
1601
1602 \par Throws
1603 Nothing.
1604 */
indexable_get() const1605 indexable_getter indexable_get() const
1606 {
1607 return m_members.indexable_getter();
1608 }
1609
1610 /*!
1611 \brief Returns function comparing Values
1612
1613 \return The value_equal function.
1614
1615 \par Throws
1616 Nothing.
1617 */
value_eq() const1618 value_equal value_eq() const
1619 {
1620 return m_members.equal_to();
1621 }
1622
1623 /*!
1624 \brief Returns allocator used by the rtree.
1625
1626 \return The allocator.
1627
1628 \par Throws
1629 If allocator copy constructor throws.
1630 */
get_allocator() const1631 allocator_type get_allocator() const
1632 {
1633 return m_members.allocators().allocator();
1634 }
1635
1636 private:
1637
1638 /*!
1639 \brief Returns the translator object.
1640
1641 \return The translator object.
1642
1643 \par Throws
1644 Nothing.
1645 */
translator() const1646 inline translator_type translator() const
1647 {
1648 return m_members.translator();
1649 }
1650
1651 /*!
1652 \brief Apply a visitor to the nodes structure in order to perform some operator.
1653
1654 This function is not a part of the 'official' interface. However it makes
1655 possible e.g. to pass a visitor drawing the tree structure.
1656
1657 \param visitor The visitor object.
1658
1659 \par Throws
1660 If Visitor::operator() throws.
1661 */
1662 template <typename Visitor>
apply_visitor(Visitor & visitor) const1663 inline void apply_visitor(Visitor & visitor) const
1664 {
1665 if ( m_members.root )
1666 detail::rtree::apply_visitor(visitor, *m_members.root);
1667 }
1668
1669 /*!
1670 \brief Returns the depth of the R-tree.
1671
1672 This function is not a part of the 'official' interface.
1673
1674 \return The depth of the R-tree.
1675
1676 \par Throws
1677 Nothing.
1678 */
depth() const1679 inline size_type depth() const
1680 {
1681 return m_members.leafs_level;
1682 }
1683
1684 private:
1685
1686 /*!
1687 \pre Root node must exist - m_root != 0.
1688
1689 \brief Insert a value to the index.
1690
1691 \param value The value which will be stored in the container.
1692
1693 \par Exception-safety
1694 basic
1695 */
raw_insert(value_type const & value)1696 inline void raw_insert(value_type const& value)
1697 {
1698 BOOST_GEOMETRY_INDEX_ASSERT(m_members.root, "The root must exist");
1699 // CONSIDER: alternative - ignore invalid indexable or throw an exception
1700 BOOST_GEOMETRY_INDEX_ASSERT(detail::is_valid(m_members.translator()(value)), "Indexable is invalid");
1701
1702 detail::rtree::visitors::insert<value_type, members_holder>
1703 insert_v(m_members.root, m_members.leafs_level, value,
1704 m_members.parameters(), m_members.translator(), m_members.allocators());
1705
1706 detail::rtree::apply_visitor(insert_v, *m_members.root);
1707
1708 // TODO
1709 // Think about this: If exception is thrown, may the root be removed?
1710 // Or it is just cleared?
1711
1712 // TODO
1713 // If exception is thrown, m_values_count may be invalid
1714 ++m_members.values_count;
1715 }
1716
1717 /*!
1718 \brief Remove the value from the container.
1719
1720 \param value The value which will be removed from the container.
1721
1722 \par Exception-safety
1723 basic
1724 */
raw_remove(value_type const & value)1725 inline size_type raw_remove(value_type const& value)
1726 {
1727 // TODO: awulkiew - assert for correct value (indexable) ?
1728 BOOST_GEOMETRY_INDEX_ASSERT(m_members.root, "The root must exist");
1729
1730 detail::rtree::visitors::remove<members_holder>
1731 remove_v(m_members.root, m_members.leafs_level, value,
1732 m_members.parameters(), m_members.translator(), m_members.allocators());
1733
1734 detail::rtree::apply_visitor(remove_v, *m_members.root);
1735
1736 // If exception is thrown, m_values_count may be invalid
1737
1738 if ( remove_v.is_value_removed() )
1739 {
1740 BOOST_GEOMETRY_INDEX_ASSERT(0 < m_members.values_count, "unexpected state");
1741
1742 --m_members.values_count;
1743
1744 return 1;
1745 }
1746
1747 return 0;
1748 }
1749
1750 /*!
1751 \brief Create an empty R-tree i.e. new empty root node and clear other attributes.
1752
1753 \par Exception-safety
1754 strong
1755 */
raw_create()1756 inline void raw_create()
1757 {
1758 BOOST_GEOMETRY_INDEX_ASSERT(0 == m_members.root, "the tree is already created");
1759
1760 m_members.root = detail::rtree::create_node<allocators_type, leaf>::apply(m_members.allocators()); // MAY THROW (N: alloc)
1761 m_members.values_count = 0;
1762 m_members.leafs_level = 0;
1763 }
1764
1765 /*!
1766 \brief Destroy the R-tree i.e. all nodes and clear attributes.
1767
1768 \param t The container which is going to be destroyed.
1769
1770 \par Exception-safety
1771 nothrow
1772 */
raw_destroy(rtree & t)1773 inline void raw_destroy(rtree & t)
1774 {
1775 if ( t.m_members.root )
1776 {
1777 detail::rtree::visitors::destroy<members_holder>
1778 ::apply(t.m_members.root, t.m_members.allocators());
1779
1780 t.m_members.root = 0;
1781 }
1782 t.m_members.values_count = 0;
1783 t.m_members.leafs_level = 0;
1784 }
1785
1786 /*!
1787 \brief Copy the R-tree i.e. whole nodes structure, values and other attributes.
1788 It uses destination's allocators to create the new structure.
1789
1790 \param src The source R-tree.
1791 \param dst The destination R-tree.
1792 \param copy_tr_and_params If true, translator and parameters will also be copied.
1793
1794 \par Exception-safety
1795 strong
1796 */
raw_copy(rtree const & src,rtree & dst,bool copy_tr_and_params) const1797 inline void raw_copy(rtree const& src, rtree & dst, bool copy_tr_and_params) const
1798 {
1799 detail::rtree::visitors::copy<members_holder> copy_v(dst.m_members.allocators());
1800
1801 if ( src.m_members.root )
1802 detail::rtree::apply_visitor(copy_v, *src.m_members.root); // MAY THROW (V, E: alloc, copy, N: alloc)
1803
1804 if ( copy_tr_and_params )
1805 {
1806 dst.m_members.indexable_getter() = src.m_members.indexable_getter();
1807 dst.m_members.equal_to() = src.m_members.equal_to();
1808 dst.m_members.parameters() = src.m_members.parameters();
1809 }
1810
1811 // TODO use subtree_destroyer
1812 if ( dst.m_members.root )
1813 {
1814 detail::rtree::visitors::destroy<members_holder>
1815 ::apply(dst.m_members.root, dst.m_members.allocators());
1816
1817 dst.m_members.root = 0;
1818 }
1819
1820 dst.m_members.root = copy_v.result;
1821 dst.m_members.values_count = src.m_members.values_count;
1822 dst.m_members.leafs_level = src.m_members.leafs_level;
1823 }
1824
1825 /*!
1826 \brief Insert a value corresponding to convertible object into the index.
1827
1828 \param val_conv The object convertible to value.
1829
1830 \par Exception-safety
1831 basic
1832 */
1833 template <typename ValueConvertible>
insert_dispatch(ValueConvertible const & val_conv,std::true_type)1834 inline void insert_dispatch(ValueConvertible const& val_conv,
1835 std::true_type /*is_convertible*/)
1836 {
1837 this->raw_insert(val_conv);
1838 }
1839
1840 /*!
1841 \brief Insert a range of values into the index.
1842
1843 \param rng The range of values.
1844
1845 \par Exception-safety
1846 basic
1847 */
1848 template <typename Range>
insert_dispatch(Range const & rng,std::false_type)1849 inline void insert_dispatch(Range const& rng,
1850 std::false_type /*is_convertible*/)
1851 {
1852 typedef typename boost::range_const_iterator<Range>::type It;
1853 for ( It it = boost::const_begin(rng); it != boost::const_end(rng) ; ++it )
1854 this->raw_insert(*it);
1855 }
1856
1857 /*!
1858 \brief Remove a value corresponding to convertible object from the index.
1859
1860 \param val_conv The object convertible to value.
1861
1862 \par Exception-safety
1863 basic
1864 */
1865 template <typename ValueConvertible>
remove_dispatch(ValueConvertible const & val_conv,std::true_type)1866 inline size_type remove_dispatch(ValueConvertible const& val_conv,
1867 std::true_type /*is_convertible*/)
1868 {
1869 return this->raw_remove(val_conv);
1870 }
1871
1872 /*!
1873 \brief Remove a range of values from the index.
1874
1875 \param rng The range of values which will be removed from the container.
1876
1877 \par Exception-safety
1878 basic
1879 */
1880 template <typename Range>
remove_dispatch(Range const & rng,std::false_type)1881 inline size_type remove_dispatch(Range const& rng,
1882 std::false_type /*is_convertible*/)
1883 {
1884 size_type result = 0;
1885 typedef typename boost::range_const_iterator<Range>::type It;
1886 for ( It it = boost::const_begin(rng); it != boost::const_end(rng) ; ++it )
1887 result += this->raw_remove(*it);
1888 return result;
1889 }
1890
1891 /*!
1892 \brief Return values meeting predicates.
1893
1894 \par Exception-safety
1895 strong
1896 */
1897 template <typename Predicates, typename OutIter>
query_dispatch(Predicates const & predicates,OutIter out_it,std::false_type) const1898 size_type query_dispatch(Predicates const& predicates, OutIter out_it, std::false_type /*is_distance_predicate*/) const
1899 {
1900 detail::rtree::visitors::spatial_query<members_holder, Predicates, OutIter>
1901 find_v(m_members.parameters(), m_members.translator(), predicates, out_it);
1902
1903 detail::rtree::apply_visitor(find_v, *m_members.root);
1904
1905 return find_v.found_count;
1906 }
1907
1908 /*!
1909 \brief Perform nearest neighbour search.
1910
1911 \par Exception-safety
1912 strong
1913 */
1914 template <typename Predicates, typename OutIter>
query_dispatch(Predicates const & predicates,OutIter out_it,std::true_type) const1915 size_type query_dispatch(Predicates const& predicates, OutIter out_it, std::true_type /*is_distance_predicate*/) const
1916 {
1917 BOOST_GEOMETRY_INDEX_ASSERT(m_members.root, "The root must exist");
1918
1919 static const unsigned distance_predicate_index = detail::predicates_find_distance<Predicates>::value;
1920 detail::rtree::visitors::distance_query<
1921 members_holder,
1922 Predicates,
1923 distance_predicate_index,
1924 OutIter
1925 > distance_v(m_members.parameters(), m_members.translator(), predicates, out_it);
1926
1927 detail::rtree::apply_visitor(distance_v, *m_members.root);
1928
1929 return distance_v.finish();
1930 }
1931
1932 /*!
1933 \brief Count elements corresponding to value or indexable.
1934
1935 \par Exception-safety
1936 strong
1937 */
1938 template <typename ValueOrIndexable>
raw_count(ValueOrIndexable const & vori) const1939 size_type raw_count(ValueOrIndexable const& vori) const
1940 {
1941 BOOST_GEOMETRY_INDEX_ASSERT(m_members.root, "The root must exist");
1942
1943 detail::rtree::visitors::count
1944 <
1945 ValueOrIndexable,
1946 members_holder
1947 > count_v(vori, m_members.parameters(), m_members.translator());
1948
1949 detail::rtree::apply_visitor(count_v, *m_members.root);
1950
1951 return count_v.found_count;
1952 }
1953
1954 /*!
1955 \brief The constructor TODO.
1956
1957 The tree is created using packing algorithm.
1958
1959 \param first The beginning of the range of Values.
1960 \param last The end of the range of Values.
1961 \param temp_allocator The temporary allocator object to be used by the packing algorithm.
1962
1963 \par Throws
1964 \li If allocator copy constructor throws.
1965 \li If Value copy constructor or copy assignment throws.
1966 \li If allocation throws or returns invalid value.
1967 */
1968 template<typename Iterator, typename PackAlloc>
pack_construct(Iterator first,Iterator last,PackAlloc const & temp_allocator)1969 inline void pack_construct(Iterator first, Iterator last, PackAlloc const& temp_allocator)
1970 {
1971 typedef detail::rtree::pack<members_holder> pack;
1972 size_type vc = 0, ll = 0;
1973 m_members.root = pack::apply(first, last, vc, ll,
1974 m_members.parameters(), m_members.translator(),
1975 m_members.allocators(), temp_allocator);
1976 m_members.values_count = vc;
1977 m_members.leafs_level = ll;
1978 }
1979
1980 members_holder m_members;
1981 };
1982
1983 /*!
1984 \brief Insert a value to the index.
1985
1986 It calls <tt>rtree::insert(value_type const&)</tt>.
1987
1988 \ingroup rtree_functions
1989
1990 \param tree The spatial index.
1991 \param v The value which will be stored in the index.
1992 */
1993 template <typename Value, typename Parameters, typename IndexableGetter, typename EqualTo, typename Allocator>
insert(rtree<Value,Parameters,IndexableGetter,EqualTo,Allocator> & tree,Value const & v)1994 inline void insert(rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator> & tree,
1995 Value const& v)
1996 {
1997 tree.insert(v);
1998 }
1999
2000 /*!
2001 \brief Insert a range of values to the index.
2002
2003 It calls <tt>rtree::insert(Iterator, Iterator)</tt>.
2004
2005 \ingroup rtree_functions
2006
2007 \param tree The spatial index.
2008 \param first The beginning of the range of values.
2009 \param last The end of the range of values.
2010 */
2011 template<typename Value, typename Parameters, typename IndexableGetter, typename EqualTo, typename Allocator,
2012 typename Iterator>
insert(rtree<Value,Parameters,IndexableGetter,EqualTo,Allocator> & tree,Iterator first,Iterator last)2013 inline void insert(rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator> & tree,
2014 Iterator first, Iterator last)
2015 {
2016 tree.insert(first, last);
2017 }
2018
2019 /*!
2020 \brief Insert a value created using convertible object or a range of values to the index.
2021
2022 It calls <tt>rtree::insert(ConvertibleOrRange const&)</tt>.
2023
2024 \ingroup rtree_functions
2025
2026 \param tree The spatial index.
2027 \param conv_or_rng The object of type convertible to value_type or a range of values.
2028 */
2029 template<typename Value, typename Parameters, typename IndexableGetter, typename EqualTo, typename Allocator,
2030 typename ConvertibleOrRange>
insert(rtree<Value,Parameters,IndexableGetter,EqualTo,Allocator> & tree,ConvertibleOrRange const & conv_or_rng)2031 inline void insert(rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator> & tree,
2032 ConvertibleOrRange const& conv_or_rng)
2033 {
2034 tree.insert(conv_or_rng);
2035 }
2036
2037 /*!
2038 \brief Remove a value from the container.
2039
2040 Remove a value from the container. In contrast to the \c std::set or <tt>std::map erase()</tt> method
2041 this function removes only one value from the container.
2042
2043 It calls <tt>rtree::remove(value_type const&)</tt>.
2044
2045 \ingroup rtree_functions
2046
2047 \param tree The spatial index.
2048 \param v The value which will be removed from the index.
2049
2050 \return 1 if value was removed, 0 otherwise.
2051 */
2052 template <typename Value, typename Parameters, typename IndexableGetter, typename EqualTo, typename Allocator>
2053 inline typename rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator>::size_type
remove(rtree<Value,Parameters,IndexableGetter,EqualTo,Allocator> & tree,Value const & v)2054 remove(rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator> & tree,
2055 Value const& v)
2056 {
2057 return tree.remove(v);
2058 }
2059
2060 /*!
2061 \brief Remove a range of values from the container.
2062
2063 Remove a range of values from the container. In contrast to the \c std::set or <tt>std::map erase()</tt> method
2064 it doesn't take iterators pointing to values stored in this container. It removes values equal
2065 to these passed as a range. Furthermore this function removes only one value for each one passed
2066 in the range, not all equal values.
2067
2068 It calls <tt>rtree::remove(Iterator, Iterator)</tt>.
2069
2070 \ingroup rtree_functions
2071
2072 \param tree The spatial index.
2073 \param first The beginning of the range of values.
2074 \param last The end of the range of values.
2075
2076 \return The number of removed values.
2077 */
2078 template<typename Value, typename Parameters, typename IndexableGetter, typename EqualTo, typename Allocator,
2079 typename Iterator>
2080 inline typename rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator>::size_type
remove(rtree<Value,Parameters,IndexableGetter,EqualTo,Allocator> & tree,Iterator first,Iterator last)2081 remove(rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator> & tree,
2082 Iterator first, Iterator last)
2083 {
2084 return tree.remove(first, last);
2085 }
2086
2087 /*!
2088 \brief Remove a value corresponding to an object convertible to it or a range of values from the container.
2089
2090 Remove a value corresponding to an object convertible to it or a range of values from the container.
2091 In contrast to the \c std::set or <tt>std::map erase()</tt> method
2092 it removes values equal to these passed as a range. Furthermore this method removes only
2093 one value for each one passed in the range, not all equal values.
2094
2095 It calls <tt>rtree::remove(ConvertibleOrRange const&)</tt>.
2096
2097 \ingroup rtree_functions
2098
2099 \param tree The spatial index.
2100 \param conv_or_rng The object of type convertible to value_type or the range of values.
2101
2102 \return The number of removed values.
2103 */
2104 template<typename Value, typename Parameters, typename IndexableGetter, typename EqualTo, typename Allocator,
2105 typename ConvertibleOrRange>
2106 inline typename rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator>::size_type
remove(rtree<Value,Parameters,IndexableGetter,EqualTo,Allocator> & tree,ConvertibleOrRange const & conv_or_rng)2107 remove(rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator> & tree,
2108 ConvertibleOrRange const& conv_or_rng)
2109 {
2110 return tree.remove(conv_or_rng);
2111 }
2112
2113 /*!
2114 \brief Finds values meeting passed predicates e.g. nearest to some Point and/or intersecting some Box.
2115
2116 This query function performs spatial and k-nearest neighbor searches. It allows to pass a set of predicates.
2117 Values will be returned only if all predicates are met.
2118
2119 <b>Spatial predicates</b>
2120
2121 Spatial predicates may be generated by one of the functions listed below:
2122 \li \c boost::geometry::index::contains(),
2123 \li \c boost::geometry::index::covered_by(),
2124 \li \c boost::geometry::index::covers(),
2125 \li \c boost::geometry::index::disjoint(),
2126 \li \c boost::geometry::index::intersects(),
2127 \li \c boost::geometry::index::overlaps(),
2128 \li \c boost::geometry::index::within(),
2129
2130 It is possible to negate spatial predicates:
2131 \li <tt>! boost::geometry::index::contains()</tt>,
2132 \li <tt>! boost::geometry::index::covered_by()</tt>,
2133 \li <tt>! boost::geometry::index::covers()</tt>,
2134 \li <tt>! boost::geometry::index::disjoint()</tt>,
2135 \li <tt>! boost::geometry::index::intersects()</tt>,
2136 \li <tt>! boost::geometry::index::overlaps()</tt>,
2137 \li <tt>! boost::geometry::index::within()</tt>
2138
2139 <b>Satisfies predicate</b>
2140
2141 This is a special kind of predicate which allows to pass a user-defined function or function object which checks
2142 if Value should be returned by the query. It's generated by:
2143 \li \c boost::geometry::index::satisfies().
2144
2145 <b>Nearest predicate</b>
2146
2147 If the nearest predicate is passed a k-nearest neighbor search will be performed. This query will result
2148 in returning k values to the output iterator. Only one nearest predicate may be passed to the query.
2149 It may be generated by:
2150 \li \c boost::geometry::index::nearest().
2151
2152 <b>Connecting predicates</b>
2153
2154 Predicates may be passed together connected with \c operator&&().
2155
2156 \par Example
2157 \verbatim
2158 // return elements intersecting box
2159 bgi::query(tree, bgi::intersects(box), std::back_inserter(result));
2160 // return elements intersecting poly but not within box
2161 bgi::query(tree, bgi::intersects(poly) && !bgi::within(box), std::back_inserter(result));
2162 // return elements overlapping box and meeting my_fun value predicate
2163 bgi::query(tree, bgi::overlaps(box) && bgi::satisfies(my_fun), std::back_inserter(result));
2164 // return 5 elements nearest to pt and elements are intersecting box
2165 bgi::query(tree, bgi::nearest(pt, 5) && bgi::intersects(box), std::back_inserter(result));
2166
2167 // For each found value do_something (it is a type of function object)
2168 tree.query(bgi::intersects(box),
2169 boost::make_function_output_iterator(do_something()));
2170 \endverbatim
2171
2172 \par Throws
2173 If Value copy constructor or copy assignment throws.
2174
2175 \warning
2176 Only one \c nearest() predicate may be passed to the query. Passing more of them results in compile-time error.
2177
2178 \ingroup rtree_functions
2179
2180 \param tree The rtree.
2181 \param predicates Predicates.
2182 \param out_it The output iterator, e.g. generated by std::back_inserter().
2183
2184 \return The number of values found.
2185 */
2186 template <typename Value, typename Parameters, typename IndexableGetter, typename EqualTo, typename Allocator,
2187 typename Predicates, typename OutIter> inline
2188 typename rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator>::size_type
query(rtree<Value,Parameters,IndexableGetter,EqualTo,Allocator> const & tree,Predicates const & predicates,OutIter out_it)2189 query(rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator> const& tree,
2190 Predicates const& predicates,
2191 OutIter out_it)
2192 {
2193 return tree.query(predicates, out_it);
2194 }
2195
2196 /*!
2197 \brief Returns the query iterator pointing at the begin of the query range.
2198
2199 This method returns the iterator which may be used to perform iterative queries. For the information
2200 about the predicates which may be passed to this method see query().
2201
2202 \par Example
2203 \verbatim
2204 std::for_each(bgi::qbegin(tree, bgi::nearest(pt, 3)), bgi::qend(tree), do_something());
2205 \endverbatim
2206
2207 \par Iterator category
2208 ForwardIterator
2209
2210 \par Throws
2211 If predicates copy throws.
2212 If allocation throws.
2213
2214 \warning
2215 The modification of the rtree may invalidate the iterators.
2216
2217 \ingroup rtree_functions
2218
2219 \param tree The rtree.
2220 \param predicates Predicates.
2221
2222 \return The iterator pointing at the begin of the query range.
2223 */
2224 template <typename Value, typename Parameters, typename IndexableGetter, typename EqualTo, typename Allocator,
2225 typename Predicates> inline
2226 typename rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator>::const_query_iterator
qbegin(rtree<Value,Parameters,IndexableGetter,EqualTo,Allocator> const & tree,Predicates const & predicates)2227 qbegin(rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator> const& tree,
2228 Predicates const& predicates)
2229 {
2230 return tree.qbegin(predicates);
2231 }
2232
2233 /*!
2234 \brief Returns the query iterator pointing at the end of the query range.
2235
2236 This method returns the iterator which may be used to check if the query has ended.
2237
2238 \par Example
2239 \verbatim
2240 std::for_each(bgi::qbegin(tree, bgi::nearest(pt, 3)), bgi::qend(tree), do_something());
2241 \endverbatim
2242
2243 \par Iterator category
2244 ForwardIterator
2245
2246 \par Throws
2247 Nothing
2248
2249 \warning
2250 The modification of the rtree may invalidate the iterators.
2251
2252 \ingroup rtree_functions
2253
2254 \return The iterator pointing at the end of the query range.
2255 */
2256 template <typename Value, typename Parameters, typename IndexableGetter, typename EqualTo, typename Allocator> inline
2257 typename rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator>::const_query_iterator
qend(rtree<Value,Parameters,IndexableGetter,EqualTo,Allocator> const & tree)2258 qend(rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator> const& tree)
2259 {
2260 return tree.qend();
2261 }
2262
2263 /*!
2264 \brief Returns the iterator pointing at the begin of the rtree values range.
2265
2266 This method returns the iterator which may be used to iterate over all values
2267 stored in the rtree.
2268
2269 \par Example
2270 \verbatim
2271 std::for_each(bgi::begin(tree), bgi::end(tree), do_something());
2272 // the same as
2273 std::for_each(boost::begin(tree), boost::end(tree), do_something());
2274 \endverbatim
2275
2276 \par Iterator category
2277 ForwardIterator
2278
2279 \par Throws
2280 If allocation throws.
2281
2282 \warning
2283 The modification of the rtree may invalidate the iterators.
2284
2285 \ingroup rtree_functions
2286
2287 \return The iterator pointing at the begin of the range.
2288 */
2289 template <typename Value, typename Parameters, typename IndexableGetter, typename EqualTo, typename Allocator> inline
2290 typename rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator>::const_iterator
begin(rtree<Value,Parameters,IndexableGetter,EqualTo,Allocator> const & tree)2291 begin(rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator> const& tree)
2292 {
2293 return tree.begin();
2294 }
2295
2296 /*!
2297 \brief Returns the iterator pointing at the end of the rtree values range.
2298
2299 This method returns the iterator which may be compared with the iterator returned by begin()
2300 in order to check if the iteration has ended.
2301
2302 \par Example
2303 \verbatim
2304 std::for_each(bgi::begin(tree), bgi::end(tree), do_something());
2305 // the same as
2306 std::for_each(boost::begin(tree), boost::end(tree), do_something());
2307 \endverbatim
2308
2309 \par Iterator category
2310 ForwardIterator
2311
2312 \par Throws
2313 Nothing.
2314
2315 \warning
2316 The modification of the rtree may invalidate the iterators.
2317
2318 \ingroup rtree_functions
2319
2320 \return The iterator pointing at the end of the range.
2321 */
2322 template <typename Value, typename Parameters, typename IndexableGetter, typename EqualTo, typename Allocator> inline
2323 typename rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator>::const_iterator
end(rtree<Value,Parameters,IndexableGetter,EqualTo,Allocator> const & tree)2324 end(rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator> const& tree)
2325 {
2326 return tree.end();
2327 }
2328
2329 /*!
2330 \brief Remove all values from the index.
2331
2332 It calls \c rtree::clear().
2333
2334 \ingroup rtree_functions
2335
2336 \param tree The spatial index.
2337 */
2338 template <typename Value, typename Parameters, typename IndexableGetter, typename EqualTo, typename Allocator>
clear(rtree<Value,Parameters,IndexableGetter,EqualTo,Allocator> & tree)2339 inline void clear(rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator> & tree)
2340 {
2341 return tree.clear();
2342 }
2343
2344 /*!
2345 \brief Get the number of values stored in the index.
2346
2347 It calls \c rtree::size().
2348
2349 \ingroup rtree_functions
2350
2351 \param tree The spatial index.
2352
2353 \return The number of values stored in the index.
2354 */
2355 template <typename Value, typename Parameters, typename IndexableGetter, typename EqualTo, typename Allocator>
size(rtree<Value,Parameters,IndexableGetter,EqualTo,Allocator> const & tree)2356 inline size_t size(rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator> const& tree)
2357 {
2358 return tree.size();
2359 }
2360
2361 /*!
2362 \brief Query if there are no values stored in the index.
2363
2364 It calls \c rtree::empty().
2365
2366 \ingroup rtree_functions
2367
2368 \param tree The spatial index.
2369
2370 \return true if there are no values in the index.
2371 */
2372 template <typename Value, typename Parameters, typename IndexableGetter, typename EqualTo, typename Allocator>
empty(rtree<Value,Parameters,IndexableGetter,EqualTo,Allocator> const & tree)2373 inline bool empty(rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator> const& tree)
2374 {
2375 return tree.bounds();
2376 }
2377
2378 /*!
2379 \brief Get the box containing all stored values or an invalid box if the index has no values.
2380
2381 It calls \c rtree::envelope().
2382
2383 \ingroup rtree_functions
2384
2385 \param tree The spatial index.
2386
2387 \return The box containing all stored values or an invalid box.
2388 */
2389 template <typename Value, typename Parameters, typename IndexableGetter, typename EqualTo, typename Allocator>
2390 inline typename rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator>::bounds_type
bounds(rtree<Value,Parameters,IndexableGetter,EqualTo,Allocator> const & tree)2391 bounds(rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator> const& tree)
2392 {
2393 return tree.bounds();
2394 }
2395
2396 /*!
2397 \brief Exchanges the contents of the container with those of other.
2398
2399 It calls \c rtree::swap().
2400
2401 \ingroup rtree_functions
2402
2403 \param l The first rtree.
2404 \param r The second rtree.
2405 */
2406 template <typename Value, typename Parameters, typename IndexableGetter, typename EqualTo, typename Allocator>
swap(rtree<Value,Parameters,IndexableGetter,EqualTo,Allocator> & l,rtree<Value,Parameters,IndexableGetter,EqualTo,Allocator> & r)2407 inline void swap(rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator> & l,
2408 rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator> & r)
2409 {
2410 return l.swap(r);
2411 }
2412
2413 }}} // namespace boost::geometry::index
2414
2415 // Boost.Range adaptation
2416 namespace boost {
2417
2418 template <typename Value, typename Parameters, typename IndexableGetter, typename EqualTo, typename Allocator>
2419 struct range_mutable_iterator
2420 <
2421 boost::geometry::index::rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator>
2422 >
2423 {
2424 typedef typename boost::geometry::index::rtree
2425 <
2426 Value, Parameters, IndexableGetter, EqualTo, Allocator
2427 >::const_iterator type;
2428 };
2429
2430 } // namespace boost
2431
2432 #include <boost/geometry/index/detail/config_end.hpp>
2433
2434 #endif // BOOST_GEOMETRY_INDEX_RTREE_HPP
2435