Boost.Geometry.Index
/home/travis/build/boostorg/boost/boost/geometry/index/rtree.hpp
00001 // Boost.Geometry Index
00002 //
00003 // R-tree implementation
00004 //
00005 // Copyright (c) 2008 Federico J. Fernandez.
00006 // Copyright (c) 2011-2015 Adam Wulkiewicz, Lodz, Poland.
00007 //
00008 // Use, modification and distribution is subject to the Boost Software License,
00009 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
00010 // http://www.boost.org/LICENSE_1_0.txt)
00011 
00012 #ifndef BOOST_GEOMETRY_INDEX_RTREE_HPP
00013 #define BOOST_GEOMETRY_INDEX_RTREE_HPP
00014 
00015 // STD
00016 #include <algorithm>
00017 
00018 // Boost
00019 #include <boost/tuple/tuple.hpp>
00020 #include <boost/move/move.hpp>
00021 
00022 // Boost.Geometry
00023 #include <boost/geometry/algorithms/detail/comparable_distance/interface.hpp>
00024 #include <boost/geometry/algorithms/centroid.hpp>
00025 #include <boost/geometry/algorithms/covered_by.hpp>
00026 #include <boost/geometry/algorithms/disjoint.hpp>
00027 #include <boost/geometry/algorithms/equals.hpp>
00028 #include <boost/geometry/algorithms/intersects.hpp>
00029 #include <boost/geometry/algorithms/overlaps.hpp>
00030 #include <boost/geometry/algorithms/touches.hpp>
00031 #include <boost/geometry/algorithms/within.hpp>
00032 
00033 #include <boost/geometry/geometries/point.hpp>
00034 #include <boost/geometry/geometries/box.hpp>
00035 
00036 #include <boost/geometry/strategies/strategies.hpp>
00037 
00038 // Boost.Geometry.Index
00039 #include <boost/geometry/index/detail/config_begin.hpp>
00040 
00041 #include <boost/geometry/index/detail/assert.hpp>
00042 #include <boost/geometry/index/detail/exception.hpp>
00043 
00044 #include <boost/geometry/index/detail/rtree/options.hpp>
00045 
00046 #include <boost/geometry/index/indexable.hpp>
00047 #include <boost/geometry/index/equal_to.hpp>
00048 
00049 #include <boost/geometry/index/detail/translator.hpp>
00050 
00051 #include <boost/geometry/index/predicates.hpp>
00052 #include <boost/geometry/index/distance_predicates.hpp>
00053 #include <boost/geometry/index/detail/rtree/adaptors.hpp>
00054 
00055 #include <boost/geometry/index/detail/meta.hpp>
00056 #include <boost/geometry/index/detail/utilities.hpp>
00057 #include <boost/geometry/index/detail/rtree/node/node.hpp>
00058 
00059 #include <boost/geometry/index/detail/algorithms/is_valid.hpp>
00060 
00061 #include <boost/geometry/index/detail/rtree/visitors/insert.hpp>
00062 #include <boost/geometry/index/detail/rtree/visitors/iterator.hpp>
00063 #include <boost/geometry/index/detail/rtree/visitors/remove.hpp>
00064 #include <boost/geometry/index/detail/rtree/visitors/copy.hpp>
00065 #include <boost/geometry/index/detail/rtree/visitors/destroy.hpp>
00066 #include <boost/geometry/index/detail/rtree/visitors/spatial_query.hpp>
00067 #include <boost/geometry/index/detail/rtree/visitors/distance_query.hpp>
00068 #include <boost/geometry/index/detail/rtree/visitors/count.hpp>
00069 #include <boost/geometry/index/detail/rtree/visitors/children_box.hpp>
00070 
00071 #include <boost/geometry/index/detail/rtree/linear/linear.hpp>
00072 #include <boost/geometry/index/detail/rtree/quadratic/quadratic.hpp>
00073 #include <boost/geometry/index/detail/rtree/rstar/rstar.hpp>
00074 //#include <boost/geometry/extensions/index/detail/rtree/kmeans/kmeans.hpp>
00075 
00076 #include <boost/geometry/index/detail/rtree/pack_create.hpp>
00077 
00078 #include <boost/geometry/index/inserter.hpp>
00079 
00080 #include <boost/geometry/index/detail/rtree/utilities/view.hpp>
00081 
00082 #include <boost/geometry/index/detail/rtree/iterators.hpp>
00083 #include <boost/geometry/index/detail/rtree/query_iterators.hpp>
00084 
00085 #ifdef BOOST_GEOMETRY_INDEX_DETAIL_EXPERIMENTAL
00086 // serialization
00087 #include <boost/geometry/index/detail/serialization.hpp>
00088 #endif
00089 
00090 // TODO change the name to bounding_tree
00091 
00096 namespace boost { namespace geometry { namespace index {
00097 
00148 template <
00149     typename Value,
00150     typename Parameters,
00151     typename IndexableGetter = index::indexable<Value>,
00152     typename EqualTo = index::equal_to<Value>,
00153     typename Allocator = std::allocator<Value>
00154 >
00155 class rtree
00156 {
00157     BOOST_COPYABLE_AND_MOVABLE(rtree)
00158 
00159 public:
00161     typedef Value value_type;
00163     typedef Parameters parameters_type;
00165     typedef IndexableGetter indexable_getter;
00167     typedef EqualTo value_equal;
00169     typedef Allocator allocator_type;
00170 
00171     // TODO: SHOULD THIS TYPE BE REMOVED?
00173     typedef typename index::detail::indexable_type<
00174         detail::translator<IndexableGetter, EqualTo>
00175     >::type indexable_type;
00176 
00178     typedef geometry::model::box<
00179                 geometry::model::point<
00180                     typename coordinate_type<indexable_type>::type,
00181                     dimension<indexable_type>::value,
00182                     typename coordinate_system<indexable_type>::type
00183                 >
00184             >
00185     bounds_type;
00186 
00187 private:
00188 
00189     typedef detail::translator<IndexableGetter, EqualTo> translator_type;
00190 
00191     typedef bounds_type box_type;
00192     typedef typename detail::rtree::options_type<Parameters>::type options_type;
00193     typedef typename options_type::node_tag node_tag;
00194     typedef detail::rtree::allocators<allocator_type, value_type, typename options_type::parameters_type, box_type, node_tag> allocators_type;
00195 
00196     typedef typename detail::rtree::node<value_type, typename options_type::parameters_type, box_type, allocators_type, node_tag>::type node;
00197     typedef typename detail::rtree::internal_node<value_type, typename options_type::parameters_type, box_type, allocators_type, node_tag>::type internal_node;
00198     typedef typename detail::rtree::leaf<value_type, typename options_type::parameters_type, box_type, allocators_type, node_tag>::type leaf;
00199 
00200     typedef typename allocators_type::node_pointer node_pointer;
00201     typedef ::boost::container::allocator_traits<Allocator> allocator_traits_type;
00202     typedef detail::rtree::subtree_destroyer<value_type, options_type, translator_type, box_type, allocators_type> subtree_destroyer;
00203 
00204     friend class detail::rtree::utilities::view<rtree>;
00205 #ifdef BOOST_GEOMETRY_INDEX_DETAIL_EXPERIMENTAL
00206     friend class detail::rtree::private_view<rtree>;
00207     friend class detail::rtree::const_private_view<rtree>;
00208 #endif
00209 
00210 public:
00211 
00213     typedef typename allocators_type::reference reference;
00215     typedef typename allocators_type::const_reference const_reference;
00217     typedef typename allocators_type::pointer pointer;
00219     typedef typename allocators_type::const_pointer const_pointer;
00221     typedef typename allocators_type::difference_type difference_type;
00223     typedef typename allocators_type::size_type size_type;
00224 
00226     typedef index::detail::rtree::iterators::iterator
00227         <
00228             value_type, options_type, translator_type, box_type, allocators_type
00229         > const_iterator;
00230 
00232     typedef index::detail::rtree::iterators::query_iterator
00233         <
00234             value_type, allocators_type
00235         > const_query_iterator;
00236 
00237 public:
00238 
00249     inline explicit rtree(parameters_type const& parameters = parameters_type(),
00250                           indexable_getter const& getter = indexable_getter(),
00251                           value_equal const& equal = value_equal())
00252         : m_members(getter, equal, parameters)
00253     {}
00254 
00266     inline rtree(parameters_type const& parameters,
00267                  indexable_getter const& getter,
00268                  value_equal const& equal,
00269                  allocator_type const& allocator)
00270         : m_members(getter, equal, parameters, allocator)
00271     {}
00272 
00290     template<typename Iterator>
00291     inline rtree(Iterator first, Iterator last,
00292                  parameters_type const& parameters = parameters_type(),
00293                  indexable_getter const& getter = indexable_getter(),
00294                  value_equal const& equal = value_equal(),
00295                  allocator_type const& allocator = allocator_type())
00296         : m_members(getter, equal, parameters, allocator)
00297     {
00298         typedef detail::rtree::pack<value_type, options_type, translator_type, box_type, allocators_type> pack;
00299         size_type vc = 0, ll = 0;
00300         m_members.root = pack::apply(first, last, vc, ll,
00301                                      m_members.parameters(), m_members.translator(), m_members.allocators());
00302         m_members.values_count = vc;
00303         m_members.leafs_level = ll;
00304     }
00305 
00322     template<typename Range>
00323     inline explicit rtree(Range const& rng,
00324                           parameters_type const& parameters = parameters_type(),
00325                           indexable_getter const& getter = indexable_getter(),
00326                           value_equal const& equal = value_equal(),
00327                           allocator_type const& allocator = allocator_type())
00328         : m_members(getter, equal, parameters, allocator)
00329     {
00330         typedef detail::rtree::pack<value_type, options_type, translator_type, box_type, allocators_type> pack;
00331         size_type vc = 0, ll = 0;
00332         m_members.root = pack::apply(::boost::begin(rng), ::boost::end(rng), vc, ll,
00333                                      m_members.parameters(), m_members.translator(), m_members.allocators());
00334         m_members.values_count = vc;
00335         m_members.leafs_level = ll;
00336     }
00337 
00344     inline ~rtree()
00345     {
00346         this->raw_destroy(*this);
00347     }
00348 
00361     inline rtree(rtree const& src)
00362         : m_members(src.m_members.indexable_getter(),
00363                     src.m_members.equal_to(),
00364                     src.m_members.parameters(),
00365                     allocator_traits_type::select_on_container_copy_construction(src.get_allocator()))
00366     {
00367         this->raw_copy(src, *this, false);
00368     }
00369 
00383     inline rtree(rtree const& src, allocator_type const& allocator)
00384         : m_members(src.m_members.indexable_getter(),
00385                     src.m_members.equal_to(),
00386                     src.m_members.parameters(), allocator)
00387     {
00388         this->raw_copy(src, *this, false);
00389     }
00390 
00401     inline rtree(BOOST_RV_REF(rtree) src)
00402         : m_members(src.m_members.indexable_getter(),
00403                     src.m_members.equal_to(),
00404                     src.m_members.parameters(),
00405                     boost::move(src.m_members.allocators()))
00406     {
00407         boost::swap(m_members.values_count, src.m_members.values_count);
00408         boost::swap(m_members.leafs_level, src.m_members.leafs_level);
00409         boost::swap(m_members.root, src.m_members.root);
00410     }
00411 
00425     inline rtree(BOOST_RV_REF(rtree) src, allocator_type const& allocator)
00426         : m_members(src.m_members.indexable_getter(),
00427                     src.m_members.equal_to(),
00428                     src.m_members.parameters(),
00429                     allocator)
00430     {
00431         if ( src.m_members.allocators() == allocator )
00432         {
00433             boost::swap(m_members.values_count, src.m_members.values_count);
00434             boost::swap(m_members.leafs_level, src.m_members.leafs_level);
00435             boost::swap(m_members.root, src.m_members.root);
00436         }
00437         else
00438         {
00439             this->raw_copy(src, *this, false);
00440         }
00441     }
00442 
00455     inline rtree & operator=(BOOST_COPY_ASSIGN_REF(rtree) src)
00456     {
00457         if ( &src != this )
00458         {
00459             allocators_type & this_allocs = m_members.allocators();
00460             allocators_type const& src_allocs = src.m_members.allocators();
00461 
00462             // NOTE: if propagate is true for std allocators on darwin 4.2.1, glibc++
00463             // (allocators stored as base classes of members_holder)
00464             // copying them changes values_count, in this case it doesn't cause errors since data must be copied
00465             
00466             typedef boost::mpl::bool_<
00467                 allocator_traits_type::propagate_on_container_copy_assignment::value
00468             > propagate;
00469             
00470             if ( propagate::value && !(this_allocs == src_allocs) )
00471                 this->raw_destroy(*this);
00472             detail::assign_cond(this_allocs, src_allocs, propagate());
00473 
00474             // It uses m_allocators
00475             this->raw_copy(src, *this, true);
00476         }
00477 
00478         return *this;
00479     }
00480 
00493     inline rtree & operator=(BOOST_RV_REF(rtree) src)
00494     {
00495         if ( &src != this )
00496         {
00497             allocators_type & this_allocs = m_members.allocators();
00498             allocators_type & src_allocs = src.m_members.allocators();
00499             
00500             if ( this_allocs == src_allocs )
00501             {
00502                 this->raw_destroy(*this);
00503 
00504                 m_members.indexable_getter() = src.m_members.indexable_getter();
00505                 m_members.equal_to() = src.m_members.equal_to();
00506                 m_members.parameters() = src.m_members.parameters();
00507 
00508                 boost::swap(m_members.values_count, src.m_members.values_count);
00509                 boost::swap(m_members.leafs_level, src.m_members.leafs_level);
00510                 boost::swap(m_members.root, src.m_members.root);
00511 
00512                 // NOTE: if propagate is true for std allocators on darwin 4.2.1, glibc++
00513                 // (allocators stored as base classes of members_holder)
00514                 // moving them changes values_count
00515                 
00516                 typedef boost::mpl::bool_<
00517                     allocator_traits_type::propagate_on_container_move_assignment::value
00518                 > propagate;
00519                 detail::move_cond(this_allocs, src_allocs, propagate());
00520             }
00521             else
00522             {
00523 // TODO - shouldn't here propagate_on_container_copy_assignment be checked like in operator=(const&)?
00524 
00525                 // It uses m_allocators
00526                 this->raw_copy(src, *this, true);
00527             }
00528         }
00529 
00530         return *this;
00531     }
00532 
00543     void swap(rtree & other)
00544     {
00545         boost::swap(m_members.indexable_getter(), other.m_members.indexable_getter());
00546         boost::swap(m_members.equal_to(), other.m_members.equal_to());
00547         boost::swap(m_members.parameters(), other.m_members.parameters());
00548         
00549         // NOTE: if propagate is true for std allocators on darwin 4.2.1, glibc++
00550         // (allocators stored as base classes of members_holder)
00551         // swapping them changes values_count
00552         
00553         typedef boost::mpl::bool_<
00554             allocator_traits_type::propagate_on_container_swap::value
00555         > propagate;
00556         detail::swap_cond(m_members.allocators(), other.m_members.allocators(), propagate());
00557 
00558         boost::swap(m_members.values_count, other.m_members.values_count);
00559         boost::swap(m_members.leafs_level, other.m_members.leafs_level);
00560         boost::swap(m_members.root, other.m_members.root);
00561     }
00562 
00578     inline void insert(value_type const& value)
00579     {
00580         if ( !m_members.root )
00581             this->raw_create();
00582 
00583         this->raw_insert(value);
00584     }
00585 
00602     template <typename Iterator>
00603     inline void insert(Iterator first, Iterator last)
00604     {
00605         if ( !m_members.root )
00606             this->raw_create();
00607 
00608         for ( ; first != last ; ++first )
00609             this->raw_insert(*first);
00610     }
00611 
00627     template <typename ConvertibleOrRange>
00628     inline void insert(ConvertibleOrRange const& conv_or_rng)
00629     {
00630         if ( !m_members.root )
00631             this->raw_create();
00632 
00633         typedef boost::mpl::bool_
00634             <
00635                 boost::is_convertible<ConvertibleOrRange, value_type>::value
00636             > is_conv_t;
00637 
00638         this->insert_dispatch(conv_or_rng, is_conv_t());
00639     }
00640 
00661     inline size_type remove(value_type const& value)
00662     {
00663         if ( !m_members.root )
00664             return 0;
00665 
00666         return this->raw_remove(value);
00667     }
00668 
00692     template <typename Iterator>
00693     inline size_type remove(Iterator first, Iterator last)
00694     {
00695         size_type result = 0;
00696 
00697         if ( !m_members.root )
00698             return result;
00699 
00700         for ( ; first != last ; ++first )
00701             result += this->raw_remove(*first);
00702         return result;
00703     }
00704 
00726     template <typename ConvertibleOrRange>
00727     inline size_type remove(ConvertibleOrRange const& conv_or_rng)
00728     {
00729         if ( !m_members.root )
00730             return 0;
00731 
00732         typedef boost::mpl::bool_
00733             <
00734                 boost::is_convertible<ConvertibleOrRange, value_type>::value
00735             > is_conv_t;
00736 
00737         return this->remove_dispatch(conv_or_rng, is_conv_t());
00738     }
00739 
00828     template <typename Predicates, typename OutIter>
00829     size_type query(Predicates const& predicates, OutIter out_it) const
00830     {
00831         if ( !m_members.root )
00832             return 0;
00833 
00834         static const unsigned distance_predicates_count = detail::predicates_count_distance<Predicates>::value;
00835         static const bool is_distance_predicate = 0 < distance_predicates_count;
00836         BOOST_MPL_ASSERT_MSG((distance_predicates_count <= 1), PASS_ONLY_ONE_DISTANCE_PREDICATE, (Predicates));
00837 
00838         return query_dispatch(predicates, out_it, boost::mpl::bool_<is_distance_predicate>());
00839     }
00840 
00883     template <typename Predicates>
00884     const_query_iterator qbegin(Predicates const& predicates) const
00885     {
00886         return const_query_iterator(qbegin_(predicates));
00887     }
00888 
00927     const_query_iterator qend() const
00928     {
00929         return const_query_iterator();
00930     }
00931 
00932 #ifndef BOOST_GEOMETRY_INDEX_DETAIL_EXPERIMENTAL
00933 private:
00934 #endif
00935 
00988     template <typename Predicates>
00989     typename boost::mpl::if_c<
00990         detail::predicates_count_distance<Predicates>::value == 0,
00991         detail::rtree::iterators::spatial_query_iterator<value_type, options_type, translator_type, box_type, allocators_type, Predicates>,
00992         detail::rtree::iterators::distance_query_iterator<
00993             value_type, options_type, translator_type, box_type, allocators_type, Predicates,
00994             detail::predicates_find_distance<Predicates>::value
00995         >
00996     >::type
00997     qbegin_(Predicates const& predicates) const
00998     {
00999         static const unsigned distance_predicates_count = detail::predicates_count_distance<Predicates>::value;
01000         BOOST_MPL_ASSERT_MSG((distance_predicates_count <= 1), PASS_ONLY_ONE_DISTANCE_PREDICATE, (Predicates));
01001 
01002         typedef typename boost::mpl::if_c<
01003             detail::predicates_count_distance<Predicates>::value == 0,
01004             detail::rtree::iterators::spatial_query_iterator<value_type, options_type, translator_type, box_type, allocators_type, Predicates>,
01005             detail::rtree::iterators::distance_query_iterator<
01006                 value_type, options_type, translator_type, box_type, allocators_type, Predicates,
01007                 detail::predicates_find_distance<Predicates>::value
01008             >
01009         >::type iterator_type;
01010 
01011         if ( !m_members.root )
01012             return iterator_type(m_members.translator(), predicates);
01013 
01014         return iterator_type(m_members.root, m_members.translator(), predicates);
01015     }
01016 
01049     template <typename Predicates>
01050     typename boost::mpl::if_c<
01051         detail::predicates_count_distance<Predicates>::value == 0,
01052         detail::rtree::iterators::spatial_query_iterator<value_type, options_type, translator_type, box_type, allocators_type, Predicates>,
01053         detail::rtree::iterators::distance_query_iterator<
01054             value_type, options_type, translator_type, box_type, allocators_type, Predicates,
01055             detail::predicates_find_distance<Predicates>::value
01056         >
01057     >::type
01058     qend_(Predicates const& predicates) const
01059     {
01060         static const unsigned distance_predicates_count = detail::predicates_count_distance<Predicates>::value;
01061         BOOST_MPL_ASSERT_MSG((distance_predicates_count <= 1), PASS_ONLY_ONE_DISTANCE_PREDICATE, (Predicates));
01062 
01063         typedef typename boost::mpl::if_c<
01064             detail::predicates_count_distance<Predicates>::value == 0,
01065             detail::rtree::iterators::spatial_query_iterator<value_type, options_type, translator_type, box_type, allocators_type, Predicates>,
01066             detail::rtree::iterators::distance_query_iterator<
01067                 value_type, options_type, translator_type, box_type, allocators_type, Predicates,
01068                 detail::predicates_find_distance<Predicates>::value
01069             >
01070         >::type iterator_type;
01071 
01072         return iterator_type(m_members.translator(), predicates);
01073     }
01074 
01124     detail::rtree::iterators::end_query_iterator<value_type, allocators_type>
01125     qend_() const
01126     {
01127         return detail::rtree::iterators::end_query_iterator<value_type, allocators_type>();
01128     }
01129 
01130 public:
01131 
01171     const_iterator begin() const
01172     {
01173         if ( !m_members.root )
01174             return const_iterator();
01175 
01176         return const_iterator(m_members.root);
01177     }
01178 
01209     const_iterator end() const
01210     {
01211         return const_iterator();
01212     }
01213 
01222     inline size_type size() const
01223     {
01224         return m_members.values_count;
01225     }
01226 
01235     inline bool empty() const
01236     {
01237         return 0 == m_members.values_count;
01238     }
01239 
01246     inline void clear()
01247     {
01248         this->raw_destroy(*this);
01249     }
01250 
01263     inline bounds_type bounds() const
01264     {
01265         bounds_type result;
01266         // in order to suppress the uninitialized variable warnings
01267         geometry::assign_inverse(result);
01268 
01269         if ( m_members.root )
01270         {
01271             detail::rtree::visitors::children_box<value_type, options_type, translator_type, box_type, allocators_type>
01272                 box_v(result, m_members.translator());
01273             detail::rtree::apply_visitor(box_v, *m_members.root);
01274         }
01275 
01276         return result;
01277     }
01278 
01292     template <typename ValueOrIndexable>
01293     size_type count(ValueOrIndexable const& vori) const
01294     {
01295         if ( !m_members.root )
01296             return 0;
01297 
01298         // the input should be convertible to Value or Indexable type
01299 
01300         enum { as_val = 0, as_ind, dont_know };
01301         typedef boost::mpl::int_
01302             <
01303                 boost::is_same<ValueOrIndexable, value_type>::value ?
01304                     as_val :
01305                     boost::is_same<ValueOrIndexable, indexable_type>::value ?
01306                         as_ind :
01307                         boost::is_convertible<ValueOrIndexable, indexable_type>::value ?
01308                             as_ind :
01309                             boost::is_convertible<ValueOrIndexable, value_type>::value ?
01310                                 as_val :
01311                                 dont_know
01312             > variant;
01313 
01314         BOOST_MPL_ASSERT_MSG((variant::value != dont_know),
01315                              PASSED_OBJECT_NOT_CONVERTIBLE_TO_VALUE_NOR_INDEXABLE_TYPE,
01316                              (ValueOrIndexable));
01317 
01318         typedef typename boost::mpl::if_c
01319             <
01320                 variant::value == as_val,
01321                 value_type,
01322                 indexable_type
01323             >::type value_or_indexable;
01324 
01325         // NOTE: If an object of convertible but not the same type is passed
01326         // into the function, here a temporary will be created.
01327         return this->template raw_count<value_or_indexable>(vori);
01328     }
01329 
01338     inline parameters_type parameters() const
01339     {
01340         return m_members.parameters();
01341     }
01342 
01351     indexable_getter indexable_get() const
01352     {
01353         return m_members.indexable_getter();
01354     }
01355 
01364     value_equal value_eq() const
01365     {
01366         return m_members.equal_to();
01367     }
01368 
01377     allocator_type get_allocator() const
01378     {
01379         return m_members.allocators().allocator();
01380     }
01381 
01382 private:
01383 
01392     inline translator_type translator() const
01393     {
01394         return m_members.translator();
01395     }
01396 
01408     template <typename Visitor>
01409     inline void apply_visitor(Visitor & visitor) const
01410     {
01411         if ( m_members.root )
01412             detail::rtree::apply_visitor(visitor, *m_members.root);
01413     }
01414 
01425     inline size_type depth() const
01426     {
01427         return m_members.leafs_level;
01428     }
01429 
01430 private:
01431 
01442     inline void raw_insert(value_type const& value)
01443     {
01444         BOOST_GEOMETRY_INDEX_ASSERT(m_members.root, "The root must exist");
01445         // CONSIDER: alternative - ignore invalid indexable or throw an exception
01446         BOOST_GEOMETRY_INDEX_ASSERT(detail::is_valid(m_members.translator()(value)), "Indexable is invalid");
01447 
01448         detail::rtree::visitors::insert<
01449             value_type,
01450             value_type, options_type, translator_type, box_type, allocators_type,
01451             typename options_type::insert_tag
01452         > insert_v(m_members.root, m_members.leafs_level, value,
01453                    m_members.parameters(), m_members.translator(), m_members.allocators());
01454 
01455         detail::rtree::apply_visitor(insert_v, *m_members.root);
01456 
01457 // TODO
01458 // Think about this: If exception is thrown, may the root be removed?
01459 // Or it is just cleared?
01460 
01461 // TODO
01462 // If exception is thrown, m_values_count may be invalid
01463         ++m_members.values_count;
01464     }
01465 
01474     inline size_type raw_remove(value_type const& value)
01475     {
01476         // TODO: awulkiew - assert for correct value (indexable) ?
01477         BOOST_GEOMETRY_INDEX_ASSERT(m_members.root, "The root must exist");
01478 
01479         detail::rtree::visitors::remove<
01480             value_type, options_type, translator_type, box_type, allocators_type
01481         > remove_v(m_members.root, m_members.leafs_level, value,
01482                    m_members.parameters(), m_members.translator(), m_members.allocators());
01483 
01484         detail::rtree::apply_visitor(remove_v, *m_members.root);
01485 
01486         // If exception is thrown, m_values_count may be invalid
01487 
01488         if ( remove_v.is_value_removed() )
01489         {
01490             BOOST_GEOMETRY_INDEX_ASSERT(0 < m_members.values_count, "unexpected state");
01491 
01492             --m_members.values_count;
01493 
01494             return 1;
01495         }
01496 
01497         return 0;
01498     }
01499 
01506     inline void raw_create()
01507     {
01508         BOOST_GEOMETRY_INDEX_ASSERT(0 == m_members.root, "the tree is already created");
01509 
01510         m_members.root = detail::rtree::create_node<allocators_type, leaf>::apply(m_members.allocators()); // MAY THROW (N: alloc)
01511         m_members.values_count = 0;
01512         m_members.leafs_level = 0;
01513     }
01514 
01523     inline void raw_destroy(rtree & t)
01524     {
01525         if ( t.m_members.root )
01526         {
01527             detail::rtree::visitors::destroy<value_type, options_type, translator_type, box_type, allocators_type>
01528                 del_v(t.m_members.root, t.m_members.allocators());
01529             detail::rtree::apply_visitor(del_v, *t.m_members.root);
01530 
01531             t.m_members.root = 0;
01532         }
01533         t.m_members.values_count = 0;
01534         t.m_members.leafs_level = 0;
01535     }
01536 
01548     inline void raw_copy(rtree const& src, rtree & dst, bool copy_tr_and_params) const
01549     {
01550         detail::rtree::visitors::copy<value_type, options_type, translator_type, box_type, allocators_type>
01551             copy_v(dst.m_members.allocators());
01552 
01553         if ( src.m_members.root )
01554             detail::rtree::apply_visitor(copy_v, *src.m_members.root);                      // MAY THROW (V, E: alloc, copy, N: alloc)
01555 
01556         if ( copy_tr_and_params )
01557         {
01558             dst.m_members.indexable_getter() = src.m_members.indexable_getter();
01559             dst.m_members.equal_to() = src.m_members.equal_to();
01560             dst.m_members.parameters() = src.m_members.parameters();
01561         }
01562 
01563         // TODO use subtree_destroyer
01564         if ( dst.m_members.root )
01565         {
01566             detail::rtree::visitors::destroy<value_type, options_type, translator_type, box_type, allocators_type>
01567                 del_v(dst.m_members.root, dst.m_members.allocators());
01568             detail::rtree::apply_visitor(del_v, *dst.m_members.root);
01569             dst.m_members.root = 0;
01570         }
01571 
01572         dst.m_members.root = copy_v.result;
01573         dst.m_members.values_count = src.m_members.values_count;
01574         dst.m_members.leafs_level = src.m_members.leafs_level;
01575     }
01576 
01585     template <typename ValueConvertible>
01586     inline void insert_dispatch(ValueConvertible const& val_conv,
01587                                 boost::mpl::bool_<true> const& /*is_convertible*/)
01588     {
01589         this->raw_insert(val_conv);
01590     }
01591 
01600     template <typename Range>
01601     inline void insert_dispatch(Range const& rng,
01602                                 boost::mpl::bool_<false> const& /*is_convertible*/)
01603     {
01604         BOOST_MPL_ASSERT_MSG((detail::is_range<Range>::value),
01605                              PASSED_OBJECT_IS_NOT_CONVERTIBLE_TO_VALUE_NOR_A_RANGE,
01606                              (Range));
01607 
01608         typedef typename boost::range_const_iterator<Range>::type It;
01609         for ( It it = boost::const_begin(rng); it != boost::const_end(rng) ; ++it )
01610             this->raw_insert(*it);
01611     }
01612 
01621     template <typename ValueConvertible>
01622     inline size_type remove_dispatch(ValueConvertible const& val_conv,
01623                                      boost::mpl::bool_<true> const& /*is_convertible*/)
01624     {
01625         return this->raw_remove(val_conv);
01626     }
01627 
01636     template <typename Range>
01637     inline size_type remove_dispatch(Range const& rng,
01638                                      boost::mpl::bool_<false> const& /*is_convertible*/)
01639     {
01640         BOOST_MPL_ASSERT_MSG((detail::is_range<Range>::value),
01641                              PASSED_OBJECT_IS_NOT_CONVERTIBLE_TO_VALUE_NOR_A_RANGE,
01642                              (Range));
01643 
01644         size_type result = 0;
01645         typedef typename boost::range_const_iterator<Range>::type It;
01646         for ( It it = boost::const_begin(rng); it != boost::const_end(rng) ; ++it )
01647             result += this->raw_remove(*it);
01648         return result;
01649     }
01650 
01657     template <typename Predicates, typename OutIter>
01658     size_type query_dispatch(Predicates const& predicates, OutIter out_it, boost::mpl::bool_<false> const& /*is_distance_predicate*/) const
01659     {
01660         detail::rtree::visitors::spatial_query<value_type, options_type, translator_type, box_type, allocators_type, Predicates, OutIter>
01661             find_v(m_members.translator(), predicates, out_it);
01662 
01663         detail::rtree::apply_visitor(find_v, *m_members.root);
01664 
01665         return find_v.found_count;
01666     }
01667 
01674     template <typename Predicates, typename OutIter>
01675     size_type query_dispatch(Predicates const& predicates, OutIter out_it, boost::mpl::bool_<true> const& /*is_distance_predicate*/) const
01676     {
01677         BOOST_GEOMETRY_INDEX_ASSERT(m_members.root, "The root must exist");
01678 
01679         static const unsigned distance_predicate_index = detail::predicates_find_distance<Predicates>::value;
01680         detail::rtree::visitors::distance_query<
01681             value_type,
01682             options_type,
01683             translator_type,
01684             box_type,
01685             allocators_type,
01686             Predicates,
01687             distance_predicate_index,
01688             OutIter
01689         > distance_v(m_members.parameters(), m_members.translator(), predicates, out_it);
01690 
01691         detail::rtree::apply_visitor(distance_v, *m_members.root);
01692 
01693         return distance_v.finish();
01694     }
01695     
01702     template <typename ValueOrIndexable>
01703     size_type raw_count(ValueOrIndexable const& vori) const
01704     {
01705         BOOST_GEOMETRY_INDEX_ASSERT(m_members.root, "The root must exist");
01706 
01707         detail::rtree::visitors::count
01708             <
01709                 ValueOrIndexable,
01710                 value_type,
01711                 options_type,
01712                 translator_type,
01713                 box_type,
01714                 allocators_type
01715             > count_v(vori, m_members.translator());
01716 
01717         detail::rtree::apply_visitor(count_v, *m_members.root);
01718 
01719         return count_v.found_count;
01720     }
01721 
01722     struct members_holder
01723         : public translator_type
01724         , public Parameters
01725         , public allocators_type
01726     {
01727     private:
01728         members_holder(members_holder const&);
01729         members_holder & operator=(members_holder const&);
01730 
01731     public:
01732         template <typename IndGet, typename ValEq, typename Alloc>
01733         members_holder(IndGet const& ind_get,
01734                        ValEq const& val_eq,
01735                        Parameters const& parameters,
01736                        BOOST_FWD_REF(Alloc) alloc)
01737             : translator_type(ind_get, val_eq)
01738             , Parameters(parameters)
01739             , allocators_type(boost::forward<Alloc>(alloc))
01740             , values_count(0)
01741             , leafs_level(0)
01742             , root(0)
01743         {}
01744 
01745         template <typename IndGet, typename ValEq>
01746         members_holder(IndGet const& ind_get,
01747                        ValEq const& val_eq,
01748                        Parameters const& parameters)
01749             : translator_type(ind_get, val_eq)
01750             , Parameters(parameters)
01751             , allocators_type()
01752             , values_count(0)
01753             , leafs_level(0)
01754             , root(0)
01755         {}
01756 
01757         translator_type const& translator() const { return *this; }
01758 
01759         IndexableGetter const& indexable_getter() const { return *this; }
01760         IndexableGetter & indexable_getter() { return *this; }
01761         EqualTo const& equal_to() const { return *this; }
01762         EqualTo & equal_to() { return *this; }
01763         Parameters const& parameters() const { return *this; }
01764         Parameters & parameters() { return *this; }
01765         allocators_type const& allocators() const { return *this; }
01766         allocators_type & allocators() { return *this; }
01767 
01768         size_type values_count;
01769         size_type leafs_level;
01770         node_pointer root;
01771     };
01772 
01773     members_holder m_members;
01774 };
01775 
01786 template <typename Value, typename Parameters, typename IndexableGetter, typename EqualTo, typename Allocator>
01787 inline void insert(rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator> & tree,
01788                    Value const& v)
01789 {
01790     tree.insert(v);
01791 }
01792 
01804 template<typename Value, typename Parameters, typename IndexableGetter, typename EqualTo, typename Allocator,
01805          typename Iterator>
01806 inline void insert(rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator> & tree,
01807                    Iterator first, Iterator last)
01808 {
01809     tree.insert(first, last);
01810 }
01811 
01822 template<typename Value, typename Parameters, typename IndexableGetter, typename EqualTo, typename Allocator,
01823          typename ConvertibleOrRange>
01824 inline void insert(rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator> & tree,
01825                    ConvertibleOrRange const& conv_or_rng)
01826 {
01827     tree.insert(conv_or_rng);
01828 }
01829 
01845 template <typename Value, typename Parameters, typename IndexableGetter, typename EqualTo, typename Allocator>
01846 inline typename rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator>::size_type
01847 remove(rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator> & tree,
01848        Value const& v)
01849 {
01850     return tree.remove(v);
01851 }
01852 
01871 template<typename Value, typename Parameters, typename IndexableGetter, typename EqualTo, typename Allocator,
01872          typename Iterator>
01873 inline typename rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator>::size_type
01874 remove(rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator> & tree,
01875        Iterator first, Iterator last)
01876 {
01877     return tree.remove(first, last);
01878 }
01879 
01897 template<typename Value, typename Parameters, typename IndexableGetter, typename EqualTo, typename Allocator,
01898          typename ConvertibleOrRange>
01899 inline typename rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator>::size_type
01900 remove(rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator> & tree,
01901        ConvertibleOrRange const& conv_or_rng)
01902 {
01903     return tree.remove(conv_or_rng);
01904 }
01905 
01979 template <typename Value, typename Parameters, typename IndexableGetter, typename EqualTo, typename Allocator,
01980           typename Predicates, typename OutIter> inline
01981 typename rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator>::size_type
01982 query(rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator> const& tree,
01983       Predicates const& predicates,
01984       OutIter out_it)
01985 {
01986     return tree.query(predicates, out_it);
01987 }
01988 
02017 template <typename Value, typename Parameters, typename IndexableGetter, typename EqualTo, typename Allocator,
02018           typename Predicates> inline
02019 typename rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator>::const_query_iterator
02020 qbegin(rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator> const& tree,
02021        Predicates const& predicates)
02022 {
02023     return tree.qbegin(predicates);
02024 }
02025 
02049 template <typename Value, typename Parameters, typename IndexableGetter, typename EqualTo, typename Allocator> inline
02050 typename rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator>::const_query_iterator
02051 qend(rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator> const& tree)
02052 {
02053     return tree.qend();
02054 }
02055 
02082 template <typename Value, typename Parameters, typename IndexableGetter, typename EqualTo, typename Allocator> inline
02083 typename rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator>::const_iterator
02084 begin(rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator> const& tree)
02085 {
02086     return tree.begin();
02087 }
02088 
02115 template <typename Value, typename Parameters, typename IndexableGetter, typename EqualTo, typename Allocator> inline
02116 typename rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator>::const_iterator
02117 end(rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator> const& tree)
02118 {
02119     return tree.end();
02120 }
02121 
02131 template <typename Value, typename Parameters, typename IndexableGetter, typename EqualTo, typename Allocator>
02132 inline void clear(rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator> & tree)
02133 {
02134     return tree.clear();
02135 }
02136 
02148 template <typename Value, typename Parameters, typename IndexableGetter, typename EqualTo, typename Allocator>
02149 inline size_t size(rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator> const& tree)
02150 {
02151     return tree.size();
02152 }
02153 
02165 template <typename Value, typename Parameters, typename IndexableGetter, typename EqualTo, typename Allocator>
02166 inline bool empty(rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator> const& tree)
02167 {
02168     return tree.bounds();
02169 }
02170 
02182 template <typename Value, typename Parameters, typename IndexableGetter, typename EqualTo, typename Allocator>
02183 inline typename rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator>::bounds_type
02184 bounds(rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator> const& tree)
02185 {
02186     return tree.bounds();
02187 }
02188 
02199 template <typename Value, typename Parameters, typename IndexableGetter, typename EqualTo, typename Allocator>
02200 inline void swap(rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator> & l,
02201                  rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator> & r)
02202 {
02203     return l.swap(r);
02204 }
02205 
02206 }}} // namespace boost::geometry::index
02207 
02208 // Boost.Range adaptation
02209 namespace boost {
02210 
02211 template <typename Value, typename Parameters, typename IndexableGetter, typename EqualTo, typename Allocator>
02212 struct range_mutable_iterator
02213     <
02214         boost::geometry::index::rtree<Value, Parameters, IndexableGetter, EqualTo, Allocator>
02215     >
02216 {
02217     typedef typename boost::geometry::index::rtree
02218         <
02219             Value, Parameters, IndexableGetter, EqualTo, Allocator
02220         >::const_iterator type;
02221 };
02222 
02223 } // namespace boost
02224 
02225 // TODO: don't include the implementation at the end of the file
02226 #include <boost/geometry/algorithms/detail/comparable_distance/implementation.hpp>
02227 
02228 #include <boost/geometry/index/detail/config_end.hpp>
02229 
02230 #endif // BOOST_GEOMETRY_INDEX_RTREE_HPP
 All Classes Functions Typedefs