|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r82600 - in sandbox-branches/geometry/index: boost/geometry/index boost/geometry/index/detail boost/geometry/index/detail/rtree/visitors test/rtree tests
From: adam.wulkiewicz_at_[hidden]
Date: 2013-01-24 17:24:59
Author: awulkiew
Date: 2013-01-24 17:24:58 EST (Thu, 24 Jan 2013)
New Revision: 82600
URL: http://svn.boost.org/trac/boost/changeset/82600
Log:
Implemented all variants of rtree::query() method. spatial and nearest returning 1 and k values.
Text files modified:
sandbox-branches/geometry/index/boost/geometry/index/detail/distance_predicates.hpp | 190 +++++++++++++++++++++++++++++++++++++++
sandbox-branches/geometry/index/boost/geometry/index/detail/predicates.hpp | 185 ++++++++++++++++++++++++++++++++++----
sandbox-branches/geometry/index/boost/geometry/index/detail/rtree/visitors/nearest_query.hpp | 6
sandbox-branches/geometry/index/boost/geometry/index/detail/rtree/visitors/spatial_query.hpp | 6
sandbox-branches/geometry/index/boost/geometry/index/detail/tuples.hpp | 30 ++++++
sandbox-branches/geometry/index/boost/geometry/index/distance_predicates.hpp | 16 +++
sandbox-branches/geometry/index/boost/geometry/index/predicates.hpp | 38 ++++++++
sandbox-branches/geometry/index/boost/geometry/index/rtree.hpp | 73 ++++++++++++++
sandbox-branches/geometry/index/test/rtree/test_rtree.hpp | 23 ++++
sandbox-branches/geometry/index/tests/additional_speed.cpp | 107 ++++++++++++++++++++++
10 files changed, 643 insertions(+), 31 deletions(-)
Modified: sandbox-branches/geometry/index/boost/geometry/index/detail/distance_predicates.hpp
==============================================================================
--- sandbox-branches/geometry/index/boost/geometry/index/detail/distance_predicates.hpp (original)
+++ sandbox-branches/geometry/index/boost/geometry/index/detail/distance_predicates.hpp 2013-01-24 17:24:58 EST (Thu, 24 Jan 2013)
@@ -29,6 +29,194 @@
namespace boost { namespace geometry { namespace index { namespace detail {
// ------------------------------------------------------------------ //
+// predicate
+// ------------------------------------------------------------------ //
+
+template <typename DistancePredicates>
+struct nearest
+{
+ static const bool is_one = false;
+
+ nearest(DistancePredicates const& dpred, unsigned k)
+ : distance_predicates(dpred)
+ , count(k)
+ {}
+ DistancePredicates const& distance_predicates;
+ unsigned count;
+};
+
+template <typename DistancePredicates>
+struct predicate_check<nearest<DistancePredicates>, value_tag>
+{
+ template <typename Value, typename Box>
+ static inline bool apply(nearest<DistancePredicates> const&, Value const&, Box const&)
+ {
+ return true;
+ }
+};
+
+template <typename DistancePredicates>
+struct predicate_check<nearest<DistancePredicates>, envelope_tag>
+{
+ template <typename Value, typename Box>
+ static inline bool apply(nearest<DistancePredicates> const&, Value const&, Box const&)
+ {
+ return true;
+ }
+};
+
+template <typename DistancePredicates>
+struct nearest_one
+{
+ static const bool is_one = true;
+
+ nearest_one(DistancePredicates const& dpred)
+ : distance_predicates(dpred)
+ {}
+ DistancePredicates const& distance_predicates;
+};
+
+template <typename DistancePredicates>
+struct predicate_check<nearest_one<DistancePredicates>, value_tag>
+{
+ template <typename Value, typename Box>
+ static inline bool apply(nearest_one<DistancePredicates> const&, Value const&, Box const&)
+ {
+ return true;
+ }
+};
+
+template <typename DistancePredicates>
+struct predicate_check<nearest_one<DistancePredicates>, envelope_tag>
+{
+ template <typename Value, typename Box>
+ static inline bool apply(nearest_one<DistancePredicates> const&, Value const&, Box const&)
+ {
+ return true;
+ }
+};
+
+// predicates_is_nearest
+
+template <typename P>
+struct predicates_is_nearest
+{
+ static const unsigned value = 0;
+};
+
+template <typename DistancePredicates>
+struct predicates_is_nearest< nearest<DistancePredicates> >
+{
+ static const unsigned value = 1;
+};
+
+template <typename DistancePredicates>
+struct predicates_is_nearest< nearest_one<DistancePredicates> >
+{
+ static const unsigned value = 1;
+};
+
+// predicates_count_nearest
+
+template <typename T>
+struct predicates_count_nearest
+{
+ static const unsigned value = predicates_is_nearest<T>::value;
+};
+
+template <typename F, typename S>
+struct predicates_count_nearest< std::pair<F, S> >
+{
+ static const unsigned value = predicates_is_nearest<F>::value
+ + predicates_is_nearest<S>::value;
+};
+
+template <typename Tuple, unsigned N>
+struct predicates_count_nearest_tuple
+{
+ static const unsigned value =
+ predicates_is_nearest<typename boost::tuples::element<N-1, Tuple>::type>::value
+ + predicates_count_nearest_tuple<Tuple, N-1>::value;
+};
+
+template <typename Tuple>
+struct predicates_count_nearest_tuple<Tuple, 1>
+{
+ static const unsigned value =
+ predicates_is_nearest<typename boost::tuples::element<0, Tuple>::type>::value;
+};
+
+template <typename T0, typename T1, typename T2, typename T3, typename T4, typename T5, typename T6, typename T7, typename T8, typename T9>
+struct predicates_count_nearest< boost::tuple<T0, T1, T2, T3, T4, T5, T6, T7, T8, T9> >
+{
+ static const unsigned value = predicates_count_nearest_tuple<
+ boost::tuple<T0, T1, T2, T3, T4, T5, T6, T7, T8, T9>,
+ boost::tuples::length< boost::tuple<T0, T1, T2, T3, T4, T5, T6, T7, T8, T9> >::value
+ >::value;
+};
+
+template <typename Head, typename Tail>
+struct predicates_count_nearest< boost::tuples::cons<Head, Tail> >
+{
+ static const unsigned value = predicates_count_nearest_tuple<
+ boost::tuples::cons<Head, Tail>,
+ boost::tuples::length< boost::tuples::cons<Head, Tail> >::value
+ >::value;
+};
+
+// predicates_find_nearest
+
+template <typename T>
+struct predicates_find_nearest
+{
+ static const unsigned value = predicates_is_nearest<T>::value ? 0 : 1;
+};
+
+template <typename F, typename S>
+struct predicates_find_nearest< std::pair<F, S> >
+{
+ static const unsigned value = predicates_is_nearest<F>::value ? 0 :
+ (predicates_is_nearest<S>::value ? 1 : 2);
+};
+
+template <typename Tuple, unsigned N>
+struct predicates_find_nearest_tuple
+{
+ static const bool is_found = predicates_find_nearest_tuple<Tuple, N-1>::is_found
+ || predicates_is_nearest<typename boost::tuples::element<N-1, Tuple>::type>::value;
+
+ static const unsigned value = predicates_find_nearest_tuple<Tuple, N-1>::is_found ?
+ predicates_find_nearest_tuple<Tuple, N-1>::value :
+ (predicates_is_nearest<typename boost::tuples::element<N-1, Tuple>::type>::value ?
+ N-1 : boost::tuples::length<Tuple>::value);
+};
+
+template <typename Tuple>
+struct predicates_find_nearest_tuple<Tuple, 1>
+{
+ static const bool is_found = predicates_is_nearest<typename boost::tuples::element<0, Tuple>::type>::value;
+ static const unsigned value = is_found ? 0 : boost::tuples::length<Tuple>::value;
+};
+
+template <typename T0, typename T1, typename T2, typename T3, typename T4, typename T5, typename T6, typename T7, typename T8, typename T9>
+struct predicates_find_nearest< boost::tuple<T0, T1, T2, T3, T4, T5, T6, T7, T8, T9> >
+{
+ static const unsigned value = predicates_find_nearest_tuple<
+ boost::tuple<T0, T1, T2, T3, T4, T5, T6, T7, T8, T9>,
+ boost::tuples::length< boost::tuple<T0, T1, T2, T3, T4, T5, T6, T7, T8, T9> >::value
+ >::value;
+};
+
+template <typename Head, typename Tail>
+struct predicates_find_nearest< boost::tuples::cons<Head, Tail> >
+{
+ static const unsigned value = predicates_find_nearest_tuple<
+ boost::tuples::cons<Head, Tail>,
+ boost::tuples::length< boost::tuples::cons<Head, Tail> >::value
+ >::value;
+};
+
+// ------------------------------------------------------------------ //
// relations
// ------------------------------------------------------------------ //
@@ -364,7 +552,7 @@
// distances_calc_impl_tuple
-template <typename Distances, typename Point, typename Indexable, size_t N>
+template <typename Distances, typename Point, typename Indexable, unsigned N>
struct distances_calc_impl_tuple
{
// TODO MPL ASSERT 0 < N
Modified: sandbox-branches/geometry/index/boost/geometry/index/detail/predicates.hpp
==============================================================================
--- sandbox-branches/geometry/index/boost/geometry/index/detail/predicates.hpp (original)
+++ sandbox-branches/geometry/index/boost/geometry/index/detail/predicates.hpp 2013-01-24 17:24:58 EST (Thu, 24 Jan 2013)
@@ -439,39 +439,157 @@
};
// ------------------------------------------------------------------ //
+// predicates_length
+// ------------------------------------------------------------------ //
+
+template <typename T>
+struct predicates_length
+{
+ static const unsigned value = 1;
+};
+
+template <typename F, typename S>
+struct predicates_length< std::pair<F, S> >
+{
+ static const unsigned value = 2;
+};
+
+template <typename T0, typename T1, typename T2, typename T3, typename T4, typename T5, typename T6, typename T7, typename T8, typename T9>
+struct predicates_length< boost::tuple<T0, T1, T2, T3, T4, T5, T6, T7, T8, T9> >
+{
+ static const unsigned value = boost::tuples::length< boost::tuple<T0, T1, T2, T3, T4, T5, T6, T7, T8, T9> >::value;
+};
+
+template <typename Head, typename Tail>
+struct predicates_length< boost::tuples::cons<Head, Tail> >
+{
+ static const unsigned value = boost::tuples::length< boost::tuples::cons<Head, Tail> >::value;
+};
+
+// ------------------------------------------------------------------ //
+// predicates_element
+// ------------------------------------------------------------------ //
+
+template <unsigned I, typename T>
+struct predicates_element
+{
+ BOOST_MPL_ASSERT_MSG((I < 1), INVALID_INDEX, (predicates_element));
+ typedef T type;
+ static type const& get(T const& p) { return p; }
+};
+
+template <unsigned I, typename F, typename S>
+struct predicates_element< I, std::pair<F, S> >
+{
+ BOOST_MPL_ASSERT_MSG((I < 2), INVALID_INDEX, (predicates_element));
+
+ typedef F type;
+ static type const& get(std::pair<F, S> const& p) { return p.first; }
+};
+
+template <typename F, typename S>
+struct predicates_element< 1, std::pair<F, S> >
+{
+ typedef S type;
+ static type const& get(std::pair<F, S> const& p) { return p.second; }
+};
+
+template <unsigned I, typename T0, typename T1, typename T2, typename T3, typename T4, typename T5, typename T6, typename T7, typename T8, typename T9>
+struct predicates_element< I, boost::tuple<T0, T1, T2, T3, T4, T5, T6, T7, T8, T9> >
+{
+ typedef boost::tuple<T0, T1, T2, T3, T4, T5, T6, T7, T8, T9> predicate_type;
+
+ typedef typename boost::tuples::element<I, predicate_type>::type type;
+ static type const& get(predicate_type const& p) { return boost::get<I>(p); }
+};
+
+template <unsigned I, typename Head, typename Tail>
+struct predicates_element< I, boost::tuples::cons<Head, Tail> >
+{
+ typedef boost::tuples::cons<Head, Tail> predicate_type;
+
+ typedef typename boost::tuples::element<I, predicate_type>::type type;
+ static type const& get(predicate_type const& p) { return boost::get<I>(p); }
+};
+
+// ------------------------------------------------------------------ //
// predicates_check
// ------------------------------------------------------------------ //
-template <typename TuplePredicates, typename Tag, unsigned int N>
+template <typename PairPredicates, typename Tag, unsigned First, unsigned Last>
+struct predicates_check_pair {};
+
+template <typename PairPredicates, typename Tag, unsigned I>
+struct predicates_check_pair<PairPredicates, Tag, I, I>
+{
+ template <typename Value, typename Indexable>
+ static inline bool apply(PairPredicates const& p, Value const& v, Indexable const& i)
+ {
+ return true;
+ }
+};
+
+template <typename PairPredicates, typename Tag>
+struct predicates_check_pair<PairPredicates, Tag, 0, 1>
+{
+ template <typename Value, typename Indexable>
+ static inline bool apply(PairPredicates const& p, Value const& v, Indexable const& i)
+ {
+ return predicate_check<typename PairPredicates::first_type, Tag>::apply(p.first, v, i);
+ }
+};
+
+template <typename PairPredicates, typename Tag>
+struct predicates_check_pair<PairPredicates, Tag, 1, 2>
+{
+ template <typename Value, typename Indexable>
+ static inline bool apply(PairPredicates const& p, Value const& v, Indexable const& i)
+ {
+ return predicate_check<typename PairPredicates::second_type, Tag>::apply(p.second, v, i);
+ }
+};
+
+template <typename PairPredicates, typename Tag>
+struct predicates_check_pair<PairPredicates, Tag, 0, 2>
+{
+ template <typename Value, typename Indexable>
+ static inline bool apply(PairPredicates const& p, Value const& v, Indexable const& i)
+ {
+ return predicate_check<typename PairPredicates::first_type, Tag>::apply(p.first, v, i)
+ && predicate_check<typename PairPredicates::second_type, Tag>::apply(p.second, v, i);
+ }
+};
+
+template <typename TuplePredicates, typename Tag, unsigned First, unsigned Last>
struct predicates_check_tuple
{
template <typename Value, typename Indexable>
static inline bool apply(TuplePredicates const& p, Value const& v, Indexable const& i)
{
- return predicates_check_tuple<TuplePredicates, Tag, N - 1>::apply(p, v, i)
- && predicate_check<
- typename boost::tuples::element<N - 1, TuplePredicates>::type,
- Tag
- >::apply(boost::get<N - 1>(p), v, i);
+ return
+ predicate_check<
+ typename boost::tuples::element<First, TuplePredicates>::type,
+ Tag
+ >::apply(boost::get<First>(p), v, i) &&
+ predicates_check_tuple<TuplePredicates, Tag, First+1, Last>::apply(p, v, i);
}
};
-template <typename TuplePredicates, typename Tag>
-struct predicates_check_tuple<TuplePredicates, Tag, 1>
+template <typename TuplePredicates, typename Tag, unsigned First>
+struct predicates_check_tuple<TuplePredicates, Tag, First, First>
{
template <typename Value, typename Indexable>
static inline bool apply(TuplePredicates const& p, Value const& v, Indexable const& i)
{
- return predicate_check<
- typename boost::tuples::element<0, TuplePredicates>::type,
- Tag
- >::apply(boost::get<0>(p), v, i);
+ return true;
}
};
-template <typename Predicate, typename Tag>
+template <typename Predicate, typename Tag, size_t First, size_t Last>
struct predicates_check_impl
{
+ BOOST_MPL_ASSERT_MSG((First < 1 && Last <= 1 && First <= Last), INVALID_INDEXES, (predicates_check_impl));
+
template <typename Value, typename Indexable>
static inline bool apply(Predicate const& p, Value const& v, Indexable const& i)
{
@@ -479,9 +597,11 @@
}
};
-template <typename Predicate1, typename Predicate2, typename Tag>
-struct predicates_check_impl<std::pair<Predicate1, Predicate2>, Tag>
+template <typename Predicate1, typename Predicate2, typename Tag, size_t First, size_t Last>
+struct predicates_check_impl<std::pair<Predicate1, Predicate2>, Tag, First, Last>
{
+ BOOST_MPL_ASSERT_MSG((First < 2 && Last <= 2 && First <= Last), INVALID_INDEXES, (predicates_check_impl));
+
template <typename Value, typename Indexable>
static inline bool apply(std::pair<Predicate1, Predicate2> const& p, Value const& v, Indexable const& i)
{
@@ -493,30 +613,53 @@
template <
typename T0, typename T1, typename T2, typename T3, typename T4,
typename T5, typename T6, typename T7, typename T8, typename T9,
- typename Tag
+ typename Tag, unsigned First, unsigned Last
>
struct predicates_check_impl<
boost::tuple<T0, T1, T2, T3, T4, T5, T6, T7, T8, T9>,
- Tag
+ Tag, First, Last
>
{
typedef boost::tuple<T0, T1, T2, T3, T4, T5, T6, T7, T8, T9> predicates_type;
+ static const unsigned pred_len = boost::tuples::length<predicates_type>::value;
+ BOOST_MPL_ASSERT_MSG((First < pred_len && Last <= pred_len && First <= Last), INVALID_INDEXES, (predicates_check_impl));
+
+ template <typename Value, typename Indexable>
+ static inline bool apply(predicates_type const& p, Value const& v, Indexable const& i)
+ {
+ return predicates_check_tuple<
+ predicates_type,
+ Tag, First, Last
+ >::apply(p, v, i);
+ }
+};
+
+template <typename Head, typename Tail, typename Tag, unsigned First, unsigned Last>
+struct predicates_check_impl<
+ boost::tuples::cons<Head, Tail>,
+ Tag, First, Last
+>
+{
+ typedef boost::tuples::cons<Head, Tail> predicates_type;
+
+ static const unsigned pred_len = boost::tuples::length<predicates_type>::value;
+ BOOST_MPL_ASSERT_MSG((First < pred_len && Last <= pred_len && First <= Last), INVALID_INDEXES, (predicates_check_impl));
+
template <typename Value, typename Indexable>
static inline bool apply(predicates_type const& p, Value const& v, Indexable const& i)
{
return predicates_check_tuple<
predicates_type,
- Tag,
- boost::tuples::length<predicates_type>::value
+ Tag, First, Last
>::apply(p, v, i);
}
};
-template <typename Tag, typename Predicates, typename Value, typename Indexable>
+template <typename Tag, unsigned First, unsigned Last, typename Predicates, typename Value, typename Indexable>
inline bool predicates_check(Predicates const& p, Value const& v, Indexable const& i)
{
- return detail::predicates_check_impl<Predicates, Tag>
+ return detail::predicates_check_impl<Predicates, Tag, First, Last>
::apply(p, v, i);
}
Modified: sandbox-branches/geometry/index/boost/geometry/index/detail/rtree/visitors/nearest_query.hpp
==============================================================================
--- sandbox-branches/geometry/index/boost/geometry/index/detail/rtree/visitors/nearest_query.hpp (original)
+++ sandbox-branches/geometry/index/boost/geometry/index/detail/rtree/visitors/nearest_query.hpp 2013-01-24 17:24:58 EST (Thu, 24 Jan 2013)
@@ -184,6 +184,8 @@
index::detail::value_tag
> value_distances_predicates_check;
+ static const unsigned predicates_len = index::detail::predicates_length<Predicates>::value;
+
inline nearest_query(parameters_type const& parameters, Translator const& translator, DistancesPredicates const& dist_pred, Predicates const& pred, Result & r)
: m_parameters(parameters), m_translator(translator)
, m_dist_pred(dist_pred), m_pred(pred)
@@ -211,7 +213,7 @@
{
// if current node meets predicates
// 0 - dummy value
- if ( index::detail::predicates_check<index::detail::envelope_tag>(m_pred, 0, it->first) )
+ if ( index::detail::predicates_check<index::detail::envelope_tag, 0, predicates_len>(m_pred, 0, it->first) )
{
// calculate node's distance(s) for distance predicate
node_distances_type node_dist_data = node_distances_calc::apply(m_dist_pred, it->first);
@@ -266,7 +268,7 @@
it != elements.end(); ++it)
{
// if value meets predicates
- if ( index::detail::predicates_check<index::detail::value_tag>(m_pred, *it, m_translator(*it)) )
+ if ( index::detail::predicates_check<index::detail::value_tag, 0, predicates_len>(m_pred, *it, m_translator(*it)) )
{
// calculate values distance for distance predicate
value_distances_type distances = value_distances_calc::apply(m_dist_pred, m_translator(*it));
Modified: sandbox-branches/geometry/index/boost/geometry/index/detail/rtree/visitors/spatial_query.hpp
==============================================================================
--- sandbox-branches/geometry/index/boost/geometry/index/detail/rtree/visitors/spatial_query.hpp (original)
+++ sandbox-branches/geometry/index/boost/geometry/index/detail/rtree/visitors/spatial_query.hpp 2013-01-24 17:24:58 EST (Thu, 24 Jan 2013)
@@ -28,6 +28,8 @@
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;
+ static const unsigned predicates_len = index::detail::predicates_length<Predicates>::value;
+
inline spatial_query(Translator const& t, Predicates const& p, OutIter out_it)
: tr(t), pred(p), out_iter(out_it), found_count(0)
{}
@@ -43,7 +45,7 @@
{
// if node meets predicates
// 0 - dummy value
- if ( index::detail::predicates_check<index::detail::envelope_tag>(pred, 0, it->first) )
+ if ( index::detail::predicates_check<index::detail::envelope_tag, 0, predicates_len>(pred, 0, it->first) )
rtree::apply_visitor(*this, *it->second);
}
}
@@ -58,7 +60,7 @@
it != elements.end(); ++it)
{
// if value meets predicates
- if ( index::detail::predicates_check<index::detail::value_tag>(pred, *it, tr(*it)) )
+ if ( index::detail::predicates_check<index::detail::value_tag, 0, predicates_len>(pred, *it, tr(*it)) )
{
out_iter = *it;
++out_iter;
Modified: sandbox-branches/geometry/index/boost/geometry/index/detail/tuples.hpp
==============================================================================
--- sandbox-branches/geometry/index/boost/geometry/index/detail/tuples.hpp (original)
+++ sandbox-branches/geometry/index/boost/geometry/index/detail/tuples.hpp 2013-01-24 17:24:58 EST (Thu, 24 Jan 2013)
@@ -164,6 +164,36 @@
>::type type;
};
+template <typename Tuple, typename T, size_t I, size_t N>
+struct push_back_impl
+{
+ typedef
+ boost::tuples::cons<
+ typename boost::tuples::element<I, Tuple>::type,
+ typename push_back_impl<Tuple, T, I+1, N>::type
+ > type;
+
+ static type apply(Tuple const& tup, T const& t)
+ {
+ return
+ type(
+ boost::get<I>(tup),
+ push_back_impl<Tuple, T, I+1, N>::apply(tup, t)
+ );
+ }
+};
+
+template <typename Tuple, typename T, size_t N>
+struct push_back_impl<Tuple, T, N, N>
+{
+ typedef boost::tuples::cons<T, boost::tuples::null_type> type;
+
+ static type apply(Tuple const&, T const& t)
+ {
+ return type(t, boost::tuples::null_type());
+ }
+};
+
} // namespace tuples
}}}} // namespace boost::geometry::index::detail
Modified: sandbox-branches/geometry/index/boost/geometry/index/distance_predicates.hpp
==============================================================================
--- sandbox-branches/geometry/index/boost/geometry/index/distance_predicates.hpp (original)
+++ sandbox-branches/geometry/index/boost/geometry/index/distance_predicates.hpp 2013-01-24 17:24:58 EST (Thu, 24 Jan 2013)
@@ -19,6 +19,22 @@
namespace boost { namespace geometry { namespace index {
+// nearest predicate generators
+
+template <typename DistancePredicates> inline
+detail::nearest<DistancePredicates>
+nearest(DistancePredicates const& dpred, unsigned k)
+{
+ return detail::nearest<DistancePredicates>(dpred, k);
+}
+
+template <typename DistancePredicates> inline
+detail::nearest_one<DistancePredicates>
+nearest(DistancePredicates const& dpred)
+{
+ return detail::nearest_one<DistancePredicates>(dpred);
+}
+
// relations generators
/*!
Modified: sandbox-branches/geometry/index/boost/geometry/index/predicates.hpp
==============================================================================
--- sandbox-branches/geometry/index/boost/geometry/index/predicates.hpp (original)
+++ sandbox-branches/geometry/index/boost/geometry/index/predicates.hpp 2013-01-24 17:24:58 EST (Thu, 24 Jan 2013)
@@ -19,6 +19,7 @@
#include <boost/geometry/algorithms/covered_by.hpp>
#include <boost/geometry/index/detail/predicates.hpp>
+#include <boost/geometry/index/detail/tuples.hpp>
/*!
\defgroup predicates Spatial predicates (boost::geometry::index::)
@@ -245,6 +246,43 @@
{
return within<Geometry>(p.geometry);
}
+
+// operator&& generators
+
+template <typename Pred1, typename Pred2> inline
+boost::tuples::cons<
+ Pred1,
+ boost::tuples::cons<Pred2, boost::tuples::null_type>
+>
+operator&&(Pred1 const& p1, Pred2 const& p2)
+{
+ return
+ boost::tuples::cons<
+ Pred1,
+ boost::tuples::cons<Pred2, boost::tuples::null_type>
+ >(
+ p1,
+ boost::tuples::cons<Pred2, boost::tuples::null_type>(p2, boost::tuples::null_type())
+ );
+}
+
+template <typename Head, typename Tail, typename Pred> inline
+typename tuples::push_back_impl<
+ boost::tuples::cons<Head, Tail>,
+ Pred,
+ 0,
+ boost::tuples::length<boost::tuples::cons<Head, Tail> >::value
+>::type
+operator&&(boost::tuples::cons<Head, Tail> const& t, Pred const& p)
+{
+ return
+ tuples::push_back_impl<
+ boost::tuples::cons<Head, Tail>,
+ Pred,
+ 0,
+ boost::tuples::length<boost::tuples::cons<Head, Tail> >::value
+ >::apply(t, p);
+}
} // namespace detail
Modified: sandbox-branches/geometry/index/boost/geometry/index/rtree.hpp
==============================================================================
--- sandbox-branches/geometry/index/boost/geometry/index/rtree.hpp (original)
+++ sandbox-branches/geometry/index/boost/geometry/index/rtree.hpp 2013-01-24 17:24:58 EST (Thu, 24 Jan 2013)
@@ -630,6 +630,75 @@
return result;
}
+ template <typename Predicates, typename OutIter>
+ size_type query(Predicates const& predicates, OutIter out_it) 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 query_dispatch(predicates, out_it, boost::mpl::bool_<is_nearest>());
+ }
+
+ template <typename Predicates>
+ size_type query(Predicates const& predicates, value_type & v) const
+ {
+ static const unsigned nearest_count = detail::predicates_count_nearest<Predicates>::value;
+ BOOST_MPL_ASSERT_MSG((nearest_count == 1), PASS_NEAREST_PREDICATE_TO_GET_VALUE_AS_RESULT, (Predicates));
+
+ return query_dispatch(predicates, v, boost::mpl::bool_<true>());
+ }
+
+private:
+
+ template <typename Predicates, typename OutIter>
+ size_type query_dispatch(Predicates const& predicates, OutIter out_it, boost::mpl::bool_<false> const& /*is_nearest*/) const
+ {
+ return spatial_query(predicates, out_it);
+ }
+
+ template <typename Predicates, typename OutIter>
+ size_type query_dispatch(Predicates const& predicates, OutIter out_it, boost::mpl::bool_<true> const& /*is_nearest*/) const
+ {
+ static const unsigned nearest_index = detail::predicates_find_nearest<Predicates>::value;
+ static const bool is_one = detail::predicates_element<nearest_index, Predicates>::type::is_one;
+
+ return query_dispatch_nearest(predicates, out_it, boost::mpl::bool_<is_one>());
+ }
+
+ template <typename Predicates>
+ size_type query_dispatch(Predicates const& predicates, value_type & v, boost::mpl::bool_<true> const& /*is_nearest*/) const
+ {
+ static const unsigned nearest_index = detail::predicates_find_nearest<Predicates>::value;
+ static const bool is_one = detail::predicates_element<nearest_index, Predicates>::type::is_one;
+ BOOST_MPL_ASSERT_MSG((is_one == 1), PASS_ONE_VALUE_NEAREST_PREDICATE_TO_GET_VALUE_AS_RESULT, (Predicates));
+
+ typedef detail::predicates_element<nearest_index, Predicates> element_access;
+ typename element_access::type const& nearest_pred = element_access::get(predicates);
+
+ return this->raw_nearest_one(nearest_pred.distance_predicates, predicates, v);
+ }
+
+ template <typename Predicates, typename OutIter>
+ size_type query_dispatch_nearest(Predicates const& predicates, OutIter out_it, boost::mpl::bool_<false> const& /*is_one*/) const
+ {
+ static const unsigned nearest_index = detail::predicates_find_nearest<Predicates>::value;
+ typedef detail::predicates_element<nearest_index, Predicates> element_access;
+ typename element_access::type const& nearest_pred = element_access::get(predicates);
+ return this->raw_nearest_k(nearest_pred.distance_predicates, nearest_pred.count, predicates, out_it);
+ }
+
+ template <typename Predicates, typename OutIter>
+ size_type query_dispatch_nearest(Predicates const& predicates, OutIter out_it, boost::mpl::bool_<true> const& /*is_one*/) const
+ {
+ static const unsigned nearest_index = detail::predicates_find_nearest<Predicates>::value;
+ typedef detail::predicates_element<nearest_index, Predicates> element_access;
+ typename element_access::type const& nearest_pred = element_access::get(predicates);
+ return this->raw_nearest_k(nearest_pred.distance_predicates, 1, predicates, out_it);
+ }
+
+public:
+
/*!
\brief Finds values meeting spatial predicates, e.g. intersecting some Box.
@@ -661,8 +730,8 @@
\li If Value copy constructor or copy assignment throws.
\li If OutIter dereference or increment throws.
*/
- template <typename Predicates, typename OutIter>
- inline size_type spatial_query(Predicates const& pred, OutIter out_it) const
+ template <typename Predicates, typename OutIter> inline
+ size_type spatial_query(Predicates const& pred, OutIter out_it) const
{
if ( !m_root )
return 0;
Modified: sandbox-branches/geometry/index/test/rtree/test_rtree.hpp
==============================================================================
--- sandbox-branches/geometry/index/test/rtree/test_rtree.hpp (original)
+++ sandbox-branches/geometry/index/test/rtree/test_rtree.hpp 2013-01-24 17:24:58 EST (Thu, 24 Jan 2013)
@@ -559,10 +559,16 @@
std::vector<Value> output2;
size_t n2 = spatial_query(rtree, pred, std::back_inserter(output2));
-
+
BOOST_CHECK( n == n2 );
test_exactly_the_same_outputs(rtree, output, output2);
+ std::vector<Value> output3;
+ size_t n3 = rtree.query(pred, std::back_inserter(output3));
+
+ BOOST_CHECK( n == n3 );
+ test_exactly_the_same_outputs(rtree, output, output3);
+
test_exactly_the_same_outputs(rtree, output, rtree | bgi::adaptors::spatial_queried(pred));
}
@@ -771,6 +777,15 @@
BOOST_CHECK(d1 == d2);
}
}
+
+ Value output2(generate_value_default<Value>::apply());
+ size_t n_res2 = rtree.query(bgi::nearest(pt), output2);
+
+ BOOST_CHECK(n == n_res2);
+ if ( 0 < n_res2 )
+ {
+ BOOST_CHECK(rtree.translator().equals(output, output2));
+ }
}
template <typename Rtree, typename Point>
@@ -861,6 +876,12 @@
output2.resize(found_count, generate_value_default<Value>::apply());
test_exactly_the_same_outputs(rtree, output, output2);
+
+ std::vector<Value> output3(k, generate_value_default<Value>::apply());
+ found_count = rtree.query(bgi::nearest(pt, k), output3.begin());
+ output3.resize(found_count, generate_value_default<Value>::apply());
+
+ test_exactly_the_same_outputs(rtree, output, output3);
}
// rtree nearest not found
Modified: sandbox-branches/geometry/index/tests/additional_speed.cpp
==============================================================================
--- sandbox-branches/geometry/index/tests/additional_speed.cpp (original)
+++ sandbox-branches/geometry/index/tests/additional_speed.cpp 2013-01-24 17:24:58 EST (Thu, 24 Jan 2013)
@@ -58,8 +58,8 @@
// typedef bgi::rtree<B, bgi::runtime::quadratic > RT;
//typedef bgi::rtree<B, bgi::rstar<32, 8> > RT;
//typedef bgi::rtree<B, bgi::runtime::rstar > RT;
-
- for ( ;; )
+
+ for (unsigned i = 0 ; i < 10 ; ++i)
{
RT t;
//RT t(bgi::runtime::linear(32, 8));
@@ -126,6 +126,60 @@
std::cout << time << "s - spatial_query(i, !w, !o) " << queries_count << " found " << temp << '\n';
}
+ {
+ tim.restart();
+ size_t temp = 0;
+ for (size_t i = 0 ; i < queries_count / 2 ; ++i )
+ {
+ float x1 = coords[i].first;
+ float y1 = coords[i].second;
+ float x2 = coords[i+1].first;
+ float y2 = coords[i+1].second;
+ float x3 = coords[i+2].first;
+ float y3 = coords[i+2].second;
+ result.clear();
+ t.spatial_query(
+ bgi::intersects(B(P(x1 - 10, y1 - 10), P(x1 + 10, y1 + 10)))
+ &&
+ !bgi::within(B(P(x2 - 10, y2 - 10), P(x2 + 10, y2 + 10)))
+ &&
+ !bgi::overlaps(B(P(x3 - 10, y3 - 10), P(x3 + 10, y3 + 10)))
+ ,
+ std::back_inserter(result)
+ );
+ temp += result.size();
+ }
+ double time = tim.elapsed();
+ std::cout << time << "s - spatial_query(i && !w && !o) " << queries_count << " found " << temp << '\n';
+ }
+
+ {
+ tim.restart();
+ size_t temp = 0;
+ for (size_t i = 0 ; i < queries_count / 2 ; ++i )
+ {
+ float x1 = coords[i].first;
+ float y1 = coords[i].second;
+ float x2 = coords[i+1].first;
+ float y2 = coords[i+1].second;
+ float x3 = coords[i+2].first;
+ float y3 = coords[i+2].second;
+ result.clear();
+ t.query(
+ bgi::intersects(B(P(x1 - 10, y1 - 10), P(x1 + 10, y1 + 10)))
+ &&
+ !bgi::within(B(P(x2 - 10, y2 - 10), P(x2 + 10, y2 + 10)))
+ &&
+ !bgi::overlaps(B(P(x3 - 10, y3 - 10), P(x3 + 10, y3 + 10)))
+ ,
+ std::back_inserter(result)
+ );
+ temp += result.size();
+ }
+ double time = tim.elapsed();
+ std::cout << time << "s - query(i && !w && !o) " << queries_count << " found " << temp << '\n';
+ }
+
result.clear();
{
@@ -178,6 +232,55 @@
}
{
+ tim.restart();
+ size_t temp = 0;
+ for (size_t i = 0 ; i < queries_count / 10 ; ++i )
+ {
+ float x = coords[i].first + 100;
+ float y = coords[i].second + 100;
+ temp += t.query(bgi::nearest(P(x, y)), result_one);
+ }
+ double time = tim.elapsed();
+ std::cout << time << "s - query(nearest(P)) " << (queries_count / 10) << " found " << temp << '\n';
+ }
+
+ {
+ tim.restart();
+ size_t temp = 0;
+ for (size_t i = 0 ; i < queries_count / 10 ; ++i )
+ {
+ float x = coords[i].first + 100;
+ float y = coords[i].second + 100;
+ result.clear();
+ temp += t.query(bgi::nearest(P(x, y), 5), std::back_inserter(result));
+ }
+ double time = tim.elapsed();
+ std::cout << time << "s - query(nearest(P, 5)) " << (queries_count / 10) << " found " << temp << '\n';
+ }
+
+ {
+ tim.restart();
+ size_t temp = 0;
+ for (size_t i = 0 ; i < queries_count / 10 ; ++i )
+ {
+ float x = coords[i].first + 100;
+ float y = coords[i].second + 100;
+ result.clear();
+ temp += t.query(bgi::nearest(
+ bgi::bounded(
+ bgi::to_nearest(P(x, y)),
+ bgi::to_centroid(0),
+ bgi::to_furthest(100000)
+ ),
+ 5),
+ std::back_inserter(result)
+ );
+ }
+ double time = tim.elapsed();
+ std::cout << time << "s - query(nearest(bounded(n, c, f), 5)) " << (queries_count / 10) << " found " << temp << '\n';
+ }
+
+ {
tim.restart();
for (size_t i = 0 ; i < values_count / 10 ; ++i )
{
Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk