|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r81458 - in sandbox-branches/geometry/index: . boost/geometry/extensions/index boost/geometry/extensions/index/adaptors boost/geometry/extensions/index/filters boost/geometry/extensions/index/rtree boost/geometry/extensions/index/rtree/linear boost/geometry/extensions/index/rtree/node boost/geometry/extensions/index/rtree/quadratic boost/geometry/extensions/index/rtree/rstar boost/geometry/extensions/index/rtree/visitors doc doc/html doc/html/geometry_index doc/html/geometry_index/r_tree doc/rtree doc/src/examples/rtree test test/rtree tests
From: adam.wulkiewicz_at_[hidden]
Date: 2012-11-21 10:47:55
Author: awulkiew
Date: 2012-11-21 10:47:51 EST (Wed, 21 Nov 2012)
New Revision: 81458
URL: http://svn.boost.org/trac/boost/changeset/81458
Log:
merged from index_dev.
Fixed memory leaks mostly related to exception-safety issues.
Modified docs, added tests.
Added:
sandbox-branches/geometry/index/boost/geometry/extensions/index/adaptors/
- copied from r81457, /sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/adaptors/
sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/adaptors.hpp
- copied unchanged from r81457, /sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/adaptors.hpp
sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/node/node_auto_ptr.hpp
- copied unchanged from r81457, /sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/node/node_auto_ptr.hpp
sandbox-branches/geometry/index/doc/html/geometry_index/r_tree/creation_and_modification.html
- copied unchanged from r81457, /sandbox-branches/geometry/index_dev/doc/html/geometry_index/r_tree/creation_and_modification.html
sandbox-branches/geometry/index/doc/html/geometry_index/r_tree/exception_safety.html
- copied unchanged from r81457, /sandbox-branches/geometry/index_dev/doc/html/geometry_index/r_tree/exception_safety.html
sandbox-branches/geometry/index/doc/rtree/exception_safety.qbk
- copied unchanged from r81457, /sandbox-branches/geometry/index_dev/doc/rtree/exception_safety.qbk
sandbox-branches/geometry/index/doc/rtree/nearest_query.qbk
- copied unchanged from r81457, /sandbox-branches/geometry/index_dev/doc/rtree/nearest_query.qbk
sandbox-branches/geometry/index/doc/rtree/spatial_query.qbk
- copied unchanged from r81457, /sandbox-branches/geometry/index_dev/doc/rtree/spatial_query.qbk
sandbox-branches/geometry/index/test/rtree/rtree_exceptions.cpp
- copied unchanged from r81457, /sandbox-branches/geometry/index_dev/test/rtree/rtree_exceptions.cpp
sandbox-branches/geometry/index/test/rtree/test_rtree_exceptions.hpp
- copied unchanged from r81457, /sandbox-branches/geometry/index_dev/test/rtree/test_rtree_exceptions.hpp
sandbox-branches/geometry/index/test/rtree/test_throwing.hpp
- copied unchanged from r81457, /sandbox-branches/geometry/index_dev/test/rtree/test_throwing.hpp
Removed:
sandbox-branches/geometry/index/boost/geometry/extensions/index/filters/
sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/filters.hpp
sandbox-branches/geometry/index/doc/rtree/nearest.qbk
sandbox-branches/geometry/index/doc/rtree/query.qbk
Properties modified:
sandbox-branches/geometry/index/ (props changed)
Text files modified:
sandbox-branches/geometry/index/boost/geometry/extensions/index/nonassignable.hpp | 2
sandbox-branches/geometry/index/boost/geometry/extensions/index/pushable_array.hpp | 14
sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/linear/redistribute_elements.hpp | 144 +++++++-----
sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/node/node.hpp | 120 ++++++++++
sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/node/node_d_mem_dynamic.hpp | 2
sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/node/node_s_mem_dynamic.hpp | 2
sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/quadratic/redistribute_elements.hpp | 192 +++++++++-------
sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/rstar/insert.hpp | 445 +++++++++++++++++++++-----------------
sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/rstar/redistribute_elements.hpp | 79 ++++--
sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/rtree.hpp | 453 ++++++++++++++++++++++++---------------
sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/tags.hpp | 2
sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/are_boxes_ok.hpp | 29 +
sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/are_levels_ok.hpp | 7
sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/copy.hpp | 27 +
sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/destroy.hpp | 3
sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/insert.hpp | 105 +++++++--
sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/query.hpp | 2
sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/remove.hpp | 156 +++++++++----
sandbox-branches/geometry/index/doc/html/geometry_index/r_tree.html | 18 +
sandbox-branches/geometry/index/doc/html/geometry_index/r_tree/nearest_neighbours_queries.html | 39 +-
sandbox-branches/geometry/index/doc/html/geometry_index/r_tree/rtree_quickstart.html | 14
sandbox-branches/geometry/index/doc/html/geometry_index/r_tree/spatial_queries.html | 28 +-
sandbox-branches/geometry/index/doc/html/index.html | 6
sandbox-branches/geometry/index/doc/rtree.qbk | 5
sandbox-branches/geometry/index/doc/rtree/creation.qbk | 44 +++
sandbox-branches/geometry/index/doc/rtree/quickstart.qbk | 6
sandbox-branches/geometry/index/doc/src/examples/rtree/quick_start.cpp | 8
sandbox-branches/geometry/index/test/geometry_index_test_common.hpp | 1
sandbox-branches/geometry/index/test/rtree/Jamfile.v2 | 2
sandbox-branches/geometry/index/test/rtree/test_rtree.hpp | 80 +++---
sandbox-branches/geometry/index/tests/additional_speed.cpp | 8
31 files changed, 1275 insertions(+), 768 deletions(-)
Modified: sandbox-branches/geometry/index/boost/geometry/extensions/index/nonassignable.hpp
==============================================================================
--- sandbox-branches/geometry/index/boost/geometry/extensions/index/nonassignable.hpp (original)
+++ sandbox-branches/geometry/index/boost/geometry/extensions/index/nonassignable.hpp 2012-11-21 10:47:51 EST (Wed, 21 Nov 2012)
@@ -1,6 +1,6 @@
// Boost.Geometry Index
//
-// Spatial query predicates
+// Nonassignable base class.
//
// Copyright (c) 2011-2012 Adam Wulkiewicz, Lodz, Poland.
//
Modified: sandbox-branches/geometry/index/boost/geometry/extensions/index/pushable_array.hpp
==============================================================================
--- sandbox-branches/geometry/index/boost/geometry/extensions/index/pushable_array.hpp (original)
+++ sandbox-branches/geometry/index/boost/geometry/extensions/index/pushable_array.hpp 2012-11-21 10:47:51 EST (Wed, 21 Nov 2012)
@@ -46,7 +46,7 @@
m_size = s;
}
- inline void reserve(size_type s)
+ inline void reserve(size_type /*s*/)
{
//BOOST_GEOMETRY_INDEX_ASSERT(s <= Capacity, "size too big");
// do nothing
@@ -133,19 +133,11 @@
m_size = 0;
}
- inline void erase(iterator it)
- {
- BOOST_GEOMETRY_INDEX_ASSERT(0 < m_size, "there are no elements in the container");
- BOOST_GEOMETRY_INDEX_ASSERT(begin() <= it && it < end(), "iterator points on the element outside the container");
- //std::copy(it + 1, end(), it);
- *it = back();
- --m_size;
- }
-
inline void push_back(Element const& v)
{
BOOST_GEOMETRY_INDEX_ASSERT(m_size < Capacity, "can't further increase the size of the container");
- m_array[m_size++] = v;
+ m_array[m_size] = v;
+ ++m_size;
}
inline void pop_back()
Deleted: sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/filters.hpp
==============================================================================
--- sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/filters.hpp 2012-11-21 10:47:51 EST (Wed, 21 Nov 2012)
+++ (empty file)
@@ -1,81 +0,0 @@
-// Boost.Geometry Index
-//
-// R-tree queries filters implementation
-//
-// Copyright (c) 2011-2012 Adam Wulkiewicz, Lodz, Poland.
-//
-// Use, modification and distribution is subject to the Boost Software License,
-// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
-// http://www.boost.org/LICENSE_1_0.txt)
-
-#ifndef BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_FILTERS_HPP
-#define BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_FILTERS_HPP
-
-#include <deque>
-#include <boost/static_assert.hpp>
-
-#include <boost/geometry/extensions/index/filters/query_filter.hpp>
-#include <boost/geometry/extensions/index/filters/nearest_filter.hpp>
-
-namespace boost { namespace geometry { namespace index {
-
-template <typename Value, typename Options, typename Translator, typename Allocator>
-class rtree;
-
-template <typename Value, typename Options, typename Translator, typename Allocator>
-class query_filter< index::rtree<Value, Options, Translator, Allocator> >
-{
-public:
- typedef std::vector<Value> result_type;
- typedef typename result_type::iterator iterator;
- typedef typename result_type::const_iterator const_iterator;
-
- template <typename Predicates>
- inline query_filter(
- index::rtree<Value, Options, Translator, Allocator> const& rtree,
- Predicates const& pred
- )
- {
- rtree.query(pred, std::back_inserter(m_result));
- }
-
- inline iterator begin() { return m_result.begin(); }
- inline iterator end() { return m_result.end(); }
- inline const_iterator begin() const { return m_result.begin(); }
- inline const_iterator end() const { return m_result.end(); }
-
-private:
- result_type m_result;
-};
-
-template <typename Value, typename Options, typename Translator, typename Allocator>
-class nearest_filter< index::rtree<Value, Options, Translator, Allocator> >
-{
-public:
- typedef std::vector<Value> result_type;
- typedef typename result_type::iterator iterator;
- typedef typename result_type::const_iterator const_iterator;
-
- template <typename DistancesPredicates, typename Predicates>
- inline nearest_filter(
- index::rtree<Value, Options, Translator, Allocator> const& rtree,
- DistancesPredicates const& dpred,
- size_t k,
- Predicates const& pred
- )
- {
- rtree.nearest(dpred, k, pred, std::back_inserter(m_result));
- }
-
- inline iterator begin() { return m_result.begin(); }
- inline iterator end() { return m_result.end(); }
- inline const_iterator begin() const { return m_result.begin(); }
- inline const_iterator end() const { return m_result.end(); }
-
-private:
- result_type m_result;
-};
-
-}}} // namespace boost::geometry::index
-
-#endif // BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_FILTERS_HPP
Modified: sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/linear/redistribute_elements.hpp
==============================================================================
--- sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/linear/redistribute_elements.hpp (original)
+++ sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/linear/redistribute_elements.hpp 2012-11-21 10:47:51 EST (Wed, 21 Nov 2012)
@@ -208,7 +208,8 @@
Box & box1,
Box & box2,
parameters_type const& parameters,
- Translator const& translator)
+ Translator const& translator,
+ Allocators & allocators)
{
typedef typename rtree::elements_type<Node>::type elements_type;
typedef typename elements_type::value_type element_type;
@@ -223,89 +224,106 @@
BOOST_GEOMETRY_INDEX_ASSERT(elements1.size() == elements1_count, "unexpected number of elements");
// copy original elements
- elements_type elements_copy(elements1);
+ elements_type elements_copy(elements1); // MAY THROW, STRONG (alloc, copy)
// calculate initial seeds
size_t seed1 = 0;
size_t seed2 = 0;
- linear::pick_seeds<elements_type, parameters_type, Translator>::apply(elements_copy, parameters, translator, seed1, seed2);
+ linear::pick_seeds<
+ elements_type,
+ parameters_type,
+ Translator
+ >::apply(elements_copy, parameters, translator, seed1, seed2);
// prepare nodes' elements containers
elements1.clear();
BOOST_GEOMETRY_INDEX_ASSERT(elements2.empty(), "unexpected container state");
- // add seeds
- elements1.push_back(elements_copy[seed1]);
- elements2.push_back(elements_copy[seed2]);
-
- // calculate boxes
- geometry::convert(rtree::element_indexable(elements_copy[seed1], translator), box1);
- geometry::convert(rtree::element_indexable(elements_copy[seed2], translator), box2);
-
- // initialize areas
- content_type content1 = index::content(box1);
- content_type content2 = index::content(box2);
+ try
+ {
+ // add seeds
+ elements1.push_back(elements_copy[seed1]); // MAY THROW, STRONG (copy)
+ elements2.push_back(elements_copy[seed2]); // MAY THROW, STRONG (alloc, copy)
+
+ // calculate boxes
+ geometry::convert(rtree::element_indexable(elements_copy[seed1], translator), box1);
+ geometry::convert(rtree::element_indexable(elements_copy[seed2], translator), box2);
+
+ // initialize areas
+ content_type content1 = index::content(box1);
+ content_type content2 = index::content(box2);
- BOOST_GEOMETRY_INDEX_ASSERT(2 <= elements1_count, "unexpected elements number");
- size_t remaining = elements1_count - 2;
+ BOOST_GEOMETRY_INDEX_ASSERT(2 <= elements1_count, "unexpected elements number");
+ size_t remaining = elements1_count - 2;
- // redistribute the rest of the elements
- for ( size_t i = 0 ; i < elements1_count ; ++i )
- {
- if (i != seed1 && i != seed2)
+ // redistribute the rest of the elements
+ for ( size_t i = 0 ; i < elements1_count ; ++i )
{
- element_type const& elem = elements_copy[i];
- indexable_type const& indexable = rtree::element_indexable(elem, translator);
-
- // if there is small number of elements left and the number of elements in node is lesser than min_elems
- // just insert them to this node
- if ( elements1.size() + remaining <= parameters.get_min_elements() )
- {
- elements1.push_back(elem);
- geometry::expand(box1, indexable);
- content1 = index::content(box1);
- }
- else if ( elements2.size() + remaining <= parameters.get_min_elements() )
- {
- elements2.push_back(elem);
- geometry::expand(box2, indexable);
- content2 = index::content(box2);
- }
- // choose better node and insert element
- else
+ if (i != seed1 && i != seed2)
{
- // calculate enlarged boxes and areas
- Box enlarged_box1(box1);
- Box enlarged_box2(box2);
- geometry::expand(enlarged_box1, indexable);
- geometry::expand(enlarged_box2, indexable);
- content_type enlarged_content1 = index::content(enlarged_box1);
- content_type enlarged_content2 = index::content(enlarged_box2);
-
- content_type content_increase1 = enlarged_content1 - content1;
- content_type content_increase2 = enlarged_content2 - content2;
-
- // choose group which box content have to be enlarged least or has smaller content or has fewer elements
- if ( content_increase1 < content_increase2 ||
- ( content_increase1 == content_increase2 && content1 < content2 ) ||
- ( content1 == content2 && elements1.size() <= elements2.size() ) )
+ element_type const& elem = elements_copy[i];
+ indexable_type const& indexable = rtree::element_indexable(elem, translator);
+
+ // if there is small number of elements left and the number of elements in node is lesser than min_elems
+ // just insert them to this node
+ if ( elements1.size() + remaining <= parameters.get_min_elements() )
{
- elements1.push_back(elem);
- box1 = enlarged_box1;
- content1 = enlarged_content1;
+ elements1.push_back(elem); // MAY THROW, STRONG (copy)
+ geometry::expand(box1, indexable);
+ content1 = index::content(box1);
}
+ else if ( elements2.size() + remaining <= parameters.get_min_elements() )
+ {
+ elements2.push_back(elem); // MAY THROW, STRONG (alloc, copy)
+ geometry::expand(box2, indexable);
+ content2 = index::content(box2);
+ }
+ // choose better node and insert element
else
{
- elements2.push_back(elem);
- box2 = enlarged_box2;
- content2 = enlarged_content2;
+ // calculate enlarged boxes and areas
+ Box enlarged_box1(box1);
+ Box enlarged_box2(box2);
+ geometry::expand(enlarged_box1, indexable);
+ geometry::expand(enlarged_box2, indexable);
+ content_type enlarged_content1 = index::content(enlarged_box1);
+ content_type enlarged_content2 = index::content(enlarged_box2);
+
+ content_type content_increase1 = enlarged_content1 - content1;
+ content_type content_increase2 = enlarged_content2 - content2;
+
+ // choose group which box content have to be enlarged least or has smaller content or has fewer elements
+ if ( content_increase1 < content_increase2 ||
+ ( content_increase1 == content_increase2 && content1 < content2 ) ||
+ ( content1 == content2 && elements1.size() <= elements2.size() ) )
+ {
+ elements1.push_back(elem); // MAY THROW, STRONG (copy)
+ box1 = enlarged_box1;
+ content1 = enlarged_content1;
+ }
+ else
+ {
+ elements2.push_back(elem); // MAY THROW, STRONG (alloc, copy)
+ box2 = enlarged_box2;
+ content2 = enlarged_content2;
+ }
}
- }
- assert(0 < remaining);
- --remaining;
+ assert(0 < remaining);
+ --remaining;
+ }
}
}
+ catch (...)
+ {
+ elements1.clear();
+ elements2.clear();
+
+ rtree::destroy_elements<Value, Options, Translator, Box, Allocators>::apply(elements_copy, allocators);
+ //elements_copy.clear();
+
+ throw; // RETHROW, BASIC
+ }
}
};
Modified: sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/node/node.hpp
==============================================================================
--- sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/node/node.hpp (original)
+++ sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/node/node.hpp 2012-11-21 10:47:51 EST (Wed, 21 Nov 2012)
@@ -13,14 +13,26 @@
#include <boost/geometry/extensions/index/rtree/node/concept.hpp>
+// WARNING!
+// The Node elements containing pointers to nodes, i.e. pair<Box, node*> MUST NOT throw an exception
+// in the copy constructor. Otherwise copying may be broken in push_back() of internal vectors.
+// The result may be two copies of the same pointer in the vector. This may cause the attempt to destroy
+// the same object two times.
+// This means for example that Value's CoordinateType copy constructor MUST NOT throw an exception
+// because Value's CoordinateType is used in Box type.
+
#include <boost/geometry/extensions/index/rtree/node/node_d_mem_dynamic.hpp>
#include <boost/geometry/extensions/index/rtree/node/node_d_mem_static.hpp>
#include <boost/geometry/extensions/index/rtree/node/node_s_mem_dynamic.hpp>
#include <boost/geometry/extensions/index/rtree/node/node_s_mem_static.hpp>
+#include <boost/geometry/extensions/index/rtree/node/node_auto_ptr.hpp>
+
#include <boost/geometry/algorithms/expand.hpp>
+#include <boost/geometry/extensions/index/rtree/visitors/is_leaf.hpp>
+
namespace boost { namespace geometry { namespace index {
namespace detail { namespace rtree {
@@ -43,6 +55,114 @@
return result;
}
+// destroys subtree if the element is internal node's element
+template <typename Value, typename Options, typename Translator, typename Box, typename Allocators>
+struct destroy_element
+{
+ typedef typename Options::parameters_type parameters_type;
+
+ typedef typename rtree::internal_node<Value, parameters_type, Box, Allocators, typename Options::node_tag>::type internal_node;
+ typedef typename rtree::leaf<Value, parameters_type, Box, Allocators, typename Options::node_tag>::type leaf;
+
+ typedef rtree::node_auto_ptr<Value, Options, Translator, Box, Allocators> node_auto_ptr;
+
+ inline static void apply(typename internal_node::elements_type::value_type & element, Allocators & allocators)
+ {
+ node_auto_ptr dummy(element.second, allocators);
+ element.second = 0;
+ }
+
+ inline static void apply(typename leaf::elements_type::value_type &, Allocators &) {}
+};
+
+// destroys stored subtrees if internal node's elements are passed
+template <typename Value, typename Options, typename Translator, typename Box, typename Allocators>
+struct destroy_elements
+{
+ typedef typename Options::parameters_type parameters_type;
+
+ typedef typename rtree::internal_node<Value, parameters_type, Box, Allocators, typename Options::node_tag>::type internal_node;
+ typedef typename rtree::leaf<Value, parameters_type, Box, Allocators, typename Options::node_tag>::type leaf;
+
+ typedef rtree::node_auto_ptr<Value, Options, Translator, Box, Allocators> node_auto_ptr;
+
+ inline static void apply(typename internal_node::elements_type & elements, Allocators & allocators)
+ {
+ for ( size_t i = 0 ; i < elements.size() ; ++i )
+ {
+ node_auto_ptr dummy(elements[i].second, allocators);
+ elements[i].second = 0;
+ }
+ }
+
+ inline static void apply(typename leaf::elements_type &, Allocators &)
+ {}
+
+ inline static void apply(typename internal_node::elements_type::iterator first,
+ typename internal_node::elements_type::iterator last,
+ Allocators & allocators)
+ {
+ for ( ; first != last ; ++first )
+ {
+ node_auto_ptr dummy(first->second, allocators);
+ first->second = 0;
+ }
+ }
+
+ inline static void apply(typename leaf::elements_type::iterator first,
+ typename leaf::elements_type::iterator last,
+ Allocators &)
+ {}
+};
+
+// clears node, deletes all subtrees stored in node
+template <typename Value, typename Options, typename Translator, typename Box, typename Allocators>
+struct clear_node
+{
+ typedef typename Options::parameters_type parameters_type;
+
+ typedef typename rtree::node<Value, parameters_type, Box, Allocators, typename Options::node_tag>::type node;
+ typedef typename rtree::internal_node<Value, parameters_type, Box, Allocators, typename Options::node_tag>::type internal_node;
+ typedef typename rtree::leaf<Value, parameters_type, Box, Allocators, typename Options::node_tag>::type leaf;
+
+ inline static void apply(node & node, Allocators & allocators)
+ {
+ rtree::visitors::is_leaf<Value, Options, Box, Allocators> ilv;
+ rtree::apply_visitor(ilv, node);
+ if ( ilv.result )
+ {
+ apply(rtree::get<leaf>(node), allocators);
+ }
+ else
+ {
+ apply(rtree::get<internal_node>(node), allocators);
+ }
+ }
+
+ inline static void apply(internal_node & internal_node, Allocators & allocators)
+ {
+ destroy_elements<Value, Options, Translator, Box, Allocators>::apply(rtree::elements(internal_node), allocators);
+ rtree::elements(internal_node).clear();
+ }
+
+ inline static void apply(leaf & leaf, Allocators &)
+ {
+ rtree::elements(leaf).clear();
+ }
+};
+
+template <typename Container, typename Iterator>
+void copy_from_back(Container & container, Iterator it)
+{
+ BOOST_GEOMETRY_INDEX_ASSERT(!container.empty(), "cannot copy from empty container");
+ Iterator back_it = container.end();
+ --back_it;
+ if ( it != back_it )
+ {
+ *it = *back_it; // MAY THROW (copy)
+ }
+}
+
}} // namespace detail::rtree
}}} // namespace boost::geometry::index
Modified: sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/node/node_d_mem_dynamic.hpp
==============================================================================
--- sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/node/node_d_mem_dynamic.hpp (original)
+++ sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/node/node_d_mem_dynamic.hpp 2012-11-21 10:47:51 EST (Wed, 21 Nov 2012)
@@ -203,6 +203,8 @@
try
{
+ // NOTE/TODO
+ // Here the whole node may be copied
alloc_node.construct(p, Node(alloc_elems));
}
catch(...)
Modified: sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/node/node_s_mem_dynamic.hpp
==============================================================================
--- sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/node/node_s_mem_dynamic.hpp (original)
+++ sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/node/node_s_mem_dynamic.hpp 2012-11-21 10:47:51 EST (Wed, 21 Nov 2012)
@@ -166,6 +166,8 @@
try
{
+ // NOTE/TODO
+ // Here the whole node may be copied
alloc_node.construct(p, Node(alloc_elems)); // implicit cast to Variant
}
catch(...)
Modified: sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/quadratic/redistribute_elements.hpp
==============================================================================
--- sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/quadratic/redistribute_elements.hpp (original)
+++ sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/quadratic/redistribute_elements.hpp 2012-11-21 10:47:51 EST (Wed, 21 Nov 2012)
@@ -90,125 +90,151 @@
template <typename Node>
static inline void apply(Node & n,
- Node & second_node,
- Box & box1,
- Box & box2,
+ Node & second_node,
+ Box & box1,
+ Box & box2,
parameters_type const& parameters,
- Translator const& translator)
+ Translator const& translator,
+ Allocators & allocators)
{
typedef typename rtree::elements_type<Node>::type elements_type;
typedef typename elements_type::value_type element_type;
typedef typename rtree::element_indexable_type<element_type, Translator>::type indexable_type;
typedef typename index::traits::coordinate_type<indexable_type>::type coordinate_type;
- elements_type & elements1 = rtree::elements(n);
- elements_type & elements2 = rtree::elements(second_node);
- const size_t elements1_count = parameters.get_max_elements() + 1;
+ elements_type & elements1 = rtree::elements(n);
+ elements_type & elements2 = rtree::elements(second_node);
+ const size_t elements1_count = parameters.get_max_elements() + 1;
- BOOST_GEOMETRY_INDEX_ASSERT(elements1.size() == elements1_count, "unexpected elements number");
+ BOOST_GEOMETRY_INDEX_ASSERT(elements1.size() == elements1_count, "unexpected elements number");
// copy original elements
- elements_type elements_copy(elements1);
+ elements_type elements_copy(elements1); // MAY THROW, STRONG (alloc, copy)
+ elements_type elements_backup(elements1); // MAY THROW, STRONG (alloc, copy)
// calculate initial seeds
size_t seed1 = 0;
size_t seed2 = 0;
- quadratic::pick_seeds<elements_type, parameters_type, Translator, Box>::apply(elements_copy, parameters, translator, seed1, seed2);
+ quadratic::pick_seeds<
+ elements_type,
+ parameters_type,
+ Translator,
+ Box
+ >::apply(elements_copy, parameters, translator, seed1, seed2);
// prepare nodes' elements containers
elements1.clear();
BOOST_GEOMETRY_INDEX_ASSERT(elements2.empty(), "second node's elements container should be empty");
- // add seeds
- elements1.push_back(elements_copy[seed1]);
- elements2.push_back(elements_copy[seed2]);
-
- // calculate boxes
- geometry::convert(rtree::element_indexable(elements_copy[seed1], translator), box1);
- geometry::convert(rtree::element_indexable(elements_copy[seed2], translator), box2);
-
- // remove seeds
- if (seed1 < seed2)
- {
- elements_copy.erase(elements_copy.begin() + seed2);
- elements_copy.erase(elements_copy.begin() + seed1);
- }
- else
+ try
{
- elements_copy.erase(elements_copy.begin() + seed1);
- elements_copy.erase(elements_copy.begin() + seed2);
- }
+ // add seeds
+ elements1.push_back(elements_copy[seed1]); // MAY THROW, STRONG (copy)
+ elements2.push_back(elements_copy[seed2]); // MAY THROW, STRONG (alloc, copy)
+
+ // calculate boxes
+ geometry::convert(rtree::element_indexable(elements_copy[seed1], translator), box1);
+ geometry::convert(rtree::element_indexable(elements_copy[seed2], translator), box2);
+
+ // remove seeds
+ if (seed1 < seed2)
+ {
+ rtree::copy_from_back(elements_copy, elements_copy.begin() + seed2); // MAY THROW, STRONG (copy)
+ elements_copy.pop_back();
+ rtree::copy_from_back(elements_copy, elements_copy.begin() + seed1); // MAY THROW, STRONG (copy)
+ elements_copy.pop_back();
+ }
+ else
+ {
+ rtree::copy_from_back(elements_copy, elements_copy.begin() + seed1); // MAY THROW, STRONG (copy)
+ elements_copy.pop_back();
+ rtree::copy_from_back(elements_copy, elements_copy.begin() + seed2); // MAY THROW, STRONG (copy)
+ elements_copy.pop_back();
+ }
- // initialize areas
- content_type content1 = index::content(box1);
- content_type content2 = index::content(box2);
+ // initialize areas
+ content_type content1 = index::content(box1);
+ content_type content2 = index::content(box2);
- size_t remaining = elements_copy.size();
+ size_t remaining = elements_copy.size();
- // redistribute the rest of the elements
- while ( !elements_copy.empty() )
- {
- typename elements_type::reverse_iterator el_it = elements_copy.rbegin();
- bool insert_into_group1 = false;
+ // redistribute the rest of the elements
+ while ( !elements_copy.empty() )
+ {
+ typename elements_type::reverse_iterator el_it = elements_copy.rbegin();
+ bool insert_into_group1 = false;
- size_t elements1_count = elements1.size();
- size_t elements2_count = elements2.size();
+ size_t elements1_count = elements1.size();
+ size_t elements2_count = elements2.size();
- // if there is small number of elements left and the number of elements in node is lesser than min_elems
- // just insert them to this node
- if ( elements1_count + remaining <= parameters.get_min_elements() )
- {
- insert_into_group1 = true;
- }
- else if ( elements2_count + remaining <= parameters.get_min_elements() )
- {
- insert_into_group1 = false;
- }
- // insert the best element
- else
- {
- // find element with minimum groups areas increses differences
- content_type content_increase1 = 0;
- content_type content_increase2 = 0;
- el_it = pick_next(elements_copy.rbegin(), elements_copy.rend(),
- box1, box2, content1, content2, translator,
- content_increase1, content_increase2);
-
- if ( content_increase1 < content_increase2 ||
- ( content_increase1 == content_increase2 && content1 < content2 ) ||
- ( content1 == content2 && elements1_count <= elements2_count ) )
+ // if there is small number of elements left and the number of elements in node is lesser than min_elems
+ // just insert them to this node
+ if ( elements1_count + remaining <= parameters.get_min_elements() )
{
insert_into_group1 = true;
}
- else
+ else if ( elements2_count + remaining <= parameters.get_min_elements() )
{
insert_into_group1 = false;
}
- }
+ // insert the best element
+ else
+ {
+ // find element with minimum groups areas increses differences
+ content_type content_increase1 = 0;
+ content_type content_increase2 = 0;
+ el_it = pick_next(elements_copy.rbegin(), elements_copy.rend(),
+ box1, box2, content1, content2, translator,
+ content_increase1, content_increase2);
+
+ if ( content_increase1 < content_increase2 ||
+ ( content_increase1 == content_increase2 && content1 < content2 ) ||
+ ( content1 == content2 && elements1_count <= elements2_count ) )
+ {
+ insert_into_group1 = true;
+ }
+ else
+ {
+ insert_into_group1 = false;
+ }
+ }
- // move element to the choosen group
- element_type const& elem = *el_it;
- indexable_type const& indexable = rtree::element_indexable(elem, translator);
+ // move element to the choosen group
+ element_type const& elem = *el_it;
+ indexable_type const& indexable = rtree::element_indexable(elem, translator);
- if ( insert_into_group1 )
- {
- elements1.push_back(elem);
- geometry::expand(box1, indexable);
- content1 = index::content(box1);
- }
- else
- {
- elements2.push_back(elem);
- geometry::expand(box2, indexable);
- content2 = index::content(box2);
+ if ( insert_into_group1 )
+ {
+ elements1.push_back(elem); // MAY THROW, STRONG (copy)
+ geometry::expand(box1, indexable);
+ content1 = index::content(box1);
+ }
+ else
+ {
+ elements2.push_back(elem); // MAY THROW, STRONG (alloc, copy)
+ geometry::expand(box2, indexable);
+ content2 = index::content(box2);
+ }
+
+ BOOST_GEOMETRY_INDEX_ASSERT(!elements_copy.empty(), "expected more elements");
+ typename elements_type::iterator el_it_base = el_it.base();
+ rtree::copy_from_back(elements_copy, --el_it_base); // MAY THROW, STRONG (copy)
+ elements_copy.pop_back();
+
+ BOOST_GEOMETRY_INDEX_ASSERT(0 < remaining, "expected more remaining elements");
+ --remaining;
}
+ }
+ catch(...)
+ {
+ //elements_copy.clear();
+ elements1.clear();
+ elements2.clear();
- BOOST_GEOMETRY_INDEX_ASSERT(!elements_copy.empty(), "expected more elements");
- typename elements_type::iterator el_it_base = el_it.base();
- elements_copy.erase(--el_it_base);
+ rtree::destroy_elements<Value, Options, Translator, Box, Allocators>::apply(elements_backup, allocators);
+ //elements_backup.clear();
- BOOST_GEOMETRY_INDEX_ASSERT(0 < remaining, "expected more remaining elements");
- --remaining;
+ throw; // RETHROW, BASIC
}
}
Modified: sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/rstar/insert.hpp
==============================================================================
--- sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/rstar/insert.hpp (original)
+++ sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/rstar/insert.hpp 2012-11-21 10:47:51 EST (Wed, 21 Nov 2012)
@@ -29,15 +29,16 @@
typedef typename rtree::internal_node<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type internal_node;
typedef typename rtree::leaf<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type leaf;
- typedef typename Options::parameters_type parameters_type;
+ typedef typename Options::parameters_type parameters_type;
template <typename Node>
static inline void apply(typename rtree::elements_type<Node>::type & result_elements,
- Node & n,
- internal_node *parent,
- size_t current_child_index,
+ Node & n,
+ internal_node *parent,
+ size_t current_child_index,
parameters_type const& parameters,
- Translator const& translator)
+ Translator const& translator,
+ Allocators & allocators)
{
typedef typename rtree::elements_type<Node>::type elements_type;
typedef typename elements_type::value_type element_type;
@@ -45,13 +46,13 @@
// TODO: awulkiew - change second point_type to the point type of the Indexable?
typedef typename geometry::default_distance_result<point_type>::type distance_type;
- elements_type & elements = rtree::elements(n);
+ elements_type & elements = rtree::elements(n);
- const size_t elements_count = parameters.get_max_elements() + 1;
- const size_t reinserted_elements_count = parameters.get_reinserted_elements();
+ const size_t elements_count = parameters.get_max_elements() + 1;
+ const size_t reinserted_elements_count = parameters.get_reinserted_elements();
- BOOST_GEOMETRY_INDEX_ASSERT(parent, "node shouldn't be the root node");
- BOOST_GEOMETRY_INDEX_ASSERT(elements.size() == elements_count, "unexpected elements number");
+ BOOST_GEOMETRY_INDEX_ASSERT(parent, "node shouldn't be the root node");
+ BOOST_GEOMETRY_INDEX_ASSERT(elements.size() == elements_count, "unexpected elements number");
BOOST_GEOMETRY_INDEX_ASSERT(0 < reinserted_elements_count, "wrong value of elements to reinsert");
// calculate current node's center
@@ -62,15 +63,16 @@
typename index::detail::rtree::container_from_elements_type<
elements_type,
std::pair<distance_type, element_type>
- >::type sorted_elements(elements_count);
-
- for ( size_t i = 0 ; i < elements_count ; ++i )
+ >::type sorted_elements;
+ // If constructor is used instead of resize() MS implementation leaks here
+ sorted_elements.resize(elements_count); // MAY THROW, STRONG (V, E: alloc, copy)
+
+ for ( size_t i = 0 ; i < elements_count ; ++i )
{
point_type element_center;
- geometry::centroid( rtree::element_indexable(elements[i], translator),
- element_center);
+ geometry::centroid( rtree::element_indexable(elements[i], translator), element_center);
sorted_elements[i].first = geometry::comparable_distance(node_center, element_center);
- sorted_elements[i].second = elements[i];
+ sorted_elements[i].second = elements[i]; // MAY THROW (V, E: copy)
}
// sort elements by distances from center
@@ -78,17 +80,30 @@
sorted_elements.begin(),
sorted_elements.begin() + reinserted_elements_count,
sorted_elements.end(),
- distances_dsc<distance_type, element_type>);
+ distances_dsc<distance_type, element_type>); // MAY THROW, BASIC (V, E: copy)
// copy elements which will be reinserted
- result_elements.resize(reinserted_elements_count);
+ result_elements.resize(reinserted_elements_count); // MAY THROW, STRONG (V, E: alloc, copy)
for ( size_t i = 0 ; i < reinserted_elements_count ; ++i )
- result_elements[i] = sorted_elements[i].second;
+ result_elements[i] = sorted_elements[i].second; // MAY THROW (V, E: copy)
- // copy remaining elements to the current node
- elements.resize(elements_count - reinserted_elements_count);
- for ( size_t i = reinserted_elements_count ; i < elements_count ; ++i )
- elements[i - reinserted_elements_count] = sorted_elements[i].second;
+ try
+ {
+ // copy remaining elements to the current node
+ size_t elements_new_count = elements_count - reinserted_elements_count;
+ elements.resize(elements_new_count); // SHOULDN'T THROW (new_size <= old size)
+ for ( size_t i = 0 ; i < elements_new_count ; ++i )
+ elements[i] = sorted_elements[i + reinserted_elements_count].second; // MAY THROW (V, E: copy)
+ }
+ catch(...)
+ {
+ elements.clear();
+
+ for ( size_t i = 0 ; i < elements_count ; ++i )
+ destroy_element<Value, Options, Translator, Box, Allocators>::apply(sorted_elements[i].second, allocators);
+
+ throw; // RETHROW
+ }
}
private:
@@ -112,99 +127,101 @@
template <size_t InsertIndex, typename Element, typename Value, typename Options, typename Box, typename Allocators>
struct level_insert_elements_type
{
- typedef typename rtree::elements_type<
- typename rtree::internal_node<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type
- >::type type;
+ typedef typename rtree::elements_type<
+ typename rtree::internal_node<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type
+ >::type type;
};
template <typename Value, typename Options, typename Box, typename Allocators>
struct level_insert_elements_type<0, Value, Value, Options, Box, Allocators>
{
- typedef typename rtree::elements_type<
- typename rtree::leaf<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type
- >::type type;
+ typedef typename rtree::elements_type<
+ typename rtree::leaf<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type
+ >::type type;
};
template <size_t InsertIndex, typename Element, typename Value, typename Options, typename Translator, typename Box, typename Allocators>
struct level_insert_base
- : public detail::insert<Element, Value, Options, Translator, Box, Allocators>
+ : public detail::insert<Element, Value, Options, Translator, Box, Allocators>
{
- typedef detail::insert<Element, Value, Options, Translator, Box, Allocators> base;
- typedef typename base::node node;
- typedef typename base::internal_node internal_node;
- typedef typename base::leaf leaf;
-
- typedef typename level_insert_elements_type<InsertIndex, Element, Value, Options, Box, Allocators>::type elements_type;
- typedef typename Options::parameters_type parameters_type;
-
- inline level_insert_base(node* & root,
- size_t & leafs_level,
- Element const& element,
+ typedef detail::insert<Element, Value, Options, Translator, Box, Allocators> base;
+ typedef typename base::node node;
+ typedef typename base::internal_node internal_node;
+ typedef typename base::leaf leaf;
+
+ typedef typename level_insert_elements_type<InsertIndex, Element, Value, Options, Box, Allocators>::type elements_type;
+ typedef typename Options::parameters_type parameters_type;
+
+ inline level_insert_base(node* & root,
+ size_t & leafs_level,
+ Element const& element,
parameters_type const& parameters,
- Translator const& translator,
+ Translator const& translator,
Allocators & allocators,
- size_t relative_level)
- : base(root, leafs_level, element, parameters, translator, allocators, relative_level)
- , result_relative_level(0)
- {}
-
- template <typename Node>
- inline void handle_possible_reinsert_or_split_of_root(Node &n)
- {
- BOOST_GEOMETRY_INDEX_ASSERT(result_elements.empty(), "reinsert should be handled only once for level");
-
- result_relative_level = base::m_leafs_level - base::m_traverse_data.current_level;
-
- // overflow
- if ( base::m_parameters.get_max_elements() < rtree::elements(n).size() )
- {
- // node isn't root node
- if ( !base::m_traverse_data.current_is_root() )
- {
- rstar::remove_elements_to_reinsert<Value, Options, Translator, Box, Allocators>::apply(
- result_elements, n,
- base::m_traverse_data.parent, base::m_traverse_data.current_child_index,
- base::m_parameters, base::m_translator);
- }
- // node is root node
- else
- {
- BOOST_GEOMETRY_INDEX_ASSERT(&n == rtree::get<Node>(base::m_root_node), "node should be the root node");
- base::split(n);
- }
- }
- }
-
- template <typename Node>
- inline void handle_possible_split(Node &n) const
- {
- // overflow
- if ( base::m_parameters.get_max_elements() < rtree::elements(n).size() )
- {
- base::split(n);
- }
- }
-
- template <typename Node>
- inline void recalculate_aabb_if_necessary(Node &n) const
- {
- if ( !result_elements.empty() && !base::m_traverse_data.current_is_root() )
- {
- // calulate node's new box
- base::m_traverse_data.current_element().first =
- elements_box<Box>(rtree::elements(n).begin(), rtree::elements(n).end(), base::m_translator);
- }
- }
+ size_t relative_level)
+ : base(root, leafs_level, element, parameters, translator, allocators, relative_level)
+ , result_relative_level(0)
+ {}
+
+ template <typename Node>
+ inline void handle_possible_reinsert_or_split_of_root(Node &n)
+ {
+ BOOST_GEOMETRY_INDEX_ASSERT(result_elements.empty(), "reinsert should be handled only once for level");
+
+ result_relative_level = base::m_leafs_level - base::m_traverse_data.current_level;
- size_t result_relative_level;
- elements_type result_elements;
+ // overflow
+ if ( base::m_parameters.get_max_elements() < rtree::elements(n).size() )
+ {
+ // node isn't root node
+ if ( !base::m_traverse_data.current_is_root() )
+ {
+ // NOTE: exception-safety
+ // After an exception result_elements may contain garbage, don't use it
+ rstar::remove_elements_to_reinsert<Value, Options, Translator, Box, Allocators>::apply(
+ result_elements, n,
+ base::m_traverse_data.parent, base::m_traverse_data.current_child_index,
+ base::m_parameters, base::m_translator, base::m_allocators); // MAY THROW, BASIC (V, E: alloc, copy)
+ }
+ // node is root node
+ else
+ {
+ BOOST_GEOMETRY_INDEX_ASSERT(&n == rtree::get<Node>(base::m_root_node), "node should be the root node");
+ base::split(n); // MAY THROW (V, E: alloc, copy, N: alloc)
+ }
+ }
+ }
+
+ template <typename Node>
+ inline void handle_possible_split(Node &n) const
+ {
+ // overflow
+ if ( base::m_parameters.get_max_elements() < rtree::elements(n).size() )
+ {
+ base::split(n); // MAY THROW (V, E: alloc, copy, N: alloc)
+ }
+ }
+
+ template <typename Node>
+ inline void recalculate_aabb_if_necessary(Node &n) const
+ {
+ if ( !result_elements.empty() && !base::m_traverse_data.current_is_root() )
+ {
+ // calulate node's new box
+ base::m_traverse_data.current_element().first =
+ elements_box<Box>(rtree::elements(n).begin(), rtree::elements(n).end(), base::m_translator);
+ }
+ }
+
+ size_t result_relative_level;
+ elements_type result_elements;
};
template <size_t InsertIndex, typename Element, typename Value, typename Options, typename Translator, typename Box, typename Allocators>
struct level_insert
: public level_insert_base<InsertIndex, Element, Value, Options, Translator, Box, Allocators>
{
- typedef level_insert_base<InsertIndex, Element, Value, Options, Translator, Box, Allocators> base;
+ typedef level_insert_base<InsertIndex, Element, Value, Options, Translator, Box, Allocators> base;
typedef typename base::node node;
typedef typename base::internal_node internal_node;
typedef typename base::leaf leaf;
@@ -223,12 +240,12 @@
inline void operator()(internal_node & n)
{
- BOOST_GEOMETRY_INDEX_ASSERT(base::m_traverse_data.current_level < base::m_leafs_level, "unexpected level");
+ BOOST_GEOMETRY_INDEX_ASSERT(base::m_traverse_data.current_level < base::m_leafs_level, "unexpected level");
if ( base::m_traverse_data.current_level < base::m_level )
{
// next traversing step
- base::traverse(*this, n);
+ base::traverse(*this, n); // MAY THROW (E: alloc, copy, N: alloc)
// further insert
if ( 0 < InsertIndex )
@@ -237,26 +254,39 @@
if ( base::m_traverse_data.current_level == base::m_level - 1 )
{
- base::handle_possible_reinsert_or_split_of_root(n);
+ base::handle_possible_reinsert_or_split_of_root(n); // MAY THROW (E: alloc, copy, N: alloc)
}
}
}
else
{
- BOOST_GEOMETRY_INDEX_ASSERT(base::m_level == base::m_traverse_data.current_level, "unexpected level");
+ BOOST_GEOMETRY_INDEX_ASSERT(base::m_level == base::m_traverse_data.current_level, "unexpected level");
+
+ try
+ {
+ // push new child node
+ rtree::elements(n).push_back(base::m_element); // MAY THROW, STRONG (E: alloc, copy)
+ }
+ catch(...)
+ {
+ // NOTE: exception-safety
+ // if the insert fails above, the element won't be stored in the tree, so delete it
- // push new child node
- rtree::elements(n).push_back(base::m_element);
+ rtree::visitors::destroy<Value, Options, Translator, Box, Allocators> del_v(base::m_element.second, base::m_allocators);
+ rtree::apply_visitor(del_v, *base::m_element.second);
+
+ throw; // RETHROW
+ }
// first insert
if ( 0 == InsertIndex )
{
- base::handle_possible_reinsert_or_split_of_root(n);
+ base::handle_possible_reinsert_or_split_of_root(n); // MAY THROW (E: alloc, copy, N: alloc)
}
// not the first insert
else
{
- base::handle_possible_split(n);
+ base::handle_possible_split(n); // MAY THROW (E: alloc, N: alloc)
}
}
@@ -292,17 +322,17 @@
inline void operator()(internal_node & n)
{
- BOOST_GEOMETRY_INDEX_ASSERT(base::m_traverse_data.current_level < base::m_leafs_level, "unexpected level");
- BOOST_GEOMETRY_INDEX_ASSERT(base::m_traverse_data.current_level < base::m_level, "unexpected level");
+ BOOST_GEOMETRY_INDEX_ASSERT(base::m_traverse_data.current_level < base::m_leafs_level, "unexpected level");
+ BOOST_GEOMETRY_INDEX_ASSERT(base::m_traverse_data.current_level < base::m_level, "unexpected level");
// next traversing step
- base::traverse(*this, n);
+ base::traverse(*this, n); // MAY THROW (V, E: alloc, copy, N: alloc)
- BOOST_GEOMETRY_INDEX_ASSERT(0 < base::m_level, "illegal level value, level shouldn't be the root level for 0 < InsertIndex");
+ BOOST_GEOMETRY_INDEX_ASSERT(0 < base::m_level, "illegal level value, level shouldn't be the root level for 0 < InsertIndex");
if ( base::m_traverse_data.current_level == base::m_level - 1 )
{
- base::handle_possible_reinsert_or_split_of_root(n);
+ base::handle_possible_reinsert_or_split_of_root(n); // MAY THROW (E: alloc, copy, N: alloc)
}
base::recalculate_aabb_if_necessary(n);
@@ -310,15 +340,15 @@
inline void operator()(leaf & n)
{
- BOOST_GEOMETRY_INDEX_ASSERT(base::m_traverse_data.current_level == base::m_leafs_level,
- "unexpected level");
- BOOST_GEOMETRY_INDEX_ASSERT(base::m_level == base::m_traverse_data.current_level ||
- base::m_level == (std::numeric_limits<size_t>::max)(),
- "unexpected level");
+ BOOST_GEOMETRY_INDEX_ASSERT(base::m_traverse_data.current_level == base::m_leafs_level,
+ "unexpected level");
+ BOOST_GEOMETRY_INDEX_ASSERT(base::m_level == base::m_traverse_data.current_level ||
+ base::m_level == (std::numeric_limits<size_t>::max)(),
+ "unexpected level");
- rtree::elements(n).push_back(base::m_element);
+ rtree::elements(n).push_back(base::m_element); // MAY THROW, STRONG (V: alloc, copy)
- base::handle_possible_split(n);
+ base::handle_possible_split(n); // MAY THROW (V: alloc, copy, N: alloc)
}
};
@@ -345,30 +375,30 @@
inline void operator()(internal_node & n)
{
- BOOST_GEOMETRY_INDEX_ASSERT(base::m_traverse_data.current_level < base::m_leafs_level,
- "unexpected level");
- BOOST_GEOMETRY_INDEX_ASSERT(base::m_traverse_data.current_level < base::m_level,
- "unexpected level");
-
+ BOOST_GEOMETRY_INDEX_ASSERT(base::m_traverse_data.current_level < base::m_leafs_level,
+ "unexpected level");
+ BOOST_GEOMETRY_INDEX_ASSERT(base::m_traverse_data.current_level < base::m_level,
+ "unexpected level");
+
// next traversing step
- base::traverse(*this, n);
+ base::traverse(*this, n); // MAY THROW (V: alloc, copy, N: alloc)
base::recalculate_aabb_if_necessary(n);
}
inline void operator()(leaf & n)
{
- BOOST_GEOMETRY_INDEX_ASSERT(base::m_traverse_data.current_level == base::m_leafs_level,
- "unexpected level");
- BOOST_GEOMETRY_INDEX_ASSERT(base::m_level == base::m_traverse_data.current_level ||
- base::m_level == (std::numeric_limits<size_t>::max)(),
- "unexpected level");
+ BOOST_GEOMETRY_INDEX_ASSERT(base::m_traverse_data.current_level == base::m_leafs_level,
+ "unexpected level");
+ BOOST_GEOMETRY_INDEX_ASSERT(base::m_level == base::m_traverse_data.current_level ||
+ base::m_level == (std::numeric_limits<size_t>::max)(),
+ "unexpected level");
- rtree::elements(n).push_back(base::m_element);
+ rtree::elements(n).push_back(base::m_element); // MAY THROW, STRONG (V: alloc, copy)
- base::handle_possible_reinsert_or_split_of_root(n);
-
- base::recalculate_aabb_if_necessary(n);
+ base::handle_possible_reinsert_or_split_of_root(n); // MAY THROW (V: alloc, copy, N: alloc)
+
+ base::recalculate_aabb_if_necessary(n);
}
};
@@ -377,91 +407,104 @@
} // namespace detail
// R*-tree insert visitor
+// After passing the Element to insert visitor the Element is managed by the tree
+// I.e. one should not delete the node passed to the insert visitor after exception is thrown
+// because this visitor may delete it
template <typename Element, typename Value, typename Options, typename Translator, typename Box, typename Allocators>
class insert<Element, Value, Options, Translator, Box, Allocators, insert_reinsert_tag>
- : public rtree::visitor<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag, false>::type
- , index::nonassignable
+ : public rtree::visitor<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag, false>::type
+ , index::nonassignable
{
typedef typename Options::parameters_type parameters_type;
- typedef typename rtree::node<Value, parameters_type, Box, Allocators, typename Options::node_tag>::type node;
- typedef typename rtree::internal_node<Value, parameters_type, Box, Allocators, typename Options::node_tag>::type internal_node;
- typedef typename rtree::leaf<Value, parameters_type, Box, Allocators, typename Options::node_tag>::type leaf;
+ typedef typename rtree::node<Value, parameters_type, Box, Allocators, typename Options::node_tag>::type node;
+ typedef typename rtree::internal_node<Value, parameters_type, Box, Allocators, typename Options::node_tag>::type internal_node;
+ typedef typename rtree::leaf<Value, parameters_type, Box, Allocators, typename Options::node_tag>::type leaf;
public:
- inline insert(node* & root,
- size_t & leafs_level,
- Element const& element,
+ inline insert(node* & root,
+ size_t & leafs_level,
+ Element const& element,
parameters_type const& parameters,
- Translator const& translator,
+ Translator const& translator,
Allocators & allocators,
- size_t relative_level = 0)
- : m_root(root), m_leafs_level(leafs_level), m_element(element)
- , m_parameters(parameters), m_translator(translator)
+ size_t relative_level = 0)
+ : m_root(root), m_leafs_level(leafs_level), m_element(element)
+ , m_parameters(parameters), m_translator(translator)
, m_relative_level(relative_level), m_allocators(allocators)
- {}
+ {}
+
+ inline void operator()(internal_node & BOOST_GEOMETRY_INDEX_ASSERT_UNUSED_PARAM(n))
+ {
+ BOOST_GEOMETRY_INDEX_ASSERT(&n == rtree::get<internal_node>(m_root), "current node should be the root");
+
+ detail::rstar::level_insert<0, Element, Value, Options, Translator, Box, Allocators> lins_v(
+ m_root, m_leafs_level, m_element, m_parameters, m_translator, m_allocators, m_relative_level);
+
+ rtree::apply_visitor(lins_v, *m_root); // MAY THROW (V, E: alloc, copy, N: alloc)
+
+ if ( !lins_v.result_elements.empty() )
+ {
+ recursive_reinsert(lins_v.result_elements, lins_v.result_relative_level); // MAY THROW (V, E: alloc, copy, N: alloc)
+ }
+ }
- inline void operator()(internal_node & BOOST_GEOMETRY_INDEX_ASSERT_UNUSED_PARAM(n))
- {
- BOOST_GEOMETRY_INDEX_ASSERT(&n == rtree::get<internal_node>(m_root), "current node should be the root");
-
- detail::rstar::level_insert<0, Element, Value, Options, Translator, Box, Allocators> lins_v(
- m_root, m_leafs_level, m_element, m_parameters, m_translator, m_allocators, m_relative_level);
-
- rtree::apply_visitor(lins_v, *m_root);
-
- if ( !lins_v.result_elements.empty() )
- {
- recursive_reinsert(lins_v.result_elements, lins_v.result_relative_level);
- }
- }
-
- inline void operator()(leaf & BOOST_GEOMETRY_INDEX_ASSERT_UNUSED_PARAM(n))
- {
- BOOST_GEOMETRY_INDEX_ASSERT(&n == rtree::get<leaf>(m_root), "current node should be the root");
-
- detail::rstar::level_insert<0, Element, Value, Options, Translator, Box, Allocators> lins_v(
- m_root, m_leafs_level, m_element, m_parameters, m_translator, m_allocators, m_relative_level);
-
- rtree::apply_visitor(lins_v, *m_root);
-
- // we're in the root, so root should be split and there should be no elements to reinsert
- assert(lins_v.result_elements.empty());
- }
+ inline void operator()(leaf & BOOST_GEOMETRY_INDEX_ASSERT_UNUSED_PARAM(n))
+ {
+ BOOST_GEOMETRY_INDEX_ASSERT(&n == rtree::get<leaf>(m_root), "current node should be the root");
+
+ detail::rstar::level_insert<0, Element, Value, Options, Translator, Box, Allocators> lins_v(
+ m_root, m_leafs_level, m_element, m_parameters, m_translator, m_allocators, m_relative_level);
+
+ rtree::apply_visitor(lins_v, *m_root); // MAY THROW (V, E: alloc, copy, N: alloc)
+
+ // we're in the root, so root should be split and there should be no elements to reinsert
+ BOOST_GEOMETRY_INDEX_ASSERT(lins_v.result_elements.empty(), "unexpected state");
+ }
private:
- template <typename Elements>
- inline void recursive_reinsert(Elements const& elements, size_t relative_level)
- {
- typedef typename Elements::value_type element_type;
-
- // reinsert children starting from the minimum distance
- for ( typename Elements::const_reverse_iterator it = elements.rbegin();
- it != elements.rend(); ++it)
- {
- detail::rstar::level_insert<1, element_type, Value, Options, Translator, Box, Allocators> lins_v(
- m_root, m_leafs_level, *it, m_parameters, m_translator, m_allocators, relative_level);
-
- rtree::apply_visitor(lins_v, *m_root);
-
- assert(relative_level + 1 == lins_v.result_relative_level);
-
- // non-root relative level
- if ( lins_v.result_relative_level < m_leafs_level && !lins_v.result_elements.empty())
- {
- recursive_reinsert(lins_v.result_elements, lins_v.result_relative_level);
- }
- }
- }
-
- node* & m_root;
- size_t & m_leafs_level;
- Element const& m_element;
+ template <typename Elements>
+ inline void recursive_reinsert(Elements & elements, size_t relative_level)
+ {
+ typedef typename Elements::value_type element_type;
+
+ // reinsert children starting from the minimum distance
+ typename Elements::reverse_iterator it = elements.rbegin();
+ for ( ; it != elements.rend() ; ++it)
+ {
+ detail::rstar::level_insert<1, element_type, Value, Options, Translator, Box, Allocators> lins_v(
+ m_root, m_leafs_level, *it, m_parameters, m_translator, m_allocators, relative_level);
+
+ try
+ {
+ rtree::apply_visitor(lins_v, *m_root); // MAY THROW (V, E: alloc, copy, N: alloc)
+ }
+ catch(...)
+ {
+ ++it;
+ for ( ; it != elements.rend() ; ++it)
+ rtree::destroy_element<Value, Options, Translator, Box, Allocators>::apply(*it, m_allocators);
+ throw; // RETHROW
+ }
+
+ BOOST_GEOMETRY_INDEX_ASSERT(relative_level + 1 == lins_v.result_relative_level, "unexpected level");
+
+ // non-root relative level
+ if ( lins_v.result_relative_level < m_leafs_level && !lins_v.result_elements.empty())
+ {
+ recursive_reinsert(lins_v.result_elements, lins_v.result_relative_level); // MAY THROW (V, E: alloc, copy, N: alloc)
+ }
+ }
+ }
+
+ node* & m_root;
+ size_t & m_leafs_level;
+ Element const& m_element;
parameters_type const& m_parameters;
- Translator const& m_translator;
+ Translator const& m_translator;
- size_t m_relative_level;
+ size_t m_relative_level;
Allocators m_allocators;
};
Modified: sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/rstar/redistribute_elements.hpp
==============================================================================
--- sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/rstar/redistribute_elements.hpp (original)
+++ sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/rstar/redistribute_elements.hpp 2012-11-21 10:47:51 EST (Wed, 21 Nov 2012)
@@ -68,11 +68,11 @@
BOOST_GEOMETRY_INDEX_ASSERT(elements.size() == parameters.get_max_elements() + 1, "wrong number of elements");
// copy elements
- Elements elements_copy = elements;
+ Elements elements_copy(elements); // MAY THROW, STRONG (alloc, copy)
// sort elements
element_axis_corner_less<element_type, Translator, Corner, AxisIndex> elements_less(translator);
- std::sort(elements_copy.begin(), elements_copy.end(), elements_less);
+ std::sort(elements_copy.begin(), elements_copy.end(), elements_less); // MAY THROW, BASIC (copy)
// init outputs
choosen_index = parameters.get_min_elements();
@@ -135,7 +135,7 @@
choose_split_axis_and_index_for_corner<Parameters, Box, min_corner, AxisIndex>::
apply(elements, index1,
som1, ovl1, con1,
- parameters, translator);
+ parameters, translator); // MAY THROW, STRONG
size_t index2 = 0;
margin_type som2 = 0;
@@ -145,7 +145,7 @@
choose_split_axis_and_index_for_corner<Parameters, Box, max_corner, AxisIndex>::
apply(elements, index2,
som2, ovl2, con2,
- parameters, translator);
+ parameters, translator); // MAY THROW, STRONG
sum_of_margins = som1 + som2;
@@ -185,7 +185,7 @@
choose_split_axis_and_index_for_corner<Parameters, Box, min_corner, AxisIndex>::
apply(elements, choosen_index,
sum_of_margins, smallest_overlap, smallest_content,
- parameters, translator);
+ parameters, translator); // MAY THROW, STRONG
choosen_corner = min_corner;
}
@@ -215,7 +215,7 @@
choose_split_axis_and_index<Parameters, Box, Dimension - 1>::
apply(elements, choosen_axis, choosen_corner, choosen_index,
smallest_sum_of_margins, smallest_overlap, smallest_content,
- parameters, translator);
+ parameters, translator); // MAY THROW, STRONG
margin_type sum_of_margins = 0;
@@ -230,7 +230,7 @@
Box,
Dimension - 1,
typename index::traits::tag<element_indexable_type>::type
- >::apply(elements, corner, index, sum_of_margins, overlap_val, content_val, parameters, translator);
+ >::apply(elements, corner, index, sum_of_margins, overlap_val, content_val, parameters, translator); // MAY THROW, STRONG
if ( sum_of_margins < smallest_sum_of_margins )
{
@@ -270,7 +270,7 @@
Box,
0,
typename index::traits::tag<element_indexable_type>::type
- >::apply(elements, choosen_corner, choosen_index, smallest_sum_of_margins, smallest_overlap, smallest_content, parameters, translator);
+ >::apply(elements, choosen_corner, choosen_index, smallest_sum_of_margins, smallest_overlap, smallest_content, parameters, translator); // MAY THROW
}
};
@@ -284,7 +284,7 @@
{
if ( axis < Dimension - 1 )
{
- partial_sort<Corner, Dimension - 1>::apply(elements, axis, index, tr);
+ partial_sort<Corner, Dimension - 1>::apply(elements, axis, index, tr); // MAY THROW, BASIC (copy)
}
else
{
@@ -292,7 +292,7 @@
typedef typename Elements::value_type element_type;
element_axis_corner_less<element_type, Translator, Corner, Dimension - 1> less(tr);
- std::partial_sort(elements.begin(), elements.begin() + index, elements.end(), less);
+ std::partial_sort(elements.begin(), elements.begin() + index, elements.end(), less); // MAY THROW, BASIC (copy)
}
}
};
@@ -307,7 +307,7 @@
typedef typename Elements::value_type element_type;
element_axis_corner_less<element_type, Translator, Corner, 0> less(tr);
- std::partial_sort(elements.begin(), elements.begin() + index, elements.end(), less);
+ std::partial_sort(elements.begin(), elements.begin() + index, elements.end(), less); // MAY THROW, BASIC (copy)
}
};
@@ -334,7 +334,8 @@
Box & box1,
Box & box2,
parameters_type const& parameters,
- Translator const& translator)
+ Translator const& translator,
+ Allocators & allocators)
{
typedef typename rtree::elements_type<Node>::type elements_type;
@@ -348,11 +349,14 @@
content_type smallest_overlap = (std::numeric_limits<content_type>::max)();
content_type smallest_content = (std::numeric_limits<content_type>::max)();
- rstar::choose_split_axis_and_index<typename Options::parameters_type, Box, index::traits::dimension<Box>::value>::
- apply(elements1,
- split_axis, split_corner, split_index,
- smallest_sum_of_margins, smallest_overlap, smallest_content,
- parameters, translator);
+ rstar::choose_split_axis_and_index<
+ typename Options::parameters_type,
+ Box,
+ index::traits::dimension<Box>::value
+ >::apply(elements1,
+ split_axis, split_corner, split_index,
+ smallest_sum_of_margins, smallest_overlap, smallest_content,
+ parameters, translator); // MAY THROW, STRONG
// TODO: awulkiew - get rid of following static_casts?
@@ -360,20 +364,41 @@
BOOST_GEOMETRY_INDEX_ASSERT(split_corner == static_cast<size_t>(min_corner) || split_corner == static_cast<size_t>(max_corner), "unexpected value");
BOOST_GEOMETRY_INDEX_ASSERT(parameters.get_min_elements() <= split_index && split_index <= parameters.get_max_elements() - parameters.get_min_elements() + 1, "unexpected value");
+ // copy original elements
+ elements_type elements_copy(elements1); // MAY THROW, STRONG
+ elements_type elements_backup(elements1); // MAY THROW, STRONG
+
// TODO: awulkiew - check if std::partial_sort produces the same result as std::sort
if ( split_corner == static_cast<size_t>(min_corner) )
- rstar::partial_sort<min_corner, dimension>::apply(elements1, split_axis, split_index, translator);
+ rstar::partial_sort<min_corner, dimension>
+ ::apply(elements_copy, split_axis, split_index, translator); // MAY THROW, BASIC (copy)
else
- rstar::partial_sort<max_corner, dimension>::apply(elements1, split_axis, split_index, translator);
+ rstar::partial_sort<max_corner, dimension>
+ ::apply(elements_copy, split_axis, split_index, translator); // MAY THROW, BASIC (copy)
- // copy elements to node 2 and remove from node 1
- elements2.resize(parameters.get_max_elements() + 1 - split_index);
- std::copy(elements1.begin() + split_index, elements1.end(), elements2.begin());
- elements1.resize(split_index);
-
- // calculate boxes
- box1 = rtree::elements_box<Box>(elements1.begin(), elements1.end(), translator);
- box2 = rtree::elements_box<Box>(elements2.begin(), elements2.end(), translator);
+ try
+ {
+ // copy elements to nodes
+ elements1.resize(split_index); // SHOULDN'T THROW
+ std::copy(elements_copy.begin(), elements_copy.begin() + split_index, elements1.begin()); // MAY THROW, BASIC
+ elements2.resize(parameters.get_max_elements() + 1 - split_index); // MAY THROW, STRONG
+ std::copy(elements_copy.begin() + split_index, elements_copy.end(), elements2.begin()); // MAY THROW, BASIC
+
+ // calculate boxes
+ box1 = rtree::elements_box<Box>(elements1.begin(), elements1.end(), translator);
+ box2 = rtree::elements_box<Box>(elements2.begin(), elements2.end(), translator);
+ }
+ catch(...)
+ {
+ //elements_copy.clear();
+ elements1.clear();
+ elements2.clear();
+
+ rtree::destroy_elements<Value, Options, Translator, Box, Allocators>::apply(elements_backup, allocators);
+ //elements_backup.clear();
+
+ throw; // RETHROW, BASIC
+ }
}
};
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-21 10:47:51 EST (Wed, 21 Nov 2012)
@@ -25,8 +25,8 @@
#include <boost/geometry/extensions/index/translator/translator.hpp>
#include <boost/geometry/extensions/index/rtree/options.hpp>
-#include <boost/geometry/extensions/index/rtree/predicates.hpp>
-#include <boost/geometry/extensions/index/rtree/filters.hpp>
+#include <boost/geometry/extensions/index/predicates.hpp>
+#include <boost/geometry/extensions/index/rtree/adaptors.hpp>
#include <boost/geometry/extensions/index/rtree/node/node.hpp>
@@ -45,6 +45,8 @@
#include <boost/geometry/extensions/index/rtree/rstar/rstar.hpp>
//#include <boost/geometry/extensions/index/rtree/kmeans/kmeans.hpp>
+// TODO change the name to bounding_tree
+
namespace boost { namespace geometry { namespace index {
/*!
@@ -78,42 +80,50 @@
public:
typedef Value value_type;
+ typedef Parameters parameters_type;
typedef Translator translator_type;
+ typedef Allocator allocator_type;
+ typedef typename allocator_type::size_type size_type;
+
typedef typename translator::indexable_type<Translator>::type indexable_type;
typedef typename index::default_box_type<indexable_type>::type box_type;
+#if !defined(BOOST_GEOMETRY_INDEX_ENABLE_DEBUG_INTERFACE)
+private:
+#endif
typedef typename detail::rtree::options_type<Parameters>::type options_type;
typedef typename options_type::node_tag node_tag;
-
- typedef Allocator allocator_type;
typedef detail::rtree::allocators<allocator_type, value_type, typename options_type::parameters_type, box_type, node_tag> allocators_type;
- typedef typename allocators_type::size_type size_type;
typedef typename detail::rtree::node<value_type, typename options_type::parameters_type, box_type, allocators_type, node_tag>::type node;
typedef typename detail::rtree::internal_node<value_type, typename options_type::parameters_type, box_type, allocators_type, node_tag>::type internal_node;
typedef typename detail::rtree::leaf<value_type, typename options_type::parameters_type, box_type, allocators_type, node_tag>::type leaf;
+public:
/*!
The constructor.
+ \note Exception-safety: nothrow (if translator has nonthrowing copy ctor),
+ strong (if translator has throwing copy ctor)
+
\param parameters The parameters object.
\param translator The translator object.
\param allocator The allocator object.
*/
inline explicit rtree(Parameters parameters = Parameters(), translator_type const& translator = translator_type(), Allocator allocator = Allocator())
- : m_values_count(0)
- , m_root(0)
- , m_leafs_level(0)
+ : m_translator(translator) // MAY THROW (copy)
, m_parameters(parameters)
- , m_translator(translator)
, m_allocators(allocator)
- {
- this->create();
- }
+ , m_values_count(0)
+ , m_leafs_level(0)
+ , m_root(0)
+ {}
/*!
The constructor.
+ \note Exception-safety: strong
+
\param first The beginning of the range of Values.
\param last The end of the range of Values.
\param parameters The parameters object.
@@ -122,147 +132,134 @@
*/
template<typename Iterator>
inline rtree(Iterator first, Iterator last, Parameters parameters = Parameters(), translator_type const& translator = translator_type(), Allocator allocator = std::allocator<value_type>())
- : m_values_count(0)
- , m_root(0)
- , m_leafs_level(0)
+ : m_translator(translator) // MAY THROW (copy)
, m_parameters(parameters)
- , m_translator(translator)
, m_allocators(allocator)
+ , m_values_count(0)
+ , m_leafs_level(0)
+ , m_root(0)
{
- this->create();
- this->insert(first, last);
+ try
+ {
+ this->insert(first, last);
+ }
+ catch(...)
+ {
+ this->raw_destroy(*this, true);
+ throw;
+ }
}
/*!
The destructor.
+
+ \note Exception-safety: nothrow
*/
inline ~rtree()
{
- if ( !this->empty() )
- this->destroy(*this);
+ this->raw_destroy(*this, true);
}
/*!
The copy constructor.
+
+ \note Exception-safety: strong
*/
inline rtree(rtree const& src)
- : m_parameters(src.m_parameters)
- , m_translator(src.m_translator)
+ : m_translator(src.m_translator) // MAY THROW (copy)
+ , m_parameters(src.m_parameters)
, m_allocators(src.m_allocators)
+ , m_values_count(0)
+ , m_leafs_level(0)
+ , m_root(0)
{
//TODO use Boost.Container allocator_traits_type::select_on_container_copy_construction()
- try
- {
- this->copy(src, *this);
- }
- catch(...)
- {
- this->destroy(*this);
- throw;
- }
+ this->raw_copy(src, *this, m_allocators);
}
/*!
The copy constructor.
+
+ \note Exception-safety: strong
*/
inline rtree(rtree const& src, Allocator const& allocator)
- : m_parameters(src.m_parameters)
- , m_translator(src.m_translator)
+ : m_translator(src.m_translator) // MAY THROW (copy)
+ , m_parameters(src.m_parameters)
, m_allocators(allocator)
+ , m_values_count(0)
+ , m_leafs_level(0)
+ , m_root(0)
{
- try
- {
- this->copy(src, *this);
- }
- catch(...)
- {
- this->destroy(*this);
- throw;
- }
+ this->raw_copy(src, *this, m_allocators);
}
/*!
The moving constructor.
+
+ \note Exception-safety: nothrow (if translator has nonthrowing copy ctor),
+ strong (if translator has throwing copy ctor)
*/
inline rtree(BOOST_RV_REF(rtree) src)
- : m_values_count(src.m_values_count)
- , m_root(src.m_root)
- , m_leafs_level(src.m_leafs_level)
+ : m_translator(src.m_translator) // MAY THROW (copy)
, m_parameters(src.m_parameters)
- , m_translator(src.m_translator)
, m_allocators(src.m_allocators)
+ , m_values_count(src.m_values_count)
+ , m_leafs_level(src.m_leafs_level)
+ , m_root(src.m_root)
{
src.m_values_count = 0;
- src.m_root = 0;
src.m_leafs_level = 0;
+ src.m_root = 0;
}
/*!
The assignment operator.
+
+ \note Exception-safety: strong
*/
inline rtree & operator=(BOOST_COPY_ASSIGN_REF(rtree) src)
{
if ( this == &src )
return *this;
- if ( !this->empty() )
- this->destroy(*this);
-
- m_parameters = src.m_parameters;
- m_translator = src.m_translator;
//TODO use Boost.Container allocator_traits_type::propagate_on_container_move_assignment
- //m_allocators = src.m_allocators;
- try
- {
- this->copy(src, *this);
- }
- catch(...)
- {
- this->destroy(*this);
- throw;
- }
+ this->raw_copy(src, *this, m_allocators);
return *this;
}
/*!
The moving assignment.
+
+ \note Exception-safety: nothrow (if allocators are equal and translator has nonthrowing copy ctor),
+ strong (if allocators aren't equal or translator has throwing copy ctor)
*/
inline rtree & operator=(BOOST_RV_REF(rtree) src)
{
if ( this == &src )
return *this;
- if ( !this->empty() )
- this->destroy(*this);
-
- m_parameters = src.m_parameters;
- m_translator = src.m_translator;
//TODO use Boost.Container allocator_traits_type::propagate_on_container_move_assignment
- //m_allocators = src.m_allocators;
if ( m_allocators.allocator == src.m_allocators.allocator )
{
+ m_translator = src.m_translator; // MAY THROW (copy)
+ m_parameters = src.m_parameters;
+ //m_allocators = src.m_allocators;
+
m_values_count = src.m_values_count;
- src.m_values_count = 0;
- m_root = src.m_root;
- src.m_root = 0;
m_leafs_level = src.m_leafs_level;
+ m_root = src.m_root;
+
+ src.m_values_count = 0;
src.m_leafs_level = 0;
+ src.m_root = 0;
}
else
{
- try
- {
- this->copy(src, *this);
- }
- catch(...)
- {
- this->destroy(*this);
- throw;
- }
+ this->raw_copy(src, *this, m_allocators);
}
return *this;
@@ -271,83 +268,53 @@
/*!
Insert a value to the index.
+ \note Exception-safety: basic
+
\param value The value which will be stored in the container.
*/
inline void insert(value_type const& value)
{
- BOOST_GEOMETRY_INDEX_ASSERT(index::is_valid(m_translator(value)), "Indexable is invalid");
-
- try
- {
- detail::rtree::visitors::insert<
- value_type,
- value_type,
- options_type,
- translator_type,
- box_type,
- allocators_type,
- typename options_type::insert_tag
- > insert_v(m_root, m_leafs_level, value, m_parameters, m_translator, m_allocators);
-
- detail::rtree::apply_visitor(insert_v, *m_root);
+ if ( !m_root )
+ this->raw_create();
- ++m_values_count;
- }
- catch(...)
- {
- this->destroy(*this);
- throw;
- }
+ this->raw_insert(value);
}
/*!
Insert a range of values to the index.
+ \note Exception-safety: basic
+
\param first The beginning of the range of values.
\param last The end of the range of values.
*/
template <typename Iterator>
inline void insert(Iterator first, Iterator last)
{
+ if ( !m_root )
+ this->raw_create();
+
for ( ; first != last ; ++first )
- this->insert(*first);
+ this->raw_insert(*first);
}
/*!
Remove the value from the container.
+ \note Exception-safety: basic
+
\param value The value which will be removed from the container.
*/
inline void remove(value_type const& value)
{
- // TODO: awulkiew - assert for correct value (indexable) ?
-
- BOOST_GEOMETRY_INDEX_ASSERT(0 < m_values_count, "can't remove, there are no elements in the rtree");
-
- try
- {
- detail::rtree::visitors::remove<
- value_type,
- options_type,
- translator_type,
- box_type,
- allocators_type
- > remove_v(m_root, m_leafs_level, value, m_parameters, m_translator, m_allocators);
-
- detail::rtree::apply_visitor(remove_v, *m_root);
-
- --m_values_count;
- }
- catch(...)
- {
- this->destroy(*this);
- throw;
- }
+ this->raw_remove(value);
}
/*!
Remove the range of values from the container.
+ \note Exception-safety: basic
+
\param first The beginning of the range of values.
\param last The end of the range of values.
*/
@@ -355,12 +322,14 @@
inline void remove(Iterator first, Iterator last)
{
for ( ; first != last ; ++first )
- this->remove(*first);
+ this->raw_remove(*first);
}
/*!
Find values meeting spatial predicates, e.g. intersecting some box.
+ \note Exception-safety: strong
+
\param pred The spatial predicates. May be a Geometry (in this case default
predicate - intersects is used) or generated by bgi::covered_by(geometry),
bgi::disjoint(geometry), bgi::intersects(geometry), bgi::overlaps(geometry),
@@ -375,7 +344,7 @@
\return The number of values found.
*/
template <typename Predicates, typename OutIter>
- inline size_type query(Predicates const& pred, OutIter out_it) const
+ inline size_type spatial_query(Predicates const& pred, OutIter out_it) const
{
detail::rtree::visitors::query<value_type, options_type, translator_type, box_type, allocators_type, Predicates, OutIter>
find_v(m_translator, pred, out_it);
@@ -388,6 +357,8 @@
/*!
Find one value meeting distances predicates, e.g. nearest to some point.
+ \note Exception-safety: strong
+
\param dpred The distances predicates. May be a Point. This is default case where Value which
nearest point is closest to Point is returned. May be a PointRelation which define
how distance to Value is calculated. This may be generated by bgi::to_nearest(Point),
@@ -403,15 +374,17 @@
\return The number of values found.
*/
template <typename DistancesPredicates>
- inline size_type nearest(DistancesPredicates const& dpred, value_type & v) const
+ inline size_type nearest_query(DistancesPredicates const& dpred, value_type & v) const
{
- return nearest_one(dpred, detail::empty(), v);
+ return raw_nearest_one(dpred, detail::empty(), v);
}
/*!
Find one value meeting distances predicates and spatial predicates,
e.g. nearest to some point and intersecting some box.
+ \note Exception-safety: strong
+
\param dpred The distances predicates. May be a Point. This is default case where Value which
nearest point is closest to Point is returned. May be a PointRelation which define
how distance to Value is calculated. This may be generated by bgi::to_nearest(Point),
@@ -433,14 +406,16 @@
\return The number of values found.
*/
template <typename DistancesPredicates, typename Predicates>
- inline size_type nearest(DistancesPredicates const& dpred, Predicates const& pred, value_type & v) const
+ inline size_type nearest_query(DistancesPredicates const& dpred, Predicates const& pred, value_type & v) const
{
- return nearest_one(dpred, pred, v);
+ return raw_nearest_one(dpred, pred, v);
}
/*!
Find k values meeting distances predicates, e.g. k nearest values to some point.
+ \note Exception-safety: strong
+
\param dpred The distances predicates. May be a Point. This is default case where Value which
nearest point is closest to Point is returned. May be a PointRelation which define
how distance to Value is calculated. This may be generated by bgi::to_nearest(Point),
@@ -456,15 +431,17 @@
\return The number of values found.
*/
template <typename DistancesPredicates, typename OutIter>
- inline size_type nearest(DistancesPredicates const& dpred, size_t k, OutIter out_it) const
+ inline size_type nearest_query(DistancesPredicates const& dpred, size_t k, OutIter out_it) const
{
- return nearest_k(dpred, k, detail::empty(), out_it);
+ return raw_nearest_k(dpred, k, detail::empty(), out_it);
}
/*!
Find k values meeting distances predicates and spatial predicates,
e.g. k nearest values to some point and intersecting some box.
+ \note Exception-safety: strong
+
\param dpred The distances predicates. May be a Point. This is default case where Value which
nearest point is closest to Point is returned. May be a PointRelation which define
how distance to Value is calculated. This may be generated by bgi::to_nearest(Point),
@@ -487,14 +464,16 @@
\return The number of values found.
*/
template <typename DistancesPredicates, typename Predicates, typename OutIter>
- inline size_type nearest(DistancesPredicates const& dpred, size_t k, Predicates const& pred, OutIter out_it) const
+ inline size_type nearest_query(DistancesPredicates const& dpred, size_t k, Predicates const& pred, OutIter out_it) const
{
- return nearest_k(dpred, k, pred, out_it);
+ return raw_nearest_k(dpred, k, pred, out_it);
}
/*!
Returns the number of stored values.
+ \note Exception-safety: nothrow
+
\return The number of stored values.
*/
inline size_type size() const
@@ -505,6 +484,8 @@
/*!
Query if the container is empty.
+ \note Exception-safety: nothrow
+
\return true if the container is empty.
*/
inline bool empty() const
@@ -514,17 +495,20 @@
/*!
Removes all values stored in the container.
+
+ \note Exception-safety: nothrow.
*/
inline void clear()
{
- this->destroy(*this);
- this->create();
+ this->raw_destroy(*this, false);
}
/*!
Returns the box containing all values stored in the container.
If the container is empty the result of geometry::assign_inverse() is returned.
+ \note Exception-safety: nothrow.
+
\return The box containing all values stored in the container or an invalid box if
there are no values in the container.
*/
@@ -546,8 +530,34 @@
}
/*!
+ Returns parameters.
+
+ \note Exception-safety: nothrow.
+
+ \return The parameters object.
+ */
+ inline parameters_type const& parameters() const
+ {
+ return m_parameters;
+ }
+
+ /*!
+ Returns the translator object.
+
+ \note Exception-safety: nothrow.
+
+ \return The translator object.
+ */
+ inline translator_type const& translator() const
+ {
+ return m_translator;
+ }
+
+ /*!
Returns allocator used by the rtree.
+ \note Exception-safety: nothrow
+
\return The allocator.
*/
allocator_type get_allocator() const
@@ -555,10 +565,15 @@
return m_allocators.allocator;
}
+#if !defined(BOOST_GEOMETRY_INDEX_ENABLE_DEBUG_INTERFACE)
+private:
+#endif
/*!
Apply a visitor to the nodes structure in order to perform some operator.
This function is not a part of the 'official' interface. However it makes
- possible to e.g. draw the tree structure.
+ possible e.g. to pass a visitor drawing the tree structure.
+
+ \note Exception-safety: the same as Visitor::operator().
\param visitor The visitor object.
*/
@@ -569,19 +584,10 @@
}
/*!
- Returns the translator object.
+ Returns the number of stored objects. Same as size()
This function is not a part of the 'official' interface.
- \return The translator object.
- */
- inline translator_type const& translator() const
- {
- return m_translator;
- }
-
- /*!
- Returns the number of stored objects. Same as size()
- This function is not a part of the 'official' interface.
+ \note Exception-safety: nothrow
\return The number of stored objects.
*/
@@ -592,7 +598,9 @@
/*!
Returns the depth of the R-tree.
- This function is not a part of the 'official' interface.
+ This function is not a part of the 'official' interface.
+
+ \note Exception-safety: nothrow.
\return The depth of the R-tree.
*/
@@ -603,13 +611,72 @@
private:
/*!
+ Insert a value to the index. Root node must exist.
+
+ \note Exception-safety: basic
+
+ \param value The value which will be stored in the container.
+ */
+ inline void raw_insert(value_type const& value)
+ {
+ BOOST_GEOMETRY_INDEX_ASSERT(m_root, "The root must exist");
+ BOOST_GEOMETRY_INDEX_ASSERT(index::is_valid(m_translator(value)), "Indexable is invalid");
+
+ detail::rtree::visitors::insert<
+ value_type,
+ value_type, options_type, translator_type, box_type, allocators_type,
+ typename options_type::insert_tag
+ > insert_v(m_root, m_leafs_level, value, m_parameters, m_translator, m_allocators);
+
+ detail::rtree::apply_visitor(insert_v, *m_root);
+
+// TODO
+// Think about this: If exception is thrown, may the root be removed?
+// Or it is just cleared?
+
+// TODO
+// If exception is thrown, m_values_count may be invalid
+ ++m_values_count;
+ }
+
+ /*!
+ Remove the value from the container.
+
+ \note Exception-safety: basic
+
+ \param value The value which will be removed from the container.
+ */
+ inline void raw_remove(value_type const& value)
+ {
+ // TODO: awulkiew - assert for correct value (indexable) ?
+ BOOST_GEOMETRY_INDEX_ASSERT(m_root, "The root must exist");
+ BOOST_GEOMETRY_INDEX_ASSERT(0 < m_values_count, "can't remove, there are no elements in the rtree");
+
+ detail::rtree::visitors::remove<
+ value_type, options_type, translator_type, box_type, allocators_type
+ > remove_v(m_root, m_leafs_level, value, m_parameters, m_translator, m_allocators);
+
+ detail::rtree::apply_visitor(remove_v, *m_root);
+
+// TODO
+// Think about this: If exception is thrown, may the root be removed?
+// Or it is just cleared?
+
+// TODO
+// If exception is thrown, m_values_count may be invalid
+ --m_values_count;
+ }
+
+ /*!
Create an empty R-tree i.e. new empty root node and clear other attributes.
+
+ \note Exception-safety: strong.
*/
- inline void create()
+ inline void raw_create()
{
- assert(0 == m_root);
+ BOOST_GEOMETRY_INDEX_ASSERT(0 == m_root, "the tree is already created");
- m_root = detail::rtree::create_node<allocators_type, leaf>::apply(m_allocators);
+ m_root = detail::rtree::create_node<allocators_type, leaf>::apply(m_allocators); // MAY THROW (N: alloc)
m_values_count = 0;
m_leafs_level = 0;
}
@@ -617,14 +684,26 @@
/*!
Destroy the R-tree i.e. all nodes and clear attributes.
+ \note Exception-safety: nothrow.
+
\param t The container which is going to be destroyed.
*/
- inline void destroy(rtree & t)
+ inline void raw_destroy(rtree & t, bool destroy_root = true)
{
- detail::rtree::visitors::destroy<value_type, options_type, translator_type, box_type, allocators_type> del_v(t.m_root, t.m_allocators);
- detail::rtree::apply_visitor(del_v, *t.m_root);
+ if ( t.m_root )
+ {
+ if ( destroy_root )
+ {
+ detail::rtree::visitors::destroy<value_type, options_type, translator_type, box_type, allocators_type> del_v(t.m_root, t.m_allocators);
+ detail::rtree::apply_visitor(del_v, *t.m_root);
+ }
+ else
+ {
+ detail::rtree::clear_node<value_type, options_type, translator_type, box_type, allocators_type>::apply(*t.m_root, t.m_allocators);
+ }
- t.m_root = 0;
+ t.m_root = 0;
+ }
t.m_values_count = 0;
t.m_leafs_level = 0;
}
@@ -632,13 +711,27 @@
/*!
Copy the R-tree i.e. whole nodes structure, values and other attributes.
+ \note Exception-safety: strong.
+
\param src The source R-tree.
\param dst The destination R-tree.
*/
- inline void copy(rtree const& src, rtree & dst) const
+ inline void raw_copy(rtree const& src, rtree & dst, allocators_type & allocators) const
{
- detail::rtree::visitors::copy<value_type, options_type, translator_type, box_type, allocators_type> copy_v(dst.m_allocators);
- detail::rtree::apply_visitor(copy_v, *src.m_root);
+ detail::rtree::visitors::copy<value_type, options_type, translator_type, box_type, allocators_type> copy_v(allocators);
+ detail::rtree::apply_visitor(copy_v, *src.m_root); // MAY THROW (V: alloc, copy, E: alloc, N: alloc)
+
+ if ( dst.m_root )
+ {
+ detail::rtree::visitors::destroy<value_type, options_type, translator_type, box_type, allocators_type> del_v(dst.m_root, dst.m_allocators);
+ detail::rtree::apply_visitor(del_v, *dst.m_root);
+ dst.m_root = 0;
+ }
+
+ dst.m_translator = src.m_translator;
+
+ dst.m_parameters = src.m_parameters;
+ dst.m_allocators = allocators;
dst.m_root = copy_v.result;
dst.m_values_count = src.m_values_count;
@@ -647,9 +740,11 @@
/*!
Find one value meeting distances and spatial predicates.
+
+ \note Exception-safety: strong.
*/
template <typename DistancesPredicates, typename Predicates>
- inline size_type nearest_one(DistancesPredicates const& dpred, Predicates const& pred, value_type & v) const
+ inline size_type raw_nearest_one(DistancesPredicates const& dpred, Predicates const& pred, value_type & v) const
{
typedef typename detail::point_relation<DistancesPredicates>::type point_relation;
typedef typename detail::relation<point_relation>::value_type point_type;
@@ -680,9 +775,11 @@
/*!
Find k values meeting distances and spatial predicates.
+
+ \note Exception-safety: strong.
*/
template <typename DistancesPredicates, typename Predicates, typename OutIter>
- inline size_type nearest_k(DistancesPredicates const& dpred, size_t k, Predicates const& pred, OutIter out_it) const
+ inline size_type raw_nearest_k(DistancesPredicates const& dpred, size_t k, Predicates const& pred, OutIter out_it) const
{
typedef typename detail::point_relation<DistancesPredicates>::type point_relation;
typedef typename detail::relation<point_relation>::value_type point_type;
@@ -711,13 +808,13 @@
return result.get(out_it);
}
- size_type m_values_count;
- node *m_root;
- size_type m_leafs_level;
-
- Parameters m_parameters;
translator_type m_translator;
+ Parameters m_parameters;
allocators_type m_allocators;
+
+ size_type m_values_count;
+ size_type m_leafs_level;
+ node * m_root;
};
/*!
@@ -780,9 +877,9 @@
\return The number of found values.
*/
template <typename Value, typename Options, typename Translator, typename Allocator, typename Predicates, typename OutIter>
-inline size_t query(rtree<Value, Options, Translator, Allocator> const& tree, Predicates const& pred, OutIter out_it)
+inline size_t spatial_query(rtree<Value, Options, Translator, Allocator> const& tree, Predicates const& pred, OutIter out_it)
{
- return tree.query(pred, out_it);
+ return tree.spatial_query(pred, out_it);
}
/*!
@@ -795,9 +892,9 @@
\return The number of found values.
*/
template <typename Value, typename Options, typename Translator, typename Allocator, typename DistancesPredicates>
-inline size_t nearest(rtree<Value, Options, Translator, Allocator> const& tree, DistancesPredicates const& dpred, Value & v)
+inline size_t nearest_query(rtree<Value, Options, Translator, Allocator> const& tree, DistancesPredicates const& dpred, Value & v)
{
- return tree.nearest(dpred, v);
+ return tree.nearest_query(dpred, v);
}
/*!
@@ -811,9 +908,9 @@
\return The number of found values.
*/
template <typename Value, typename Options, typename Translator, typename Allocator, typename DistancesPredicates, typename Predicates>
-inline size_t nearest(rtree<Value, Options, Translator, Allocator> const& tree, DistancesPredicates const& dpred, Predicates const& pred, Value & v)
+inline size_t nearest_query(rtree<Value, Options, Translator, Allocator> const& tree, DistancesPredicates const& dpred, Predicates const& pred, Value & v)
{
- return tree.nearest(dpred, pred, v);
+ return tree.nearest_query(dpred, pred, v);
}
/*!
@@ -827,9 +924,9 @@
\return The number of found values.
*/
template <typename Value, typename Options, typename Translator, typename Allocator, typename DistancesPredicates, typename OutIter>
-inline size_t nearest(rtree<Value, Options, Translator, Allocator> const& tree, DistancesPredicates const& dpred, size_t k, OutIter out_it)
+inline size_t nearest_query(rtree<Value, Options, Translator, Allocator> const& tree, DistancesPredicates const& dpred, size_t k, OutIter out_it)
{
- return tree.nearest(dpred, k, out_it);
+ return tree.nearest_query(dpred, k, out_it);
}
/*!
@@ -844,9 +941,9 @@
\return The number of found values.
*/
template <typename Value, typename Options, typename Translator, typename Allocator, typename DistancesPredicates, typename Predicates, typename OutIter>
-inline size_t nearest(rtree<Value, Options, Translator, Allocator> const& tree, DistancesPredicates const& dpred, size_t k, Predicates const& pred, OutIter out_it)
+inline size_t nearest_query(rtree<Value, Options, Translator, Allocator> const& tree, DistancesPredicates const& dpred, size_t k, Predicates const& pred, OutIter out_it)
{
- return tree.nearest(dpred, k, pred, out_it);
+ return tree.nearest_query(dpred, k, pred, out_it);
}
/*!
Modified: sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/tags.hpp
==============================================================================
--- sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/tags.hpp (original)
+++ sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/tags.hpp 2012-11-21 10:47:51 EST (Wed, 21 Nov 2012)
@@ -1,6 +1,6 @@
// Boost.Geometry Index
//
-// Tags used by the R-tree implementation.
+// Tags used by the R-tree predicates implementation.
//
// Copyright (c) 2011-2012 Adam Wulkiewicz, Lodz, Poland.
//
Modified: sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/are_boxes_ok.hpp
==============================================================================
--- sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/are_boxes_ok.hpp (original)
+++ sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/are_boxes_ok.hpp 2012-11-21 10:47:51 EST (Wed, 21 Nov 2012)
@@ -27,11 +27,11 @@
typedef typename rtree::leaf<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type leaf;
public:
- inline are_boxes_ok(Translator const& tr)
- : result(false), m_tr(tr), m_is_root(true)
+ are_boxes_ok(Translator const& tr, bool exact_match)
+ : result(false), m_tr(tr), m_is_root(true), m_exact_match(exact_match)
{}
- inline void operator()(internal_node const& n)
+ void operator()(internal_node const& n)
{
typedef typename rtree::elements_type<internal_node>::type elements_type;
elements_type const& elements = rtree::elements(n);
@@ -69,10 +69,13 @@
geometry::expand(box_exp, it->first);
}
- result = m_is_root || geometry::equals(box_exp, m_box);
+ if ( m_exact_match )
+ result = m_is_root || geometry::equals(box_exp, m_box);
+ else
+ result = m_is_root || geometry::covered_by(box_exp, m_box);
}
- inline void operator()(leaf const& n)
+ void operator()(leaf const& n)
{
typedef typename rtree::elements_type<leaf>::type elements_type;
elements_type const& elements = rtree::elements(n);
@@ -94,7 +97,10 @@
geometry::expand(box_exp, m_tr(*it));
}
- result = geometry::equals(box_exp, m_box);
+ if ( m_exact_match )
+ result = geometry::equals(box_exp, m_box);
+ else
+ result = geometry::covered_by(box_exp, m_box);
}
else
result = true;
@@ -106,21 +112,24 @@
Translator const& m_tr;
Box m_box;
bool m_is_root;
+ bool m_exact_match;
};
}}} // namespace detail::rtree::visitors
-template <typename Value, typename Options, typename Translator, typename Allocator>
-bool are_boxes_ok(rtree<Value, Options, Translator, Allocator> const& tree)
+template <typename Value, typename Parameters, typename Translator, typename Allocator>
+bool are_boxes_ok(rtree<Value, Parameters, Translator, Allocator> const& tree,
+ bool exact_match = true)
{
- typedef rtree<Value, Options, Translator, Allocator> rt;
+ typedef rtree<Value, Parameters, Translator, Allocator> rt;
+
detail::rtree::visitors::are_boxes_ok<
typename rt::value_type,
typename rt::options_type,
typename rt::translator_type,
typename rt::box_type,
typename rt::allocators_type
- > v(tree.translator());
+ > v(tree.translator(), exact_match);
tree.apply_visitor(v);
Modified: sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/are_levels_ok.hpp
==============================================================================
--- sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/are_levels_ok.hpp (original)
+++ sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/are_levels_ok.hpp 2012-11-21 10:47:51 EST (Wed, 21 Nov 2012)
@@ -88,10 +88,11 @@
}}} // namespace detail::rtree::visitors
-template <typename Value, typename Options, typename Translator, typename Allocator>
-bool are_levels_ok(rtree<Value, Options, Translator, Allocator> const& tree)
+template <typename Value, typename Parameters, typename Translator, typename Allocator>
+bool are_levels_ok(rtree<Value, Parameters, Translator, Allocator> const& tree)
{
- typedef rtree<Value, Options, Translator, Allocator> rt;
+ typedef rtree<Value, Parameters, Translator, Allocator> rt;
+
detail::rtree::visitors::are_levels_ok<
typename rt::value_type,
typename rt::options_type,
Modified: sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/copy.hpp
==============================================================================
--- sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/copy.hpp (original)
+++ sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/copy.hpp 2012-11-21 10:47:51 EST (Wed, 21 Nov 2012)
@@ -27,6 +27,8 @@
typedef typename rtree::internal_node<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type internal_node;
typedef typename rtree::leaf<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type leaf;
+ typedef rtree::node_auto_ptr<Value, Options, Translator, Box, Allocators> node_auto_ptr;
+
explicit inline copy(Allocators & allocators)
: result(0)
, m_allocators(allocators)
@@ -34,7 +36,8 @@
inline void operator()(internal_node & n)
{
- node * new_node = rtree::create_node<Allocators, internal_node>::apply(m_allocators);
+ node * raw_new_node = rtree::create_node<Allocators, internal_node>::apply(m_allocators); // MAY THROW, STRONG (N: alloc)
+ node_auto_ptr new_node(raw_new_node, m_allocators);
typedef typename rtree::elements_type<internal_node>::type elements_type;
elements_type & elements = rtree::elements(n);
@@ -44,18 +47,25 @@
for (typename elements_type::iterator it = elements.begin();
it != elements.end(); ++it)
{
- rtree::apply_visitor(*this, *it->second);
+ rtree::apply_visitor(*this, *it->second); // MAY THROW (V, E: alloc, copy, N: alloc)
+
+ // for exception safety
+ node_auto_ptr auto_result(result, m_allocators);
- elements_dst.push_back( std::make_pair(it->first, result) );
+ elements_dst.push_back( std::make_pair(it->first, result) ); // MAY THROW, STRONG (E: alloc, copy)
+
+ auto_result.release();
}
- result = new_node;
+ result = new_node.get();
+ new_node.release();
}
inline void operator()(leaf & l)
{
- node * new_node = rtree::create_node<Allocators, leaf>::apply(m_allocators);
-
+ node * raw_new_node = rtree::create_node<Allocators, leaf>::apply(m_allocators); // MAY THROW, STRONG (N: alloc)
+ node_auto_ptr new_node(raw_new_node, m_allocators);
+
typedef typename rtree::elements_type<leaf>::type elements_type;
elements_type & elements = rtree::elements(l);
@@ -64,10 +74,11 @@
for (typename elements_type::iterator it = elements.begin();
it != elements.end(); ++it)
{
- elements_dst.push_back(*it);
+ elements_dst.push_back(*it); // MAY THROW, STRONG (V: alloc, copy)
}
- result = new_node;
+ result = new_node.get();
+ new_node.release();
}
node * result;
Modified: sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/destroy.hpp
==============================================================================
--- sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/destroy.hpp (original)
+++ sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/destroy.hpp 2012-11-21 10:47:51 EST (Wed, 21 Nov 2012)
@@ -42,10 +42,11 @@
elements_type & elements = rtree::elements(n);
for (typename elements_type::iterator it = elements.begin();
- it != elements.end(); ++it)
+ it != elements.end(); ++it)
{
m_current_node = it->second;
rtree::apply_visitor(*this, *m_current_node);
+ it->second = 0;
}
rtree::destroy_node<Allocators, internal_node>::apply(m_allocators, node_to_destroy);
Modified: sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/insert.hpp
==============================================================================
--- sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/insert.hpp (original)
+++ sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/insert.hpp 2012-11-21 10:47:51 EST (Wed, 21 Nov 2012)
@@ -119,6 +119,8 @@
typedef typename rtree::internal_node<Value, parameters_type, Box, Allocators, typename Options::node_tag>::type internal_node;
typedef typename rtree::leaf<Value, parameters_type, Box, Allocators, typename Options::node_tag>::type leaf;
+ typedef rtree::node_auto_ptr<Value, Options, Translator, Box, Allocators> node_auto_ptr;
+
public:
typedef index::pushable_array<std::pair<Box, node*>, 1> nodes_container_type;
@@ -130,14 +132,32 @@
Translator const& translator,
Allocators & allocators)
{
- // create additional node
- node * second_node = rtree::create_node<Allocators, Node>::apply(allocators);
+ // TODO - consider creating nodes always with sufficient memory allocated
+
+ // create additional node, use auto ptr for automatic destruction on exception
+ node_auto_ptr second_node(rtree::create_node<Allocators, Node>::apply(allocators), allocators); // MAY THROW, STRONG (N: alloc)
+ // create reference to the newly created node
Node & n2 = rtree::get<Node>(*second_node);
+ // NOTE: thread-safety
+ // After throwing an exception by redistribute_elements the original node may be not changed or
+ // both nodes may be empty. In both cases the tree won't be valid r-tree.
+ // The alternative is to create 2 (or more) additional nodes here and store backup info
+ // in the original node, then, if exception was thrown, the node would always have more than max
+ // elements.
+ // The alternative is to use moving semantics in the implementations of redistribute_elements,
+ // it will be possible to throw from boost::move() in the case of e.g. static size nodes.
+
// redistribute elements
Box box2;
- redistribute_elements<Value, Options, Translator, Box, Allocators, typename Options::redistribute_tag>::
- apply(n, n2, n_box, box2, parameters, translator);
+ redistribute_elements<
+ Value,
+ Options,
+ Translator,
+ Box,
+ Allocators,
+ typename Options::redistribute_tag
+ >::apply(n, n2, n_box, box2, parameters, translator, allocators); // MAY THROW (V, E: alloc, copy, copy)
// check numbers of elements
BOOST_GEOMETRY_INDEX_ASSERT(parameters.get_min_elements() <= rtree::elements(n).size() &&
@@ -147,7 +167,11 @@
rtree::elements(n2).size() <= parameters.get_max_elements(),
"unexpected number of elements");
- additional_nodes.push_back(std::make_pair(box2, second_node));
+ // return the list of newly created nodes (this algorithm returns one)
+ additional_nodes.push_back(std::make_pair(box2, second_node.get())); // MAY THROW, STRONG (alloc, copy)
+
+ // release the ptr
+ second_node.release();
}
};
@@ -205,6 +229,8 @@
typedef typename rtree::internal_node<Value, parameters_type, Box, Allocators, typename Options::node_tag>::type internal_node;
typedef typename rtree::leaf<Value, parameters_type, Box, Allocators, typename Options::node_tag>::type leaf;
+ typedef rtree::node_auto_ptr<Value, Options, Translator, Box, Allocators> node_auto_ptr;
+
inline insert(node* & root,
size_t & leafs_level,
Element const& element,
@@ -243,7 +269,7 @@
rtree::element_indexable(m_element, m_translator));
// next traversing step
- traverse_apply_visitor(visitor, n, choosen_node_index);
+ traverse_apply_visitor(visitor, n, choosen_node_index); // MAY THROW (V, E: alloc, copy, N:alloc)
}
// TODO: awulkiew - change post_traverse name to handle_overflow or overflow_treatment?
@@ -258,7 +284,7 @@
// handle overflow
if ( m_parameters.get_max_elements() < rtree::elements(n).size() )
{
- split(n);
+ split(n); // MAY THROW (V, E: alloc, copy, N:alloc)
}
}
@@ -272,7 +298,7 @@
m_traverse_data.move_to_next_level(&n, choosen_node_index);
// next traversing step
- rtree::apply_visitor(visitor, *rtree::elements(n)[choosen_node_index].second);
+ rtree::apply_visitor(visitor, *rtree::elements(n)[choosen_node_index].second); // MAY THROW (V, E: alloc, copy, N:alloc)
// restore previous traverse inputs
m_traverse_data = backup_traverse_data;
@@ -288,26 +314,30 @@
typename split_algo::nodes_container_type additional_nodes;
Box n_box;
- split_algo::apply(additional_nodes, n, n_box, m_parameters, m_translator, m_allocators);
+ split_algo::apply(additional_nodes, n, n_box, m_parameters, m_translator, m_allocators); // MAY THROW (V, E: alloc, copy, N:alloc)
BOOST_GEOMETRY_INDEX_ASSERT(additional_nodes.size() == 1, "unexpected number of additional nodes");
// TODO add all additional nodes
+ // For kmeans algorithm:
// elements number may be greater than node max elements count
// split and reinsert must take node with some elements count
// and container of additional elements (std::pair<Box, node*>s or Values)
// and translator + allocators
// where node_elements_count + additional_elements > node_max_elements_count
- // What with elements other than std::pair<Box, node*> ???
+ // What with elements other than std::pair<Box, node*> ?
// Implement template <node_tag> struct node_element_type or something like that
+ // for exception safety
+ node_auto_ptr additional_node_ptr(additional_nodes[0].second, m_allocators);
+
// node is not the root - just add the new node
if ( !m_traverse_data.current_is_root() )
{
// update old node's box
m_traverse_data.current_element().first = n_box;
- // add new node to the parent's children
- m_traverse_data.parent_elements().push_back(additional_nodes[0]);
+ // add new node to parent's children
+ m_traverse_data.parent_elements().push_back(additional_nodes[0]); // MAY THROW, STRONG (V, E: alloc, copy)
}
// node is the root - add level
else
@@ -315,14 +345,24 @@
BOOST_GEOMETRY_INDEX_ASSERT(&n == rtree::get<Node>(m_root_node), "node should be the root");
// create new root and add nodes
- node * new_root = rtree::create_node<Allocators, internal_node>::apply(m_allocators);
+ node_auto_ptr new_root(rtree::create_node<Allocators, internal_node>::apply(m_allocators), m_allocators); // MAY THROW, STRONG (N:alloc)
- rtree::elements(rtree::get<internal_node>(*new_root)).push_back(std::make_pair(n_box, m_root_node));
- rtree::elements(rtree::get<internal_node>(*new_root)).push_back(additional_nodes[0]);
+ try {
+ rtree::elements(rtree::get<internal_node>(*new_root)).push_back(std::make_pair(n_box, m_root_node)); // MAY THROW, STRONG (E:alloc, copy)
+ rtree::elements(rtree::get<internal_node>(*new_root)).push_back(additional_nodes[0]); // MAY THROW, STRONG (E:alloc, copy)
+ } catch (...) {
+ // clear new root to not delete in the ~node_auto_ptr() potentially stored old root node
+ rtree::elements(rtree::get<internal_node>(*new_root)).clear();
+ throw; // RETHROW
+ }
- m_root_node = new_root;
+ m_root_node = new_root.get();
++m_leafs_level;
+
+ new_root.release();
}
+
+ additional_node_ptr.release();
}
// TODO: awulkiew - implement dispatchable split::apply to enable additional nodes creation
@@ -349,6 +389,9 @@
class insert;
// Default insert visitor used for nodes elements
+// After passing the Element to insert visitor the Element is managed by the tree
+// I.e. one should not delete the node passed to the insert visitor after exception is thrown
+// because this visitor may delete it
template <typename Element, typename Value, typename Options, typename Translator, typename Box, typename Allocators>
class insert<Element, Value, Options, Translator, Box, Allocators, insert_default_tag>
: public detail::insert<Element, Value, Options, Translator, Box, Allocators>
@@ -363,7 +406,7 @@
inline insert(node* & root,
size_t & leafs_level,
- Element const& element,
+ Element & element,
parameters_type const& parameters,
Translator const& translator,
Allocators & allocators,
@@ -379,17 +422,29 @@
if ( base::m_traverse_data.current_level < base::m_level )
{
// next traversing step
- base::traverse(*this, n);
+ base::traverse(*this, n); // MAY THROW (E: alloc, copy, N: alloc)
}
else
{
BOOST_GEOMETRY_INDEX_ASSERT(base::m_level == base::m_traverse_data.current_level, "unexpected level");
- // push new child node
- rtree::elements(n).push_back(base::m_element);
+ try
+ {
+ // push new child node
+ rtree::elements(n).push_back(base::m_element); // MAY THROW, STRONG (E: alloc, copy)
+ }
+ catch(...)
+ {
+ // if the insert fails above, the element won't be stored in the tree
+
+ rtree::visitors::destroy<Value, Options, Translator, Box, Allocators> del_v(base::m_element.second, base::m_allocators);
+ rtree::apply_visitor(del_v, *base::m_element.second);
+
+ throw; // RETHROW
+ }
}
- base::post_traverse(n);
+ base::post_traverse(n); // MAY THROW (E: alloc, copy, N: alloc)
}
inline void operator()(leaf &)
@@ -428,9 +483,9 @@
BOOST_GEOMETRY_INDEX_ASSERT(base::m_traverse_data.current_level < base::m_level, "unexpected level");
// next traversing step
- base::traverse(*this, n);
+ base::traverse(*this, n); // MAY THROW (V, E: alloc, copy, N: alloc)
- base::post_traverse(n);
+ base::post_traverse(n); // MAY THROW (E: alloc, copy, N: alloc)
}
inline void operator()(leaf & n)
@@ -439,9 +494,9 @@
BOOST_GEOMETRY_INDEX_ASSERT(base::m_level == base::m_traverse_data.current_level ||
base::m_level == (std::numeric_limits<size_t>::max)(), "unexpected level");
- rtree::elements(n).push_back(base::m_element);
+ rtree::elements(n).push_back(base::m_element); // MAY THROW, STRONG (V: alloc, copy)
- base::post_traverse(n);
+ base::post_traverse(n); // MAY THROW (V: alloc, copy, N: alloc)
}
};
Modified: sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/query.hpp
==============================================================================
--- sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/query.hpp (original)
+++ sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/query.hpp 2012-11-21 10:47:51 EST (Wed, 21 Nov 2012)
@@ -11,6 +11,8 @@
#ifndef BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_VISITORS_QUERY_HPP
#define BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_VISITORS_QUERY_HPP
+#include <boost/geometry/extensions/index/rtree/predicates.hpp>
+
#include <boost/geometry/extensions/index/rtree/node/node.hpp>
namespace boost { namespace geometry { namespace index {
Modified: sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/remove.hpp
==============================================================================
--- sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/remove.hpp (original)
+++ sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/remove.hpp 2012-11-21 10:47:51 EST (Wed, 21 Nov 2012)
@@ -33,6 +33,8 @@
typedef typename rtree::internal_node<Value, parameters_type, Box, Allocators, typename Options::node_tag>::type internal_node;
typedef typename rtree::leaf<Value, parameters_type, Box, Allocators, typename Options::node_tag>::type leaf;
+ typedef rtree::node_auto_ptr<Value, Options, Translator, Box, Allocators> node_auto_ptr;
+
public:
inline remove(node* & root,
size_t & leafs_level,
@@ -68,7 +70,7 @@
if ( geometry::covered_by(m_translator(m_value), children[child_node_index].first) )
{
// next traversing step
- traverse_apply_visitor(n, child_node_index);
+ traverse_apply_visitor(n, child_node_index); // MAY THROW
if ( m_is_value_removed )
break;
@@ -86,13 +88,10 @@
if ( m_is_underflow )
{
element_iterator underfl_el_it = elements.begin() + child_node_index;
+ size_t relative_level = m_leafs_level - m_current_level;
- // move node to the container - store node's relative level as well
- m_underflowed_nodes.push_back(std::make_pair(m_leafs_level - m_current_level, underfl_el_it->second));
- elements.erase(underfl_el_it);
-
- // calc underflow
- m_is_underflow = elements.size() < m_parameters.get_min_elements();
+ // move node to the container - store node's relative level as well and return new underflow state
+ m_is_underflow = store_underflowed_node(elements, underfl_el_it, relative_level); // MAY THROW (E: alloc, copy)
}
// n is not root - adjust aabb
@@ -112,26 +111,8 @@
BOOST_GEOMETRY_INDEX_ASSERT(&n == rtree::get<internal_node>(m_root_node), "node must be the root");
BOOST_GEOMETRY_INDEX_ASSERT(m_is_value_removed, "value not found");
- // reinsert elements from removed nodes
- // begin with levels closer to the root
- for ( typename std::vector< std::pair<size_t, node*> >::reverse_iterator it = m_underflowed_nodes.rbegin();
- it != m_underflowed_nodes.rend() ; ++it )
- {
- is_leaf<Value, Options, Box, Allocators> ilv;
- rtree::apply_visitor(ilv, *it->second);
- if ( ilv.result )
- {
- reinsert_elements(rtree::get<leaf>(*it->second), it->first);
-
- rtree::destroy_node<Allocators, leaf>::apply(m_allocators, it->second);
- }
- else
- {
- reinsert_elements(rtree::get<internal_node>(*it->second), it->first);
-
- rtree::destroy_node<Allocators, internal_node>::apply(m_allocators, it->second);
- }
- }
+ // reinsert elements from removed nodes (underflows)
+ reinsert_removed_nodes_elements(); // MAY THROW (V, E: alloc, copy, N: alloc)
// shorten the tree
if ( rtree::elements(n).size() == 1 )
@@ -156,7 +137,8 @@
{
if ( m_translator.equals(*it, m_value) )
{
- elements.erase(it);
+ rtree::copy_from_back(elements, it); // MAY THROW (V: copy)
+ elements.pop_back();
m_is_value_removed = true;
break;
}
@@ -178,7 +160,10 @@
}
private:
- inline void traverse_apply_visitor(internal_node &n, size_t choosen_node_index)
+
+ typedef std::vector< std::pair<size_t, node*> > UnderflowNodes;
+
+ void traverse_apply_visitor(internal_node &n, size_t choosen_node_index)
{
// save previous traverse inputs and set new ones
internal_node * parent_bckup = m_parent;
@@ -190,7 +175,7 @@
++m_current_level;
// next traversing step
- rtree::apply_visitor(*this, *rtree::elements(n)[choosen_node_index].second);
+ rtree::apply_visitor(*this, *rtree::elements(n)[choosen_node_index].second); // MAY THROW (V, E: alloc, copy, N: alloc)
// restore previous traverse inputs
m_parent = parent_bckup;
@@ -198,32 +183,101 @@
m_current_level = current_level_bckup;
}
+ bool store_underflowed_node(
+ typename rtree::elements_type<internal_node>::type & elements,
+ typename rtree::elements_type<internal_node>::type::iterator underfl_el_it,
+ size_t relative_level)
+ {
+ // move node to the container - store node's relative level as well
+ m_underflowed_nodes.push_back(std::make_pair(relative_level, underfl_el_it->second)); // MAY THROW (E: alloc, copy)
+
+ try
+ {
+ rtree::copy_from_back(elements, underfl_el_it); // MAY THROW (E: copy)
+ elements.pop_back();
+ }
+ catch(...)
+ {
+ m_underflowed_nodes.pop_back();
+ throw; // RETHROW
+ }
+
+ // calc underflow
+ return elements.size() < m_parameters.get_min_elements();
+ }
+
+ void reinsert_removed_nodes_elements()
+ {
+ typename UnderflowNodes::reverse_iterator it = m_underflowed_nodes.rbegin();
+
+ try
+ {
+ // reinsert elements from removed nodes
+ // begin with levels closer to the root
+ for ( ; it != m_underflowed_nodes.rend() ; ++it )
+ {
+ is_leaf<Value, Options, Box, Allocators> ilv;
+ rtree::apply_visitor(ilv, *it->second);
+ if ( ilv.result )
+ {
+ reinsert_node_elements(rtree::get<leaf>(*it->second), it->first); // MAY THROW (V, E: alloc, copy, N: alloc)
+
+ rtree::destroy_node<Allocators, leaf>::apply(m_allocators, it->second);
+ }
+ else
+ {
+ reinsert_node_elements(rtree::get<internal_node>(*it->second), it->first); // MAY THROW (V, E: alloc, copy, N: alloc)
+
+ rtree::destroy_node<Allocators, internal_node>::apply(m_allocators, it->second);
+ }
+ }
+
+ //m_underflowed_nodes.clear();
+ }
+ catch(...)
+ {
+ // destroy current and remaining nodes
+ for ( ; it != m_underflowed_nodes.rend() ; ++it )
+ {
+ node_auto_ptr dummy(it->second, m_allocators);
+ }
+
+ //m_underflowed_nodes.clear();
+
+ throw; // RETHROW
+ }
+ }
+
template <typename Node>
- void reinsert_elements(Node &n, size_t node_relative_level)
+ void reinsert_node_elements(Node &n, size_t node_relative_level)
{
typedef typename rtree::elements_type<Node>::type elements_type;
elements_type & elements = rtree::elements(n);
- for ( typename elements_type::iterator it = elements.begin();
- it != elements.end() ; ++it )
+
+ typename elements_type::iterator it = elements.begin();
+ try
{
- visitors::insert<
- typename elements_type::value_type,
- Value,
- Options,
- Translator,
- Box,
- Allocators,
- typename Options::insert_tag
- > insert_v(
- m_root_node,
- m_leafs_level,
- *it,
- m_parameters,
- m_translator,
- m_allocators,
- node_relative_level - 1);
+ for ( ; it != elements.end() ; ++it )
+ {
+ visitors::insert<
+ typename elements_type::value_type,
+ Value, Options, Translator, Box, Allocators,
+ typename Options::insert_tag
+ > insert_v(
+ m_root_node, m_leafs_level, *it,
+ m_parameters, m_translator, m_allocators,
+ node_relative_level - 1);
- rtree::apply_visitor(insert_v, *m_root_node);
+ rtree::apply_visitor(insert_v, *m_root_node); // MAY THROW (V, E: alloc, copy, N: alloc)
+ }
+ }
+ catch(...)
+ {
+ ++it;
+ rtree::destroy_elements<Value, Options, Translator, Box, Allocators>
+ ::apply(it, elements.end(), m_allocators);
+ elements.clear();
+ throw; // RETHROW
}
}
@@ -235,7 +289,7 @@
node* & m_root_node;
size_t & m_leafs_level;
bool m_is_value_removed;
- std::vector< std::pair<size_t, node*> > m_underflowed_nodes;
+ UnderflowNodes m_underflowed_nodes;
// traversing input parameters
internal_node *m_parent;
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-21 10:47:51 EST (Wed, 21 Nov 2012)
@@ -29,15 +29,20 @@
<div class="toc"><dl>
<dt><span class="section">Introduction</span></dt>
<dt><span class="section">Quick Start</span></dt>
-<dt><span class="section">R-tree creation</span></dt>
+<dt><span class="section"><a href="r_tree/creation_and_modification.html">Creation
+ and modification</a></span></dt>
<dd><dl>
-<dt><span class="section"><a href="r_tree/r_tree_creation.html#geometry_index.r_tree.r_tree_creation.r_tree_template_parameters">R-tree
- template parameters</a></span></dt>
-<dt><span class="section"><a href="r_tree/r_tree_creation.html#geometry_index.r_tree.r_tree_creation.values__indexables_and_default_translator">Values,
+<dt><span class="section"><a href="r_tree/creation_and_modification.html#geometry_index.r_tree.creation_and_modification.template_parameters">Template
+ parameters</a></span></dt>
+<dt><span class="section"><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></span></dt>
-<dt><span class="section"><a href="r_tree/r_tree_creation.html#geometry_index.r_tree.r_tree_creation.inserting_and_splitting_algorithms">Inserting
+<dt><span class="section"><a href="r_tree/creation_and_modification.html#geometry_index.r_tree.creation_and_modification.inserting_and_splitting_algorithms">Inserting
and splitting algorithms</a></span></dt>
-<dt><span class="section"><a href="r_tree/r_tree_creation.html#geometry_index.r_tree.r_tree_creation.inserting_and_removing_values">Inserting
+<dt><span class="section"><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></span></dt>
+<dt><span class="section"><a href="r_tree/creation_and_modification.html#geometry_index.r_tree.creation_and_modification.copying_and_moving">Copying
+ and moving</a></span></dt>
+<dt><span class="section"><a href="r_tree/creation_and_modification.html#geometry_index.r_tree.creation_and_modification.inserting_and_removing_values">Inserting
and removing Values</a></span></dt>
</dl></dd>
<dt><span class="section">Spatial queries</span></dt>
@@ -59,6 +64,7 @@
<dt><span class="section"><a href="r_tree/nearest_neighbours_queries.html#geometry_index.r_tree.nearest_neighbours_queries.using_spatial_predicates">Using
spatial predicates</a></span></dt>
</dl></dd>
+<dt><span class="section">Exception safety</span></dt>
</dl></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/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-21 10:47:51 EST (Wed, 21 Nov 2012)
@@ -7,6 +7,7 @@
<link rel="home" href="../../index.html" title="Chapter 1. Geometry Index">
<link rel="up" href="../r_tree.html" title="R-tree">
<link rel="prev" href="spatial_queries.html" title="Spatial queries">
+<link rel="next" href="exception_safety.html" title="Exception safety">
</head>
<body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF">
<table cellpadding="2" width="100%"><tr>
@@ -19,7 +20,7 @@
</tr></table>
<hr>
<div class="spirit-nav">
-<a accesskey="p" href="spatial_queries.html"><img src="http://www.boost.org/doc/libs/release/doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../r_tree.html"><img src="http://www.boost.org/doc/libs/release/doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../../index.html"><img src="http://www.boost.org/doc/libs/release/doc/src/images/home.png" alt="Home"></a>
+<a accesskey="p" href="spatial_queries.html"><img src="http://www.boost.org/doc/libs/release/doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../r_tree.html"><img src="http://www.boost.org/doc/libs/release/doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../../index.html"><img src="http://www.boost.org/doc/libs/release/doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="exception_safety.html"><img src="http://www.boost.org/doc/libs/release/doc/src/images/next.png" alt="Next"></a>
</div>
<div class="section">
<div class="titlepage"><div><div><h3 class="title">
@@ -52,20 +53,20 @@
</p>
<pre class="programlisting"><span class="identifier">std</span><span class="special">::</span><span class="identifier">vector</span><span class="special"><</span>Value<span class="special">></span> <span class="identifier">returned_values</span><span class="special">;</span>
<a href="http://www.boost.org/libs/geometry/doc/html/geometry/reference/concepts/concept_point.html" target="_top">Point</a> <span class="identifier">pt</span><span class="special">(...);</span>
-<span class="identifier">rt</span><span class="special">.</span><span class="identifier">nearest</span><span class="special">(</span><span class="identifier">pt</span><span class="special">,</span> <span class="identifier">k</span><span class="special">,</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">back_inserter</span><span class="special">(</span><span class="identifier">returned_values</span><span class="special">));</span>
+<span class="identifier">rt</span><span class="special">.</span><span class="identifier">nearest_query</span><span class="special">(</span><span class="identifier">pt</span><span class="special">,</span> <span class="identifier">k</span><span class="special">,</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">back_inserter</span><span class="special">(</span><span class="identifier">returned_values</span><span class="special">));</span>
</pre>
<p>
Function call
</p>
<pre class="programlisting"><span class="identifier">std</span><span class="special">::</span><span class="identifier">vector</span><span class="special"><</span>Value<span class="special">></span> <span class="identifier">returned_values</span><span class="special">;</span>
<a href="http://www.boost.org/libs/geometry/doc/html/geometry/reference/concepts/concept_point.html" target="_top">Point</a> <span class="identifier">pt</span><span class="special">(...);</span>
-<span class="identifier">index</span><span class="special">::</span><span class="identifier">nearest</span><span class="special">(</span><span class="identifier">rt</span><span class="special">,</span> <span class="identifier">pt</span><span class="special">,</span> <span class="identifier">k</span><span class="special">,</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">back_inserter</span><span class="special">(</span><span class="identifier">returned_values</span><span class="special">));</span>
+<span class="identifier">index</span><span class="special">::</span><span class="identifier">nearest_query</span><span class="special">(</span><span class="identifier">rt</span><span class="special">,</span> <span class="identifier">pt</span><span class="special">,</span> <span class="identifier">k</span><span class="special">,</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">back_inserter</span><span class="special">(</span><span class="identifier">returned_values</span><span class="special">));</span>
</pre>
<p>
Use of <code class="computeroutput"><span class="keyword">operator</span> <span class="special">|</span></code>
</p>
<pre class="programlisting">Point <span class="identifier">pt</span><span class="special">(...);</span>
-<span class="identifier">BOOST_FOREACH</span><span class="special">(</span>Value <span class="special">&</span> <span class="identifier">v</span><span class="special">,</span> <span class="identifier">rt</span> <span class="special">|</span> <span class="identifier">index</span><span class="special">::</span><span class="identifier">nearest_filtered</span><span class="special">(</span><span class="identifier">pt</span><span class="special">,</span> <span class="identifier">k</span><span class="special">))</span>
+<span class="identifier">BOOST_FOREACH</span><span class="special">(</span>Value <span class="special">&</span> <span class="identifier">v</span><span class="special">,</span> <span class="identifier">rt</span> <span class="special">|</span> <span class="identifier">index</span><span class="special">::</span><span class="identifier">adaptors</span><span class="special">::</span><span class="identifier">nearest_queried</span><span class="special">(</span><span class="identifier">pt</span><span class="special">,</span> <span class="identifier">k</span><span class="special">))</span>
<span class="special">;</span> <span class="comment">// do something with v</span>
</pre>
</div>
@@ -84,14 +85,14 @@
</p>
<pre class="programlisting">Value <span class="identifier">returned_value</span><span class="special">;</span>
<a href="http://www.boost.org/libs/geometry/doc/html/geometry/reference/concepts/concept_point.html" target="_top">Point</a> <span class="identifier">pt</span><span class="special">(...);</span>
-<span class="identifier">size_t</span> <span class="identifier">n</span> <span class="special">=</span> <span class="identifier">rt</span><span class="special">.</span><span class="identifier">nearest</span><span class="special">(</span><span class="identifier">pt</span><span class="special">,</span> <span class="identifier">returned_value</span><span class="special">);</span>
+<span class="identifier">size_t</span> <span class="identifier">n</span> <span class="special">=</span> <span class="identifier">rt</span><span class="special">.</span><span class="identifier">nearest_query</span><span class="special">(</span><span class="identifier">pt</span><span class="special">,</span> <span class="identifier">returned_value</span><span class="special">);</span>
</pre>
<p>
Function call
</p>
<pre class="programlisting">Value <span class="identifier">Value</span> <span class="identifier">returned_value</span><span class="special">;</span>
<a href="http://www.boost.org/libs/geometry/doc/html/geometry/reference/concepts/concept_point.html" target="_top">Point</a> <span class="identifier">pt</span><span class="special">(...);</span>
-<span class="identifier">size_t</span> <span class="identifier">n</span> <span class="special">=</span> <span class="identifier">index</span><span class="special">::</span><span class="identifier">nearest</span><span class="special">(</span><span class="identifier">rt</span><span class="special">,</span> <span class="identifier">pt</span><span class="special">,</span> <span class="identifier">returned_value</span><span class="special">);</span>
+<span class="identifier">size_t</span> <span class="identifier">n</span> <span class="special">=</span> <span class="identifier">index</span><span class="special">::</span><span class="identifier">nearest_query</span><span class="special">(</span><span class="identifier">rt</span><span class="special">,</span> <span class="identifier">pt</span><span class="special">,</span> <span class="identifier">returned_value</span><span class="special">);</span>
</pre>
</div>
<div class="section">
@@ -109,19 +110,19 @@
<a href="http://www.boost.org/libs/geometry/doc/html/geometry/reference/concepts/concept_point.html" target="_top">Point</a> <span class="identifier">pt</span><span class="special">(...);</span>
<span class="comment">/* default - without bounds */</span>
-<span class="identifier">index</span><span class="special">::</span><span class="identifier">nearest</span><span class="special">(</span><span class="identifier">rt</span><span class="special">,</span> <span class="identifier">pt</span><span class="special">,</span> <span class="identifier">k</span><span class="special">,</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">back_inserter</span><span class="special">(</span><span class="identifier">returned_values</span><span class="special">));</span>
+<span class="identifier">index</span><span class="special">::</span><span class="identifier">nearest_query</span><span class="special">(</span><span class="identifier">rt</span><span class="special">,</span> <span class="identifier">pt</span><span class="special">,</span> <span class="identifier">k</span><span class="special">,</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">back_inserter</span><span class="special">(</span><span class="identifier">returned_values</span><span class="special">));</span>
<span class="comment">/* same as default */</span>
-<span class="identifier">index</span><span class="special">::</span><span class="identifier">nearest</span><span class="special">(</span><span class="identifier">rt</span><span class="special">,</span> <span class="identifier">index</span><span class="special">::</span><span class="identifier">unbounded</span><span class="special">(</span><span class="identifier">pt</span><span class="special">),</span> <span class="identifier">k</span><span class="special">,</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">back_inserter</span><span class="special">(</span><span class="identifier">returned_values</span><span class="special">));</span>
+<span class="identifier">index</span><span class="special">::</span><span class="identifier">nearest_query</span><span class="special">(</span><span class="identifier">rt</span><span class="special">,</span> <span class="identifier">index</span><span class="special">::</span><span class="identifier">unbounded</span><span class="special">(</span><span class="identifier">pt</span><span class="special">),</span> <span class="identifier">k</span><span class="special">,</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">back_inserter</span><span class="special">(</span><span class="identifier">returned_values</span><span class="special">));</span>
<span class="comment">/* distance must be greater than or equal to 10 */</span>
-<span class="identifier">index</span><span class="special">::</span><span class="identifier">nearest</span><span class="special">(</span><span class="identifier">rt</span><span class="special">,</span> <span class="identifier">index</span><span class="special">::</span><span class="identifier">min_bounded</span><span class="special">(</span><span class="identifier">pt</span><span class="special">,</span> <span class="number">10</span><span class="special">),</span> <span class="identifier">k</span><span class="special">,</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">back_inserter</span><span class="special">(</span><span class="identifier">returned_values</span><span class="special">));</span>
+<span class="identifier">index</span><span class="special">::</span><span class="identifier">nearest_query</span><span class="special">(</span><span class="identifier">rt</span><span class="special">,</span> <span class="identifier">index</span><span class="special">::</span><span class="identifier">min_bounded</span><span class="special">(</span><span class="identifier">pt</span><span class="special">,</span> <span class="number">10</span><span class="special">),</span> <span class="identifier">k</span><span class="special">,</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">back_inserter</span><span class="special">(</span><span class="identifier">returned_values</span><span class="special">));</span>
<span class="comment">/* distance must be lesser than or equal to 500 */</span>
-<span class="identifier">index</span><span class="special">::</span><span class="identifier">nearest</span><span class="special">(</span><span class="identifier">rt</span><span class="special">,</span> <span class="identifier">index</span><span class="special">::</span><span class="identifier">max_bounded</span><span class="special">(</span><span class="identifier">pt</span><span class="special">,</span> <span class="number">500</span><span class="special">),</span> <span class="identifier">k</span><span class="special">,</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">back_inserter</span><span class="special">(</span><span class="identifier">returned_values</span><span class="special">));</span>
+<span class="identifier">index</span><span class="special">::</span><span class="identifier">nearest_query</span><span class="special">(</span><span class="identifier">rt</span><span class="special">,</span> <span class="identifier">index</span><span class="special">::</span><span class="identifier">max_bounded</span><span class="special">(</span><span class="identifier">pt</span><span class="special">,</span> <span class="number">500</span><span class="special">),</span> <span class="identifier">k</span><span class="special">,</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">back_inserter</span><span class="special">(</span><span class="identifier">returned_values</span><span class="special">));</span>
<span class="comment">/* distance must be between 10 and 500 */</span>
-<span class="identifier">index</span><span class="special">::</span><span class="identifier">nearest</span><span class="special">(</span><span class="identifier">rt</span><span class="special">,</span> <span class="identifier">index</span><span class="special">::</span><span class="identifier">bounded</span><span class="special">(</span><span class="identifier">pt</span><span class="special">,</span> <span class="number">10</span><span class="special">,</span> <span class="number">500</span><span class="special">),</span> <span class="identifier">k</span><span class="special">,</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">back_inserter</span><span class="special">(</span><span class="identifier">returned_values</span><span class="special">));</span>
+<span class="identifier">index</span><span class="special">::</span><span class="identifier">nearest_query</span><span class="special">(</span><span class="identifier">rt</span><span class="special">,</span> <span class="identifier">index</span><span class="special">::</span><span class="identifier">bounded</span><span class="special">(</span><span class="identifier">pt</span><span class="special">,</span> <span class="number">10</span><span class="special">,</span> <span class="number">500</span><span class="special">),</span> <span class="identifier">k</span><span class="special">,</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">back_inserter</span><span class="special">(</span><span class="identifier">returned_values</span><span class="special">));</span>
</pre>
<p>
Furthermore, it's possible to define if the closest, furthest or centroidal
@@ -133,19 +134,19 @@
<span class="comment">/* default - distance between Indexable's closest point and a query point
must be greater than 10 */</span>
-<span class="identifier">index</span><span class="special">::</span><span class="identifier">nearest</span><span class="special">(</span><span class="identifier">rt</span><span class="special">,</span> <span class="identifier">index</span><span class="special">::</span><span class="identifier">min_bounded</span><span class="special">(</span><span class="identifier">pt</span><span class="special">,</span> <span class="number">10</span><span class="special">),</span> <span class="identifier">k</span><span class="special">,</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">back_inserter</span><span class="special">(</span><span class="identifier">returned_values</span><span class="special">));</span>
+<span class="identifier">index</span><span class="special">::</span><span class="identifier">nearest_query</span><span class="special">(</span><span class="identifier">rt</span><span class="special">,</span> <span class="identifier">index</span><span class="special">::</span><span class="identifier">min_bounded</span><span class="special">(</span><span class="identifier">pt</span><span class="special">,</span> <span class="number">10</span><span class="special">),</span> <span class="identifier">k</span><span class="special">,</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">back_inserter</span><span class="special">(</span><span class="identifier">returned_values</span><span class="special">));</span>
<span class="comment">/* same as default - distance between Indexable's closest point and a query point
must be greater than 10 */</span>
-<span class="identifier">index</span><span class="special">::</span><span class="identifier">nearest</span><span class="special">(</span><span class="identifier">rt</span><span class="special">,</span> <span class="identifier">index</span><span class="special">::</span><span class="identifier">min_bounded</span><span class="special">(</span><span class="identifier">pt</span><span class="special">,</span> <span class="identifier">index</span><span class="special">::</span><span class="identifier">to_nearest</span><span class="special">(</span><span class="number">10</span><span class="special">)),</span> <span class="identifier">k</span><span class="special">,</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">back_inserter</span><span class="special">(</span><span class="identifier">returned_values</span><span class="special">));</span>
+<span class="identifier">index</span><span class="special">::</span><span class="identifier">nearest_query</span><span class="special">(</span><span class="identifier">rt</span><span class="special">,</span> <span class="identifier">index</span><span class="special">::</span><span class="identifier">min_bounded</span><span class="special">(</span><span class="identifier">pt</span><span class="special">,</span> <span class="identifier">index</span><span class="special">::</span><span class="identifier">to_nearest</span><span class="special">(</span><span class="number">10</span><span class="special">)),</span> <span class="identifier">k</span><span class="special">,</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">back_inserter</span><span class="special">(</span><span class="identifier">returned_values</span><span class="special">));</span>
<span class="comment">/* distance between Indexable's furthest point and a query point
must be greater than 10 */</span>
-<span class="identifier">index</span><span class="special">::</span><span class="identifier">nearest</span><span class="special">(</span><span class="identifier">rt</span><span class="special">,</span> <span class="identifier">index</span><span class="special">::</span><span class="identifier">min_bounded</span><span class="special">(</span><span class="identifier">pt</span><span class="special">,</span> <span class="identifier">index</span><span class="special">::</span><span class="identifier">to_furthest</span><span class="special">(</span><span class="number">10</span><span class="special">)),</span> <span class="identifier">k</span><span class="special">,</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">back_inserter</span><span class="special">(</span><span class="identifier">returned_values</span><span class="special">));</span>
+<span class="identifier">index</span><span class="special">::</span><span class="identifier">nearest_query</span><span class="special">(</span><span class="identifier">rt</span><span class="special">,</span> <span class="identifier">index</span><span class="special">::</span><span class="identifier">min_bounded</span><span class="special">(</span><span class="identifier">pt</span><span class="special">,</span> <span class="identifier">index</span><span class="special">::</span><span class="identifier">to_furthest</span><span class="special">(</span><span class="number">10</span><span class="special">)),</span> <span class="identifier">k</span><span class="special">,</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">back_inserter</span><span class="special">(</span><span class="identifier">returned_values</span><span class="special">));</span>
<span class="comment">/* distance between Indexable's centroid and a query point
must be greater than 10 */</span>
-<span class="identifier">index</span><span class="special">::</span><span class="identifier">nearest</span><span class="special">(</span><span class="identifier">rt</span><span class="special">,</span> <span class="identifier">index</span><span class="special">::</span><span class="identifier">min_bounded</span><span class="special">(</span><span class="identifier">pt</span><span class="special">,</span> <span class="identifier">index</span><span class="special">::</span><span class="identifier">to_centroid</span><span class="special">(</span><span class="number">10</span><span class="special">)),</span> <span class="identifier">k</span><span class="special">,</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">back_inserter</span><span class="special">(</span><span class="identifier">returned_values</span><span class="special">));</span>
+<span class="identifier">index</span><span class="special">::</span><span class="identifier">nearest_query</span><span class="special">(</span><span class="identifier">rt</span><span class="special">,</span> <span class="identifier">index</span><span class="special">::</span><span class="identifier">min_bounded</span><span class="special">(</span><span class="identifier">pt</span><span class="special">,</span> <span class="identifier">index</span><span class="special">::</span><span class="identifier">to_centroid</span><span class="special">(</span><span class="number">10</span><span class="special">)),</span> <span class="identifier">k</span><span class="special">,</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">back_inserter</span><span class="special">(</span><span class="identifier">returned_values</span><span class="special">));</span>
</pre>
</div>
<div class="section">
@@ -163,11 +164,11 @@
<a href="http://www.boost.org/libs/geometry/doc/html/geometry/reference/concepts/concept_point.html" target="_top">Point</a> <span class="identifier">pt</span><span class="special">(...);</span>
<a href="http://www.boost.org/libs/geometry/doc/html/geometry/reference/concepts/concept_box.html" target="_top">Box</a> <span class="identifier">b</span><span class="special">(...);</span>
-<span class="identifier">size_t</span> <span class="identifier">n1</span> <span class="special">=</span> <span class="identifier">rt</span><span class="special">.</span><span class="identifier">nearest</span><span class="special">(</span><span class="identifier">index</span><span class="special">::</span><span class="identifier">bounded</span><span class="special">(</span><span class="identifier">pt</span><span class="special">,</span> <span class="identifier">index</span><span class="special">::</span><span class="identifier">to_furthest</span><span class="special">(</span><span class="number">1</span><span class="special">),</span> <span class="number">10</span><span class="special">),</span> <span class="identifier">index</span><span class="special">::</span><span class="identifier">intersects</span><span class="special">(</span><span class="identifier">b</span><span class="special">),</span> <span class="identifier">returned_value</span><span class="special">);</span>
+<span class="identifier">size_t</span> <span class="identifier">n1</span> <span class="special">=</span> <span class="identifier">rt</span><span class="special">.</span><span class="identifier">nearest_query</span><span class="special">(</span><span class="identifier">index</span><span class="special">::</span><span class="identifier">bounded</span><span class="special">(</span><span class="identifier">pt</span><span class="special">,</span> <span class="identifier">index</span><span class="special">::</span><span class="identifier">to_furthest</span><span class="special">(</span><span class="number">1</span><span class="special">),</span> <span class="number">10</span><span class="special">),</span> <span class="identifier">index</span><span class="special">::</span><span class="identifier">intersects</span><span class="special">(</span><span class="identifier">b</span><span class="special">),</span> <span class="identifier">returned_value</span><span class="special">);</span>
-<span class="identifier">size_t</span> <span class="identifier">n2</span> <span class="special">=</span> <span class="identifier">index</span><span class="special">::</span><span class="identifier">nearest</span><span class="special">(</span><span class="identifier">rt</span><span class="special">,</span> <span class="identifier">pt</span><span class="special">,</span> <span class="identifier">k</span><span class="special">,</span> <span class="identifier">index</span><span class="special">::</span><span class="identifier">within</span><span class="special">(</span><span class="identifier">b</span><span class="special">),</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">back_inserter</span><span class="special">(</span><span class="identifier">returned_values</span><span class="special">));</span>
+<span class="identifier">size_t</span> <span class="identifier">n2</span> <span class="special">=</span> <span class="identifier">index</span><span class="special">::</span><span class="identifier">nearest_query</span><span class="special">(</span><span class="identifier">rt</span><span class="special">,</span> <span class="identifier">pt</span><span class="special">,</span> <span class="identifier">k</span><span class="special">,</span> <span class="identifier">index</span><span class="special">::</span><span class="identifier">within</span><span class="special">(</span><span class="identifier">b</span><span class="special">),</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">back_inserter</span><span class="special">(</span><span class="identifier">returned_values</span><span class="special">));</span>
-<span class="identifier">BOOST_FOREACH</span><span class="special">(</span><span class="identifier">Value</span> <span class="special">&</span> <span class="identifier">v</span><span class="special">,</span> <span class="identifier">rt</span> <span class="special">|</span> <span class="identifier">index</span><span class="special">::</span><span class="identifier">nearest_filtered</span><span class="special">(</span><span class="identifier">pt</span><span class="special">,</span> <span class="identifier">k</span><span class="special">,</span> <span class="identifier">index</span><span class="special">::</span><span class="identifier">covered_by</span><span class="special">(</span><span class="identifier">b</span><span class="special">)))</span>
+<span class="identifier">BOOST_FOREACH</span><span class="special">(</span><span class="identifier">Value</span> <span class="special">&</span> <span class="identifier">v</span><span class="special">,</span> <span class="identifier">rt</span> <span class="special">|</span> <span class="identifier">index</span><span class="special">::</span><span class="identifier">adaptors</span><span class="special">::</span><span class="identifier">nearest_queried</span><span class="special">(</span><span class="identifier">pt</span><span class="special">,</span> <span class="identifier">k</span><span class="special">,</span> <span class="identifier">index</span><span class="special">::</span><span class="identifier">covered_by</span><span class="special">(</span><span class="identifier">b</span><span class="special">)))</span>
<span class="special">;</span> <span class="comment">// do something with v</span>
</pre>
</div>
@@ -182,7 +183,7 @@
</tr></table>
<hr>
<div class="spirit-nav">
-<a accesskey="p" href="spatial_queries.html"><img src="http://www.boost.org/doc/libs/release/doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../r_tree.html"><img src="http://www.boost.org/doc/libs/release/doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../../index.html"><img src="http://www.boost.org/doc/libs/release/doc/src/images/home.png" alt="Home"></a>
+<a accesskey="p" href="spatial_queries.html"><img src="http://www.boost.org/doc/libs/release/doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../r_tree.html"><img src="http://www.boost.org/doc/libs/release/doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../../index.html"><img src="http://www.boost.org/doc/libs/release/doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="exception_safety.html"><img src="http://www.boost.org/doc/libs/release/doc/src/images/next.png" alt="Next"></a>
</div>
</body>
</html>
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-21 10:47:51 EST (Wed, 21 Nov 2012)
@@ -7,7 +7,7 @@
<link rel="home" href="../../index.html" title="Chapter 1. Geometry Index">
<link rel="up" href="../r_tree.html" title="R-tree">
<link rel="prev" href="introduction.html" title="Introduction">
-<link rel="next" href="r_tree_creation.html" title="R-tree creation">
+<link rel="next" href="creation_and_modification.html" title="Creation and modification">
</head>
<body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF">
<table cellpadding="2" width="100%"><tr>
@@ -20,7 +20,7 @@
</tr></table>
<hr>
<div class="spirit-nav">
-<a accesskey="p" href="introduction.html"><img src="http://www.boost.org/doc/libs/release/doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../r_tree.html"><img src="http://www.boost.org/doc/libs/release/doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../../index.html"><img src="http://www.boost.org/doc/libs/release/doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="r_tree_creation.html"><img src="http://www.boost.org/doc/libs/release/doc/src/images/next.png" alt="Next"></a>
+<a accesskey="p" href="introduction.html"><img src="http://www.boost.org/doc/libs/release/doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../r_tree.html"><img src="http://www.boost.org/doc/libs/release/doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../../index.html"><img src="http://www.boost.org/doc/libs/release/doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="creation_and_modification.html"><img src="http://www.boost.org/doc/libs/release/doc/src/images/next.png" alt="Next"></a>
</div>
<div class="section">
<div class="titlepage"><div><div><h3 class="title">
@@ -86,14 +86,14 @@
<p>
</p>
<p>
- There are various types of queries that may be performed, they can be even
- combined together in one call. For simplicity, default one is used.
+ There are various types of spatial queries that may be performed, they can
+ be even combined together in one call. For simplicity, default one is used.
</p>
<p>
</p>
<pre class="programlisting"><span class="comment">// find values intersecting a box</span>
<span class="identifier">std</span><span class="special">::</span><span class="identifier">vector</span><span class="special"><</span><span class="identifier">value</span><span class="special">></span> <span class="identifier">result</span><span class="special">;</span>
-<span class="identifier">rtree</span><span class="special">.</span><span class="identifier">query</span><span class="special">(</span><span class="identifier">b</span><span class="special">,</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">back_inserter</span><span class="special">(</span><span class="identifier">result</span><span class="special">));</span>
+<span class="identifier">rtree</span><span class="special">.</span><span class="identifier">spatial_query</span><span class="special">(</span><span class="identifier">b</span><span class="special">,</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">back_inserter</span><span class="special">(</span><span class="identifier">result</span><span class="special">));</span>
</pre>
<p>
</p>
@@ -103,7 +103,7 @@
<p>
</p>
<pre class="programlisting"><span class="comment">// find 5 nearest values to a point</span>
-<span class="identifier">rtree</span><span class="special">.</span><span class="identifier">nearest</span><span class="special">(</span><span class="identifier">point</span><span class="special">(</span><span class="number">0</span><span class="special">,</span> <span class="number">0</span><span class="special">),</span> <span class="number">5</span><span class="special">,</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">back_inserter</span><span class="special">(</span><span class="identifier">result</span><span class="special">));</span>
+<span class="identifier">rtree</span><span class="special">.</span><span class="identifier">nearest_query</span><span class="special">(</span><span class="identifier">point</span><span class="special">(</span><span class="number">0</span><span class="special">,</span> <span class="number">0</span><span class="special">),</span> <span class="number">5</span><span class="special">,</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">back_inserter</span><span class="special">(</span><span class="identifier">result</span><span class="special">));</span>
</pre>
<p>
</p>
@@ -126,7 +126,7 @@
</tr></table>
<hr>
<div class="spirit-nav">
-<a accesskey="p" href="introduction.html"><img src="http://www.boost.org/doc/libs/release/doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../r_tree.html"><img src="http://www.boost.org/doc/libs/release/doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../../index.html"><img src="http://www.boost.org/doc/libs/release/doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="r_tree_creation.html"><img src="http://www.boost.org/doc/libs/release/doc/src/images/next.png" alt="Next"></a>
+<a accesskey="p" href="introduction.html"><img src="http://www.boost.org/doc/libs/release/doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../r_tree.html"><img src="http://www.boost.org/doc/libs/release/doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../../index.html"><img src="http://www.boost.org/doc/libs/release/doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="creation_and_modification.html"><img src="http://www.boost.org/doc/libs/release/doc/src/images/next.png" alt="Next"></a>
</div>
</body>
</html>
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-21 10:47:51 EST (Wed, 21 Nov 2012)
@@ -6,7 +6,7 @@
<meta name="generator" content="DocBook XSL Stylesheets V1.77.1">
<link rel="home" href="../../index.html" title="Chapter 1. Geometry Index">
<link rel="up" href="../r_tree.html" title="R-tree">
-<link rel="prev" href="r_tree_creation.html" title="R-tree creation">
+<link rel="prev" href="creation_and_modification.html" title="Creation and modification">
<link rel="next" href="nearest_neighbours_queries.html" title="Nearest neighbours queries">
</head>
<body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF">
@@ -20,7 +20,7 @@
</tr></table>
<hr>
<div class="spirit-nav">
-<a accesskey="p" href="r_tree_creation.html"><img src="http://www.boost.org/doc/libs/release/doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../r_tree.html"><img src="http://www.boost.org/doc/libs/release/doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../../index.html"><img src="http://www.boost.org/doc/libs/release/doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="nearest_neighbours_queries.html"><img src="http://www.boost.org/doc/libs/release/doc/src/images/next.png" alt="Next"></a>
+<a accesskey="p" href="creation_and_modification.html"><img src="http://www.boost.org/doc/libs/release/doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../r_tree.html"><img src="http://www.boost.org/doc/libs/release/doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../../index.html"><img src="http://www.boost.org/doc/libs/release/doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="nearest_neighbours_queries.html"><img src="http://www.boost.org/doc/libs/release/doc/src/images/next.png" alt="Next"></a>
</div>
<div class="section">
<div class="titlepage"><div><div><h3 class="title">
@@ -46,20 +46,20 @@
</p>
<pre class="programlisting"><span class="identifier">std</span><span class="special">::</span><span class="identifier">vector</span><span class="special"><</span>Value<span class="special">></span> <span class="identifier">returned_values</span><span class="special">;</span>
<a href="http://www.boost.org/libs/geometry/doc/html/geometry/reference/concepts/concept_box.html" target="_top">Box</a> <span class="identifier">box_region</span><span class="special">(...);</span>
-<span class="identifier">rt</span><span class="special">.</span><span class="identifier">query</span><span class="special">(</span><span class="identifier">box_region</span><span class="special">,</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">back_inserter</span><span class="special">(</span><span class="identifier">returned_values</span><span class="special">));</span>
+<span class="identifier">rt</span><span class="special">.</span><span class="identifier">spatial_query</span><span class="special">(</span><span class="identifier">box_region</span><span class="special">,</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">back_inserter</span><span class="special">(</span><span class="identifier">returned_values</span><span class="special">));</span>
</pre>
<p>
Function call
</p>
<pre class="programlisting"><span class="identifier">std</span><span class="special">::</span><span class="identifier">vector</span><span class="special"><</span>Value<span class="special">></span> <span class="identifier">returned_values</span><span class="special">;</span>
<a href="http://www.boost.org/libs/geometry/doc/html/geometry/reference/concepts/concept_box.html" target="_top">Box</a> <span class="identifier">box_region</span><span class="special">(...);</span>
-<span class="identifier">index</span><span class="special">::</span><span class="identifier">query</span><span class="special">(</span><span class="identifier">rt</span><span class="special">,</span> <span class="identifier">box_region</span><span class="special">,</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">back_inserter</span><span class="special">(</span><span class="identifier">returned_values</span><span class="special">));</span>
+<span class="identifier">index</span><span class="special">::</span><span class="identifier">spatial_query</span><span class="special">(</span><span class="identifier">rt</span><span class="special">,</span> <span class="identifier">box_region</span><span class="special">,</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">back_inserter</span><span class="special">(</span><span class="identifier">returned_values</span><span class="special">));</span>
</pre>
<p>
Use of pipe operator generating a range
</p>
<pre class="programlisting">Box <span class="identifier">box_region</span><span class="special">(...);</span>
-<span class="identifier">BOOST_FOREACH</span><span class="special">(</span>Value <span class="special">&</span> <span class="identifier">v</span><span class="special">,</span> <span class="identifier">rt</span> <span class="special">|</span> <span class="identifier">index</span><span class="special">::</span><span class="identifier">query_filtered</span><span class="special">(</span><span class="identifier">box_region</span><span class="special">))</span>
+<span class="identifier">BOOST_FOREACH</span><span class="special">(</span>Value <span class="special">&</span> <span class="identifier">v</span><span class="special">,</span> <span class="identifier">rt</span> <span class="special">|</span> <span class="identifier">index</span><span class="special">::</span><span class="identifier">adaptors</span><span class="special">::</span><span class="identifier">spatial_queried</span><span class="special">(</span><span class="identifier">box_region</span><span class="special">))</span>
<span class="special">;</span> <span class="comment">// do something with v</span>
</pre>
</div>
@@ -75,7 +75,7 @@
algorithms.
</p>
<pre class="programlisting"><span class="identifier">rt</span><span class="special">.</span><span class="identifier">query</span><span class="special">(</span><span class="identifier">box</span><span class="special">,</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">back_inserter</span><span class="special">(</span><span class="identifier">result</span><span class="special">));</span> <span class="comment">// default case - intersects</span>
-<span class="identifier">rt</span><span class="special">.</span><span class="identifier">query</span><span class="special">(</span><span class="identifier">index</span><span class="special">::</span><span class="identifier">intersects</span><span class="special">(</span><span class="identifier">box</span><span class="special">),</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">back_inserter</span><span class="special">(</span><span class="identifier">result</span><span class="special">));</span> <span class="comment">// same as default</span>
+<span class="identifier">rt</span><span class="special">.</span><span class="identifier">query</span><span class="special">(</span><span class="identifier">index</span><span class="special">::</span><span class="identifier">intersects</span><span class="special">(</span><span class="identifier">box</span><span class="special">),</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">back_inserter</span><span class="special">(</span><span class="identifier">result</span><span class="special">));</span> <span class="comment">// the same as default</span>
<span class="identifier">rt</span><span class="special">.</span><span class="identifier">query</span><span class="special">(</span><span class="identifier">index</span><span class="special">::</span><span class="identifier">covered_by</span><span class="special">(</span><span class="identifier">box</span><span class="special">),</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">back_inserter</span><span class="special">(</span><span class="identifier">result</span><span class="special">));</span>
<span class="identifier">rt</span><span class="special">.</span><span class="identifier">query</span><span class="special">(</span><span class="identifier">index</span><span class="special">::</span><span class="identifier">disjont</span><span class="special">(</span><span class="identifier">box</span><span class="special">),</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">back_inserter</span><span class="special">(</span><span class="identifier">result</span><span class="special">));</span>
<span class="identifier">rt</span><span class="special">.</span><span class="identifier">query</span><span class="special">(</span><span class="identifier">index</span><span class="special">::</span><span class="identifier">overlaps</span><span class="special">(</span><span class="identifier">box</span><span class="special">),</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">back_inserter</span><span class="special">(</span><span class="identifier">result</span><span class="special">));</span>
@@ -84,23 +84,21 @@
<p>
All predicates may be negated, e.g.:
</p>
-<pre class="programlisting"><span class="identifier">rt</span><span class="special">.</span><span class="identifier">query</span><span class="special">(</span><span class="identifier">index</span><span class="special">::</span><span class="identifier">not_intersects</span><span class="special">(</span><span class="identifier">box</span><span class="special">),</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">back_inserter</span><span class="special">(</span><span class="identifier">result</span><span class="special">));</span>
-<span class="comment">// or</span>
-<span class="identifier">rt</span><span class="special">.</span><span class="identifier">query</span><span class="special">(!</span><span class="identifier">index</span><span class="special">::</span><span class="identifier">intersects</span><span class="special">(</span><span class="identifier">box</span><span class="special">),</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">back_inserter</span><span class="special">(</span><span class="identifier">result</span><span class="special">));</span>
+<pre class="programlisting"><span class="identifier">rt</span><span class="special">.</span><span class="identifier">spatial_query</span><span class="special">(!</span><span class="identifier">index</span><span class="special">::</span><span class="identifier">intersects</span><span class="special">(</span><span class="identifier">box</span><span class="special">),</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">back_inserter</span><span class="special">(</span><span class="identifier">result</span><span class="special">));</span>
<span class="comment">// the same as</span>
-<span class="identifier">rt</span><span class="special">.</span><span class="identifier">query</span><span class="special">(</span><span class="identifier">index</span><span class="special">::</span><span class="identifier">disjoint</span><span class="special">(</span><span class="identifier">box</span><span class="special">),</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">back_inserter</span><span class="special">(</span><span class="identifier">result</span><span class="special">));</span>
+<span class="identifier">rt</span><span class="special">.</span><span class="identifier">spatial_query</span><span class="special">(</span><span class="identifier">index</span><span class="special">::</span><span class="identifier">disjoint</span><span class="special">(</span><span class="identifier">box</span><span class="special">),</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">back_inserter</span><span class="special">(</span><span class="identifier">result</span><span class="special">));</span>
</pre>
<p>
It's possible to use some number of predicates by passing <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">pair</span><span class="special"><</span><span class="identifier">Pred1</span><span class="special">,</span> <span class="identifier">Pred2</span><span class="special">></span></code>
</p>
-<pre class="programlisting"><span class="identifier">rt</span><span class="special">.</span><span class="identifier">query</span><span class="special">(</span>
+<pre class="programlisting"><span class="identifier">rt</span><span class="special">.</span><span class="identifier">spatial_query</span><span class="special">(</span>
<span class="identifier">std</span><span class="special">::</span><span class="identifier">make_pair</span><span class="special">(</span><span class="identifier">index</span><span class="special">::</span><span class="identifier">intersects</span><span class="special">(</span><span class="identifier">box1</span><span class="special">),</span> <span class="special">!</span><span class="identifier">index</span><span class="special">::</span><span class="identifier">within</span><span class="special">(</span><span class="identifier">box2</span><span class="special">))</span>
<span class="special">,</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">back_inserter</span><span class="special">(</span><span class="identifier">result</span><span class="special">));</span>
</pre>
<p>
or <code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">tuple</span><span class="special"><</span><span class="identifier">Pred1</span><span class="special">,</span> <span class="identifier">Pred2</span><span class="special">,</span> <span class="identifier">Pred3</span><span class="special">,</span> <span class="special">...></span></code>
</p>
-<pre class="programlisting"><span class="identifier">rt</span><span class="special">.</span><span class="identifier">query</span><span class="special">(</span>
+<pre class="programlisting"><span class="identifier">rt</span><span class="special">.</span><span class="identifier">spatial_query</span><span class="special">(</span>
<span class="identifier">boost</span><span class="special">::</span><span class="identifier">make_tuple</span><span class="special">(</span>
<span class="identifier">index</span><span class="special">::</span><span class="identifier">intersects</span><span class="special">(</span><span class="identifier">box1</span><span class="special">),</span> <span class="special">!</span><span class="identifier">index</span><span class="special">::</span><span class="identifier">within</span><span class="special">(</span><span class="identifier">box2</span><span class="special">),</span> <span class="identifier">index</span><span class="special">::</span><span class="identifier">overlaps</span><span class="special">(</span><span class="identifier">box3</span><span class="special">))</span>
<span class="special">,</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">back_inserter</span><span class="special">(</span><span class="identifier">result</span><span class="special">));</span>
@@ -116,9 +114,9 @@
<span class="comment">// ...</span>
-<span class="identifier">rt</span><span class="special">.</span><span class="identifier">query</span><span class="special">(</span>
+<span class="identifier">rt</span><span class="special">.</span><span class="identifier">spatial_query</span><span class="special">(</span>
<span class="identifier">boost</span><span class="special">::</span><span class="identifier">make_pair</span><span class="special">(</span><span class="identifier">index</span><span class="special">::</span><span class="identifier">intersects</span><span class="special">(</span><span class="identifier">box</span><span class="special">),</span> <span class="identifier">index</span><span class="special">::</span><span class="identifier">value</span><span class="special">(</span><span class="identifier">fun</span><span class="special">))</span>
- <span class="special">,</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">back_inserter</span><span class="special">(</span><span class="identifier">result</span><span class="special">));</span>
+<span class="special">,</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">back_inserter</span><span class="special">(</span><span class="identifier">result</span><span class="special">));</span>
</pre>
</div>
</div>
@@ -132,7 +130,7 @@
</tr></table>
<hr>
<div class="spirit-nav">
-<a accesskey="p" href="r_tree_creation.html"><img src="http://www.boost.org/doc/libs/release/doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../r_tree.html"><img src="http://www.boost.org/doc/libs/release/doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../../index.html"><img src="http://www.boost.org/doc/libs/release/doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="nearest_neighbours_queries.html"><img src="http://www.boost.org/doc/libs/release/doc/src/images/next.png" alt="Next"></a>
+<a accesskey="p" href="creation_and_modification.html"><img src="http://www.boost.org/doc/libs/release/doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../r_tree.html"><img src="http://www.boost.org/doc/libs/release/doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../../index.html"><img src="http://www.boost.org/doc/libs/release/doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="nearest_neighbours_queries.html"><img src="http://www.boost.org/doc/libs/release/doc/src/images/next.png" alt="Next"></a>
</div>
</body>
</html>
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-21 10:47:51 EST (Wed, 21 Nov 2012)
@@ -45,16 +45,18 @@
<dd><dl>
<dt><span class="section">Introduction</span></dt>
<dt><span class="section">Quick Start</span></dt>
-<dt><span class="section">R-tree creation</span></dt>
+<dt><span class="section"><a href="geometry_index/r_tree/creation_and_modification.html">Creation
+ and modification</a></span></dt>
<dt><span class="section">Spatial queries</span></dt>
<dt><span class="section"><a href="geometry_index/r_tree/nearest_neighbours_queries.html">Nearest
neighbours queries</a></span></dt>
+<dt><span class="section">Exception safety</span></dt>
</dl></dd>
</dl>
</div>
</div>
<table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr>
-<td align="left"><p><small>Last revised: September 04, 2012 at 18:00:33 GMT</small></p></td>
+<td align="left"><p><small>Last revised: November 20, 2012 at 22:42:04 GMT</small></p></td>
<td align="right"><div class="copyright-footer"></div></td>
</tr></table>
<hr>
Modified: sandbox-branches/geometry/index/doc/rtree.qbk
==============================================================================
--- sandbox-branches/geometry/index/doc/rtree.qbk (original)
+++ sandbox-branches/geometry/index/doc/rtree.qbk 2012-11-21 10:47:51 EST (Wed, 21 Nov 2012)
@@ -13,7 +13,8 @@
[include rtree/introduction.qbk]
[include rtree/quickstart.qbk]
[include rtree/creation.qbk]
-[include rtree/query.qbk]
-[include rtree/nearest.qbk]
+[include rtree/spatial_query.qbk]
+[include rtree/nearest_query.qbk]
+[include rtree/exception_safety.qbk]
[endsect]
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-21 10:47:51 EST (Wed, 21 Nov 2012)
@@ -8,19 +8,19 @@
http://www.boost.org/LICENSE_1_0.txt)
=============================================================================/]
-[section R-tree creation]
+[section Creation and modification]
-[section R-tree template parameters]
+[section Template parameters]
__rtree__ has 4 parameters:
rtree<Value, Parameters, Translator, Allocator>
-* `Value` - type of object which will be stored in the container.
+* `__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.
-* `Translator` - type of object translating `Value` objects to
- `Indexable` objects (`__point__` or `__box__`) which __rtree__ can handle.
+* `__translator__` - type of object translating `Value` objects to
+ `__indexable__` objects (`__point__` or `__box__`) which __rtree__ can handle.
* `Allocator` - the allocator.
[endsect]
@@ -68,6 +68,38 @@
[endsect]
+[section Inserting and splitting algorithms (run-time)]
+
+By default splitting algorithm parameters are passed to the __rtree__ in compile 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));
+
+[endsect]
+
+[section Copying and moving]
+
+The __rtree__ is copyable and movable container. Move semantics is implemented using Boost.Move library
+which also supports compilers not supporting rvalue references.
+
+ index::rtree< __value__, index::quadratic<32, 8> > rt1;
+ // copy constructor
+ index::rtree< __value__, index::quadratic<32, 8> > rt2;
+ // copy assignment
+ rt2 = r1;
+ // move constructor
+ index::rtree< __value__, index::quadratic<32, 8> > rt3(boost::move(rt1));
+ // move assignment
+ rt3 = boost::move(rt2);
+
+[endsect]
+
[section Inserting and removing Values]
Following code creates an __rtree__ using quadratic algorithm.
@@ -92,4 +124,4 @@
[endsect]
-[endsect] [/ R-tree creation /]
+[endsect] [/ Creation and modification /]
Deleted: sandbox-branches/geometry/index/doc/rtree/nearest.qbk
==============================================================================
--- sandbox-branches/geometry/index/doc/rtree/nearest.qbk 2012-11-21 10:47:51 EST (Wed, 21 Nov 2012)
+++ (empty file)
@@ -1,126 +0,0 @@
-[/============================================================================
- Boost.Geometry Index
-
- Copyright (c) 2011-2012 Adam Wulkiewicz.
-
- Use, modification and distribution is subject to the Boost Software License,
- Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
- http://www.boost.org/LICENSE_1_0.txt)
-=============================================================================/]
-
-[section Nearest neighbours queries]
-
-[section k nearest neighbours]
-
-There are three ways of performing knn queries. Following queries returns
-k `__value__`s closest to some point in space. For `__box__`es
-`__indexable__`s the distance to the nearest point is calculated by default.
-
-Method call
-
- std::vector<__value__> returned_values;
- __point__ pt(...);
- rt.nearest(pt, k, std::back_inserter(returned_values));
-
-Function call
-
- std::vector<__value__> returned_values;
- __point__ pt(...);
- index::nearest(rt, pt, k, std::back_inserter(returned_values));
-
-Use of `operator |`
-
- __point__ pt(...);
- BOOST_FOREACH(__value__ & v, rt | index::nearest_filtered(pt, k))
- ; // do something with v
-
-[endsect]
-
-[section One nearest neighbour]
-
-Another type of nearest neighbour query is searching for the one closest `__value__`.
-If it is found, 1 is returned by the method or function. This kind of query
-has only two forms.
-
-Method call
-
- __value__ returned_value;
- __point__ pt(...);
- size_t n = rt.nearest(pt, returned_value);
-
-Function call
-
- __value__ Value returned_value;
- __point__ pt(...);
- size_t n = index::nearest(rt, pt, returned_value);
-
-[endsect]
-
-[section Distances predicates]
-
-It is possible to define if calculated distance between query point and `__value__` should be
-greater, lesser or between some other distances. Those are called `DistancesPredicate`s and
-may be defined as follows.
-
- std::vector<__Value__> returned_values;
- __point__ pt(...);
-
- /* default - without bounds */
- index::nearest(rt, pt, k, std::back_inserter(returned_values));
-
- /* same as default */
- index::nearest(rt, index::unbounded(pt), k, std::back_inserter(returned_values));
-
- /* distance must be greater than or equal to 10 */
- index::nearest(rt, index::min_bounded(pt, 10), k, std::back_inserter(returned_values));
-
- /* distance must be lesser than or equal to 500 */
- index::nearest(rt, index::max_bounded(pt, 500), k, std::back_inserter(returned_values));
-
- /* distance must be between 10 and 500 */
- index::nearest(rt, index::bounded(pt, 10, 500), k, std::back_inserter(returned_values));
-
-Furthermore, it's possible to define if the closest, furthest or centroidal point of the
-non-point `__indexable__` should be taken into account in the routine calculating distance.
-
- std::vector<__value__> returned_values;
- __point__ pt(...);
-
- /* default - distance between Indexable's closest point and a query point
- must be greater than 10 */
- index::nearest(rt, index::min_bounded(pt, 10), k, std::back_inserter(returned_values));
-
- /* same as default - distance between Indexable's closest point and a query point
- must be greater than 10 */
- index::nearest(rt, index::min_bounded(pt, index::to_nearest(10)), k, std::back_inserter(returned_values));
-
- /* distance between Indexable's furthest point and a query point
- must be greater than 10 */
- index::nearest(rt, index::min_bounded(pt, index::to_furthest(10)), k, std::back_inserter(returned_values));
-
- /* distance between Indexable's centroid and a query point
- must be greater than 10 */
- index::nearest(rt, index::min_bounded(pt, index::to_centroid(10)), k, std::back_inserter(returned_values));
-
-[endsect]
-
-[section Using spatial predicates]
-
-It is possible to use spatial predicates described before in nearest neighbours queries.
-
- __value__ returned_value;
- std::vector<__value__> returned_values;
-
- __point__ pt(...);
- __box__ b(...);
-
- size_t n1 = rt.nearest(index::bounded(pt, index::to_furthest(1), 10), index::intersects(b), returned_value);
-
- size_t n2 = index::nearest(rt, pt, k, index::within(b), std::back_inserter(returned_values));
-
- BOOST_FOREACH(Value & v, rt | index::nearest_filtered(pt, k, index::covered_by(b)))
- ; // do something with v
-
-[endsect]
-
-[endsect] [/ Nearest neighbours queries /]
Deleted: sandbox-branches/geometry/index/doc/rtree/query.qbk
==============================================================================
--- sandbox-branches/geometry/index/doc/rtree/query.qbk 2012-11-21 10:47:51 EST (Wed, 21 Nov 2012)
+++ (empty file)
@@ -1,86 +0,0 @@
-[/============================================================================
- Boost.Geometry Index
-
- Copyright (c) 2011-2012 Adam Wulkiewicz.
-
- Use, modification and distribution is subject to the Boost Software License,
- Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
- http://www.boost.org/LICENSE_1_0.txt)
-=============================================================================/]
-
-[section Spatial queries]
-
-[section Basic queries]
-
-There are three ways to perform a spatial query. Following queries returns
-`__value__`s intersecting some box_region.
-
-Method call
-
- std::vector<__value__> returned_values;
- __box__ box_region(...);
- rt.query(box_region, std::back_inserter(returned_values));
-
-Function call
-
- std::vector<__value__> returned_values;
- __box__ box_region(...);
- index::query(rt, box_region, std::back_inserter(returned_values));
-
-Use of pipe operator generating a range
-
- __box__ box_region(...);
- BOOST_FOREACH(__value__ & v, rt | index::query_filtered(box_region))
- ; // do something with v
-[endsect]
-
-[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.
-
- rt.query(box, std::back_inserter(result)); // default case - intersects
- rt.query(index::intersects(box), std::back_inserter(result)); // same as default
- rt.query(index::covered_by(box), std::back_inserter(result));
- rt.query(index::disjont(box), std::back_inserter(result));
- rt.query(index::overlaps(box), std::back_inserter(result));
- rt.query(index::within(box), std::back_inserter(result));
-
-All predicates may be negated, e.g.:
-
- rt.query(index::not_intersects(box), std::back_inserter(result));
- // or
- rt.query(!index::intersects(box), std::back_inserter(result));
- // the same as
- rt.query(index::disjoint(box), std::back_inserter(result));
-
-It's possible to use some number of predicates by passing `std::pair<Pred1, Pred2>`
-
- rt.query(
- std::make_pair(index::intersects(box1), !index::within(box2))
- , std::back_inserter(result));
-
-or `boost::tuple<Pred1, Pred2, Pred3, ...>`
-
- rt.query(
- boost::make_tuple(
- index::intersects(box1), !index::within(box2), index::overlaps(box3))
- , std::back_inserter(result));
-
-There is also a unique predicate `index::value(...)` taking user-defined function/functor
-which checks if `__value__` should be returned by the query.
-
- bool fun(__value__ const& v)
- {
- return v.is_red();
- }
-
- // ...
-
- rt.query(
- boost::make_pair(index::intersects(box), index::value(fun))
- , std::back_inserter(result));
-
-[endsect]
-
-[endsect] [/ Spatial queries /]
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-21 10:47:51 EST (Wed, 21 Nov 2012)
@@ -31,14 +31,14 @@
[rtree_quickstart_insert]
-There are various types of queries that may be performed, they can be even combined together
+There are various types of spatial queries that may be performed, they can be even combined together
in one call. For simplicity, default one is used.
-[rtree_quickstart_query]
+[rtree_quickstart_spatial_query]
Default k-nearest neighbors query may be performed as follows.
-[rtree_quickstart_nearest]
+[rtree_quickstart_nearest_query]
[h3 More]
More information about the R-tree implementation, other algorithms and queries may be found in
Modified: sandbox-branches/geometry/index/doc/src/examples/rtree/quick_start.cpp
==============================================================================
--- sandbox-branches/geometry/index/doc/src/examples/rtree/quick_start.cpp (original)
+++ sandbox-branches/geometry/index/doc/src/examples/rtree/quick_start.cpp 2012-11-21 10:47:51 EST (Wed, 21 Nov 2012)
@@ -42,15 +42,15 @@
rtree.insert(std::make_pair(b, 0));
//]
- //[rtree_quickstart_query
+ //[rtree_quickstart_spatial_query
// find values intersecting a box
std::vector<value> result;
- rtree.query(b, std::back_inserter(result));
+ rtree.spatial_query(b, std::back_inserter(result));
//]
- //[rtree_quickstart_nearest
+ //[rtree_quickstart_nearest_query
// find 5 nearest values to a point
- rtree.nearest(point(0, 0), 5, std::back_inserter(result));
+ rtree.nearest_query(point(0, 0), 5, std::back_inserter(result));
//]
return 0;
Modified: sandbox-branches/geometry/index/test/geometry_index_test_common.hpp
==============================================================================
--- sandbox-branches/geometry/index/test/geometry_index_test_common.hpp (original)
+++ sandbox-branches/geometry/index/test/geometry_index_test_common.hpp 2012-11-21 10:47:51 EST (Wed, 21 Nov 2012)
@@ -11,6 +11,7 @@
#define GEOMETRY_TEST_GEOMETRY_INDEX_TEST_COMMON_HPP
#include <boost/geometry.hpp>
+#define BOOST_GEOMETRY_INDEX_ENABLE_DEBUG_INTERFACE
#include <boost/geometry/extensions/index/rtree/rtree.hpp>
#include <geometry_test_common.hpp>
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-21 10:47:51 EST (Wed, 21 Nov 2012)
@@ -37,5 +37,7 @@
[ run rtree3d_rstar_f.cpp ]
[ run rtree3d_rstar_d.cpp ]
[ run rtree3d_rstar_tt.cpp ]
+
+ [ run rtree_exceptions.cpp ]
;
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-21 10:47:51 EST (Wed, 21 Nov 2012)
@@ -149,11 +149,13 @@
struct generate_input<2>
{
template <typename Value, typename Box>
- static void apply(std::vector<Value> & input, Box & qbox)
+ static void apply(std::vector<Value> & input, Box & qbox, int size = 1)
{
- for ( int i = 0 ; i < 12 ; i += 3 )
+ assert(0 < size);
+
+ for ( int i = 0 ; i < 12 * size ; i += 3 )
{
- for ( int j = 1 ; j < 25 ; j += 4 )
+ for ( int j = 1 ; j < 25 * size ; j += 4 )
{
input.push_back( generate_value<Value>::apply(i, j) );
}
@@ -169,13 +171,15 @@
struct generate_input<3>
{
template <typename Value, typename Box>
- static void apply(std::vector<Value> & input, Box & qbox)
+ static void apply(std::vector<Value> & input, Box & qbox, int size = 1)
{
- for ( int i = 0 ; i < 12 ; i += 3 )
+ assert(0 < size);
+
+ for ( int i = 0 ; i < 12 * size ; i += 3 )
{
- for ( int j = 1 ; j < 25 ; j += 4 )
+ for ( int j = 1 ; j < 25 * size ; j += 4 )
{
- for ( int k = 2 ; k < 12 ; k += 5 )
+ for ( int k = 2 ; k < 12 * size ; k += 5 )
{
input.push_back( generate_value<Value>::apply(i, j, k) );
}
@@ -253,24 +257,24 @@
// spatial query
template <typename Rtree, typename Value, typename Predicates>
-void test_query(Rtree & rtree, Predicates const& pred, std::vector<Value> const& expected_output)
+void test_spatial_query(Rtree & rtree, Predicates const& pred, std::vector<Value> const& expected_output)
{
BOOST_CHECK( bgi::are_levels_ok(rtree) );
BOOST_CHECK( bgi::are_boxes_ok(rtree) );
std::vector<Value> output;
- size_t n = rtree.query(pred, std::back_inserter(output));
+ size_t n = rtree.spatial_query(pred, std::back_inserter(output));
BOOST_CHECK( expected_output.size() == n );
test_compare_outputs(rtree, output, expected_output);
std::vector<Value> output2;
- size_t n2 = query(rtree, pred, std::back_inserter(output2));
+ size_t n2 = spatial_query(rtree, pred, std::back_inserter(output2));
BOOST_CHECK( n == n2 );
test_exactly_the_same_outputs(rtree, output, output2);
- test_exactly_the_same_outputs(rtree, output, rtree | bgi::query_filtered(pred));
+ test_exactly_the_same_outputs(rtree, output, rtree | bgi::adaptors::spatial_queried(pred));
}
// rtree specific queries tests
@@ -284,11 +288,11 @@
if ( bg::intersects(tree.translator()(v), qbox) )
expected_output.push_back(v);
- test_query(tree, qbox, expected_output);
- test_query(tree, bgi::intersects(qbox), expected_output);
- test_query(tree, !bgi::not_intersects(qbox), expected_output);
- test_query(tree, !bgi::disjoint(qbox), expected_output);
- test_query(tree, bgi::not_disjoint(qbox), expected_output);
+ 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>
@@ -300,7 +304,7 @@
if ( bg::covered_by(tree.translator()(v), qbox) )
expected_output.push_back(v);
- test_query(tree, bgi::covered_by(qbox), expected_output);
+ test_spatial_query(tree, bgi::covered_by(qbox), expected_output);
}
template <typename Tag>
@@ -315,7 +319,7 @@
if ( bg::overlaps(tree.translator()(v), qbox) )
expected_output.push_back(v);
- test_query(tree, bgi::overlaps(qbox), expected_output);
+ test_spatial_query(tree, bgi::overlaps(qbox), expected_output);
}
};
@@ -357,7 +361,7 @@
// if ( bg::touches(tree.translator()(v), qbox) )
// expected_output.push_back(v);
//
-// test_query(tree, bgi::touches(qbox), expected_output);
+// test_spatial_query(tree, bgi::touches(qbox), expected_output);
// }
//};
//
@@ -383,13 +387,13 @@
if ( bg::within(tree.translator()(v), qbox) )
expected_output.push_back(v);
- test_query(tree, bgi::within(qbox), expected_output);
+ test_spatial_query(tree, bgi::within(qbox), expected_output);
}
// rtree nearest queries
template <typename Rtree, typename Value, typename Point>
-void test_nearest(Rtree const& rtree, std::vector<Value> const& input, Point const& pt)
+void test_nearest_query(Rtree const& rtree, std::vector<Value> const& input, Point const& pt)
{
// TODO: Nearest object may not be the same as found by the rtree if distances are equal
// Should all objects with the same closest distance be picked?
@@ -409,7 +413,7 @@
size_t n = ( (std::numeric_limits<D>::max)() == smallest_d ) ? 0 : 1;
Value output;
- size_t n_res = rtree.nearest(pt, output);
+ size_t n_res = rtree.nearest_query(pt, output);
BOOST_CHECK(n == n_res);
if ( n == n_res && 0 < n )
@@ -451,7 +455,7 @@
};
template <typename Rtree, typename Value, typename Point>
-void test_nearest_k(Rtree const& rtree, std::vector<Value> const& input, Point const& pt, size_t k)
+void test_nearest_query_k(Rtree const& rtree, std::vector<Value> const& input, Point const& pt, size_t k)
{
// TODO: Nearest object may not be the same as found by the rtree if distances are equal
// All objects with the same closest distance should be picked
@@ -485,7 +489,7 @@
// calculate output using rtree
std::vector<Value> output;
- rtree.nearest(pt, k, std::back_inserter(output));
+ rtree.nearest_query(pt, k, std::back_inserter(output));
// check output
bool are_sizes_ok = (expected_output.size() == output.size());
@@ -504,19 +508,21 @@
}
}
}
+
+ test_exactly_the_same_outputs(rtree, output, rtree | bgi::adaptors::nearest_queried(pt, k));
}
// rtree nearest not found
template <typename Rtree, typename Point, typename CoordinateType>
-void test_nearest_not_found(Rtree const& rtree, Point const& pt, CoordinateType max_distance_1, CoordinateType max_distance_k)
+void test_nearest_query_not_found(Rtree const& rtree, Point const& pt, CoordinateType max_distance_1, CoordinateType max_distance_k)
{
typename Rtree::value_type output;
- size_t n_res = rtree.nearest(bgi::max_bounded(pt, max_distance_1), output);
+ size_t n_res = rtree.nearest_query(bgi::max_bounded(pt, max_distance_1), output);
BOOST_CHECK(0 == n_res);
std::vector<typename Rtree::value_type> output_v;
- n_res = rtree.nearest(bgi::max_bounded(pt, max_distance_k), 5, std::back_inserter(output_v));
+ n_res = rtree.nearest_query(bgi::max_bounded(pt, max_distance_k), 5, std::back_inserter(output_v));
BOOST_CHECK(output_v.size() == n_res);
BOOST_CHECK(n_res < 5);
}
@@ -531,7 +537,7 @@
BOOST_CHECK(s);
std::vector<Value> expected_output;
- tree.query(qbox, std::back_inserter(expected_output));
+ tree.spatial_query(qbox, std::back_inserter(expected_output));
// copy constructor
bgi::rtree<Value, Algo> t1(tree);
@@ -539,7 +545,7 @@
BOOST_CHECK(tree.size() == t1.size());
std::vector<Value> output;
- t1.query(qbox, std::back_inserter(output));
+ t1.spatial_query(qbox, std::back_inserter(output));
test_exactly_the_same_outputs(t1, output, expected_output);
// copying assignment operator
@@ -548,7 +554,7 @@
BOOST_CHECK(tree.size() == t1.size());
output.clear();
- t1.query(qbox, std::back_inserter(output));
+ t1.spatial_query(qbox, std::back_inserter(output));
test_exactly_the_same_outputs(t1, output, expected_output);
// moving constructor
@@ -558,7 +564,7 @@
BOOST_CHECK(t1.size() == 0);
output.clear();
- t2.query(qbox, std::back_inserter(output));
+ t2.spatial_query(qbox, std::back_inserter(output));
test_exactly_the_same_outputs(t2, output, expected_output);
// moving assignment operator
@@ -568,7 +574,7 @@
BOOST_CHECK(t2.size() == 0);
output.clear();
- t1.query(qbox, std::back_inserter(output));
+ t1.spatial_query(qbox, std::back_inserter(output));
test_exactly_the_same_outputs(t1, output, expected_output);
}
@@ -580,7 +586,7 @@
size_t prev_size = tree.size();
std::vector<Value> output;
- tree.query(qbox, std::back_inserter(output));
+ tree.spatial_query(qbox, std::back_inserter(output));
BOOST_CHECK(0 < output.size());
@@ -589,7 +595,7 @@
BOOST_CHECK(tree.size() == prev_size - output.size());
output.clear();
- tree.query(qbox, std::back_inserter(output));
+ tree.spatial_query(qbox, std::back_inserter(output));
BOOST_CHECK(0 == output.size());
}
@@ -619,9 +625,9 @@
P pt;
bg::centroid(qbox, pt);
- test_nearest(tree, input, pt);
- test_nearest_k(tree, input, pt, 10);
- test_nearest_not_found(tree, generate_outside_point<P>::apply(), 1, 3);
+ test_nearest_query(tree, input, pt);
+ test_nearest_query_k(tree, input, pt, 10);
+ test_nearest_query_not_found(tree, generate_outside_point<P>::apply(), 1, 3);
test_copy_assignment_move(tree, qbox);
Modified: sandbox-branches/geometry/index/tests/additional_speed.cpp
==============================================================================
--- sandbox-branches/geometry/index/tests/additional_speed.cpp (original)
+++ sandbox-branches/geometry/index/tests/additional_speed.cpp 2012-11-21 10:47:51 EST (Wed, 21 Nov 2012)
@@ -48,9 +48,9 @@
typedef bg::model::box<P> B;
//typedef bgi::rtree<B, bgi::linear<32, 8> > RT;
//typedef bgi::rtree<B, bgi::runtime::linear > RT;
- typedef bgi::rtree<B, bgi::quadratic<32, 8> > RT;
+ //typedef bgi::rtree<B, bgi::quadratic<32, 8> > RT;
// typedef bgi::rtree<B, bgi::runtime::quadratic > RT;
- //typedef bgi::rtree<B, bgi::rstar<32, 8> > RT;
+ typedef bgi::rtree<B, bgi::rstar<32, 8> > RT;
//typedef bgi::rtree<B, bgi::runtime::rstar > RT;
for ( ;; )
@@ -97,7 +97,7 @@
float x = coords[i].first;
float y = coords[i].second;
result.clear();
- t.query(B(P(x - 10, y - 10), P(x + 10, y + 10)), std::back_inserter(result));
+ t.spatial_query(B(P(x - 10, y - 10), P(x + 10, y + 10)), std::back_inserter(result));
temp += result.size();
}
std::cout << "time: " << tim.elapsed() << "s\n";
@@ -117,7 +117,7 @@
float x = coords[i].first + 100;
float y = coords[i].second + 100;
result.clear();
- temp += t.nearest(P(x, y), 5, std::back_inserter(result));
+ temp += t.nearest_query(P(x, y), 5, std::back_inserter(result));
}
std::cout << "time: " << tim.elapsed() << "s\n";
std::cout << "found: " << temp << "\n";
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
