[Boost-commit] svn:boost r85507 - in trunk/boost/geometry/index: . detail detail/rtree

Subject: [Boost-commit] svn:boost r85507 - in trunk/boost/geometry/index: . detail detail/rtree
From: adam.wulkiewicz_at_[hidden]
Date: 2013-08-28 20:33:54

Author: awulkiew
Date: 2013-08-28 20:33:54 EDT (Wed, 28 Aug 2013)
New Revision: 85507
URL: http://svn.boost.org/trac/boost/changeset/85507

Log:
[geometry][index] query iterators added to the rtree official interface.

Deleted:
   trunk/boost/geometry/index/detail/type_erased_iterators.hpp
Text files modified: 
   trunk/boost/geometry/index/detail/rtree/query_iterators.hpp |    92 +++++++++++++-----------                
   /dev/null                                                   |    61 ----------------                        
   trunk/boost/geometry/index/rtree.hpp                        |   147 ++++++++++++++++++++++++++++++--------- 
   3 files changed, 159 insertions(+), 141 deletions(-)

Modified: trunk/boost/geometry/index/detail/rtree/query_iterators.hpp
==============================================================================
--- trunk/boost/geometry/index/detail/rtree/query_iterators.hpp	Wed Aug 28 19:04:09 2013	(r85506)
+++ trunk/boost/geometry/index/detail/rtree/query_iterators.hpp	2013-08-28 20:33:54 EDT (Wed, 28 Aug 2013)	(r85507)
@@ -11,7 +11,10 @@
 #ifndef BOOST_GEOMETRY_INDEX_DETAIL_RTREE_QUERY_ITERATORS_HPP
 #define BOOST_GEOMETRY_INDEX_DETAIL_RTREE_QUERY_ITERATORS_HPP
 
-namespace boost { namespace geometry { namespace index { namespace detail { namespace rtree {
+//#define BOOST_GEOMETRY_INDEX_DETAIL_QUERY_ITERATORS_USE_TYPE_ERASURE
+#define BOOST_GEOMETRY_INDEX_DETAIL_QUERY_ITERATORS_USE_MOVE
+
+namespace boost { namespace geometry { namespace index { namespace detail { namespace rtree { namespace iterators {
 
 template <typename Value, typename Allocators>
 struct end_query_iterator
@@ -190,11 +193,11 @@
     return !(l == r);
 }
 
-}}}}} // namespace boost::geometry::index::detail::rtree
+}}}}}} // namespace boost::geometry::index::detail::rtree::iterators
 
-#ifdef BOOST_GEOMETRY_INDEX_DETAIL_ENABLE_TYPE_ERASED_ITERATORS
+#ifndef BOOST_GEOMETRY_INDEX_DETAIL_QUERY_ITERATORS_USE_TYPE_ERASURE
 
-namespace boost { namespace geometry { namespace index { namespace detail { namespace rtree {
+namespace boost { namespace geometry { namespace index { namespace detail { namespace rtree { namespace iterators {
 
 template <typename Value, typename Allocators>
 class query_iterator_base
@@ -248,7 +251,7 @@
 };
 
 template <typename Value, typename Allocators>
-class query_iterator_poly
+class query_iterator
 {
     typedef query_iterator_base<Value, Allocators> iterator_base;
     typedef std::auto_ptr<iterator_base> iterator_ptr;
@@ -260,42 +263,42 @@
     typedef typename Allocators::difference_type difference_type;
     typedef typename Allocators::const_pointer pointer;
 
-    query_iterator_poly() {}
+    query_iterator() {}
 
     template <typename It>
-    query_iterator_poly(It const& it)
+    query_iterator(It const& it)
         : m_ptr(static_cast<iterator_base*>(
                     new query_iterator_wrapper<Value, Allocators, It>(it) ))
     {}
 
-    query_iterator_poly(end_query_iterator<Value, Allocators> const& /*it*/)
+    query_iterator(end_query_iterator<Value, Allocators> const& /*it*/)
     {}
 
-    query_iterator_poly(query_iterator_poly const& o)
+    query_iterator(query_iterator const& o)
         : m_ptr(o.m_ptr.get() ? o.m_ptr->clone() : 0)
     {}
 
-#ifndef BOOST_GEOMETRY_INDEX_DETAIL_ENABLE_TYPE_ERASED_ITERATORS_MOVE
-    query_iterator_poly & operator=(query_iterator_poly const& o)
+#ifndef BOOST_GEOMETRY_INDEX_DETAIL_QUERY_ITERATORS_USE_MOVE
+    query_iterator & operator=(query_iterator const& o)
     {
         m_ptr.reset(o.m_ptr.get() ? o.m_ptr->clone() : 0);
         return *this;
     }
-#else
+#else // !BOOST_GEOMETRY_INDEX_DETAIL_QUERY_ITERATORS_USE_MOVE
 private:
-    BOOST_COPYABLE_AND_MOVABLE(query_iterator_poly)
+    BOOST_COPYABLE_AND_MOVABLE(query_iterator)
 public:
-    query_iterator_poly & operator=(BOOST_COPY_ASSIGN_REF(query_iterator_poly) o)
+    query_iterator & operator=(BOOST_COPY_ASSIGN_REF(query_iterator) o)
     {
         m_ptr.reset(o.m_ptr.get() ? o.m_ptr->clone() : 0);
         return *this;
     }
-    query_iterator_poly(BOOST_RV_REF(query_iterator_poly) o)
+    query_iterator(BOOST_RV_REF(query_iterator) o)
         : m_ptr(o.m_ptr.get())
     {
         o.m_ptr.release();
     }
-    query_iterator_poly & operator=(BOOST_RV_REF(query_iterator_poly) o)
+    query_iterator & operator=(BOOST_RV_REF(query_iterator) o)
     {
         if ( this != boost::addressof(o) )
         {
@@ -304,7 +307,7 @@
         }
         return *this;
     }
-#endif
+#endif // BOOST_GEOMETRY_INDEX_DETAIL_QUERY_ITERATORS_USE_MOVE
 
     reference operator*() const
     {
@@ -316,20 +319,20 @@
         return boost::addressof(m_ptr->dereference());
     }
 
-    query_iterator_poly & operator++()
+    query_iterator & operator++()
     {
         m_ptr->increment();
         return *this;
     }
 
-    query_iterator_poly operator++(int)
+    query_iterator operator++(int)
     {
-        query_iterator_poly temp = *this;
+        query_iterator temp = *this;
         this->operator++();
         return temp;
     }
 
-    friend bool operator==(query_iterator_poly const& l, query_iterator_poly const& r)
+    friend bool operator==(query_iterator const& l, query_iterator const& r)
     {
         if ( l.m_ptr.get() )
         {
@@ -351,13 +354,15 @@
     iterator_ptr m_ptr;
 };
 
-}}}}} // namespace boost::geometry::index::detail::rtree
+}}}}}} // namespace boost::geometry::index::detail::rtree::iterators
+
+#else // BOOST_GEOMETRY_INDEX_DETAIL_QUERY_ITERATORS_USE_TYPE_ERASURE
 
 #include <boost/type_erasure/any.hpp>
 #include <boost/type_erasure/operators.hpp>
 #include <boost/type_erasure/is_empty.hpp>
 
-namespace boost { namespace geometry { namespace index { namespace detail { namespace rtree {
+namespace boost { namespace geometry { namespace index { namespace detail { namespace rtree { namespace iterators {
 
 template<typename T, typename Value, typename Allocators>
 struct single_pass_iterator_concept :
@@ -382,7 +387,7 @@
     > type;
 };
 
-}}}}} // namespace boost::geometry::index::detail::rtree
+}}}}}} // namespace boost::geometry::index::detail::rtree::iterators
 
 namespace boost { namespace type_erasure {
 
@@ -395,17 +400,17 @@
 {
     typedef Value value_type;
     typedef typename Allocators::const_reference reference;
-    typedef typename Allocators::const_pointer;
+    typedef typename Allocators::const_pointer pointer;
     typedef typename Allocators::difference_type difference_type;
     typedef ::std::input_iterator_tag iterator_category;
 };
 
 }} // boost::type_erasure
 
-namespace boost { namespace geometry { namespace index { namespace detail { namespace rtree {
+namespace boost { namespace geometry { namespace index { namespace detail { namespace rtree { namespace iterators {
 
 template <typename Value, typename Allocators>
-class query_iterator_te
+class query_iterator
 {
 public:
     typedef std::input_iterator_tag iterator_category;
@@ -419,33 +424,32 @@
 
 public:
 
-    query_iterator_te() {}
+    query_iterator() {}
 
     template <typename It>
-    query_iterator_te(It const& it)
+    query_iterator(It const& it)
         : m_iterator(it)
     {}
 
-    query_iterator_te(end_query_iterator<Value, Allocators> const& /*it*/)
+    query_iterator(end_query_iterator<Value, Allocators> const& /*it*/)
     {}
 
-#ifdef BOOST_GEOMETRY_INDEX_DETAIL_ENABLE_TYPE_ERASED_ITERATORS_MOVE
+#ifdef BOOST_GEOMETRY_INDEX_DETAIL_QUERY_ITERATORS_USE_MOVE
 private:
-    BOOST_COPYABLE_AND_MOVABLE(query_iterator_te)
+    BOOST_COPYABLE_AND_MOVABLE(query_iterator)
 public:
-    query_iterator_te(query_iterator_te const& o)
+    query_iterator(query_iterator const& o)
         : m_iterator(o.m_iterator)
     {}
-
-    query_iterator_te & operator=(BOOST_COPY_ASSIGN_REF(query_iterator_te) o)
+    query_iterator & operator=(BOOST_COPY_ASSIGN_REF(query_iterator) o)
     {
         m_iterator = o.m_iterator;
         return *this;
     }
-    query_iterator_te(BOOST_RV_REF(query_iterator_te) o)
+    query_iterator(BOOST_RV_REF(query_iterator) o)
         : m_iterator(boost::move(o.m_iterator))
     {}
-    query_iterator_te & operator=(BOOST_RV_REF(query_iterator_te) o)
+    query_iterator & operator=(BOOST_RV_REF(query_iterator) o)
     {
         if ( this != boost::addressof(o) )
         {
@@ -453,7 +457,7 @@
         }
         return *this;
     }
-#endif
+#endif // BOOST_GEOMETRY_INDEX_DETAIL_QUERY_ITERATORS_USE_MOVE
 
     reference operator*() const
     {
@@ -465,20 +469,20 @@
         return boost::addressof(*m_iterator);
     }
 
-    query_iterator_te & operator++()
+    query_iterator & operator++()
     {
         ++m_iterator;
         return *this;
     }
 
-    query_iterator_te operator++(int)
+    query_iterator operator++(int)
     {
-        query_iterator_te temp = *this;
+        query_iterator temp = *this;
         ++m_iterator;
         return temp;
     }
 
-    friend bool operator==(query_iterator_te const& l, query_iterator_te const& r)
+    friend bool operator==(query_iterator const& l, query_iterator const& r)
     {
         if ( !::boost::type_erasure::is_empty(l.m_iterator) )
         {
@@ -500,8 +504,8 @@
     iterator_type m_iterator;
 };
 
-}}}}} // namespace boost::geometry::index::detail::rtree
+}}}}}} // namespace boost::geometry::index::detail::rtree::iterators
 
-#endif // BOOST_GEOMETRY_INDEX_DETAIL_ENABLE_TYPE_ERASED_ITERATORS
+#endif // BOOST_GEOMETRY_INDEX_DETAIL_QUERY_ITERATORS_USE_TYPE_ERASURE
 
 #endif // BOOST_GEOMETRY_INDEX_DETAIL_RTREE_QUERY_ITERATORS_HPP

Deleted: trunk/boost/geometry/index/detail/type_erased_iterators.hpp
==============================================================================
--- trunk/boost/geometry/index/detail/type_erased_iterators.hpp	2013-08-28 20:33:54 EDT (Wed, 28 Aug 2013)	(r85506)
+++ /dev/null	00:00:00 1970	(deleted)
@@ -1,61 +0,0 @@
-// Boost.Geometry Index
-//
-// Type-erased iterators
-//
-// Copyright (c) 2011-2013 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_DETAIL_TYPE_ERASED_ITERATORS_HPP
-#define BOOST_GEOMETRY_INDEX_DETAIL_TYPE_ERASED_ITERATORS_HPP
-
-#include <boost/type_erasure/any.hpp>
-#include <boost/type_erasure/operators.hpp>
-
-namespace boost { namespace geometry { namespace index { namespace detail {
-
-template<typename T, typename ValueType, typename Reference, typename Pointer, typename DifferenceType>
-struct single_pass_iterator_concept :
-    ::boost::mpl::vector<
-        ::boost::type_erasure::copy_constructible<T>,
-        ::boost::type_erasure::equality_comparable<T>,
-        ::boost::type_erasure::dereferenceable<Reference, T>,
-        ::boost::type_erasure::assignable<T>,
-        ::boost::type_erasure::incrementable<T>,
-        ::boost::type_erasure::relaxed // default ctor
-    >
-{};
-
-template <typename ValueType, typename Reference, typename Pointer, typename DifferenceType>
-struct single_pass_iterator_type
-{
-    typedef ::boost::type_erasure::any<
-        single_pass_iterator_concept<
-            ::boost::type_erasure::_self, ValueType, Reference, Pointer, DifferenceType
-        >
-    > type;
-};
-
-}}}} // namespace boost::geometry::index::detail
-
-namespace boost { namespace type_erasure {
-
-template<typename T, typename ValueType, typename Reference, typename Pointer, typename DifferenceType, typename Base>
-struct concept_interface<
-    ::boost::geometry::index::detail::single_pass_iterator_concept<
-        T, ValueType, Reference, Pointer, DifferenceType
-    >, Base, T>
-    : Base
-{
-    typedef ValueType value_type;
-    typedef Reference reference;
-    typedef Pointer pointer;
-    typedef DifferenceType difference_type;
-    typedef ::std::input_iterator_tag iterator_category;
-};
-
-}} // namespace boost::type_erasure
-
-#endif // BOOST_GEOMETRY_INDEX_DETAIL_TYPE_ERASED_ITERATORS_HPP

Modified: trunk/boost/geometry/index/rtree.hpp
==============================================================================
--- trunk/boost/geometry/index/rtree.hpp	Wed Aug 28 19:04:09 2013	(r85506)
+++ trunk/boost/geometry/index/rtree.hpp	2013-08-28 20:33:54 EDT (Wed, 28 Aug 2013)	(r85507)
@@ -61,13 +61,9 @@
 
 #include <boost/geometry/index/detail/rtree/utilities/view.hpp>
 
-#ifdef BOOST_GEOMETRY_INDEX_DETAIL_EXPERIMENTAL
-// query iterators
 #include <boost/geometry/index/detail/rtree/query_iterators.hpp>
-#ifdef BOOST_GEOMETRY_INDEX_DETAIL_ENABLE_TYPE_ERASED_ITERATORS
-// type-erased iterators
-#include <boost/geometry/index/detail/type_erased_iterators.hpp>
-#endif
+
+#ifdef BOOST_GEOMETRY_INDEX_DETAIL_EXPERIMENTAL
 // serialization
 #include <boost/geometry/index/detail/serialization.hpp>
 #endif
@@ -189,6 +185,9 @@
     /*! \brief Unsigned integral type used by the container. */
     typedef typename allocators_type::size_type size_type;
 
+    /*! \brief The type-erased const query iterator. */
+    typedef index::detail::rtree::iterators::query_iterator<value_type, allocators_type> const_query_iterator;
+
 public:
 
     /*!
@@ -731,6 +730,7 @@
 
     \par Throws
     If Value copy constructor or copy assignment throws.
+    If predicates copy throws.
 
     \warning
     Only one \c nearest() perdicate may be passed to the query. Passing more of them results in compile-time error.
@@ -753,34 +753,50 @@
         return query_dispatch(predicates, out_it, boost::mpl::bool_<is_distance_predicate>());
     }
 
-#ifdef BOOST_GEOMETRY_INDEX_DETAIL_EXPERIMENTAL
+    /*!
+    \brief Returns the query iterator pointing at the begin of the query range.
 
-#ifdef BOOST_GEOMETRY_INDEX_DETAIL_ENABLE_TYPE_ERASED_ITERATORS
+    This method returns the iterator which may be used to perform iterative queries. For the information
+    about the predicates which may be passed to this method see query().
+    
+    The type of the returned iterator depends on the type of passed Predicates but the iterator of this type
+    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 method you may get the type e.g. by using C++11 decltype or Boost.Typeof library.
+    This iterator may be compared with iterators returned by both versions of qend() method.
 
-    // BEWARE!
-    // Don't use this type-erased iterator after assigning values returned by qbegin(Pred) and qend()
-    // e.g. don't pass them into the std::copy() or compare them like this:
-    // const_query_iterator i1 = qbegin(...);
-    // const_query_iterator i2 = qend();
-    // i1 == i2; // BAM!
-    // now this will cause undefined behaviour.
-    // using native types is ok:
-    // qbegin(...) == qend();
-
-    typedef typename index::detail::single_pass_iterator_type<
-        value_type, const_reference, const_pointer, difference_type
-    >::type const_query_iterator;
+    \par Example
+    \verbatim
+    // Store the result in the container using std::copy() - it requires both iterators of the same type
+    std::copy(tree.qbegin(bgi::intersects(box)), tree.qend(bgi::intersects(box)), std::back_inserter(result));
 
-    typedef index::detail::rtree::query_iterator_poly<value_type, allocators_type> const_query_iterator_alt;
-    typedef index::detail::rtree::query_iterator_te<value_type, allocators_type> const_query_iterator_alt2;
+    // Store the result in the container using std::copy() and type-erased iterators
+    Rtree::const_query_iterator first = tree.qbegin(bgi::intersects(box));
+    Rtree::const_query_iterator last = tree.qend();
+    std::copy(first, last, std::back_inserter(result));
+
+    // Boost.Typeof
+    typedef BOOST_TYPEOF(tree.qbegin(bgi::nearest(pt, 10000))) Iter;
+    for ( Iter it = tree.qbegin(bgi::nearest(pt, 10000)) ; it != tree.qend() ; ++it )
+    {
+        // do something with value
+        if ( has_enough_nearest_values() )
+            break;
+    }
+    \endverbatim
 
-#endif // BOOST_GEOMETRY_INDEX_DETAIL_ENABLE_TYPE_ERASED_ITERATORS
+    \par Throws
+    If predicates copy throws.
+    If allocation throws.
 
+    \param predicates   Predicates.
+    
+    \return             The iterator pointing at the begin of the query range.
+    */
     template <typename Predicates>
     typename boost::mpl::if_c<
         detail::predicates_count_distance<Predicates>::value == 0,
-        detail::rtree::spatial_query_iterator<value_type, options_type, translator_type, box_type, allocators_type, Predicates>,
-        detail::rtree::distance_query_iterator<
+        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
         >
@@ -792,8 +808,8 @@
 
         typedef typename boost::mpl::if_c<
             detail::predicates_count_distance<Predicates>::value == 0,
-            detail::rtree::spatial_query_iterator<value_type, options_type, translator_type, box_type, allocators_type, Predicates>,
-            detail::rtree::distance_query_iterator<
+            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
             >
@@ -805,11 +821,37 @@
         return iterator_type(m_members.root, m_members.translator(), predicates);
     }
 
+    /*!
+    \brief Returns the query iterator pointing at the end of the query range.
+
+    This method returns the iterator which may be used to perform iterative queries. For the information
+    about the predicates which may be passed to this method see query().
+    
+    The type of the returned iterator depends on the type of passed Predicates but the iterator of this type
+    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 method you may get the type e.g. by using C++11 decltype or Boost.Typeof library.
+
+    The type of the iterator returned by this method is the same as the one returned by qbegin() to which
+    the same predicates were passed.
+
+    \par Example
+    \verbatim
+    // Store the result in the container using std::copy() - it requires both iterators of the same type
+    std::copy(tree.qbegin(bgi::intersects(box)), tree.qend(bgi::intersects(box)), std::back_inserter(result));
+    \endverbatim
+
+    \par Throws
+    If predicates copy throws.
+
+    \param predicates   Predicates.
+    
+    \return             The iterator pointing at the end of the query range.
+    */
     template <typename Predicates>
     typename boost::mpl::if_c<
         detail::predicates_count_distance<Predicates>::value == 0,
-        detail::rtree::spatial_query_iterator<value_type, options_type, translator_type, box_type, allocators_type, Predicates>,
-        detail::rtree::distance_query_iterator<
+        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
         >
@@ -821,8 +863,8 @@
 
         typedef typename boost::mpl::if_c<
             detail::predicates_count_distance<Predicates>::value == 0,
-            detail::rtree::spatial_query_iterator<value_type, options_type, translator_type, box_type, allocators_type, Predicates>,
-            detail::rtree::distance_query_iterator<
+            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
             >
@@ -831,14 +873,47 @@
         return iterator_type(m_members.translator(), predicates);
     }
 
-    detail::rtree::end_query_iterator<value_type, allocators_type>
+    /*!
+    \brief Returns the query iterator pointing at the end of the query range.
+
+    This method returns the iterator which may be compared with the iterator returned by qbegin() in order to
+    check if the query has ended.
+    
+    The type of the returned iterator is different than the type returned by qbegin() but the iterator of this type
+    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
+    method, which most certainly will be faster than the type-erased iterator, you may get the type
+    e.g. by using C++11 decltype or Boost.Typeof library.
+
+    The type of the iterator returned by this method is dfferent than the type returned by qbegin().
+
+    \par Example
+    \verbatim
+    // Store the result in the container using std::copy() and type-erased iterators
+    Rtree::const_query_iterator first = tree.qbegin(bgi::intersects(box));
+    Rtree::const_query_iterator last = tree.qend();
+    std::copy(first, last, std::back_inserter(result));
+
+    // Boost.Typeof
+    typedef BOOST_TYPEOF(tree.qbegin(bgi::nearest(pt, 10000))) Iter;
+    for ( Iter it = tree.qbegin(bgi::nearest(pt, 10000)) ; it != tree.qend() ; ++it )
+    {
+        // do something with value
+        if ( has_enough_nearest_values() )
+            break;
+    }
+    \endverbatim
+
+    \par Throws
+    Nothing
+    
+    \return             The iterator pointing at the end of the query range.
+    */
+    detail::rtree::iterators::end_query_iterator<value_type, allocators_type>
     qend() const
     {
-        return detail::rtree::end_query_iterator<value_type, allocators_type>();
+        return detail::rtree::iterators::end_query_iterator<value_type, allocators_type>();
     }
 
-#endif // BOOST_GEOMETRY_INDEX_DETAIL_EXPERIMENTAL
-
     /*!
     \brief Returns the number of stored values.