ceph/src/boost/boost/geometry/index/rtree.hpp

   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(*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, *this, false);
 367     }
 368
 369     /*!
 370     \brief The copy constructor.
 371
 372     It uses Parameters and translator from the source tree.
 373
 374     \param src          The rtree which content will be copied.
 375     \param allocator    The allocator which will be used.
 376
 377     \par Throws
 378     \li If allocator copy constructor throws.
 379     \li If Value copy constructor throws.
 380     \li If allocation throws or returns invalid value.
 381     */
 382     inline rtree(rtree const& src, allocator_type const& allocator)
 383         : m_members(src.m_members.indexable_getter(),
 384                     src.m_members.equal_to(),
 385                     src.m_members.parameters(), allocator)
 386     {
 387         this->raw_copy(src, *this, false);
 388     }
 389
 390     /*!
 391     \brief The moving constructor.
 392
 393     It uses parameters, translator and allocator from the source tree.
 394
 395     \param src          The rtree which content will be moved.
 396
 397     \par Throws
 398     Nothing.
 399     */
 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, *this, false);
 439         }
 440     }
 441
 442     /*!
 443     \brief The assignment operator.
 444
 445     It uses parameters and translator from the source tree.
 446
 447     \param src          The rtree which content will be copied.
 448
 449     \par Throws
 450     \li If Value copy constructor throws.
 451     \li If allocation throws.
 452     \li If allocation throws or returns invalid value.
 453     */
 454     inline rtree & operator=(BOOST_COPY_ASSIGN_REF(rtree) src)
 455     {
 456         if ( &src != this )
 457         {
 458             allocators_type & this_allocs = m_members.allocators();
 459             allocators_type const& src_allocs = src.m_members.allocators();
 460
 461             // NOTE: if propagate is true for std allocators on darwin 4.2.1, glibc++
 462             // (allocators stored as base classes of members_holder)
 463             // copying them changes values_count, in this case it doesn't cause errors since data must be copied
 464
 465             typedef boost::mpl::bool_<
 466                 allocator_traits_type::propagate_on_container_copy_assignment::value
 467             > propagate;
 468
 469             if ( propagate::value && !(this_allocs == src_allocs) )
 470                 this->raw_destroy(*this);
 471             detail::assign_cond(this_allocs, src_allocs, propagate());
 472
 473             // It uses m_allocators
 474             this->raw_copy(src, *this, true);
 475         }
 476
 477         return *this;
 478     }
 479
 480     /*!
 481     \brief The moving assignment.
 482
 483     It uses parameters and translator from the source tree.
 484
 485     \param src          The rtree which content will be moved.
 486
 487     \par Throws
 488     Only if allocators aren't equal.
 489     \li If Value copy constructor throws.
 490     \li If allocation throws or returns invalid value.
 491     */
 492     inline rtree & operator=(BOOST_RV_REF(rtree) src)
 493     {
 494         if ( &src != this )
 495         {
 496             allocators_type & this_allocs = m_members.allocators();
 497             allocators_type & src_allocs = src.m_members.allocators();
 498
 499             if ( this_allocs == src_allocs )
 500             {
 501                 this->raw_destroy(*this);
 502
 503                 m_members.indexable_getter() = src.m_members.indexable_getter();
 504                 m_members.equal_to() = src.m_members.equal_to();
 505                 m_members.parameters() = src.m_members.parameters();
 506
 507                 boost::swap(m_members.values_count, src.m_members.values_count);
 508                 boost::swap(m_members.leafs_level, src.m_members.leafs_level);
 509                 boost::swap(m_members.root, src.m_members.root);
 510
 511                 // NOTE: if propagate is true for std allocators on darwin 4.2.1, glibc++
 512                 // (allocators stored as base classes of members_holder)
 513                 // moving them changes values_count
 514
 515                 typedef boost::mpl::bool_<
 516                     allocator_traits_type::propagate_on_container_move_assignment::value
 517                 > propagate;
 518                 detail::move_cond(this_allocs, src_allocs, propagate());
 519             }
 520             else
 521             {
 522 // TODO - shouldn't here propagate_on_container_copy_assignment be checked like in operator=(const&)?
 523
 524                 // It uses m_allocators
 525                 this->raw_copy(src, *this, true);
 526             }
 527         }
 528
 529         return *this;
 530     }
 531
 532     /*!
 533     \brief Swaps contents of two rtrees.
 534
 535     Parameters, translator and allocators are swapped as well.
 536
 537     \param other    The rtree which content will be swapped with this rtree content.
 538
 539     \par Throws
 540     If allocators swap throws.
 541     */
 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(*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(*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() predicate 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 different 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(*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(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(*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(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(*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() predicate 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