rtree.hpp

// Boost.Geometry Index
//
// R-tree implementation
//
// Copyright (c) 2008 Federico J. Fernandez.
// Copyright (c) 2011-2015 Adam Wulkiewicz, Lodz, Poland.
//
// Use, modification and distribution is subject to the Boost Software License,
// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)

#ifndef BOOST_GEOMETRY_INDEX_RTREE_HPP
#define BOOST_GEOMETRY_INDEX_RTREE_HPP

// STD
#include <algorithm>

// Boost
#include <boost/tuple/tuple.hpp>
#include <boost/move/move.hpp>

// Boost.Geometry
#include <boost/geometry/algorithms/detail/comparable_distance/interface.hpp>
#include <boost/geometry/algorithms/centroid.hpp>
#include <boost/geometry/algorithms/covered_by.hpp>
#include <boost/geometry/algorithms/disjoint.hpp>
#include <boost/geometry/algorithms/equals.hpp>
#include <boost/geometry/algorithms/intersects.hpp>
#include <boost/geometry/algorithms/overlaps.hpp>
#include <boost/geometry/algorithms/touches.hpp>
#include <boost/geometry/algorithms/within.hpp>

#include <boost/geometry/geometries/point.hpp>
#include <boost/geometry/geometries/box.hpp>

#include <boost/geometry/strategies/strategies.hpp>

// Boost.Geometry.Index
#include <boost/geometry/index/detail/config_begin.hpp>

#include <boost/geometry/index/detail/assert.hpp>
#include <boost/geometry/index/detail/exception.hpp>

#include <boost/geometry/index/detail/rtree/options.hpp>

#include <boost/geometry/index/indexable.hpp>
#include <boost/geometry/index/equal_to.hpp>

#include <boost/geometry/index/detail/translator.hpp>

#include <boost/geometry/index/predicates.hpp>
#include <boost/geometry/index/distance_predicates.hpp>
#include <boost/geometry/index/detail/rtree/adaptors.hpp>

#include <boost/geometry/index/detail/meta.hpp>
#include <boost/geometry/index/detail/utilities.hpp>
#include <boost/geometry/index/detail/rtree/node/node.hpp>

#include <boost/geometry/index/detail/algorithms/is_valid.hpp>

#include <boost/geometry/index/detail/rtree/visitors/insert.hpp>
#include <boost/geometry/index/detail/rtree/visitors/iterator.hpp>
#include <boost/geometry/index/detail/rtree/visitors/remove.hpp>
#include <boost/geometry/index/detail/rtree/visitors/copy.hpp>
#include <boost/geometry/index/detail/rtree/visitors/destroy.hpp>
#include <boost/geometry/index/detail/rtree/visitors/spatial_query.hpp>
#include <boost/geometry/index/detail/rtree/visitors/distance_query.hpp>
#include <boost/geometry/index/detail/rtree/visitors/count.hpp>
#include <boost/geometry/index/detail/rtree/visitors/children_box.hpp>

#include <boost/geometry/index/detail/rtree/linear/linear.hpp>
#include <boost/geometry/index/detail/rtree/quadratic/quadratic.hpp>
#include <boost/geometry/index/detail/rtree/rstar/rstar.hpp>
//#include <boost/geometry/extensions/index/detail/rtree/kmeans/kmeans.hpp>

#include <boost/geometry/index/detail/rtree/pack_create.hpp>

#include <boost/geometry/index/inserter.hpp>

#include <boost/geometry/index/detail/rtree/utilities/view.hpp>

#include <boost/geometry/index/detail/rtree/iterators.hpp>
#include <boost/geometry/index/detail/rtree/query_iterators.hpp>

#ifdef BOOST_GEOMETRY_INDEX_DETAIL_EXPERIMENTAL
// serialization
#include <boost/geometry/index/detail/serialization.hpp>
#endif

// TODO change the name to bounding_tree

namespace boost { namespace geometry { namespace index {

template <
    typename Value,
    typename Parameters,
    typename IndexableGetter = index::indexable<Value>,
    typename EqualTo = index::equal_to<Value>,
    typename Allocator = std::allocator<Value>
>
class rtree
{
    BOOST_COPYABLE_AND_MOVABLE(rtree)

public:
    typedef Value value_type;
    typedef Parameters parameters_type;
    typedef IndexableGetter indexable_getter;
    typedef EqualTo value_equal;
    typedef Allocator allocator_type;

    // TODO: SHOULD THIS TYPE BE REMOVED?
    typedef typename index::detail::indexable_type<
        detail::translator<IndexableGetter, EqualTo>
    >::type indexable_type;

    typedef geometry::model::box<
                geometry::model::point<
                    typename coordinate_type<indexable_type>::type,
                    dimension<indexable_type>::value,
                    typename coordinate_system<indexable_type>::type
                >
            >
    bounds_type;

private:

    typedef detail::translator<IndexableGetter, EqualTo> translator_type;

    typedef bounds_type box_type;
    typedef typename detail::rtree::options_type<Parameters>::type options_type;
    typedef typename options_type::node_tag node_tag;
    typedef detail::rtree::allocators<allocator_type, value_type, typename options_type::parameters_type, box_type, node_tag> allocators_type;

    typedef typename detail::rtree::node<value_type, typename options_type::parameters_type, box_type, allocators_type, node_tag>::type node;
    typedef typename detail::rtree::internal_node<value_type, typename options_type::parameters_type, box_type, allocators_type, node_tag>::type internal_node;
    typedef typename detail::rtree::leaf<value_type, typename options_type::parameters_type, box_type, allocators_type, node_tag>::type leaf;

    typedef typename allocators_type::node_pointer node_pointer;
    typedef ::boost::container::allocator_traits<Allocator> allocator_traits_type;
    typedef detail::rtree::subtree_destroyer<value_type, options_type, translator_type, box_type, allocators_type> subtree_destroyer;

    friend class detail::rtree::utilities::view<rtree>;
#ifdef BOOST_GEOMETRY_INDEX_DETAIL_EXPERIMENTAL
    friend class detail::rtree::private_view<rtree>;
    friend class detail::rtree::const_private_view<rtree>;
#endif

public:

    typedef typename allocators_type::reference reference;
    typedef typename allocators_type::const_reference const_reference;
    typedef typename allocators_type::pointer pointer;
    typedef typename allocators_type::const_pointer const_pointer;
    typedef typename allocators_type::difference_type difference_type;
    typedef typename allocators_type::size_type size_type;

    typedef index::detail::rtree::iterators::iterator
        <
            value_type, options_type, translator_type, box_type, allocators_type
        > const_iterator;

    typedef index::detail::rtree::iterators::query_iterator
        <
            value_type, allocators_type
        > const_query_iterator;

public:

    inline explicit rtree(parameters_type const& parameters = parameters_type(),
                          indexable_getter const& getter = indexable_getter(),
                          value_equal const& equal = value_equal())
        : m_members(getter, equal, parameters)
    {}

    inline rtree(parameters_type const& parameters,
                 indexable_getter const& getter,
                 value_equal const& equal,
                 allocator_type const& allocator)
        : m_members(getter, equal, parameters, allocator)
    {}

    template<typename Iterator>
    inline rtree(Iterator first, Iterator last,
                 parameters_type const& parameters = parameters_type(),
                 indexable_getter const& getter = indexable_getter(),
                 value_equal const& equal = value_equal(),
                 allocator_type const& allocator = allocator_type())
        : m_members(getter, equal, parameters, allocator)
    {
        typedef detail::rtree::pack<value_type, options_type, translator_type, box_type, allocators_type> pack;
        size_type vc = 0, ll = 0;
        m_members.root = pack::apply(first, last, vc, ll,
                                     m_members.parameters(), m_members.translator(), m_members.allocators());
        m_members.values_count = vc;
        m_members.leafs_level = ll;
    }

    template<typename Range>
    inline explicit rtree(Range const& rng,
                          parameters_type const& parameters = parameters_type(),
                          indexable_getter const& getter = indexable_getter(),
                          value_equal const& equal = value_equal(),
                          allocator_type const& allocator = allocator_type())
        : m_members(getter, equal, parameters, allocator)
    {
        typedef detail::rtree::pack<value_type, options_type, translator_type, box_type, allocators_type> pack;
        size_type vc = 0, ll = 0;
        m_members.root = pack::apply(::boost::begin(rng), ::boost::end(rng), vc, ll,
                                     m_members.parameters(), m_members.translator(), m_members.allocators());
        m_members.values_count = vc;
        m_members.leafs_level = ll;
    }

    inline ~rtree()
    {
        this->raw_destroy(*this);
    }

    inline rtree(rtree const& src)
        : m_members(src.m_members.indexable_getter(),
                    src.m_members.equal_to(),
                    src.m_members.parameters(),
                    allocator_traits_type::select_on_container_copy_construction(src.get_allocator()))
    {
        this->raw_copy(src, *this, false);
    }

    inline rtree(rtree const& src, allocator_type const& allocator)
        : m_members(src.m_members.indexable_getter(),
                    src.m_members.equal_to(),
                    src.m_members.parameters(), allocator)
    {
        this->raw_copy(src, *this, false);
    }

    inline rtree(BOOST_RV_REF(rtree) src)
        : m_members(src.m_members.indexable_getter(),
                    src.m_members.equal_to(),
                    src.m_members.parameters(),
                    boost::move(src.m_members.allocators()))
    {
        boost::swap(m_members.values_count, src.m_members.values_count);
        boost::swap(m_members.leafs_level, src.m_members.leafs_level);
        boost::swap(m_members.root, src.m_members.root);
    }

    inline rtree(BOOST_RV_REF(rtree) src, allocator_type const& allocator)
        : m_members(src.m_members.indexable_getter(),
                    src.m_members.equal_to(),
                    src.m_members.parameters(),
                    allocator)
    {
        if ( src.m_members.allocators() == allocator )
        {
            boost::swap(m_members.values_count, src.m_members.values_count);
            boost::swap(m_members.leafs_level, src.m_members.leafs_level);
            boost::swap(m_members.root, src.m_members.root);
        }
        else
        {
            this->raw_copy(src, *this, false);
        }
    }

    inline rtree & operator=(BOOST_COPY_ASSIGN_REF(rtree) src)
    {
        if ( &src != this )
        {
            allocators_type & this_allocs = m_members.allocators();
            allocators_type const& src_allocs = src.m_members.allocators();

            // NOTE: if propagate is true for std allocators on darwin 4.2.1, glibc++
            // (allocators stored as base classes of members_holder)
            // copying them changes values_count, in this case it doesn't cause errors since data must be copied
            
            typedef boost::mpl::bool_<
                allocator_traits_type::propagate_on_container_copy_assignment::value
            > propagate;
            
            if ( propagate::value && !(this_allocs == src_allocs) )
                this->raw_destroy(*this);
            detail::assign_cond(this_allocs, src_allocs, propagate());

            // It uses m_allocators
            this->raw_copy(src, *this, true);
        }

        return *this;
    }

    inline rtree & operator=(BOOST_RV_REF(rtree) src)
    {
        if ( &src != this )
        {
            allocators_type & this_allocs = m_members.allocators();
            allocators_type & src_allocs = src.m_members.allocators();
            
            if ( this_allocs == src_allocs )
            {
                this->raw_destroy(*this);

                m_members.indexable_getter() = src.m_members.indexable_getter();
                m_members.equal_to() = src.m_members.equal_to();
                m_members.parameters() = src.m_members.parameters();

                boost::swap(m_members.values_count, src.m_members.values_count);
                boost::swap(m_members.leafs_level, src.m_members.leafs_level);
                boost::swap(m_members.root, src.m_members.root);

                // NOTE: if propagate is true for std allocators on darwin 4.2.1, glibc++
                // (allocators stored as base classes of members_holder)
                // moving them changes values_count
                
                typedef boost::mpl::bool_<
                    allocator_traits_type::propagate_on_container_move_assignment::value
                > propagate;
                detail::move_cond(this_allocs, src_allocs, propagate());
            }
            else
            {
// TODO - shouldn't here propagate_on_container_copy_assignment be checked like in operator=(const&)?

                // It uses m_allocators
                this->raw_copy(src, *this, true);
            }
        }

        return *this;
    }

    void swap(rtree & other)
    {
        boost::swap(m_members.indexable_getter(), other.m_members.indexable_getter());
        boost::swap(m_members.equal_to(), other.m_members.equal_to());
        boost::swap(m_members.parameters(), other.m_members.parameters());
        
        // NOTE: if propagate is true for std allocators on darwin 4.2.1, glibc++
        // (allocators stored as base classes of members_holder)
        // swapping them changes values_count
        
        typedef boost::mpl::bool_<
            allocator_traits_type::propagate_on_container_swap::value
        > propagate;
        detail::swap_cond(m_members.allocators(), other.m_members.allocators(), propagate());

        boost::swap(m_members.values_count, other.m_members.values_count);
        boost::swap(m_members.leafs_level, other.m_members.leafs_level);
        boost::swap(m_members.root, other.m_members.root);
    }

    inline void insert(value_type const& value)
    {
        if ( !m_members.root )
            this->raw_create();

        this->raw_insert(value);
    }

    template <typename Iterator>
    inline void insert(Iterator first, Iterator last)
    {
        if ( !m_members.root )
            this->raw_create();

        for ( ; first != last ; ++first )
            this->raw_insert(*first);
    }

    template <typename ConvertibleOrRange>
    inline void insert(ConvertibleOrRange const& conv_or_rng)
    {
        if ( !m_members.root )
            this->raw_create();

        typedef boost::mpl::bool_
            <
                boost::is_convertible<ConvertibleOrRange, value_type>::value
            > is_conv_t;

        this->insert_dispatch(conv_or_rng, is_conv_t());
    }

    inline size_type remove(value_type const& value)
    {
        if ( !m_members.root )
            return 0;

        return this->raw_remove(value);
    }

    template <typename Iterator>
    inline size_type remove(Iterator first, Iterator last)
    {
        size_type result = 0;

        if ( !m_members.root )
            return result;

        for ( ; first != last ; ++first )
            result += this->raw_remove(*first);
        return result;
    }

    template <typename ConvertibleOrRange>
    inline size_type remove(ConvertibleOrRange const& conv_or_rng)
    {
        if ( !m_members.root )
            return 0;

        typedef boost::mpl::bool_
            <
                boost::is_convertible<ConvertibleOrRange, value_type>::value
            > is_conv_t;

        return this->remove_dispatch(conv_or_rng, is_conv_t());
    }

    template <typename Predicates, typename OutIter>
    size_type query(Predicates const& predicates, OutIter out_it) const
    {
        if ( !m_members.root )
            return 0;

        static const unsigned distance_predicates_count = detail::predicates_count_distance<Predicates>::value;
        static const bool is_distance_predicate = 0 < distance_predicates_count;
        BOOST_MPL_ASSERT_MSG((distance_predicates_count <= 1), PASS_ONLY_ONE_DISTANCE_PREDICATE, (Predicates));

        return query_dispatch(predicates, out_it, boost::mpl::bool_<is_distance_predicate>());
    }

    template <typename Predicates>
    const_query_iterator qbegin(Predicates const& predicates) const
    {
        return const_query_iterator(qbegin_(predicates));
    }

    const_query_iterator qend() const
    {
        return const_query_iterator();
    }

#ifndef BOOST_GEOMETRY_INDEX_DETAIL_EXPERIMENTAL
private:
#endif

    template <typename Predicates>
    typename boost::mpl::if_c<
        detail::predicates_count_distance<Predicates>::value == 0,
        detail::rtree::iterators::spatial_query_iterator<value_type, options_type, translator_type, box_type, allocators_type, Predicates>,
        detail::rtree::iterators::distance_query_iterator<
            value_type, options_type, translator_type, box_type, allocators_type, Predicates,
            detail::predicates_find_distance<Predicates>::value
        >
    >::type
    qbegin_(Predicates const& predicates) const
    {
        static const unsigned distance_predicates_count = detail::predicates_count_distance<Predicates>::value;
        BOOST_MPL_ASSERT_MSG((distance_predicates_count <= 1), PASS_ONLY_ONE_DISTANCE_PREDICATE, (Predicates));

        typedef typename boost::mpl::if_c<
            detail::predicates_count_distance<Predicates>::value == 0,
            detail::rtree::iterators::spatial_query_iterator<value_type, options_type, translator_type, box_type, allocators_type, Predicates>,
            detail::rtree::iterators::distance_query_iterator<
                value_type, options_type, translator_type, box_type, allocators_type, Predicates,
                detail::predicates_find_distance<Predicates>::value
            >
        >::type iterator_type;

        if ( !m_members.root )
            return iterator_type(m_members.translator(), predicates);

        return iterator_type(m_members.root, m_members.translator(), predicates);
    }

    template <typename Predicates>
    typename boost::mpl::if_c<
        detail::predicates_count_distance<Predicates>::value == 0,
        detail::rtree::iterators::spatial_query_iterator<value_type, options_type, translator_type, box_type, allocators_type, Predicates>,
        detail::rtree::iterators::distance_query_iterator<
            value_type, options_type, translator_type, box_type, allocators_type, Predicates,
            detail::predicates_find_distance<Predicates>::value
        >
    >::type
    qend_(Predicates const& predicates) const
    {
        static const unsigned distance_predicates_count = detail::predicates_count_distance<Predicates>::value;
        BOOST_MPL_ASSERT_MSG((distance_predicates_count <= 1), PASS_ONLY_ONE_DISTANCE_PREDICATE, (Predicates));

        typedef typename boost::mpl::if_c<
            detail::predicates_count_distance<Predicates>::value == 0,
            detail::rtree::iterators::spatial_query_iterator<value_type, options_type, translator_type, box_type, allocators_type, Predicates>,
            detail::rtree::iterators::distance_query_iterator<
                value_type, options_type, translator_type, box_type, allocators_type, Predicates,
                detail::predicates_find_distance<Predicates>::value
            >
        >::type iterator_type;

        return iterator_type(m_members.translator(), predicates);
    }

    detail::rtree::iterators::end_query_iterator<value_type, allocators_type>
    qend_() const
    {
        return detail::rtree::iterators::end_query_iterator<value_type, allocators_type>();
    }

public:

    const_iterator begin() const
    {
        if ( !m_members.root )
            return const_iterator();

        return const_iterator(m_members.root);
    }

    const_iterator end() const
    {
        return const_iterator();
    }

    inline size_type size() const
    {
        return m_members.values_count;
    }

    inline bool empty() const
    {
        return 0 == m_members.values_count;
    }

    inline void clear()
    {
        this->raw_destroy(*this);
    }

    inline bounds_type bounds() const
    {
        bounds_type result;
        // in order to suppress the uninitialized variable warnings
        geometry::assign_inverse(result);

        if ( m_members.root )
        {
            detail::rtree::visitors::children_box<value_type, options_type, translator_type, box_type, allocators_type>
                box_v(result, m_members.translator());
            detail::rtree::apply_visitor(box_v, *m_members.root);
        }

        return result;
    }

    template <typename ValueOrIndexable>
    size_type count(ValueOrIndexable const& vori) const
    {
        if ( !m_members.root )
            return 0;

        // the input should be convertible to Value or Indexable type

        enum { as_val = 0, as_ind, dont_know };
        typedef boost::mpl::int_
            <
                boost::is_same<ValueOrIndexable, value_type>::value ?
                    as_val :
                    boost::is_same<ValueOrIndexable, indexable_type>::value ?
                        as_ind :
                        boost::is_convertible<ValueOrIndexable, indexable_type>::value ?
                            as_ind :
                            boost::is_convertible<ValueOrIndexable, value_type>::value ?
                                as_val :
                                dont_know
            > variant;

        BOOST_MPL_ASSERT_MSG((variant::value != dont_know),
                             PASSED_OBJECT_NOT_CONVERTIBLE_TO_VALUE_NOR_INDEXABLE_TYPE,
                             (ValueOrIndexable));

        typedef typename boost::mpl::if_c
            <
                variant::value == as_val,
                value_type,
                indexable_type
            >::type value_or_indexable;

        // NOTE: If an object of convertible but not the same type is passed
        // into the function, here a temporary will be created.
        return this->template raw_count<value_or_indexable>(vori);
    }

    inline parameters_type parameters() const
    {
        return m_members.parameters();
    }

    indexable_getter indexable_get() const
    {
        return m_members.indexable_getter();
    }

    value_equal value_eq() const
    {
        return m_members.equal_to();
    }

    allocator_type get_allocator() const
    {
        return m_members.allocators().allocator();
    }

private:

    inline translator_type translator() const
    {
        return m_members.translator();
    }

    template <typename Visitor>
    inline void apply_visitor(Visitor & visitor) const
    {
        if ( m_members.root )
            detail::rtree::apply_visitor(visitor, *m_members.root);
    }

    inline size_type depth() const
    {
        return m_members.leafs_level;
    }

private:

    inline void raw_insert(value_type const& value)
    {
        BOOST_GEOMETRY_INDEX_ASSERT(m_members.root, "The root must exist");
        // CONSIDER: alternative - ignore invalid indexable or throw an exception
        BOOST_GEOMETRY_INDEX_ASSERT(detail::is_valid(m_members.translator()(value)), "Indexable is invalid");

        detail::rtree::visitors::insert<
            value_type,
            value_type, options_type, translator_type, box_type, allocators_type,
            typename options_type::insert_tag
        > insert_v(m_members.root, m_members.leafs_level, value,
                   m_members.parameters(), m_members.translator(), m_members.allocators());

        detail::rtree::apply_visitor(insert_v, *m_members.root);

// TODO
// Think about this: If exception is thrown, may the root be removed?
// Or it is just cleared?

// TODO
// If exception is thrown, m_values_count may be invalid
        ++m_members.values_count;
    }

    inline size_type raw_remove(value_type const& value)
    {
        // TODO: awulkiew - assert for correct value (indexable) ?
        BOOST_GEOMETRY_INDEX_ASSERT(m_members.root, "The root must exist");

        detail::rtree::visitors::remove<
            value_type, options_type, translator_type, box_type, allocators_type
        > remove_v(m_members.root, m_members.leafs_level, value,
                   m_members.parameters(), m_members.translator(), m_members.allocators());

        detail::rtree::apply_visitor(remove_v, *m_members.root);

        // If exception is thrown, m_values_count may be invalid

        if ( remove_v.is_value_removed() )
        {
            BOOST_GEOMETRY_INDEX_ASSERT(0 < m_members.values_count, "unexpected state");

            --m_members.values_count;

            return 1;
        }

        return 0;
    }

    inline void raw_create()
    {
        BOOST_GEOMETRY_INDEX_ASSERT(0 == m_members.root, "the tree is already created");

        m_members.root = detail::rtree::create_node<allocators_type, leaf>::apply(m_members.allocators()); // MAY THROW (N: alloc)
        m_members.values_count = 0;
        m_members.leafs_level = 0;
    }

    inline void raw_destroy(rtree & t)
    {
        if ( t.m_members.root )
        {
            detail::rtree::visitors::destroy<value_type, options_type, translator_type, box_type, allocators_type>
                del_v(t.m_members.root, t.m_members.allocators());
            detail::rtree::apply_visitor(del_v, *t.m_members.root);

            t.m_members.root = 0;
        }
        t.m_members.values_count = 0;
        t.m_members.leafs_level = 0;
    }

    inline void raw_copy(rtree const& src, rtree & dst, bool copy_tr_and_params) const
    {
        detail::rtree::visitors::copy<value_type, options_type, translator_type, box_type, allocators_type>
            copy_v(dst.m_members.allocators());

        if ( src.m_members.root )
            detail::rtree::apply_visitor(copy_v, *src.m_members.root);                      // MAY THROW (V, E: alloc, copy, N: alloc)

        if ( copy_tr_and_params )
        {
            dst.m_members.indexable_getter() = src.m_members.indexable_getter();
            dst.m_members.equal_to() = src.m_members.equal_to();
            dst.m_members.parameters() = src.m_members.parameters();
        }

        // TODO use subtree_destroyer
        if ( dst.m_members.root )
        {
            detail::rtree::visitors::destroy<value_type, options_type, translator_type, box_type, allocators_type>
                del_v(dst.m_members.root, dst.m_members.allocators());
            detail::rtree::apply_visitor(del_v, *dst.m_members.root);
            dst.m_members.root = 0;
        }

        dst.m_members.root = copy_v.result;
        dst.m_members.values_count = src.m_members.values_count;
        dst.m_members.leafs_level = src.m_members.leafs_level;
    }

    template <typename ValueConvertible>
    inline void insert_dispatch(ValueConvertible const& val_conv,
                                boost::mpl::bool_<true> const& /*is_convertible*/)
    {
        this->raw_insert(val_conv);
    }

    template <typename Range>
    inline void insert_dispatch(Range const& rng,
                                boost::mpl::bool_<false> const& /*is_convertible*/)
    {
        BOOST_MPL_ASSERT_MSG((detail::is_range<Range>::value),
                             PASSED_OBJECT_IS_NOT_CONVERTIBLE_TO_VALUE_NOR_A_RANGE,
                             (Range));

        typedef typename boost::range_const_iterator<Range>::type It;
        for ( It it = boost::const_begin(rng); it != boost::const_end(rng) ; ++it )
            this->raw_insert(*it);
    }

    template <typename ValueConvertible>
    inline size_type remove_dispatch(ValueConvertible const& val_conv,
                                     boost::mpl::bool_<true> const& /*is_convertible*/)
    {
        return this->raw_remove(val_conv);
    }

    template <typename Range>
    inline size_type remove_dispatch(Range const& rng,
                                     boost::mpl::bool_<false> const& /*is_convertible*/)
    {
        BOOST_MPL_ASSERT_MSG((detail::is_range<Range>::value),
                             PASSED_OBJECT_IS_NOT_CONVERTIBLE_TO_VALUE_NOR_A_RANGE,
                             (Range));

        size_type result = 0;
        typedef typename boost::range_const_iterator<Range>::type It;
        for ( It it = boost::const_begin(rng); it != boost::const_end(rng) ; ++it )
            result += this->raw_remove(*it);
        return result;
    }

    template <typename Predicates, typename OutIter>
    size_type query_dispatch(Predicates const& predicates, OutIter out_it, boost::mpl::bool_<false> const& /*is_distance_predicate*/) const
    {
        detail::rtree::visitors::spatial_query<value_type, options_type, translator_type, box_type, allocators_type, Predicates, OutIter>
            find_v(m_members.translator(), predicates, out_it);

        detail::rtree::apply_visitor(find_v, *m_members.root);

        return find_v.found_count;
    }

    template <typename Predicates, typename OutIter>
    size_type query_dispatch(Predicates const& predicates, OutIter out_it, boost::mpl::bool_<true> const& /*is_distance_predicate*/) const
    {
        BOOST_GEOMETRY_INDEX_ASSERT(m_members.root, "The root must exist");

        static const unsigned distance_predicate_index = detail::predicates_find_distance<Predicates>::value;
        detail::rtree::visitors::distance_query<
            value_type,
            options_type,
            translator_type,
            box_type,
            allocators_type,
            Predicates,
            distance_predicate_index,
            OutIter
        > distance_v(m_members.parameters(), m_members.translator(), predicates, out_it);

        detail::rtree::apply_visitor(distance_v, *m_members.root);

        return distance_v.finish();
    }
    
    template <typename ValueOrIndexable>
    size_type raw_count(ValueOrIndexable const& vori) const
    {
        BOOST_GEOMETRY_INDEX_ASSERT(m_members.root, "The root must exist");

        detail::rtree::visitors::count
            <
                ValueOrIndexable,
                value_type,
                options_type,
                translator_type,
                box_type,
                allocators_type
            > count_v(vori, m_members.translator());

        detail::rtree::apply_visitor(count_v, *m_members.root);

        return count_v.found_count;
    }

    struct members_holder
        : public translator_type
        , public Parameters
        , public allocators_type
    {
    private:
        members_holder(members_holder const&);
        members_holder & operator=(members_holder const&);

    public:
        template <typename IndGet, typename ValEq, typename Alloc>
        members_holder(IndGet const& ind_get,
                       ValEq const& val_eq,
                       Parameters const& parameters,
                       BOOST_FWD_REF(Alloc) alloc)
            : translator_type(ind_get, val_eq)
            , Parameters(parameters)
            , allocators_type(boost::forward<Alloc>(alloc))
            , values_count(0)
            , leafs_level(0)
            , root(0)
        {}

        template <typename IndGet, typename ValEq>
        members_holder(IndGet const& ind_get,
                       ValEq const& val_eq,
                       Parameters const& parameters)
            : translator_type(ind_get, val_eq)
            , Parameters(parameters)
            , allocators_type()
            , values_count(0)
            , leafs_level(0)
            , root(0)
        {}

        translator_type const& translator() const { return *this; }

        IndexableGetter const& indexable_getter() const { return *this; }
        IndexableGetter & indexable_getter() { return *this; }
        EqualTo const& equal_to() const { return *this; }
        EqualTo & equal_to() { return *this; }
        Parameters const& parameters() const { return *this; }
        Parameters & parameters() { return *this; }
        allocators_type const& allocators() const { return *this; }
        allocators_type & allocators() { return *this; }

        size_type values_count;
        size_type leafs_level;
        node_pointer root;
    };

    members_holder m_members;
};

template <typename Value, typename Parameters, typename IndexableGetter, typename EqualTo, typename Allocator>
inline void insert(rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator> & tree,
                   Value const& v)
{
    tree.insert(v);
}

template<typename Value, typename Parameters, typename IndexableGetter, typename EqualTo, typename Allocator,
         typename Iterator>
inline void insert(rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator> & tree,
                   Iterator first, Iterator last)
{
    tree.insert(first, last);
}

template<typename Value, typename Parameters, typename IndexableGetter, typename EqualTo, typename Allocator,
         typename ConvertibleOrRange>
inline void insert(rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator> & tree,
                   ConvertibleOrRange const& conv_or_rng)
{
    tree.insert(conv_or_rng);
}

template <typename Value, typename Parameters, typename IndexableGetter, typename EqualTo, typename Allocator>
inline typename rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator>::size_type
remove(rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator> & tree,
       Value const& v)
{
    return tree.remove(v);
}

template<typename Value, typename Parameters, typename IndexableGetter, typename EqualTo, typename Allocator,
         typename Iterator>
inline typename rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator>::size_type
remove(rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator> & tree,
       Iterator first, Iterator last)
{
    return tree.remove(first, last);
}

template<typename Value, typename Parameters, typename IndexableGetter, typename EqualTo, typename Allocator,
         typename ConvertibleOrRange>
inline typename rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator>::size_type
remove(rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator> & tree,
       ConvertibleOrRange const& conv_or_rng)
{
    return tree.remove(conv_or_rng);
}

template <typename Value, typename Parameters, typename IndexableGetter, typename EqualTo, typename Allocator,
          typename Predicates, typename OutIter> inline
typename rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator>::size_type
query(rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator> const& tree,
      Predicates const& predicates,
      OutIter out_it)
{
    return tree.query(predicates, out_it);
}

template <typename Value, typename Parameters, typename IndexableGetter, typename EqualTo, typename Allocator,
          typename Predicates> inline
typename rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator>::const_query_iterator
qbegin(rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator> const& tree,
       Predicates const& predicates)
{
    return tree.qbegin(predicates);
}

template <typename Value, typename Parameters, typename IndexableGetter, typename EqualTo, typename Allocator> inline
typename rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator>::const_query_iterator
qend(rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator> const& tree)
{
    return tree.qend();
}

template <typename Value, typename Parameters, typename IndexableGetter, typename EqualTo, typename Allocator> inline
typename rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator>::const_iterator
begin(rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator> const& tree)
{
    return tree.begin();
}

template <typename Value, typename Parameters, typename IndexableGetter, typename EqualTo, typename Allocator> inline
typename rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator>::const_iterator
end(rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator> const& tree)
{
    return tree.end();
}

template <typename Value, typename Parameters, typename IndexableGetter, typename EqualTo, typename Allocator>
inline void clear(rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator> & tree)
{
    return tree.clear();
}

template <typename Value, typename Parameters, typename IndexableGetter, typename EqualTo, typename Allocator>
inline size_t size(rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator> const& tree)
{
    return tree.size();
}

template <typename Value, typename Parameters, typename IndexableGetter, typename EqualTo, typename Allocator>
inline bool empty(rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator> const& tree)
{
    return tree.bounds();
}

template <typename Value, typename Parameters, typename IndexableGetter, typename EqualTo, typename Allocator>
inline typename rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator>::bounds_type
bounds(rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator> const& tree)
{
    return tree.bounds();
}

template <typename Value, typename Parameters, typename IndexableGetter, typename EqualTo, typename Allocator>
inline void swap(rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator> & l,
                 rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator> & r)
{
    return l.swap(r);
}

}}} // namespace boost::geometry::index

// Boost.Range adaptation
namespace boost {

template <typename Value, typename Parameters, typename IndexableGetter, typename EqualTo, typename Allocator>
struct range_mutable_iterator
    <
        boost::geometry::index::rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator>
    >
{
    typedef typename boost::geometry::index::rtree
        <
            Value, Parameters, IndexableGetter, EqualTo, Allocator
        >::const_iterator type;
};

} // namespace boost

// TODO: don't include the implementation at the end of the file
#include <boost/geometry/algorithms/detail/comparable_distance/implementation.hpp>

#include <boost/geometry/index/detail/config_end.hpp>

#endif // BOOST_GEOMETRY_INDEX_RTREE_HPP