Chris@16: // Boost.Geometry Index
Chris@16: //
Chris@16: // R-tree implementation
Chris@16: //
Chris@16: // Copyright (c) 2008 Federico J. Fernandez.
Chris@101: // Copyright (c) 2011-2015 Adam Wulkiewicz, Lodz, Poland.
Chris@16: //
Chris@16: // Use, modification and distribution is subject to the Boost Software License,
Chris@16: // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
Chris@16: // http://www.boost.org/LICENSE_1_0.txt)
Chris@16: 
Chris@16: #ifndef BOOST_GEOMETRY_INDEX_RTREE_HPP
Chris@16: #define BOOST_GEOMETRY_INDEX_RTREE_HPP
Chris@16: 
Chris@101: // STD
Chris@16: #include <algorithm>
Chris@16: 
Chris@101: // Boost
Chris@16: #include <boost/tuple/tuple.hpp>
Chris@16: #include <boost/move/move.hpp>
Chris@16: 
Chris@101: // Boost.Geometry
Chris@101: #include <boost/geometry/algorithms/detail/comparable_distance/interface.hpp>
Chris@101: #include <boost/geometry/algorithms/centroid.hpp>
Chris@101: #include <boost/geometry/algorithms/covered_by.hpp>
Chris@101: #include <boost/geometry/algorithms/disjoint.hpp>
Chris@101: #include <boost/geometry/algorithms/equals.hpp>
Chris@101: #include <boost/geometry/algorithms/intersects.hpp>
Chris@101: #include <boost/geometry/algorithms/overlaps.hpp>
Chris@101: #include <boost/geometry/algorithms/touches.hpp>
Chris@101: #include <boost/geometry/algorithms/within.hpp>
Chris@16: 
Chris@101: #include <boost/geometry/geometries/point.hpp>
Chris@101: #include <boost/geometry/geometries/box.hpp>
Chris@101: 
Chris@101: #include <boost/geometry/strategies/strategies.hpp>
Chris@101: 
Chris@101: // Boost.Geometry.Index
Chris@16: #include <boost/geometry/index/detail/config_begin.hpp>
Chris@16: 
Chris@16: #include <boost/geometry/index/detail/assert.hpp>
Chris@16: #include <boost/geometry/index/detail/exception.hpp>
Chris@16: 
Chris@16: #include <boost/geometry/index/detail/rtree/options.hpp>
Chris@16: 
Chris@16: #include <boost/geometry/index/indexable.hpp>
Chris@16: #include <boost/geometry/index/equal_to.hpp>
Chris@16: 
Chris@16: #include <boost/geometry/index/detail/translator.hpp>
Chris@16: 
Chris@16: #include <boost/geometry/index/predicates.hpp>
Chris@16: #include <boost/geometry/index/distance_predicates.hpp>
Chris@16: #include <boost/geometry/index/detail/rtree/adaptors.hpp>
Chris@16: 
Chris@16: #include <boost/geometry/index/detail/meta.hpp>
Chris@16: #include <boost/geometry/index/detail/utilities.hpp>
Chris@16: #include <boost/geometry/index/detail/rtree/node/node.hpp>
Chris@16: 
Chris@16: #include <boost/geometry/index/detail/algorithms/is_valid.hpp>
Chris@16: 
Chris@16: #include <boost/geometry/index/detail/rtree/visitors/insert.hpp>
Chris@16: #include <boost/geometry/index/detail/rtree/visitors/remove.hpp>
Chris@16: #include <boost/geometry/index/detail/rtree/visitors/copy.hpp>
Chris@16: #include <boost/geometry/index/detail/rtree/visitors/destroy.hpp>
Chris@16: #include <boost/geometry/index/detail/rtree/visitors/spatial_query.hpp>
Chris@16: #include <boost/geometry/index/detail/rtree/visitors/distance_query.hpp>
Chris@16: #include <boost/geometry/index/detail/rtree/visitors/count.hpp>
Chris@16: #include <boost/geometry/index/detail/rtree/visitors/children_box.hpp>
Chris@16: 
Chris@16: #include <boost/geometry/index/detail/rtree/linear/linear.hpp>
Chris@16: #include <boost/geometry/index/detail/rtree/quadratic/quadratic.hpp>
Chris@16: #include <boost/geometry/index/detail/rtree/rstar/rstar.hpp>
Chris@16: //#include <boost/geometry/extensions/index/detail/rtree/kmeans/kmeans.hpp>
Chris@16: 
Chris@16: #include <boost/geometry/index/detail/rtree/pack_create.hpp>
Chris@16: 
Chris@16: #include <boost/geometry/index/inserter.hpp>
Chris@16: 
Chris@16: #include <boost/geometry/index/detail/rtree/utilities/view.hpp>
Chris@16: 
Chris@16: #include <boost/geometry/index/detail/rtree/query_iterators.hpp>
Chris@16: 
Chris@16: #ifdef BOOST_GEOMETRY_INDEX_DETAIL_EXPERIMENTAL
Chris@16: // serialization
Chris@16: #include <boost/geometry/index/detail/serialization.hpp>
Chris@16: #endif
Chris@16: 
Chris@16: // TODO change the name to bounding_tree
Chris@16: 
Chris@16: /*!
Chris@16: \defgroup rtree_functions R-tree free functions (boost::geometry::index::)
Chris@16: */
Chris@16: 
Chris@16: namespace boost { namespace geometry { namespace index {
Chris@16: 
Chris@16: /*!
Chris@16: \brief The R-tree spatial index.
Chris@16: 
Chris@101: This is self-balancing spatial index capable to store various types of Values
Chris@101: and balancing algorithms.
Chris@16: 
Chris@16: \par Parameters
Chris@16: The user must pass a type defining the Parameters which will
Chris@101: be used in rtree creation process. This type is used e.g. to specify balancing
Chris@101: algorithm with specific parameters like min and max number of elements in node.
Chris@16: 
Chris@16: \par
Chris@16: Predefined algorithms with compile-time parameters are:
Chris@16: \li <tt>boost::geometry::index::linear</tt>,
Chris@16:  \li <tt>boost::geometry::index::quadratic</tt>,
Chris@16:  \li <tt>boost::geometry::index::rstar</tt>.
Chris@16: 
Chris@16: \par
Chris@16: Predefined algorithms with run-time parameters are:
Chris@16:  \li \c boost::geometry::index::dynamic_linear,
Chris@16:  \li \c boost::geometry::index::dynamic_quadratic,
Chris@16:  \li \c boost::geometry::index::dynamic_rstar.
Chris@16: 
Chris@16: \par IndexableGetter
Chris@101: The object of IndexableGetter type translates from Value to Indexable each time
Chris@101: r-tree requires it. This means that this operation is done for each Value
Chris@101: access. Therefore the IndexableGetter should return the Indexable by
Chris@101: a reference type. The Indexable should not be calculated since it could harm
Chris@101: the performance. The default IndexableGetter can translate all types adapted
Chris@101: to Point, Box or Segment concepts (called Indexables). Furthermore, it can
Chris@101: handle <tt>std::pair<Indexable, T></tt>, <tt>boost::tuple<Indexable, ...></tt>
Chris@101: and <tt>std::tuple<Indexable, ...></tt> when possible. For example, for Value
Chris@101: of type <tt>std::pair<Box, int></tt>, the default IndexableGetter translates
Chris@101: from <tt>std::pair<Box, int> const&</tt> to <tt>Box const&</tt>.
Chris@16: 
Chris@16: \par EqualTo
Chris@101: The object of EqualTo type compares Values and returns <tt>true</tt> if they
Chris@101: are equal. It's similar to <tt>std::equal_to<></tt>. The default EqualTo
Chris@101: returns the result of <tt>boost::geometry::equals()</tt> for types adapted to
Chris@101: some Geometry concept defined in Boost.Geometry and the result of
Chris@101: <tt>operator==</tt> for other types. Components of Pairs and Tuples are
Chris@101: compared left-to-right.
Chris@16: 
Chris@16: \tparam Value           The type of objects stored in the container.
Chris@16: \tparam Parameters      Compile-time parameters.
Chris@16: \tparam IndexableGetter The function object extracting Indexable from Value.
Chris@16: \tparam EqualTo         The function object comparing objects of type Value.
Chris@101: \tparam Allocator       The allocator used to allocate/deallocate memory,
Chris@101:                         construct/destroy nodes and Values.
Chris@16: */
Chris@16: template <
Chris@16:     typename Value,
Chris@16:     typename Parameters,
Chris@16:     typename IndexableGetter = index::indexable<Value>,
Chris@16:     typename EqualTo = index::equal_to<Value>,
Chris@16:     typename Allocator = std::allocator<Value>
Chris@16: >
Chris@16: class rtree
Chris@16: {
Chris@16:     BOOST_COPYABLE_AND_MOVABLE(rtree)
Chris@16: 
Chris@16: public:
Chris@16:     /*! \brief The type of Value stored in the container. */
Chris@16:     typedef Value value_type;
Chris@16:     /*! \brief R-tree parameters type. */
Chris@16:     typedef Parameters parameters_type;
Chris@16:     /*! \brief The function object extracting Indexable from Value. */
Chris@16:     typedef IndexableGetter indexable_getter;
Chris@16:     /*! \brief The function object comparing objects of type Value. */
Chris@16:     typedef EqualTo value_equal;
Chris@16:     /*! \brief The type of allocator used by the container. */
Chris@16:     typedef Allocator allocator_type;
Chris@16: 
Chris@16:     // TODO: SHOULD THIS TYPE BE REMOVED?
Chris@16:     /*! \brief The Indexable type to which Value is translated. */
Chris@16:     typedef typename index::detail::indexable_type<
Chris@16:         detail::translator<IndexableGetter, EqualTo>
Chris@16:     >::type indexable_type;
Chris@16: 
Chris@16:     /*! \brief The Box type used by the R-tree. */
Chris@16:     typedef geometry::model::box<
Chris@16:                 geometry::model::point<
Chris@16:                     typename coordinate_type<indexable_type>::type,
Chris@16:                     dimension<indexable_type>::value,
Chris@16:                     typename coordinate_system<indexable_type>::type
Chris@16:                 >
Chris@16:             >
Chris@16:     bounds_type;
Chris@16: 
Chris@16: private:
Chris@16: 
Chris@16:     typedef detail::translator<IndexableGetter, EqualTo> translator_type;
Chris@16: 
Chris@16:     typedef bounds_type box_type;
Chris@16:     typedef typename detail::rtree::options_type<Parameters>::type options_type;
Chris@16:     typedef typename options_type::node_tag node_tag;
Chris@16:     typedef detail::rtree::allocators<allocator_type, value_type, typename options_type::parameters_type, box_type, node_tag> allocators_type;
Chris@16: 
Chris@16:     typedef typename detail::rtree::node<value_type, typename options_type::parameters_type, box_type, allocators_type, node_tag>::type node;
Chris@16:     typedef typename detail::rtree::internal_node<value_type, typename options_type::parameters_type, box_type, allocators_type, node_tag>::type internal_node;
Chris@16:     typedef typename detail::rtree::leaf<value_type, typename options_type::parameters_type, box_type, allocators_type, node_tag>::type leaf;
Chris@16: 
Chris@16:     typedef typename allocators_type::node_pointer node_pointer;
Chris@16:     typedef ::boost::container::allocator_traits<Allocator> allocator_traits_type;
Chris@101:     typedef detail::rtree::subtree_destroyer<value_type, options_type, translator_type, box_type, allocators_type> subtree_destroyer;
Chris@16: 
Chris@16:     friend class detail::rtree::utilities::view<rtree>;
Chris@16: #ifdef BOOST_GEOMETRY_INDEX_DETAIL_EXPERIMENTAL
Chris@16:     friend class detail::rtree::private_view<rtree>;
Chris@16:     friend class detail::rtree::const_private_view<rtree>;
Chris@16: #endif
Chris@16: 
Chris@16: public:
Chris@16: 
Chris@16:     /*! \brief Type of reference to Value. */
Chris@16:     typedef typename allocators_type::reference reference;
Chris@16:     /*! \brief Type of reference to const Value. */
Chris@16:     typedef typename allocators_type::const_reference const_reference;
Chris@16:     /*! \brief Type of pointer to Value. */
Chris@16:     typedef typename allocators_type::pointer pointer;
Chris@16:     /*! \brief Type of pointer to const Value. */
Chris@16:     typedef typename allocators_type::const_pointer const_pointer;
Chris@16:     /*! \brief Type of difference type. */
Chris@16:     typedef typename allocators_type::difference_type difference_type;
Chris@16:     /*! \brief Unsigned integral type used by the container. */
Chris@16:     typedef typename allocators_type::size_type size_type;
Chris@16: 
Chris@16:     /*! \brief Type of const query iterator. */
Chris@16:     typedef index::detail::rtree::iterators::query_iterator<value_type, allocators_type> const_query_iterator;
Chris@16: 
Chris@16: public:
Chris@16: 
Chris@16:     /*!
Chris@16:     \brief The constructor.
Chris@16: 
Chris@16:     \param parameters   The parameters object.
Chris@16:     \param getter       The function object extracting Indexable from Value.
Chris@16:     \param equal        The function object comparing Values.
Chris@16: 
Chris@16:     \par Throws
Chris@16:     If allocator default constructor throws.
Chris@16:     */
Chris@16:     inline explicit rtree(parameters_type const& parameters = parameters_type(),
Chris@16:                           indexable_getter const& getter = indexable_getter(),
Chris@16:                           value_equal const& equal = value_equal())
Chris@16:         : m_members(getter, equal, parameters)
Chris@16:     {}
Chris@16: 
Chris@16:     /*!
Chris@16:     \brief The constructor.
Chris@16: 
Chris@16:     \param parameters   The parameters object.
Chris@16:     \param getter       The function object extracting Indexable from Value.
Chris@16:     \param equal        The function object comparing Values.
Chris@16:     \param allocator    The allocator object.
Chris@16: 
Chris@16:     \par Throws
Chris@16:     If allocator copy constructor throws.
Chris@16:     */
Chris@16:     inline rtree(parameters_type const& parameters,
Chris@16:                  indexable_getter const& getter,
Chris@16:                  value_equal const& equal,
Chris@16:                  allocator_type const& allocator)
Chris@16:         : m_members(getter, equal, parameters, allocator)
Chris@16:     {}
Chris@16: 
Chris@16:     /*!
Chris@16:     \brief The constructor.
Chris@16: 
Chris@16:     The tree is created using packing algorithm.
Chris@16: 
Chris@16:     \param first        The beginning of the range of Values.
Chris@16:     \param last         The end of the range of Values.
Chris@16:     \param parameters   The parameters object.
Chris@16:     \param getter       The function object extracting Indexable from Value.
Chris@16:     \param equal        The function object comparing Values.
Chris@16:     \param allocator    The allocator object.
Chris@16: 
Chris@16:     \par Throws
Chris@16:     \li If allocator copy constructor throws.
Chris@16:     \li If Value copy constructor or copy assignment throws.
Chris@16:     \li If allocation throws or returns invalid value.
Chris@16:     */
Chris@16:     template<typename Iterator>
Chris@16:     inline rtree(Iterator first, Iterator last,
Chris@16:                  parameters_type const& parameters = parameters_type(),
Chris@16:                  indexable_getter const& getter = indexable_getter(),
Chris@16:                  value_equal const& equal = value_equal(),
Chris@16:                  allocator_type const& allocator = allocator_type())
Chris@16:         : m_members(getter, equal, parameters, allocator)
Chris@16:     {
Chris@16:         typedef detail::rtree::pack<value_type, options_type, translator_type, box_type, allocators_type> pack;
Chris@16:         size_type vc = 0, ll = 0;
Chris@16:         m_members.root = pack::apply(first, last, vc, ll,
Chris@16:                                      m_members.parameters(), m_members.translator(), m_members.allocators());
Chris@16:         m_members.values_count = vc;
Chris@16:         m_members.leafs_level = ll;
Chris@16:     }
Chris@16: 
Chris@16:     /*!
Chris@16:     \brief The constructor.
Chris@16: 
Chris@16:     The tree is created using packing algorithm.
Chris@16: 
Chris@16:     \param rng          The range of Values.
Chris@16:     \param parameters   The parameters object.
Chris@16:     \param getter       The function object extracting Indexable from Value.
Chris@16:     \param equal        The function object comparing Values.
Chris@16:     \param allocator    The allocator object.
Chris@16: 
Chris@16:     \par Throws
Chris@16:     \li If allocator copy constructor throws.
Chris@16:     \li If Value copy constructor or copy assignment throws.
Chris@16:     \li If allocation throws or returns invalid value.
Chris@16:     */
Chris@16:     template<typename Range>
Chris@16:     inline explicit rtree(Range const& rng,
Chris@16:                           parameters_type const& parameters = parameters_type(),
Chris@16:                           indexable_getter const& getter = indexable_getter(),
Chris@16:                           value_equal const& equal = value_equal(),
Chris@16:                           allocator_type const& allocator = allocator_type())
Chris@16:         : m_members(getter, equal, parameters, allocator)
Chris@16:     {
Chris@16:         typedef detail::rtree::pack<value_type, options_type, translator_type, box_type, allocators_type> pack;
Chris@16:         size_type vc = 0, ll = 0;
Chris@16:         m_members.root = pack::apply(::boost::begin(rng), ::boost::end(rng), vc, ll,
Chris@16:                                      m_members.parameters(), m_members.translator(), m_members.allocators());
Chris@16:         m_members.values_count = vc;
Chris@16:         m_members.leafs_level = ll;
Chris@16:     }
Chris@16: 
Chris@16:     /*!
Chris@16:     \brief The destructor.
Chris@16: 
Chris@16:     \par Throws
Chris@16:     Nothing.
Chris@16:     */
Chris@16:     inline ~rtree()
Chris@16:     {
Chris@16:         this->raw_destroy(*this);
Chris@16:     }
Chris@16: 
Chris@16:     /*!
Chris@16:     \brief  The copy constructor.
Chris@16: 
Chris@16:     It uses parameters, translator and allocator from the source tree.
Chris@16: 
Chris@16:     \param src          The rtree which content will be copied.
Chris@16: 
Chris@16:     \par Throws
Chris@16:     \li If allocator copy constructor throws.
Chris@16:     \li If Value copy constructor throws.
Chris@16:     \li If allocation throws or returns invalid value.
Chris@16:     */
Chris@16:     inline rtree(rtree const& src)
Chris@16:         : m_members(src.m_members.indexable_getter(),
Chris@16:                     src.m_members.equal_to(),
Chris@16:                     src.m_members.parameters(),
Chris@16:                     allocator_traits_type::select_on_container_copy_construction(src.get_allocator()))
Chris@16:     {
Chris@16:         this->raw_copy(src, *this, false);
Chris@16:     }
Chris@16: 
Chris@16:     /*!
Chris@16:     \brief The copy constructor.
Chris@16: 
Chris@16:     It uses Parameters and translator from the source tree.
Chris@16: 
Chris@16:     \param src          The rtree which content will be copied.
Chris@16:     \param allocator    The allocator which will be used.
Chris@16: 
Chris@16:     \par Throws
Chris@16:     \li If allocator copy constructor throws.
Chris@16:     \li If Value copy constructor throws.
Chris@16:     \li If allocation throws or returns invalid value.
Chris@16:     */
Chris@16:     inline rtree(rtree const& src, allocator_type const& allocator)
Chris@16:         : m_members(src.m_members.indexable_getter(),
Chris@16:                     src.m_members.equal_to(),
Chris@16:                     src.m_members.parameters(), allocator)
Chris@16:     {
Chris@16:         this->raw_copy(src, *this, false);
Chris@16:     }
Chris@16: 
Chris@16:     /*!
Chris@16:     \brief The moving constructor.
Chris@16: 
Chris@16:     It uses parameters, translator and allocator from the source tree.
Chris@16: 
Chris@16:     \param src          The rtree which content will be moved.
Chris@16: 
Chris@16:     \par Throws
Chris@16:     Nothing.
Chris@16:     */
Chris@16:     inline rtree(BOOST_RV_REF(rtree) src)
Chris@16:         : m_members(src.m_members.indexable_getter(),
Chris@16:                     src.m_members.equal_to(),
Chris@16:                     src.m_members.parameters(),
Chris@16:                     boost::move(src.m_members.allocators()))
Chris@16:     {
Chris@16:         boost::swap(m_members.values_count, src.m_members.values_count);
Chris@16:         boost::swap(m_members.leafs_level, src.m_members.leafs_level);
Chris@16:         boost::swap(m_members.root, src.m_members.root);
Chris@16:     }
Chris@16: 
Chris@16:     /*!
Chris@16:     \brief The moving constructor.
Chris@16: 
Chris@16:     It uses parameters and translator from the source tree.
Chris@16: 
Chris@16:     \param src          The rtree which content will be moved.
Chris@16:     \param allocator    The allocator.
Chris@16: 
Chris@16:     \par Throws
Chris@16:     \li If allocator copy constructor throws.
Chris@16:     \li If Value copy constructor throws (only if allocators aren't equal).
Chris@16:     \li If allocation throws or returns invalid value (only if allocators aren't equal).
Chris@16:     */
Chris@16:     inline rtree(BOOST_RV_REF(rtree) src, allocator_type const& allocator)
Chris@16:         : m_members(src.m_members.indexable_getter(),
Chris@16:                     src.m_members.equal_to(),
Chris@16:                     src.m_members.parameters(),
Chris@16:                     allocator)
Chris@16:     {
Chris@16:         if ( src.m_members.allocators() == allocator )
Chris@16:         {
Chris@16:             boost::swap(m_members.values_count, src.m_members.values_count);
Chris@16:             boost::swap(m_members.leafs_level, src.m_members.leafs_level);
Chris@16:             boost::swap(m_members.root, src.m_members.root);
Chris@16:         }
Chris@16:         else
Chris@16:         {
Chris@16:             this->raw_copy(src, *this, false);
Chris@16:         }
Chris@16:     }
Chris@16: 
Chris@16:     /*!
Chris@16:     \brief The assignment operator.
Chris@16: 
Chris@16:     It uses parameters and translator from the source tree.
Chris@16: 
Chris@16:     \param src          The rtree which content will be copied.
Chris@16: 
Chris@16:     \par Throws
Chris@16:     \li If Value copy constructor throws.
Chris@16:     \li If allocation throws.
Chris@16:     \li If allocation throws or returns invalid value.
Chris@16:     */
Chris@16:     inline rtree & operator=(BOOST_COPY_ASSIGN_REF(rtree) src)
Chris@16:     {
Chris@16:         if ( &src != this )
Chris@16:         {
Chris@16:             allocators_type & this_allocs = m_members.allocators();
Chris@16:             allocators_type const& src_allocs = src.m_members.allocators();
Chris@16: 
Chris@16:             // NOTE: if propagate is true for std allocators on darwin 4.2.1, glibc++
Chris@16:             // (allocators stored as base classes of members_holder)
Chris@16:             // copying them changes values_count, in this case it doesn't cause errors since data must be copied
Chris@16:             
Chris@16:             typedef boost::mpl::bool_<
Chris@16:                 allocator_traits_type::propagate_on_container_copy_assignment::value
Chris@16:             > propagate;
Chris@16:             
Chris@16:             if ( propagate::value && !(this_allocs == src_allocs) )
Chris@16:                 this->raw_destroy(*this);
Chris@16:             detail::assign_cond(this_allocs, src_allocs, propagate());
Chris@16: 
Chris@16:             // It uses m_allocators
Chris@16:             this->raw_copy(src, *this, true);
Chris@16:         }
Chris@16: 
Chris@16:         return *this;
Chris@16:     }
Chris@16: 
Chris@16:     /*!
Chris@16:     \brief The moving assignment.
Chris@16: 
Chris@16:     It uses parameters and translator from the source tree.
Chris@16: 
Chris@16:     \param src          The rtree which content will be moved.
Chris@16: 
Chris@16:     \par Throws
Chris@16:     Only if allocators aren't equal.
Chris@16:     \li If Value copy constructor throws.
Chris@16:     \li If allocation throws or returns invalid value.
Chris@16:     */
Chris@16:     inline rtree & operator=(BOOST_RV_REF(rtree) src)
Chris@16:     {
Chris@16:         if ( &src != this )
Chris@16:         {
Chris@16:             allocators_type & this_allocs = m_members.allocators();
Chris@16:             allocators_type & src_allocs = src.m_members.allocators();
Chris@16:             
Chris@16:             if ( this_allocs == src_allocs )
Chris@16:             {
Chris@16:                 this->raw_destroy(*this);
Chris@16: 
Chris@16:                 m_members.indexable_getter() = src.m_members.indexable_getter();
Chris@16:                 m_members.equal_to() = src.m_members.equal_to();
Chris@16:                 m_members.parameters() = src.m_members.parameters();
Chris@16: 
Chris@16:                 boost::swap(m_members.values_count, src.m_members.values_count);
Chris@16:                 boost::swap(m_members.leafs_level, src.m_members.leafs_level);
Chris@16:                 boost::swap(m_members.root, src.m_members.root);
Chris@16: 
Chris@16:                 // NOTE: if propagate is true for std allocators on darwin 4.2.1, glibc++
Chris@16:                 // (allocators stored as base classes of members_holder)
Chris@16:                 // moving them changes values_count
Chris@16:                 
Chris@16:                 typedef boost::mpl::bool_<
Chris@16:                     allocator_traits_type::propagate_on_container_move_assignment::value
Chris@16:                 > propagate;
Chris@16:                 detail::move_cond(this_allocs, src_allocs, propagate());
Chris@16:             }
Chris@16:             else
Chris@16:             {
Chris@16: // TODO - shouldn't here propagate_on_container_copy_assignment be checked like in operator=(const&)?
Chris@16: 
Chris@16:                 // It uses m_allocators
Chris@16:                 this->raw_copy(src, *this, true);
Chris@16:             }
Chris@16:         }
Chris@16: 
Chris@16:         return *this;
Chris@16:     }
Chris@16: 
Chris@16:     /*!
Chris@16:     \brief Swaps contents of two rtrees.
Chris@16: 
Chris@16:     Parameters, translator and allocators are swapped as well.
Chris@16: 
Chris@16:     \param other    The rtree which content will be swapped with this rtree content.
Chris@16: 
Chris@16:     \par Throws
Chris@16:     If allocators swap throws.
Chris@16:     */
Chris@16:     void swap(rtree & other)
Chris@16:     {
Chris@16:         boost::swap(m_members.indexable_getter(), other.m_members.indexable_getter());
Chris@16:         boost::swap(m_members.equal_to(), other.m_members.equal_to());
Chris@16:         boost::swap(m_members.parameters(), other.m_members.parameters());
Chris@16:         
Chris@16:         // NOTE: if propagate is true for std allocators on darwin 4.2.1, glibc++
Chris@16:         // (allocators stored as base classes of members_holder)
Chris@16:         // swapping them changes values_count
Chris@16:         
Chris@16:         typedef boost::mpl::bool_<
Chris@16:             allocator_traits_type::propagate_on_container_swap::value
Chris@16:         > propagate;
Chris@16:         detail::swap_cond(m_members.allocators(), other.m_members.allocators(), propagate());
Chris@16: 
Chris@16:         boost::swap(m_members.values_count, other.m_members.values_count);
Chris@16:         boost::swap(m_members.leafs_level, other.m_members.leafs_level);
Chris@16:         boost::swap(m_members.root, other.m_members.root);
Chris@16:     }
Chris@16: 
Chris@16:     /*!
Chris@16:     \brief Insert a value to the index.
Chris@16: 
Chris@16:     \param value    The value which will be stored in the container.
Chris@16: 
Chris@16:     \par Throws
Chris@16:     \li If Value copy constructor or copy assignment throws.
Chris@16:     \li If allocation throws or returns invalid value.
Chris@16: 
Chris@16:     \warning
Chris@16:     This operation only guarantees that there will be no memory leaks.
Chris@16:     After an exception is thrown the R-tree may be left in an inconsistent state,
Chris@16:     elements must not be inserted or removed. Other operations are allowed however
Chris@16:     some of them may return invalid data.
Chris@16:     */
Chris@16:     inline void insert(value_type const& value)
Chris@16:     {
Chris@16:         if ( !m_members.root )
Chris@16:             this->raw_create();
Chris@16: 
Chris@16:         this->raw_insert(value);
Chris@16:     }
Chris@16: 
Chris@16:     /*!
Chris@16:     \brief Insert a range of values to the index.
Chris@16: 
Chris@16:     \param first    The beginning of the range of values.
Chris@16:     \param last     The end of the range of values.
Chris@16: 
Chris@16:     \par Throws
Chris@16:     \li If Value copy constructor or copy assignment throws.
Chris@16:     \li If allocation throws or returns invalid value.
Chris@16: 
Chris@16:     \warning
Chris@16:     This operation only guarantees that there will be no memory leaks.
Chris@16:     After an exception is thrown the R-tree may be left in an inconsistent state,
Chris@16:     elements must not be inserted or removed. Other operations are allowed however
Chris@16:     some of them may return invalid data.
Chris@16:     */
Chris@16:     template <typename Iterator>
Chris@16:     inline void insert(Iterator first, Iterator last)
Chris@16:     {
Chris@16:         if ( !m_members.root )
Chris@16:             this->raw_create();
Chris@16: 
Chris@16:         for ( ; first != last ; ++first )
Chris@16:             this->raw_insert(*first);
Chris@16:     }
Chris@16: 
Chris@16:     /*!
Chris@101:     \brief Insert a value created using convertible object or a range of values to the index.
Chris@16: 
Chris@101:     \param conv_or_rng      An object of type convertible to value_type or a range of values.
Chris@16: 
Chris@16:     \par Throws
Chris@16:     \li If Value copy constructor or copy assignment throws.
Chris@16:     \li If allocation throws or returns invalid value.
Chris@16: 
Chris@16:     \warning
Chris@16:     This operation only guarantees that there will be no memory leaks.
Chris@16:     After an exception is thrown the R-tree may be left in an inconsistent state,
Chris@16:     elements must not be inserted or removed. Other operations are allowed however
Chris@16:     some of them may return invalid data.
Chris@16:     */
Chris@101:     template <typename ConvertibleOrRange>
Chris@101:     inline void insert(ConvertibleOrRange const& conv_or_rng)
Chris@16:     {
Chris@101:         typedef boost::mpl::bool_
Chris@101:             <
Chris@101:                 boost::is_convertible<ConvertibleOrRange, value_type>::value
Chris@101:             > is_conv_t;
Chris@16: 
Chris@101:         this->insert_dispatch(conv_or_rng, is_conv_t());
Chris@16:     }
Chris@16: 
Chris@16:     /*!
Chris@16:     \brief Remove a value from the container.
Chris@16: 
Chris@16:     In contrast to the \c std::set or <tt>std::map erase()</tt> method
Chris@16:     this method removes only one value from the container.
Chris@16: 
Chris@16:     \param value    The value which will be removed from the container.
Chris@16: 
Chris@16:     \return         1 if the value was removed, 0 otherwise.
Chris@16: 
Chris@16:     \par Throws
Chris@16:     \li If Value copy constructor or copy assignment throws.
Chris@16:     \li If allocation throws or returns invalid value.
Chris@16: 
Chris@16:     \warning
Chris@16:     This operation only guarantees that there will be no memory leaks.
Chris@16:     After an exception is thrown the R-tree may be left in an inconsistent state,
Chris@16:     elements must not be inserted or removed. Other operations are allowed however
Chris@16:     some of them may return invalid data.
Chris@16:     */
Chris@16:     inline size_type remove(value_type const& value)
Chris@16:     {
Chris@16:         return this->raw_remove(value);
Chris@16:     }
Chris@16: 
Chris@16:     /*!
Chris@16:     \brief Remove a range of values from the container.
Chris@16: 
Chris@16:     In contrast to the \c std::set or <tt>std::map erase()</tt> method
Chris@16:     it doesn't take iterators pointing to values stored in this container. It removes values equal
Chris@16:     to these passed as a range. Furthermore this method removes only one value for each one passed
Chris@16:     in the range, not all equal values.
Chris@16: 
Chris@16:     \param first    The beginning of the range of values.
Chris@16:     \param last     The end of the range of values.
Chris@16: 
Chris@16:     \return         The number of removed values.
Chris@16: 
Chris@16:     \par Throws
Chris@16:     \li If Value copy constructor or copy assignment throws.
Chris@16:     \li If allocation throws or returns invalid value.
Chris@16: 
Chris@16:     \warning
Chris@16:     This operation only guarantees that there will be no memory leaks.
Chris@16:     After an exception is thrown the R-tree may be left in an inconsistent state,
Chris@16:     elements must not be inserted or removed. Other operations are allowed however
Chris@16:     some of them may return invalid data.
Chris@16:     */
Chris@16:     template <typename Iterator>
Chris@16:     inline size_type remove(Iterator first, Iterator last)
Chris@16:     {
Chris@16:         size_type result = 0;
Chris@16:         for ( ; first != last ; ++first )
Chris@16:             result += this->raw_remove(*first);
Chris@16:         return result;
Chris@16:     }
Chris@16: 
Chris@16:     /*!
Chris@101:     \brief Remove value corresponding to an object convertible to it or a range of values from the container.
Chris@16: 
Chris@16:     In contrast to the \c std::set or <tt>std::map erase()</tt> method
Chris@16:     it removes values equal to these passed as a range. Furthermore, this method removes only
Chris@16:     one value for each one passed in the range, not all equal values.
Chris@16: 
Chris@101:     \param conv_or_rng      The object of type convertible to value_type or a range of values.
Chris@16: 
Chris@16:     \return         The number of removed values.
Chris@16: 
Chris@16:     \par Throws
Chris@16:     \li If Value copy constructor or copy assignment throws.
Chris@16:     \li If allocation throws or returns invalid value.
Chris@16: 
Chris@16:     \warning
Chris@16:     This operation only guarantees that there will be no memory leaks.
Chris@16:     After an exception is thrown the R-tree may be left in an inconsistent state,
Chris@16:     elements must not be inserted or removed. Other operations are allowed however
Chris@16:     some of them may return invalid data.
Chris@16:     */
Chris@101:     template <typename ConvertibleOrRange>
Chris@101:     inline size_type remove(ConvertibleOrRange const& conv_or_rng)
Chris@16:     {
Chris@101:         typedef boost::mpl::bool_
Chris@101:             <
Chris@101:                 boost::is_convertible<ConvertibleOrRange, value_type>::value
Chris@101:             > is_conv_t;
Chris@16: 
Chris@101:         return this->remove_dispatch(conv_or_rng, is_conv_t());
Chris@16:     }
Chris@16: 
Chris@16:     /*!
Chris@16:     \brief Finds values meeting passed predicates e.g. nearest to some Point and/or intersecting some Box.
Chris@16: 
Chris@16:     This query function performs spatial and k-nearest neighbor searches. It allows to pass a set of predicates.
Chris@16:     Values will be returned only if all predicates are met.
Chris@16: 
Chris@16:     <b>Spatial predicates</b>
Chris@16:     
Chris@16:     Spatial predicates may be generated by one of the functions listed below:
Chris@16:     \li \c boost::geometry::index::contains(),
Chris@16:     \li \c boost::geometry::index::covered_by(),
Chris@16:     \li \c boost::geometry::index::covers(),
Chris@16:     \li \c boost::geometry::index::disjoint(),
Chris@16:     \li \c boost::geometry::index::intersects(),
Chris@16:     \li \c boost::geometry::index::overlaps(),
Chris@16:     \li \c boost::geometry::index::within(),
Chris@16: 
Chris@16:     It is possible to negate spatial predicates:
Chris@16:     \li <tt>! boost::geometry::index::contains()</tt>,
Chris@16:     \li <tt>! boost::geometry::index::covered_by()</tt>,
Chris@16:     \li <tt>! boost::geometry::index::covers()</tt>,
Chris@16:     \li <tt>! boost::geometry::index::disjoint()</tt>,
Chris@16:     \li <tt>! boost::geometry::index::intersects()</tt>,
Chris@16:     \li <tt>! boost::geometry::index::overlaps()</tt>,
Chris@16:     \li <tt>! boost::geometry::index::within()</tt>
Chris@16: 
Chris@16:     <b>Satisfies predicate</b>
Chris@16:     
Chris@16:     This is a special kind of predicate which allows to pass a user-defined function or function object which checks
Chris@16:     if Value should be returned by the query. It's generated by:
Chris@16:     \li \c boost::geometry::index::satisfies().
Chris@16: 
Chris@16:     <b>Nearest predicate</b>
Chris@16: 
Chris@16:     If the nearest predicate is passed a k-nearest neighbor search will be performed. This query will result
Chris@16:     in returning k values to the output iterator. Only one nearest predicate may be passed to the query.
Chris@16:     It may be generated by:
Chris@16:     \li \c boost::geometry::index::nearest().
Chris@16:         
Chris@16:     <b>Connecting predicates</b>
Chris@16: 
Chris@16:     Predicates may be passed together connected with \c operator&&().
Chris@16: 
Chris@16:     \par Example
Chris@16:     \verbatim
Chris@16:     // return elements intersecting box
Chris@16:     tree.query(bgi::intersects(box), std::back_inserter(result));
Chris@16:     // return elements intersecting poly but not within box
Chris@16:     tree.query(bgi::intersects(poly) && !bgi::within(box), std::back_inserter(result));
Chris@16:     // return elements overlapping box and meeting my_fun unary predicate
Chris@16:     tree.query(bgi::overlaps(box) && bgi::satisfies(my_fun), std::back_inserter(result));
Chris@16:     // return 5 elements nearest to pt and elements are intersecting box
Chris@16:     tree.query(bgi::nearest(pt, 5) && bgi::intersects(box), std::back_inserter(result));
Chris@16:     \endverbatim
Chris@16: 
Chris@16:     \par Throws
Chris@16:     If Value copy constructor or copy assignment throws.
Chris@16:     If predicates copy throws.
Chris@16: 
Chris@16:     \warning
Chris@16:     Only one \c nearest() perdicate may be passed to the query. Passing more of them results in compile-time error.
Chris@16:     
Chris@16:     \param predicates   Predicates.
Chris@16:     \param out_it       The output iterator, e.g. generated by std::back_inserter().
Chris@16: 
Chris@16:     \return             The number of values found.
Chris@16:     */
Chris@16:     template <typename Predicates, typename OutIter>
Chris@16:     size_type query(Predicates const& predicates, OutIter out_it) const
Chris@16:     {
Chris@16:         if ( !m_members.root )
Chris@16:             return 0;
Chris@16: 
Chris@16:         static const unsigned distance_predicates_count = detail::predicates_count_distance<Predicates>::value;
Chris@16:         static const bool is_distance_predicate = 0 < distance_predicates_count;
Chris@16:         BOOST_MPL_ASSERT_MSG((distance_predicates_count <= 1), PASS_ONLY_ONE_DISTANCE_PREDICATE, (Predicates));
Chris@16: 
Chris@16:         return query_dispatch(predicates, out_it, boost::mpl::bool_<is_distance_predicate>());
Chris@16:     }
Chris@16: 
Chris@16:     /*!
Chris@16:     \brief Returns the query iterator pointing at the begin of the query range.
Chris@16: 
Chris@16:     This method returns the iterator which may be used to perform iterative queries. For the information
Chris@16:     about the predicates which may be passed to this method see query().
Chris@16:     
Chris@16:     \par Example
Chris@16:     \verbatim    
Chris@16:     for ( Rtree::const_query_iterator it = tree.qbegin(bgi::nearest(pt, 10000)) ;
Chris@16:           it != tree.qend() ; ++it )
Chris@16:     {
Chris@16:         // do something with value
Chris@16:         if ( has_enough_nearest_values() )
Chris@16:             break;
Chris@16:     }
Chris@16:     \endverbatim
Chris@16: 
Chris@16:     \par Throws
Chris@16:     If predicates copy throws.
Chris@16:     If allocation throws.
Chris@16: 
Chris@16:     \param predicates   Predicates.
Chris@16:     
Chris@16:     \return             The iterator pointing at the begin of the query range.
Chris@16:     */
Chris@16:     template <typename Predicates>
Chris@16:     const_query_iterator qbegin(Predicates const& predicates) const
Chris@16:     {
Chris@16:         return const_query_iterator(qbegin_(predicates));
Chris@16:     }
Chris@16: 
Chris@16:     /*!
Chris@16:     \brief Returns the query iterator pointing at the end of the query range.
Chris@16: 
Chris@16:     This method returns the iterator which may be used to check if the query has ended.
Chris@16:     
Chris@16:     \par Example
Chris@16:     \verbatim    
Chris@16:     for ( Rtree::const_query_iterator it = tree.qbegin(bgi::nearest(pt, 10000)) ;
Chris@16:           it != tree.qend() ; ++it )
Chris@16:     {
Chris@16:         // do something with value
Chris@16:         if ( has_enough_nearest_values() )
Chris@16:             break;
Chris@16:     }
Chris@16:     \endverbatim
Chris@16: 
Chris@16:     \par Throws
Chris@16:     Nothing
Chris@16:     
Chris@16:     \return             The iterator pointing at the end of the query range.
Chris@16:     */
Chris@16:     const_query_iterator qend() const
Chris@16:     {
Chris@16:         return const_query_iterator();
Chris@16:     }
Chris@16: 
Chris@16: #ifndef BOOST_GEOMETRY_INDEX_DETAIL_EXPERIMENTAL
Chris@16: private:
Chris@16: #endif
Chris@16:     /*!
Chris@16:     \brief Returns the query iterator pointing at the begin of the query range.
Chris@16: 
Chris@16:     This method returns the iterator which may be used to perform iterative queries. For the information
Chris@16:     about the predicates which may be passed to this method see query().
Chris@16:     
Chris@16:     The type of the returned iterator depends on the type of passed Predicates but the iterator of this type
Chris@16:     may be assigned to the variable of const_query_iterator type. If you'd like to use the type of the iterator
Chris@16:     returned by this method you may get the type e.g. by using C++11 decltype or Boost.Typeof library.
Chris@16:     This iterator may be compared with iterators returned by both versions of qend() method.
Chris@16: 
Chris@16:     \par Example
Chris@16:     \verbatim
Chris@16:     // Store the result in the container using std::copy() - it requires both iterators of the same type
Chris@16:     std::copy(tree.qbegin(bgi::intersects(box)), tree.qend(bgi::intersects(box)), std::back_inserter(result));
Chris@16: 
Chris@16:     // Store the result in the container using std::copy() and type-erased iterators
Chris@16:     Rtree::const_query_iterator first = tree.qbegin(bgi::intersects(box));
Chris@16:     Rtree::const_query_iterator last = tree.qend();
Chris@16:     std::copy(first, last, std::back_inserter(result));
Chris@16: 
Chris@16:     // Boost.Typeof
Chris@16:     typedef BOOST_TYPEOF(tree.qbegin(bgi::nearest(pt, 10000))) Iter;
Chris@16:     for ( Iter it = tree.qbegin(bgi::nearest(pt, 10000)) ; it != tree.qend() ; ++it )
Chris@16:     {
Chris@16:         // do something with value
Chris@16:         if ( has_enough_nearest_values() )
Chris@16:             break;
Chris@16:     }
Chris@16:     \endverbatim
Chris@16: 
Chris@16:     \par Throws
Chris@16:     If predicates copy throws.
Chris@16:     If allocation throws.
Chris@16: 
Chris@16:     \param predicates   Predicates.
Chris@16:     
Chris@16:     \return             The iterator pointing at the begin of the query range.
Chris@16:     */
Chris@16:     template <typename Predicates>
Chris@16:     typename boost::mpl::if_c<
Chris@16:         detail::predicates_count_distance<Predicates>::value == 0,
Chris@16:         detail::rtree::iterators::spatial_query_iterator<value_type, options_type, translator_type, box_type, allocators_type, Predicates>,
Chris@16:         detail::rtree::iterators::distance_query_iterator<
Chris@16:             value_type, options_type, translator_type, box_type, allocators_type, Predicates,
Chris@16:             detail::predicates_find_distance<Predicates>::value
Chris@16:         >
Chris@16:     >::type
Chris@16:     qbegin_(Predicates const& predicates) const
Chris@16:     {
Chris@16:         static const unsigned distance_predicates_count = detail::predicates_count_distance<Predicates>::value;
Chris@16:         BOOST_MPL_ASSERT_MSG((distance_predicates_count <= 1), PASS_ONLY_ONE_DISTANCE_PREDICATE, (Predicates));
Chris@16: 
Chris@16:         typedef typename boost::mpl::if_c<
Chris@16:             detail::predicates_count_distance<Predicates>::value == 0,
Chris@16:             detail::rtree::iterators::spatial_query_iterator<value_type, options_type, translator_type, box_type, allocators_type, Predicates>,
Chris@16:             detail::rtree::iterators::distance_query_iterator<
Chris@16:                 value_type, options_type, translator_type, box_type, allocators_type, Predicates,
Chris@16:                 detail::predicates_find_distance<Predicates>::value
Chris@16:             >
Chris@16:         >::type iterator_type;
Chris@16: 
Chris@16:         if ( !m_members.root )
Chris@16:             return iterator_type(m_members.translator(), predicates);
Chris@16: 
Chris@16:         return iterator_type(m_members.root, m_members.translator(), predicates);
Chris@16:     }
Chris@16: 
Chris@16:     /*!
Chris@16:     \brief Returns the query iterator pointing at the end of the query range.
Chris@16: 
Chris@16:     This method returns the iterator which may be used to perform iterative queries. For the information
Chris@16:     about the predicates which may be passed to this method see query().
Chris@16:     
Chris@16:     The type of the returned iterator depends on the type of passed Predicates but the iterator of this type
Chris@16:     may be assigned to the variable of const_query_iterator type. If you'd like to use the type of the iterator
Chris@16:     returned by this method you may get the type e.g. by using C++11 decltype or Boost.Typeof library.
Chris@16: 
Chris@16:     The type of the iterator returned by this method is the same as the one returned by qbegin() to which
Chris@16:     the same predicates were passed.
Chris@16: 
Chris@16:     \par Example
Chris@16:     \verbatim
Chris@16:     // Store the result in the container using std::copy() - it requires both iterators of the same type
Chris@16:     std::copy(tree.qbegin(bgi::intersects(box)), tree.qend(bgi::intersects(box)), std::back_inserter(result));
Chris@16:     \endverbatim
Chris@16: 
Chris@16:     \par Throws
Chris@16:     If predicates copy throws.
Chris@16: 
Chris@16:     \param predicates   Predicates.
Chris@16:     
Chris@16:     \return             The iterator pointing at the end of the query range.
Chris@16:     */
Chris@16:     template <typename Predicates>
Chris@16:     typename boost::mpl::if_c<
Chris@16:         detail::predicates_count_distance<Predicates>::value == 0,
Chris@16:         detail::rtree::iterators::spatial_query_iterator<value_type, options_type, translator_type, box_type, allocators_type, Predicates>,
Chris@16:         detail::rtree::iterators::distance_query_iterator<
Chris@16:             value_type, options_type, translator_type, box_type, allocators_type, Predicates,
Chris@16:             detail::predicates_find_distance<Predicates>::value
Chris@16:         >
Chris@16:     >::type
Chris@16:     qend_(Predicates const& predicates) const
Chris@16:     {
Chris@16:         static const unsigned distance_predicates_count = detail::predicates_count_distance<Predicates>::value;
Chris@16:         BOOST_MPL_ASSERT_MSG((distance_predicates_count <= 1), PASS_ONLY_ONE_DISTANCE_PREDICATE, (Predicates));
Chris@16: 
Chris@16:         typedef typename boost::mpl::if_c<
Chris@16:             detail::predicates_count_distance<Predicates>::value == 0,
Chris@16:             detail::rtree::iterators::spatial_query_iterator<value_type, options_type, translator_type, box_type, allocators_type, Predicates>,
Chris@16:             detail::rtree::iterators::distance_query_iterator<
Chris@16:                 value_type, options_type, translator_type, box_type, allocators_type, Predicates,
Chris@16:                 detail::predicates_find_distance<Predicates>::value
Chris@16:             >
Chris@16:         >::type iterator_type;
Chris@16: 
Chris@16:         return iterator_type(m_members.translator(), predicates);
Chris@16:     }
Chris@16: 
Chris@16:     /*!
Chris@16:     \brief Returns the query iterator pointing at the end of the query range.
Chris@16: 
Chris@16:     This method returns the iterator which may be compared with the iterator returned by qbegin() in order to
Chris@16:     check if the query has ended.
Chris@16:     
Chris@16:     The type of the returned iterator is different than the type returned by qbegin() but the iterator of this type
Chris@16:     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
Chris@16:     method, which most certainly will be faster than the type-erased iterator, you may get the type
Chris@16:     e.g. by using C++11 decltype or Boost.Typeof library.
Chris@16: 
Chris@16:     The type of the iterator returned by this method is dfferent than the type returned by qbegin().
Chris@16: 
Chris@16:     \par Example
Chris@16:     \verbatim
Chris@16:     // Store the result in the container using std::copy() and type-erased iterators
Chris@16:     Rtree::const_query_iterator first = tree.qbegin(bgi::intersects(box));
Chris@16:     Rtree::const_query_iterator last = tree.qend();
Chris@16:     std::copy(first, last, std::back_inserter(result));
Chris@16: 
Chris@16:     // Boost.Typeof
Chris@16:     typedef BOOST_TYPEOF(tree.qbegin(bgi::nearest(pt, 10000))) Iter;
Chris@16:     for ( Iter it = tree.qbegin(bgi::nearest(pt, 10000)) ; it != tree.qend() ; ++it )
Chris@16:     {
Chris@16:         // do something with value
Chris@16:         if ( has_enough_nearest_values() )
Chris@16:             break;
Chris@16:     }
Chris@16:     \endverbatim
Chris@16: 
Chris@16:     \par Throws
Chris@16:     Nothing
Chris@16:     
Chris@16:     \return             The iterator pointing at the end of the query range.
Chris@16:     */
Chris@16:     detail::rtree::iterators::end_query_iterator<value_type, allocators_type>
Chris@16:     qend_() const
Chris@16:     {
Chris@16:         return detail::rtree::iterators::end_query_iterator<value_type, allocators_type>();
Chris@16:     }
Chris@16: 
Chris@16: public:
Chris@16: 
Chris@16:     /*!
Chris@16:     \brief Returns the number of stored values.
Chris@16: 
Chris@16:     \return         The number of stored values.
Chris@16: 
Chris@16:     \par Throws
Chris@16:     Nothing.
Chris@16:     */
Chris@16:     inline size_type size() const
Chris@16:     {
Chris@16:         return m_members.values_count;
Chris@16:     }
Chris@16: 
Chris@16:     /*!
Chris@16:     \brief Query if the container is empty.
Chris@16: 
Chris@16:     \return         true if the container is empty.
Chris@16: 
Chris@16:     \par Throws
Chris@16:     Nothing.
Chris@16:     */
Chris@16:     inline bool empty() const
Chris@16:     {
Chris@16:         return 0 == m_members.values_count;
Chris@16:     }
Chris@16: 
Chris@16:     /*!
Chris@16:     \brief Removes all values stored in the container.
Chris@16: 
Chris@16:     \par Throws
Chris@16:     Nothing.
Chris@16:     */
Chris@16:     inline void clear()
Chris@16:     {
Chris@16:         this->raw_destroy(*this);
Chris@16:     }
Chris@16: 
Chris@16:     /*!
Chris@16:     \brief Returns the box able to contain all values stored in the container.
Chris@16: 
Chris@16:     Returns the box able to contain all values stored in the container.
Chris@16:     If the container is empty the result of \c geometry::assign_inverse() is returned.
Chris@16: 
Chris@16:     \return     The box able to contain all values stored in the container or an invalid box if
Chris@16:                 there are no values in the container.
Chris@16: 
Chris@16:     \par Throws
Chris@16:     Nothing.
Chris@16:     */
Chris@16:     inline bounds_type bounds() const
Chris@16:     {
Chris@16:         bounds_type result;
Chris@16:         if ( !m_members.root )
Chris@16:         {
Chris@16:             geometry::assign_inverse(result);
Chris@16:             return result;
Chris@16:         }
Chris@16: 
Chris@16:         detail::rtree::visitors::children_box<value_type, options_type, translator_type, box_type, allocators_type>
Chris@16:             box_v(result, m_members.translator());
Chris@16:         detail::rtree::apply_visitor(box_v, *m_members.root);
Chris@16: 
Chris@16:         return result;
Chris@16:     }
Chris@16: 
Chris@16:     /*!
Chris@16:     \brief Count Values or Indexables stored in the container.
Chris@16:     
Chris@16:     For indexable_type it returns the number of values which indexables equals the parameter.
Chris@16:     For value_type it returns the number of values which equals the parameter.
Chris@16: 
Chris@16:     \param vori The value or indexable which will be counted.
Chris@16: 
Chris@16:     \return     The number of values found.
Chris@16: 
Chris@16:     \par Throws
Chris@16:     Nothing.
Chris@16:     */
Chris@16:     template <typename ValueOrIndexable>
Chris@16:     size_type count(ValueOrIndexable const& vori) const
Chris@16:     {
Chris@101:         // the input should be convertible to Value or Indexable type
Chris@16: 
Chris@101:         enum { as_val = 0, as_ind, dont_know };
Chris@101:         typedef boost::mpl::int_
Chris@101:             <
Chris@101:                 boost::is_same<ValueOrIndexable, value_type>::value ?
Chris@101:                     as_val :
Chris@101:                     boost::is_same<ValueOrIndexable, indexable_type>::value ?
Chris@101:                         as_ind :
Chris@101:                         boost::is_convertible<ValueOrIndexable, indexable_type>::value ?
Chris@101:                             as_ind :
Chris@101:                             boost::is_convertible<ValueOrIndexable, value_type>::value ?
Chris@101:                                 as_val :
Chris@101:                                 dont_know
Chris@101:             > variant;
Chris@16: 
Chris@101:         BOOST_MPL_ASSERT_MSG((variant::value != dont_know),
Chris@101:                              PASSED_OBJECT_NOT_CONVERTIBLE_TO_VALUE_NOR_INDEXABLE_TYPE,
Chris@101:                              (ValueOrIndexable));
Chris@16: 
Chris@101:         typedef typename boost::mpl::if_c
Chris@101:             <
Chris@101:                 variant::value == as_val,
Chris@101:                 value_type,
Chris@101:                 indexable_type
Chris@101:             >::type value_or_indexable;
Chris@101: 
Chris@101:         // NOTE: If an object of convertible but not the same type is passed
Chris@101:         // into the function, here a temporary will be created.
Chris@101:         return this->template raw_count<value_or_indexable>(vori);
Chris@16:     }
Chris@16: 
Chris@16:     /*!
Chris@16:     \brief Returns parameters.
Chris@16: 
Chris@16:     \return     The parameters object.
Chris@16: 
Chris@16:     \par Throws
Chris@16:     Nothing.
Chris@16:     */
Chris@16:     inline parameters_type parameters() const
Chris@16:     {
Chris@16:         return m_members.parameters();
Chris@16:     }
Chris@16: 
Chris@16:     /*!
Chris@16:     \brief Returns function retrieving Indexable from Value.
Chris@16: 
Chris@16:     \return     The indexable_getter object.
Chris@16: 
Chris@16:     \par Throws
Chris@16:     Nothing.
Chris@16:     */
Chris@16:     indexable_getter indexable_get() const
Chris@16:     {
Chris@16:         return m_members.indexable_getter();
Chris@16:     }
Chris@16: 
Chris@16:     /*!
Chris@16:     \brief Returns function comparing Values
Chris@16: 
Chris@16:     \return     The value_equal function.
Chris@16: 
Chris@16:     \par Throws
Chris@16:     Nothing.
Chris@16:     */
Chris@16:     value_equal value_eq() const
Chris@16:     {
Chris@16:         return m_members.equal_to();
Chris@16:     }
Chris@16: 
Chris@16:     /*!
Chris@16:     \brief Returns allocator used by the rtree.
Chris@16: 
Chris@16:     \return     The allocator.
Chris@16: 
Chris@16:     \par Throws
Chris@16:     If allocator copy constructor throws.
Chris@16:     */
Chris@16:     allocator_type get_allocator() const
Chris@16:     {
Chris@16:         return m_members.allocators().allocator();
Chris@16:     }
Chris@16: 
Chris@16: private:
Chris@16: 
Chris@16:     /*!
Chris@16:     \brief Returns the translator object.
Chris@16: 
Chris@16:     \return     The translator object.
Chris@16: 
Chris@16:     \par Throws
Chris@16:     Nothing.
Chris@16:     */
Chris@16:     inline translator_type translator() const
Chris@16:     {
Chris@16:         return m_members.translator();
Chris@16:     }
Chris@16: 
Chris@16:     /*!
Chris@16:     \brief Apply a visitor to the nodes structure in order to perform some operator.
Chris@16: 
Chris@16:     This function is not a part of the 'official' interface. However it makes
Chris@16:     possible e.g. to pass a visitor drawing the tree structure.
Chris@16: 
Chris@16:     \param visitor  The visitor object.
Chris@16: 
Chris@16:     \par Throws
Chris@16:     If Visitor::operator() throws.
Chris@16:     */
Chris@16:     template <typename Visitor>
Chris@16:     inline void apply_visitor(Visitor & visitor) const
Chris@16:     {
Chris@16:         if ( m_members.root )
Chris@16:             detail::rtree::apply_visitor(visitor, *m_members.root);
Chris@16:     }
Chris@16: 
Chris@16:     /*!
Chris@16:     \brief Returns the depth of the R-tree.
Chris@16: 
Chris@16:     This function is not a part of the 'official' interface.
Chris@16: 
Chris@16:     \return     The depth of the R-tree.
Chris@16: 
Chris@16:     \par Throws
Chris@16:     Nothing.
Chris@16:     */
Chris@16:     inline size_type depth() const
Chris@16:     {
Chris@16:         return m_members.leafs_level;
Chris@16:     }
Chris@16: 
Chris@16: private:
Chris@16: 
Chris@16:     /*!
Chris@16:     \pre Root node must exist - m_root != 0.
Chris@16: 
Chris@16:     \brief Insert a value to the index.
Chris@16: 
Chris@16:     \param value    The value which will be stored in the container.
Chris@16: 
Chris@16:     \par Exception-safety
Chris@16:     basic
Chris@16:     */
Chris@16:     inline void raw_insert(value_type const& value)
Chris@16:     {
Chris@16:         BOOST_GEOMETRY_INDEX_ASSERT(m_members.root, "The root must exist");
Chris@101:         // CONSIDER: alternative - ignore invalid indexable or throw an exception
Chris@16:         BOOST_GEOMETRY_INDEX_ASSERT(detail::is_valid(m_members.translator()(value)), "Indexable is invalid");
Chris@16: 
Chris@16:         detail::rtree::visitors::insert<
Chris@16:             value_type,
Chris@16:             value_type, options_type, translator_type, box_type, allocators_type,
Chris@16:             typename options_type::insert_tag
Chris@16:         > insert_v(m_members.root, m_members.leafs_level, value,
Chris@16:                    m_members.parameters(), m_members.translator(), m_members.allocators());
Chris@16: 
Chris@16:         detail::rtree::apply_visitor(insert_v, *m_members.root);
Chris@16: 
Chris@16: // TODO
Chris@16: // Think about this: If exception is thrown, may the root be removed?
Chris@16: // Or it is just cleared?
Chris@16: 
Chris@16: // TODO
Chris@16: // If exception is thrown, m_values_count may be invalid
Chris@16:         ++m_members.values_count;
Chris@16:     }
Chris@16: 
Chris@16:     /*!
Chris@16:     \brief Remove the value from the container.
Chris@16: 
Chris@16:     \param value    The value which will be removed from the container.
Chris@16: 
Chris@16:     \par Exception-safety
Chris@16:     basic
Chris@16:     */
Chris@16:     inline size_type raw_remove(value_type const& value)
Chris@16:     {
Chris@16:         // TODO: awulkiew - assert for correct value (indexable) ?
Chris@16:         BOOST_GEOMETRY_INDEX_ASSERT(m_members.root, "The root must exist");
Chris@16: 
Chris@16:         detail::rtree::visitors::remove<
Chris@16:             value_type, options_type, translator_type, box_type, allocators_type
Chris@16:         > remove_v(m_members.root, m_members.leafs_level, value,
Chris@16:                    m_members.parameters(), m_members.translator(), m_members.allocators());
Chris@16: 
Chris@16:         detail::rtree::apply_visitor(remove_v, *m_members.root);
Chris@16: 
Chris@16:         // If exception is thrown, m_values_count may be invalid
Chris@16: 
Chris@16:         if ( remove_v.is_value_removed() )
Chris@16:         {
Chris@16:             BOOST_GEOMETRY_INDEX_ASSERT(0 < m_members.values_count, "unexpected state");
Chris@16: 
Chris@16:             --m_members.values_count;
Chris@16: 
Chris@16:             return 1;
Chris@16:         }
Chris@16: 
Chris@16:         return 0;
Chris@16:     }
Chris@16: 
Chris@16:     /*!
Chris@16:     \brief Create an empty R-tree i.e. new empty root node and clear other attributes.
Chris@16: 
Chris@16:     \par Exception-safety
Chris@16:     strong
Chris@16:     */
Chris@16:     inline void raw_create()
Chris@16:     {
Chris@16:         BOOST_GEOMETRY_INDEX_ASSERT(0 == m_members.root, "the tree is already created");
Chris@16: 
Chris@16:         m_members.root = detail::rtree::create_node<allocators_type, leaf>::apply(m_members.allocators()); // MAY THROW (N: alloc)
Chris@16:         m_members.values_count = 0;
Chris@16:         m_members.leafs_level = 0;
Chris@16:     }
Chris@16: 
Chris@16:     /*!
Chris@16:     \brief Destroy the R-tree i.e. all nodes and clear attributes.
Chris@16: 
Chris@16:     \param t    The container which is going to be destroyed.
Chris@16: 
Chris@16:     \par Exception-safety
Chris@16:     nothrow
Chris@16:     */
Chris@16:     inline void raw_destroy(rtree & t)
Chris@16:     {
Chris@16:         if ( t.m_members.root )
Chris@16:         {
Chris@16:             detail::rtree::visitors::destroy<value_type, options_type, translator_type, box_type, allocators_type>
Chris@16:                 del_v(t.m_members.root, t.m_members.allocators());
Chris@16:             detail::rtree::apply_visitor(del_v, *t.m_members.root);
Chris@16: 
Chris@16:             t.m_members.root = 0;
Chris@16:         }
Chris@16:         t.m_members.values_count = 0;
Chris@16:         t.m_members.leafs_level = 0;
Chris@16:     }
Chris@16: 
Chris@16:     /*!
Chris@16:     \brief Copy the R-tree i.e. whole nodes structure, values and other attributes.
Chris@16:     It uses destination's allocators to create the new structure.
Chris@16: 
Chris@16:     \param src                  The source R-tree.
Chris@16:     \param dst                  The destination R-tree.
Chris@16:     \param copy_tr_and_params   If true, translator and parameters will also be copied.
Chris@16: 
Chris@16:     \par Exception-safety
Chris@16:     strong
Chris@16:     */
Chris@16:     inline void raw_copy(rtree const& src, rtree & dst, bool copy_tr_and_params) const
Chris@16:     {
Chris@16:         detail::rtree::visitors::copy<value_type, options_type, translator_type, box_type, allocators_type>
Chris@16:             copy_v(dst.m_members.allocators());
Chris@16: 
Chris@16:         if ( src.m_members.root )
Chris@16:             detail::rtree::apply_visitor(copy_v, *src.m_members.root);                      // MAY THROW (V, E: alloc, copy, N: alloc)
Chris@16: 
Chris@16:         if ( copy_tr_and_params )
Chris@16:         {
Chris@16:             dst.m_members.indexable_getter() = src.m_members.indexable_getter();
Chris@16:             dst.m_members.equal_to() = src.m_members.equal_to();
Chris@16:             dst.m_members.parameters() = src.m_members.parameters();
Chris@16:         }
Chris@16: 
Chris@101:         // TODO use subtree_destroyer
Chris@16:         if ( dst.m_members.root )
Chris@16:         {
Chris@16:             detail::rtree::visitors::destroy<value_type, options_type, translator_type, box_type, allocators_type>
Chris@16:                 del_v(dst.m_members.root, dst.m_members.allocators());
Chris@16:             detail::rtree::apply_visitor(del_v, *dst.m_members.root);
Chris@16:             dst.m_members.root = 0;
Chris@16:         }
Chris@16: 
Chris@16:         dst.m_members.root = copy_v.result;
Chris@16:         dst.m_members.values_count = src.m_members.values_count;
Chris@16:         dst.m_members.leafs_level = src.m_members.leafs_level;
Chris@16:     }
Chris@16: 
Chris@16:     /*!
Chris@101:     \brief Insert a value corresponding to convertible object into the index.
Chris@101: 
Chris@101:     \param val_conv    The object convertible to value.
Chris@101: 
Chris@101:     \par Exception-safety
Chris@101:     basic
Chris@101:     */
Chris@101:     template <typename ValueConvertible>
Chris@101:     inline void insert_dispatch(ValueConvertible const& val_conv,
Chris@101:                                 boost::mpl::bool_<true> const& /*is_convertible*/)
Chris@101:     {
Chris@101:         if ( !m_members.root )
Chris@101:             this->raw_create();
Chris@101: 
Chris@101:         this->raw_insert(val_conv);
Chris@101:     }
Chris@101: 
Chris@101:     /*!
Chris@101:     \brief Insert a range of values into the index.
Chris@101: 
Chris@101:     \param rng    The range of values.
Chris@101: 
Chris@101:     \par Exception-safety
Chris@101:     basic
Chris@101:     */
Chris@101:     template <typename Range>
Chris@101:     inline void insert_dispatch(Range const& rng,
Chris@101:                                 boost::mpl::bool_<false> const& /*is_convertible*/)
Chris@101:     {
Chris@101:         BOOST_MPL_ASSERT_MSG((detail::is_range<Range>::value),
Chris@101:                              PASSED_OBJECT_IS_NOT_CONVERTIBLE_TO_VALUE_NOR_A_RANGE,
Chris@101:                              (Range));
Chris@101: 
Chris@101:         if ( !m_members.root )
Chris@101:             this->raw_create();
Chris@101: 
Chris@101:         typedef typename boost::range_const_iterator<Range>::type It;
Chris@101:         for ( It it = boost::const_begin(rng); it != boost::const_end(rng) ; ++it )
Chris@101:             this->raw_insert(*it);
Chris@101:     }
Chris@101: 
Chris@101:     /*!
Chris@101:     \brief Remove a value corresponding to convertible object from the index.
Chris@101: 
Chris@101:     \param val_conv    The object convertible to value.
Chris@101: 
Chris@101:     \par Exception-safety
Chris@101:     basic
Chris@101:     */
Chris@101:     template <typename ValueConvertible>
Chris@101:     inline size_type remove_dispatch(ValueConvertible const& val_conv,
Chris@101:                                      boost::mpl::bool_<true> const& /*is_convertible*/)
Chris@101:     {
Chris@101:         return this->raw_remove(val_conv);
Chris@101:     }
Chris@101: 
Chris@101:     /*!
Chris@101:     \brief Remove a range of values from the index.
Chris@101: 
Chris@101:     \param rng    The range of values which will be removed from the container.
Chris@101: 
Chris@101:     \par Exception-safety
Chris@101:     basic
Chris@101:     */
Chris@101:     template <typename Range>
Chris@101:     inline size_type remove_dispatch(Range const& rng,
Chris@101:                                      boost::mpl::bool_<false> const& /*is_convertible*/)
Chris@101:     {
Chris@101:         BOOST_MPL_ASSERT_MSG((detail::is_range<Range>::value),
Chris@101:                              PASSED_OBJECT_IS_NOT_CONVERTIBLE_TO_VALUE_NOR_A_RANGE,
Chris@101:                              (Range));
Chris@101: 
Chris@101:         size_type result = 0;
Chris@101:         typedef typename boost::range_const_iterator<Range>::type It;
Chris@101:         for ( It it = boost::const_begin(rng); it != boost::const_end(rng) ; ++it )
Chris@101:             result += this->raw_remove(*it);
Chris@101:         return result;
Chris@101:     }
Chris@101: 
Chris@101:     /*!
Chris@16:     \brief Return values meeting predicates.
Chris@16: 
Chris@16:     \par Exception-safety
Chris@16:     strong
Chris@16:     */
Chris@16:     template <typename Predicates, typename OutIter>
Chris@16:     size_type query_dispatch(Predicates const& predicates, OutIter out_it, boost::mpl::bool_<false> const& /*is_distance_predicate*/) const
Chris@16:     {
Chris@16:         detail::rtree::visitors::spatial_query<value_type, options_type, translator_type, box_type, allocators_type, Predicates, OutIter>
Chris@16:             find_v(m_members.translator(), predicates, out_it);
Chris@16: 
Chris@16:         detail::rtree::apply_visitor(find_v, *m_members.root);
Chris@16: 
Chris@16:         return find_v.found_count;
Chris@16:     }
Chris@16: 
Chris@16:     /*!
Chris@16:     \brief Perform nearest neighbour search.
Chris@16: 
Chris@16:     \par Exception-safety
Chris@16:     strong
Chris@16:     */
Chris@16:     template <typename Predicates, typename OutIter>
Chris@16:     size_type query_dispatch(Predicates const& predicates, OutIter out_it, boost::mpl::bool_<true> const& /*is_distance_predicate*/) const
Chris@16:     {
Chris@16:         static const unsigned distance_predicate_index = detail::predicates_find_distance<Predicates>::value;
Chris@16:         detail::rtree::visitors::distance_query<
Chris@16:             value_type,
Chris@16:             options_type,
Chris@16:             translator_type,
Chris@16:             box_type,
Chris@16:             allocators_type,
Chris@16:             Predicates,
Chris@16:             distance_predicate_index,
Chris@16:             OutIter
Chris@16:         > distance_v(m_members.parameters(), m_members.translator(), predicates, out_it);
Chris@16: 
Chris@16:         detail::rtree::apply_visitor(distance_v, *m_members.root);
Chris@16: 
Chris@16:         return distance_v.finish();
Chris@16:     }
Chris@101:     
Chris@101:     /*!
Chris@101:     \brief Count elements corresponding to value or indexable.
Chris@101: 
Chris@101:     \par Exception-safety
Chris@101:     strong
Chris@101:     */
Chris@101:     template <typename ValueOrIndexable>
Chris@101:     size_type raw_count(ValueOrIndexable const& vori) const
Chris@101:     {
Chris@101:         if ( !m_members.root )
Chris@101:             return 0;
Chris@101: 
Chris@101:         detail::rtree::visitors::count
Chris@101:             <
Chris@101:                 ValueOrIndexable,
Chris@101:                 value_type,
Chris@101:                 options_type,
Chris@101:                 translator_type,
Chris@101:                 box_type,
Chris@101:                 allocators_type
Chris@101:             > count_v(vori, m_members.translator());
Chris@101: 
Chris@101:         detail::rtree::apply_visitor(count_v, *m_members.root);
Chris@101: 
Chris@101:         return count_v.found_count;
Chris@101:     }
Chris@16: 
Chris@16:     struct members_holder
Chris@16:         : public translator_type
Chris@16:         , public Parameters
Chris@16:         , public allocators_type
Chris@16:     {
Chris@16:     private:
Chris@16:         members_holder(members_holder const&);
Chris@16:         members_holder & operator=(members_holder const&);
Chris@16: 
Chris@16:     public:
Chris@16:         template <typename IndGet, typename ValEq, typename Alloc>
Chris@16:         members_holder(IndGet const& ind_get,
Chris@16:                        ValEq const& val_eq,
Chris@16:                        Parameters const& parameters,
Chris@16:                        BOOST_FWD_REF(Alloc) alloc)
Chris@16:             : translator_type(ind_get, val_eq)
Chris@16:             , Parameters(parameters)
Chris@16:             , allocators_type(boost::forward<Alloc>(alloc))
Chris@16:             , values_count(0)
Chris@16:             , leafs_level(0)
Chris@16:             , root(0)
Chris@16:         {}
Chris@16: 
Chris@16:         template <typename IndGet, typename ValEq>
Chris@16:         members_holder(IndGet const& ind_get,
Chris@16:                        ValEq const& val_eq,
Chris@16:                        Parameters const& parameters)
Chris@16:             : translator_type(ind_get, val_eq)
Chris@16:             , Parameters(parameters)
Chris@16:             , allocators_type()
Chris@16:             , values_count(0)
Chris@16:             , leafs_level(0)
Chris@16:             , root(0)
Chris@16:         {}
Chris@16: 
Chris@16:         translator_type const& translator() const { return *this; }
Chris@16: 
Chris@16:         IndexableGetter const& indexable_getter() const { return *this; }
Chris@16:         IndexableGetter & indexable_getter() { return *this; }
Chris@16:         EqualTo const& equal_to() const { return *this; }
Chris@16:         EqualTo & equal_to() { return *this; }
Chris@16:         Parameters const& parameters() const { return *this; }
Chris@16:         Parameters & parameters() { return *this; }
Chris@16:         allocators_type const& allocators() const { return *this; }
Chris@16:         allocators_type & allocators() { return *this; }
Chris@16: 
Chris@16:         size_type values_count;
Chris@16:         size_type leafs_level;
Chris@16:         node_pointer root;
Chris@16:     };
Chris@16: 
Chris@16:     members_holder m_members;
Chris@16: };
Chris@16: 
Chris@16: /*!
Chris@16: \brief Insert a value to the index.
Chris@16: 
Chris@16: It calls <tt>rtree::insert(value_type const&)</tt>.
Chris@16: 
Chris@16: \ingroup rtree_functions
Chris@16: 
Chris@16: \param tree The spatial index.
Chris@16: \param v    The value which will be stored in the index.
Chris@16: */
Chris@16: template <typename Value, typename Parameters, typename IndexableGetter, typename EqualTo, typename Allocator>
Chris@101: inline void insert(rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator> & tree,
Chris@101:                    Value const& v)
Chris@16: {
Chris@16:     tree.insert(v);
Chris@16: }
Chris@16: 
Chris@16: /*!
Chris@16: \brief Insert a range of values to the index.
Chris@16: 
Chris@16: It calls <tt>rtree::insert(Iterator, Iterator)</tt>.
Chris@16: 
Chris@16: \ingroup rtree_functions
Chris@16: 
Chris@16: \param tree     The spatial index.
Chris@16: \param first    The beginning of the range of values.
Chris@16: \param last     The end of the range of values.
Chris@16: */
Chris@101: template<typename Value, typename Parameters, typename IndexableGetter, typename EqualTo, typename Allocator,
Chris@101:          typename Iterator>
Chris@101: inline void insert(rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator> & tree,
Chris@101:                    Iterator first, Iterator last)
Chris@16: {
Chris@16:     tree.insert(first, last);
Chris@16: }
Chris@16: 
Chris@16: /*!
Chris@101: \brief Insert a value created using convertible object or a range of values to the index.
Chris@16: 
Chris@101: It calls <tt>rtree::insert(ConvertibleOrRange const&)</tt>.
Chris@16: 
Chris@16: \ingroup rtree_functions
Chris@16: 
Chris@101: \param tree             The spatial index.
Chris@101: \param conv_or_rng      The object of type convertible to value_type or a range of values.
Chris@16: */
Chris@101: template<typename Value, typename Parameters, typename IndexableGetter, typename EqualTo, typename Allocator,
Chris@101:          typename ConvertibleOrRange>
Chris@101: inline void insert(rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator> & tree,
Chris@101:                    ConvertibleOrRange const& conv_or_rng)
Chris@16: {
Chris@101:     tree.insert(conv_or_rng);
Chris@16: }
Chris@16: 
Chris@16: /*!
Chris@16: \brief Remove a value from the container.
Chris@16: 
Chris@16: Remove a value from the container. In contrast to the \c std::set or <tt>std::map erase()</tt> method
Chris@16: this function removes only one value from the container.
Chris@16: 
Chris@16: It calls <tt>rtree::remove(value_type const&)</tt>.
Chris@16: 
Chris@16: \ingroup rtree_functions
Chris@16: 
Chris@16: \param tree The spatial index.
Chris@16: \param v    The value which will be removed from the index.
Chris@16: 
Chris@16: \return     1 if value was removed, 0 otherwise.
Chris@16: */
Chris@16: template <typename Value, typename Parameters, typename IndexableGetter, typename EqualTo, typename Allocator>
Chris@16: inline typename rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator>::size_type
Chris@101: remove(rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator> & tree,
Chris@101:        Value const& v)
Chris@16: {
Chris@16:     return tree.remove(v);
Chris@16: }
Chris@16: 
Chris@16: /*!
Chris@16: \brief Remove a range of values from the container.
Chris@16: 
Chris@16: Remove a range of values from the container. In contrast to the \c std::set or <tt>std::map erase()</tt> method
Chris@16: it doesn't take iterators pointing to values stored in this container. It removes values equal
Chris@16: to these passed as a range. Furthermore this function removes only one value for each one passed
Chris@16: in the range, not all equal values.
Chris@16: 
Chris@16: It calls <tt>rtree::remove(Iterator, Iterator)</tt>.
Chris@16: 
Chris@16: \ingroup rtree_functions
Chris@16: 
Chris@16: \param tree     The spatial index.
Chris@16: \param first    The beginning of the range of values.
Chris@16: \param last     The end of the range of values.
Chris@16: 
Chris@16: \return         The number of removed values.
Chris@16: */
Chris@101: template<typename Value, typename Parameters, typename IndexableGetter, typename EqualTo, typename Allocator,
Chris@101:          typename Iterator>
Chris@16: inline typename rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator>::size_type
Chris@101: remove(rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator> & tree,
Chris@101:        Iterator first, Iterator last)
Chris@16: {
Chris@16:     return tree.remove(first, last);
Chris@16: }
Chris@16: 
Chris@16: /*!
Chris@101: \brief Remove a value corresponding to an object convertible to it or a range of values from the container.
Chris@16: 
Chris@101: Remove a value corresponding to an object convertible to it or a range of values from the container.
Chris@101: In contrast to the \c std::set or <tt>std::map erase()</tt> method
Chris@16: it removes values equal to these passed as a range. Furthermore this method removes only
Chris@16: one value for each one passed in the range, not all equal values.
Chris@16: 
Chris@101: It calls <tt>rtree::remove(ConvertibleOrRange const&)</tt>.
Chris@16: 
Chris@16: \ingroup rtree_functions
Chris@16: 
Chris@101: \param tree                 The spatial index.
Chris@101: \param conv_or_rng      The object of type convertible to value_type or the range of values.
Chris@16: 
Chris@16: \return         The number of removed values.
Chris@16: */
Chris@101: template<typename Value, typename Parameters, typename IndexableGetter, typename EqualTo, typename Allocator,
Chris@101:          typename ConvertibleOrRange>
Chris@16: inline typename rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator>::size_type
Chris@101: remove(rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator> & tree,
Chris@101:        ConvertibleOrRange const& conv_or_rng)
Chris@16: {
Chris@101:     return tree.remove(conv_or_rng);
Chris@16: }
Chris@16: 
Chris@16: /*!
Chris@16: \brief Finds values meeting passed predicates e.g. nearest to some Point and/or intersecting some Box.
Chris@16: 
Chris@16: This query function performs spatial and k-nearest neighbor searches. It allows to pass a set of predicates.
Chris@16: Values will be returned only if all predicates are met.
Chris@16: 
Chris@16: <b>Spatial predicates</b>
Chris@16:     
Chris@16: Spatial predicates may be generated by one of the functions listed below:
Chris@16: \li \c boost::geometry::index::contains(),
Chris@16: \li \c boost::geometry::index::covered_by(),
Chris@16: \li \c boost::geometry::index::covers(),
Chris@16: \li \c boost::geometry::index::disjoint(),
Chris@16: \li \c boost::geometry::index::intersects(),
Chris@16: \li \c boost::geometry::index::overlaps(),
Chris@16: \li \c boost::geometry::index::within(),
Chris@16: 
Chris@16: It is possible to negate spatial predicates:
Chris@16: \li <tt>! boost::geometry::index::contains()</tt>,
Chris@16: \li <tt>! boost::geometry::index::covered_by()</tt>,
Chris@16: \li <tt>! boost::geometry::index::covers()</tt>,
Chris@16: \li <tt>! boost::geometry::index::disjoint()</tt>,
Chris@16: \li <tt>! boost::geometry::index::intersects()</tt>,
Chris@16: \li <tt>! boost::geometry::index::overlaps()</tt>,
Chris@16: \li <tt>! boost::geometry::index::within()</tt>
Chris@16: 
Chris@16: <b>Satisfies predicate</b>
Chris@16: 
Chris@16: This is a special kind of predicate which allows to pass a user-defined function or function object which checks
Chris@16: if Value should be returned by the query. It's generated by:
Chris@16: \li \c boost::geometry::index::satisfies().
Chris@16: 
Chris@16: <b>Nearest predicate</b>
Chris@16: 
Chris@16: If the nearest predicate is passed a k-nearest neighbor search will be performed. This query will result
Chris@16: in returning k values to the output iterator. Only one nearest predicate may be passed to the query.
Chris@16: It may be generated by:
Chris@16: \li \c boost::geometry::index::nearest().
Chris@16:         
Chris@16: <b>Connecting predicates</b>
Chris@16: 
Chris@16: Predicates may be passed together connected with \c operator&&().
Chris@16: 
Chris@16: \par Example
Chris@16: \verbatim
Chris@16: // return elements intersecting box
Chris@16: bgi::query(tree, bgi::intersects(box), std::back_inserter(result));
Chris@16: // return elements intersecting poly but not within box
Chris@16: bgi::query(tree, bgi::intersects(poly) && !bgi::within(box), std::back_inserter(result));
Chris@16: // return elements overlapping box and meeting my_fun value predicate
Chris@16: bgi::query(tree, bgi::overlaps(box) && bgi::satisfies(my_fun), std::back_inserter(result));
Chris@16: // return 5 elements nearest to pt and elements are intersecting box
Chris@16: bgi::query(tree, bgi::nearest(pt, 5) && bgi::intersects(box), std::back_inserter(result));
Chris@16: \endverbatim
Chris@16: 
Chris@16: \par Throws
Chris@16: If Value copy constructor or copy assignment throws.
Chris@16: 
Chris@16: \warning
Chris@16: Only one \c nearest() perdicate may be passed to the query. Passing more of them results in compile-time error.
Chris@16: 
Chris@16: \ingroup rtree_functions
Chris@16: 
Chris@16: \param tree         The rtree.
Chris@16: \param predicates   Predicates.
Chris@16: \param out_it       The output iterator, e.g. generated by std::back_inserter().
Chris@16: 
Chris@16: \return             The number of values found.
Chris@16: */
Chris@16: template <typename Value, typename Parameters, typename IndexableGetter, typename EqualTo, typename Allocator,
Chris@16:           typename Predicates, typename OutIter> inline
Chris@16: typename rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator>::size_type
Chris@16: query(rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator> const& tree,
Chris@16:       Predicates const& predicates,
Chris@16:       OutIter out_it)
Chris@16: {
Chris@16:     return tree.query(predicates, out_it);
Chris@16: }
Chris@16: 
Chris@16: /*!
Chris@16: \brief Returns the query iterator pointing at the begin of the query range.
Chris@16: 
Chris@16: This method returns the iterator which may be used to perform iterative queries. For the information
Chris@16: about the predicates which may be passed to this method see query().
Chris@16:     
Chris@16: \par Example
Chris@16: \verbatim
Chris@16:     
Chris@16: for ( Rtree::const_query_iterator it = qbegin(tree, bgi::nearest(pt, 10000)) ;
Chris@16:         it != qend(tree) ; ++it )
Chris@16: {
Chris@16:     // do something with value
Chris@16:     if ( has_enough_nearest_values() )
Chris@16:         break;
Chris@16: }
Chris@16: \endverbatim
Chris@16: 
Chris@16: \par Throws
Chris@16: If predicates copy throws.
Chris@16: If allocation throws.
Chris@16: 
Chris@16: \ingroup rtree_functions
Chris@16: 
Chris@16: \param tree         The rtree.
Chris@16: \param predicates   Predicates.
Chris@16:     
Chris@16: \return             The iterator pointing at the begin of the query range.
Chris@16: */
Chris@16: template <typename Value, typename Parameters, typename IndexableGetter, typename EqualTo, typename Allocator,
Chris@16:           typename Predicates> inline
Chris@16: typename rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator>::const_query_iterator
Chris@16: qbegin(rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator> const& tree,
Chris@16:        Predicates const& predicates)
Chris@16: {
Chris@16:     return tree.qbegin(predicates);
Chris@16: }
Chris@16: 
Chris@16: /*!
Chris@16: \brief Returns the query iterator pointing at the end of the query range.
Chris@16: 
Chris@16: This method returns the iterator which may be used to check if the query has ended.
Chris@16:     
Chris@16: \par Example
Chris@16: \verbatim
Chris@16:     
Chris@16: for ( Rtree::const_query_iterator it = qbegin(tree, bgi::nearest(pt, 10000)) ;
Chris@16:       it != qend(tree) ; ++it )
Chris@16: {
Chris@16:     // do something with value
Chris@16:     if ( has_enough_nearest_values() )
Chris@16:         break;
Chris@16: }
Chris@16: \endverbatim
Chris@16: 
Chris@16: \par Throws
Chris@16: Nothing
Chris@16: 
Chris@16: \ingroup rtree_functions
Chris@16:     
Chris@16: \return             The iterator pointing at the end of the query range.
Chris@16: */
Chris@16: template <typename Value, typename Parameters, typename IndexableGetter, typename EqualTo, typename Allocator> inline
Chris@16: typename rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator>::const_query_iterator
Chris@16: qend(rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator> const& tree)
Chris@16: {
Chris@16:     return tree.qend();
Chris@16: }
Chris@16: 
Chris@16: /*!
Chris@16: \brief Remove all values from the index.
Chris@16: 
Chris@16: It calls \c rtree::clear().
Chris@16: 
Chris@16: \ingroup rtree_functions
Chris@16: 
Chris@16: \param tree     The spatial index.
Chris@16: */
Chris@16: template <typename Value, typename Parameters, typename IndexableGetter, typename EqualTo, typename Allocator>
Chris@16: inline void clear(rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator> & tree)
Chris@16: {
Chris@16:     return tree.clear();
Chris@16: }
Chris@16: 
Chris@16: /*!
Chris@16: \brief Get the number of values stored in the index.
Chris@16: 
Chris@16: It calls \c rtree::size().
Chris@16: 
Chris@16: \ingroup rtree_functions
Chris@16: 
Chris@16: \param tree     The spatial index.
Chris@16: 
Chris@16: \return         The number of values stored in the index.
Chris@16: */
Chris@16: template <typename Value, typename Parameters, typename IndexableGetter, typename EqualTo, typename Allocator>
Chris@16: inline size_t size(rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator> const& tree)
Chris@16: {
Chris@16:     return tree.size();
Chris@16: }
Chris@16: 
Chris@16: /*!
Chris@16: \brief Query if there are no values stored in the index.
Chris@16: 
Chris@16: It calls \c rtree::empty().
Chris@16: 
Chris@16: \ingroup rtree_functions
Chris@16: 
Chris@16: \param tree     The spatial index.
Chris@16: 
Chris@16: \return         true if there are no values in the index.
Chris@16: */
Chris@16: template <typename Value, typename Parameters, typename IndexableGetter, typename EqualTo, typename Allocator>
Chris@16: inline bool empty(rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator> const& tree)
Chris@16: {
Chris@16:     return tree.bounds();
Chris@16: }
Chris@16: 
Chris@16: /*!
Chris@16: \brief Get the box containing all stored values or an invalid box if the index has no values.
Chris@16: 
Chris@16: It calls \c rtree::envelope().
Chris@16: 
Chris@16: \ingroup rtree_functions
Chris@16: 
Chris@16: \param tree     The spatial index.
Chris@16: 
Chris@16: \return         The box containing all stored values or an invalid box.
Chris@16: */
Chris@16: template <typename Value, typename Parameters, typename IndexableGetter, typename EqualTo, typename Allocator>
Chris@16: inline typename rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator>::bounds_type
Chris@16: bounds(rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator> const& tree)
Chris@16: {
Chris@16:     return tree.bounds();
Chris@16: }
Chris@16: 
Chris@16: /*!
Chris@16: \brief Exchanges the contents of the container with those of other.
Chris@16: 
Chris@16: It calls \c rtree::swap().
Chris@16: 
Chris@16: \ingroup rtree_functions
Chris@16: 
Chris@16: \param l     The first rtree.
Chris@16: \param r     The second rtree.
Chris@16: */
Chris@16: template <typename Value, typename Parameters, typename IndexableGetter, typename EqualTo, typename Allocator>
Chris@16: inline void swap(rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator> & l,
Chris@16:                  rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator> & r)
Chris@16: {
Chris@16:     return l.swap(r);
Chris@16: }
Chris@16: 
Chris@16: }}} // namespace boost::geometry::index
Chris@16: 
Chris@101: // TODO: don't include the implementation at the end of the file
Chris@101: #include <boost/geometry/algorithms/detail/comparable_distance/implementation.hpp>
Chris@101: 
Chris@16: #include <boost/geometry/index/detail/config_end.hpp>
Chris@16: 
Chris@16: #endif // BOOST_GEOMETRY_INDEX_RTREE_HPP