Subject: [Boost-commit] svn:boost r83935 - in trunk/boost/geometry/index: . detail/rtree/node detail/rtree/visitors
From: adam.wulkiewicz_at_[hidden]
Date: 2013-04-16 18:08:56
Author: awulkiew
Date: 2013-04-16 18:08:55 EDT (Tue, 16 Apr 2013)
New Revision: 83935
URL: http://svn.boost.org/trac/boost/changeset/83935
Log:
geometry.index: added experimental spatial query iterator and rtree::qbegin() and rtree::qend() methods, added allocator_type to Allocators.
Text files modified:
trunk/boost/geometry/index/detail/rtree/node/node_d_mem_dynamic.hpp | 1
trunk/boost/geometry/index/detail/rtree/node/node_d_mem_static.hpp | 1
trunk/boost/geometry/index/detail/rtree/node/node_s_mem_dynamic.hpp | 1
trunk/boost/geometry/index/detail/rtree/node/node_s_mem_static.hpp | 1
trunk/boost/geometry/index/detail/rtree/visitors/spatial_query.hpp | 225 +++++++++++++++++++++++++++++----------
trunk/boost/geometry/index/rtree.hpp | 85 +++++++++++++++
6 files changed, 254 insertions(+), 60 deletions(-)
Modified: trunk/boost/geometry/index/detail/rtree/node/node_d_mem_dynamic.hpp
==============================================================================
--- trunk/boost/geometry/index/detail/rtree/node/node_d_mem_dynamic.hpp (original)
+++ trunk/boost/geometry/index/detail/rtree/node/node_d_mem_dynamic.hpp 2013-04-16 18:08:55 EDT (Tue, 16 Apr 2013)
@@ -165,6 +165,7 @@
>::other
{
public:
+ typedef Allocator allocator_type;
typedef typename Allocator::size_type size_type;
typedef typename Allocator::template rebind<
Modified: trunk/boost/geometry/index/detail/rtree/node/node_d_mem_static.hpp
==============================================================================
--- trunk/boost/geometry/index/detail/rtree/node/node_d_mem_static.hpp (original)
+++ trunk/boost/geometry/index/detail/rtree/node/node_d_mem_static.hpp 2013-04-16 18:08:55 EDT (Tue, 16 Apr 2013)
@@ -114,6 +114,7 @@
>::other
{
public:
+ typedef Allocator allocator_type;
typedef typename Allocator::size_type size_type;
typedef typename Allocator::template rebind<
Modified: trunk/boost/geometry/index/detail/rtree/node/node_s_mem_dynamic.hpp
==============================================================================
--- trunk/boost/geometry/index/detail/rtree/node/node_s_mem_dynamic.hpp (original)
+++ trunk/boost/geometry/index/detail/rtree/node/node_s_mem_dynamic.hpp 2013-04-16 18:08:55 EDT (Tue, 16 Apr 2013)
@@ -97,6 +97,7 @@
>::other
{
public:
+ typedef Allocator allocator_type;
typedef typename Allocator::size_type size_type;
typedef typename Allocator::template rebind<
Modified: trunk/boost/geometry/index/detail/rtree/node/node_s_mem_static.hpp
==============================================================================
--- trunk/boost/geometry/index/detail/rtree/node/node_s_mem_static.hpp (original)
+++ trunk/boost/geometry/index/detail/rtree/node/node_s_mem_static.hpp 2013-04-16 18:08:55 EDT (Tue, 16 Apr 2013)
@@ -95,6 +95,7 @@
>::other
{
public:
+ typedef Allocator allocator_type;
typedef typename Allocator::size_type size_type;
typedef typename Allocator::template rebind<
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-04-16 18:08:55 EDT (Tue, 16 Apr 2013)
@@ -75,67 +75,172 @@
size_type found_count;
};
-//template <typename Value, typename Options, typename Translator, typename Box, typename Allocators, typename Predicates, typename OutIter>
-//struct spatial_query_incremental
-// : public rtree::visitor<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag, true>::type
-//{
-// typedef typename rtree::node<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type node;
-// typedef typename rtree::internal_node<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type internal_node;
-// typedef typename rtree::leaf<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type leaf;
-//
-// typedef typename Allocators::size_type size_type;
-// typedef typename Allocators::node_pointer node_pointer;
-//
-// static const unsigned predicates_len = index::detail::predicates_length<Predicates>::value;
-//
-// inline spatial_query_incremental(Translator const& t, Predicates const& p)
-// : tr(t), pred(p)
-// {}
-//
-// inline void operator()(internal_node const& n)
-// {
-// typedef typename rtree::elements_type<internal_node>::type elements_type;
-// elements_type const& elements = rtree::elements(n);
-//
-// internal_stack.push_back(std::make_pair(elements.begin(), elements.end()));
-//
-// //// if node meets predicates
-// //// 0 - dummy value
-// //if ( index::detail::predicates_check<index::detail::bounds_tag, 0, predicates_len>(pred, 0, internal_stack.back().first->first) )
-// //{
-// // nodes.push_back(it->second);
-// // rtree::apply_visitor(*this, *it->second);
-// //}
-// }
-//
-// inline void operator()(leaf const& n)
-// {
-// typedef typename rtree::elements_type<leaf>::type elements_type;
-// elements_type const& elements = rtree::elements(n);
-//
-// leaf_range.push_back(std::make_pair(elements.begin(), elements.end()));
-//
-// //// if value meets predicates
-// //if ( index::detail::predicates_check<index::detail::value_tag, 0, predicates_len>(pred, *it, tr(*it)) )
-// //{
-// // out_iter = *it;
-// // ++out_iter;
-//
-// // ++found_count;
-// //}
-// }
-//
-// Translator const& tr;
-// Predicates pred;
-//
-// typedef typename rtree::elements_type<internal_node>::type::const_iterator internal_iterator;
-// typedef typename rtree::elements_type<leaf>::type::const_iterator leaf_iterator;
-//
-// std::vector< std::pair<internal_iterator, internal_iterator> > internal_stack;
-// std::pair<leaf_iterator, leaf_iterator> leaf_range;
-//};
+template <typename Value, typename Options, typename Translator, typename Box, typename Allocators, typename Predicates>
+struct spatial_query_incremental
+ : public rtree::visitor<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag, true>::type
+{
+ typedef typename rtree::node<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type node;
+ typedef typename rtree::internal_node<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type internal_node;
+ typedef typename rtree::leaf<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type leaf;
-}}} // namespace detail::rtree::visitors
+ typedef typename Allocators::size_type size_type;
+ typedef typename Allocators::node_pointer node_pointer;
+
+ typedef typename rtree::elements_type<internal_node>::type::const_iterator internal_iterator;
+ typedef typename rtree::elements_type<leaf>::type leaf_elements;
+
+ static const unsigned predicates_len = index::detail::predicates_length<Predicates>::value;
+
+ inline spatial_query_incremental(Translator const& t, Predicates const& p)
+ : tr(t), pred(p)
+ , values(0), value_index(0)
+ {}
+
+ inline void operator()(internal_node const& n)
+ {
+ typedef typename rtree::elements_type<internal_node>::type elements_type;
+ elements_type const& elements = rtree::elements(n);
+
+ internal_stack.push_back(std::make_pair(elements.begin(), elements.end()));
+ }
+
+ inline void operator()(leaf const& n)
+ {
+ typedef typename rtree::elements_type<leaf>::type elements_type;
+ elements_type const& elements = rtree::elements(n);
+
+ values = &elements;
+ value_index = 0;
+ }
+
+ Value const& dereference() const
+ {
+ BOOST_ASSERT_MSG(values, "not dereferencable");
+ return (*values)[value_index];
+ }
+
+ void increment()
+ {
+ for (;;)
+ {
+ if ( values )
+ {
+ // ERROR: infinite loop - value_index isn't incremented
+
+ for ( ;; ++value_index )
+ {
+ if ( values->size() <= value_index )
+ {
+ values = 0;
+ value_index = 0;
+ break;
+ }
+
+ Value const& v = (*values)[value_index];
+ if ( index::detail::predicates_check<index::detail::value_tag, 0, predicates_len>(pred, v, tr(v)) )
+ return;
+ }
+ }
+
+ // move to the next leaf if values aren't set
+ for ( ; !values ; ++internal_stack.back().first )
+ {
+ if ( internal_stack.empty() )
+ return;
+
+ if ( internal_stack.back().first == internal_stack.back().second )
+ {
+ internal_stack.pop_back();
+ continue;
+ }
+
+ if ( index::detail::predicates_check<index::detail::bounds_tag, 0, predicates_len>(pred, 0, internal_stack.back().first->first) )
+ rtree::apply_visitor(*this, *(internal_stack.back().first->second));
+ }
+ }
+ }
+
+ friend bool operator==(spatial_query_incremental const& l, spatial_query_incremental const& r)
+ {
+ return (l.values == r.values) && (l.value_index == r.value_index);
+ }
+
+ Translator const& tr;
+ Predicates pred;
+
+ boost::container::vector< std::pair<internal_iterator, internal_iterator> > internal_stack;
+ const leaf_elements * values;
+ size_type value_index;
+};
+
+} // 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;
+
+ // WARNING! If const Value is passed to rebind it won't compile for interprocess' allocator
+ typedef typename Allocators::allocator_type::template rebind<Value>::other allocator_type;
+
+public:
+
+ typedef std::input_iterator_tag iterator_category;
+ typedef const Value value_type;
+ typedef Value const& reference;
+ typedef typename allocator_type::difference_type difference_type;
+ typedef typename allocator_type::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 boost::geometry::index
Modified: trunk/boost/geometry/index/rtree.hpp
==============================================================================
--- trunk/boost/geometry/index/rtree.hpp (original)
+++ trunk/boost/geometry/index/rtree.hpp 2013-04-16 18:08:55 EDT (Tue, 16 Apr 2013)
@@ -719,6 +719,40 @@
return query_dispatch(predicates, out_it, boost::mpl::bool_<is_nearest>());
}
+#ifdef BOOST_GEOMETRY_INDEX_DETAIL_EXPERIMENTAL
+
+ template <typename Predicates>
+ typename boost::mpl::if_c<
+ detail::predicates_count_nearest<Predicates>::value == 0,
+ detail::rtree::spatial_query_iterator<value_type, options_type, translator_type, box_type, allocators_type, Predicates>,
+ void
+ >::type
+ qbegin(Predicates const& predicates) const
+ {
+ static const unsigned nearest_count = detail::predicates_count_nearest<Predicates>::value;
+ static const bool is_nearest = 0 < nearest_count;
+ BOOST_MPL_ASSERT_MSG((nearest_count <= 1), PASS_ONLY_ONE_NEAREST_PREDICATE, (Predicates));
+
+ return qbegin_dispatch(predicates, boost::mpl::bool_<is_nearest>());
+ }
+
+ template <typename Predicates>
+ typename boost::mpl::if_c<
+ detail::predicates_count_nearest<Predicates>::value == 0,
+ detail::rtree::spatial_query_iterator<value_type, options_type, translator_type, box_type, allocators_type, Predicates>,
+ void
+ >::type
+ qend(Predicates const& predicates) const
+ {
+ static const unsigned nearest_count = detail::predicates_count_nearest<Predicates>::value;
+ static const bool is_nearest = 0 < nearest_count;
+ BOOST_MPL_ASSERT_MSG((nearest_count <= 1), PASS_ONLY_ONE_NEAREST_PREDICATE, (Predicates));
+
+ return qend_dispatch(predicates, boost::mpl::bool_<is_nearest>());
+ }
+
+#endif // BOOST_GEOMETRY_INDEX_DETAIL_EXPERIMENTAL
+
/*!
\brief Returns the number of stored values.
@@ -1104,6 +1138,57 @@
return raw_nearest_k(nearest_pred.distance_predicates, nearest_pred.count, predicates, out_it);
}
+#ifdef BOOST_GEOMETRY_INDEX_DETAIL_EXPERIMENTAL
+
+ template <typename Predicates>
+ typename
+ boost::mpl::if_c<
+ detail::predicates_count_nearest<Predicates>::value == 0,
+ detail::rtree::spatial_query_iterator<value_type, options_type, translator_type, box_type, allocators_type, Predicates>,
+ void
+ >::type
+ qbegin_dispatch(Predicates const& predicates, boost::mpl::bool_<false> const& /*is_nearest*/) const
+ {
+ typedef detail::rtree::spatial_query_iterator<
+ value_type, options_type, translator_type, box_type, allocators_type, Predicates
+ > iterator_type;
+
+ if ( !m_members.root )
+ return iterator_type(m_members.translator(), predicates);
+
+ return iterator_type(m_members.root, m_members.translator(), predicates);
+ }
+
+ template <typename Predicates>
+ void qbegin_dispatch(Predicates const& predicates, boost::mpl::bool_<true> const& /*is_nearest*/) const
+ {
+ BOOST_MPL_ASSERT_MSG(false, NEAREST_QUERY_ITERATOR_NOT_IMPLEMENTED_YET, (rtree));
+ }
+
+ template <typename Predicates>
+ typename
+ boost::mpl::if_c<
+ detail::predicates_count_nearest<Predicates>::value == 0,
+ detail::rtree::spatial_query_iterator<value_type, options_type, translator_type, box_type, allocators_type, Predicates>,
+ void
+ >::type
+ qend_dispatch(Predicates const& predicates, boost::mpl::bool_<false> const& /*is_nearest*/) const
+ {
+ typedef detail::rtree::spatial_query_iterator<
+ value_type, options_type, translator_type, box_type, allocators_type, Predicates
+ > iterator_type;
+
+ return iterator_type(m_members.translator(), predicates);
+ }
+
+ template <typename Predicates>
+ void qend_dispatch(Predicates const& predicates, boost::mpl::bool_<true> const& /*is_nearest*/) const
+ {
+ BOOST_MPL_ASSERT_MSG(false, NEAREST_QUERY_ITERATOR_NOT_IMPLEMENTED_YET, (rtree));
+ }
+
+#endif // BOOST_GEOMETRY_INDEX_DETAIL_EXPERIMENTAL
+
/*!
\brief Find k values meeting distances and spatial predicates.