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