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

Subject: [Boost-commit] svn:boost r84120 - in trunk/boost/geometry/index: . detail/rtree detail/rtree/visitors
From: adam.wulkiewicz_at_[hidden]
Date: 2013-05-02 20:14:34

Author: awulkiew
Date: 2013-05-02 20:14:33 EDT (Thu, 02 May 2013)
New Revision: 84120
URL: http://svn.boost.org/trac/boost/changeset/84120

Log:
geometry.index: added experimental end_query_iterator which may be compared with spatial_query_iterator or nearest_query_iterator to check if query is finished.
Added:
   trunk/boost/geometry/index/detail/rtree/query_iterators.hpp   (contents, props changed)
Text files modified: 
   trunk/boost/geometry/index/detail/rtree/visitors/nearest_query.hpp |    72 +++------------------------------------ 
   trunk/boost/geometry/index/detail/rtree/visitors/spatial_query.hpp |    72 +++------------------------------------ 
   trunk/boost/geometry/index/rtree.hpp                               |    19 ++++++++++                              
   3 files changed, 33 insertions(+), 130 deletions(-)

Added: trunk/boost/geometry/index/detail/rtree/query_iterators.hpp
==============================================================================
--- (empty file)
+++ trunk/boost/geometry/index/detail/rtree/query_iterators.hpp	2013-05-02 20:14:33 EDT (Thu, 02 May 2013)
@@ -0,0 +1,230 @@
+// Boost.Geometry Index
+//
+// R-tree query 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_RTREE_QUERY_ITERATORS_HPP
+#define BOOST_GEOMETRY_INDEX_DETAIL_RTREE_QUERY_ITERATORS_HPP
+
+namespace boost { namespace geometry { namespace index {
+
+namespace detail { namespace rtree {
+
+template <typename Value, typename Allocators>
+struct end_query_iterator
+{
+    typedef std::input_iterator_tag iterator_category;
+    typedef Value value_type;
+    typedef typename Allocators::const_reference reference;
+    typedef typename Allocators::difference_type difference_type;
+    typedef typename Allocators::const_pointer pointer;
+
+    reference operator*() const
+    {
+        BOOST_ASSERT_MSG(false, "iterator not dereferencable");
+        pointer p(0);
+        return *p;
+    }
+
+    const value_type * operator->() const
+    {
+        BOOST_ASSERT_MSG(false, "iterator not dereferencable");
+        const value_type * p = 0;
+        return p;
+    }
+
+    end_query_iterator & operator++()
+    {
+        BOOST_ASSERT_MSG(false, "iterator not incrementable");
+        return *this;
+    }
+
+    end_query_iterator operator++(int)
+    {
+        BOOST_ASSERT_MSG(false, "iterator not incrementable");
+        return *this;
+    }
+
+    friend bool operator==(end_query_iterator l, end_query_iterator r)
+    {
+        return true;
+    }
+
+    friend bool operator!=(end_query_iterator l, end_query_iterator r)
+    {
+        return false;
+    }
+};
+
+template <typename Value, typename Options, typename Translator, typename Box, typename Allocators, typename Predicates>
+class spatial_query_iterator
+{
+    typedef visitors::spatial_query_incremental<Value, Options, Translator, Box, Allocators, Predicates> visitor_type;
+    typedef typename visitor_type::node_pointer node_pointer;
+
+public:
+    typedef std::input_iterator_tag iterator_category;
+    typedef Value value_type;
+    typedef typename Allocators::const_reference reference;
+    typedef typename Allocators::difference_type difference_type;
+    typedef typename Allocators::const_pointer pointer;
+
+    inline spatial_query_iterator(Translator const& t, Predicates const& p)
+        : m_visitor(t, p)
+    {}
+
+    inline spatial_query_iterator(node_pointer root, Translator const& t, Predicates const& p)
+        : m_visitor(t, p)
+    {
+        detail::rtree::apply_visitor(m_visitor, *root);
+        m_visitor.increment();
+    }
+
+    reference operator*() const
+    {
+        return m_visitor.dereference();
+    }
+
+    const value_type * operator->() const
+    {
+        return boost::addressof(m_visitor.dereference());
+    }
+
+    spatial_query_iterator & operator++()
+    {
+        m_visitor.increment();
+        return *this;
+    }
+
+    spatial_query_iterator operator++(int)
+    {
+        spatial_query_iterator temp = *this;
+        this->operator++();
+        return temp;
+    }
+
+    friend bool operator==(spatial_query_iterator const& l, spatial_query_iterator const& r)
+    {
+        return l.m_visitor == r.m_visitor;
+    }
+
+    friend bool operator==(spatial_query_iterator const& l, end_query_iterator<Value, Allocators>)
+    {
+        return l.m_visitor.is_end();
+    }
+
+    friend bool operator==(end_query_iterator<Value, Allocators>, spatial_query_iterator const& r)
+    {
+        return r.m_visitor.is_end();
+    }
+
+    friend bool operator!=(spatial_query_iterator const& l, spatial_query_iterator const& r)
+    {
+        return l.m_visitor != r.m_visitor;
+    }
+
+    friend bool operator!=(spatial_query_iterator const& l, end_query_iterator<Value, Allocators>)
+    {
+        return !l.m_visitor.is_end();
+    }
+
+    friend bool operator!=(end_query_iterator<Value, Allocators>, spatial_query_iterator const& r)
+    {
+        return !r.m_visitor.is_end();
+    }
+    
+private:
+    visitor_type m_visitor;
+};
+
+template <typename Value, typename Options, typename Translator, typename Box, typename Allocators, typename Predicates, unsigned NearestPredicateIndex>
+class nearest_query_iterator
+{
+    typedef visitors::nearest_query_incremental<Value, Options, Translator, Box, Allocators, Predicates, NearestPredicateIndex> visitor_type;
+    typedef typename visitor_type::node_pointer node_pointer;
+
+public:
+    typedef std::input_iterator_tag iterator_category;
+    typedef Value value_type;
+    typedef typename Allocators::const_reference reference;
+    typedef typename Allocators::difference_type difference_type;
+    typedef typename Allocators::const_pointer pointer;
+
+    inline nearest_query_iterator(Translator const& t, Predicates const& p)
+        : m_visitor(t, p)
+    {}
+
+    inline nearest_query_iterator(node_pointer root, Translator const& t, Predicates const& p)
+        : m_visitor(t, p)
+    {
+        detail::rtree::apply_visitor(m_visitor, *root);
+        m_visitor.increment();
+    }
+
+    reference operator*() const
+    {
+        return m_visitor.dereference();
+    }
+
+    const value_type * operator->() const
+    {
+        return boost::addressof(m_visitor.dereference());
+    }
+
+    nearest_query_iterator & operator++()
+    {
+        m_visitor.increment();
+        return *this;
+    }
+
+    nearest_query_iterator operator++(int)
+    {
+        nearest_query_iterator temp = *this;
+        this->operator++();
+        return temp;
+    }
+
+    friend bool operator==(nearest_query_iterator const& l, nearest_query_iterator const& r)
+    {
+        return l.m_visitor == r.m_visitor;
+    }
+
+    friend bool operator==(nearest_query_iterator const& l, end_query_iterator<Value, Allocators>)
+    {
+        return l.m_visitor.is_end();
+    }
+
+    friend bool operator==(end_query_iterator<Value, Allocators>, nearest_query_iterator const& r)
+    {
+        return r.m_visitor.is_end();
+    }
+
+    friend bool operator!=(nearest_query_iterator const& l, nearest_query_iterator const& r)
+    {
+        return l.m_visitor != r.m_visitor;
+    }
+
+    friend bool operator!=(nearest_query_iterator const& l, end_query_iterator<Value, Allocators>)
+    {
+        return !l.m_visitor.is_end();
+    }
+
+    friend bool operator!=(end_query_iterator<Value, Allocators>, nearest_query_iterator const& r)
+    {
+        return !r.m_visitor.is_end();
+    }
+
+private:
+    visitor_type m_visitor;
+};
+
+}} // namespace detail::rtree
+
+}}} // namespace boost::geometry::index
+
+#endif // BOOST_GEOMETRY_INDEX_DETAIL_RTREE_QUERY_ITERATORS_HPP

Modified: trunk/boost/geometry/index/detail/rtree/visitors/nearest_query.hpp
==============================================================================
--- trunk/boost/geometry/index/detail/rtree/visitors/nearest_query.hpp	(original)
+++ trunk/boost/geometry/index/detail/rtree/visitors/nearest_query.hpp	2013-05-02 20:14:33 EDT (Thu, 02 May 2013)
@@ -470,10 +470,15 @@
         }
     }
 
+    bool is_end() const
+    {
+        return (std::numeric_limits<size_type>::max)() == current_neighbor;
+    }
+
     friend bool operator==(nearest_query_incremental const& l, nearest_query_incremental const& r)
     {
         BOOST_ASSERT_MSG(l.current_neighbor != r.current_neighbor ||
-                         l.current_neighbor == (std::numeric_limits<size_type>::max)() ||
+                         (std::numeric_limits<size_type>::max)() == l.current_neighbor ||
                          l.neighbors[l.current_neighbor].second == r.neighbors[r.current_neighbor].second,
                          "not corresponding iterators");
         return l.current_neighbor == r.current_neighbor;
@@ -629,70 +634,7 @@
     node_distance_type next_closest_node_distance;
 };
 
-} // namespace visitors
-
-template <typename Value, typename Options, typename Translator, typename Box, typename Allocators, typename Predicates, unsigned NearestPredicateIndex>
-class nearest_query_iterator
-{
-    typedef visitors::nearest_query_incremental<Value, Options, Translator, Box, Allocators, Predicates, NearestPredicateIndex> visitor_type;
-    typedef typename visitor_type::node_pointer node_pointer;
-
-public:
-    typedef std::input_iterator_tag iterator_category;
-    typedef Value value_type;
-    typedef typename Allocators::const_reference reference;
-    typedef typename Allocators::difference_type difference_type;
-    typedef typename Allocators::const_pointer pointer;
-
-    inline nearest_query_iterator(Translator const& t, Predicates const& p)
-        : m_visitor(t, p)
-    {}
-
-    inline nearest_query_iterator(node_pointer root, Translator const& t, Predicates const& p)
-        : m_visitor(t, p)
-    {
-        detail::rtree::apply_visitor(m_visitor, *root);
-        m_visitor.increment();
-    }
-
-    reference operator*() const
-    {
-        return m_visitor.dereference();
-    }
-
-    const value_type * operator->() const
-    {
-        return boost::addressof(m_visitor.dereference());
-    }
-
-    nearest_query_iterator & operator++()
-    {
-        m_visitor.increment();
-        return *this;
-    }
-
-    nearest_query_iterator operator++(int)
-    {
-        nearest_query_iterator temp = *this;
-        this->operator++();
-        return temp;
-    }
-
-    friend bool operator==(nearest_query_iterator const& l, nearest_query_iterator const& r)
-    {
-        return l.m_visitor == r.m_visitor;
-    }
-
-    friend bool operator!=(nearest_query_iterator const& l, nearest_query_iterator const& r)
-    {
-        return !(l.m_visitor == r.m_visitor);
-    }
-
-private:
-    visitor_type m_visitor;
-};
-
-}} // namespace detail::rtree
+}}} // namespace detail::rtree::visitors
 
 }}} // namespace boost::geometry::index
 

Modified: trunk/boost/geometry/index/detail/rtree/visitors/spatial_query.hpp
==============================================================================
--- trunk/boost/geometry/index/detail/rtree/visitors/spatial_query.hpp	(original)
+++ trunk/boost/geometry/index/detail/rtree/visitors/spatial_query.hpp	2013-05-02 20:14:33 EDT (Thu, 02 May 2013)
@@ -170,9 +170,14 @@
         }
     }
 
+    bool is_end() const
+    {
+        return 0 == m_values;
+    }
+
     friend bool operator==(spatial_query_incremental const& l, spatial_query_incremental const& r)
     {
-        return (l.m_values == r.m_values) && (l.m_values == 0 || l.m_current == r.m_current );
+        return (l.m_values == r.m_values) && (0 == l.m_values || l.m_current == r.m_current );
     }
 
 private:
@@ -186,70 +191,7 @@
     leaf_iterator m_current, m_last;
 };
 
-} // namespace visitors
-
-template <typename Value, typename Options, typename Translator, typename Box, typename Allocators, typename Predicates>
-class spatial_query_iterator
-{
-    typedef visitors::spatial_query_incremental<Value, Options, Translator, Box, Allocators, Predicates> visitor_type;
-    typedef typename visitor_type::node_pointer node_pointer;
-
-public:
-    typedef std::input_iterator_tag iterator_category;
-    typedef Value value_type;
-    typedef typename Allocators::const_reference reference;
-    typedef typename Allocators::difference_type difference_type;
-    typedef typename Allocators::const_pointer pointer;
-
-    inline spatial_query_iterator(Translator const& t, Predicates const& p)
-        : m_visitor(t, p)
-    {}
-
-    inline spatial_query_iterator(node_pointer root, Translator const& t, Predicates const& p)
-        : m_visitor(t, p)
-    {
-        detail::rtree::apply_visitor(m_visitor, *root);
-        m_visitor.increment();
-    }
-
-    reference operator*() const
-    {
-        return m_visitor.dereference();
-    }
-
-    const value_type * operator->() const
-    {
-        return boost::addressof(m_visitor.dereference());
-    }
-
-    spatial_query_iterator & operator++()
-    {
-        m_visitor.increment();
-        return *this;
-    }
-
-    spatial_query_iterator operator++(int)
-    {
-        spatial_query_iterator temp = *this;
-        this->operator++();
-        return temp;
-    }
-
-    friend bool operator==(spatial_query_iterator const& l, spatial_query_iterator const& r)
-    {
-        return l.m_visitor == r.m_visitor;
-    }
-
-    friend bool operator!=(spatial_query_iterator const& l, spatial_query_iterator const& r)
-    {
-        return !(l.m_visitor == r.m_visitor);
-    }
-    
-private:
-    visitor_type m_visitor;
-};
-
-}} // namespace detail::rtree
+}}} // namespace detail::rtree::visitors
 
 }}} // namespace boost::geometry::index
 

Modified: trunk/boost/geometry/index/rtree.hpp
==============================================================================
--- trunk/boost/geometry/index/rtree.hpp	(original)
+++ trunk/boost/geometry/index/rtree.hpp	2013-05-02 20:14:33 EDT (Thu, 02 May 2013)
@@ -57,9 +57,12 @@
 
 #include <boost/geometry/index/inserter.hpp>
 
+#ifdef BOOST_GEOMETRY_INDEX_DETAIL_EXPERIMENTAL
+#include <boost/geometry/index/detail/rtree/query_iterators.hpp>
 #ifdef BOOST_GEOMETRY_INDEX_DETAIL_ENABLE_TYPE_ERASED_ITERATORS
 #include <boost/geometry/index/detail/type_erased_iterators.hpp>
 #endif
+#endif
 
 // TODO change the name to bounding_tree
 
@@ -743,6 +746,16 @@
 
 #ifdef BOOST_GEOMETRY_INDEX_DETAIL_ENABLE_TYPE_ERASED_ITERATORS
 
+    // 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;
@@ -804,6 +817,12 @@
         return iterator_type(m_members.translator(), predicates);
     }
 
+    detail::rtree::end_query_iterator<value_type, allocators_type>
+    qend() const
+    {
+        return detail::rtree::end_query_iterator<value_type, allocators_type>();
+    }
+
 #endif // BOOST_GEOMETRY_INDEX_DETAIL_EXPERIMENTAL
 
     /*!