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
/*!