1 // Boost.Geometry Index
3 // R-tree implementation
5 // Copyright (c) 2008 Federico J. Fernandez.
6 // Copyright (c) 2011-2015 Adam Wulkiewicz, Lodz, Poland.
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)
12 #ifndef BOOST_GEOMETRY_INDEX_RTREE_HPP
13 #define BOOST_GEOMETRY_INDEX_RTREE_HPP
19 #include <boost/tuple/tuple.hpp>
20 #include <boost/move/move.hpp>
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>
33 #include <boost/geometry/geometries/point.hpp>
34 #include <boost/geometry/geometries/box.hpp>
36 #include <boost/geometry/strategies/strategies.hpp>
38 // Boost.Geometry.Index
39 #include <boost/geometry/index/detail/config_begin.hpp>
41 #include <boost/geometry/index/detail/assert.hpp>
42 #include <boost/geometry/index/detail/exception.hpp>
44 #include <boost/geometry/index/detail/rtree/options.hpp>
46 #include <boost/geometry/index/indexable.hpp>
47 #include <boost/geometry/index/equal_to.hpp>
49 #include <boost/geometry/index/detail/translator.hpp>
51 #include <boost/geometry/index/predicates.hpp>
52 #include <boost/geometry/index/distance_predicates.hpp>
53 #include <boost/geometry/index/detail/rtree/adaptors.hpp>
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>
59 #include <boost/geometry/index/detail/algorithms/is_valid.hpp>
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>
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>
76 #include <boost/geometry/index/detail/rtree/pack_create.hpp>
78 #include <boost/geometry/index/inserter.hpp>
80 #include <boost/geometry/index/detail/rtree/utilities/view.hpp>
82 #include <boost/geometry/index/detail/rtree/iterators.hpp>
83 #include <boost/geometry/index/detail/rtree/query_iterators.hpp>
85 #ifdef BOOST_GEOMETRY_INDEX_DETAIL_EXPERIMENTAL
87 #include <boost/geometry/index/detail/serialization.hpp>
90 // TODO change the name to bounding_tree
93 \defgroup rtree_functions R-tree free functions (boost::geometry::index::)
96 namespace boost { namespace geometry { namespace index {
99 \brief The R-tree spatial index.
101 This is self-balancing spatial index capable to store various types of Values
102 and balancing algorithms.
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.
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>.
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.
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>.
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.
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.
151 typename IndexableGetter = index::indexable<Value>,
152 typename EqualTo = index::equal_to<Value>,
153 typename Allocator = std::allocator<Value>
157 BOOST_COPYABLE_AND_MOVABLE(rtree)
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;
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;
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
189 typedef detail::translator<IndexableGetter, EqualTo> translator_type;
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;
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;
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;
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>;
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;
225 /*! \brief Type of const iterator, category ForwardIterator. */
226 typedef index::detail::rtree::iterators::iterator
228 value_type, options_type, translator_type, box_type, allocators_type
231 /*! \brief Type of const query iterator, category ForwardIterator. */
232 typedef index::detail::rtree::iterators::query_iterator
234 value_type, allocators_type
235 > const_query_iterator;
240 \brief The constructor.
242 \param parameters The parameters object.
243 \param getter The function object extracting Indexable from Value.
244 \param equal The function object comparing Values.
247 If allocator default constructor throws.
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)
256 \brief The constructor.
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.
264 If allocator copy constructor throws.
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)
274 \brief The constructor.
276 The tree is created using packing algorithm.
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.
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.
290 template<typename Iterator>
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)
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;
307 \brief The constructor.
309 The tree is created using packing algorithm.
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.
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.
322 template<typename Range>
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)
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;
339 \brief The destructor.
346 this->raw_destroy(*this);
350 \brief The copy constructor.
352 It uses parameters, translator and allocator from the source tree.
354 \param src The rtree which content will be copied.
357 \li If allocator copy constructor throws.
358 \li If Value copy constructor throws.
359 \li If allocation throws or returns invalid value.
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()))
367 this->raw_copy(src, *this, false);
371 \brief The copy constructor.
373 It uses Parameters and translator from the source tree.
375 \param src The rtree which content will be copied.
376 \param allocator The allocator which will be used.
379 \li If allocator copy constructor throws.
380 \li If Value copy constructor throws.
381 \li If allocation throws or returns invalid value.
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)
388 this->raw_copy(src, *this, false);
392 \brief The moving constructor.
394 It uses parameters, translator and allocator from the source tree.
396 \param src The rtree which content will be moved.
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()))
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);
413 \brief The moving constructor.
415 It uses parameters and translator from the source tree.
417 \param src The rtree which content will be moved.
418 \param allocator The allocator.
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).
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(),
431 if ( src.m_members.allocators() == allocator )
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);
439 this->raw_copy(src, *this, false);
444 \brief The assignment operator.
446 It uses parameters and translator from the source tree.
448 \param src The rtree which content will be copied.
451 \li If Value copy constructor throws.
452 \li If allocation throws.
453 \li If allocation throws or returns invalid value.
455 inline rtree & operator=(BOOST_COPY_ASSIGN_REF(rtree) src)
459 allocators_type & this_allocs = m_members.allocators();
460 allocators_type const& src_allocs = src.m_members.allocators();
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
466 typedef boost::mpl::bool_<
467 allocator_traits_type::propagate_on_container_copy_assignment::value
470 if ( propagate::value && !(this_allocs == src_allocs) )
471 this->raw_destroy(*this);
472 detail::assign_cond(this_allocs, src_allocs, propagate());
474 // It uses m_allocators
475 this->raw_copy(src, *this, true);
482 \brief The moving assignment.
484 It uses parameters and translator from the source tree.
486 \param src The rtree which content will be moved.
489 Only if allocators aren't equal.
490 \li If Value copy constructor throws.
491 \li If allocation throws or returns invalid value.
493 inline rtree & operator=(BOOST_RV_REF(rtree) src)
497 allocators_type & this_allocs = m_members.allocators();
498 allocators_type & src_allocs = src.m_members.allocators();
500 if ( this_allocs == src_allocs )
502 this->raw_destroy(*this);
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();
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);
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
516 typedef boost::mpl::bool_<
517 allocator_traits_type::propagate_on_container_move_assignment::value
519 detail::move_cond(this_allocs, src_allocs, propagate());
523 // TODO - shouldn't here propagate_on_container_copy_assignment be checked like in operator=(const&)?
525 // It uses m_allocators
526 this->raw_copy(src, *this, true);
534 \brief Swaps contents of two rtrees.
536 Parameters, translator and allocators are swapped as well.
538 \param other The rtree which content will be swapped with this rtree content.
541 If allocators swap throws.
543 void swap(rtree & other)
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());
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
553 typedef boost::mpl::bool_<
554 allocator_traits_type::propagate_on_container_swap::value
556 detail::swap_cond(m_members.allocators(), other.m_members.allocators(), propagate());
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);
564 \brief Insert a value to the index.
566 \param value The value which will be stored in the container.
569 \li If Value copy constructor or copy assignment throws.
570 \li If allocation throws or returns invalid value.
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.
578 inline void insert(value_type const& value)
580 if ( !m_members.root )
583 this->raw_insert(value);
587 \brief Insert a range of values to the index.
589 \param first The beginning of the range of values.
590 \param last The end of the range of values.
593 \li If Value copy constructor or copy assignment throws.
594 \li If allocation throws or returns invalid value.
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.
602 template <typename Iterator>
603 inline void insert(Iterator first, Iterator last)
605 if ( !m_members.root )
608 for ( ; first != last ; ++first )
609 this->raw_insert(*first);
613 \brief Insert a value created using convertible object or a range of values to the index.
615 \param conv_or_rng An object of type convertible to value_type or a range of values.
618 \li If Value copy constructor or copy assignment throws.
619 \li If allocation throws or returns invalid value.
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.
627 template <typename ConvertibleOrRange>
628 inline void insert(ConvertibleOrRange const& conv_or_rng)
630 if ( !m_members.root )
633 typedef boost::mpl::bool_
635 boost::is_convertible<ConvertibleOrRange, value_type>::value
638 this->insert_dispatch(conv_or_rng, is_conv_t());
642 \brief Remove a value from the container.
644 In contrast to the \c std::set or <tt>std::map erase()</tt> method
645 this method removes only one value from the container.
647 \param value The value which will be removed from the container.
649 \return 1 if the value was removed, 0 otherwise.
652 \li If Value copy constructor or copy assignment throws.
653 \li If allocation throws or returns invalid value.
656 This operation only guarantees that there will be no memory leaks.
657 After an exception is thrown the R-tree may be left in an inconsistent state,
658 elements must not be inserted or removed. Other operations are allowed however
659 some of them may return invalid data.
661 inline size_type remove(value_type const& value)
663 if ( !m_members.root )
666 return this->raw_remove(value);
670 \brief Remove a range of values from the container.
672 In contrast to the \c std::set or <tt>std::map erase()</tt> method
673 it doesn't take iterators pointing to values stored in this container. It removes values equal
674 to these passed as a range. Furthermore this method removes only one value for each one passed
675 in the range, not all equal values.
677 \param first The beginning of the range of values.
678 \param last The end of the range of values.
680 \return The number of removed values.
683 \li If Value copy constructor or copy assignment throws.
684 \li If allocation throws or returns invalid value.
687 This operation only guarantees that there will be no memory leaks.
688 After an exception is thrown the R-tree may be left in an inconsistent state,
689 elements must not be inserted or removed. Other operations are allowed however
690 some of them may return invalid data.
692 template <typename Iterator>
693 inline size_type remove(Iterator first, Iterator last)
695 size_type result = 0;
697 if ( !m_members.root )
700 for ( ; first != last ; ++first )
701 result += this->raw_remove(*first);
706 \brief Remove value corresponding to an object convertible to it or a range of values from the container.
708 In contrast to the \c std::set or <tt>std::map erase()</tt> method
709 it removes values equal to these passed as a range. Furthermore, this method removes only
710 one value for each one passed in the range, not all equal values.
712 \param conv_or_rng The object of type convertible to value_type or a range of values.
714 \return The number of removed values.
717 \li If Value copy constructor or copy assignment throws.
718 \li If allocation throws or returns invalid value.
721 This operation only guarantees that there will be no memory leaks.
722 After an exception is thrown the R-tree may be left in an inconsistent state,
723 elements must not be inserted or removed. Other operations are allowed however
724 some of them may return invalid data.
726 template <typename ConvertibleOrRange>
727 inline size_type remove(ConvertibleOrRange const& conv_or_rng)
729 if ( !m_members.root )
732 typedef boost::mpl::bool_
734 boost::is_convertible<ConvertibleOrRange, value_type>::value
737 return this->remove_dispatch(conv_or_rng, is_conv_t());
741 \brief Finds values meeting passed predicates e.g. nearest to some Point and/or intersecting some Box.
743 This query function performs spatial and k-nearest neighbor searches. It allows to pass a set of predicates.
744 Values will be returned only if all predicates are met.
746 <b>Spatial predicates</b>
748 Spatial predicates may be generated by one of the functions listed below:
749 \li \c boost::geometry::index::contains(),
750 \li \c boost::geometry::index::covered_by(),
751 \li \c boost::geometry::index::covers(),
752 \li \c boost::geometry::index::disjoint(),
753 \li \c boost::geometry::index::intersects(),
754 \li \c boost::geometry::index::overlaps(),
755 \li \c boost::geometry::index::within(),
757 It is possible to negate spatial predicates:
758 \li <tt>! boost::geometry::index::contains()</tt>,
759 \li <tt>! boost::geometry::index::covered_by()</tt>,
760 \li <tt>! boost::geometry::index::covers()</tt>,
761 \li <tt>! boost::geometry::index::disjoint()</tt>,
762 \li <tt>! boost::geometry::index::intersects()</tt>,
763 \li <tt>! boost::geometry::index::overlaps()</tt>,
764 \li <tt>! boost::geometry::index::within()</tt>
766 <b>Satisfies predicate</b>
768 This is a special kind of predicate which allows to pass a user-defined function or function object which checks
769 if Value should be returned by the query. It's generated by:
770 \li \c boost::geometry::index::satisfies().
772 <b>Nearest predicate</b>
774 If the nearest predicate is passed a k-nearest neighbor search will be performed. This query will result
775 in returning k values to the output iterator. Only one nearest predicate may be passed to the query.
776 It may be generated by:
777 \li \c boost::geometry::index::nearest().
779 <b>Connecting predicates</b>
781 Predicates may be passed together connected with \c operator&&().
785 // return elements intersecting box
786 tree.query(bgi::intersects(box), std::back_inserter(result));
787 // return elements intersecting poly but not within box
788 tree.query(bgi::intersects(poly) && !bgi::within(box), std::back_inserter(result));
789 // return elements overlapping box and meeting my_fun unary predicate
790 tree.query(bgi::overlaps(box) && bgi::satisfies(my_fun), std::back_inserter(result));
791 // return 5 elements nearest to pt and elements are intersecting box
792 tree.query(bgi::nearest(pt, 5) && bgi::intersects(box), std::back_inserter(result));
794 // For each found value do_something (it is a type of function object)
795 tree.query(bgi::intersects(box),
796 boost::make_function_output_iterator(do_something()));
798 // For each value stored in the rtree do_something
799 // always_true is a type of function object always returning true
800 tree.query(bgi::satisfies(always_true()),
801 boost::make_function_output_iterator(do_something()));
803 // C++11 (lambda expression)
804 tree.query(bgi::intersects(box),
805 boost::make_function_output_iterator([](value_type const& val){
809 // C++14 (generic lambda expression)
810 tree.query(bgi::intersects(box),
811 boost::make_function_output_iterator([](auto const& val){
817 If Value copy constructor or copy assignment throws.
818 If predicates copy throws.
821 Only one \c nearest() perdicate may be passed to the query. Passing more of them results in compile-time error.
823 \param predicates Predicates.
824 \param out_it The output iterator, e.g. generated by std::back_inserter().
826 \return The number of values found.
828 template <typename Predicates, typename OutIter>
829 size_type query(Predicates const& predicates, OutIter out_it) const
831 if ( !m_members.root )
834 static const unsigned distance_predicates_count = detail::predicates_count_distance<Predicates>::value;
835 static const bool is_distance_predicate = 0 < distance_predicates_count;
836 BOOST_MPL_ASSERT_MSG((distance_predicates_count <= 1), PASS_ONLY_ONE_DISTANCE_PREDICATE, (Predicates));
838 return query_dispatch(predicates, out_it, boost::mpl::bool_<is_distance_predicate>());
842 \brief Returns a query iterator pointing at the begin of the query range.
844 This method returns an iterator which may be used to perform iterative queries.
845 For the information about predicates which may be passed to this method see query().
849 for ( Rtree::const_query_iterator it = tree.qbegin(bgi::nearest(pt, 10000)) ;
850 it != tree.qend() ; ++it )
852 // do something with value
853 if ( has_enough_nearest_values() )
858 for ( auto it = tree.qbegin(bgi::nearest(pt, 3)) ; it != tree.qend() ; ++it )
860 // do something with value
863 // C++14 (generic lambda expression)
864 std::for_each(tree.qbegin(bgi::nearest(pt, 3)), tree.qend(), [](auto const& val){
865 // do something with value
869 \par Iterator category
873 If predicates copy throws.
874 If allocation throws.
877 The modification of the rtree may invalidate the iterators.
879 \param predicates Predicates.
881 \return The iterator pointing at the begin of the query range.
883 template <typename Predicates>
884 const_query_iterator qbegin(Predicates const& predicates) const
886 return const_query_iterator(qbegin_(predicates));
890 \brief Returns a query iterator pointing at the end of the query range.
892 This method returns an iterator which may be used to check if the query has ended.
896 for ( Rtree::const_query_iterator it = tree.qbegin(bgi::nearest(pt, 10000)) ;
897 it != tree.qend() ; ++it )
899 // do something with value
900 if ( has_enough_nearest_values() )
905 for ( auto it = tree.qbegin(bgi::nearest(pt, 3)) ; it != tree.qend() ; ++it )
907 // do something with value
910 // C++14 (generic lambda expression)
911 std::for_each(tree.qbegin(bgi::nearest(pt, 3)), tree.qend(), [](auto const& val){
912 // do something with value
916 \par Iterator category
923 The modification of the rtree may invalidate the iterators.
925 \return The iterator pointing at the end of the query range.
927 const_query_iterator qend() const
929 return const_query_iterator();
932 #ifndef BOOST_GEOMETRY_INDEX_DETAIL_EXPERIMENTAL
936 \brief Returns a query iterator pointing at the begin of the query range.
938 This method returns an iterator which may be used to perform iterative queries.
939 For the information about predicates which may be passed to this method see query().
941 The type of the returned iterator depends on the type of passed Predicates but the iterator of this type
942 may be assigned to the variable of const_query_iterator type. If you'd like to use the type of the iterator
943 returned by this method you may get the type e.g. by using C++11 decltype or Boost.Typeof library.
944 This iterator may be compared with iterators returned by both versions of qend() method.
948 // Store the result in the container using std::copy() - it requires both iterators of the same type
949 std::copy(tree.qbegin_(bgi::intersects(box)), tree.qend_(bgi::intersects(box)), std::back_inserter(result));
951 // Store the result in the container using std::copy() and type-erased iterators
952 Rtree::const_query_iterator first = tree.qbegin_(bgi::intersects(box));
953 Rtree::const_query_iterator last = tree.qend_();
954 std::copy(first, last, std::back_inserter(result));
957 typedef BOOST_TYPEOF(tree.qbegin(bgi::nearest(pt, 10000))) Iter;
958 for ( Iter it = tree.qbegin_(bgi::nearest(pt, 10000)) ; it != tree.qend_() ; ++it )
960 // do something with value
961 if ( has_enough_nearest_values() )
966 for ( auto it = tree.qbegin_(bgi::nearest(pt, 10000)) ; it != tree.qend_() ; ++it )
968 // do something with value
969 if ( has_enough_nearest_values() )
974 \par Iterator category
978 If predicates copy throws.
979 If allocation throws.
982 The modification of the rtree may invalidate the iterators.
984 \param predicates Predicates.
986 \return The iterator pointing at the begin of the query range.
988 template <typename Predicates>
989 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
997 qbegin_(Predicates const& predicates) const
999 static const unsigned distance_predicates_count = detail::predicates_count_distance<Predicates>::value;
1000 BOOST_MPL_ASSERT_MSG((distance_predicates_count <= 1), PASS_ONLY_ONE_DISTANCE_PREDICATE, (Predicates));
1002 typedef typename boost::mpl::if_c<
1003 detail::predicates_count_distance<Predicates>::value == 0,
1004 detail::rtree::iterators::spatial_query_iterator<value_type, options_type, translator_type, box_type, allocators_type, Predicates>,
1005 detail::rtree::iterators::distance_query_iterator<
1006 value_type, options_type, translator_type, box_type, allocators_type, Predicates,
1007 detail::predicates_find_distance<Predicates>::value
1009 >::type iterator_type;
1011 if ( !m_members.root )
1012 return iterator_type(m_members.translator(), predicates);
1014 return iterator_type(m_members.root, m_members.translator(), predicates);
1018 \brief Returns the query iterator pointing at the end of the query range.
1020 This method returns the iterator which may be used to perform iterative queries. For the information
1021 about the predicates which may be passed to this method see query().
1023 The type of the returned iterator depends on the type of passed Predicates but the iterator of this type
1024 may be assigned to the variable of const_query_iterator type. If you'd like to use the type of the iterator
1025 returned by this method you may get the type e.g. by using C++11 decltype or Boost.Typeof library.
1027 The type of the iterator returned by this method is the same as the one returned by qbegin() to which
1028 the same predicates were passed.
1032 // Store the result in the container using std::copy() - it requires both iterators of the same type
1033 std::copy(tree.qbegin_(bgi::intersects(box)), tree.qend_(bgi::intersects(box)), std::back_inserter(result));
1036 \par Iterator category
1040 If predicates copy throws.
1043 The modification of the rtree may invalidate the iterators.
1045 \param predicates Predicates.
1047 \return The iterator pointing at the end of the query range.
1049 template <typename Predicates>
1050 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
1058 qend_(Predicates const& predicates) const
1060 static const unsigned distance_predicates_count = detail::predicates_count_distance<Predicates>::value;
1061 BOOST_MPL_ASSERT_MSG((distance_predicates_count <= 1), PASS_ONLY_ONE_DISTANCE_PREDICATE, (Predicates));
1063 typedef typename boost::mpl::if_c<
1064 detail::predicates_count_distance<Predicates>::value == 0,
1065 detail::rtree::iterators::spatial_query_iterator<value_type, options_type, translator_type, box_type, allocators_type, Predicates>,
1066 detail::rtree::iterators::distance_query_iterator<
1067 value_type, options_type, translator_type, box_type, allocators_type, Predicates,
1068 detail::predicates_find_distance<Predicates>::value
1070 >::type iterator_type;
1072 return iterator_type(m_members.translator(), predicates);
1076 \brief Returns the query iterator pointing at the end of the query range.
1078 This method returns the iterator which may be compared with the iterator returned by qbegin() in order to
1079 check if the query has ended.
1081 The type of the returned iterator is different than the type returned by qbegin() but the iterator of this type
1082 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
1083 method, which most certainly will be faster than the type-erased iterator, you may get the type
1084 e.g. by using C++11 decltype or Boost.Typeof library.
1086 The type of the iterator returned by this method is dfferent than the type returned by qbegin().
1090 // Store the result in the container using std::copy() and type-erased iterators
1091 Rtree::const_query_iterator first = tree.qbegin_(bgi::intersects(box));
1092 Rtree::const_query_iterator last = tree.qend_();
1093 std::copy(first, last, std::back_inserter(result));
1096 typedef BOOST_TYPEOF(tree.qbegin(bgi::nearest(pt, 10000))) Iter;
1097 for ( Iter it = tree.qbegin_(bgi::nearest(pt, 10000)) ; it != tree.qend_() ; ++it )
1099 // do something with value
1100 if ( has_enough_nearest_values() )
1105 for ( auto it = tree.qbegin_(bgi::nearest(pt, 10000)) ; it != tree.qend_() ; ++it )
1107 // do something with value
1108 if ( has_enough_nearest_values() )
1113 \par Iterator category
1120 The modification of the rtree may invalidate the iterators.
1122 \return The iterator pointing at the end of the query range.
1124 detail::rtree::iterators::end_query_iterator<value_type, allocators_type>
1127 return detail::rtree::iterators::end_query_iterator<value_type, allocators_type>();
1133 \brief Returns the iterator pointing at the begin of the rtree values range.
1135 This method returns the iterator which may be used to iterate over all values
1136 stored in the rtree.
1140 // Copy all values into the vector
1141 std::copy(tree.begin(), tree.end(), std::back_inserter(vec));
1143 for ( Rtree::const_iterator it = tree.begin() ; it != tree.end() ; ++it )
1145 // do something with value
1149 for ( auto it = tree.begin() ; it != tree.end() ; ++it )
1151 // do something with value
1154 // C++14 (generic lambda expression)
1155 std::for_each(tree.begin(), tree.end(), [](auto const& val){
1156 // do something with value
1160 \par Iterator category
1164 If allocation throws.
1167 The modification of the rtree may invalidate the iterators.
1169 \return The iterator pointing at the begin of the range.
1171 const_iterator begin() const
1173 if ( !m_members.root )
1174 return const_iterator();
1176 return const_iterator(m_members.root);
1180 \brief Returns the iterator pointing at the end of the rtree values range.
1182 This method returns the iterator which may be compared with the iterator returned by begin()
1183 in order to check if the iteration has ended.
1187 for ( Rtree::const_iterator it = tree.begin() ; it != tree.end() ; ++it )
1189 // do something with value
1192 // C++11 (lambda expression)
1193 std::for_each(tree.begin(), tree.end(), [](value_type const& val){
1194 // do something with value
1198 \par Iterator category
1205 The modification of the rtree may invalidate the iterators.
1207 \return The iterator pointing at the end of the range.
1209 const_iterator end() const
1211 return const_iterator();
1215 \brief Returns the number of stored values.
1217 \return The number of stored values.
1222 inline size_type size() const
1224 return m_members.values_count;
1228 \brief Query if the container is empty.
1230 \return true if the container is empty.
1235 inline bool empty() const
1237 return 0 == m_members.values_count;
1241 \brief Removes all values stored in the container.
1248 this->raw_destroy(*this);
1252 \brief Returns the box able to contain all values stored in the container.
1254 Returns the box able to contain all values stored in the container.
1255 If the container is empty the result of \c geometry::assign_inverse() is returned.
1257 \return The box able to contain all values stored in the container or an invalid box if
1258 there are no values in the container.
1263 inline bounds_type bounds() const
1266 // in order to suppress the uninitialized variable warnings
1267 geometry::assign_inverse(result);
1269 if ( m_members.root )
1271 detail::rtree::visitors::children_box<value_type, options_type, translator_type, box_type, allocators_type>
1272 box_v(result, m_members.translator());
1273 detail::rtree::apply_visitor(box_v, *m_members.root);
1280 \brief Count Values or Indexables stored in the container.
1282 For indexable_type it returns the number of values which indexables equals the parameter.
1283 For value_type it returns the number of values which equals the parameter.
1285 \param vori The value or indexable which will be counted.
1287 \return The number of values found.
1292 template <typename ValueOrIndexable>
1293 size_type count(ValueOrIndexable const& vori) const
1295 if ( !m_members.root )
1298 // the input should be convertible to Value or Indexable type
1300 enum { as_val = 0, as_ind, dont_know };
1301 typedef boost::mpl::int_
1303 boost::is_same<ValueOrIndexable, value_type>::value ?
1305 boost::is_same<ValueOrIndexable, indexable_type>::value ?
1307 boost::is_convertible<ValueOrIndexable, indexable_type>::value ?
1309 boost::is_convertible<ValueOrIndexable, value_type>::value ?
1314 BOOST_MPL_ASSERT_MSG((variant::value != dont_know),
1315 PASSED_OBJECT_NOT_CONVERTIBLE_TO_VALUE_NOR_INDEXABLE_TYPE,
1316 (ValueOrIndexable));
1318 typedef typename boost::mpl::if_c
1320 variant::value == as_val,
1323 >::type value_or_indexable;
1325 // NOTE: If an object of convertible but not the same type is passed
1326 // into the function, here a temporary will be created.
1327 return this->template raw_count<value_or_indexable>(vori);
1331 \brief Returns parameters.
1333 \return The parameters object.
1338 inline parameters_type parameters() const
1340 return m_members.parameters();
1344 \brief Returns function retrieving Indexable from Value.
1346 \return The indexable_getter object.
1351 indexable_getter indexable_get() const
1353 return m_members.indexable_getter();
1357 \brief Returns function comparing Values
1359 \return The value_equal function.
1364 value_equal value_eq() const
1366 return m_members.equal_to();
1370 \brief Returns allocator used by the rtree.
1372 \return The allocator.
1375 If allocator copy constructor throws.
1377 allocator_type get_allocator() const
1379 return m_members.allocators().allocator();
1385 \brief Returns the translator object.
1387 \return The translator object.
1392 inline translator_type translator() const
1394 return m_members.translator();
1398 \brief Apply a visitor to the nodes structure in order to perform some operator.
1400 This function is not a part of the 'official' interface. However it makes
1401 possible e.g. to pass a visitor drawing the tree structure.
1403 \param visitor The visitor object.
1406 If Visitor::operator() throws.
1408 template <typename Visitor>
1409 inline void apply_visitor(Visitor & visitor) const
1411 if ( m_members.root )
1412 detail::rtree::apply_visitor(visitor, *m_members.root);
1416 \brief Returns the depth of the R-tree.
1418 This function is not a part of the 'official' interface.
1420 \return The depth of the R-tree.
1425 inline size_type depth() const
1427 return m_members.leafs_level;
1433 \pre Root node must exist - m_root != 0.
1435 \brief Insert a value to the index.
1437 \param value The value which will be stored in the container.
1439 \par Exception-safety
1442 inline void raw_insert(value_type const& value)
1444 BOOST_GEOMETRY_INDEX_ASSERT(m_members.root, "The root must exist");
1445 // CONSIDER: alternative - ignore invalid indexable or throw an exception
1446 BOOST_GEOMETRY_INDEX_ASSERT(detail::is_valid(m_members.translator()(value)), "Indexable is invalid");
1448 detail::rtree::visitors::insert<
1450 value_type, options_type, translator_type, box_type, allocators_type,
1451 typename options_type::insert_tag
1452 > insert_v(m_members.root, m_members.leafs_level, value,
1453 m_members.parameters(), m_members.translator(), m_members.allocators());
1455 detail::rtree::apply_visitor(insert_v, *m_members.root);
1458 // Think about this: If exception is thrown, may the root be removed?
1459 // Or it is just cleared?
1462 // If exception is thrown, m_values_count may be invalid
1463 ++m_members.values_count;
1467 \brief Remove the value from the container.
1469 \param value The value which will be removed from the container.
1471 \par Exception-safety
1474 inline size_type raw_remove(value_type const& value)
1476 // TODO: awulkiew - assert for correct value (indexable) ?
1477 BOOST_GEOMETRY_INDEX_ASSERT(m_members.root, "The root must exist");
1479 detail::rtree::visitors::remove<
1480 value_type, options_type, translator_type, box_type, allocators_type
1481 > remove_v(m_members.root, m_members.leafs_level, value,
1482 m_members.parameters(), m_members.translator(), m_members.allocators());
1484 detail::rtree::apply_visitor(remove_v, *m_members.root);
1486 // If exception is thrown, m_values_count may be invalid
1488 if ( remove_v.is_value_removed() )
1490 BOOST_GEOMETRY_INDEX_ASSERT(0 < m_members.values_count, "unexpected state");
1492 --m_members.values_count;
1501 \brief Create an empty R-tree i.e. new empty root node and clear other attributes.
1503 \par Exception-safety
1506 inline void raw_create()
1508 BOOST_GEOMETRY_INDEX_ASSERT(0 == m_members.root, "the tree is already created");
1510 m_members.root = detail::rtree::create_node<allocators_type, leaf>::apply(m_members.allocators()); // MAY THROW (N: alloc)
1511 m_members.values_count = 0;
1512 m_members.leafs_level = 0;
1516 \brief Destroy the R-tree i.e. all nodes and clear attributes.
1518 \param t The container which is going to be destroyed.
1520 \par Exception-safety
1523 inline void raw_destroy(rtree & t)
1525 if ( t.m_members.root )
1527 detail::rtree::visitors::destroy<value_type, options_type, translator_type, box_type, allocators_type>
1528 del_v(t.m_members.root, t.m_members.allocators());
1529 detail::rtree::apply_visitor(del_v, *t.m_members.root);
1531 t.m_members.root = 0;
1533 t.m_members.values_count = 0;
1534 t.m_members.leafs_level = 0;
1538 \brief Copy the R-tree i.e. whole nodes structure, values and other attributes.
1539 It uses destination's allocators to create the new structure.
1541 \param src The source R-tree.
1542 \param dst The destination R-tree.
1543 \param copy_tr_and_params If true, translator and parameters will also be copied.
1545 \par Exception-safety
1548 inline void raw_copy(rtree const& src, rtree & dst, bool copy_tr_and_params) const
1550 detail::rtree::visitors::copy<value_type, options_type, translator_type, box_type, allocators_type>
1551 copy_v(dst.m_members.allocators());
1553 if ( src.m_members.root )
1554 detail::rtree::apply_visitor(copy_v, *src.m_members.root); // MAY THROW (V, E: alloc, copy, N: alloc)
1556 if ( copy_tr_and_params )
1558 dst.m_members.indexable_getter() = src.m_members.indexable_getter();
1559 dst.m_members.equal_to() = src.m_members.equal_to();
1560 dst.m_members.parameters() = src.m_members.parameters();
1563 // TODO use subtree_destroyer
1564 if ( dst.m_members.root )
1566 detail::rtree::visitors::destroy<value_type, options_type, translator_type, box_type, allocators_type>
1567 del_v(dst.m_members.root, dst.m_members.allocators());
1568 detail::rtree::apply_visitor(del_v, *dst.m_members.root);
1569 dst.m_members.root = 0;
1572 dst.m_members.root = copy_v.result;
1573 dst.m_members.values_count = src.m_members.values_count;
1574 dst.m_members.leafs_level = src.m_members.leafs_level;
1578 \brief Insert a value corresponding to convertible object into the index.
1580 \param val_conv The object convertible to value.
1582 \par Exception-safety
1585 template <typename ValueConvertible>
1586 inline void insert_dispatch(ValueConvertible const& val_conv,
1587 boost::mpl::bool_<true> const& /*is_convertible*/)
1589 this->raw_insert(val_conv);
1593 \brief Insert a range of values into the index.
1595 \param rng The range of values.
1597 \par Exception-safety
1600 template <typename Range>
1601 inline void insert_dispatch(Range const& rng,
1602 boost::mpl::bool_<false> const& /*is_convertible*/)
1604 BOOST_MPL_ASSERT_MSG((detail::is_range<Range>::value),
1605 PASSED_OBJECT_IS_NOT_CONVERTIBLE_TO_VALUE_NOR_A_RANGE,
1608 typedef typename boost::range_const_iterator<Range>::type It;
1609 for ( It it = boost::const_begin(rng); it != boost::const_end(rng) ; ++it )
1610 this->raw_insert(*it);
1614 \brief Remove a value corresponding to convertible object from the index.
1616 \param val_conv The object convertible to value.
1618 \par Exception-safety
1621 template <typename ValueConvertible>
1622 inline size_type remove_dispatch(ValueConvertible const& val_conv,
1623 boost::mpl::bool_<true> const& /*is_convertible*/)
1625 return this->raw_remove(val_conv);
1629 \brief Remove a range of values from the index.
1631 \param rng The range of values which will be removed from the container.
1633 \par Exception-safety
1636 template <typename Range>
1637 inline size_type remove_dispatch(Range const& rng,
1638 boost::mpl::bool_<false> const& /*is_convertible*/)
1640 BOOST_MPL_ASSERT_MSG((detail::is_range<Range>::value),
1641 PASSED_OBJECT_IS_NOT_CONVERTIBLE_TO_VALUE_NOR_A_RANGE,
1644 size_type result = 0;
1645 typedef typename boost::range_const_iterator<Range>::type It;
1646 for ( It it = boost::const_begin(rng); it != boost::const_end(rng) ; ++it )
1647 result += this->raw_remove(*it);
1652 \brief Return values meeting predicates.
1654 \par Exception-safety
1657 template <typename Predicates, typename OutIter>
1658 size_type query_dispatch(Predicates const& predicates, OutIter out_it, boost::mpl::bool_<false> const& /*is_distance_predicate*/) const
1660 detail::rtree::visitors::spatial_query<value_type, options_type, translator_type, box_type, allocators_type, Predicates, OutIter>
1661 find_v(m_members.translator(), predicates, out_it);
1663 detail::rtree::apply_visitor(find_v, *m_members.root);
1665 return find_v.found_count;
1669 \brief Perform nearest neighbour search.
1671 \par Exception-safety
1674 template <typename Predicates, typename OutIter>
1675 size_type query_dispatch(Predicates const& predicates, OutIter out_it, boost::mpl::bool_<true> const& /*is_distance_predicate*/) const
1677 BOOST_GEOMETRY_INDEX_ASSERT(m_members.root, "The root must exist");
1679 static const unsigned distance_predicate_index = detail::predicates_find_distance<Predicates>::value;
1680 detail::rtree::visitors::distance_query<
1687 distance_predicate_index,
1689 > distance_v(m_members.parameters(), m_members.translator(), predicates, out_it);
1691 detail::rtree::apply_visitor(distance_v, *m_members.root);
1693 return distance_v.finish();
1697 \brief Count elements corresponding to value or indexable.
1699 \par Exception-safety
1702 template <typename ValueOrIndexable>
1703 size_type raw_count(ValueOrIndexable const& vori) const
1705 BOOST_GEOMETRY_INDEX_ASSERT(m_members.root, "The root must exist");
1707 detail::rtree::visitors::count
1715 > count_v(vori, m_members.translator());
1717 detail::rtree::apply_visitor(count_v, *m_members.root);
1719 return count_v.found_count;
1722 struct members_holder
1723 : public translator_type
1725 , public allocators_type
1728 members_holder(members_holder const&);
1729 members_holder & operator=(members_holder const&);
1732 template <typename IndGet, typename ValEq, typename Alloc>
1733 members_holder(IndGet const& ind_get,
1734 ValEq const& val_eq,
1735 Parameters const& parameters,
1736 BOOST_FWD_REF(Alloc) alloc)
1737 : translator_type(ind_get, val_eq)
1738 , Parameters(parameters)
1739 , allocators_type(boost::forward<Alloc>(alloc))
1745 template <typename IndGet, typename ValEq>
1746 members_holder(IndGet const& ind_get,
1747 ValEq const& val_eq,
1748 Parameters const& parameters)
1749 : translator_type(ind_get, val_eq)
1750 , Parameters(parameters)
1757 translator_type const& translator() const { return *this; }
1759 IndexableGetter const& indexable_getter() const { return *this; }
1760 IndexableGetter & indexable_getter() { return *this; }
1761 EqualTo const& equal_to() const { return *this; }
1762 EqualTo & equal_to() { return *this; }
1763 Parameters const& parameters() const { return *this; }
1764 Parameters & parameters() { return *this; }
1765 allocators_type const& allocators() const { return *this; }
1766 allocators_type & allocators() { return *this; }
1768 size_type values_count;
1769 size_type leafs_level;
1773 members_holder m_members;
1777 \brief Insert a value to the index.
1779 It calls <tt>rtree::insert(value_type const&)</tt>.
1781 \ingroup rtree_functions
1783 \param tree The spatial index.
1784 \param v The value which will be stored in the index.
1786 template <typename Value, typename Parameters, typename IndexableGetter, typename EqualTo, typename Allocator>
1787 inline void insert(rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator> & tree,
1794 \brief Insert a range of values to the index.
1796 It calls <tt>rtree::insert(Iterator, Iterator)</tt>.
1798 \ingroup rtree_functions
1800 \param tree The spatial index.
1801 \param first The beginning of the range of values.
1802 \param last The end of the range of values.
1804 template<typename Value, typename Parameters, typename IndexableGetter, typename EqualTo, typename Allocator,
1806 inline void insert(rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator> & tree,
1807 Iterator first, Iterator last)
1809 tree.insert(first, last);
1813 \brief Insert a value created using convertible object or a range of values to the index.
1815 It calls <tt>rtree::insert(ConvertibleOrRange const&)</tt>.
1817 \ingroup rtree_functions
1819 \param tree The spatial index.
1820 \param conv_or_rng The object of type convertible to value_type or a range of values.
1822 template<typename Value, typename Parameters, typename IndexableGetter, typename EqualTo, typename Allocator,
1823 typename ConvertibleOrRange>
1824 inline void insert(rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator> & tree,
1825 ConvertibleOrRange const& conv_or_rng)
1827 tree.insert(conv_or_rng);
1831 \brief Remove a value from the container.
1833 Remove a value from the container. In contrast to the \c std::set or <tt>std::map erase()</tt> method
1834 this function removes only one value from the container.
1836 It calls <tt>rtree::remove(value_type const&)</tt>.
1838 \ingroup rtree_functions
1840 \param tree The spatial index.
1841 \param v The value which will be removed from the index.
1843 \return 1 if value was removed, 0 otherwise.
1845 template <typename Value, typename Parameters, typename IndexableGetter, typename EqualTo, typename Allocator>
1846 inline typename rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator>::size_type
1847 remove(rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator> & tree,
1850 return tree.remove(v);
1854 \brief Remove a range of values from the container.
1856 Remove a range of values from the container. In contrast to the \c std::set or <tt>std::map erase()</tt> method
1857 it doesn't take iterators pointing to values stored in this container. It removes values equal
1858 to these passed as a range. Furthermore this function removes only one value for each one passed
1859 in the range, not all equal values.
1861 It calls <tt>rtree::remove(Iterator, Iterator)</tt>.
1863 \ingroup rtree_functions
1865 \param tree The spatial index.
1866 \param first The beginning of the range of values.
1867 \param last The end of the range of values.
1869 \return The number of removed values.
1871 template<typename Value, typename Parameters, typename IndexableGetter, typename EqualTo, typename Allocator,
1873 inline typename rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator>::size_type
1874 remove(rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator> & tree,
1875 Iterator first, Iterator last)
1877 return tree.remove(first, last);
1881 \brief Remove a value corresponding to an object convertible to it or a range of values from the container.
1883 Remove a value corresponding to an object convertible to it or a range of values from the container.
1884 In contrast to the \c std::set or <tt>std::map erase()</tt> method
1885 it removes values equal to these passed as a range. Furthermore this method removes only
1886 one value for each one passed in the range, not all equal values.
1888 It calls <tt>rtree::remove(ConvertibleOrRange const&)</tt>.
1890 \ingroup rtree_functions
1892 \param tree The spatial index.
1893 \param conv_or_rng The object of type convertible to value_type or the range of values.
1895 \return The number of removed values.
1897 template<typename Value, typename Parameters, typename IndexableGetter, typename EqualTo, typename Allocator,
1898 typename ConvertibleOrRange>
1899 inline typename rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator>::size_type
1900 remove(rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator> & tree,
1901 ConvertibleOrRange const& conv_or_rng)
1903 return tree.remove(conv_or_rng);
1907 \brief Finds values meeting passed predicates e.g. nearest to some Point and/or intersecting some Box.
1909 This query function performs spatial and k-nearest neighbor searches. It allows to pass a set of predicates.
1910 Values will be returned only if all predicates are met.
1912 <b>Spatial predicates</b>
1914 Spatial predicates may be generated by one of the functions listed below:
1915 \li \c boost::geometry::index::contains(),
1916 \li \c boost::geometry::index::covered_by(),
1917 \li \c boost::geometry::index::covers(),
1918 \li \c boost::geometry::index::disjoint(),
1919 \li \c boost::geometry::index::intersects(),
1920 \li \c boost::geometry::index::overlaps(),
1921 \li \c boost::geometry::index::within(),
1923 It is possible to negate spatial predicates:
1924 \li <tt>! boost::geometry::index::contains()</tt>,
1925 \li <tt>! boost::geometry::index::covered_by()</tt>,
1926 \li <tt>! boost::geometry::index::covers()</tt>,
1927 \li <tt>! boost::geometry::index::disjoint()</tt>,
1928 \li <tt>! boost::geometry::index::intersects()</tt>,
1929 \li <tt>! boost::geometry::index::overlaps()</tt>,
1930 \li <tt>! boost::geometry::index::within()</tt>
1932 <b>Satisfies predicate</b>
1934 This is a special kind of predicate which allows to pass a user-defined function or function object which checks
1935 if Value should be returned by the query. It's generated by:
1936 \li \c boost::geometry::index::satisfies().
1938 <b>Nearest predicate</b>
1940 If the nearest predicate is passed a k-nearest neighbor search will be performed. This query will result
1941 in returning k values to the output iterator. Only one nearest predicate may be passed to the query.
1942 It may be generated by:
1943 \li \c boost::geometry::index::nearest().
1945 <b>Connecting predicates</b>
1947 Predicates may be passed together connected with \c operator&&().
1951 // return elements intersecting box
1952 bgi::query(tree, bgi::intersects(box), std::back_inserter(result));
1953 // return elements intersecting poly but not within box
1954 bgi::query(tree, bgi::intersects(poly) && !bgi::within(box), std::back_inserter(result));
1955 // return elements overlapping box and meeting my_fun value predicate
1956 bgi::query(tree, bgi::overlaps(box) && bgi::satisfies(my_fun), std::back_inserter(result));
1957 // return 5 elements nearest to pt and elements are intersecting box
1958 bgi::query(tree, bgi::nearest(pt, 5) && bgi::intersects(box), std::back_inserter(result));
1960 // For each found value do_something (it is a type of function object)
1961 tree.query(bgi::intersects(box),
1962 boost::make_function_output_iterator(do_something()));
1966 If Value copy constructor or copy assignment throws.
1969 Only one \c nearest() perdicate may be passed to the query. Passing more of them results in compile-time error.
1971 \ingroup rtree_functions
1973 \param tree The rtree.
1974 \param predicates Predicates.
1975 \param out_it The output iterator, e.g. generated by std::back_inserter().
1977 \return The number of values found.
1979 template <typename Value, typename Parameters, typename IndexableGetter, typename EqualTo, typename Allocator,
1980 typename Predicates, typename OutIter> inline
1981 typename rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator>::size_type
1982 query(rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator> const& tree,
1983 Predicates const& predicates,
1986 return tree.query(predicates, out_it);
1990 \brief Returns the query iterator pointing at the begin of the query range.
1992 This method returns the iterator which may be used to perform iterative queries. For the information
1993 about the predicates which may be passed to this method see query().
1997 std::for_each(bgi::qbegin(tree, bgi::nearest(pt, 3)), bgi::qend(tree), do_something());
2000 \par Iterator category
2004 If predicates copy throws.
2005 If allocation throws.
2008 The modification of the rtree may invalidate the iterators.
2010 \ingroup rtree_functions
2012 \param tree The rtree.
2013 \param predicates Predicates.
2015 \return The iterator pointing at the begin of the query range.
2017 template <typename Value, typename Parameters, typename IndexableGetter, typename EqualTo, typename Allocator,
2018 typename Predicates> inline
2019 typename rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator>::const_query_iterator
2020 qbegin(rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator> const& tree,
2021 Predicates const& predicates)
2023 return tree.qbegin(predicates);
2027 \brief Returns the query iterator pointing at the end of the query range.
2029 This method returns the iterator which may be used to check if the query has ended.
2033 std::for_each(bgi::qbegin(tree, bgi::nearest(pt, 3)), bgi::qend(tree), do_something());
2036 \par Iterator category
2043 The modification of the rtree may invalidate the iterators.
2045 \ingroup rtree_functions
2047 \return The iterator pointing at the end of the query range.
2049 template <typename Value, typename Parameters, typename IndexableGetter, typename EqualTo, typename Allocator> inline
2050 typename rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator>::const_query_iterator
2051 qend(rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator> const& tree)
2057 \brief Returns the iterator pointing at the begin of the rtree values range.
2059 This method returns the iterator which may be used to iterate over all values
2060 stored in the rtree.
2064 std::for_each(bgi::begin(tree), bgi::end(tree), do_something());
2066 std::for_each(boost::begin(tree), boost::end(tree), do_something());
2069 \par Iterator category
2073 If allocation throws.
2076 The modification of the rtree may invalidate the iterators.
2078 \ingroup rtree_functions
2080 \return The iterator pointing at the begin of the range.
2082 template <typename Value, typename Parameters, typename IndexableGetter, typename EqualTo, typename Allocator> inline
2083 typename rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator>::const_iterator
2084 begin(rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator> const& tree)
2086 return tree.begin();
2090 \brief Returns the iterator pointing at the end of the rtree values range.
2092 This method returns the iterator which may be compared with the iterator returned by begin()
2093 in order to check if the iteration has ended.
2097 std::for_each(bgi::begin(tree), bgi::end(tree), do_something());
2099 std::for_each(boost::begin(tree), boost::end(tree), do_something());
2102 \par Iterator category
2109 The modification of the rtree may invalidate the iterators.
2111 \ingroup rtree_functions
2113 \return The iterator pointing at the end of the range.
2115 template <typename Value, typename Parameters, typename IndexableGetter, typename EqualTo, typename Allocator> inline
2116 typename rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator>::const_iterator
2117 end(rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator> const& tree)
2123 \brief Remove all values from the index.
2125 It calls \c rtree::clear().
2127 \ingroup rtree_functions
2129 \param tree The spatial index.
2131 template <typename Value, typename Parameters, typename IndexableGetter, typename EqualTo, typename Allocator>
2132 inline void clear(rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator> & tree)
2134 return tree.clear();
2138 \brief Get the number of values stored in the index.
2140 It calls \c rtree::size().
2142 \ingroup rtree_functions
2144 \param tree The spatial index.
2146 \return The number of values stored in the index.
2148 template <typename Value, typename Parameters, typename IndexableGetter, typename EqualTo, typename Allocator>
2149 inline size_t size(rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator> const& tree)
2155 \brief Query if there are no values stored in the index.
2157 It calls \c rtree::empty().
2159 \ingroup rtree_functions
2161 \param tree The spatial index.
2163 \return true if there are no values in the index.
2165 template <typename Value, typename Parameters, typename IndexableGetter, typename EqualTo, typename Allocator>
2166 inline bool empty(rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator> const& tree)
2168 return tree.bounds();
2172 \brief Get the box containing all stored values or an invalid box if the index has no values.
2174 It calls \c rtree::envelope().
2176 \ingroup rtree_functions
2178 \param tree The spatial index.
2180 \return The box containing all stored values or an invalid box.
2182 template <typename Value, typename Parameters, typename IndexableGetter, typename EqualTo, typename Allocator>
2183 inline typename rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator>::bounds_type
2184 bounds(rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator> const& tree)
2186 return tree.bounds();
2190 \brief Exchanges the contents of the container with those of other.
2192 It calls \c rtree::swap().
2194 \ingroup rtree_functions
2196 \param l The first rtree.
2197 \param r The second rtree.
2199 template <typename Value, typename Parameters, typename IndexableGetter, typename EqualTo, typename Allocator>
2200 inline void swap(rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator> & l,
2201 rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator> & r)
2206 }}} // namespace boost::geometry::index
2208 // Boost.Range adaptation
2211 template <typename Value, typename Parameters, typename IndexableGetter, typename EqualTo, typename Allocator>
2212 struct range_mutable_iterator
2214 boost::geometry::index::rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator>
2217 typedef typename boost::geometry::index::rtree
2219 Value, Parameters, IndexableGetter, EqualTo, Allocator
2220 >::const_iterator type;
2223 } // namespace boost
2225 // TODO: don't include the implementation at the end of the file
2226 #include <boost/geometry/algorithms/detail/comparable_distance/implementation.hpp>
2228 #include <boost/geometry/index/detail/config_end.hpp>
2230 #endif // BOOST_GEOMETRY_INDEX_RTREE_HPP