Boost-Commit :

Date view	Thread view	Subject view	Author view

Subject: [Boost-commit] svn:boost r81582 - in sandbox-branches/geometry/index: . boost/geometry/extensions/index 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 17:20:40

Author: awulkiew
Date: 2012-11-26 17:20:38 EST (Mon, 26 Nov 2012)
New Revision: 81582
URL: http://svn.boost.org/trac/boost/changeset/81582

Log:
Inserter included in the rtree.hpp
Added docs regarding inserter and creation of the rtree from the query results.
Added info about comparison of tuples in default translator.
Merged from index_dev.
Properties modified:
   sandbox-branches/geometry/index/ (props changed)
Text files modified:
   sandbox-branches/geometry/index/boost/geometry/extensions/index/inserter.hpp | 10 +----
   sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/rtree.hpp | 2 +
   sandbox-branches/geometry/index/doc/html/geometry_index/r_tree.html | 4 ++
   sandbox-branches/geometry/index/doc/html/geometry_index/r_tree/creation_and_modification.html | 69 +++++++++++++++++++++++++++++++++------
   sandbox-branches/geometry/index/doc/html/geometry_index/r_tree/spatial_queries.html | 39 ++++++++++++++++++++++
   sandbox-branches/geometry/index/doc/html/index.html | 2
   sandbox-branches/geometry/index/doc/rtree/creation.qbk | 50 ++++++++++++++++++++++------
   sandbox-branches/geometry/index/doc/rtree/spatial_query.qbk | 30 +++++++++++++++++
   sandbox-branches/geometry/index/test/rtree/test_rtree.hpp | 8 ++++
   9 files changed, 184 insertions(+), 30 deletions(-)

Modified: sandbox-branches/geometry/index/boost/geometry/extensions/index/inserter.hpp
==============================================================================
--- sandbox-branches/geometry/index/boost/geometry/extensions/index/inserter.hpp (original)
+++ sandbox-branches/geometry/index/boost/geometry/extensions/index/inserter.hpp 2012-11-26 17:20:38 EST (Mon, 26 Nov 2012)
@@ -22,17 +22,13 @@
public:
 typedef Container container_type;

- inline explicit insert_iterator()
-// : container(0)
- {}
-
 inline explicit insert_iterator(Container & c)
- : container(&c)
+ : container(c)
 {}

 insert_iterator & operator=(typename Container::value_type const& value)
 {
- index::insert(*container, value);
+ container.insert(value);
 return *this;
 }

@@ -52,7 +48,7 @@
 }

private:
- Container * container;
+ Container & container;
};

template <typename Container>

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-11-26 17:20:38 EST (Mon, 26 Nov 2012)
@@ -45,6 +45,8 @@
#include <boost/geometry/extensions/index/rtree/rstar/rstar.hpp>
//#include <boost/geometry/extensions/index/rtree/kmeans/kmeans.hpp>

+#include <boost/geometry/extensions/index/inserter.hpp>
+
// TODO change the name to bounding_tree

namespace boost { namespace geometry { namespace index {

Modified: sandbox-branches/geometry/index/doc/html/geometry_index/r_tree.html
==============================================================================
--- sandbox-branches/geometry/index/doc/html/geometry_index/r_tree.html (original)
+++ sandbox-branches/geometry/index/doc/html/geometry_index/r_tree.html 2012-11-26 17:20:38 EST (Mon, 26 Nov 2012)
@@ -46,6 +46,8 @@
 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>
+<dt><a href="r_tree/creation_and_modification.html#geometry_index.r_tree.creation_and_modification.insert_iterator">Insert
+ iterator</a></dt>
</dl></dd>
<dt>Spatial queries</dt>
<dd><dl>
@@ -57,6 +59,8 @@
 predicates</a></dt>
<dt><a href="r_tree/spatial_queries.html#geometry_index.r_tree.spatial_queries.value_predicate">Value
 predicate</a></dt>
+<dt><a href="r_tree/spatial_queries.html#geometry_index.r_tree.spatial_queries.inserting_query_results_into_the_other_r_tree">Inserting
+ query results into the other R-tree</a></dt>
</dl></dd>
<dt><a href="r_tree/nearest_neighbours_queries.html">Nearest
 neighbours queries</a></dt>

Modified: sandbox-branches/geometry/index/doc/html/geometry_index/r_tree/creation_and_modification.html
==============================================================================
--- sandbox-branches/geometry/index/doc/html/geometry_index/r_tree/creation_and_modification.html (original)
+++ sandbox-branches/geometry/index/doc/html/geometry_index/r_tree/creation_and_modification.html 2012-11-26 17:20:38 EST (Mon, 26 Nov 2012)
@@ -42,6 +42,8 @@
 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>
+<dt><a href="creation_and_modification.html#geometry_index.r_tree.creation_and_modification.insert_iterator">Insert
+ iterator</a></dt>
</dl></div>
<div class="section">
<div class="titlepage"><div><div><h4 class="title">
@@ -130,10 +132,27 @@
 to the <code class="computeroutput">Indexable</code> than a copy.
 

- If comparison of two <code class="computeroutput">Value</code>s is required, the default translator
- compares both components of the <code class="computeroutput">std::pair<...></code>. If the second one is a <code class="computeroutput">Geometry</code>, <code class="computeroutput">geometry::equals()</code> function is used. For other types it
- uses <code class="computeroutput">operator==()</code>.
+ If comparison of two <code class="computeroutput">Value</code>s is required, the default translator:
 
+<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; ">
+<li class="listitem">
+ for <code class="computeroutput">Point</code>
+ and <code class="computeroutput">Box</code>
+ - compares <code class="computeroutput">Value</code>s with geometry::equals().
+ </li>
+<li class="listitem">
+ for <code class="computeroutput">std::pair<...></code>
+ - compares both components of the <code class="computeroutput">Value</code>. The first one
+ is compared with <code class="computeroutput">geometry::equals()</code>. If the second one is a <code class="computeroutput">Geometry</code>, <code class="computeroutput">geometry::equals()</code> function is used. For other types
+ it uses <code class="computeroutput">operator==()</code>.
+ </li>
+<li class="listitem">
+ for <code class="computeroutput">boost::tuple<...></code>
+ - compares all components of the <code class="computeroutput">Value</code>. If the component
+ is a <code class="computeroutput">Geometry</code>, <code class="computeroutput">geometry::equals()</code>
+ function is used. For other types it uses <code class="computeroutput">operator==()</code>.
+ </li>
+</ul></div>
</div>
<div class="section">
<div class="titlepage"><div><div><h4 class="title">
@@ -269,36 +288,64 @@
std::vector<Value> values;
/* vector filling code, here */

-// create a RTree with default constructor and insert values with RTree::insert(Value const&)
+// create R-tree with default constructor and insert values with 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)
+// create R-tree with default constructor and insert values with insert(Iter, Iter)
RTree rt2;
rt2.insert(values.begin(), values.end());

-// create a RTree with default constructor and insert values with RTree::insert(Range)
+// create R-tree with default constructor and insert values with insert(Range)
RTree rt3;
rt3.insert(values);

-// create a RTree with constructor taking Iterators
+// create R-tree with constructor taking Iterators
RTree rt4(values.begin(), values.end());

-// create a RTree with constructor taking Range
+// create R-tree with constructor taking Range
RTree rt5(values);

-// remove values with RTree::remove(Value const&)
+// remove values with remove(Value const&)
BOOST_FOREACH(Value const& v, values)
 rt1.remove(v);

-// remove values with RTree::remove(Iter, Iter)
+// remove values with remove(Iter, Iter)
rt2.remove(values.begin(), values.end());

-// remove values with RTree::remove(Range)
+// remove values with remove(Range)
rt3.remove(values);
</pre>
</div>
+<div class="section">
+<div class="titlepage"><div><div><h4 class="title">
+<a name="geometry_index.r_tree.creation_and_modification.insert_iterator"></a><a class="link" href="creation_and_modification.html#geometry_index.r_tree.creation_and_modification.insert_iterator" title="Insert iterator">Insert
+ iterator</a>
+</h4></div></div></div>
+
+ There are functions like <code class="computeroutput">std::copy()</code>, or R-tree's queries that copy values
+ to an output iterator. In order to insert values to a container in this
+ kind of function insert iterators may be used. Geometry.Index provide its
+ own <code class="computeroutput">bgi::insert_iterator<Container></code>
+ which is generated by <code class="computeroutput">bgi::inserter()</code> function.
+ 
+<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 R-tree and insert values from the vector
+RTree rt1;
+std::copy(values.begin(), values.end(), bgi::inserter(rt1));
+
+// create R-tree and insert values returned by a query
+RTree rt2;
+rt1.spatial_query(Box(/*...*/), bgi::inserter(rt2));
+</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/doc/html/geometry_index/r_tree/spatial_queries.html
==============================================================================
--- sandbox-branches/geometry/index/doc/html/geometry_index/r_tree/spatial_queries.html (original)
+++ sandbox-branches/geometry/index/doc/html/geometry_index/r_tree/spatial_queries.html 2012-11-26 17:20:38 EST (Mon, 26 Nov 2012)
@@ -35,6 +35,8 @@
 predicates</a></dt>
<dt><a href="spatial_queries.html#geometry_index.r_tree.spatial_queries.value_predicate">Value
 predicate</a></dt>
+<dt><a href="spatial_queries.html#geometry_index.r_tree.spatial_queries.inserting_query_results_into_the_other_r_tree">Inserting
+ query results into the other R-tree</a></dt>
</dl></div>

 Spatial queries returns <code class="computeroutput">Value</code>s
@@ -211,6 +213,43 @@
 std::back_inserter(result));
</pre>
</div>
+<div class="section">
+<div class="titlepage"><div><div><h4 class="title">
+<a name="geometry_index.r_tree.spatial_queries.inserting_query_results_into_the_other_r_tree"></a><a class="link" href="spatial_queries.html#geometry_index.r_tree.spatial_queries.inserting_query_results_into_the_other_r_tree" title="Inserting query results into the other R-tree">Inserting
+ query results into the other R-tree</a>
+</h4></div></div></div>
+
+ There are several ways of inserting Values returned by a query to the other
+ R-tree container. The most basic way is creating a temporary container
+ for Values and insert them later.
+ 
+<pre class="programlisting">namespace bgi = boost::geometry::index;
+typedef std::pair<Box, int> Value;
+typedef bgi::rtree< Value, bgi::linear<32, 8> > RTree;
+
+RTree rt1;
+/* some inserting into the tree */
+
+std::vector<Value> result;
+rt1.spatial_query(Box(/*...*/), std::back_inserter(result));
+RTree rt2(result.begin(), result.end());
+</pre>
+
+ However there are better ways. One of these methods is mentioned in the
+ "Creation and modification" section. The insert iterator may
+ be passed directly to the query, which will be the fastest way of inserting
+ query results because temporary container won't be used.
+ 
+<pre class="programlisting">RTree rt3;
+rt1.spatial_query(Box(/*...*/), bgi::inserter(rt3));
+</pre>
+
+ If you like Boost.Range you'll appreciate the third option. You may pass
+ the result Range directly to the constructor.
+ 
+<pre class="programlisting">RTree rt4(rt1 | bgi::adaptors::spatial_queried(Box(/*...*/)));
+</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/doc/html/index.html
==============================================================================
--- sandbox-branches/geometry/index/doc/html/index.html (original)
+++ sandbox-branches/geometry/index/doc/html/index.html 2012-11-26 17:20:38 EST (Mon, 26 Nov 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: November 26, 2012 at 17:58:58 GMT</td>
+<td align="left">Last revised: November 26, 2012 at 22:11:47 GMT</td>
<td align="right"><div class="copyright-footer"></div></td>
</tr></table>
<hr>

Modified: sandbox-branches/geometry/index/doc/rtree/creation.qbk
==============================================================================
--- sandbox-branches/geometry/index/doc/rtree/creation.qbk (original)
+++ sandbox-branches/geometry/index/doc/rtree/creation.qbk 2012-11-26 17:20:38 EST (Mon, 26 Nov 2012)
@@ -51,9 +51,13 @@
A `__translator__` translates the `__value__` each time the __rtree__ needs it. For this reason
it should rather return const reference to the `__indexable__` than a copy.

-If comparison of two `__value__`s is required, the default translator compares
-both components of the `std::pair<...>`. If the second one is a `Geometry`,
-`geometry::equals()` function is used. For other types it uses `operator==()`.
+If comparison of two `__value__`s is required, the default translator:
+
+* for `__point__` and `__box__` - compares `__value__`s with geometry::equals().
+* for `std::pair<...>` - compares both components of the `__value__`. The first one is compared with `geometry::equals()`.
+ If the second one is a `Geometry`, `geometry::equals()` function is used. For other types it uses `operator==()`.
+* for `boost::tuple<...>` - compares all components of the `__value__`. If the component is a `Geometry`, `geometry::equals()`
+ function is used. For other types it uses `operator==()`.

[endsect]

@@ -165,35 +169,59 @@
 std::vector<__value__> values;
 /* vector filling code, here */

- // create a RTree with default constructor and insert values with RTree::insert(Value const&)
+ // create R-tree with default constructor and insert values with 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)
+ // create R-tree with default constructor and insert values with insert(Iter, Iter)
 RTree rt2;
 rt2.insert(values.begin(), values.end());

- // create a RTree with default constructor and insert values with RTree::insert(Range)
+ // create R-tree with default constructor and insert values with insert(Range)
 RTree rt3;
 rt3.insert(values);

- // create a RTree with constructor taking Iterators
+ // create R-tree with constructor taking Iterators
 RTree rt4(values.begin(), values.end());

- // create a RTree with constructor taking Range
+ // create R-tree with constructor taking Range
 RTree rt5(values);

- // remove values with RTree::remove(Value const&)
+ // remove values with remove(Value const&)
 BOOST_FOREACH(__value__ const& v, values)
 rt1.remove(v);

- // remove values with RTree::remove(Iter, Iter)
+ // remove values with remove(Iter, Iter)
 rt2.remove(values.begin(), values.end());

- // remove values with RTree::remove(Range)
+ // remove values with remove(Range)
 rt3.remove(values);

[endsect]

+[section Insert iterator]
+
+There are functions like `std::copy()`, or __rtree__'s queries that copy values to an output iterator.
+In order to insert values to a container in this kind of function insert iterators may be used.
+Geometry.Index provide its own `bgi::insert_iterator<Container>` which is generated by
+`bgi::inserter()` function.
+
+ 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 R-tree and insert values from the vector
+ RTree rt1;
+ std::copy(values.begin(), values.end(), bgi::inserter(rt1));
+
+ // create R-tree and insert values returned by a query
+ RTree rt2;
+ rt1.spatial_query(Box(/*...*/), bgi::inserter(rt2));
+
+[endsect]
+
[endsect] [/ Creation and modification /]

Modified: sandbox-branches/geometry/index/doc/rtree/spatial_query.qbk
==============================================================================
--- sandbox-branches/geometry/index/doc/rtree/spatial_query.qbk (original)
+++ sandbox-branches/geometry/index/doc/rtree/spatial_query.qbk 2012-11-26 17:20:38 EST (Mon, 26 Nov 2012)
@@ -104,4 +104,34 @@

[endsect]

+[section Inserting query results into the other R-tree]
+
+There are several ways of inserting Values returned by a query to the other R-tree container.
+The most basic way is creating a temporary container for Values and insert them later.
+
+ namespace bgi = boost::geometry::index;
+ typedef std::pair<Box, int> __value__;
+ typedef bgi::rtree< __value__, bgi::linear<32, 8> > RTree;
+
+ RTree rt1;
+ /* some inserting into the tree */
+
+ std::vector<Value> result;
+ rt1.spatial_query(Box(/*...*/), std::back_inserter(result));
+ RTree rt2(result.begin(), result.end());
+
+However there are better ways. One of these methods is mentioned in the "Creation and modification" section.
+The insert iterator may be passed directly to the query, which will be the fastest way of inserting
+query results because temporary container won't be used.
+
+ RTree rt3;
+ rt1.spatial_query(Box(/*...*/), bgi::inserter(rt3));
+
+If you like Boost.Range you'll appreciate the third option. You may pass the result Range directly to the
+constructor.
+
+ RTree rt4(rt1 | bgi::adaptors::spatial_queried(Box(/*...*/)));
+
+[endsect]
+
[endsect] [/ Spatial queries /]

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-11-26 17:20:38 EST (Mon, 26 Nov 2012)
@@ -677,6 +677,14 @@
 test_exactly_the_same_outputs(t, output, expected_output);
 }
 {
+ T t(tree.parameters());
+ std::copy(input.begin(), input.end(), bgi::inserter(t));
+ 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;

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