1 // Boost.Geometry Index
3 // R-tree implementation
5 // Copyright (c) 2008 Federico J. Fernandez.
6 // Copyright (c) 2011-2019 Adam Wulkiewicz, Lodz, Poland.
7 // Copyright (c) 2020 Caian Benedicto, Campinas, Brazil.
9 // This file was modified by Oracle on 2019-2021.
10 // Modifications copyright (c) 2019-2021 Oracle and/or its affiliates.
11 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
13 // Use, modification and distribution is subject to the Boost Software License,
14 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
15 // http://www.boost.org/LICENSE_1_0.txt)
17 #ifndef BOOST_GEOMETRY_INDEX_RTREE_HPP
18 #define BOOST_GEOMETRY_INDEX_RTREE_HPP
22 #include <type_traits>
25 #include <boost/container/new_allocator.hpp>
26 #include <boost/move/move.hpp>
27 #include <boost/tuple/tuple.hpp>
30 #include <boost/geometry/core/static_assert.hpp>
32 #include <boost/geometry/algorithms/detail/comparable_distance/interface.hpp>
33 #include <boost/geometry/algorithms/detail/covered_by/interface.hpp>
34 #include <boost/geometry/algorithms/detail/disjoint/interface.hpp>
35 #include <boost/geometry/algorithms/detail/equals/interface.hpp>
36 #include <boost/geometry/algorithms/detail/intersects/interface.hpp>
37 #include <boost/geometry/algorithms/detail/overlaps/interface.hpp>
38 #include <boost/geometry/algorithms/detail/touches/interface.hpp>
39 #include <boost/geometry/algorithms/detail/within/interface.hpp>
40 #include <boost/geometry/algorithms/centroid.hpp>
42 #include <boost/geometry/geometries/point.hpp>
43 #include <boost/geometry/geometries/box.hpp>
45 // Boost.Geometry.Index
46 #include <boost/geometry/index/detail/config_begin.hpp>
48 #include <boost/geometry/index/detail/assert.hpp>
49 #include <boost/geometry/index/detail/exception.hpp>
51 #include <boost/geometry/index/detail/rtree/options.hpp>
53 #include <boost/geometry/index/indexable.hpp>
54 #include <boost/geometry/index/equal_to.hpp>
56 #include <boost/geometry/index/detail/translator.hpp>
58 #include <boost/geometry/index/predicates.hpp>
59 #include <boost/geometry/index/distance_predicates.hpp>
60 #include <boost/geometry/index/detail/rtree/adaptors.hpp>
62 #include <boost/geometry/index/detail/meta.hpp>
63 #include <boost/geometry/index/detail/utilities.hpp>
64 #include <boost/geometry/index/detail/rtree/node/node.hpp>
66 #include <boost/geometry/index/detail/algorithms/is_valid.hpp>
68 #include <boost/geometry/index/detail/rtree/visitors/insert.hpp>
69 #include <boost/geometry/index/detail/rtree/visitors/iterator.hpp>
70 #include <boost/geometry/index/detail/rtree/visitors/remove.hpp>
71 #include <boost/geometry/index/detail/rtree/visitors/copy.hpp>
72 #include <boost/geometry/index/detail/rtree/visitors/destroy.hpp>
73 #include <boost/geometry/index/detail/rtree/visitors/spatial_query.hpp>
74 #include <boost/geometry/index/detail/rtree/visitors/distance_query.hpp>
75 #include <boost/geometry/index/detail/rtree/visitors/count.hpp>
76 #include <boost/geometry/index/detail/rtree/visitors/children_box.hpp>
78 #include <boost/geometry/index/detail/rtree/linear/linear.hpp>
79 #include <boost/geometry/index/detail/rtree/quadratic/quadratic.hpp>
80 #include <boost/geometry/index/detail/rtree/rstar/rstar.hpp>
81 //#include <boost/geometry/extensions/index/detail/rtree/kmeans/kmeans.hpp>
83 #include <boost/geometry/index/detail/rtree/pack_create.hpp>
85 #include <boost/geometry/index/inserter.hpp>
87 #include <boost/geometry/index/detail/rtree/utilities/view.hpp>
89 #include <boost/geometry/index/detail/rtree/iterators.hpp>
90 #include <boost/geometry/index/detail/rtree/query_iterators.hpp>
92 #ifdef BOOST_GEOMETRY_INDEX_DETAIL_EXPERIMENTAL
94 #include <boost/geometry/index/detail/serialization.hpp>
97 #include <boost/geometry/util/range.hpp>
98 #include <boost/geometry/util/type_traits.hpp>
100 // TODO change the name to bounding_tree
103 \defgroup rtree_functions R-tree free functions (boost::geometry::index::)
106 namespace boost { namespace geometry { namespace index {
109 \brief The R-tree spatial index.
111 This is self-balancing spatial index capable to store various types of Values
112 and balancing algorithms.
115 The user must pass a type defining the Parameters which will
116 be used in rtree creation process. This type is used e.g. to specify balancing
117 algorithm with specific parameters like min and max number of elements in node.
120 Predefined algorithms with compile-time parameters are:
121 \li <tt>boost::geometry::index::linear</tt>,
122 \li <tt>boost::geometry::index::quadratic</tt>,
123 \li <tt>boost::geometry::index::rstar</tt>.
126 Predefined algorithms with run-time parameters are:
127 \li \c boost::geometry::index::dynamic_linear,
128 \li \c boost::geometry::index::dynamic_quadratic,
129 \li \c boost::geometry::index::dynamic_rstar.
132 The object of IndexableGetter type translates from Value to Indexable each time
133 r-tree requires it. This means that this operation is done for each Value
134 access. Therefore the IndexableGetter should return the Indexable by
135 a reference type. The Indexable should not be calculated since it could harm
136 the performance. The default IndexableGetter can translate all types adapted
137 to Point, Box or Segment concepts (called Indexables). Furthermore, it can
138 handle <tt>std::pair<Indexable, T></tt>, <tt>std::tuple<Indexable, ...></tt>
139 and <tt>boost::tuple<Indexable, ...></tt>. For example, for Value
140 of type <tt>std::pair<Box, int></tt>, the default IndexableGetter translates
141 from <tt>std::pair<Box, int> const&</tt> to <tt>Box const&</tt>.
144 The object of EqualTo type compares Values and returns <tt>true</tt> if they
145 are equal. It's similar to <tt>std::equal_to<></tt>. The default EqualTo
146 returns the result of <tt>boost::geometry::equals()</tt> for types adapted to
147 some Geometry concept defined in Boost.Geometry and the result of
148 <tt>operator==</tt> for other types. Components of Pairs and Tuples are
149 compared left-to-right.
151 \tparam Value The type of objects stored in the container.
152 \tparam Parameters Compile-time parameters.
153 \tparam IndexableGetter The function object extracting Indexable from Value.
154 \tparam EqualTo The function object comparing objects of type Value.
155 \tparam Allocator The allocator used to allocate/deallocate memory,
156 construct/destroy nodes and Values.
162 typename IndexableGetter = index::indexable<Value>,
163 typename EqualTo = index::equal_to<Value>,
164 typename Allocator = boost::container::new_allocator<Value>
168 BOOST_COPYABLE_AND_MOVABLE(rtree)
171 /*! \brief The type of Value stored in the container. */
172 typedef Value value_type;
173 /*! \brief R-tree parameters type. */
174 typedef Parameters parameters_type;
175 /*! \brief The function object extracting Indexable from Value. */
176 typedef IndexableGetter indexable_getter;
177 /*! \brief The function object comparing objects of type Value. */
178 typedef EqualTo value_equal;
179 /*! \brief The type of allocator used by the container. */
180 typedef Allocator allocator_type;
182 // TODO: SHOULD THIS TYPE BE REMOVED?
183 /*! \brief The Indexable type to which Value is translated. */
184 typedef typename index::detail::indexable_type<
185 detail::translator<IndexableGetter, EqualTo>
186 >::type indexable_type;
188 /*! \brief The Box type used by the R-tree. */
189 typedef geometry::model::box<
190 geometry::model::point<
191 typename coordinate_type<indexable_type>::type,
192 dimension<indexable_type>::value,
193 typename coordinate_system<indexable_type>::type
200 typedef bounds_type box_type;
202 struct members_holder
203 : public detail::translator<IndexableGetter, EqualTo>
205 , public detail::rtree::allocators
211 typename detail::rtree::options_type<Parameters>::type::node_tag
214 typedef Value value_type;
215 typedef typename rtree::bounds_type bounds_type;
216 typedef Parameters parameters_type;
217 //typedef IndexableGetter indexable_getter;
218 //typedef EqualTo value_equal;
219 //typedef Allocator allocator_type;
221 typedef bounds_type box_type;
222 typedef detail::translator<IndexableGetter, EqualTo> translator_type;
223 typedef typename detail::rtree::options_type<Parameters>::type options_type;
224 typedef typename options_type::node_tag node_tag;
225 typedef detail::rtree::allocators
227 Allocator, Value, Parameters, bounds_type, node_tag
230 typedef typename detail::rtree::node
232 value_type, parameters_type, bounds_type, allocators_type, node_tag
234 typedef typename detail::rtree::internal_node
236 value_type, parameters_type, bounds_type, allocators_type, node_tag
237 >::type internal_node;
238 typedef typename detail::rtree::leaf
240 value_type, parameters_type, bounds_type, allocators_type, node_tag
243 // TODO: only one visitor type is needed
244 typedef typename detail::rtree::visitor
246 value_type, parameters_type, bounds_type, allocators_type, node_tag, false
248 typedef typename detail::rtree::visitor
250 value_type, parameters_type, bounds_type, allocators_type, node_tag, true
251 >::type visitor_const;
253 typedef typename allocators_type::node_pointer node_pointer;
255 typedef ::boost::container::allocator_traits<Allocator> allocator_traits_type;
256 typedef typename allocators_type::size_type size_type;
259 members_holder(members_holder const&);
260 members_holder & operator=(members_holder const&);
263 template <typename IndGet, typename ValEq, typename Alloc>
264 members_holder(IndGet const& ind_get,
266 Parameters const& parameters,
267 BOOST_FWD_REF(Alloc) alloc)
268 : translator_type(ind_get, val_eq)
269 , Parameters(parameters)
270 , allocators_type(boost::forward<Alloc>(alloc))
276 template <typename IndGet, typename ValEq>
277 members_holder(IndGet const& ind_get,
279 Parameters const& parameters)
280 : translator_type(ind_get, val_eq)
281 , Parameters(parameters)
288 translator_type const& translator() const { return *this; }
290 IndexableGetter const& indexable_getter() const { return *this; }
291 IndexableGetter & indexable_getter() { return *this; }
292 EqualTo const& equal_to() const { return *this; }
293 EqualTo & equal_to() { return *this; }
294 Parameters const& parameters() const { return *this; }
295 Parameters & parameters() { return *this; }
296 allocators_type const& allocators() const { return *this; }
297 allocators_type & allocators() { return *this; }
299 size_type values_count;
300 size_type leafs_level;
304 typedef typename members_holder::translator_type translator_type;
305 typedef typename members_holder::options_type options_type;
306 typedef typename members_holder::allocators_type allocators_type;
307 typedef typename members_holder::node node;
308 typedef typename members_holder::internal_node internal_node;
309 typedef typename members_holder::leaf leaf;
311 typedef typename members_holder::node_pointer node_pointer;
312 typedef typename members_holder::allocator_traits_type allocator_traits_type;
314 friend class detail::rtree::utilities::view<rtree>;
315 #ifdef BOOST_GEOMETRY_INDEX_DETAIL_EXPERIMENTAL
316 friend class detail::rtree::private_view<rtree>;
317 friend class detail::rtree::const_private_view<rtree>;
322 /*! \brief Type of reference to Value. */
323 typedef typename allocators_type::reference reference;
324 /*! \brief Type of reference to const Value. */
325 typedef typename allocators_type::const_reference const_reference;
326 /*! \brief Type of pointer to Value. */
327 typedef typename allocators_type::pointer pointer;
328 /*! \brief Type of pointer to const Value. */
329 typedef typename allocators_type::const_pointer const_pointer;
330 /*! \brief Type of difference type. */
331 typedef typename allocators_type::difference_type difference_type;
332 /*! \brief Unsigned integral type used by the container. */
333 typedef typename allocators_type::size_type size_type;
335 /*! \brief Type of const iterator, category ForwardIterator. */
336 typedef index::detail::rtree::iterators::iterator
338 value_type, options_type, translator_type, box_type, allocators_type
341 /*! \brief Type of const query iterator, category ForwardIterator. */
342 typedef index::detail::rtree::iterators::query_iterator
344 value_type, allocators_type
345 > const_query_iterator;
350 \brief The constructor.
352 \param parameters The parameters object.
353 \param getter The function object extracting Indexable from Value.
354 \param equal The function object comparing Values.
357 If allocator default constructor throws.
359 inline explicit rtree(parameters_type const& parameters = parameters_type(),
360 indexable_getter const& getter = indexable_getter(),
361 value_equal const& equal = value_equal())
362 : m_members(getter, equal, parameters)
366 \brief The constructor.
368 \param parameters The parameters object.
369 \param getter The function object extracting Indexable from Value.
370 \param equal The function object comparing Values.
371 \param allocator The allocator object.
374 If allocator copy constructor throws.
376 inline rtree(parameters_type const& parameters,
377 indexable_getter const& getter,
378 value_equal const& equal,
379 allocator_type const& allocator)
380 : m_members(getter, equal, parameters, allocator)
384 \brief The constructor.
386 The tree is created using packing algorithm.
388 \param first The beginning of the range of Values.
389 \param last The end of the range of Values.
390 \param parameters The parameters object.
391 \param getter The function object extracting Indexable from Value.
392 \param equal The function object comparing Values.
393 \param allocator The allocator object.
396 \li If allocator copy constructor throws.
397 \li If Value copy constructor or copy assignment throws.
398 \li If allocation throws or returns invalid value.
400 template<typename Iterator>
401 inline rtree(Iterator first, Iterator last,
402 parameters_type const& parameters = parameters_type(),
403 indexable_getter const& getter = indexable_getter(),
404 value_equal const& equal = value_equal(),
405 allocator_type const& allocator = allocator_type())
406 : m_members(getter, equal, parameters, allocator)
408 pack_construct(first, last, boost::container::new_allocator<void>());
412 \brief The constructor.
414 The tree is created using packing algorithm.
416 \param rng The range of Values.
417 \param parameters The parameters object.
418 \param getter The function object extracting Indexable from Value.
419 \param equal The function object comparing Values.
420 \param allocator The allocator object.
423 \li If allocator copy constructor throws.
424 \li If Value copy constructor or copy assignment throws.
425 \li If allocation throws or returns invalid value.
427 template<typename Range>
428 inline explicit rtree(Range const& rng,
429 parameters_type const& parameters = parameters_type(),
430 indexable_getter const& getter = indexable_getter(),
431 value_equal const& equal = value_equal(),
432 allocator_type const& allocator = allocator_type())
433 : m_members(getter, equal, parameters, allocator)
435 pack_construct(::boost::begin(rng), ::boost::end(rng), boost::container::new_allocator<void>());
439 \brief The constructor.
441 The tree is created using packing algorithm and a temporary packing allocator.
443 \param first The beginning of the range of Values.
444 \param last The end of the range of Values.
445 \param parameters The parameters object.
446 \param getter The function object extracting Indexable from Value.
447 \param equal The function object comparing Values.
448 \param allocator The allocator object for persistent data in the tree.
449 \param temp_allocator The temporary allocator object used when packing.
452 \li If allocator copy constructor throws.
453 \li If Value copy constructor or copy assignment throws.
454 \li If allocation throws or returns invalid value.
456 template<typename Iterator, typename PackAlloc>
457 inline rtree(Iterator first, Iterator last,
458 parameters_type const& parameters,
459 indexable_getter const& getter,
460 value_equal const& equal,
461 allocator_type const& allocator,
462 PackAlloc const& temp_allocator)
463 : m_members(getter, equal, parameters, allocator)
465 pack_construct(first, last, temp_allocator);
469 \brief The constructor.
471 The tree is created using packing algorithm and a temporary packing allocator.
473 \param rng The range of Values.
474 \param parameters The parameters object.
475 \param getter The function object extracting Indexable from Value.
476 \param equal The function object comparing Values.
477 \param allocator The allocator object for persistent data in the tree.
478 \param temp_allocator The temporary allocator object used when packing.
481 \li If allocator copy constructor throws.
482 \li If Value copy constructor or copy assignment throws.
483 \li If allocation throws or returns invalid value.
485 template<typename Range, typename PackAlloc>
486 inline explicit rtree(Range const& rng,
487 parameters_type const& parameters,
488 indexable_getter const& getter,
489 value_equal const& equal,
490 allocator_type const& allocator,
491 PackAlloc const& temp_allocator)
492 : m_members(getter, equal, parameters, allocator)
494 pack_construct(::boost::begin(rng), ::boost::end(rng), temp_allocator);
498 \brief The constructor.
500 The tree is created using packing algorithm and a temporary packing allocator.
502 \param first The beginning of the range of Values.
503 \param last The end of the range of Values.
504 \param allocator The allocator object for persistent data in the tree.
507 \li If allocator copy constructor throws.
508 \li If Value copy constructor or copy assignment throws.
509 \li If allocation throws or returns invalid value.
511 template<typename Iterator>
512 inline rtree(Iterator first, Iterator last,
513 allocator_type const& allocator)
514 : m_members(indexable_getter(), value_equal(), parameters_type(), allocator)
516 pack_construct(first, last, boost::container::new_allocator<void>());
520 \brief The constructor.
522 The tree is created using packing algorithm and a temporary packing allocator.
524 \param rng The range of Values.
525 \param allocator The allocator object for persistent data in the tree.
528 \li If allocator copy constructor throws.
529 \li If Value copy constructor or copy assignment throws.
530 \li If allocation throws or returns invalid value.
532 template<typename Range>
533 inline explicit rtree(Range const& rng,
534 allocator_type const& allocator)
535 : m_members(indexable_getter(), value_equal(), parameters_type(), allocator)
537 pack_construct(::boost::begin(rng), ::boost::end(rng), boost::container::new_allocator<void>());
541 \brief The constructor.
543 The tree is created using packing algorithm and a temporary packing allocator.
545 \param first The beginning of the range of Values.
546 \param last The end of the range of Values.
547 \param allocator The allocator object for persistent data in the tree.
548 \param temp_allocator The temporary allocator object used when packing.
551 \li If allocator copy constructor throws.
552 \li If Value copy constructor or copy assignment throws.
553 \li If allocation throws or returns invalid value.
555 template<typename Iterator, typename PackAlloc>
556 inline rtree(Iterator first, Iterator last,
557 allocator_type const& allocator,
558 PackAlloc const& temp_allocator)
559 : m_members(indexable_getter(), value_equal(), parameters_type(), allocator)
561 pack_construct(first, last, temp_allocator);
565 \brief The constructor.
567 The tree is created using packing algorithm and a temporary packing allocator.
569 \param rng The range of Values.
570 \param allocator The allocator object for persistent data in the tree.
571 \param temp_allocator The temporary allocator object used when packing.
574 \li If allocator copy constructor throws.
575 \li If Value copy constructor or copy assignment throws.
576 \li If allocation throws or returns invalid value.
578 template<typename Range, typename PackAlloc>
579 inline explicit rtree(Range const& rng,
580 allocator_type const& allocator,
581 PackAlloc const& temp_allocator)
582 : m_members(indexable_getter(), value_equal(), parameters_type(), allocator)
584 pack_construct(::boost::begin(rng), ::boost::end(rng), temp_allocator);
588 \brief The destructor.
595 this->raw_destroy(*this);
599 \brief The copy constructor.
601 It uses parameters, translator and allocator from the source tree.
603 \param src The rtree which content will be copied.
606 \li If allocator copy constructor throws.
607 \li If Value copy constructor throws.
608 \li If allocation throws or returns invalid value.
610 inline rtree(rtree const& src)
611 : m_members(src.m_members.indexable_getter(),
612 src.m_members.equal_to(),
613 src.m_members.parameters(),
614 allocator_traits_type::select_on_container_copy_construction(src.get_allocator()))
616 this->raw_copy(src, *this, false);
620 \brief The copy constructor.
622 It uses Parameters and translator from the source tree.
624 \param src The rtree which content will be copied.
625 \param allocator The allocator which will be used.
628 \li If allocator copy constructor throws.
629 \li If Value copy constructor throws.
630 \li If allocation throws or returns invalid value.
632 inline rtree(rtree const& src, allocator_type const& allocator)
633 : m_members(src.m_members.indexable_getter(),
634 src.m_members.equal_to(),
635 src.m_members.parameters(), allocator)
637 this->raw_copy(src, *this, false);
641 \brief The moving constructor.
643 It uses parameters, translator and allocator from the source tree.
645 \param src The rtree which content will be moved.
650 inline rtree(BOOST_RV_REF(rtree) src)
651 : m_members(src.m_members.indexable_getter(),
652 src.m_members.equal_to(),
653 src.m_members.parameters(),
654 boost::move(src.m_members.allocators()))
656 boost::swap(m_members.values_count, src.m_members.values_count);
657 boost::swap(m_members.leafs_level, src.m_members.leafs_level);
658 boost::swap(m_members.root, src.m_members.root);
662 \brief The moving constructor.
664 It uses parameters and translator from the source tree.
666 \param src The rtree which content will be moved.
667 \param allocator The allocator.
670 \li If allocator copy constructor throws.
671 \li If Value copy constructor throws (only if allocators aren't equal).
672 \li If allocation throws or returns invalid value (only if allocators aren't equal).
674 inline rtree(BOOST_RV_REF(rtree) src, allocator_type const& allocator)
675 : m_members(src.m_members.indexable_getter(),
676 src.m_members.equal_to(),
677 src.m_members.parameters(),
680 if ( src.m_members.allocators() == allocator )
682 boost::swap(m_members.values_count, src.m_members.values_count);
683 boost::swap(m_members.leafs_level, src.m_members.leafs_level);
684 boost::swap(m_members.root, src.m_members.root);
688 this->raw_copy(src, *this, false);
693 \brief The assignment operator.
695 It uses parameters and translator from the source tree.
697 \param src The rtree which content will be copied.
700 \li If Value copy constructor throws.
701 \li If allocation throws.
702 \li If allocation throws or returns invalid value.
704 inline rtree & operator=(BOOST_COPY_ASSIGN_REF(rtree) src)
708 allocators_type & this_allocs = m_members.allocators();
709 allocators_type const& src_allocs = src.m_members.allocators();
711 // NOTE: if propagate is true for std allocators on darwin 4.2.1, glibc++
712 // (allocators stored as base classes of members_holder)
713 // copying them changes values_count, in this case it doesn't cause errors since data must be copied
715 typedef std::integral_constant<bool,
716 allocator_traits_type::propagate_on_container_copy_assignment::value
719 if ( propagate::value && !(this_allocs == src_allocs) )
720 this->raw_destroy(*this);
721 detail::assign_cond(this_allocs, src_allocs, propagate());
723 // It uses m_allocators
724 this->raw_copy(src, *this, true);
731 \brief The moving assignment.
733 It uses parameters and translator from the source tree.
735 \param src The rtree which content will be moved.
738 Only if allocators aren't equal.
739 \li If Value copy constructor throws.
740 \li If allocation throws or returns invalid value.
742 inline rtree & operator=(BOOST_RV_REF(rtree) src)
746 allocators_type & this_allocs = m_members.allocators();
747 allocators_type & src_allocs = src.m_members.allocators();
749 if ( this_allocs == src_allocs )
751 this->raw_destroy(*this);
753 m_members.indexable_getter() = src.m_members.indexable_getter();
754 m_members.equal_to() = src.m_members.equal_to();
755 m_members.parameters() = src.m_members.parameters();
757 boost::swap(m_members.values_count, src.m_members.values_count);
758 boost::swap(m_members.leafs_level, src.m_members.leafs_level);
759 boost::swap(m_members.root, src.m_members.root);
761 // NOTE: if propagate is true for std allocators on darwin 4.2.1, glibc++
762 // (allocators stored as base classes of members_holder)
763 // moving them changes values_count
765 typedef std::integral_constant<bool,
766 allocator_traits_type::propagate_on_container_move_assignment::value
768 detail::move_cond(this_allocs, src_allocs, propagate());
772 // TODO - shouldn't here propagate_on_container_copy_assignment be checked like in operator=(const&)?
774 // It uses m_allocators
775 this->raw_copy(src, *this, true);
783 \brief Swaps contents of two rtrees.
785 Parameters, translator and allocators are swapped as well.
787 \param other The rtree which content will be swapped with this rtree content.
790 If allocators swap throws.
792 void swap(rtree & other)
794 boost::swap(m_members.indexable_getter(), other.m_members.indexable_getter());
795 boost::swap(m_members.equal_to(), other.m_members.equal_to());
796 boost::swap(m_members.parameters(), other.m_members.parameters());
798 // NOTE: if propagate is true for std allocators on darwin 4.2.1, glibc++
799 // (allocators stored as base classes of members_holder)
800 // swapping them changes values_count
802 typedef std::integral_constant<bool,
803 allocator_traits_type::propagate_on_container_swap::value
805 detail::swap_cond(m_members.allocators(), other.m_members.allocators(), propagate());
807 boost::swap(m_members.values_count, other.m_members.values_count);
808 boost::swap(m_members.leafs_level, other.m_members.leafs_level);
809 boost::swap(m_members.root, other.m_members.root);
813 \brief Insert a value to the index.
815 \param value The value which will be stored in the container.
818 \li If Value copy constructor or copy assignment throws.
819 \li If allocation throws or returns invalid value.
822 This operation only guarantees that there will be no memory leaks.
823 After an exception is thrown the R-tree may be left in an inconsistent state,
824 elements must not be inserted or removed. Other operations are allowed however
825 some of them may return invalid data.
827 inline void insert(value_type const& value)
829 if ( !m_members.root )
832 this->raw_insert(value);
836 \brief Insert a range of values to the index.
838 \param first The beginning of the range of values.
839 \param last The end of the range of values.
842 \li If Value copy constructor or copy assignment throws.
843 \li If allocation throws or returns invalid value.
846 This operation only guarantees that there will be no memory leaks.
847 After an exception is thrown the R-tree may be left in an inconsistent state,
848 elements must not be inserted or removed. Other operations are allowed however
849 some of them may return invalid data.
851 template <typename Iterator>
852 inline void insert(Iterator first, Iterator last)
854 if ( !m_members.root )
857 for ( ; first != last ; ++first )
858 this->raw_insert(*first);
862 \brief Insert a value created using convertible object or a range of values to the index.
864 \param conv_or_rng An object of type convertible to value_type or a range of values.
867 \li If Value copy constructor or copy assignment throws.
868 \li If allocation throws or returns invalid value.
871 This operation only guarantees that there will be no memory leaks.
872 After an exception is thrown the R-tree may be left in an inconsistent state,
873 elements must not be inserted or removed. Other operations are allowed however
874 some of them may return invalid data.
876 template <typename ConvertibleOrRange>
877 inline void insert(ConvertibleOrRange const& conv_or_rng)
879 if ( !m_members.root )
882 typedef std::is_convertible<ConvertibleOrRange, value_type> is_conv_t;
883 typedef range::detail::is_range<ConvertibleOrRange> is_range_t;
884 BOOST_GEOMETRY_STATIC_ASSERT((is_conv_t::value || is_range_t::value),
885 "The argument has to be convertible to Value type or be a Range.",
888 this->insert_dispatch(conv_or_rng, is_conv_t());
892 \brief Remove a value from the container.
894 In contrast to the \c std::set or <tt>std::map erase()</tt> method
895 this method removes only one value from the container.
897 \param value The value which will be removed from the container.
899 \return 1 if the value was removed, 0 otherwise.
902 \li If Value copy constructor or copy assignment throws.
903 \li If allocation throws or returns invalid value.
906 This operation only guarantees that there will be no memory leaks.
907 After an exception is thrown the R-tree may be left in an inconsistent state,
908 elements must not be inserted or removed. Other operations are allowed however
909 some of them may return invalid data.
911 inline size_type remove(value_type const& value)
913 if ( !m_members.root )
916 return this->raw_remove(value);
920 \brief Remove a range of values from the container.
922 In contrast to the \c std::set or <tt>std::map erase()</tt> method
923 it doesn't take iterators pointing to values stored in this container. It removes values equal
924 to these passed as a range. Furthermore this method removes only one value for each one passed
925 in the range, not all equal values.
927 \param first The beginning of the range of values.
928 \param last The end of the range of values.
930 \return The number of removed values.
933 \li If Value copy constructor or copy assignment throws.
934 \li If allocation throws or returns invalid value.
937 This operation only guarantees that there will be no memory leaks.
938 After an exception is thrown the R-tree may be left in an inconsistent state,
939 elements must not be inserted or removed. Other operations are allowed however
940 some of them may return invalid data.
942 template <typename Iterator>
943 inline size_type remove(Iterator first, Iterator last)
945 size_type result = 0;
947 if ( !m_members.root )
950 for ( ; first != last ; ++first )
951 result += this->raw_remove(*first);
956 \brief Remove value corresponding to an object convertible to it or a range of values from the container.
958 In contrast to the \c std::set or <tt>std::map erase()</tt> method
959 it removes values equal to these passed as a range. Furthermore, this method removes only
960 one value for each one passed in the range, not all equal values.
962 \param conv_or_rng The object of type convertible to value_type or a range of values.
964 \return The number of removed values.
967 \li If Value copy constructor or copy assignment throws.
968 \li If allocation throws or returns invalid value.
971 This operation only guarantees that there will be no memory leaks.
972 After an exception is thrown the R-tree may be left in an inconsistent state,
973 elements must not be inserted or removed. Other operations are allowed however
974 some of them may return invalid data.
976 template <typename ConvertibleOrRange>
977 inline size_type remove(ConvertibleOrRange const& conv_or_rng)
979 if ( !m_members.root )
982 typedef std::is_convertible<ConvertibleOrRange, value_type> is_conv_t;
983 typedef range::detail::is_range<ConvertibleOrRange> is_range_t;
984 BOOST_GEOMETRY_STATIC_ASSERT((is_conv_t::value || is_range_t::value),
985 "The argument has to be convertible to Value type or be a Range.",
988 return this->remove_dispatch(conv_or_rng, is_conv_t());
992 \brief Finds values meeting passed predicates e.g. nearest to some Point and/or intersecting some Box.
994 This query function performs spatial and k-nearest neighbor searches. It allows to pass a set of predicates.
995 Values will be returned only if all predicates are met.
997 <b>Spatial predicates</b>
999 Spatial predicates may be generated by one of the functions listed below:
1000 \li \c boost::geometry::index::contains(),
1001 \li \c boost::geometry::index::covered_by(),
1002 \li \c boost::geometry::index::covers(),
1003 \li \c boost::geometry::index::disjoint(),
1004 \li \c boost::geometry::index::intersects(),
1005 \li \c boost::geometry::index::overlaps(),
1006 \li \c boost::geometry::index::within(),
1008 It is possible to negate spatial predicates:
1009 \li <tt>! boost::geometry::index::contains()</tt>,
1010 \li <tt>! boost::geometry::index::covered_by()</tt>,
1011 \li <tt>! boost::geometry::index::covers()</tt>,
1012 \li <tt>! boost::geometry::index::disjoint()</tt>,
1013 \li <tt>! boost::geometry::index::intersects()</tt>,
1014 \li <tt>! boost::geometry::index::overlaps()</tt>,
1015 \li <tt>! boost::geometry::index::within()</tt>
1017 <b>Satisfies predicate</b>
1019 This is a special kind of predicate which allows to pass a user-defined function or function object which checks
1020 if Value should be returned by the query. It's generated by:
1021 \li \c boost::geometry::index::satisfies().
1023 <b>Nearest predicate</b>
1025 If the nearest predicate is passed a k-nearest neighbor search will be performed. This query will result
1026 in returning k values to the output iterator. Only one nearest predicate may be passed to the query.
1027 It may be generated by:
1028 \li \c boost::geometry::index::nearest().
1030 <b>Connecting predicates</b>
1032 Predicates may be passed together connected with \c operator&&().
1036 // return elements intersecting box
1037 tree.query(bgi::intersects(box), std::back_inserter(result));
1038 // return elements intersecting poly but not within box
1039 tree.query(bgi::intersects(poly) && !bgi::within(box), std::back_inserter(result));
1040 // return elements overlapping box and meeting my_fun unary predicate
1041 tree.query(bgi::overlaps(box) && bgi::satisfies(my_fun), std::back_inserter(result));
1042 // return 5 elements nearest to pt and elements are intersecting box
1043 tree.query(bgi::nearest(pt, 5) && bgi::intersects(box), std::back_inserter(result));
1045 // For each found value do_something (it is a type of function object)
1046 tree.query(bgi::intersects(box),
1047 boost::make_function_output_iterator(do_something()));
1049 // For each value stored in the rtree do_something
1050 // always_true is a type of function object always returning true
1051 tree.query(bgi::satisfies(always_true()),
1052 boost::make_function_output_iterator(do_something()));
1054 // C++11 (lambda expression)
1055 tree.query(bgi::intersects(box),
1056 boost::make_function_output_iterator([](value_type const& val){
1060 // C++14 (generic lambda expression)
1061 tree.query(bgi::intersects(box),
1062 boost::make_function_output_iterator([](auto const& val){
1068 If Value copy constructor or copy assignment throws.
1069 If predicates copy throws.
1072 Only one \c nearest() predicate may be passed to the query. Passing more of them results in compile-time error.
1074 \param predicates Predicates.
1075 \param out_it The output iterator, e.g. generated by std::back_inserter().
1077 \return The number of values found.
1079 template <typename Predicates, typename OutIter>
1080 size_type query(Predicates const& predicates, OutIter out_it) const
1082 return m_members.root
1083 ? query_dispatch(predicates, out_it)
1088 \brief Returns a query iterator pointing at the begin of the query range.
1090 This method returns an iterator which may be used to perform iterative queries.
1091 For the information about predicates which may be passed to this method see query().
1095 for ( Rtree::const_query_iterator it = tree.qbegin(bgi::nearest(pt, 10000)) ;
1096 it != tree.qend() ; ++it )
1098 // do something with value
1099 if ( has_enough_nearest_values() )
1104 for ( auto it = tree.qbegin(bgi::nearest(pt, 3)) ; it != tree.qend() ; ++it )
1106 // do something with value
1109 // C++14 (generic lambda expression)
1110 std::for_each(tree.qbegin(bgi::nearest(pt, 3)), tree.qend(), [](auto const& val){
1111 // do something with value
1115 \par Iterator category
1119 If predicates copy throws.
1120 If allocation throws.
1123 The modification of the rtree may invalidate the iterators.
1125 \param predicates Predicates.
1127 \return The iterator pointing at the begin of the query range.
1129 template <typename Predicates>
1130 const_query_iterator qbegin(Predicates const& predicates) const
1132 return const_query_iterator(qbegin_(predicates));
1136 \brief Returns a query iterator pointing at the end of the query range.
1138 This method returns an iterator which may be used to check if the query has ended.
1142 for ( Rtree::const_query_iterator it = tree.qbegin(bgi::nearest(pt, 10000)) ;
1143 it != tree.qend() ; ++it )
1145 // do something with value
1146 if ( has_enough_nearest_values() )
1151 for ( auto it = tree.qbegin(bgi::nearest(pt, 3)) ; it != tree.qend() ; ++it )
1153 // do something with value
1156 // C++14 (generic lambda expression)
1157 std::for_each(tree.qbegin(bgi::nearest(pt, 3)), tree.qend(), [](auto const& val){
1158 // do something with value
1162 \par Iterator category
1169 The modification of the rtree may invalidate the iterators.
1171 \return The iterator pointing at the end of the query range.
1173 const_query_iterator qend() const
1175 return const_query_iterator();
1179 template <typename Predicates>
1180 using query_iterator_t = std::conditional_t
1182 detail::predicates_count_distance<Predicates>::value == 0,
1183 detail::rtree::iterators::spatial_query_iterator<members_holder, Predicates>,
1184 detail::rtree::iterators::distance_query_iterator<members_holder, Predicates>
1187 #ifndef BOOST_GEOMETRY_INDEX_DETAIL_EXPERIMENTAL
1191 \brief Returns a query iterator pointing at the begin of the query range.
1193 This method returns an iterator which may be used to perform iterative queries.
1194 For the information about predicates which may be passed to this method see query().
1196 The type of the returned iterator depends on the type of passed Predicates but the iterator of this type
1197 may be assigned to the variable of const_query_iterator type. If you'd like to use the type of the iterator
1198 returned by this method you may get the type e.g. by using C++11 decltype or Boost.Typeof library.
1199 This iterator may be compared with iterators returned by both versions of qend() method.
1203 // Store the result in the container using std::copy() - it requires both iterators of the same type
1204 std::copy(tree.qbegin_(bgi::intersects(box)), tree.qend_(bgi::intersects(box)), std::back_inserter(result));
1206 // Store the result in the container using std::copy() and type-erased iterators
1207 Rtree::const_query_iterator first = tree.qbegin_(bgi::intersects(box));
1208 Rtree::const_query_iterator last = tree.qend_();
1209 std::copy(first, last, std::back_inserter(result));
1212 typedef BOOST_TYPEOF(tree.qbegin(bgi::nearest(pt, 10000))) Iter;
1213 for ( Iter it = tree.qbegin_(bgi::nearest(pt, 10000)) ; it != tree.qend_() ; ++it )
1215 // do something with value
1216 if ( has_enough_nearest_values() )
1221 for ( auto it = tree.qbegin_(bgi::nearest(pt, 10000)) ; it != tree.qend_() ; ++it )
1223 // do something with value
1224 if ( has_enough_nearest_values() )
1229 \par Iterator category
1233 If predicates copy throws.
1234 If allocation throws.
1237 The modification of the rtree may invalidate the iterators.
1239 \param predicates Predicates.
1241 \return The iterator pointing at the begin of the query range.
1243 template <typename Predicates>
1244 query_iterator_t<Predicates> qbegin_(Predicates const& predicates) const
1246 BOOST_GEOMETRY_STATIC_ASSERT((detail::predicates_count_distance<Predicates>::value <= 1),
1247 "Only one distance predicate can be passed.",
1250 return m_members.root
1251 ? query_iterator_t<Predicates>(m_members, predicates)
1252 : query_iterator_t<Predicates>(predicates);
1256 \brief Returns the query iterator pointing at the end of the query range.
1258 This method returns the iterator which may be used to perform iterative queries. For the information
1259 about the predicates which may be passed to this method see query().
1261 The type of the returned iterator depends on the type of passed Predicates but the iterator of this type
1262 may be assigned to the variable of const_query_iterator type. If you'd like to use the type of the iterator
1263 returned by this method you may get the type e.g. by using C++11 decltype or Boost.Typeof library.
1265 The type of the iterator returned by this method is the same as the one returned by qbegin() to which
1266 the same predicates were passed.
1270 // Store the result in the container using std::copy() - it requires both iterators of the same type
1271 std::copy(tree.qbegin_(bgi::intersects(box)), tree.qend_(bgi::intersects(box)), std::back_inserter(result));
1274 \par Iterator category
1278 If predicates copy throws.
1281 The modification of the rtree may invalidate the iterators.
1283 \param predicates Predicates.
1285 \return The iterator pointing at the end of the query range.
1287 template <typename Predicates>
1288 query_iterator_t<Predicates> qend_(Predicates const& predicates) const
1290 BOOST_GEOMETRY_STATIC_ASSERT((detail::predicates_count_distance<Predicates>::value <= 1),
1291 "Only one distance predicate can be passed.",
1294 return query_iterator_t<Predicates>(m_members.parameters(), m_members.translator(), predicates);
1298 \brief Returns the query iterator pointing at the end of the query range.
1300 This method returns the iterator which may be compared with the iterator returned by qbegin() in order to
1301 check if the query has ended.
1303 The type of the returned iterator is different than the type returned by qbegin() but the iterator of this type
1304 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
1305 method, which most certainly will be faster than the type-erased iterator, you may get the type
1306 e.g. by using C++11 decltype or Boost.Typeof library.
1308 The type of the iterator returned by this method is different than the type returned by qbegin().
1312 // Store the result in the container using std::copy() and type-erased iterators
1313 Rtree::const_query_iterator first = tree.qbegin_(bgi::intersects(box));
1314 Rtree::const_query_iterator last = tree.qend_();
1315 std::copy(first, last, std::back_inserter(result));
1318 typedef BOOST_TYPEOF(tree.qbegin(bgi::nearest(pt, 10000))) Iter;
1319 for ( Iter it = tree.qbegin_(bgi::nearest(pt, 10000)) ; it != tree.qend_() ; ++it )
1321 // do something with value
1322 if ( has_enough_nearest_values() )
1327 for ( auto it = tree.qbegin_(bgi::nearest(pt, 10000)) ; it != tree.qend_() ; ++it )
1329 // do something with value
1330 if ( has_enough_nearest_values() )
1335 \par Iterator category
1342 The modification of the rtree may invalidate the iterators.
1344 \return The iterator pointing at the end of the query range.
1346 detail::rtree::iterators::end_query_iterator<value_type, allocators_type>
1349 return detail::rtree::iterators::end_query_iterator<value_type, allocators_type>();
1355 \brief Returns the iterator pointing at the begin of the rtree values range.
1357 This method returns the iterator which may be used to iterate over all values
1358 stored in the rtree.
1362 // Copy all values into the vector
1363 std::copy(tree.begin(), tree.end(), std::back_inserter(vec));
1365 for ( Rtree::const_iterator it = tree.begin() ; it != tree.end() ; ++it )
1367 // do something with value
1371 for ( auto it = tree.begin() ; it != tree.end() ; ++it )
1373 // do something with value
1376 // C++14 (generic lambda expression)
1377 std::for_each(tree.begin(), tree.end(), [](auto const& val){
1378 // do something with value
1382 \par Iterator category
1386 If allocation throws.
1389 The modification of the rtree may invalidate the iterators.
1391 \return The iterator pointing at the begin of the range.
1393 const_iterator begin() const
1395 return m_members.root
1396 ? const_iterator(m_members.root)
1401 \brief Returns the iterator pointing at the end of the rtree values range.
1403 This method returns the iterator which may be compared with the iterator returned by begin()
1404 in order to check if the iteration has ended.
1408 for ( Rtree::const_iterator it = tree.begin() ; it != tree.end() ; ++it )
1410 // do something with value
1413 // C++11 (lambda expression)
1414 std::for_each(tree.begin(), tree.end(), [](value_type const& val){
1415 // do something with value
1419 \par Iterator category
1426 The modification of the rtree may invalidate the iterators.
1428 \return The iterator pointing at the end of the range.
1430 const_iterator end() const
1432 return const_iterator();
1436 \brief Returns the number of stored values.
1438 \return The number of stored values.
1443 inline size_type size() const
1445 return m_members.values_count;
1449 \brief Query if the container is empty.
1451 \return true if the container is empty.
1456 inline bool empty() const
1458 return 0 == m_members.values_count;
1462 \brief Removes all values stored in the container.
1469 this->raw_destroy(*this);
1473 \brief Returns the box able to contain all values stored in the container.
1475 Returns the box able to contain all values stored in the container.
1476 If the container is empty the result of \c geometry::assign_inverse() is returned.
1478 \return The box able to contain all values stored in the container or an invalid box if
1479 there are no values in the container.
1484 inline bounds_type bounds() const
1487 // in order to suppress the uninitialized variable warnings
1488 geometry::assign_inverse(result);
1490 if ( m_members.root )
1492 detail::rtree::visitors::children_box
1495 > box_v(result, m_members.parameters(), m_members.translator());
1496 detail::rtree::apply_visitor(box_v, *m_members.root);
1503 \brief Count Values or Indexables stored in the container.
1505 For indexable_type it returns the number of values which indexables equals the parameter.
1506 For value_type it returns the number of values which equals the parameter.
1508 \param vori The value or indexable which will be counted.
1510 \return The number of values found.
1515 template <typename ValueOrIndexable>
1516 size_type count(ValueOrIndexable const& vori) const
1518 if ( !m_members.root )
1521 // the input should be convertible to Value or Indexable type
1522 typedef typename index::detail::convertible_type
1527 >::type value_or_indexable;
1529 static const bool is_void = std::is_void<value_or_indexable>::value;
1530 BOOST_GEOMETRY_STATIC_ASSERT((! is_void),
1531 "The argument has to be convertible to Value or Indexable type.",
1534 // NOTE: If an object of convertible but not the same type is passed
1535 // into the function, here a temporary will be created.
1536 return this->template raw_count<value_or_indexable>(vori);
1540 \brief Returns parameters.
1542 \return The parameters object.
1547 inline parameters_type parameters() const
1549 return m_members.parameters();
1553 \brief Returns function retrieving Indexable from Value.
1555 \return The indexable_getter object.
1560 indexable_getter indexable_get() const
1562 return m_members.indexable_getter();
1566 \brief Returns function comparing Values
1568 \return The value_equal function.
1573 value_equal value_eq() const
1575 return m_members.equal_to();
1579 \brief Returns allocator used by the rtree.
1581 \return The allocator.
1584 If allocator copy constructor throws.
1586 allocator_type get_allocator() const
1588 return m_members.allocators().allocator();
1594 \brief Returns the translator object.
1596 \return The translator object.
1601 inline translator_type translator() const
1603 return m_members.translator();
1607 \brief Apply a visitor to the nodes structure in order to perform some operator.
1609 This function is not a part of the 'official' interface. However it makes
1610 possible e.g. to pass a visitor drawing the tree structure.
1612 \param visitor The visitor object.
1615 If Visitor::operator() throws.
1617 template <typename Visitor>
1618 inline void apply_visitor(Visitor & visitor) const
1620 if ( m_members.root )
1621 detail::rtree::apply_visitor(visitor, *m_members.root);
1625 \brief Returns the depth of the R-tree.
1627 This function is not a part of the 'official' interface.
1629 \return The depth of the R-tree.
1634 inline size_type depth() const
1636 return m_members.leafs_level;
1642 \pre Root node must exist - m_root != 0.
1644 \brief Insert a value to the index.
1646 \param value The value which will be stored in the container.
1648 \par Exception-safety
1651 inline void raw_insert(value_type const& value)
1653 BOOST_GEOMETRY_INDEX_ASSERT(m_members.root, "The root must exist");
1654 // CONSIDER: alternative - ignore invalid indexable or throw an exception
1655 BOOST_GEOMETRY_INDEX_ASSERT(detail::is_valid(m_members.translator()(value)), "Indexable is invalid");
1657 detail::rtree::visitors::insert<value_type, members_holder>
1658 insert_v(m_members.root, m_members.leafs_level, value,
1659 m_members.parameters(), m_members.translator(), m_members.allocators());
1661 detail::rtree::apply_visitor(insert_v, *m_members.root);
1664 // Think about this: If exception is thrown, may the root be removed?
1665 // Or it is just cleared?
1668 // If exception is thrown, m_values_count may be invalid
1669 ++m_members.values_count;
1673 \brief Remove the value from the container.
1675 \param value The value which will be removed from the container.
1677 \par Exception-safety
1680 inline size_type raw_remove(value_type const& value)
1682 // TODO: awulkiew - assert for correct value (indexable) ?
1683 BOOST_GEOMETRY_INDEX_ASSERT(m_members.root, "The root must exist");
1685 detail::rtree::visitors::remove<members_holder>
1686 remove_v(m_members.root, m_members.leafs_level, value,
1687 m_members.parameters(), m_members.translator(), m_members.allocators());
1689 detail::rtree::apply_visitor(remove_v, *m_members.root);
1691 // If exception is thrown, m_values_count may be invalid
1693 if ( remove_v.is_value_removed() )
1695 BOOST_GEOMETRY_INDEX_ASSERT(0 < m_members.values_count, "unexpected state");
1697 --m_members.values_count;
1706 \brief Create an empty R-tree i.e. new empty root node and clear other attributes.
1708 \par Exception-safety
1711 inline void raw_create()
1713 BOOST_GEOMETRY_INDEX_ASSERT(0 == m_members.root, "the tree is already created");
1715 m_members.root = detail::rtree::create_node<allocators_type, leaf>::apply(m_members.allocators()); // MAY THROW (N: alloc)
1716 m_members.values_count = 0;
1717 m_members.leafs_level = 0;
1721 \brief Destroy the R-tree i.e. all nodes and clear attributes.
1723 \param t The container which is going to be destroyed.
1725 \par Exception-safety
1728 inline void raw_destroy(rtree & t)
1730 if ( t.m_members.root )
1732 detail::rtree::visitors::destroy<members_holder>
1733 ::apply(t.m_members.root, t.m_members.allocators());
1735 t.m_members.root = 0;
1737 t.m_members.values_count = 0;
1738 t.m_members.leafs_level = 0;
1742 \brief Copy the R-tree i.e. whole nodes structure, values and other attributes.
1743 It uses destination's allocators to create the new structure.
1745 \param src The source R-tree.
1746 \param dst The destination R-tree.
1747 \param copy_tr_and_params If true, translator and parameters will also be copied.
1749 \par Exception-safety
1752 inline void raw_copy(rtree const& src, rtree & dst, bool copy_tr_and_params) const
1754 detail::rtree::visitors::copy<members_holder> copy_v(dst.m_members.allocators());
1756 if ( src.m_members.root )
1757 detail::rtree::apply_visitor(copy_v, *src.m_members.root); // MAY THROW (V, E: alloc, copy, N: alloc)
1759 if ( copy_tr_and_params )
1761 dst.m_members.indexable_getter() = src.m_members.indexable_getter();
1762 dst.m_members.equal_to() = src.m_members.equal_to();
1763 dst.m_members.parameters() = src.m_members.parameters();
1766 // TODO use subtree_destroyer
1767 if ( dst.m_members.root )
1769 detail::rtree::visitors::destroy<members_holder>
1770 ::apply(dst.m_members.root, dst.m_members.allocators());
1772 dst.m_members.root = 0;
1775 dst.m_members.root = copy_v.result;
1776 dst.m_members.values_count = src.m_members.values_count;
1777 dst.m_members.leafs_level = src.m_members.leafs_level;
1781 \brief Insert a value corresponding to convertible object into the index.
1783 \param val_conv The object convertible to value.
1785 \par Exception-safety
1788 template <typename ValueConvertible>
1789 inline void insert_dispatch(ValueConvertible const& val_conv,
1790 std::true_type /*is_convertible*/)
1792 this->raw_insert(val_conv);
1796 \brief Insert a range of values into the index.
1798 \param rng The range of values.
1800 \par Exception-safety
1803 template <typename Range>
1804 inline void insert_dispatch(Range const& rng,
1805 std::false_type /*is_convertible*/)
1807 typedef typename boost::range_const_iterator<Range>::type It;
1808 for ( It it = boost::const_begin(rng); it != boost::const_end(rng) ; ++it )
1809 this->raw_insert(*it);
1813 \brief Remove a value corresponding to convertible object from the index.
1815 \param val_conv The object convertible to value.
1817 \par Exception-safety
1820 template <typename ValueConvertible>
1821 inline size_type remove_dispatch(ValueConvertible const& val_conv,
1822 std::true_type /*is_convertible*/)
1824 return this->raw_remove(val_conv);
1828 \brief Remove a range of values from the index.
1830 \param rng The range of values which will be removed from the container.
1832 \par Exception-safety
1835 template <typename Range>
1836 inline size_type remove_dispatch(Range const& rng,
1837 std::false_type /*is_convertible*/)
1839 size_type result = 0;
1840 typedef typename boost::range_const_iterator<Range>::type It;
1841 for ( It it = boost::const_begin(rng); it != boost::const_end(rng) ; ++it )
1842 result += this->raw_remove(*it);
1847 \brief Return values meeting predicates.
1849 \par Exception-safety
1854 typename Predicates, typename OutIter,
1855 std::enable_if_t<(detail::predicates_count_distance<Predicates>::value == 0), int> = 0
1857 size_type query_dispatch(Predicates const& predicates, OutIter out_it) const
1859 detail::rtree::visitors::spatial_query<members_holder, Predicates, OutIter>
1860 query(m_members, predicates, out_it);
1861 return query.apply(m_members);
1865 \brief Perform nearest neighbour search.
1867 \par Exception-safety
1872 typename Predicates, typename OutIter,
1873 std::enable_if_t<(detail::predicates_count_distance<Predicates>::value > 0), int> = 0
1875 size_type query_dispatch(Predicates const& predicates, OutIter out_it) const
1877 BOOST_GEOMETRY_STATIC_ASSERT((detail::predicates_count_distance<Predicates>::value == 1),
1878 "Only one distance predicate can be passed.",
1881 detail::rtree::visitors::distance_query<members_holder, Predicates>
1882 distance_v(m_members, predicates);
1884 return distance_v.apply(m_members, out_it);
1888 \brief Count elements corresponding to value or indexable.
1890 \par Exception-safety
1893 template <typename ValueOrIndexable>
1894 size_type raw_count(ValueOrIndexable const& vori) const
1896 BOOST_GEOMETRY_INDEX_ASSERT(m_members.root, "The root must exist");
1898 detail::rtree::visitors::count
1902 > count_v(vori, m_members.parameters(), m_members.translator());
1904 detail::rtree::apply_visitor(count_v, *m_members.root);
1906 return count_v.found_count;
1910 \brief The constructor TODO.
1912 The tree is created using packing algorithm.
1914 \param first The beginning of the range of Values.
1915 \param last The end of the range of Values.
1916 \param temp_allocator The temporary allocator object to be used by the packing algorithm.
1919 \li If allocator copy constructor throws.
1920 \li If Value copy constructor or copy assignment throws.
1921 \li If allocation throws or returns invalid value.
1923 template<typename Iterator, typename PackAlloc>
1924 inline void pack_construct(Iterator first, Iterator last, PackAlloc const& temp_allocator)
1926 typedef detail::rtree::pack<members_holder> pack;
1927 size_type vc = 0, ll = 0;
1928 m_members.root = pack::apply(first, last, vc, ll,
1929 m_members.parameters(), m_members.translator(),
1930 m_members.allocators(), temp_allocator);
1931 m_members.values_count = vc;
1932 m_members.leafs_level = ll;
1935 members_holder m_members;
1939 \brief Insert a value to the index.
1941 It calls <tt>rtree::insert(value_type const&)</tt>.
1943 \ingroup rtree_functions
1945 \param tree The spatial index.
1946 \param v The value which will be stored in the index.
1948 template <typename Value, typename Parameters, typename IndexableGetter, typename EqualTo, typename Allocator>
1949 inline void insert(rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator> & tree,
1956 \brief Insert a range of values to the index.
1958 It calls <tt>rtree::insert(Iterator, Iterator)</tt>.
1960 \ingroup rtree_functions
1962 \param tree The spatial index.
1963 \param first The beginning of the range of values.
1964 \param last The end of the range of values.
1966 template<typename Value, typename Parameters, typename IndexableGetter, typename EqualTo, typename Allocator,
1968 inline void insert(rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator> & tree,
1969 Iterator first, Iterator last)
1971 tree.insert(first, last);
1975 \brief Insert a value created using convertible object or a range of values to the index.
1977 It calls <tt>rtree::insert(ConvertibleOrRange const&)</tt>.
1979 \ingroup rtree_functions
1981 \param tree The spatial index.
1982 \param conv_or_rng The object of type convertible to value_type or a range of values.
1984 template<typename Value, typename Parameters, typename IndexableGetter, typename EqualTo, typename Allocator,
1985 typename ConvertibleOrRange>
1986 inline void insert(rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator> & tree,
1987 ConvertibleOrRange const& conv_or_rng)
1989 tree.insert(conv_or_rng);
1993 \brief Remove a value from the container.
1995 Remove a value from the container. In contrast to the \c std::set or <tt>std::map erase()</tt> method
1996 this function removes only one value from the container.
1998 It calls <tt>rtree::remove(value_type const&)</tt>.
2000 \ingroup rtree_functions
2002 \param tree The spatial index.
2003 \param v The value which will be removed from the index.
2005 \return 1 if value was removed, 0 otherwise.
2007 template <typename Value, typename Parameters, typename IndexableGetter, typename EqualTo, typename Allocator>
2008 inline typename rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator>::size_type
2009 remove(rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator> & tree,
2012 return tree.remove(v);
2016 \brief Remove a range of values from the container.
2018 Remove a range of values from the container. In contrast to the \c std::set or <tt>std::map erase()</tt> method
2019 it doesn't take iterators pointing to values stored in this container. It removes values equal
2020 to these passed as a range. Furthermore this function removes only one value for each one passed
2021 in the range, not all equal values.
2023 It calls <tt>rtree::remove(Iterator, Iterator)</tt>.
2025 \ingroup rtree_functions
2027 \param tree The spatial index.
2028 \param first The beginning of the range of values.
2029 \param last The end of the range of values.
2031 \return The number of removed values.
2033 template<typename Value, typename Parameters, typename IndexableGetter, typename EqualTo, typename Allocator,
2035 inline typename rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator>::size_type
2036 remove(rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator> & tree,
2037 Iterator first, Iterator last)
2039 return tree.remove(first, last);
2043 \brief Remove a value corresponding to an object convertible to it or a range of values from the container.
2045 Remove a value corresponding to an object convertible to it or a range of values from the container.
2046 In contrast to the \c std::set or <tt>std::map erase()</tt> method
2047 it removes values equal to these passed as a range. Furthermore this method removes only
2048 one value for each one passed in the range, not all equal values.
2050 It calls <tt>rtree::remove(ConvertibleOrRange const&)</tt>.
2052 \ingroup rtree_functions
2054 \param tree The spatial index.
2055 \param conv_or_rng The object of type convertible to value_type or the range of values.
2057 \return The number of removed values.
2059 template<typename Value, typename Parameters, typename IndexableGetter, typename EqualTo, typename Allocator,
2060 typename ConvertibleOrRange>
2061 inline typename rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator>::size_type
2062 remove(rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator> & tree,
2063 ConvertibleOrRange const& conv_or_rng)
2065 return tree.remove(conv_or_rng);
2069 \brief Finds values meeting passed predicates e.g. nearest to some Point and/or intersecting some Box.
2071 This query function performs spatial and k-nearest neighbor searches. It allows to pass a set of predicates.
2072 Values will be returned only if all predicates are met.
2074 <b>Spatial predicates</b>
2076 Spatial predicates may be generated by one of the functions listed below:
2077 \li \c boost::geometry::index::contains(),
2078 \li \c boost::geometry::index::covered_by(),
2079 \li \c boost::geometry::index::covers(),
2080 \li \c boost::geometry::index::disjoint(),
2081 \li \c boost::geometry::index::intersects(),
2082 \li \c boost::geometry::index::overlaps(),
2083 \li \c boost::geometry::index::within(),
2085 It is possible to negate spatial predicates:
2086 \li <tt>! boost::geometry::index::contains()</tt>,
2087 \li <tt>! boost::geometry::index::covered_by()</tt>,
2088 \li <tt>! boost::geometry::index::covers()</tt>,
2089 \li <tt>! boost::geometry::index::disjoint()</tt>,
2090 \li <tt>! boost::geometry::index::intersects()</tt>,
2091 \li <tt>! boost::geometry::index::overlaps()</tt>,
2092 \li <tt>! boost::geometry::index::within()</tt>
2094 <b>Satisfies predicate</b>
2096 This is a special kind of predicate which allows to pass a user-defined function or function object which checks
2097 if Value should be returned by the query. It's generated by:
2098 \li \c boost::geometry::index::satisfies().
2100 <b>Nearest predicate</b>
2102 If the nearest predicate is passed a k-nearest neighbor search will be performed. This query will result
2103 in returning k values to the output iterator. Only one nearest predicate may be passed to the query.
2104 It may be generated by:
2105 \li \c boost::geometry::index::nearest().
2107 <b>Connecting predicates</b>
2109 Predicates may be passed together connected with \c operator&&().
2113 // return elements intersecting box
2114 bgi::query(tree, bgi::intersects(box), std::back_inserter(result));
2115 // return elements intersecting poly but not within box
2116 bgi::query(tree, bgi::intersects(poly) && !bgi::within(box), std::back_inserter(result));
2117 // return elements overlapping box and meeting my_fun value predicate
2118 bgi::query(tree, bgi::overlaps(box) && bgi::satisfies(my_fun), std::back_inserter(result));
2119 // return 5 elements nearest to pt and elements are intersecting box
2120 bgi::query(tree, bgi::nearest(pt, 5) && bgi::intersects(box), std::back_inserter(result));
2122 // For each found value do_something (it is a type of function object)
2123 tree.query(bgi::intersects(box),
2124 boost::make_function_output_iterator(do_something()));
2128 If Value copy constructor or copy assignment throws.
2131 Only one \c nearest() predicate may be passed to the query. Passing more of them results in compile-time error.
2133 \ingroup rtree_functions
2135 \param tree The rtree.
2136 \param predicates Predicates.
2137 \param out_it The output iterator, e.g. generated by std::back_inserter().
2139 \return The number of values found.
2141 template <typename Value, typename Parameters, typename IndexableGetter, typename EqualTo, typename Allocator,
2142 typename Predicates, typename OutIter> inline
2143 typename rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator>::size_type
2144 query(rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator> const& tree,
2145 Predicates const& predicates,
2148 return tree.query(predicates, out_it);
2152 \brief Returns the query iterator pointing at the begin of the query range.
2154 This method returns the iterator which may be used to perform iterative queries. For the information
2155 about the predicates which may be passed to this method see query().
2159 std::for_each(bgi::qbegin(tree, bgi::nearest(pt, 3)), bgi::qend(tree), do_something());
2162 \par Iterator category
2166 If predicates copy throws.
2167 If allocation throws.
2170 The modification of the rtree may invalidate the iterators.
2172 \ingroup rtree_functions
2174 \param tree The rtree.
2175 \param predicates Predicates.
2177 \return The iterator pointing at the begin of the query range.
2179 template <typename Value, typename Parameters, typename IndexableGetter, typename EqualTo, typename Allocator,
2180 typename Predicates> inline
2181 typename rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator>::const_query_iterator
2182 qbegin(rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator> const& tree,
2183 Predicates const& predicates)
2185 return tree.qbegin(predicates);
2189 \brief Returns the query iterator pointing at the end of the query range.
2191 This method returns the iterator which may be used to check if the query has ended.
2195 std::for_each(bgi::qbegin(tree, bgi::nearest(pt, 3)), bgi::qend(tree), do_something());
2198 \par Iterator category
2205 The modification of the rtree may invalidate the iterators.
2207 \ingroup rtree_functions
2209 \return The iterator pointing at the end of the query range.
2211 template <typename Value, typename Parameters, typename IndexableGetter, typename EqualTo, typename Allocator> inline
2212 typename rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator>::const_query_iterator
2213 qend(rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator> const& tree)
2219 \brief Returns the iterator pointing at the begin of the rtree values range.
2221 This method returns the iterator which may be used to iterate over all values
2222 stored in the rtree.
2226 std::for_each(bgi::begin(tree), bgi::end(tree), do_something());
2228 std::for_each(boost::begin(tree), boost::end(tree), do_something());
2231 \par Iterator category
2235 If allocation throws.
2238 The modification of the rtree may invalidate the iterators.
2240 \ingroup rtree_functions
2242 \return The iterator pointing at the begin of the range.
2244 template <typename Value, typename Parameters, typename IndexableGetter, typename EqualTo, typename Allocator> inline
2245 typename rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator>::const_iterator
2246 begin(rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator> const& tree)
2248 return tree.begin();
2252 \brief Returns the iterator pointing at the end of the rtree values range.
2254 This method returns the iterator which may be compared with the iterator returned by begin()
2255 in order to check if the iteration has ended.
2259 std::for_each(bgi::begin(tree), bgi::end(tree), do_something());
2261 std::for_each(boost::begin(tree), boost::end(tree), do_something());
2264 \par Iterator category
2271 The modification of the rtree may invalidate the iterators.
2273 \ingroup rtree_functions
2275 \return The iterator pointing at the end of the range.
2277 template <typename Value, typename Parameters, typename IndexableGetter, typename EqualTo, typename Allocator> inline
2278 typename rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator>::const_iterator
2279 end(rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator> const& tree)
2285 \brief Remove all values from the index.
2287 It calls \c rtree::clear().
2289 \ingroup rtree_functions
2291 \param tree The spatial index.
2293 template <typename Value, typename Parameters, typename IndexableGetter, typename EqualTo, typename Allocator>
2294 inline void clear(rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator> & tree)
2296 return tree.clear();
2300 \brief Get the number of values stored in the index.
2302 It calls \c rtree::size().
2304 \ingroup rtree_functions
2306 \param tree The spatial index.
2308 \return The number of values stored in the index.
2310 template <typename Value, typename Parameters, typename IndexableGetter, typename EqualTo, typename Allocator>
2311 inline size_t size(rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator> const& tree)
2317 \brief Query if there are no values stored in the index.
2319 It calls \c rtree::empty().
2321 \ingroup rtree_functions
2323 \param tree The spatial index.
2325 \return true if there are no values in the index.
2327 template <typename Value, typename Parameters, typename IndexableGetter, typename EqualTo, typename Allocator>
2328 inline bool empty(rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator> const& tree)
2330 return tree.bounds();
2334 \brief Get the box containing all stored values or an invalid box if the index has no values.
2336 It calls \c rtree::envelope().
2338 \ingroup rtree_functions
2340 \param tree The spatial index.
2342 \return The box containing all stored values or an invalid box.
2344 template <typename Value, typename Parameters, typename IndexableGetter, typename EqualTo, typename Allocator>
2345 inline typename rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator>::bounds_type
2346 bounds(rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator> const& tree)
2348 return tree.bounds();
2352 \brief Exchanges the contents of the container with those of other.
2354 It calls \c rtree::swap().
2356 \ingroup rtree_functions
2358 \param l The first rtree.
2359 \param r The second rtree.
2361 template <typename Value, typename Parameters, typename IndexableGetter, typename EqualTo, typename Allocator>
2362 inline void swap(rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator> & l,
2363 rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator> & r)
2368 }}} // namespace boost::geometry::index
2370 // Boost.Range adaptation
2373 template <typename Value, typename Parameters, typename IndexableGetter, typename EqualTo, typename Allocator>
2374 struct range_mutable_iterator
2376 boost::geometry::index::rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator>
2379 typedef typename boost::geometry::index::rtree
2381 Value, Parameters, IndexableGetter, EqualTo, Allocator
2382 >::const_iterator type;
2385 } // namespace boost
2387 #include <boost/geometry/index/detail/config_end.hpp>
2389 #endif // BOOST_GEOMETRY_INDEX_RTREE_HPP