|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r74596 - in sandbox-branches/geometry/index: boost/geometry/extensions/index boost/geometry/extensions/index/rtree boost/geometry/extensions/index/rtree/visitors tests
From: adam.wulkiewicz_at_[hidden]
Date: 2011-09-28 07:04:19
Author: awulkiew
Date: 2011-09-28 07:04:17 EDT (Wed, 28 Sep 2011)
New Revision: 74596
URL: http://svn.boost.org/trac/boost/changeset/74596
Log:
Value predicates added. Error in boost::tuple predicates check fixed.
Text files modified:
sandbox-branches/geometry/index/boost/geometry/extensions/index/distance_predicates.hpp | 2
sandbox-branches/geometry/index/boost/geometry/extensions/index/predicates.hpp | 96 ++++++++++++++++++++++++---------------
sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/predicates.hpp | 43 +++++++----------
sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/nearest.hpp | 5 +
sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/query.hpp | 9 ++
sandbox-branches/geometry/index/tests/additional_sizes_and_times.cpp | 33 +++++++++++++
6 files changed, 121 insertions(+), 67 deletions(-)
Modified: sandbox-branches/geometry/index/boost/geometry/extensions/index/distance_predicates.hpp
==============================================================================
--- sandbox-branches/geometry/index/boost/geometry/extensions/index/distance_predicates.hpp (original)
+++ sandbox-branches/geometry/index/boost/geometry/extensions/index/distance_predicates.hpp 2011-09-28 07:04:17 EDT (Wed, 28 Sep 2011)
@@ -122,6 +122,8 @@
namespace detail {
+// TODO: awulkiew - consider storing points instead of PointRelations in predicates below
+
template <typename PointRelation>
struct unbounded
: nonassignable
Modified: sandbox-branches/geometry/index/boost/geometry/extensions/index/predicates.hpp
==============================================================================
--- sandbox-branches/geometry/index/boost/geometry/extensions/index/predicates.hpp (original)
+++ sandbox-branches/geometry/index/boost/geometry/extensions/index/predicates.hpp 2011-09-28 07:04:17 EDT (Wed, 28 Sep 2011)
@@ -27,7 +27,6 @@
template <typename Geometry>
struct covered_by
- : nonassignable
{
covered_by(Geometry const& g) : geometry(g) {}
Geometry geometry;
@@ -35,7 +34,6 @@
template <typename Geometry>
struct intersects
- : nonassignable
{
intersects(Geometry const& g) : geometry(g) {}
Geometry geometry;
@@ -43,7 +41,6 @@
template <typename Geometry>
struct overlaps
- : nonassignable
{
overlaps(Geometry const& g) : geometry(g) {}
Geometry geometry;
@@ -51,12 +48,18 @@
template <typename Geometry>
struct within
- : nonassignable
{
within(Geometry const& g) : geometry(g) {}
Geometry geometry;
};
+template <typename ValuePredicate>
+struct value
+{
+ value(ValuePredicate const& vpred) : value_predicate(vpred) {}
+ ValuePredicate value_predicate;
+};
+
} // namespace detail
inline detail::empty empty()
@@ -88,6 +91,12 @@
return detail::within<Geometry>(g);
}
+template <typename ValuePredicate>
+inline detail::value<ValuePredicate> value(ValuePredicate const& vpred)
+{
+ return detail::value<ValuePredicate>(vpred);
+}
+
namespace detail
{
@@ -99,11 +108,14 @@
// distinguish between geometries and other types by use of geometry::tag
// in predicate_check_default<..., GeomTag> -> predicate_check_default<..., void>
+// TODO: awulkiew - consider passing Value/Node and Translator instead of
+// Value and Indexable
+
template <typename Geometry, typename Tag>
struct predicate_check
{
- template <typename Indexable>
- static inline bool apply(Geometry const& g, Indexable const& i)
+ template <typename Value, typename Indexable>
+ static inline bool apply(Geometry const& g, Value const&, Indexable const& i)
{
return geometry::intersects(i, g);
}
@@ -112,8 +124,8 @@
template <typename Tag>
struct predicate_check<empty, Tag>
{
- template <typename Geometry, typename Indexable>
- static inline bool apply(Geometry const&, Indexable const&)
+ template <typename Geometry, typename Value, typename Indexable>
+ static inline bool apply(Geometry const&, Value const&, Indexable const&)
{
return true;
}
@@ -122,8 +134,8 @@
template <typename Geometry, typename Tag>
struct predicate_check<covered_by<Geometry>, Tag>
{
- template <typename Indexable>
- static inline bool apply(covered_by<Geometry> const& p, Indexable const& i)
+ template <typename Value, typename Indexable>
+ static inline bool apply(covered_by<Geometry> const& p, Value const&, Indexable const& i)
{
return geometry::covered_by(i, p.geometry);
}
@@ -132,8 +144,8 @@
template <typename Geometry, typename Tag>
struct predicate_check<intersects<Geometry>, Tag>
{
- template <typename Indexable>
- static inline bool apply(intersects<Geometry> const& p, Indexable const& i)
+ template <typename Value, typename Indexable>
+ static inline bool apply(intersects<Geometry> const& p, Value const&, Indexable const& i)
{
return geometry::intersects(i, p.geometry);
}
@@ -142,8 +154,8 @@
template <typename Geometry, typename Tag>
struct predicate_check<overlaps<Geometry>, Tag>
{
- template <typename Indexable>
- static inline bool apply(overlaps<Geometry> const& p, Indexable const& i)
+ template <typename Value, typename Indexable>
+ static inline bool apply(overlaps<Geometry> const& p, Value const&, Indexable const& i)
{
return geometry::overlaps(i, p.geometry);
}
@@ -152,60 +164,70 @@
template <typename Geometry, typename Tag>
struct predicate_check<within<Geometry>, Tag>
{
- template <typename Indexable>
- static inline bool apply(within<Geometry> const& p, Indexable const& i)
+ template <typename Value, typename Indexable>
+ static inline bool apply(within<Geometry> const& p, Value const&, Indexable const& i)
{
return geometry::within(i, p.geometry);
}
};
+template <typename ValuePredicate, typename Tag>
+struct predicate_check<value<ValuePredicate>, Tag>
+{
+ template <typename Value, typename Indexable>
+ static inline bool apply(value<ValuePredicate> const& p, Value const& v, Indexable const&)
+ {
+ return p.value_predicate(v);
+ }
+};
+
// predicates check
template <typename TuplePredicates, typename Tag, unsigned int N>
struct predicates_check_tuple
{
- template <typename Indexable>
- static inline bool apply(TuplePredicates const& p, Indexable const& i)
+ 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, 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), i);
+ >::apply(boost::get<N - 1>(p), v, i);
}
};
template <typename TuplePredicates, typename Tag>
-struct predicates_check_tuple<TuplePredicates, Tag, 0>
+struct predicates_check_tuple<TuplePredicates, Tag, 1>
{
- template <typename Indexable>
- static inline bool apply(TuplePredicates const& p, Indexable const& i)
+ 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), i);
+ >::apply(boost::get<0>(p), v, i);
}
};
template <typename Predicate, typename Tag>
struct predicates_check
{
- template <typename Indexable>
- static inline bool apply(Predicate const& p, Indexable const& i)
+ template <typename Value, typename Indexable>
+ static inline bool apply(Predicate const& p, Value const& v, Indexable const& i)
{
- return predicate_check<Predicate, Tag>::apply(p, i);
+ return predicate_check<Predicate, Tag>::apply(p, v, i);
}
};
template <typename Predicate1, typename Predicate2, typename Tag>
struct predicates_check<std::pair<Predicate1, Predicate2>, Tag>
{
- template <typename Indexable>
- static inline bool apply(std::pair<Predicate1, Predicate2> const& p, Indexable const& i)
+ template <typename Value, typename Indexable>
+ static inline bool apply(std::pair<Predicate1, Predicate2> const& p, Value const& v, Indexable const& i)
{
- return predicate_check<Predicate1, Tag>::apply(p.first, i)
- && predicate_check<Predicate2, Tag>::apply(p.second, i);
+ return predicate_check<Predicate1, Tag>::apply(p.first, v, i)
+ && predicate_check<Predicate2, Tag>::apply(p.second, v, i);
}
};
@@ -221,24 +243,24 @@
{
typedef boost::tuple<T0, T1, T2, T3, T4, T5, T6, T7, T8, T9> predicates_type;
- template <typename Indexable>
- static inline bool apply(predicates_type const& p, Indexable const& i)
+ 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
- >::apply(p, i);
+ >::apply(p, v, i);
}
};
} // namespace detail
-template <typename Tag, typename Predicates, typename Indexable>
-inline bool predicates_check(Predicates const& p, Indexable const& i)
+template <typename Tag, typename Predicates, typename Value, typename Indexable>
+inline bool predicates_check(Predicates const& p, Value const& v, Indexable const& i)
{
return detail::predicates_check<Predicates, Tag>
- ::apply(p, i);
+ ::apply(p, v, i);
}
}}} // namespace boost::geometry::index
Modified: sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/predicates.hpp
==============================================================================
--- sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/predicates.hpp (original)
+++ sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/predicates.hpp 2011-09-28 07:04:17 EDT (Wed, 28 Sep 2011)
@@ -17,41 +17,24 @@
namespace detail {
-//template <typename Geometry>
-//struct predicate_check<Geometry, rtree::node_predicates_tag>
-//{
-// template <typename Box>
-// static inline bool apply(Geometry const& g, Box const& i)
-// {
-// return geometry::intersects(i, g);
-// }
-//};
+// TODO: awulkiew - consider removing Value from parameters
+// then predicates_check must be implemented for nodes as well
template <typename Geometry>
struct predicate_check<covered_by<Geometry>, rtree::node_tag>
{
- template <typename Box>
- static bool apply(covered_by<Geometry> const& p, Box const& i)
+ template <typename Value, typename Box>
+ static bool apply(covered_by<Geometry> const& p, Value const&, Box const& i)
{
return geometry::intersects(i, p.geometry);
}
};
-//template <typename Geometry>
-//struct predicate_check<intersects<Geometry>, rtree::node_predicates_tag>
-//{
-// template <typename Box>
-// static inline bool apply(intersects<Geometry> const& p, Box const& i)
-// {
-// return geometry::intersects(i, p.geometry);
-// }
-//};
-
template <typename Geometry>
struct predicate_check<overlaps<Geometry>, rtree::node_tag>
{
- template <typename Box>
- static inline bool apply(overlaps<Geometry> const& p, Box const& i)
+ template <typename Value, typename Box>
+ static inline bool apply(overlaps<Geometry> const& p, Value const&, Box const& i)
{
// TODO: awulkiew - possibly change to the version without border case
// e.g. intersects_without_border(0,0x1,1, 1,1x2,2) should give false
@@ -62,8 +45,8 @@
template <typename Geometry>
struct predicate_check<within<Geometry>, rtree::node_tag>
{
- template <typename Box>
- static bool apply(within<Geometry> const& p, Box const& i)
+ template <typename Value, typename Box>
+ static bool apply(within<Geometry> const& p, Value const&, Box const& i)
{
// TODO: awulkiew - possibly change to the version without border case
// e.g. intersects_without_border(0,0x1,1, 1,1x2,2) should give false
@@ -71,6 +54,16 @@
}
};
+template <typename ValuePredicate>
+struct predicate_check<value<ValuePredicate>, rtree::node_tag>
+{
+ template <typename Value, typename Box>
+ static bool apply(value<ValuePredicate> const&, Value const&, Box const&)
+ {
+ return true;
+ }
+};
+
} // namespace detail
}}} // namespace boost::geometry::index
Modified: sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/nearest.hpp
==============================================================================
--- sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/nearest.hpp (original)
+++ sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/nearest.hpp 2011-09-28 07:04:17 EDT (Wed, 28 Sep 2011)
@@ -174,7 +174,8 @@
it != elements.end(); ++it)
{
// if current node meets predicates
- if ( index::predicates_check<rtree::node_tag>(m_pred, it->first) )
+ // 0 - dummy value
+ if ( index::predicates_check<rtree::node_tag>(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);
@@ -218,7 +219,7 @@
it != elements.end(); ++it)
{
// if value meets predicates
- if ( index::predicates_check<rtree::value_tag>(m_pred, m_tr(*it)) )
+ if ( index::predicates_check<rtree::value_tag>(m_pred, *it, m_tr(*it)) )
{
// calculate values distance for distance predicate
value_distances_type distances = value_distances_calc::apply(m_dist_pred, m_tr(*it));
Modified: sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/query.hpp
==============================================================================
--- sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/query.hpp (original)
+++ sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/query.hpp 2011-09-28 07:04:17 EDT (Wed, 28 Sep 2011)
@@ -34,10 +34,13 @@
typedef typename rtree::elements_type<internal_node>::type elements_type;
elements_type const& elements = rtree::elements(n);
+ // traverse nodes meeting predicates
for (typename elements_type::const_iterator it = elements.begin();
it != elements.end(); ++it)
{
- if ( index::predicates_check<rtree::node_tag>(pred, it->first) )
+ // if node meets predicates
+ // 0 - dummy value
+ if ( index::predicates_check<rtree::node_tag>(pred, 0, it->first) )
rtree::apply_visitor(*this, *it->second);
}
}
@@ -47,10 +50,12 @@
typedef typename rtree::elements_type<leaf>::type elements_type;
elements_type const& elements = rtree::elements(n);
+ // get all values meeting predicates
for (typename elements_type::const_iterator it = elements.begin();
it != elements.end(); ++it)
{
- if ( index::predicates_check<rtree::value_tag>(pred, tr(*it)) )
+ // if value meets predicates
+ if ( index::predicates_check<rtree::value_tag>(pred, *it, tr(*it)) )
{
out_iter = *it;
++out_iter;
Modified: sandbox-branches/geometry/index/tests/additional_sizes_and_times.cpp
==============================================================================
--- sandbox-branches/geometry/index/tests/additional_sizes_and_times.cpp (original)
+++ sandbox-branches/geometry/index/tests/additional_sizes_and_times.cpp 2011-09-28 07:04:17 EDT (Wed, 28 Sep 2011)
@@ -19,6 +19,15 @@
#include <boost/foreach.hpp>
#include <boost/random.hpp>
+template <typename V>
+struct test_pred
+{
+ bool operator()(V const& v) const
+ {
+ return v.second % 2 != 0;
+ }
+};
+
int main()
{
boost::timer tim;
@@ -194,6 +203,28 @@
// searching test
{
+ std::cout << "query(B) and value(odd index) searching time test... ("
+ << queries_count << ")\n";
+ tim.restart();
+ size_t temp = 0;
+ for (size_t i = 0 ; i < queries_count ; ++i )
+ {
+ float x = coords[i].first;
+ float y = coords[i].second;
+ std::deque< std::pair<B, size_t> > result;
+ t.query(
+ std::make_pair(
+ B(P(x - 10, y - 10), P(x + 10, y + 10)),
+ bgi::value(test_pred< std::pair<B, size_t> >())
+ ), std::back_inserter(result));
+ temp += result.size();
+ }
+ std::cout << "time: " << tim.elapsed() << "s\n";
+ std::cout << "found: " << temp << "\n";
+ }
+
+ // searching test
+ {
std::cout << "vector searching time test... ("
<< queries_count / 1000 << ")\n";
tim.restart();
@@ -231,7 +262,7 @@
float x = coords[i].first + 100;
float y = coords[i].second + 100;
std::pair<B, size_t> result;
- temp += t.nearest(P(x, y), result);
+ temp += t.nearest(bgi::unbounded(P(x, y)), result);
}
std::cout << "time: " << tim.elapsed() << "s\n";
std::cout << "found: " << temp << "\n";
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