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