Boost logo

Boost-Commit :

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();


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