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