Boost-Commit :

Date view	Thread view	Subject view	Author view

Subject: [Boost-commit] svn:boost r81552 - in sandbox-branches/geometry/index_dev: boost/geometry/extensions/index/rtree doc/html doc/html/geometry_index doc/html/geometry_index/r_tree doc/rtree test/rtree
From: adam.wulkiewicz_at_[hidden]
Date: 2012-11-26 11:40:23

Author: awulkiew
Date: 2012-11-26 11:40:22 EST (Mon, 26 Nov 2012)
New Revision: 81552
URL: http://svn.boost.org/trac/boost/changeset/81552

Log:
Added constructor, insert() and remove() taking a Range.
Added construction, insertion and removal tests for all versions of methods and functions.
Docs updated.
Text files modified:
   sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/rtree.hpp | 91 ++++++++++++++++++++++++
   sandbox-branches/geometry/index_dev/doc/html/geometry_index/r_tree.html | 6 +
   sandbox-branches/geometry/index_dev/doc/html/geometry_index/r_tree/creation_and_modification.html | 56 ++++++++++++++-
   sandbox-branches/geometry/index_dev/doc/html/geometry_index/r_tree/exception_safety.html | 30 +++++++
   sandbox-branches/geometry/index_dev/doc/html/index.html | 4
   sandbox-branches/geometry/index_dev/doc/rtree/creation.qbk | 45 +++++++++++
   sandbox-branches/geometry/index_dev/doc/rtree/exception_safety.qbk | 4
   sandbox-branches/geometry/index_dev/test/rtree/test_rtree.hpp | 147 ++++++++++++++++++++++++++++++++++++---
   8 files changed, 356 insertions(+), 27 deletions(-)

Modified: sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/rtree.hpp
==============================================================================
--- sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/rtree.hpp (original)
+++ sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/rtree.hpp 2012-11-26 11:40:22 EST (Mon, 26 Nov 2012)
@@ -150,6 +150,36 @@
 }

 /*!
+ The constructor.
+
+ \note Exception-safety: strong
+
+ \param rng The range of Values.
+ \param parameters The parameters object.
+ \param translator The translator object.
+ \param allocator The allocator object.
+ */
+ template<typename Range>
+ inline rtree(Range const& rng, Parameters parameters = Parameters(), translator_type const& translator = translator_type(), Allocator allocator = std::allocator<value_type>())
+ : m_translator(translator) // SHOULDN'T THROW
+ , m_parameters(parameters)
+ , m_allocators(allocator)
+ , m_values_count(0)
+ , m_leafs_level(0)
+ , m_root(0)
+ {
+ try
+ {
+ this->insert(rng);
+ }
+ catch(...)
+ {
+ this->raw_destroy(*this, true);
+ throw;
+ }
+ }
+
+ /*!
 The destructor.

 \note Exception-safety: nothrow
@@ -317,7 +347,25 @@
 }

 /*!
- Remove the value from the container.
+ Insert a range of values to the index.
+
+ \note Exception-safety: basic
+
+ \param rng The range of values.
+ */
+ template <typename Range>
+ inline void insert(Range const& rng)
+ {
+ if ( !m_root )
+ this->raw_create();
+
+ typedef typename boost::range_const_iterator<Range>::type It;
+ for ( It it = boost::const_begin(rng); it != boost::const_end(rng) ; ++it )
+ this->raw_insert(*it);
+ }
+
+ /*!
+ Remove a value from the container.

 \note Exception-safety: basic

@@ -329,7 +377,7 @@
 }

 /*!
- Remove the range of values from the container.
+ Remove a range of values from the container.

 \note Exception-safety: basic

@@ -344,6 +392,21 @@
 }

 /*!
+ Remove a range of values from the container.
+
+ \note Exception-safety: basic
+
+ \param rng The range of values.
+ */
+ template <typename Range>
+ inline void remove(Range const& rng)
+ {
+ typedef typename boost::range_const_iterator<Range>::type It;
+ for ( It it = boost::const_begin(rng); it != boost::const_end(rng) ; ++it )
+ this->raw_remove(*it);
+ }
+
+ /*!
 Find values meeting spatial predicates, e.g. intersecting some box.

 \note Exception-safety: strong
@@ -877,6 +940,18 @@
}

/*!
+Insert a range of values to the index.
+
+\param tree The spatial index.
+\param rng The range of values.
+*/
+template<typename Value, typename Options, typename Translator, typename Allocator, typename Range>
+inline void insert(rtree<Value, Options, Translator, Allocator> & tree, Range const& rng)
+{
+ tree.insert(rng);
+}
+
+/*!
Remove a value from the index.

\param tree The spatial index.
@@ -902,6 +977,18 @@
}

/*!
+Remove a range of values from the index.
+
+\param tree The spatial index.
+\param rng The range of values.
+*/
+template<typename Value, typename Options, typename Translator, typename Allocator, typename Range>
+inline void remove(rtree<Value, Options, Translator, Allocator> & tree, Range const& rng)
+{
+ tree.remove(rng);
+}
+
+/*!
Find values meeting spatial predicates.

\param tree The spatial index.

Modified: sandbox-branches/geometry/index_dev/doc/html/geometry_index/r_tree.html
==============================================================================
--- sandbox-branches/geometry/index_dev/doc/html/geometry_index/r_tree.html (original)
+++ sandbox-branches/geometry/index_dev/doc/html/geometry_index/r_tree.html 2012-11-26 11:40:22 EST (Mon, 26 Nov 2012)
@@ -42,8 +42,10 @@
and splitting algorithms (run-time)</a></dt>
<dt><a href="r_tree/creation_and_modification.html#geometry_index.r_tree.creation_and_modification.copying__moving_and_swapping">Copying,
moving and swapping</a></dt>
-<dt><a href="r_tree/creation_and_modification.html#geometry_index.r_tree.creation_and_modification.inserting_and_removing_values">Inserting
- and removing Values</a></dt>
+<dt><a href="r_tree/creation_and_modification.html#geometry_index.r_tree.creation_and_modification.inserting_and_removing_of_values">Inserting
+ and removing of Values</a></dt>
+<dt><a href="r_tree/creation_and_modification.html#geometry_index.r_tree.creation_and_modification.additional_interface">Additional
+ interface</a></dt>
</dl></dd>
<dt>Spatial queries</dt>
<dd><dl>

Modified: sandbox-branches/geometry/index_dev/doc/html/geometry_index/r_tree/creation_and_modification.html
==============================================================================
--- sandbox-branches/geometry/index_dev/doc/html/geometry_index/r_tree/creation_and_modification.html (original)
+++ sandbox-branches/geometry/index_dev/doc/html/geometry_index/r_tree/creation_and_modification.html 2012-11-26 11:40:22 EST (Mon, 26 Nov 2012)
@@ -38,8 +38,10 @@
 and splitting algorithms (run-time)</a></dt>
<dt><a href="creation_and_modification.html#geometry_index.r_tree.creation_and_modification.copying__moving_and_swapping">Copying,
 moving and swapping</a></dt>
-<dt><a href="creation_and_modification.html#geometry_index.r_tree.creation_and_modification.inserting_and_removing_values">Inserting
- and removing Values</a></dt>
+<dt><a href="creation_and_modification.html#geometry_index.r_tree.creation_and_modification.inserting_and_removing_of_values">Inserting
+ and removing of Values</a></dt>
+<dt><a href="creation_and_modification.html#geometry_index.r_tree.creation_and_modification.additional_interface">Additional
+ interface</a></dt>
</dl></div>
<div class="section">
<div class="titlepage"><div><div><h4 class="title">
@@ -212,8 +214,8 @@
</div>
<div class="section">
<div class="titlepage"><div><div><h4 class="title">
-<a name="geometry_index.r_tree.creation_and_modification.inserting_and_removing_values"></a><a class="link" href="creation_and_modification.html#geometry_index.r_tree.creation_and_modification.inserting_and_removing_values" title="Inserting and removing Values">Inserting
- and removing Values</a>
+<a name="geometry_index.r_tree.creation_and_modification.inserting_and_removing_of_values"></a><a class="link" href="creation_and_modification.html#geometry_index.r_tree.creation_and_modification.inserting_and_removing_of_values" title="Inserting and removing of Values">Inserting
+ and removing of Values</a>
</h4></div></div></div>

 The following code creates an R-tree using quadratic algorithm.
@@ -249,6 +251,52 @@
 stored in another container.
 
</div>
+<div class="section">
+<div class="titlepage"><div><div><h4 class="title">
+<a name="geometry_index.r_tree.creation_and_modification.additional_interface"></a><a class="link" href="creation_and_modification.html#geometry_index.r_tree.creation_and_modification.additional_interface" title="Additional interface">Additional
+ interface</a>
+</h4></div></div></div>
+
+ The R-tree allows creation, inserting and removing of Values from a range.
+ The range may be passed as [first, last) Iterators pair or as a Range.
+ 
+<pre class="programlisting">namespace bgi = boost::geometry::index;
+typedef std::pair<Box, int> Value;
+typedef bgi::rtree< Value, bgi::linear<32, 8> > RTree;
+
+std::vector<Value> values;
+/* vector filling code, here */
+
+// create a RTree with default constructor and insert values with RTree::insert(Value const&)
+RTree rt1;
+BOOST_FOREACH(Value const& v, values)
+ rt1.insert(v);
+
+// create a RTree with default constructor and insert values with RTree::insert(Iter, Iter)
+RTree rt2;
+rt2.insert(values.begin(), values.end());
+
+// create a RTree with default constructor and insert values with RTree::insert(Range)
+RTree rt3;
+rt3.insert(values);
+
+// create a RTree with constructor taking Iterators
+RTree rt4(values.begin(), values.end());
+
+// create a RTree with constructor taking Range
+RTree rt5(values);
+
+// remove values with RTree::remove(Value const&)
+BOOST_FOREACH(Value const& v, values)
+ rt1.remove(v);
+
+// remove values with RTree::remove(Iter, Iter)
+rt2.remove(values.begin(), values.end());
+
+// remove values with RTree::remove(Range)
+rt3.remove(values);
+</pre>
+</div>
</div>
<table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr>
<td align="left"></td>

Modified: sandbox-branches/geometry/index_dev/doc/html/geometry_index/r_tree/exception_safety.html
==============================================================================
--- sandbox-branches/geometry/index_dev/doc/html/geometry_index/r_tree/exception_safety.html (original)
+++ sandbox-branches/geometry/index_dev/doc/html/geometry_index/r_tree/exception_safety.html 2012-11-26 11:40:22 EST (Mon, 26 Nov 2012)
@@ -30,9 +30,6 @@
 
<div class="itemizedlist"><ul class="itemizedlist" type="disc">
<li class="listitem">
- Nonthrowing destructor of the <code class="computeroutput">Value</code>.
- </li>
-<li class="listitem">
 Exception-safe copy constructor of the <code class="computeroutput">Value</code>.
 </li>
<li class="listitem">
@@ -42,6 +39,9 @@
<li class="listitem">
 Nonthrowing copy constructor of the <code class="computeroutput">Translator</code>.
 </li>
+<li class="listitem">
+ Nonthrowing destructors of the above types.
+ </li>
</ul></div>
<div class="informaltable"><table class="table">
<colgroup>
@@ -205,6 +205,18 @@
<tr>
<td>
 
+ <code class="computeroutput">insert(range)</code>
+ 
+ </td>
+<td>
+ 
+ basic
+ 
+ </td>
+</tr>
+<tr>
+<td>
+ 
 <code class="computeroutput">remove(Value)</code>
 
 </td>
@@ -229,6 +241,18 @@
</tr>
<tr>
<td>
+ 
+ <code class="computeroutput">remove(range)</code>
+ 
+ </td>
+<td>
+ 
+ basic
+ 
+ </td>
+</tr>
+<tr>
+<td>
 </td>
<td>
 </td>

Modified: sandbox-branches/geometry/index_dev/doc/html/index.html
==============================================================================
--- sandbox-branches/geometry/index_dev/doc/html/index.html (original)
+++ sandbox-branches/geometry/index_dev/doc/html/index.html 2012-11-26 11:40:22 EST (Mon, 26 Nov 2012)
@@ -3,7 +3,7 @@
<meta http-equiv="Content-Type" content="text/html; charset=US-ASCII">
<title>Chapter 1. Geometry Index</title>
<link rel="stylesheet" href="http://www.boost.org/doc/libs/release/doc/src/boostbook.css" type="text/css">
-<meta name="generator" content="DocBook XSL Stylesheets V1.76.1">
+<meta name="generator" content="DocBook XSL Stylesheets V1.77.1">
<link rel="home" href="index.html" title="Chapter 1. Geometry Index">
<link rel="next" href="geometry_index/introduction.html" title="Introduction">
</head>
@@ -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: November 26, 2012 at 12:46:47 GMT</td>
+<td align="left">Last revised: November 26, 2012 at 16:32:21 GMT</td>
<td align="right"><div class="copyright-footer"></div></td>
</tr></table>
<hr>

Modified: sandbox-branches/geometry/index_dev/doc/rtree/creation.qbk
==============================================================================
--- sandbox-branches/geometry/index_dev/doc/rtree/creation.qbk (original)
+++ sandbox-branches/geometry/index_dev/doc/rtree/creation.qbk 2012-11-26 11:40:22 EST (Mon, 26 Nov 2012)
@@ -120,7 +120,7 @@

[endsect]

-[section Inserting and removing Values]
+[section Inserting and removing of Values]

The following code creates an __rtree__ using quadratic algorithm.

@@ -152,4 +152,47 @@

[endsect]

+[section Additional interface]
+
+The __rtree__ allows creation, inserting and removing of Values from a range. The range may be passed as
+[first, last) Iterators pair or as a Range.
+
+ namespace bgi = boost::geometry::index;
+ typedef std::pair<Box, int> __value__;
+ typedef bgi::rtree< __value__, bgi::linear<32, 8> > RTree;
+
+ std::vector<__value__> values;
+ /* vector filling code, here */
+
+ // create a RTree with default constructor and insert values with RTree::insert(Value const&)
+ RTree rt1;
+ BOOST_FOREACH(__value__ const& v, values)
+ rt1.insert(v);
+
+ // create a RTree with default constructor and insert values with RTree::insert(Iter, Iter)
+ RTree rt2;
+ rt2.insert(values.begin(), values.end());
+
+ // create a RTree with default constructor and insert values with RTree::insert(Range)
+ RTree rt3;
+ rt3.insert(values);
+
+ // create a RTree with constructor taking Iterators
+ RTree rt4(values.begin(), values.end());
+
+ // create a RTree with constructor taking Range
+ RTree rt5(values);
+
+ // remove values with RTree::remove(Value const&)
+ BOOST_FOREACH(__value__ const& v, values)
+ rt1.remove(v);
+
+ // remove values with RTree::remove(Iter, Iter)
+ rt2.remove(values.begin(), values.end());
+
+ // remove values with RTree::remove(Range)
+ rt3.remove(values);
+
+[endsect]
+
[endsect] [/ Creation and modification /]

Modified: sandbox-branches/geometry/index_dev/doc/rtree/exception_safety.qbk
==============================================================================
--- sandbox-branches/geometry/index_dev/doc/rtree/exception_safety.qbk (original)
+++ sandbox-branches/geometry/index_dev/doc/rtree/exception_safety.qbk 2012-11-26 11:40:22 EST (Mon, 26 Nov 2012)
@@ -12,10 +12,10 @@

In order to be exception-safe the __rtree__ requires:

-* Nonthrowing destructor of the `__value__`.
* Exception-safe copy constructor of the `__value__`.
* Exception-safe copy constructor of the `CoordinateType` used in the `Indexable`.
* Nonthrowing copy constructor of the `Translator`.
+* Nonthrowing destructors of the above types.

[table
[[Operation] [exception-safety]]
@@ -33,8 +33,10 @@
[[][]]
[[`insert(__value__)`] [ basic ]]
[[`insert(first, last)`] [ basic ]]
+[[`insert(range)`] [ basic ]]
[[`remove(__value__)`] [ basic ]]
[[`remove(first, last)`] [ basic ]]
+[[`remove(range)`] [ basic ]]
[[][]]
[[`spatial_query(...)`] [ *strong* ]]
[[`nearest_query(...)`] [ *strong* ]]

Modified: sandbox-branches/geometry/index_dev/test/rtree/test_rtree.hpp
==============================================================================
--- sandbox-branches/geometry/index_dev/test/rtree/test_rtree.hpp (original)
+++ sandbox-branches/geometry/index_dev/test/rtree/test_rtree.hpp 2012-11-26 11:40:22 EST (Mon, 26 Nov 2012)
@@ -611,26 +611,148 @@
 //TODO - test SWAP
}

-// rtree removing
+// rtree creation and insertion

template <typename Value, typename Algo, typename Box>
-void test_remove(bgi::rtree<Value, Algo> & tree, Box const& qbox)
+void test_create_insert(bgi::rtree<Value, Algo> & tree, std::vector<Value> const& input, Box const& qbox)
{
- size_t prev_size = tree.size();
+ typedef bgi::rtree<Value, Algo> T;

- std::vector<Value> output;
- tree.spatial_query(qbox, std::back_inserter(output));
+ std::vector<Value> expected_output;
+ tree.spatial_query(qbox, std::back_inserter(expected_output));

- BOOST_CHECK(0 < output.size());
-
- tree.remove(output.begin(), output.end());
+ {
+ T t(tree.parameters());
+ BOOST_FOREACH(Value const& v, input)
+ t.insert(v);
+ BOOST_CHECK(tree.size() == t.size());
+ std::vector<Value> output;
+ t.spatial_query(qbox, std::back_inserter(output));
+ test_exactly_the_same_outputs(t, output, expected_output);
+ }
+ {
+ T t(input.begin(), input.end(), tree.parameters());
+ BOOST_CHECK(tree.size() == t.size());
+ std::vector<Value> output;
+ t.spatial_query(qbox, std::back_inserter(output));
+ test_exactly_the_same_outputs(t, output, expected_output);
+ }
+ {
+ T t(input, tree.parameters());
+ BOOST_CHECK(tree.size() == t.size());
+ std::vector<Value> output;
+ t.spatial_query(qbox, std::back_inserter(output));
+ test_exactly_the_same_outputs(t, output, expected_output);
+ }
+ {
+ T t(tree.parameters());
+ t.insert(input.begin(), input.end());
+ BOOST_CHECK(tree.size() == t.size());
+ std::vector<Value> output;
+ t.spatial_query(qbox, std::back_inserter(output));
+ test_exactly_the_same_outputs(t, output, expected_output);
+ }
+ {
+ T t(tree.parameters());
+ t.insert(input);
+ BOOST_CHECK(tree.size() == t.size());
+ std::vector<Value> output;
+ t.spatial_query(qbox, std::back_inserter(output));
+ test_exactly_the_same_outputs(t, output, expected_output);
+ }
+
+ {
+ T t(tree.parameters());
+ BOOST_FOREACH(Value const& v, input)
+ bgi::insert(t, v);
+ BOOST_CHECK(tree.size() == t.size());
+ std::vector<Value> output;
+ bgi::spatial_query(t, qbox, std::back_inserter(output));
+ test_exactly_the_same_outputs(t, output, expected_output);
+ }
+ {
+ T t(tree.parameters());
+ bgi::insert(t, input.begin(), input.end());
+ BOOST_CHECK(tree.size() == t.size());
+ std::vector<Value> output;
+ bgi::spatial_query(t, qbox, std::back_inserter(output));
+ test_exactly_the_same_outputs(t, output, expected_output);
+ }
+ {
+ T t(tree.parameters());
+ bgi::insert(t, input);
+ BOOST_CHECK(tree.size() == t.size());
+ std::vector<Value> output;
+ bgi::spatial_query(t, qbox, std::back_inserter(output));
+ test_exactly_the_same_outputs(t, output, expected_output);
+ }
+}

- BOOST_CHECK(tree.size() == prev_size - output.size());
+// rtree removing

- output.clear();
- tree.spatial_query(qbox, std::back_inserter(output));
+template <typename Value, typename Algo, typename Box>
+void test_remove(bgi::rtree<Value, Algo> & tree, Box const& qbox)
+{
+ typedef bgi::rtree<Value, Algo> T;

- BOOST_CHECK(0 == output.size());
+ std::vector<Value> values_to_remove;
+ tree.spatial_query(qbox, std::back_inserter(values_to_remove));
+ BOOST_CHECK(0 < values_to_remove.size());
+
+ std::vector<Value> expected_output;
+ tree.spatial_query(bgi::disjoint(qbox), std::back_inserter(expected_output));
+
+ {
+ T t(tree);
+ BOOST_FOREACH(Value const& v, values_to_remove)
+ t.remove(v);
+ std::vector<Value> output;
+ t.spatial_query(bgi::disjoint(qbox), std::back_inserter(output));
+ BOOST_CHECK( output.size() == tree.size() - values_to_remove.size() );
+ test_compare_outputs(t, output, expected_output);
+ }
+ {
+ T t(tree);
+ t.remove(values_to_remove.begin(), values_to_remove.end());
+ std::vector<Value> output;
+ t.spatial_query(bgi::disjoint(qbox), std::back_inserter(output));
+ BOOST_CHECK( output.size() == tree.size() - values_to_remove.size() );
+ test_compare_outputs(t, output, expected_output);
+ }
+ {
+ T t(tree);
+ t.remove(values_to_remove);
+ std::vector<Value> output;
+ t.spatial_query(bgi::disjoint(qbox), std::back_inserter(output));
+ BOOST_CHECK( output.size() == tree.size() - values_to_remove.size() );
+ test_compare_outputs(t, output, expected_output);
+ }
+
+ {
+ T t(tree);
+ BOOST_FOREACH(Value const& v, values_to_remove)
+ bgi::remove(t, v);
+ std::vector<Value> output;
+ bgi::spatial_query(t, bgi::disjoint(qbox), std::back_inserter(output));
+ BOOST_CHECK( output.size() == tree.size() - values_to_remove.size() );
+ test_compare_outputs(t, output, expected_output);
+ }
+ {
+ T t(tree);
+ bgi::remove(t, values_to_remove.begin(), values_to_remove.end());
+ std::vector<Value> output;
+ bgi::spatial_query(t, bgi::disjoint(qbox), std::back_inserter(output));
+ BOOST_CHECK( output.size() == tree.size() - values_to_remove.size() );
+ test_compare_outputs(t, output, expected_output);
+ }
+ {
+ T t(tree);
+ bgi::remove(t, values_to_remove);
+ std::vector<Value> output;
+ bgi::spatial_query(t, bgi::disjoint(qbox), std::back_inserter(output));
+ BOOST_CHECK( output.size() == tree.size() - values_to_remove.size() );
+ test_compare_outputs(t, output, expected_output);
+ }
}

// run all tests for a single Algorithm and single rtree
@@ -667,6 +789,7 @@

 test_copy_assignment_swap_move(tree, qbox);

+ test_create_insert(tree, input, qbox);
 test_remove(tree, qbox);

 // empty tree test

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