Subject: [Boost-commit] svn:boost r85693 - in trunk: boost/geometry/index/detail/rtree libs/geometry/doc/index libs/geometry/index/example
From: adam.wulkiewicz_at_[hidden]
Date: 2013-09-15 20:25:37
Author: awulkiew
Date: 2013-09-15 20:25:37 EDT (Sun, 15 Sep 2013)
New Revision: 85693
URL: http://svn.boost.org/trac/boost/changeset/85693
Log:
[geometry][index]: added iterators test implementation using Boost.Function. Fixed compilation errors in benchmark_experimental.
Text files modified:
trunk/boost/geometry/index/detail/rtree/query_iterators.hpp | 76 ++++++++++++++++++++++++++++++++++++++-
trunk/libs/geometry/doc/index/introduction.qbk | 2
trunk/libs/geometry/index/example/benchmark_experimental.cpp | 72 +++++++------------------------------
3 files changed, 89 insertions(+), 61 deletions(-)
Modified: trunk/boost/geometry/index/detail/rtree/query_iterators.hpp
==============================================================================
--- trunk/boost/geometry/index/detail/rtree/query_iterators.hpp Sun Sep 15 18:15:46 2013 (r85692)
+++ trunk/boost/geometry/index/detail/rtree/query_iterators.hpp 2013-09-15 20:25:37 EDT (Sun, 15 Sep 2013) (r85693)
@@ -11,6 +11,8 @@
#ifndef BOOST_GEOMETRY_INDEX_DETAIL_RTREE_QUERY_ITERATORS_HPP
#define BOOST_GEOMETRY_INDEX_DETAIL_RTREE_QUERY_ITERATORS_HPP
+#define BOOST_GEOMETRY_INDEX_DETAIL_QUERY_ITERATORS_USE_VIRTUAL
+//#define BOOST_GEOMETRY_INDEX_DETAIL_QUERY_ITERATORS_USE_FUNCTION
//#define BOOST_GEOMETRY_INDEX_DETAIL_QUERY_ITERATORS_USE_TYPE_ERASURE
//#define BOOST_GEOMETRY_INDEX_DETAIL_QUERY_ITERATORS_USE_MOVE
@@ -195,7 +197,9 @@
}}}}}} // namespace boost::geometry::index::detail::rtree::iterators
-#ifndef BOOST_GEOMETRY_INDEX_DETAIL_QUERY_ITERATORS_USE_TYPE_ERASURE
+#if defined(BOOST_GEOMETRY_INDEX_DETAIL_QUERY_ITERATORS_USE_VIRTUAL) || defined(BOOST_GEOMETRY_INDEX_DETAIL_QUERY_ITERATORS_USE_FUNCTION)
+
+#if defined(BOOST_GEOMETRY_INDEX_DETAIL_QUERY_ITERATORS_USE_VIRTUAL)
namespace boost { namespace geometry { namespace index { namespace detail { namespace rtree { namespace iterators {
@@ -250,6 +254,74 @@
Iterator m_iterator;
};
+#elif defined(BOOST_GEOMETRY_INDEX_DETAIL_QUERY_ITERATORS_USE_FUNCTION)
+
+#include <boost/function.hpp>
+#include <boost/bind.hpp>
+
+namespace boost { namespace geometry { namespace index { namespace detail { namespace rtree { namespace iterators {
+
+template <typename Value, typename Allocators>
+class query_iterator_base
+{
+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;
+
+ virtual ~query_iterator_base() {}
+
+ boost::function<query_iterator_base*()> clone;
+ boost::function<bool()> is_end;
+ boost::function<reference()> dereference;
+ boost::function<void()> increment;
+ boost::function<bool(query_iterator_base const&)> equals;
+};
+
+template <typename Value, typename Allocators, typename Iterator>
+class query_iterator_wrapper
+ : public query_iterator_base<Value, Allocators>
+{
+ typedef query_iterator_base<Value, Allocators> base_t;
+
+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;
+
+ explicit query_iterator_wrapper(Iterator const& it)
+ : m_iterator(it)
+ {
+ base_t::clone = boost::bind(&query_iterator_wrapper::clone_, this);
+ base_t::is_end = boost::bind(&query_iterator_wrapper::is_end_, this);
+ base_t::dereference = boost::bind(&query_iterator_wrapper::dereference_, this);
+ base_t::increment = boost::bind(&query_iterator_wrapper::increment_, this);
+ base_t::equals = boost::bind(&query_iterator_wrapper::equals_, this, _1);
+ }
+
+private:
+ base_t * clone_() const { return new query_iterator_wrapper(m_iterator); }
+
+ bool is_end_() const { return m_iterator == end_query_iterator<Value, Allocators>(); }
+ reference dereference_() const { return *m_iterator; }
+ void increment_() { ++m_iterator; }
+ bool equals_(base_t const& r) const
+ {
+ const query_iterator_wrapper * p = dynamic_cast<const query_iterator_wrapper *>(boost::addressof(r));
+ BOOST_ASSERT_MSG(p, "those iterators can't be compared");
+ return m_iterator == p->m_iterator;
+ }
+
+private:
+ Iterator m_iterator;
+};
+
+#endif
+
template <typename Value, typename Allocators>
class query_iterator
{
@@ -372,7 +444,7 @@
}}}}}} // namespace boost::geometry::index::detail::rtree::iterators
-#else // BOOST_GEOMETRY_INDEX_DETAIL_QUERY_ITERATORS_USE_TYPE_ERASURE
+#elif defined(BOOST_GEOMETRY_INDEX_DETAIL_QUERY_ITERATORS_USE_TYPE_ERASURE)
#include <boost/type_erasure/any.hpp>
#include <boost/type_erasure/operators.hpp>
Modified: trunk/libs/geometry/doc/index/introduction.qbk
==============================================================================
--- trunk/libs/geometry/doc/index/introduction.qbk Sun Sep 15 18:15:46 2013 (r85692)
+++ trunk/libs/geometry/doc/index/introduction.qbk 2013-09-15 20:25:37 EDT (Sun, 15 Sep 2013) (r85693)
@@ -53,7 +53,7 @@
[[*Example structure*] [[$img/index/rtree/linear.png]] [[$img/index/rtree/quadratic.png]] [[$img/index/rtree/rstar.png]] [[$img/index/rtree/bulk.png]]]
[[*1M Values inserts*] [1.76s] [2.47s] [6.19s] [1.67s]]
[[*100k spatial queries*] [2.21s] [0.51s] [0.12s] [0.07s]]
-[[*100k knn queries*] [6.37s] [2.09s] [0.64s] [0.52]]
+[[*100k knn queries*] [6.37s] [2.09s] [0.64s] [0.52s]]
]
The performance of the R-tree for different values of Max parameter and Min=0.5*Max is presented in the table below.
Modified: trunk/libs/geometry/index/example/benchmark_experimental.cpp
==============================================================================
--- trunk/libs/geometry/index/example/benchmark_experimental.cpp Sun Sep 15 18:15:46 2013 (r85692)
+++ trunk/libs/geometry/index/example/benchmark_experimental.cpp 2013-09-15 20:25:37 EDT (Sun, 15 Sep 2013) (r85693)
@@ -190,6 +190,7 @@
std::cout << time << " - range queried(B) " << queries_count << " found " << temp << '\n';
}
+#ifdef BOOST_GEOMETRY_INDEX_DETAIL_EXPERIMENTAL
{
clock_t::time_point start = clock_t::now();
size_t temp = 0;
@@ -199,8 +200,8 @@
float y = coords[i].second;
result.clear();
std::copy(
- t.qbegin(bgi::intersects(B(P(x - 10, y - 10), P(x + 10, y + 10)))),
- t.qend(bgi::intersects(B(P(x - 10, y - 10), P(x + 10, y + 10)))),
+ t.qbegin_(bgi::intersects(B(P(x - 10, y - 10), P(x + 10, y + 10)))),
+ t.qend_(bgi::intersects(B(P(x - 10, y - 10), P(x + 10, y + 10)))),
std::back_inserter(result));
temp += result.size();
}
@@ -216,8 +217,8 @@
float y = coords[i].second;
result.clear();
mycopy(
- t.qbegin(bgi::intersects(B(P(x - 10, y - 10), P(x + 10, y + 10)))),
- t.qend(),
+ t.qbegin_(bgi::intersects(B(P(x - 10, y - 10), P(x + 10, y + 10)))),
+ t.qend_(),
std::back_inserter(result));
temp += result.size();
}
@@ -234,14 +235,15 @@
result.clear();
boost::copy(
std::make_pair(
- t.qbegin(bgi::intersects(B(P(x - 10, y - 10), P(x + 10, y + 10)))),
- t.qend(bgi::intersects(B(P(x - 10, y - 10), P(x + 10, y + 10))))
+ t.qbegin_(bgi::intersects(B(P(x - 10, y - 10), P(x + 10, y + 10)))),
+ t.qend_(bgi::intersects(B(P(x - 10, y - 10), P(x + 10, y + 10))))
), std::back_inserter(result));
temp += result.size();
}
dur_t time = clock_t::now() - start;
std::cout << time << " - range qbegin(B) qend(B)" << queries_count << " found " << temp << '\n';
}
+#endif // BOOST_GEOMETRY_INDEX_DETAIL_EXPERIMENTAL
{
clock_t::time_point start = clock_t::now();
@@ -252,22 +254,6 @@
float y = coords[i].second;
result.clear();
RT::const_query_iterator first = t.qbegin(bgi::intersects(B(P(x - 10, y - 10), P(x + 10, y + 10))));
- RT::const_query_iterator last = t.qend(bgi::intersects(B(P(x - 10, y - 10), P(x + 10, y + 10))));
- std::copy(first, last, std::back_inserter(result));
- temp += result.size();
- }
- dur_t time = clock_t::now() - start;
- std::cout << time << " - type-erased qbegin(B) qend(B) " << queries_count << " found " << temp << '\n';
- }
- {
- clock_t::time_point start = clock_t::now();
- size_t temp = 0;
- for (size_t i = 0 ; i < queries_count ; ++i )
- {
- float x = coords[i].first;
- float y = coords[i].second;
- result.clear();
- RT::const_query_iterator first = t.qbegin(bgi::intersects(B(P(x - 10, y - 10), P(x + 10, y + 10))));
RT::const_query_iterator last = t.qend();
std::copy(first, last, std::back_inserter(result));
temp += result.size();
@@ -284,22 +270,6 @@
float y = coords[i].second;
result.clear();
RT::const_query_iterator first = t.qbegin(bgi::intersects(B(P(x - 10, y - 10), P(x + 10, y + 10))));
- RT::const_query_iterator last = t.qend(bgi::intersects(B(P(x - 10, y - 10), P(x + 10, y + 10))));
- boost::copy(std::make_pair(first, last), std::back_inserter(result));
- temp += result.size();
- }
- dur_t time = clock_t::now() - start;
- std::cout << time << " - range type-erased qbegin(B) qend(B) " << queries_count << " found " << temp << '\n';
- }
- {
- clock_t::time_point start = clock_t::now();
- size_t temp = 0;
- for (size_t i = 0 ; i < queries_count ; ++i )
- {
- float x = coords[i].first;
- float y = coords[i].second;
- result.clear();
- RT::const_query_iterator first = t.qbegin(bgi::intersects(B(P(x - 10, y - 10), P(x + 10, y + 10))));
RT::const_query_iterator last = t.qend();
boost::copy(std::make_pair(first, last), std::back_inserter(result));
temp += result.size();
@@ -351,6 +321,7 @@
std::cout << time << " - query(nearest(P, " << neighbours_count << ")) " << nearest_queries_count << " found " << temp << '\n';
}
+#ifdef BOOST_GEOMETRY_INDEX_DETAIL_EXPERIMENTAL
{
clock_t::time_point start = clock_t::now();
size_t temp = 0;
@@ -360,8 +331,8 @@
float y = coords[i].second + 100;
result.clear();
std::copy(
- t.qbegin(bgi::nearest(P(x, y), neighbours_count)),
- t.qend(bgi::nearest(P(x, y), neighbours_count)),
+ t.qbegin_(bgi::nearest(P(x, y), neighbours_count)),
+ t.qend_(bgi::nearest(P(x, y), neighbours_count)),
std::back_inserter(result));
temp += result.size();
}
@@ -377,14 +348,15 @@
float y = coords[i].second + 100;
result.clear();
mycopy(
- t.qbegin(bgi::nearest(P(x, y), neighbours_count)),
- t.qend(),
+ t.qbegin_(bgi::nearest(P(x, y), neighbours_count)),
+ t.qend_(),
std::back_inserter(result));
temp += result.size();
}
dur_t time = clock_t::now() - start;
std::cout << time << " - qbegin(nearest(P, " << neighbours_count << ")) qend() " << nearest_queries_count << " found " << temp << '\n';
}
+#endif // BOOST_GEOMETRY_INDEX_DETAIL_EXPERIMENTAL
{
clock_t::time_point start = clock_t::now();
@@ -395,22 +367,6 @@
float y = coords[i].second;
result.clear();
RT::const_query_iterator first = t.qbegin(bgi::nearest(P(x, y), neighbours_count));
- RT::const_query_iterator last = t.qend(bgi::nearest(P(x, y), neighbours_count));
- std::copy(first, last, std::back_inserter(result));
- temp += result.size();
- }
- dur_t time = clock_t::now() - start;
- std::cout << time << " - type-erased qbegin(nearest(P, " << neighbours_count << ")) qend(n) " << nearest_queries_count << " found " << temp << '\n';
- }
- {
- clock_t::time_point start = clock_t::now();
- size_t temp = 0;
- for (size_t i = 0 ; i < nearest_queries_count ; ++i )
- {
- float x = coords[i].first;
- float y = coords[i].second;
- result.clear();
- RT::const_query_iterator first = t.qbegin(bgi::nearest(P(x, y), neighbours_count));
RT::const_query_iterator last = t.qend();
std::copy(first, last, std::back_inserter(result));
temp += result.size();