Boost-Commit :

Date view	Thread view	Subject view	Author view

Subject: [Boost-commit] svn:boost r81571 - in sandbox-branches/geometry/index: . boost/geometry/extensions/index boost/geometry/extensions/index/rtree boost/geometry/extensions/index/translator 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 13:54:11

Next message: marshall_at_[hidden]: "[Boost-commit] svn:boost r81572 - trunk/boost/container/detail"
Previous message: marshall_at_[hidden]: "[Boost-commit] svn:boost r81570 - trunk/libs/function/test"

Author: awulkiew
Date: 2012-11-26 13:54:09 EST (Mon, 26 Nov 2012)
New Revision: 81571
URL: http://svn.boost.org/trac/boost/changeset/81571

Log:
Merged from index_dev.
not_xxx predicates generators removed.
Added rtree constructor, insert() and remove() taking Range.
Added default translator for boost::tuple<>.
Each R*tree test divided into 2 files.
Docs updated/modified/fixed.
Added:
 sandbox-branches/geometry/index/test/rtree/rtree2d_rstar_d_rt.cpp
 - copied unchanged from r81570, /sandbox-branches/geometry/index_dev/test/rtree/rtree2d_rstar_d_rt.cpp
 sandbox-branches/geometry/index/test/rtree/rtree2d_rstar_f_rt.cpp
 - copied unchanged from r81570, /sandbox-branches/geometry/index_dev/test/rtree/rtree2d_rstar_f_rt.cpp
 sandbox-branches/geometry/index/test/rtree/rtree2d_rstar_i_rt.cpp
 - copied unchanged from r81570, /sandbox-branches/geometry/index_dev/test/rtree/rtree2d_rstar_i_rt.cpp
 sandbox-branches/geometry/index/test/rtree/rtree2d_rstar_tt_rt.cpp
 - copied unchanged from r81570, /sandbox-branches/geometry/index_dev/test/rtree/rtree2d_rstar_tt_rt.cpp
 sandbox-branches/geometry/index/test/rtree/rtree3d_rstar_d_rt.cpp
 - copied unchanged from r81570, /sandbox-branches/geometry/index_dev/test/rtree/rtree3d_rstar_d_rt.cpp
 sandbox-branches/geometry/index/test/rtree/rtree3d_rstar_f_rt.cpp
 - copied unchanged from r81570, /sandbox-branches/geometry/index_dev/test/rtree/rtree3d_rstar_f_rt.cpp
 sandbox-branches/geometry/index/test/rtree/rtree3d_rstar_i_rt.cpp
 - copied unchanged from r81570, /sandbox-branches/geometry/index_dev/test/rtree/rtree3d_rstar_i_rt.cpp
 sandbox-branches/geometry/index/test/rtree/rtree3d_rstar_tt_rt.cpp
 - copied unchanged from r81570, /sandbox-branches/geometry/index_dev/test/rtree/rtree3d_rstar_tt_rt.cpp
Properties modified:
 sandbox-branches/geometry/index/ (props changed)
Text files modified:
 sandbox-branches/geometry/index/boost/geometry/extensions/index/predicates.hpp | 108 +------------------
 sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/rtree.hpp | 91 ++++++++++++++++
 sandbox-branches/geometry/index/boost/geometry/extensions/index/translator/def.hpp | 63 +++++++++++
 sandbox-branches/geometry/index/doc/html/geometry_index/r_tree.html | 18 ++-
 sandbox-branches/geometry/index/doc/html/geometry_index/r_tree/creation_and_modification.html | 180 ++++++++++++++++++++++++--------
 sandbox-branches/geometry/index/doc/html/geometry_index/r_tree/exception_safety.html | 30 ++++
 sandbox-branches/geometry/index/doc/html/geometry_index/r_tree/nearest_neighbours_queries.html | 6
 sandbox-branches/geometry/index/doc/html/geometry_index/r_tree/rtree_quickstart.html | 2
 sandbox-branches/geometry/index/doc/html/geometry_index/r_tree/spatial_queries.html | 60 +++++++---
 sandbox-branches/geometry/index/doc/html/index.html | 2
 sandbox-branches/geometry/index/doc/rtree/creation.qbk | 126 +++++++++++++++++-----
 sandbox-branches/geometry/index/doc/rtree/exception_safety.qbk | 4
 sandbox-branches/geometry/index/doc/rtree/nearest_query.qbk | 2
 sandbox-branches/geometry/index/doc/rtree/quickstart.qbk | 2
 sandbox-branches/geometry/index/doc/rtree/spatial_query.qbk | 38 ++++--
 sandbox-branches/geometry/index/test/rtree/Jamfile.v2 | 8 +
 sandbox-branches/geometry/index/test/rtree/rtree2d_rstar_d.cpp | 1
 sandbox-branches/geometry/index/test/rtree/rtree2d_rstar_f.cpp | 1
 sandbox-branches/geometry/index/test/rtree/rtree2d_rstar_i.cpp | 1
 sandbox-branches/geometry/index/test/rtree/rtree2d_rstar_tt.cpp | 1
 sandbox-branches/geometry/index/test/rtree/rtree3d_rstar_d.cpp | 1
 sandbox-branches/geometry/index/test/rtree/rtree3d_rstar_f.cpp | 1
 sandbox-branches/geometry/index/test/rtree/rtree3d_rstar_i.cpp | 1
 sandbox-branches/geometry/index/test/rtree/rtree3d_rstar_tt.cpp | 1
 sandbox-branches/geometry/index/test/rtree/test_rtree.hpp | 219 +++++++++++++++++++++++++++++++++++++--
 25 files changed, 723 insertions(+), 244 deletions(-)

Modified: sandbox-branches/geometry/index/boost/geometry/extensions/index/predicates.hpp
==============================================================================
--- sandbox-branches/geometry/index/boost/geometry/extensions/index/predicates.hpp (original)
+++ sandbox-branches/geometry/index/boost/geometry/extensions/index/predicates.hpp 2012-11-26 13:54:09 EST (Mon, 26 Nov 2012)
@@ -203,15 +203,15 @@
return detail::overlaps<Geometry>(g);
}

-/*!
-Generate a predicate defining Value and Geometry relationship.
-Value will be returned by the query if bg::touches(Indexable, Geometry)
-returns true.
-
-\tparam Geometry The Geometry type.
-
-\param g The Geometry object.
-*/
+//*!
+//Generate a predicate defining Value and Geometry relationship.
+//Value will be returned by the query if bg::touches(Indexable, Geometry)
+//returns true.
+//
+//\tparam Geometry The Geometry type.
+//
+//\param g The Geometry object.
+//*/
//template <typename Geometry>
//inline detail::touches<Geometry> touches(Geometry const& g)
//{
@@ -233,96 +233,6 @@
return detail::within<Geometry>(g);
}

-/*!
-Generate a predicate defining Value and Geometry relationship.
-Value will be returned by the query if bg::covered_by(Indexable, Geometry)
-returns false.
-
-\tparam Geometry The Geometry type.
-
-\param g The Geometry object.
-*/
-template <typename Geometry>
-inline detail::not_covered_by<Geometry> not_covered_by(Geometry const& g)
-{
- return detail::not_covered_by<Geometry>(g);
-}
-
-/*!
-Generate a predicate defining Value and Geometry relationship.
-Value will be returned by the query if bg::disjoint(Indexable, Geometry)
-returns false.
-
-\tparam Geometry The Geometry type.
-
-\param g The Geometry object.
-*/
-template <typename Geometry>
-inline detail::not_disjoint<Geometry> not_disjoint(Geometry const& g)
-{
- return detail::not_disjoint<Geometry>(g);
-}
-
-/*!
-Generate a predicate defining Value and Geometry relationship.
-Value will be returned by the query if bg::intersects(Indexable, Geometry)
-returns false.
-
-\tparam Geometry The Geometry type.
-
-\param g The Geometry object.
-*/
-template <typename Geometry>
-inline detail::not_intersects<Geometry> not_intersects(Geometry const& g)
-{
- return detail::not_intersects<Geometry>(g);
-}
-
-/*!
-Generate a predicate defining Value and Geometry relationship.
-Value will be returned by the query if bg::overlaps(Indexable, Geometry)
-returns false.
-
-\tparam Geometry The Geometry type.
-
-\param g The Geometry object.
-*/
-template <typename Geometry>
-inline detail::not_overlaps<Geometry> not_overlaps(Geometry const& g)
-{
- return detail::not_overlaps<Geometry>(g);
-}
-
-/*!
-Generate a predicate defining Value and Geometry relationship.
-Value will be returned by the query if bg::touches(Indexable, Geometry)
-returns false.
-
-\tparam Geometry The Geometry type.
-
-\param g The Geometry object.
-*/
-//template <typename Geometry>
-//inline detail::not_touches<Geometry> not_touches(Geometry const& g)
-//{
-// return detail::not_touches<Geometry>(g);
-//}
-
-/*!
-Generate a predicate defining Value and Geometry relationship.
-Value will be returned by the query if bg::within(Indexable, Geometry)
-returns false.
-
-\tparam Geometry The Geometry type.
-
-\param g The Geometry object.
-*/
-template <typename Geometry>
-inline detail::not_within<Geometry> not_within(Geometry const& g)
-{
- return detail::not_within<Geometry>(g);
-}
-
namespace detail
{

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 13:54:09 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/boost/geometry/extensions/index/translator/def.hpp
==============================================================================
--- sandbox-branches/geometry/index/boost/geometry/extensions/index/translator/def.hpp (original)
+++ sandbox-branches/geometry/index/boost/geometry/extensions/index/translator/def.hpp 2012-11-26 13:54:09 EST (Mon, 26 Nov 2012)
@@ -176,6 +176,69 @@
}
};

+namespace detail
+{
+
+template <typename Tuple, size_t I, size_t N>
+struct compare_tuples
+{
+ inline static bool apply(Tuple const& t1, Tuple const& t2)
+ {
+ typedef typename boost::tuples::element<I, Tuple>::type T;
+ return dispatch::equals<
+ T,
+ typename geometry::traits::tag<T>::type
+ >::apply(boost::get(t1), boost::get(t2))
+ &&
+ compare_tuples<Tuple, I+1, N>::apply(t1, t2);
+ }
+};
+
+template <typename Tuple, size_t I>
+struct compare_tuples<Tuple, I, I>
+{
+ inline static bool apply(Tuple const&, Tuple const&)
+ {
+ return true;
+ }
+};
+
+} // namespace detail
+
+/*!
+The default translator. This specialization translates from boost::tuple<Indexable, ...>.
+
+\tparam Indexable The Indexable type.
+\tparam Second The second type.
+*/
+template <typename Indexable, typename T1, typename T2, typename T3, typename T4,
+ typename T5, typename T6, typename T7, typename T8, typename T9>
+struct def< boost::tuple<Indexable, T1, T2, T3, T4, T5, T6, T7, T8, T9> >
+{
+ typedef boost::tuple<Indexable, T1, T2, T3, T4, T5, T6, T7, T8, T9> value_type;
+
+ BOOST_MPL_ASSERT_MSG(
+ (!detail::indexable_not_found_error<
+ typename traits::indexable_type<Indexable>::type
+ >::value),
+ NOT_VALID_INDEXABLE_TYPE,
+ (Indexable)
+ );
+
+ typedef Indexable const& result_type;
+
+ result_type operator()(value_type const& value) const
+ {
+ return boost::get<0>(value);
+ }
+
+ bool equals(value_type const& v1, value_type const& v2) const
+ {
+ return detail::compare_tuples<value_type, 0, boost::tuples::length<value_type>::value>
+ ::apply(v1, v2);
+ }
+};
+
}}}} // namespace boost::geometry::index::translator

#endif // BOOST_GEOMETRY_EXTENSIONS_INDEX_TRANSLATOR_DEF_HPP

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 13:54:09 EST (Mon, 26 Nov 2012)
@@ -36,14 +36,16 @@
 parameters</a></dt>
<dt><a href="r_tree/creation_and_modification.html#geometry_index.r_tree.creation_and_modification.values__indexables_and_default_translator">Values,
 Indexables and default Translator</a></dt>
-<dt><a href="r_tree/creation_and_modification.html#geometry_index.r_tree.creation_and_modification.inserting_and_splitting_algorithms">Inserting
- and splitting algorithms</a></dt>
+<dt><a href="r_tree/creation_and_modification.html#geometry_index.r_tree.creation_and_modification.inserting_and_splitting_algorithms__compile_time_">Inserting
+ and splitting algorithms (compile-time)</a></dt>
<dt><a href="r_tree/creation_and_modification.html#geometry_index.r_tree.creation_and_modification.inserting_and_splitting_algorithms__run_time_">Inserting
 and splitting algorithms (run-time)</a></dt>
-<dt><a href="r_tree/creation_and_modification.html#geometry_index.r_tree.creation_and_modification.copying_and_moving">Copying
- and moving</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.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_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>
@@ -51,6 +53,10 @@
 queries</a></dt>
<dt><a href="r_tree/spatial_queries.html#geometry_index.r_tree.spatial_queries.spatial_predicates">Spatial
 predicates</a></dt>
+<dt><a href="r_tree/spatial_queries.html#geometry_index.r_tree.spatial_queries.connecting_predicates">Connecting
+ predicates</a></dt>
+<dt><a href="r_tree/spatial_queries.html#geometry_index.r_tree.spatial_queries.value_predicate">Value
+ predicate</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 13:54:09 EST (Mon, 26 Nov 2012)
@@ -32,14 +32,16 @@
 parameters</a></dt>
<dt><a href="creation_and_modification.html#geometry_index.r_tree.creation_and_modification.values__indexables_and_default_translator">Values,
 Indexables and default Translator</a></dt>
-<dt><a href="creation_and_modification.html#geometry_index.r_tree.creation_and_modification.inserting_and_splitting_algorithms">Inserting
- and splitting algorithms</a></dt>
+<dt><a href="creation_and_modification.html#geometry_index.r_tree.creation_and_modification.inserting_and_splitting_algorithms__compile_time_">Inserting
+ and splitting algorithms (compile-time)</a></dt>
<dt><a href="creation_and_modification.html#geometry_index.r_tree.creation_and_modification.inserting_and_splitting_algorithms__run_time_">Inserting
 and splitting algorithms (run-time)</a></dt>
-<dt><a href="creation_and_modification.html#geometry_index.r_tree.creation_and_modification.copying_and_moving">Copying
- and moving</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.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_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">
@@ -49,25 +51,25 @@

 R-tree has 4 parameters:
 
-<pre class="programlisting">rtree<Value, Parameters, Translator, Allocator>
+<pre class="programlisting">rtree<Value, Parameters, Translator = translator::def<Value>, Allocator> = std::allocator<Value> >
</pre>
<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; ">
<li class="listitem">
- <code class="computeroutput">Value</code> - type of object which will be stored in the container.
+ <code class="computeroutput">Value</code> - type of object which will be stored in the container,
 </li>
<li class="listitem">
- <code class="computeroutput">Parameters</code> - compile-time
- parameters, e.g. inserting/splitting algorithm with min and max nodes'
- elements numbers.
+ <code class="computeroutput">Parameters</code> - parameters
+ type, inserting/splitting algorithm,
 </li>
<li class="listitem">
 <code class="computeroutput">Translator</code> - type of object translating <code class="computeroutput">Value</code> objects to <code class="computeroutput">Indexable</code>
 objects (<code class="computeroutput">Point</code>
 or <code class="computeroutput">Box</code>)
- which R-tree can handle.
+ which R-tree can handle,
 </li>
<li class="listitem">
- <code class="computeroutput">Allocator</code> - the allocator.
+ <code class="computeroutput">Allocator</code> - <code class="computeroutput">Value</code>s allocator, all allocators
+ needed by the container are created from it.
 </li>
</ul></div>
</div>
@@ -78,15 +80,13 @@
</h4></div></div></div>

 R-tree may store <code class="computeroutput">Value</code>s of any type as long the <code class="computeroutput">Translator</code>
- is passed as parameter. It knows how to interpret those <code class="computeroutput">Value</code>s
- and extract an object understandable by the R-tree. Those objects are called
- <code class="computeroutput">Indexable</code>s. Each type adapted to <code class="computeroutput">Point</code>
+ knows how to interpret those <code class="computeroutput">Value</code>s and extract an object
+ that the R-tree can handle. Those objects are called <code class="computeroutput">Indexable</code>s
+ in this documentation. Each type adapted to <code class="computeroutput">Point</code>
 or <code class="computeroutput">Box</code>
- concept is an <code class="computeroutput">Indexable</code>. Default <code class="computeroutput">Translator</code>
- <code class="computeroutput">index::translator::def<Value></code> is able to handle <code class="computeroutput">Point</code>,
- <code class="computeroutput">Box</code>
- or <code class="computeroutput">std::pair<...></code>
- <code class="computeroutput">Value</code>s.
+ concept is an <code class="computeroutput">Indexable</code>. <code class="computeroutput">Value</code>s types which can
+ be handled by the default <code class="computeroutput">Translator</code> - <code class="computeroutput">index::translator::def<Value></code>
+ are defined as follows:
 
<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; ">
<li class="listitem">
@@ -96,33 +96,55 @@
<li class="listitem">
 <code class="computeroutput">Value = Indexable
 | std::pair<Indexable,
- T></code>
+ T>
+ | boost::tuple<Indexable,
+ ...></code>
 </li>
</ul></div>

- 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>.
- 
-
- Examples of <code class="computeroutput">Value</code> types:
+ Examples of default <code class="computeroutput">Value</code> types:
 
<pre class="programlisting">geometry::model::point<...>
geometry::model::point_xy<...>
geometry::model::box<...>
-std::pair<geometry::model::box<...>, size_t>
+std::pair<geometry::model::box<...>, unsigned>
+boost::tuple<geometry::model::point<...>, int, float>
</pre>
+
+ A <code class="computeroutput">Translator</code> is a type which knows how to handle <code class="computeroutput">Value</code>s.
+ It has two purposes:
+ 
+<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; ">
+<li class="listitem">
+ it translates <code class="computeroutput">Value</code> to a more suitable <code class="computeroutput">Indexable</code>
+ type which is needed by most of operations,
+ </li>
+<li class="listitem">
+ performs a comparison of <code class="computeroutput">Value</code> which is needed by the
+ removing process.
+ </li>
+</ul></div>
+
+ A <code class="computeroutput">Translator</code> translates the <code class="computeroutput">Value</code> each time the
+ R-tree needs it. For this reason it should rather return const reference
+ 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>.
+ 
</div>
<div class="section">
<div class="titlepage"><div><div><h4 class="title">
-<a name="geometry_index.r_tree.creation_and_modification.inserting_and_splitting_algorithms"></a><a class="link" href="creation_and_modification.html#geometry_index.r_tree.creation_and_modification.inserting_and_splitting_algorithms" title="Inserting and splitting algorithms">Inserting
- and splitting algorithms</a>
+<a name="geometry_index.r_tree.creation_and_modification.inserting_and_splitting_algorithms__compile_time_"></a><a class="link" href="creation_and_modification.html#geometry_index.r_tree.creation_and_modification.inserting_and_splitting_algorithms__compile_time_" title="Inserting and splitting algorithms (compile-time)">Inserting
+ and splitting algorithms (compile-time)</a>
</h4></div></div></div>

 <code class="computeroutput">Value</code>s may be inserted to the R-tree in many various ways.
 Final internal structure of the R-tree depends on algorithms used in the
- insertion process. The most important is nodes' splitting algorithm. Currently,
- three well-known types of R-trees may be created.
+ insertion process and parameters. The most important is nodes' splitting
+ algorithm. Currently, three well-known types of R-trees may be created.
 

 Linear - classic R-tree using splitting algorithm of linear complexity
@@ -146,66 +168,136 @@
 and splitting algorithms (run-time)</a>
</h4></div></div></div>

- By default splitting algorithm parameters are passed to the R-tree in compile
- time. To use run-time versions of the R-tree one may pass parameters defined
+ Splitting algorithm parameters may be passed to the R-tree in run time.
+ To use run-time versions of the R-tree one may pass parameters defined
 in index::runtime namespace.
 
<pre class="programlisting">// linear
index::rtree<Value, index::runtime::linear> rt(index::runtime::linear(32, 8));
+
// quadratic
index::rtree<Value, index::runtime::quadratic> rt(index::runtime::quadratic(32, 8));
+
// rstar
index::rtree<Value, index::runtime::rstar> rt(index::runtime::rstar(32, 8));
</pre>
+
+ The obvious drawback is a slightly slower R-tree.
+ 
</div>
<div class="section">
<div class="titlepage"><div><div><h4 class="title">
-<a name="geometry_index.r_tree.creation_and_modification.copying_and_moving"></a><a class="link" href="creation_and_modification.html#geometry_index.r_tree.creation_and_modification.copying_and_moving" title="Copying and moving">Copying
- and moving</a>
+<a name="geometry_index.r_tree.creation_and_modification.copying__moving_and_swapping"></a><a class="link" href="creation_and_modification.html#geometry_index.r_tree.creation_and_modification.copying__moving_and_swapping" title="Copying, moving and swapping">Copying,
+ moving and swapping</a>
</h4></div></div></div>

 The R-tree is copyable and movable container. Move semantics is implemented
 using Boost.Move library which also supports compilers not supporting rvalue
 references.
 
-<pre class="programlisting">index::rtree< Value, index::quadratic<32, 8> > rt1;
+<pre class="programlisting">// default constructor
+index::rtree< Value, index::quadratic<32, 8> > rt1;
+
// copy constructor
-index::rtree< Value, index::quadratic<32, 8> > rt2;
+index::rtree< Value, index::quadratic<32, 8> > rt2(r1);
+
// copy assignment
rt2 = r1;
+
// move constructor
index::rtree< Value, index::quadratic<32, 8> > rt3(boost::move(rt1));
+
// move assignment
rt3 = boost::move(rt2);
+
+// swap
+rt3.swap(rt2);
</pre>
</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>

- Following code creates an R-tree using quadratic algorithm.
+ The following code creates an R-tree using quadratic algorithm.
 
<pre class="programlisting">using namespace boost::geometry;
typedef std::pair<Box, int> Value;
index::rtree< Value, index::quadratic<32, 8> > rt;
</pre>

- To insert or remove Value's by method calls one may use the following code.
+ To insert or remove a `Value' by method call one may use the following
+ code.
 
<pre class="programlisting">Value v = std::make_pair(Box(...), 0);
+
rt.insert(v);
+
rt.remove(v);
</pre>

- To insert or remove Value's by function calls one may use the following
+ To insert or remove a `Value' by function call one may use the following
 code.
 
<pre class="programlisting">Value v = std::make_pair(Box(...), 0);
+
index::insert(rt, v);
+
index::remove(rt, v);
</pre>
+
+ Typically you will perform those operations in a loop in order to e.g.
+ insert some number of <code class="computeroutput">Value</code>s corresponding to geometrical
+ objects (e.g. <code class="computeroutput">Polygons</code>)
+ 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>

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-11-26 13:54:09 EST (Mon, 26 Nov 2012)
@@ -30,9 +30,6 @@
 
<div class="itemizedlist"><ul class="itemizedlist" style="list-style-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/doc/html/geometry_index/r_tree/nearest_neighbours_queries.html
==============================================================================
--- sandbox-branches/geometry/index/doc/html/geometry_index/r_tree/nearest_neighbours_queries.html (original)
+++ sandbox-branches/geometry/index/doc/html/geometry_index/r_tree/nearest_neighbours_queries.html 2012-11-26 13:54:09 EST (Mon, 26 Nov 2012)
@@ -59,12 +59,14 @@
 </th>
<th>
 
- knn in a ring (Value's furthest point)
+ knn query - distance to Indexable's furthest point greather than
+ ...
 
 </th>
<th>
 
- knn in a ring (Value's closest point)
+ knn query - distance to Indexable's closest point greather than
+ ...
 
 </th>
</tr></thead>

Modified: sandbox-branches/geometry/index/doc/html/geometry_index/r_tree/rtree_quickstart.html
==============================================================================
--- sandbox-branches/geometry/index/doc/html/geometry_index/r_tree/rtree_quickstart.html (original)
+++ sandbox-branches/geometry/index/doc/html/geometry_index/r_tree/rtree_quickstart.html 2012-11-26 13:54:09 EST (Mon, 26 Nov 2012)
@@ -87,7 +87,7 @@
 Typically <code class="computeroutput">Value</code>s will be
 generated in a loop from e.g. <code class="computeroutput">Polygon</code>s
 stored in some other container. In this case <code class="computeroutput">Box</code>
- objects will probably be created with <code class="computeroutput">geometry::make_envelope()</code> function. But to keep it simple lets just
+ objects will probably be created with <code class="computeroutput">geometry::envelope()</code> function. But to keep it simple lets just
 generate some boxes manually and insert them into the R-tree by using <code class="computeroutput">insert()</code>
 method.

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 13:54:09 EST (Mon, 26 Nov 2012)
@@ -31,13 +31,19 @@
 queries</a></dt>
<dt><a href="spatial_queries.html#geometry_index.r_tree.spatial_queries.spatial_predicates">Spatial
 predicates</a></dt>
+<dt><a href="spatial_queries.html#geometry_index.r_tree.spatial_queries.connecting_predicates">Connecting
+ predicates</a></dt>
+<dt><a href="spatial_queries.html#geometry_index.r_tree.spatial_queries.value_predicate">Value
+ predicate</a></dt>
</dl></div>

 Spatial queries returns <code class="computeroutput">Value</code>s
 which meets some predicates. For instance it may be used to retrieve Values
- intersecting some area or are within some other area. The examples of some
- basic queries may be found in the table below. The query region and result
- <code class="computeroutput">Value</code>s are orange.
+ intersecting some area or are within some other area. Names of predicates
+ corresponds to names of Boost.Geometry
+ algorithms. The examples of some basic queries may be found in the table
+ below. The query region and result <code class="computeroutput">Value</code>s
+ are orange.
 
<div class="informaltable"><table class="table">
<colgroup>
@@ -139,10 +145,8 @@
 predicates</a>
</h4></div></div></div>

- It is possible to define other relations between queried <code class="computeroutput">Value</code>s
- and region/regions of interest. Names of predicates corresponds to names
- of Boost.Geometry
- algorithms.
+ To explicitly define one of the predicates one may pass it to the <code class="computeroutput">spatial_query()</code>
+ as the first argument instead of <code class="computeroutput">Box</code>.
 
<pre class="programlisting">rt.spatial_query(box, std::back_inserter(result)); // default case - intersects
rt.spatial_query(index::intersects(box), std::back_inserter(result)); // the same as default
@@ -158,21 +162,38 @@
// the same as
rt.spatial_query(index::disjoint(box), 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.connecting_predicates"></a><a class="link" href="spatial_queries.html#geometry_index.r_tree.spatial_queries.connecting_predicates" title="Connecting predicates">Connecting
+ predicates</a>
+</h4></div></div></div>

- It's possible to use some number of predicates by passing <code class="computeroutput">std::pair<Pred1, Pred2></code>
- 
-<pre class="programlisting">rt.spatial_query(
- std::make_pair(index::intersects(box1), !index::within(box2))
- , std::back_inserter(result));
-</pre>
-
- or <code class="computeroutput">boost::tuple<Pred1, Pred2, Pred3, ...></code>
+ It's possible to use some number of predicates in one time by passing
+ <code class="computeroutput">std::pair<Pred1, Pred2></code>
+ or <code class="computeroutput">boost::tuple<Pred1, Pred2, Pred3, ...></code>. These predicates are connected
+ by logical AND. Passing all predicates together not only makes possible
+ to construct advanced queries but is also faster than separate calls because
+ the tree is traversed only once. Traversing is continued and <code class="computeroutput">Value</code>s are returned only if all predicates
+ are met. Predicates are checked left-to-right so placing most restictive
+ predicates first should accelerate the search even more.
 
<pre class="programlisting">rt.spatial_query(
+ std::make_pair(
+ index::intersects(box1), !index::within(box2) ),
+ std::back_inserter(result));
+
+rt.spatial_query(
 boost::make_tuple(
- index::intersects(box1), !index::within(box2), index::overlaps(box3))
- , std::back_inserter(result));
+ index::intersects(box1), !index::within(box2), index::overlaps(box3) ),
+ 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.value_predicate"></a><a class="link" href="spatial_queries.html#geometry_index.r_tree.spatial_queries.value_predicate" title="Value predicate">Value
+ predicate</a>
+</h4></div></div></div>

 There is also a unique predicate <code class="computeroutput">index::value(...)</code> taking user-defined function/functor
 which checks if <code class="computeroutput">Value</code> should be returned by the query.
@@ -185,8 +206,9 @@
// ...

rt.spatial_query(
- boost::make_pair(index::intersects(box), index::value(fun))
-, std::back_inserter(result));
+ boost::make_pair(
+ index::intersects(box), index::value(fun) ),
+ std::back_inserter(result));
</pre>
</div>
</div>

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 13:54:09 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 25, 2012 at 21:53:32 GMT</td>
+<td align="left">Last revised: November 26, 2012 at 17:58:58 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 13:54:09 EST (Mon, 26 Nov 2012)
@@ -14,46 +14,53 @@

__rtree__ has 4 parameters:

- rtree<Value, Parameters, Translator, Allocator>
+ rtree<Value, Parameters, Translator = translator::def<Value>, Allocator> = std::allocator<Value> >

-* `__value__` - type of object which will be stored in the container.
-* `Parameters` - compile-time parameters, e.g. inserting/splitting
- algorithm with min and max nodes' elements numbers.
+* `__value__` - type of object which will be stored in the container,
+* `Parameters` - parameters type, inserting/splitting algorithm,
* `__translator__` - type of object translating `Value` objects to
- `__indexable__` objects (`__point__` or `__box__`) which __rtree__ can handle.
-* `Allocator` - the allocator.
+ `__indexable__` objects (`__point__` or `__box__`) which __rtree__ can handle,
+* `Allocator` - `Value`s allocator, all allocators needed by the container are created from it.

[endsect]

[section Values, Indexables and default Translator]

-__rtree__ may store `__value__`s of any type as long the `__translator__`
-is passed as parameter. It knows how to interpret those `__value__`s
-and extract an object understandable by the __rtree__. Those objects are called
-`__indexable__`s. Each type adapted to `__point__` or `__box__` concept is an `__indexable__`.
-Default `__translator__` `index::translator::def<__value__>`
-is able to handle `__point__`, `__box__` or `std::pair<...>` `__value__`s.
+__rtree__ may store `__value__`s of any type as long the `__translator__` knows how to interpret those `__value__`s
+and extract an object that the __rtree__ can handle. Those objects are called
+`__indexable__`s in this documentation. Each type adapted to `__point__` or `__box__` concept is an `__indexable__`.
+`__value__`s types which can be handled by the default `__translator__` - `index::translator::def<__value__>`
+are defined as follows:

* `__indexable__ = __point__ | __box__`
-* `__value__ = Indexable | std::pair<__indexable__, T>`
+* `__value__ = Indexable | std::pair<__indexable__, T> | boost::tuple<__indexable__, ...>`

-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==()`.
-
-Examples of `__value__` types:
+Examples of default `__value__` types:

 geometry::model::point<...>
 geometry::model::point_xy<...>
 geometry::model::box<...>
- std::pair<geometry::model::box<...>, size_t>
+ std::pair<geometry::model::box<...>, unsigned>
+ boost::tuple<geometry::model::point<...>, int, float>
+
+A `__translator__` is a type which knows how to handle `__value__`s. It has two purposes:
+
+* it translates `__value__` to a more suitable `__indexable__` type which is needed by most of operations,
+* performs a comparison of `__value__` which is needed by the removing process.
+
+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==()`.

[endsect]

-[section Inserting and splitting algorithms]
+[section Inserting and splitting algorithms (compile-time)]

`__value__`s may be inserted to the __rtree__ in many various ways. Final internal structure
-of the __rtree__ depends on algorithms used in the insertion process. The most important is
+of the __rtree__ depends on algorithms used in the insertion process and parameters. The most important is
nodes' splitting algorithm. Currently, three well-known types of R-trees may be created.

Linear - classic __rtree__ using splitting algorithm of linear complexity
@@ -72,58 +79,121 @@

[section Inserting and splitting algorithms (run-time)]

-By default splitting algorithm parameters are passed to the __rtree__ in compile time.
+Splitting algorithm parameters may be passed to the __rtree__ in run time.
To use run-time versions of the __rtree__ one may pass parameters defined in index::runtime
namespace.

 // linear
 index::rtree<__value__, index::runtime::linear> rt(index::runtime::linear(32, 8));
+
 // quadratic
 index::rtree<__value__, index::runtime::quadratic> rt(index::runtime::quadratic(32, 8));
+
 // rstar
 index::rtree<__value__, index::runtime::rstar> rt(index::runtime::rstar(32, 8));

+The obvious drawback is a slightly slower __rtree__.
+
[endsect]

-[section Copying and moving]
+[section Copying, moving and swapping]

The __rtree__ is copyable and movable container. Move semantics is implemented using Boost.Move library
which also supports compilers not supporting rvalue references.

+ // default constructor
 index::rtree< __value__, index::quadratic<32, 8> > rt1;
+
 // copy constructor
- index::rtree< __value__, index::quadratic<32, 8> > rt2;
+ index::rtree< __value__, index::quadratic<32, 8> > rt2(r1);
+
 // copy assignment
 rt2 = r1;
+
 // move constructor
 index::rtree< __value__, index::quadratic<32, 8> > rt3(boost::move(rt1));
+
 // move assignment
 rt3 = boost::move(rt2);

+ // swap
+ rt3.swap(rt2);
+
[endsect]

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

-Following code creates an __rtree__ using quadratic algorithm.
+The following code creates an __rtree__ using quadratic algorithm.

 using namespace boost::geometry;
 typedef std::pair<Box, int> __value__;
 index::rtree< __value__, index::quadratic<32, 8> > rt;

-To insert or remove __value__'s by method calls one may use the following
+To insert or remove a `__value__' by method call one may use the following
code.

 __value__ v = std::make_pair(__box__(...), 0);
+
 rt.insert(v);
+
 rt.remove(v);

-To insert or remove __value__'s by function calls one may use the following
+To insert or remove a `__value__' by function call one may use the following
code.

 __value__ v = std::make_pair(__box__(...), 0);
+
 index::insert(rt, v);
+
 index::remove(rt, v);

+Typically you will perform those operations in a loop in order to e.g. insert
+some number of `__value__`s corresponding to geometrical objects (e.g. `Polygons`)
+stored in another container.
+
+[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/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-11-26 13:54:09 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/doc/rtree/nearest_query.qbk
==============================================================================
--- sandbox-branches/geometry/index/doc/rtree/nearest_query.qbk (original)
+++ sandbox-branches/geometry/index/doc/rtree/nearest_query.qbk 2012-11-26 13:54:09 EST (Mon, 26 Nov 2012)
@@ -17,7 +17,7 @@
The query point, region and result Values are orange.

[table
-[[Basic knn query] [knn in a ring (Value's furthest point)] [knn in a ring (Value's closest point)]]
+[[Basic knn query] [knn query - distance to Indexable's furthest point greather than ...] [knn query - distance to Indexable's closest point greather than ...]]
[[[$../images/knn.png]] [[$../images/knn_inters.png]] [[$../images/knn_cover.png]]]
]

Modified: sandbox-branches/geometry/index/doc/rtree/quickstart.qbk
==============================================================================
--- sandbox-branches/geometry/index/doc/rtree/quickstart.qbk (original)
+++ sandbox-branches/geometry/index/doc/rtree/quickstart.qbk 2012-11-26 13:54:09 EST (Mon, 26 Nov 2012)
@@ -31,7 +31,7 @@
[rtree_quickstart_create]

Typically `Value`s will be generated in a loop from e.g. `Polygon`s stored in some other container.
-In this case `Box` objects will probably be created with `geometry::make_envelope()` function.
+In this case `Box` objects will probably be created with `geometry::envelope()` function.
But to keep it simple lets just generate some boxes manually and insert them into the R-tree by
using `insert()` method.

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 13:54:09 EST (Mon, 26 Nov 2012)
@@ -11,7 +11,8 @@
[section Spatial queries]

Spatial queries returns `Value`s which meets some predicates. For instance it may be used to
-retrieve Values intersecting some area or are within some other area. The examples of some
+retrieve Values intersecting some area or are within some other area. Names of predicates
+corresponds to names of __boost_geometry__ algorithms. The examples of some
basic queries may be found in the table below. The query region and result `Value`s are orange.

[table
@@ -45,8 +46,8 @@

[section Spatial predicates]

-It is possible to define other relations between queried `__value__`s and region/regions
-of interest. Names of predicates corresponds to names of __boost_geometry__ algorithms.
+To explicitly define one of the predicates one may pass it to the `spatial_query()` as
+the first argument instead of `Box`.

 rt.spatial_query(box, std::back_inserter(result)); // default case - intersects
 rt.spatial_query(index::intersects(box), std::back_inserter(result)); // the same as default
@@ -61,18 +62,30 @@
 // the same as
 rt.spatial_query(index::disjoint(box), std::back_inserter(result));

-It's possible to use some number of predicates by passing `std::pair<Pred1, Pred2>`
+[endsect]

- rt.spatial_query(
- std::make_pair(index::intersects(box1), !index::within(box2))
- , std::back_inserter(result));
+[section Connecting predicates]

-or `boost::tuple<Pred1, Pred2, Pred3, ...>`
+It's possible to use some number of predicates in one time by passing `std::pair<Pred1, Pred2>`
+or `boost::tuple<Pred1, Pred2, Pred3, ...>`. These predicates are connected by logical AND.
+Passing all predicates together not only makes possible to construct advanced queries but is also
+faster than separate calls because the tree is traversed only once. Traversing is continued and
+`Value`s are returned only if all predicates are met. Predicates are checked left-to-right so placing
+most restictive predicates first should accelerate the search even more.
+
+ rt.spatial_query(
+ std::make_pair(
+ index::intersects(box1), !index::within(box2) ),
+ std::back_inserter(result));

 rt.spatial_query(
 boost::make_tuple(
- index::intersects(box1), !index::within(box2), index::overlaps(box3))
- , std::back_inserter(result));
+ index::intersects(box1), !index::within(box2), index::overlaps(box3) ),
+ std::back_inserter(result));
+
+[endsect]
+
+[section Value predicate]

There is also a unique predicate `index::value(...)` taking user-defined function/functor
which checks if `__value__` should be returned by the query.
@@ -85,8 +98,9 @@
 // ...

 rt.spatial_query(
- boost::make_pair(index::intersects(box), index::value(fun))
- , std::back_inserter(result));
+ boost::make_pair(
+ index::intersects(box), index::value(fun) ),
+ std::back_inserter(result));

[endsect]

Modified: sandbox-branches/geometry/index/test/rtree/Jamfile.v2
==============================================================================
--- sandbox-branches/geometry/index/test/rtree/Jamfile.v2 (original)
+++ sandbox-branches/geometry/index/test/rtree/Jamfile.v2 2012-11-26 13:54:09 EST (Mon, 26 Nov 2012)
@@ -22,6 +22,10 @@
     [ run rtree2d_rstar_f.cpp ]
     [ run rtree2d_rstar_d.cpp ]
     [ run rtree2d_rstar_tt.cpp ]
+ [ run rtree2d_rstar_i_rt.cpp ]
+ [ run rtree2d_rstar_f_rt.cpp ]
+ [ run rtree2d_rstar_d_rt.cpp ]
+ [ run rtree2d_rstar_tt_rt.cpp ]

     [ run rtree3d_linear_i.cpp ]
     [ run rtree3d_linear_f.cpp ]
@@ -37,6 +41,10 @@
     [ run rtree3d_rstar_f.cpp ]
     [ run rtree3d_rstar_d.cpp ]
     [ run rtree3d_rstar_tt.cpp ]
+ [ run rtree3d_rstar_i_rt.cpp ]
+ [ run rtree3d_rstar_f_rt.cpp ]
+ [ run rtree3d_rstar_d_rt.cpp ]
+ [ run rtree3d_rstar_tt_rt.cpp ]

     [ run rtree_exceptions.cpp ]
     ;

Modified: sandbox-branches/geometry/index/test/rtree/rtree2d_rstar_d.cpp
==============================================================================
--- sandbox-branches/geometry/index/test/rtree/rtree2d_rstar_d.cpp (original)
+++ sandbox-branches/geometry/index/test/rtree/rtree2d_rstar_d.cpp 2012-11-26 13:54:09 EST (Mon, 26 Nov 2012)
@@ -18,7 +18,6 @@
 typedef bg::model::point<double, 2, bg::cs::cartesian> P2dc;

 test_rtree<P2dc, bgi::rstar<4, 2> >();
- test_rtree<P2dc>(bgi::runtime::rstar(4, 2));

 return 0;
}

Modified: sandbox-branches/geometry/index/test/rtree/rtree2d_rstar_f.cpp
==============================================================================
--- sandbox-branches/geometry/index/test/rtree/rtree2d_rstar_f.cpp (original)
+++ sandbox-branches/geometry/index/test/rtree/rtree2d_rstar_f.cpp 2012-11-26 13:54:09 EST (Mon, 26 Nov 2012)
@@ -18,7 +18,6 @@
 typedef bg::model::point<float, 2, bg::cs::cartesian> P2fc;

 test_rtree<P2fc, bgi::rstar<4, 2> >();
- test_rtree<P2fc>(bgi::runtime::rstar(4, 2));

 return 0;
}

Modified: sandbox-branches/geometry/index/test/rtree/rtree2d_rstar_i.cpp
==============================================================================
--- sandbox-branches/geometry/index/test/rtree/rtree2d_rstar_i.cpp (original)
+++ sandbox-branches/geometry/index/test/rtree/rtree2d_rstar_i.cpp 2012-11-26 13:54:09 EST (Mon, 26 Nov 2012)
@@ -18,7 +18,6 @@
 typedef bg::model::point<int, 2, bg::cs::cartesian> P2ic;

 test_rtree<P2ic, bgi::rstar<4, 2> >();
- test_rtree<P2ic>(bgi::runtime::rstar(4, 2));

 return 0;
}

Modified: sandbox-branches/geometry/index/test/rtree/rtree2d_rstar_tt.cpp
==============================================================================
--- sandbox-branches/geometry/index/test/rtree/rtree2d_rstar_tt.cpp (original)
+++ sandbox-branches/geometry/index/test/rtree/rtree2d_rstar_tt.cpp 2012-11-26 13:54:09 EST (Mon, 26 Nov 2012)
@@ -20,7 +20,6 @@
 typedef bg::model::point<ttmath_big, 2, bg::cs::cartesian> P2ttmc;

 test_rtree<P2ttmc, bgi::rstar<4, 2> >();
- test_rtree<P2ttmc>(bgi::runtime::rstar(4, 2));
#endif

 return 0;

Modified: sandbox-branches/geometry/index/test/rtree/rtree3d_rstar_d.cpp
==============================================================================
--- sandbox-branches/geometry/index/test/rtree/rtree3d_rstar_d.cpp (original)
+++ sandbox-branches/geometry/index/test/rtree/rtree3d_rstar_d.cpp 2012-11-26 13:54:09 EST (Mon, 26 Nov 2012)
@@ -18,7 +18,6 @@
 typedef bg::model::point<double, 3, bg::cs::cartesian> P3dc;

 test_rtree<P3dc, bgi::rstar<4, 2> >();
- test_rtree<P3dc>(bgi::runtime::rstar(4, 2));

 return 0;
}

Modified: sandbox-branches/geometry/index/test/rtree/rtree3d_rstar_f.cpp
==============================================================================
--- sandbox-branches/geometry/index/test/rtree/rtree3d_rstar_f.cpp (original)
+++ sandbox-branches/geometry/index/test/rtree/rtree3d_rstar_f.cpp 2012-11-26 13:54:09 EST (Mon, 26 Nov 2012)
@@ -18,7 +18,6 @@
 typedef bg::model::point<float, 3, bg::cs::cartesian> P3fc;

 test_rtree<P3fc, bgi::rstar<4, 2> >();
- test_rtree<P3fc>(bgi::runtime::rstar(4, 2));

 return 0;
}

Modified: sandbox-branches/geometry/index/test/rtree/rtree3d_rstar_i.cpp
==============================================================================
--- sandbox-branches/geometry/index/test/rtree/rtree3d_rstar_i.cpp (original)
+++ sandbox-branches/geometry/index/test/rtree/rtree3d_rstar_i.cpp 2012-11-26 13:54:09 EST (Mon, 26 Nov 2012)
@@ -18,7 +18,6 @@
 typedef bg::model::point<int, 3, bg::cs::cartesian> P3ic;

 test_rtree<P3ic, bgi::rstar<4, 2> >();
- test_rtree<P3ic>(bgi::runtime::rstar(4, 2));

 return 0;
}

Modified: sandbox-branches/geometry/index/test/rtree/rtree3d_rstar_tt.cpp
==============================================================================
--- sandbox-branches/geometry/index/test/rtree/rtree3d_rstar_tt.cpp (original)
+++ sandbox-branches/geometry/index/test/rtree/rtree3d_rstar_tt.cpp 2012-11-26 13:54:09 EST (Mon, 26 Nov 2012)
@@ -20,7 +20,6 @@
 typedef bg::model::point<ttmath_big, 3, bg::cs::cartesian> P3ttmc;

 test_rtree<P3ttmc, bgi::rstar<4, 2> >();
- test_rtree<P3ttmc>(bgi::runtime::rstar(4, 2));
#endif

 return 0;

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 13:54:09 EST (Mon, 26 Nov 2012)
@@ -98,6 +98,29 @@
};

template <typename T, typename C>
+struct generate_value< boost::tuple<bg::model::point<T, 2, C>, int, int> >
+{
+ typedef bg::model::point<T, 2, C> P;
+ typedef boost::tuple<P, int, int> R;
+ static R apply(int x, int y)
+ {
+ return boost::make_tuple(P(x, y), x + y * 100, 0);
+ }
+};
+
+template <typename T, typename C>
+struct generate_value< boost::tuple<bg::model::box< bg::model::point<T, 2, C> >, int, int> >
+{
+ typedef bg::model::point<T, 2, C> P;
+ typedef bg::model::box B;
+ typedef boost::tuple<B, int, int> R;
+ static R apply(int x, int y)
+ {
+ return boost::make_tuple(B(P(x, y), P(x + 2, y + 3)), x + y * 100, 0);
+ }
+};
+
+template <typename T, typename C>
struct generate_value< bg::model::point<T, 3, C> >
{
 typedef bg::model::point<T, 3, C> P;
@@ -141,6 +164,29 @@
 }
};

+template <typename T, typename C>
+struct generate_value< boost::tuple<bg::model::point<T, 3, C>, int, int> >
+{
+ typedef bg::model::point<T, 3, C> P;
+ typedef boost::tuple<P, int, int> R;
+ static R apply(int x, int y, int z)
+ {
+ return boost::make_tuple(P(x, y, z), x + y * 100 + z * 10000, 0);
+ }
+};
+
+template <typename T, typename C>
+struct generate_value< boost::tuple<bg::model::box< bg::model::point<T, 3, C> >, int, int> >
+{
+ typedef bg::model::point<T, 3, C> P;
+ typedef bg::model::box B;
+ typedef boost::tuple<B, int, int> R;
+ static R apply(int x, int y, int z)
+ {
+ return boost::make_tuple(B(P(x, y, z), P(x + 2, y + 3, z + 4)), x + y * 100 + z * 10000, 0);
+ }
+};
+
template <size_t Dimension>
struct generate_input
{};
@@ -281,7 +327,7 @@
// rtree specific queries tests

template <typename Value, typename Algo, typename Box>
-void test_intersects_and_disjoint(bgi::rtree<Value, Algo> const& tree, std::vector<Value> const& input, Box const& qbox)
+void test_intersects(bgi::rtree<Value, Algo> const& tree, std::vector<Value> const& input, Box const& qbox)
{
 std::vector<Value> expected_output;

@@ -291,12 +337,24 @@

 test_spatial_query(tree, qbox, expected_output);
 test_spatial_query(tree, bgi::intersects(qbox), expected_output);
- test_spatial_query(tree, !bgi::not_intersects(qbox), expected_output);
 test_spatial_query(tree, !bgi::disjoint(qbox), expected_output);
- test_spatial_query(tree, bgi::not_disjoint(qbox), expected_output);
}

template <typename Value, typename Algo, typename Box>
+void test_disjoint(bgi::rtree<Value, Algo> const& tree, std::vector<Value> const& input, Box const& qbox)
+{
+ std::vector<Value> expected_output;
+
+ BOOST_FOREACH(Value const& v, input)
+ if ( bg::disjoint(tree.translator()(v), qbox) )
+ expected_output.push_back(v);
+
+ test_spatial_query(tree, bgi::disjoint(qbox), expected_output);
+ test_spatial_query(tree, !bgi::intersects(qbox), expected_output);
+}
+
+
+template <typename Value, typename Algo, typename Box>
void test_covered_by(bgi::rtree<Value, Algo> const& tree, std::vector<Value> const& input, Box const& qbox)
{
 std::vector<Value> expected_output;
@@ -599,26 +657,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());
+ {
+ 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);
+ }

- tree.remove(output.begin(), output.end());
+ {
+ 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;
+
+ std::vector<Value> values_to_remove;
+ tree.spatial_query(qbox, std::back_inserter(values_to_remove));
+ BOOST_CHECK(0 < values_to_remove.size());

- BOOST_CHECK(0 == output.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
@@ -638,7 +818,8 @@

 generate_rtree(tree, input, qbox);

- test_intersects_and_disjoint(tree, input, qbox);
+ test_intersects(tree, input, qbox);
+ test_disjoint(tree, input, qbox);
 test_covered_by(tree, input, qbox);
 test_overlaps(tree, input, qbox);
 //test_touches(tree, input, qbox);
@@ -654,6 +835,7 @@

 test_copy_assignment_swap_move(tree, qbox);

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

 // empty tree test
@@ -661,7 +843,8 @@
 Tree empty_tree(parameters);
 std::vector<Value> empty_input;

- test_intersects_and_disjoint(empty_tree, empty_input, qbox);
+ test_intersects(empty_tree, empty_input, qbox);
+ test_disjoint(empty_tree, empty_input, qbox);
 test_covered_by(empty_tree, empty_input, qbox);
 test_overlaps(empty_tree, empty_input, qbox);
 //test_touches(empty_tree, empty_input, qbox);
@@ -681,11 +864,15 @@
 typedef bg::model::box<Point> Box;
 typedef std::pair<Box, int> PairB;
 typedef std::pair<Point, int> PairP;
+ typedef boost::tuple<Point, int, int> TupleP;
+ typedef boost::tuple<Box, int, int> TupleB;

 test_rtree_by_value<Point, Parameters>(parameters);
 test_rtree_by_value<Box, Parameters>(parameters);
 test_rtree_by_value<PairB, Parameters>(parameters);
 test_rtree_by_value<PairP, Parameters>(parameters);
+ test_rtree_by_value<TupleP, Parameters>(parameters);
+ test_rtree_by_value<TupleB, Parameters>(parameters);
}

#endif

Next message: marshall_at_[hidden]: "[Boost-commit] svn:boost r81572 - trunk/boost/container/detail"
Previous message: marshall_at_[hidden]: "[Boost-commit] svn:boost r81570 - trunk/libs/function/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