Boost-Commit :

Date view	Thread view	Subject view	Author view

Subject: [Boost-commit] svn:boost r81947 - in sandbox-branches/geometry/index: boost/geometry/extensions/index/rtree boost/geometry/extensions/index/rtree/visitors doc/html doc/html/geometry_index/r_tree doc/rtree test/rtree
From: adam.wulkiewicz_at_[hidden]
Date: 2012-12-14 14:15:35

Author: awulkiew
Date: 2012-12-14 14:15:34 EST (Fri, 14 Dec 2012)
New Revision: 81947
URL: http://svn.boost.org/trac/boost/changeset/81947

Log:
Added rtree::count() method. Docs modified.
Added:
   sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/count.hpp (contents, props changed)
Text files modified:
   sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/rtree.hpp | 25 +++++++++++++++++++++++++
   sandbox-branches/geometry/index/doc/html/geometry_index/r_tree/exception_safety.html | 28 ++++++++++++++++++++--------
   sandbox-branches/geometry/index/doc/html/index.html | 2 +-
   sandbox-branches/geometry/index/doc/rtree/exception_safety.qbk | 11 ++++++-----
   sandbox-branches/geometry/index/test/rtree/test_rtree.hpp | 40 ++++++++++++++++++++++++++++++++++------
   5 files changed, 86 insertions(+), 20 deletions(-)

Modified: sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/rtree.hpp
==============================================================================
--- sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/rtree.hpp (original)
+++ sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/rtree.hpp 2012-12-14 14:15:34 EST (Fri, 14 Dec 2012)
@@ -39,6 +39,7 @@
#include <boost/geometry/extensions/index/rtree/visitors/spatial_query.hpp>
#include <boost/geometry/extensions/index/rtree/visitors/nearest_query.hpp>
#include <boost/geometry/extensions/index/rtree/visitors/children_box.hpp>
+#include <boost/geometry/extensions/index/rtree/visitors/count.hpp>

#include <boost/geometry/extensions/index/rtree/linear/linear.hpp>
#include <boost/geometry/extensions/index/rtree/quadratic/quadratic.hpp>
@@ -645,6 +646,30 @@
 }

 /*!
+ For indexable_type it returns the number of values which indexables equals the parameter.
+ For value_type it returns the number of values which equals the parameter.
+
+ \note Exception-safety: nothrow.
+
+ \param The value or indexable which will be counted.
+
+ \return The number of values found.
+ */
+ template <typename ValueOrIndexable>
+ size_type count(ValueOrIndexable const& vori) const
+ {
+ if ( !m_root )
+ return 0;
+
+ detail::rtree::visitors::count<ValueOrIndexable, value_type, options_type, translator_type, box_type, allocators_type>
+ count_v(vori, m_translator);
+
+ detail::rtree::apply_visitor(count_v, *m_root);
+
+ return count_v.found_count;
+ }
+
+ /*!
 Returns parameters.

 \note Exception-safety: nothrow.

Added: sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/count.hpp
==============================================================================
--- (empty file)
+++ sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/count.hpp 2012-12-14 14:15:34 EST (Fri, 14 Dec 2012)
@@ -0,0 +1,124 @@
+// Boost.Geometry Index
+//
+// R-tree count visitor implementation
+//
+// Copyright (c) 2011-2012 Adam Wulkiewicz, Lodz, Poland.
+//
+// Use, modification and distribution is subject to the Boost Software License,
+// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+#ifndef BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_VISITORS_COUNT_HPP
+#define BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_VISITORS_COUNT_HPP
+
+#include <boost/geometry/extensions/index/rtree/predicates.hpp>
+
+#include <boost/geometry/extensions/index/rtree/node/node.hpp>
+
+namespace boost { namespace geometry { namespace index {
+
+namespace detail { namespace rtree { namespace visitors {
+
+template <typename Indexable, typename Value, typename Options, typename Translator, typename Box, typename Allocators>
+struct count
+ : public rtree::visitor<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag, true>::type
+ , index::nonassignable
+{
+ 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;
+
+ inline count(Indexable const& i, Translator const& t)
+ : indexable(i), tr(t), found_count(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);
+
+ // traverse nodes meeting predicates
+ for (typename elements_type::const_iterator it = elements.begin();
+ it != elements.end(); ++it)
+ {
+ if ( geometry::covered_by(indexable, it->first) )
+ 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);
+
+ // get all values meeting predicates
+ for (typename elements_type::const_iterator it = elements.begin();
+ it != elements.end(); ++it)
+ {
+ // if value meets predicates
+ if ( geometry::equals(indexable, tr(*it)) )
+ {
+ ++found_count;
+ }
+ }
+ }
+
+ Indexable const& indexable;
+ Translator const& tr;
+ typename Allocators::size_type found_count;
+};
+
+template <typename Value, typename Options, typename Translator, typename Box, typename Allocators>
+struct count<Value, Value, Options, Translator, Box, Allocators>
+ : public rtree::visitor<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag, true>::type
+ , index::nonassignable
+{
+ 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;
+
+ inline count(Value const& v, Translator const& t)
+ : value(v), tr(t), found_count(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);
+
+ // traverse nodes meeting predicates
+ for (typename elements_type::const_iterator it = elements.begin();
+ it != elements.end(); ++it)
+ {
+ if ( geometry::covered_by(tr(value), it->first) )
+ 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);
+
+ // get all values meeting predicates
+ for (typename elements_type::const_iterator it = elements.begin();
+ it != elements.end(); ++it)
+ {
+ // if value meets predicates
+ if ( tr.equals(value, *it) )
+ {
+ ++found_count;
+ }
+ }
+ }
+
+ Value const& value;
+ Translator const& tr;
+ typename Allocators::size_type found_count;
+};
+
+}}} // namespace detail::rtree::visitors
+
+}}} // namespace boost::geometry::index
+
+#endif // BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_VISITORS_COUNT_HPP

Modified: sandbox-branches/geometry/index/doc/html/geometry_index/r_tree/exception_safety.html
==============================================================================
--- sandbox-branches/geometry/index/doc/html/geometry_index/r_tree/exception_safety.html (original)
+++ sandbox-branches/geometry/index/doc/html/geometry_index/r_tree/exception_safety.html 2012-12-14 14:15:34 EST (Fri, 14 Dec 2012)
@@ -75,8 +75,8 @@
<tr>
<td>
 
- <code class="computeroutput">rtree(first,
- last)</code>
+ <code class="computeroutput">rtree(Iterator,
+ Iterator)</code>
 
 </td>
<td>
@@ -191,8 +191,8 @@
<tr>
<td>
 
- <code class="computeroutput">insert(first,
- last)</code>
+ <code class="computeroutput">insert(Iterator,
+ Iterator)</code>
 
 </td>
<td>
@@ -204,7 +204,7 @@
<tr>
<td>
 
- <code class="computeroutput">insert(range)</code>
+ <code class="computeroutput">insert(Range)</code>
 
 </td>
<td>
@@ -228,8 +228,8 @@
<tr>
<td>
 
- <code class="computeroutput">remove(first,
- last)</code>
+ <code class="computeroutput">remove(Iterator,
+ Iterator)</code>
 
 </td>
<td>
@@ -241,7 +241,7 @@
<tr>
<td>
 
- <code class="computeroutput">remove(range)</code>
+ <code class="computeroutput">remove(Range)</code>
 
 </td>
<td>
@@ -289,6 +289,18 @@
<tr>
<td>
 
+ <code class="computeroutput">count(ValueOrIndexable)</code>
+ 
+ </td>
+<td>
+ 
+ nothrow
+ 
+ </td>
+</tr>
+<tr>
+<td>
+ 
 <code class="computeroutput">size()</code>
 
 </td>

Modified: sandbox-branches/geometry/index/doc/html/index.html
==============================================================================
--- sandbox-branches/geometry/index/doc/html/index.html (original)
+++ sandbox-branches/geometry/index/doc/html/index.html 2012-12-14 14:15:34 EST (Fri, 14 Dec 2012)
@@ -56,7 +56,7 @@
</div>
</div>
<table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr>
-<td align="left">Last revised: December 14, 2012 at 15:00:09 GMT</td>
+<td align="left">Last revised: December 14, 2012 at 19:10:44 GMT</td>
<td align="right"><div class="copyright-footer"></div></td>
</tr></table>
<hr>

Modified: sandbox-branches/geometry/index/doc/rtree/exception_safety.qbk
==============================================================================
--- sandbox-branches/geometry/index/doc/rtree/exception_safety.qbk (original)
+++ sandbox-branches/geometry/index/doc/rtree/exception_safety.qbk 2012-12-14 14:15:34 EST (Fri, 14 Dec 2012)
@@ -20,7 +20,7 @@
[table
[[Operation] [exception-safety]]
[[`rtree()`] [ /nothrow/ ]]
-[[`rtree(first, last)`] [ *strong* ]]
+[[`rtree(Iterator, Iterator)`] [ *strong* ]]
[[`~rtree()`] [ /nothrow/ ]]
[[][]]
[[`rtree(rtree const&)`] [ *strong* ]]
@@ -32,15 +32,16 @@
[[`swap(rtree &)`] [ /nothrow/ ]]
[[][]]
[[`insert(__value__)`] [ basic ]]
-[[`insert(first, last)`] [ basic ]]
-[[`insert(range)`] [ basic ]]
+[[`insert(Iterator, Iterator)`][ basic ]]
+[[`insert(Range)`] [ basic ]]
[[`remove(__value__)`] [ basic ]]
-[[`remove(first, last)`] [ basic ]]
-[[`remove(range)`] [ basic ]]
+[[`remove(Iterator, Iterator)`][ basic ]]
+[[`remove(Range)`] [ basic ]]
[[][]]
[[`spatial_query(...)`] [ *strong* ]]
[[`nearest_query(...)`] [ *strong* ]]
[[][]]
+[[`count(ValueOrIndexable)`] [ /nothrow/ ]]
[[`size()`] [ /nothrow/ ]]
[[`empty()`] [ /nothrow/ ]]
[[`clear()`] [ /nothrow/ ]]

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 2012-12-14 14:15:34 EST (Fri, 14 Dec 2012)
@@ -1192,7 +1192,7 @@
 test_copy_assignment_swap_move(empty_tree, qbox);
}

-// rtree inserting removing by use of counting_value
+// rtree inserting and removing of counting_value

template <typename Indexable, typename Parameters>
void test_count_rtree_values(Parameters const& parameters)
@@ -1207,11 +1207,6 @@

 generate_rtree(t, input, qbox);

- {
- BOOST_FOREACH(Value const& v, input)
- t.insert(v);
- }
-
 size_t rest_count = input.size();

 BOOST_CHECK(t.size() + rest_count == Value::counter());
@@ -1235,6 +1230,35 @@
 }
}

+// rtree count
+
+template <typename Indexable, typename Parameters>
+void test_rtree_count(Parameters const& parameters)
+{
+ typedef std::pair<Indexable, int> Value;
+ typedef bgi::rtree<Value, Parameters> Tree;
+ typedef typename Tree::box_type B;
+
+ Tree t(parameters);
+ std::vector<Value> input;
+ B qbox;
+
+ generate_rtree(t, input, qbox);
+
+ BOOST_CHECK(t.count(input[0]) == 1);
+ BOOST_CHECK(t.count(input[0].first) == 1);
+
+ t.insert(input[0]);
+
+ BOOST_CHECK(t.count(input[0]) == 2);
+ BOOST_CHECK(t.count(input[0].first) == 2);
+
+ t.insert(std::make_pair(input[0].first, -1));
+
+ BOOST_CHECK(t.count(input[0]) == 2);
+ BOOST_CHECK(t.count(input[0].first) == 3);
+}
+
// run all tests for one Algorithm for some number of rtrees
// defined by some number of Values constructed from given Point

@@ -1254,6 +1278,8 @@
 test_rtree_by_value<VNoDCtor, Parameters>(parameters);

 test_count_rtree_values<Point>(parameters);
+
+ test_rtree_count<Point>(parameters);
}

template<typename Point, typename Parameters>
@@ -1271,6 +1297,8 @@
 test_rtree_by_value<VNoDCtor, Parameters>(parameters);

 test_count_rtree_values<Box>(parameters);
+
+ test_rtree_count<Box>(parameters);
}

#endif

Date view	Thread view	Subject view	Author view

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