|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r80771 - in sandbox-branches/geometry/index_dev: 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 test/rtree
From: adam.wulkiewicz_at_[hidden]
Date: 2012-09-30 07:11:52
Author: awulkiew
Date: 2012-09-30 07:11:50 EDT (Sun, 30 Sep 2012)
New Revision: 80771
URL: http://svn.boost.org/trac/boost/changeset/80771
Log:
NodeProxy used in visitors instead of Parameters, Translator and Allocators.
Text files modified:
sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/linear/redistribute_elements.hpp | 95 +++++++++----------
sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/node/node.hpp | 28 -----
sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/node_proxy.hpp | 60 ++++++++++--
sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/quadratic/redistribute_elements.hpp | 67 ++++++-------
sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/rstar/choose_next_node.hpp | 31 +++---
sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/rstar/insert.hpp | 157 ++++++++++++++-----------------
sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/rstar/redistribute_elements.hpp | 200 ++++++++++++++++++++-------------------
sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/rtree.hpp | 67 +++++++-----
sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/visitors/are_boxes_ok.hpp | 53 ++++++----
sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/visitors/are_levels_ok.hpp | 40 ++++---
sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/visitors/children_box.hpp | 28 +++--
sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/visitors/copy.hpp | 27 +++--
sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/visitors/destroy.hpp | 27 +++--
sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/visitors/insert.hpp | 155 +++++++++++++++---------------
sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/visitors/is_leaf.hpp | 16 ++
sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/visitors/nearest.hpp | 59 ++++++-----
sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/visitors/query.hpp | 39 +++++--
sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/visitors/remove.hpp | 68 ++++++-------
sandbox-branches/geometry/index_dev/test/rtree/test_rtree.hpp | 24 ++--
19 files changed, 654 insertions(+), 587 deletions(-)
Modified: sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/linear/redistribute_elements.hpp
==============================================================================
--- sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/linear/redistribute_elements.hpp (original)
+++ sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/linear/redistribute_elements.hpp 2012-09-30 07:11:50 EDT (Sun, 30 Sep 2012)
@@ -40,34 +40,33 @@
// from void find_normalized_separations(std::vector<Box> const& boxes, T& separation, unsigned int& first, unsigned int& second) const
-template <typename Elements, typename Parameters, typename Translator, size_t DimensionIndex>
+template <typename Elements, typename NodeProxy, size_t DimensionIndex>
struct find_greatest_normalized_separation
{
typedef typename Elements::value_type element_type;
- typedef typename rtree::element_indexable_type<element_type, Translator>::type indexable_type;
+ typedef typename rtree::element_indexable_type<element_type, typename NodeProxy::translator_type>::type indexable_type;
typedef typename index::traits::coordinate_type<indexable_type>::type coordinate_type;
static inline void apply(Elements const& elements,
- Parameters const& parameters,
- Translator const& translator,
+ NodeProxy const& node_proxy,
coordinate_type & separation,
size_t & seed1,
size_t & seed2)
{
- const size_t elements_count = parameters.get_max_elements() + 1;
+ const size_t elements_count = node_proxy.parameters().get_max_elements() + 1;
BOOST_GEOMETRY_INDEX_ASSERT(elements.size() == elements_count, "unexpected number of elements");
BOOST_GEOMETRY_INDEX_ASSERT(2 <= elements_count, "unexpected number of elements");
// find the lowest low, highest high
- coordinate_type lowest_low = index::get<min_corner, DimensionIndex>(rtree::element_indexable(elements[0], translator));
- coordinate_type highest_high = index::get<max_corner, DimensionIndex>(rtree::element_indexable(elements[0], translator));
+ coordinate_type lowest_low = index::get<min_corner, DimensionIndex>(node_proxy.indexable(elements[0]));
+ coordinate_type highest_high = index::get<max_corner, DimensionIndex>(node_proxy.indexable(elements[0]));
// and the lowest high
coordinate_type lowest_high = highest_high;
size_t lowest_high_index = 0;
for ( size_t i = 1 ; i < elements_count ; ++i )
{
- coordinate_type min_coord = index::get<min_corner, DimensionIndex>(rtree::element_indexable(elements[i], translator));
- coordinate_type max_coord = index::get<max_corner, DimensionIndex>(rtree::element_indexable(elements[i], translator));
+ coordinate_type min_coord = index::get<min_corner, DimensionIndex>(node_proxy.indexable(elements[i]));
+ coordinate_type max_coord = index::get<max_corner, DimensionIndex>(node_proxy.indexable(elements[i]));
if ( max_coord < lowest_high )
{
@@ -84,10 +83,10 @@
// find the highest low
size_t highest_low_index = lowest_high_index == 0 ? 1 : 0;
- coordinate_type highest_low = index::get<min_corner, DimensionIndex>(rtree::element_indexable(elements[highest_low_index], translator));
+ coordinate_type highest_low = index::get<min_corner, DimensionIndex>(node_proxy.indexable(elements[highest_low_index]));
for ( size_t i = highest_low_index ; i < elements_count ; ++i )
{
- coordinate_type min_coord = index::get<min_corner, DimensionIndex>(rtree::element_indexable(elements[i], translator));
+ coordinate_type min_coord = index::get<min_corner, DimensionIndex>(node_proxy.indexable(elements[i]));
if ( highest_low < min_coord &&
i != lowest_high_index )
{
@@ -117,27 +116,26 @@
}
};
-template <typename Elements, typename Parameters, typename Translator, size_t Dimension>
+template <typename Elements, typename NodeProxy, size_t Dimension>
struct pick_seeds_impl
{
BOOST_STATIC_ASSERT(0 < Dimension);
typedef typename Elements::value_type element_type;
- typedef typename rtree::element_indexable_type<element_type, Translator>::type indexable_type;
+ typedef typename rtree::element_indexable_type<element_type, typename NodeProxy::translator_type>::type indexable_type;
typedef typename index::traits::coordinate_type<indexable_type>::type coordinate_type;
static inline void apply(Elements const& elements,
- Parameters const& parameters,
- Translator const& tr,
+ NodeProxy const& node_proxy,
coordinate_type & separation,
size_t & seed1,
size_t & seed2)
{
- pick_seeds_impl<Elements, Parameters, Translator, Dimension - 1>::apply(elements, parameters, tr, separation, seed1, seed2);
+ pick_seeds_impl<Elements, NodeProxy, Dimension - 1>::apply(elements, node_proxy, separation, seed1, seed2);
coordinate_type current_separation;
size_t s1, s2;
- find_greatest_normalized_separation<Elements, Parameters, Translator, Dimension - 1>::apply(elements, parameters, tr, current_separation, s1, s2);
+ find_greatest_normalized_separation<Elements, NodeProxy, Dimension - 1>::apply(elements, node_proxy, current_separation, s1, s2);
// in the old implementation different operator was used: <= (y axis prefered)
if ( separation < current_separation )
@@ -149,43 +147,41 @@
}
};
-template <typename Elements, typename Parameters, typename Translator>
-struct pick_seeds_impl<Elements, Parameters, Translator, 1>
+template <typename Elements, typename NodeProxy>
+struct pick_seeds_impl<Elements, NodeProxy, 1>
{
typedef typename Elements::value_type element_type;
- typedef typename rtree::element_indexable_type<element_type, Translator>::type indexable_type;
+ typedef typename rtree::element_indexable_type<element_type, typename NodeProxy::translator_type>::type indexable_type;
typedef typename index::traits::coordinate_type<indexable_type>::type coordinate_type;
static inline void apply(Elements const& elements,
- Parameters const& parameters,
- Translator const& tr,
+ NodeProxy const& node_proxy,
coordinate_type & separation,
size_t & seed1,
size_t & seed2)
{
- find_greatest_normalized_separation<Elements, Parameters, Translator, 0>::apply(elements, parameters, tr, separation, seed1, seed2);
+ find_greatest_normalized_separation<Elements, NodeProxy, 0>::apply(elements, node_proxy, separation, seed1, seed2);
}
};
// from void linear_pick_seeds(node_pointer const& n, unsigned int &seed1, unsigned int &seed2) const
-template <typename Elements, typename Parameters, typename Translator>
+template <typename Elements, typename NodeProxy>
struct pick_seeds
{
typedef typename Elements::value_type element_type;
- typedef typename rtree::element_indexable_type<element_type, Translator>::type indexable_type;
+ typedef typename rtree::element_indexable_type<element_type, typename NodeProxy::translator_type>::type indexable_type;
typedef typename index::traits::coordinate_type<indexable_type>::type coordinate_type;
static const size_t dimension = index::traits::dimension<indexable_type>::value;
static inline void apply(Elements const& elements,
- Parameters const& parameters,
- Translator const& tr,
+ NodeProxy const& node_proxy,
size_t & seed1,
size_t & seed2)
{
coordinate_type separation = 0;
- pick_seeds_impl<Elements, Parameters, Translator, dimension>::apply(elements, parameters, tr, separation, seed1, seed2);
+ pick_seeds_impl<Elements, NodeProxy, dimension>::apply(elements, node_proxy, separation, seed1, seed2);
}
};
@@ -193,32 +189,30 @@
// from void split_node(node_pointer const& n, node_pointer& n1, node_pointer& n2) const
-template <typename Value, typename Options, typename Translator, typename Box, typename Allocators>
-struct redistribute_elements<Value, Options, Translator, Box, Allocators, linear_tag>
+template <typename Value, typename NodeProxy>
+struct redistribute_elements<Value, NodeProxy, linear_tag>
{
- 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 NodeProxy::node node;
+ typedef typename NodeProxy::internal_node internal_node;
+ typedef typename NodeProxy::leaf leaf;
+ typedef typename NodeProxy::box_type box_type;
template <typename Node>
static inline void apply(Node & n,
Node & second_node,
- Box & box1,
- Box & box2,
- parameters_type const& parameters,
- Translator const& translator)
+ box_type & box1,
+ box_type & box2,
+ NodeProxy const& node_proxy)
{
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 rtree::element_indexable_type<element_type, typename NodeProxy::translator_type>::type indexable_type;
typedef typename index::traits::coordinate_type<indexable_type>::type coordinate_type;
- typedef typename index::default_content_result<Box>::type content_type;
+ typedef typename index::default_content_result<box_type>::type content_type;
elements_type & elements1 = rtree::elements(n);
elements_type & elements2 = rtree::elements(second_node);
- const size_t elements1_count = parameters.get_max_elements() + 1;
+ const size_t elements1_count = node_proxy.parameters().get_max_elements() + 1;
BOOST_GEOMETRY_INDEX_ASSERT(elements1.size() == elements1_count, "unexpected number of elements");
@@ -228,7 +222,7 @@
// 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, NodeProxy>::apply(elements_copy, node_proxy, seed1, seed2);
// prepare nodes' elements containers
elements1.clear();
@@ -239,8 +233,8 @@
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);
+ geometry::convert(node_proxy.indexable(elements_copy[seed1]), box1);
+ geometry::convert(node_proxy.indexable(elements_copy[seed2]), box2);
// initialize areas
content_type content1 = index::content(box1);
@@ -255,17 +249,18 @@
if (i != seed1 && i != seed2)
{
element_type const& elem = elements_copy[i];
- indexable_type const& indexable = rtree::element_indexable(elem, translator);
+ // TODO - here indexable by value may be returned
+ indexable_type const& indexable = node_proxy.indexable(elem);
// 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() )
+ if ( elements1.size() + remaining <= node_proxy.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() )
+ else if ( elements2.size() + remaining <= node_proxy.parameters().get_min_elements() )
{
elements2.push_back(elem);
geometry::expand(box2, indexable);
@@ -275,8 +270,8 @@
else
{
// calculate enlarged boxes and areas
- Box enlarged_box1(box1);
- Box enlarged_box2(box2);
+ box_type enlarged_box1(box1);
+ box_type enlarged_box2(box2);
geometry::expand(enlarged_box1, indexable);
geometry::expand(enlarged_box2, indexable);
content_type enlarged_content1 = index::content(enlarged_box1);
Modified: sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/node/node.hpp
==============================================================================
--- sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/node/node.hpp (original)
+++ sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/node/node.hpp 2012-09-30 07:11:50 EDT (Sun, 30 Sep 2012)
@@ -18,32 +18,4 @@
#include <boost/geometry/extensions/index/rtree/node/node_d_mem_static.hpp>
#include <boost/geometry/extensions/index/rtree/node/node_s_mem_static.hpp>
-#include <boost/geometry/algorithms/expand.hpp>
-
-namespace boost { namespace geometry { namespace index {
-
-namespace detail { namespace rtree {
-
-// elements box
-
-template <typename Box, typename FwdIter, typename Translator>
-inline Box elements_box(FwdIter first, FwdIter last, Translator const& tr)
-{
- BOOST_GEOMETRY_INDEX_ASSERT(first != last, "Can't calculate element's box");
-
- Box result;
-
- geometry::convert(element_indexable(*first, tr), result);
- ++first;
-
- for ( ; first != last ; ++first )
- geometry::expand(result, element_indexable(*first, tr));
-
- return result;
-}
-
-}} // namespace detail::rtree
-
-}}} // namespace boost::geometry::index
-
#endif // BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_NODE_NODE_HPP
Modified: sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/node_proxy.hpp
==============================================================================
--- sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/node_proxy.hpp (original)
+++ sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/node_proxy.hpp 2012-09-30 07:11:50 EDT (Sun, 30 Sep 2012)
@@ -51,33 +51,68 @@
value_type, parameters_type, box_type, allocators_type, node_tag
>::type leaf;
- node_proxy(Parameters parameters, translator_type const& translator, Allocator allocator)
+ node_proxy(parameters_type const& parameters, translator_type const& translator, Allocator allocator)
: m_parameters(parameters)
, m_translator(translator)
, m_allocators(allocator)
{}
template <typename Node>
- node * create_node()
+ node * create()
{
return detail::rtree::create_node<allocators_type, Node>::apply(m_allocators);
}
template <typename Node>
- void destroy_node(node * n)
+ void destroy(node * n)
{
return detail::rtree::destroy_node<allocators_type, Node>::apply(m_allocators, n);
}
- template <typename Visitor>
- void apply_visitor(Visitor & visitor, node * n) const
+ // HMMMM - trzeba zwracac uwage na translator::return_type
+// template <typename Element>
+// typename element_indexable_type<Element>::type const&
+// rtree::element_indexable(m_element, m_translator));
+
+ typename translator_type::result_type
+ indexable(value_type const& v) const
{
- detail::rtree::apply_visitor(visitor, *n);
+ return m_translator(v);
}
- indexable_type const& translate(value_type const& v) const
+ typename element_indexable_type<
+ typename internal_node::elements_type::value_type,
+ translator_type
+ >::type const&
+ indexable(typename internal_node::elements_type::value_type const& el) const
{
- return m_translator(v);
+ return element_indexable(el, m_translator);
+ }
+
+ bool equals(value_type const& v1, value_type const& v2) const
+ {
+ return m_translator.equals(v1, v2);
+ }
+
+ template <typename FwdIter>
+ box_type elements_box(FwdIter first, FwdIter last) const
+ {
+ BOOST_GEOMETRY_INDEX_ASSERT(first != last, "Can't calculate element's box");
+
+ box_type result;
+
+ geometry::convert(element_indexable(*first, m_translator), result);
+ ++first;
+
+ for ( ; first != last ; ++first )
+ geometry::expand(result, element_indexable(*first, m_translator));
+
+ return result;
+ }
+
+ parameters_type const& parameters() const
+ {
+ return m_parameters;
}
translator_type const& translator() const
@@ -85,12 +120,17 @@
return m_translator;
}
+ allocator_type allocator() const
+ {
+ return m_allocators.allocator;
+ }
+
private:
- Parameters m_parameters;
+ parameters_type m_parameters;
translator_type m_translator;
allocators_type m_allocators;
};
-}}} // namespace boost::geometry::index::detail::rtree
+}}}}} // namespace boost::geometry::index::detail::rtree
#endif // BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_NODE_PROXY_HPP
Modified: sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/quadratic/redistribute_elements.hpp
==============================================================================
--- sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/quadratic/redistribute_elements.hpp (original)
+++ sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/quadratic/redistribute_elements.hpp 2012-09-30 07:11:50 EDT (Sun, 30 Sep 2012)
@@ -28,22 +28,21 @@
namespace quadratic {
-template <typename Elements, typename Parameters, typename Translator, typename Box>
+template <typename Elements, typename NodeProxy>
struct pick_seeds
{
typedef typename Elements::value_type element_type;
- typedef typename rtree::element_indexable_type<element_type, Translator>::type indexable_type;
+ typedef typename rtree::element_indexable_type<element_type, typename NodeProxy::translator_type>::type indexable_type;
typedef typename index::traits::coordinate_type<indexable_type>::type coordinate_type;
- typedef Box box_type;
+ typedef typename NodeProxy::box_type box_type;
typedef typename index::default_content_result<box_type>::type content_type;
static inline void apply(Elements const& elements,
- Parameters const& parameters,
- Translator const& tr,
+ NodeProxy const& node_proxy,
size_t & seed1,
size_t & seed2)
{
- const size_t elements_count = parameters.get_max_elements() + 1;
+ const size_t elements_count = node_proxy.parameters().get_max_elements() + 1;
BOOST_GEOMETRY_INDEX_ASSERT(elements.size() == elements_count, "wrong number of elements");
BOOST_GEOMETRY_INDEX_ASSERT(2 <= elements_count, "unexpected number of elements");
@@ -55,8 +54,8 @@
{
for ( size_t j = i + 1 ; j < elements_count ; ++j )
{
- indexable_type const& ind1 = rtree::element_indexable(elements[i], tr);
- indexable_type const& ind2 = rtree::element_indexable(elements[j], tr);
+ indexable_type const& ind1 = node_proxy.indexable(elements[i]);
+ indexable_type const& ind2 = node_proxy.indexable(elements[j]);
box_type enlarged_box;
geometry::convert(ind1, enlarged_box);
@@ -77,33 +76,31 @@
} // namespace quadratic
-template <typename Value, typename Options, typename Translator, typename Box, typename Allocators>
-struct redistribute_elements<Value, Options, Translator, Box, Allocators, quadratic_tag>
+template <typename Value, typename NodeProxy>
+struct redistribute_elements<Value, NodeProxy, quadratic_tag>
{
- typedef typename Options::parameters_type parameters_type;
+ typedef typename NodeProxy::node node;
+ typedef typename NodeProxy::internal_node internal_node;
+ typedef typename NodeProxy::leaf leaf;
+ typedef typename NodeProxy::box_type box_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 index::default_content_result<Box>::type content_type;
+ typedef typename index::default_content_result<box_type>::type content_type;
template <typename Node>
static inline void apply(Node & n,
Node & second_node,
- Box & box1,
- Box & box2,
- parameters_type const& parameters,
- Translator const& translator)
+ box_type & box1,
+ box_type & box2,
+ NodeProxy const& node_proxy)
{
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 rtree::element_indexable_type<element_type, typename NodeProxy::translator_type>::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;
+ const size_t elements1_count = node_proxy.parameters().get_max_elements() + 1;
BOOST_GEOMETRY_INDEX_ASSERT(elements1.size() == elements1_count, "unexpected elements number");
@@ -113,7 +110,7 @@
// 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, NodeProxy>::apply(elements_copy, node_proxy, seed1, seed2);
// prepare nodes' elements containers
elements1.clear();
@@ -124,8 +121,8 @@
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);
+ geometry::convert(node_proxy.indexable(elements_copy[seed1]), box1);
+ geometry::convert(node_proxy.indexable(elements_copy[seed2]), box2);
// remove seeds
if (seed1 < seed2)
@@ -156,11 +153,11 @@
// 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() )
+ if ( elements1_count + remaining <= node_proxy.parameters().get_min_elements() )
{
insert_into_group1 = true;
}
- else if ( elements2_count + remaining <= parameters.get_min_elements() )
+ else if ( elements2_count + remaining <= node_proxy.parameters().get_min_elements() )
{
insert_into_group1 = false;
}
@@ -171,7 +168,7 @@
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,
+ box1, box2, content1, content2, node_proxy,
content_increase1, content_increase2);
if ( content_increase1 < content_increase2 ||
@@ -188,7 +185,7 @@
// move element to the choosen group
element_type const& elem = *el_it;
- indexable_type const& indexable = rtree::element_indexable(elem, translator);
+ indexable_type const& indexable = node_proxy.indexable(elem);
if ( insert_into_group1 )
{
@@ -216,13 +213,13 @@
template <typename It>
static inline It pick_next(It first, It last,
- Box const& box1, Box const& box2,
+ box_type const& box1, box_type const& box2,
content_type const& content1, content_type const& content2,
- Translator const& translator,
+ NodeProxy const& node_proxy,
content_type & out_content_increase1, content_type & out_content_increase2)
{
typedef typename boost::iterator_value<It>::type element_type;
- typedef typename rtree::element_indexable_type<element_type, Translator>::type indexable_type;
+ typedef typename rtree::element_indexable_type<element_type, typename NodeProxy::translator_type>::type indexable_type;
content_type greatest_content_incrase_diff = 0;
It out_it = first;
@@ -232,11 +229,11 @@
// find element with greatest difference between increased group's boxes areas
for ( It el_it = first ; el_it != last ; ++el_it )
{
- indexable_type const& indexable = rtree::element_indexable(*el_it, translator);
+ indexable_type const& indexable = node_proxy.indexable(*el_it);
// calculate enlarged boxes and areas
- Box enlarged_box1(box1);
- Box enlarged_box2(box2);
+ box_type enlarged_box1(box1);
+ box_type enlarged_box2(box2);
geometry::expand(enlarged_box1, indexable);
geometry::expand(enlarged_box2, indexable);
content_type enlarged_content1 = index::content(enlarged_box1);
Modified: sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/rstar/choose_next_node.hpp
==============================================================================
--- sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/rstar/choose_next_node.hpp (original)
+++ sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/rstar/choose_next_node.hpp 2012-09-30 07:11:50 EDT (Sun, 30 Sep 2012)
@@ -28,25 +28,24 @@
namespace detail {
-template <typename Value, typename Options, typename Box, typename Allocators>
-class choose_next_node<Value, Options, Box, Allocators, choose_by_overlap_diff_tag>
+template <typename Value, typename NodeProxy>
+class choose_next_node<Value, NodeProxy, choose_by_overlap_diff_tag>
{
- typedef typename rtree::node<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type node;
- typedef typename rtree::internal_node<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type internal_node;
- typedef typename rtree::leaf<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type leaf;
+ typedef typename NodeProxy::node node;
+ typedef typename NodeProxy::internal_node internal_node;
+ typedef typename NodeProxy::leaf leaf;
+ typedef typename NodeProxy::box_type box_type;
typedef typename rtree::elements_type<internal_node>::type children_type;
typedef typename children_type::value_type child_type;
- typedef typename Options::parameters_type parameters_type;
-
- typedef typename index::default_content_result<Box>::type content_type;
+ typedef typename index::default_content_result<box_type>::type content_type;
public:
template <typename Indexable>
static inline size_t apply(internal_node & n,
Indexable const& indexable,
- parameters_type const& parameters,
+ NodeProxy const& node_proxy,
size_t node_relative_level)
{
children_type & children = rtree::elements(n);
@@ -54,9 +53,9 @@
// children are leafs
if ( node_relative_level <= 1 )
{
- if ( 0 < parameters.get_overlap_cost_threshold() &&
- parameters.get_overlap_cost_threshold() < children.size() )
- return choose_by_nearly_minimum_overlap_cost(children, indexable, parameters.get_overlap_cost_threshold());
+ if ( 0 < node_proxy.parameters().get_overlap_cost_threshold() &&
+ node_proxy.parameters().get_overlap_cost_threshold() < children.size() )
+ return choose_by_nearly_minimum_overlap_cost(children, indexable, node_proxy.parameters().get_overlap_cost_threshold());
else
return choose_by_minimum_overlap_cost(children, indexable);
}
@@ -83,7 +82,7 @@
{
child_type const& ch_i = children[i];
- Box box_exp(ch_i.first);
+ box_type box_exp(ch_i.first);
// calculate expanded box of child node ch_i
geometry::expand(box_exp, indexable);
@@ -137,7 +136,7 @@
child_type const& ch_i = children[i];
// expanded child node's box
- Box box_exp(ch_i.first);
+ box_type box_exp(ch_i.first);
geometry::expand(box_exp, indexable);
// areas difference
@@ -164,7 +163,7 @@
typedef typename children_type::value_type child_type;
child_type const& ch_i = children[child_index];
- Box box_exp(ch_i.first);
+ box_type box_exp(ch_i.first);
// calculate expanded box of child node ch_i
geometry::expand(box_exp, indexable);
@@ -218,7 +217,7 @@
child_type const& ch_i = children[i];
// expanded child node's box
- Box box_exp(ch_i.first);
+ box_type box_exp(ch_i.first);
geometry::expand(box_exp, indexable);
// areas difference
Modified: sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/rstar/insert.hpp
==============================================================================
--- sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/rstar/insert.hpp (original)
+++ sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/rstar/insert.hpp 2012-09-30 07:11:50 EDT (Sun, 30 Sep 2012)
@@ -21,34 +21,32 @@
namespace rstar {
-template <typename Value, typename Options, typename Translator, typename Box, typename Allocators>
+template <typename Value, typename NodeProxy>
class remove_elements_to_reinsert
{
public:
- typedef typename rtree::node<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type node;
- typedef typename rtree::internal_node<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type internal_node;
- typedef typename rtree::leaf<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type leaf;
-
- typedef typename Options::parameters_type parameters_type;
+ typedef typename NodeProxy::node node;
+ typedef typename NodeProxy::internal_node internal_node;
+ typedef typename NodeProxy::leaf leaf;
+ typedef typename NodeProxy::box_type box_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,
- parameters_type const& parameters,
- Translator const& translator)
+ NodeProxy const& node_proxy)
{
typedef typename rtree::elements_type<Node>::type elements_type;
typedef typename elements_type::value_type element_type;
- typedef typename geometry::point_type<Box>::type point_type;
+ typedef typename geometry::point_type<box_type>::type point_type;
// 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);
- 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 = node_proxy.parameters().get_max_elements() + 1;
+ const size_t reinserted_elements_count = node_proxy.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");
@@ -67,8 +65,7 @@
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( node_proxy.indexable(elements[i]), element_center);
sorted_elements[i].first = geometry::comparable_distance(node_center, element_center);
sorted_elements[i].second = elements[i];
}
@@ -109,42 +106,42 @@
}
};
-template <size_t InsertIndex, typename Element, typename Value, typename Options, typename Box, typename Allocators>
+template <size_t InsertIndex, typename Element, typename Value, typename NodeProxy>
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
+ typename NodeProxy::internal_node
>::type type;
};
-template <typename Value, typename Options, typename Box, typename Allocators>
-struct level_insert_elements_type<0, Value, Value, Options, Box, Allocators>
+template <typename Value, typename NodeProxy>
+struct level_insert_elements_type<0, Value, Value, NodeProxy>
{
typedef typename rtree::elements_type<
- typename rtree::leaf<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type
+ typename NodeProxy::leaf
>::type type;
};
-template <size_t InsertIndex, typename Element, typename Value, typename Options, typename Translator, typename Box, typename Allocators>
+template <size_t InsertIndex, typename Element, typename Value, typename NodeProxy>
struct level_insert_base
- : public detail::insert<Element, Value, Options, Translator, Box, Allocators>
+ : public detail::insert<
+ Element,
+ Value,
+ NodeProxy>
{
- typedef detail::insert<Element, Value, Options, Translator, Box, Allocators> base;
+ typedef detail::insert<Element, Value, NodeProxy> 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;
+ typedef typename level_insert_elements_type<InsertIndex, Element, Value, NodeProxy>::type elements_type;
inline level_insert_base(node* & root,
size_t & leafs_level,
Element const& element,
- parameters_type const& parameters,
- Translator const& translator,
- Allocators & allocators,
+ NodeProxy & node_proxy,
size_t relative_level)
- : base(root, leafs_level, element, parameters, translator, allocators, relative_level)
+ : base(root, leafs_level, element, node_proxy, relative_level)
, result_relative_level(0)
{}
@@ -156,15 +153,15 @@
result_relative_level = base::m_leafs_level - base::m_current_level;
// overflow
- if ( base::m_parameters.get_max_elements() < rtree::elements(n).size() )
+ if ( base::m_node_proxy.parameters().get_max_elements() < rtree::elements(n).size() )
{
// node isn't root node
if ( base::m_parent )
{
- rstar::remove_elements_to_reinsert<Value, Options, Translator, Box, Allocators>::apply(
+ rstar::remove_elements_to_reinsert<Value, NodeProxy>::apply(
result_elements, n,
base::m_parent, base::m_current_child_index,
- base::m_parameters, base::m_translator);
+ base::m_node_proxy);
}
// node is root node
else
@@ -179,20 +176,20 @@
inline void handle_possible_split(Node &n) const
{
// overflow
- if ( base::m_parameters.get_max_elements() < rtree::elements(n).size() )
+ if ( base::m_node_proxy.parameters().get_max_elements() < rtree::elements(n).size() )
{
- base::split(n);
+ base::split(n);
}
}
template <typename Node>
inline void recalculate_aabb_if_necessary(Node &n) const
{
- if ( !result_elements.empty() && base::m_parent )
+ if ( !result_elements.empty() && this->m_parent )
{
// calulate node's new box
rtree::elements(*base::m_parent)[base::m_current_child_index].first =
- elements_box<Box>(rtree::elements(n).begin(), rtree::elements(n).end(), base::m_translator);
+ base::m_node_proxy.elements_box(rtree::elements(n).begin(), rtree::elements(n).end());
}
}
@@ -200,25 +197,21 @@
elements_type result_elements;
};
-template <size_t InsertIndex, typename Element, typename Value, typename Options, typename Translator, typename Box, typename Allocators>
+template <size_t InsertIndex, typename Element, typename Value, typename NodeProxy>
struct level_insert
- : public level_insert_base<InsertIndex, Element, Value, Options, Translator, Box, Allocators>
+ : public level_insert_base<InsertIndex, Element, Value, NodeProxy>
{
- typedef level_insert_base<InsertIndex, Element, Value, Options, Translator, Box, Allocators> base;
+ typedef level_insert_base<InsertIndex, Element, Value, NodeProxy> base;
typedef typename base::node node;
typedef typename base::internal_node internal_node;
typedef typename base::leaf leaf;
- typedef typename Options::parameters_type parameters_type;
-
inline level_insert(node* & root,
size_t & leafs_level,
Element const& element,
- parameters_type const& parameters,
- Translator const& translator,
- Allocators & allocators,
+ NodeProxy & node_proxy,
size_t relative_level)
- : base(root, leafs_level, element, parameters, translator, allocators, relative_level)
+ : base(root, leafs_level, element, node_proxy, relative_level)
{}
inline void operator()(internal_node & n)
@@ -269,25 +262,21 @@
}
};
-template <size_t InsertIndex, typename Value, typename Options, typename Translator, typename Box, typename Allocators>
-struct level_insert<InsertIndex, Value, Value, Options, Translator, Box, Allocators>
- : public level_insert_base<InsertIndex, Value, Value, Options, Translator, Box, Allocators>
+template <size_t InsertIndex, typename Value, typename NodeProxy>
+struct level_insert<InsertIndex, Value, Value, NodeProxy>
+ : public level_insert_base<InsertIndex, Value, Value, NodeProxy>
{
- typedef level_insert_base<InsertIndex, Value, Value, Options, Translator, Box, Allocators> base;
+ typedef level_insert_base<InsertIndex, Value, Value, NodeProxy> base;
typedef typename base::node node;
typedef typename base::internal_node internal_node;
typedef typename base::leaf leaf;
- typedef typename Options::parameters_type parameters_type;
-
inline level_insert(node* & root,
size_t & leafs_level,
Value const& v,
- parameters_type const& parameters,
- Translator const& translator,
- Allocators & allocators,
+ NodeProxy & node_proxy,
size_t relative_level)
- : base(root, leafs_level, v, parameters, translator, allocators, relative_level)
+ : base(root, leafs_level, v, node_proxy, relative_level)
{}
inline void operator()(internal_node & n)
@@ -319,25 +308,21 @@
}
};
-template <typename Value, typename Options, typename Translator, typename Box, typename Allocators>
-struct level_insert<0, Value, Value, Options, Translator, Box, Allocators>
- : public level_insert_base<0, Value, Value, Options, Translator, Box, Allocators>
+template <typename Value, typename NodeProxy>
+struct level_insert<0, Value, Value, NodeProxy>
+ : public level_insert_base<0, Value, Value, NodeProxy>
{
- typedef level_insert_base<0, Value, Value, Options, Translator, Box, Allocators> base;
+ typedef level_insert_base<0, Value, Value, NodeProxy> base;
typedef typename base::node node;
typedef typename base::internal_node internal_node;
typedef typename base::leaf leaf;
- typedef typename Options::parameters_type parameters_type;
-
inline level_insert(node* & root,
size_t & leafs_level,
Value const& v,
- parameters_type const& parameters,
- Translator const& translator,
- Allocators & allocators,
+ NodeProxy & node_proxy,
size_t relative_level)
- : base(root, leafs_level, v, parameters, translator, allocators, relative_level)
+ : base(root, leafs_level, v, node_proxy, relative_level)
{}
inline void operator()(internal_node & n)
@@ -369,36 +354,39 @@
} // namespace detail
// R*-tree insert visitor
-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
+template <typename Element, typename Value, typename NodeProxy>
+class insert<Element, Value, NodeProxy, insert_reinsert_tag>
+ : public rtree::visitor<
+ Value,
+ typename NodeProxy::parameters_type,
+ typename NodeProxy::box_type,
+ typename NodeProxy::allocators_type,
+ typename NodeProxy::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 NodeProxy::node node;
+ typedef typename NodeProxy::internal_node internal_node;
+ typedef typename NodeProxy::leaf leaf;
public:
inline insert(node* & root,
size_t & leafs_level,
Element const& element,
- parameters_type const& parameters,
- Translator const& translator,
- Allocators & allocators,
+ NodeProxy & node_proxy,
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)
+ , m_node_proxy(node_proxy)
+ , m_relative_level(relative_level)
{}
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);
+ detail::rstar::level_insert<0, Element, Value, NodeProxy> lins_v(
+ m_root, m_leafs_level, m_element, m_node_proxy, m_relative_level);
rtree::apply_visitor(lins_v, *m_root);
@@ -412,8 +400,8 @@
{
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);
+ detail::rstar::level_insert<0, Element, Value, NodeProxy> lins_v(
+ m_root, m_leafs_level, m_element, m_node_proxy, m_relative_level);
rtree::apply_visitor(lins_v, *m_root);
@@ -431,8 +419,8 @@
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);
+ detail::rstar::level_insert<1, element_type, Value, NodeProxy> lins_v(
+ m_root, m_leafs_level, *it, m_node_proxy, relative_level);
rtree::apply_visitor(lins_v, *m_root);
@@ -450,12 +438,9 @@
size_t & m_leafs_level;
Element const& m_element;
- parameters_type const& m_parameters;
- Translator const& m_translator;
+ NodeProxy & m_node_proxy;
size_t m_relative_level;
-
- Allocators m_allocators;
};
}}} // namespace detail::rtree::visitors
Modified: sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/rstar/redistribute_elements.hpp
==============================================================================
--- sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/rstar/redistribute_elements.hpp (original)
+++ sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/rstar/redistribute_elements.hpp 2012-09-30 07:11:50 EDT (Sun, 30 Sep 2012)
@@ -29,66 +29,66 @@
namespace rstar {
-template <typename Element, typename Translator, size_t Corner, size_t AxisIndex>
+template <typename Element, typename NodeProxy, size_t Corner, size_t AxisIndex>
class element_axis_corner_less
: index::nonassignable
{
public:
- element_axis_corner_less(Translator const& tr)
- : m_tr(tr)
+ element_axis_corner_less(NodeProxy const& node_proxy)
+ : m_node_proxy(node_proxy)
{}
bool operator()(Element const& e1, Element const& e2) const
{
- return index::get<Corner, AxisIndex>(rtree::element_indexable(e1, m_tr))
- < index::get<Corner, AxisIndex>(rtree::element_indexable(e2, m_tr));
+ return index::get<Corner, AxisIndex>(m_node_proxy.indexable(e1))
+ < index::get<Corner, AxisIndex>(m_node_proxy.indexable(e2));
}
private:
- Translator const& m_tr;
+ NodeProxy const& m_node_proxy;
};
-template <typename Parameters, typename Box, size_t Corner, size_t AxisIndex>
+template <typename NodeProxy, size_t Corner, size_t AxisIndex>
struct choose_split_axis_and_index_for_corner
{
- typedef typename index::default_margin_result<Box>::type margin_type;
- typedef typename index::default_content_result<Box>::type content_type;
+ typedef typename NodeProxy::box_type box_type;
+ typedef typename index::default_margin_result<box_type>::type margin_type;
+ typedef typename index::default_content_result<box_type>::type content_type;
- template <typename Elements, typename Translator>
+ template <typename Elements>
static inline void apply(Elements const& elements,
size_t & choosen_index,
margin_type & sum_of_margins,
content_type & smallest_overlap,
content_type & smallest_content,
- Parameters const& parameters,
- Translator const& translator)
+ NodeProxy const& node_proxy)
{
typedef typename Elements::value_type element_type;
- BOOST_GEOMETRY_INDEX_ASSERT(elements.size() == parameters.get_max_elements() + 1, "wrong number of elements");
+ BOOST_GEOMETRY_INDEX_ASSERT(elements.size() == node_proxy.parameters().get_max_elements() + 1, "wrong number of elements");
// copy elements
Elements elements_copy = elements;
// sort elements
- element_axis_corner_less<element_type, Translator, Corner, AxisIndex> elements_less(translator);
+ element_axis_corner_less<element_type, NodeProxy, Corner, AxisIndex> elements_less(node_proxy);
std::sort(elements_copy.begin(), elements_copy.end(), elements_less);
// init outputs
- choosen_index = parameters.get_min_elements();
+ choosen_index = node_proxy.parameters().get_min_elements();
sum_of_margins = 0;
smallest_overlap = (std::numeric_limits<content_type>::max)();
smallest_content = (std::numeric_limits<content_type>::max)();
// calculate sum of margins for all distributions
- size_t index_last = parameters.get_max_elements() - parameters.get_min_elements() + 2;
- for ( size_t i = parameters.get_min_elements() ; i < index_last ; ++i )
+ size_t index_last = node_proxy.parameters().get_max_elements() - node_proxy.parameters().get_min_elements() + 2;
+ for ( size_t i = node_proxy.parameters().get_min_elements() ; i < index_last ; ++i )
{
// TODO - awulkiew: may be optimized - box of group 1 may be initialized with
// box of min_elems number of elements and expanded for each iteration by another element
- Box box1 = rtree::elements_box<Box>(elements_copy.begin(), elements_copy.begin() + i, translator);
- Box box2 = rtree::elements_box<Box>(elements_copy.begin() + i, elements_copy.end(), translator);
+ box_type box1 = node_proxy.elements_box(elements_copy.begin(), elements_copy.begin() + i);
+ box_type box2 = node_proxy.elements_box(elements_copy.begin() + i, elements_copy.end());
sum_of_margins += index::margin(box1) + index::margin(box2);
@@ -105,47 +105,47 @@
}
};
-template <typename Parameters, typename Box, size_t AxisIndex, typename ElementIndexableTag>
+template <typename NodeProxy, size_t AxisIndex, typename ElementIndexableTag>
struct choose_split_axis_and_index_for_axis
{
//BOOST_STATIC_ASSERT(0);
};
-template <typename Parameters, typename Box, size_t AxisIndex>
-struct choose_split_axis_and_index_for_axis<Parameters, Box, AxisIndex, box_tag>
+template <typename NodeProxy, size_t AxisIndex>
+struct choose_split_axis_and_index_for_axis<NodeProxy, AxisIndex, box_tag>
{
- typedef typename index::default_margin_result<Box>::type margin_type;
- typedef typename index::default_content_result<Box>::type content_type;
+ typedef typename NodeProxy::box_type box_type;
+ typedef typename index::default_margin_result<box_type>::type margin_type;
+ typedef typename index::default_content_result<box_type>::type content_type;
- template <typename Elements, typename Translator>
+ template <typename Elements>
static inline void apply(Elements const& elements,
size_t & choosen_corner,
size_t & choosen_index,
margin_type & sum_of_margins,
content_type & smallest_overlap,
content_type & smallest_content,
- Parameters const& parameters,
- Translator const& translator)
+ NodeProxy const& node_proxy)
{
size_t index1 = 0;
margin_type som1 = 0;
content_type ovl1 = (std::numeric_limits<content_type>::max)();
content_type con1 = (std::numeric_limits<content_type>::max)();
- choose_split_axis_and_index_for_corner<Parameters, Box, min_corner, AxisIndex>::
+ choose_split_axis_and_index_for_corner<NodeProxy, min_corner, AxisIndex>::
apply(elements, index1,
som1, ovl1, con1,
- parameters, translator);
+ node_proxy);
size_t index2 = 0;
margin_type som2 = 0;
content_type ovl2 = (std::numeric_limits<content_type>::max)();
content_type con2 = (std::numeric_limits<content_type>::max)();
- choose_split_axis_and_index_for_corner<Parameters, Box, max_corner, AxisIndex>::
+ choose_split_axis_and_index_for_corner<NodeProxy, max_corner, AxisIndex>::
apply(elements, index2,
som2, ovl2, con2,
- parameters, translator);
+ node_proxy);
sum_of_margins = som1 + som2;
@@ -166,40 +166,41 @@
}
};
-template <typename Parameters, typename Box, size_t AxisIndex>
-struct choose_split_axis_and_index_for_axis<Parameters, Box, AxisIndex, point_tag>
+template <typename NodeProxy, size_t AxisIndex>
+struct choose_split_axis_and_index_for_axis<NodeProxy, AxisIndex, point_tag>
{
- typedef typename index::default_margin_result<Box>::type margin_type;
- typedef typename index::default_content_result<Box>::type content_type;
+ typedef typename NodeProxy::box_type box_type;
+ typedef typename index::default_margin_result<box_type>::type margin_type;
+ typedef typename index::default_content_result<box_type>::type content_type;
- template <typename Elements, typename Translator>
+ template <typename Elements>
static inline void apply(Elements const& elements,
size_t & choosen_corner,
size_t & choosen_index,
margin_type & sum_of_margins,
content_type & smallest_overlap,
content_type & smallest_content,
- Parameters const& parameters,
- Translator const& translator)
+ NodeProxy const& node_proxy)
{
- choose_split_axis_and_index_for_corner<Parameters, Box, min_corner, AxisIndex>::
+ choose_split_axis_and_index_for_corner<NodeProxy, min_corner, AxisIndex>::
apply(elements, choosen_index,
sum_of_margins, smallest_overlap, smallest_content,
- parameters, translator);
+ node_proxy);
choosen_corner = min_corner;
}
};
-template <typename Parameters, typename Box, size_t Dimension>
+template <typename NodeProxy, size_t Dimension>
struct choose_split_axis_and_index
{
BOOST_STATIC_ASSERT(0 < Dimension);
- typedef typename index::default_margin_result<Box>::type margin_type;
- typedef typename index::default_content_result<Box>::type content_type;
+ typedef typename NodeProxy::box_type box_type;
+ typedef typename index::default_margin_result<box_type>::type margin_type;
+ typedef typename index::default_content_result<box_type>::type content_type;
- template <typename Elements, typename Translator>
+ template <typename Elements>
static inline void apply(Elements const& elements,
size_t & choosen_axis,
size_t & choosen_corner,
@@ -207,15 +208,17 @@
margin_type & smallest_sum_of_margins,
content_type & smallest_overlap,
content_type & smallest_content,
- Parameters const& parameters,
- Translator const& translator)
+ NodeProxy const& node_proxy)
{
- typedef typename rtree::element_indexable_type<typename Elements::value_type, Translator>::type element_indexable_type;
+ typedef typename rtree::element_indexable_type<
+ typename Elements::value_type,
+ typename NodeProxy::translator_type
+ >::type element_indexable_type;
- choose_split_axis_and_index<Parameters, Box, Dimension - 1>::
+ choose_split_axis_and_index<NodeProxy, Dimension - 1>::
apply(elements, choosen_axis, choosen_corner, choosen_index,
smallest_sum_of_margins, smallest_overlap, smallest_content,
- parameters, translator);
+ node_proxy);
margin_type sum_of_margins = 0;
@@ -226,11 +229,10 @@
content_type content_val = (std::numeric_limits<content_type>::max)();
choose_split_axis_and_index_for_axis<
- Parameters,
- Box,
+ NodeProxy,
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, node_proxy);
if ( sum_of_margins < smallest_sum_of_margins )
{
@@ -244,13 +246,14 @@
}
};
-template <typename Parameters, typename Box>
-struct choose_split_axis_and_index<Parameters, Box, 1>
+template <typename NodeProxy>
+struct choose_split_axis_and_index<NodeProxy, 1>
{
- typedef typename index::default_margin_result<Box>::type margin_type;
- typedef typename index::default_content_result<Box>::type content_type;
+ typedef typename NodeProxy::box_type box_type;
+ typedef typename index::default_margin_result<box_type>::type margin_type;
+ typedef typename index::default_content_result<box_type>::type content_type;
- template <typename Elements, typename Translator>
+ template <typename Elements>
static inline void apply(Elements const& elements,
size_t & choosen_axis,
size_t & choosen_corner,
@@ -258,19 +261,20 @@
margin_type & smallest_sum_of_margins,
content_type & smallest_overlap,
content_type & smallest_content,
- Parameters const& parameters,
- Translator const& translator)
+ NodeProxy const& node_proxy)
{
- typedef typename rtree::element_indexable_type<typename Elements::value_type, Translator>::type element_indexable_type;
+ typedef typename rtree::element_indexable_type<
+ typename Elements::value_type,
+ typename NodeProxy::translator_type
+ >::type element_indexable_type;
choosen_axis = 0;
choose_split_axis_and_index_for_axis<
- Parameters,
- Box,
+ NodeProxy,
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, node_proxy);
}
};
@@ -279,19 +283,19 @@
{
BOOST_STATIC_ASSERT(0 < Dimension);
- template <typename Elements, typename Translator>
- static inline void apply(Elements & elements, const size_t axis, const size_t index, Translator const& tr)
+ template <typename Elements, typename NodeProxy>
+ static inline void apply(Elements & elements, const size_t axis, const size_t index, NodeProxy const& node_proxy)
{
if ( axis < Dimension - 1 )
{
- partial_sort<Corner, Dimension - 1>::apply(elements, axis, index, tr);
+ partial_sort<Corner, Dimension - 1>::apply(elements, axis, index, node_proxy);
}
else
{
BOOST_GEOMETRY_INDEX_ASSERT(axis == Dimension - 1, "unexpected axis value");
typedef typename Elements::value_type element_type;
- element_axis_corner_less<element_type, Translator, Corner, Dimension - 1> less(tr);
+ element_axis_corner_less<element_type, NodeProxy, Corner, Dimension - 1> less(node_proxy);
std::partial_sort(elements.begin(), elements.begin() + index, elements.end(), less);
}
}
@@ -300,41 +304,39 @@
template <size_t Corner>
struct partial_sort<Corner, 1>
{
- template <typename Elements, typename Translator>
- static inline void apply(Elements & elements, const size_t axis, const size_t index, Translator const& tr)
+ template <typename Elements, typename NodeProxy>
+ static inline void apply(Elements & elements, const size_t axis, const size_t index, NodeProxy const& node_proxy)
{
BOOST_GEOMETRY_INDEX_ASSERT(axis == 0, "unexpected axis value");
typedef typename Elements::value_type element_type;
- element_axis_corner_less<element_type, Translator, Corner, 0> less(tr);
+ element_axis_corner_less<element_type, NodeProxy, Corner, 0> less(node_proxy);
std::partial_sort(elements.begin(), elements.begin() + index, elements.end(), less);
}
};
} // namespace rstar
-template <typename Value, typename Options, typename Translator, typename Box, typename Allocators>
-struct redistribute_elements<Value, Options, Translator, Box, Allocators, rstar_tag>
+template <typename Value, typename NodeProxy>
+struct redistribute_elements<Value, NodeProxy, rstar_tag>
{
- typedef typename rtree::node<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type node;
- typedef typename rtree::internal_node<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type internal_node;
- typedef typename rtree::leaf<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type leaf;
+ typedef typename NodeProxy::node node;
+ typedef typename NodeProxy::internal_node internal_node;
+ typedef typename NodeProxy::leaf leaf;
+ typedef typename NodeProxy::box_type box_type;
- typedef typename Options::parameters_type parameters_type;
+ static const size_t dimension = index::traits::dimension<box_type>::value;
- static const size_t dimension = index::traits::dimension<Box>::value;
-
- typedef typename index::default_margin_result<Box>::type margin_type;
- typedef typename index::default_content_result<Box>::type content_type;
+ typedef typename index::default_margin_result<box_type>::type margin_type;
+ typedef typename index::default_content_result<box_type>::type content_type;
template <typename Node>
static inline void apply(
Node & n,
Node & second_node,
- Box & box1,
- Box & box2,
- parameters_type const& parameters,
- Translator const& translator)
+ box_type & box1,
+ box_type & box2,
+ NodeProxy & node_proxy)
{
typedef typename rtree::elements_type<Node>::type elements_type;
@@ -343,37 +345,41 @@
size_t split_axis = 0;
size_t split_corner = 0;
- size_t split_index = parameters.get_min_elements();
+ size_t split_index = node_proxy.parameters().get_min_elements();
margin_type smallest_sum_of_margins = (std::numeric_limits<margin_type>::max)();
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<
+ NodeProxy,
+ index::traits::dimension<box_type>::value
+ >::apply(elements1,
+ split_axis, split_corner, split_index,
+ smallest_sum_of_margins, smallest_overlap, smallest_content,
+ node_proxy);
// TODO: awulkiew - get rid of following static_casts?
- BOOST_GEOMETRY_INDEX_ASSERT(split_axis < index::traits::dimension<Box>::value, "unexpected value");
+ BOOST_GEOMETRY_INDEX_ASSERT(split_axis < index::traits::dimension<box_type>::value, "unexpected value");
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");
+ BOOST_GEOMETRY_INDEX_ASSERT(node_proxy.parameters().get_min_elements() <= split_index &&
+ split_index <= node_proxy.parameters().get_max_elements() - node_proxy.parameters().get_min_elements() + 1,
+ "unexpected value");
// 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(elements1, split_axis, split_index, node_proxy);
else
- rstar::partial_sort<max_corner, dimension>::apply(elements1, split_axis, split_index, translator);
+ rstar::partial_sort<max_corner, dimension>::apply(elements1, split_axis, split_index, node_proxy);
// copy elements to node 2 and remove from node 1
- elements2.resize(parameters.get_max_elements() + 1 - split_index);
+ elements2.resize(node_proxy.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);
+ box1 = node_proxy.elements_box(elements1.begin(), elements1.end());
+ box2 = node_proxy.elements_box(elements2.begin(), elements2.end());
}
};
Modified: sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/rtree.hpp
==============================================================================
--- sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/rtree.hpp (original)
+++ sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/rtree.hpp 2012-09-30 07:11:50 EDT (Sun, 30 Sep 2012)
@@ -78,16 +78,21 @@
{
BOOST_COPYABLE_AND_MOVABLE(rtree)
- typedef node_proxy<Value, Parameters, Translator, Allocator> node_proxy_type;
-
public:
+ typedef detail::rtree::node_proxy<
+ Value, Parameters, Translator, Allocator
+ > node_proxy_type;
+
typedef typename node_proxy_type::value_type value_type;
typedef typename node_proxy_type::translator_type translator_type;
typedef typename node_proxy_type::indexable_type indexable_type;
typedef typename node_proxy_type::box_type box_type;
typedef typename node_proxy_type::allocator_type allocator_type;
- typedef typename node_proxy_type::size_type size_type size_type;
+ typedef typename node_proxy_type::size_type size_type;
+
+ typedef typename node_proxy_type::node node;
+ typedef typename node_proxy_type::leaf leaf;
/*!
The constructor.
@@ -157,7 +162,9 @@
The copy constructor.
*/
inline rtree(rtree const& src, Allocator const& allocator)
- : m_node_proxy(src.m_parameters, src.m_translator, allocator)
+ : m_node_proxy(src.m_node_proxy.parameters(),
+ src.m_node_proxy.translator(),
+ allocator)
{
try
{
@@ -189,15 +196,17 @@
*/
inline rtree & operator=(BOOST_COPY_ASSIGN_REF(rtree) src)
{
- //TODO use Boost.Container allocator_traits_type::propagate_on_container_move_assignment
-
if ( this == &src )
return *this;
if ( !this->empty() )
this->destroy(*this);
-
- m_node_proxy = src.m_node_proxy;
+
+ //TODO use Boost.Container allocator_traits_type::propagate_on_container_move_assignment
+ m_node_proxy = node_proxy_type(
+ src.m_node_proxy.parameters(),
+ src.m_node_proxy.translator(),
+ m_node_proxy.allocator());
try
{
@@ -217,17 +226,19 @@
*/
inline rtree & operator=(BOOST_RV_REF(rtree) src)
{
- //TODO use Boost.Container allocator_traits_type::propagate_on_container_move_assignment
-
if ( this == &src )
return *this;
if ( !this->empty() )
this->destroy(*this);
- m_node_proxy = src.m_node_proxy;
+ //TODO use Boost.Container allocator_traits_type::propagate_on_container_move_assignment
+ m_node_proxy = node_proxy_type(
+ src.m_node_proxy.parameters(),
+ src.m_node_proxy.translator(),
+ m_node_proxy.allocator());
- if ( m_allocators.allocator == src.m_allocators.allocator)
+ if ( m_node_proxy.allocator() == src.m_node_proxy.allocator() )
{
m_values_count = src.m_values_count;
src.m_values_count = 0;
@@ -259,7 +270,7 @@
*/
inline void insert(value_type const& value)
{
- BOOST_GEOMETRY_INDEX_ASSERT(index::is_valid(m_node_proxy.translate(value)), "Indexable is invalid");
+ BOOST_GEOMETRY_INDEX_ASSERT(index::is_valid(m_node_proxy.indexable(value)), "Indexable is invalid");
try
{
@@ -267,10 +278,10 @@
value_type,
value_type,
node_proxy_type,
- typename options_type::insert_tag
+ typename node_proxy_type::options_type::insert_tag
> insert_v(m_root, m_leafs_level, value, m_node_proxy);
- m_node_proxy.apply_visitor(insert_v, *m_root);
+ detail::rtree::apply_visitor(insert_v, *m_root);
++m_values_count;
}
@@ -312,7 +323,7 @@
node_proxy_type
> remove_v(m_root, m_leafs_level, value, m_node_proxy);
- m_node_proxy.apply_visitor(remove_v, *m_root);
+ detail::rtree::apply_visitor(remove_v, *m_root);
--m_values_count;
}
@@ -358,7 +369,7 @@
detail::rtree::visitors::query<value_type, node_proxy_type, Predicates, OutIter>
find_v(m_node_proxy, pred, out_it);
- m_node_proxy.apply_visitor(find_v, *m_root);
+ detail::rtree::apply_visitor(find_v, *m_root);
return find_v.found_count;
}
@@ -515,10 +526,10 @@
return result;
}
- detail::rtree::visitors::children_box<value_type, node_proxy>
+ detail::rtree::visitors::children_box<value_type, node_proxy_type>
children_box_v(m_node_proxy);
- m_node_proxy.apply_visitor(children_box_v, *m_root);
+ detail::rtree::apply_visitor(children_box_v, *m_root);
return children_box_v.result;
}
@@ -533,18 +544,18 @@
template <typename Visitor>
inline void apply_visitor(Visitor & visitor) const
{
- m_node_proxy.apply_visitor(visitor, *m_root);
+ detail::rtree::apply_visitor(visitor, *m_root);
}
/*!
- Returns the translator object.
+ Returns the node proxy object.
This function is not a part of the 'official' interface.
- \return The translator object.
+ \return The node proxy object.
*/
- inline translator_type const& translator() const
+ inline node_proxy_type const& node_proxy() const
{
- return m_node_proxy.m_translator;
+ return m_node_proxy;
}
/*!
@@ -593,7 +604,7 @@
value_type,
node_proxy_type
> del_v(t.m_root, t.m_node_proxy);
- m_node_proxy.apply_visitor(del_v, *t.m_root);
+ detail::rtree::apply_visitor(del_v, *t.m_root);
t.m_root = 0;
t.m_values_count = 0;
@@ -612,7 +623,7 @@
value_type,
node_proxy_type
> copy_v(dst.m_node_proxy);
- m_node_proxy.apply_visitor(copy_v, *src.m_root);
+ detail::rtree::apply_visitor(copy_v, *src.m_root);
dst.m_root = copy_v.result;
dst.m_values_count = src.m_values_count;
@@ -644,7 +655,7 @@
result_type
> nearest_v(m_node_proxy, dpred, pred, result);
- m_node_proxy.apply_visitor(nearest_v, *m_root);
+ detail::rtree::apply_visitor(nearest_v, *m_root);
return result.get(v);
}
@@ -674,7 +685,7 @@
result_type
> nearest_v(m_node_proxy, dpred, pred, result);
- m_node_proxy.apply_visitor(nearest_v, *m_root);
+ detail::rtree::apply_visitor(nearest_v, *m_root);
return result.get(out_it);
}
Modified: sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/visitors/are_boxes_ok.hpp
==============================================================================
--- sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/visitors/are_boxes_ok.hpp (original)
+++ sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/visitors/are_boxes_ok.hpp 2012-09-30 07:11:50 EDT (Sun, 30 Sep 2012)
@@ -18,17 +18,25 @@
namespace detail { namespace rtree { namespace visitors {
-template <typename Value, typename Options, typename Translator, typename Box, typename Allocators>
+template <typename Value, typename NodeProxy>
class are_boxes_ok
- : public rtree::visitor<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag, true>::type
+ : public rtree::visitor<
+ Value,
+ typename NodeProxy::parameters_type,
+ typename NodeProxy::box_type,
+ typename NodeProxy::allocators_type,
+ typename NodeProxy::node_tag,
+ true
+ >::type
, index::nonassignable
{
- 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 NodeProxy::internal_node internal_node;
+ typedef typename NodeProxy::leaf leaf;
+ typedef typename NodeProxy::box_type box_type;
public:
- inline are_boxes_ok(Translator const& tr)
- : result(false), m_tr(tr), m_is_root(true)
+ inline are_boxes_ok(NodeProxy const& node_proxy)
+ : result(false), m_node_proxy(node_proxy), m_is_root(true)
{}
inline void operator()(internal_node const& n)
@@ -42,7 +50,7 @@
return;
}
- Box box_bckup = m_box;
+ box_type box_bckup = m_box;
bool is_root_bckup = m_is_root;
m_is_root = false;
@@ -61,7 +69,7 @@
m_box = box_bckup;
m_is_root = is_root_bckup;
- Box box_exp;
+ box_type box_exp;
geometry::convert(elements.front().first, box_exp);
for( typename elements_type::const_iterator it = elements.begin() + 1;
it != elements.end() ; ++it)
@@ -86,12 +94,12 @@
return;
}
- Box box_exp;
- geometry::convert(m_tr(elements.front()), box_exp);
+ box_type box_exp;
+ geometry::convert(m_node_proxy.indexable(elements.front()), box_exp);
for(typename elements_type::const_iterator it = elements.begin() + 1;
it != elements.end() ; ++it)
{
- geometry::expand(box_exp, m_tr(*it));
+ geometry::expand(box_exp, m_node_proxy.indexable(*it));
}
result = geometry::equals(box_exp, m_box);
@@ -103,24 +111,25 @@
bool result;
private:
- Translator const& m_tr;
- Box m_box;
+ NodeProxy const& m_node_proxy;
+ box_type m_box;
bool m_is_root;
};
}}} // 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)
{
- typedef rtree<Value, Options, 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());
+ Value,
+ detail::rtree::node_proxy<
+ Value,
+ Parameters,
+ Translator,
+ Allocator
+ >
+ > v(tree.node_proxy());
tree.apply_visitor(v);
Modified: sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/visitors/are_levels_ok.hpp
==============================================================================
--- sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/visitors/are_levels_ok.hpp (original)
+++ sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/visitors/are_levels_ok.hpp 2012-09-30 07:11:50 EDT (Sun, 30 Sep 2012)
@@ -17,17 +17,25 @@
namespace detail { namespace rtree { namespace visitors {
-template <typename Value, typename Options, typename Translator, typename Box, typename Allocators>
+template <typename Value, typename NodeProxy>
class are_levels_ok
- : public rtree::visitor<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag, true>::type
+ : public rtree::visitor<
+ Value,
+ typename NodeProxy::parameters_type,
+ typename NodeProxy::box_type,
+ typename NodeProxy::allocators_type,
+ typename NodeProxy::node_tag,
+ true
+ >::type
, index::nonassignable
{
- 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 NodeProxy::internal_node internal_node;
+ typedef typename NodeProxy::leaf leaf;
+ typedef typename NodeProxy::box_type box_type;
public:
- inline are_levels_ok(Translator const& tr)
- : result(true), m_tr(tr), m_leafs_level((std::numeric_limits<size_t>::max)()), m_current_level(0)
+ inline are_levels_ok()
+ : result(true), m_leafs_level((std::numeric_limits<size_t>::max)()), m_current_level(0)
{}
inline void operator()(internal_node const& n)
@@ -81,24 +89,24 @@
bool result;
private:
- Translator const& m_tr;
size_t m_leafs_level;
size_t m_current_level;
};
}}} // 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;
detail::rtree::visitors::are_levels_ok<
- typename rt::value_type,
- typename rt::options_type,
- typename rt::translator_type,
- typename rt::box_type,
- typename rt::allocators_type
- > v(tree.translator());
+ Value,
+ detail::rtree::node_proxy<
+ Value,
+ Parameters,
+ Translator,
+ Allocator
+ >
+ > v;
tree.apply_visitor(v);
Modified: sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/visitors/children_box.hpp
==============================================================================
--- sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/visitors/children_box.hpp (original)
+++ sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/visitors/children_box.hpp 2012-09-30 07:11:50 EDT (Sun, 30 Sep 2012)
@@ -17,17 +17,25 @@
namespace detail { namespace rtree { namespace visitors {
-template <typename Value, typename Options, typename Translator, typename Box, typename Allocators>
+template <typename Value, typename NodeProxy>
class children_box
- : public rtree::visitor<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag, true>::type
+ : public rtree::visitor<
+ Value,
+ typename NodeProxy::parameters_type,
+ typename NodeProxy::box_type,
+ typename NodeProxy::allocators_type,
+ typename NodeProxy::node_tag,
+ true
+ >::type
, index::nonassignable
{
- 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 NodeProxy::internal_node internal_node;
+ typedef typename NodeProxy::leaf leaf;
+ typedef typename NodeProxy::box_type box_type;
public:
- inline children_box(Translator const& tr)
- : m_tr(tr)
+ inline children_box(NodeProxy const& node_proxy)
+ : m_node_proxy(node_proxy)
{}
inline void operator()(internal_node const& n)
@@ -35,7 +43,7 @@
typedef typename rtree::elements_type<internal_node>::type elements_type;
elements_type const& elements = rtree::elements(n);
- result = rtree::elements_box<Box>(elements.begin(), elements.end(), m_tr);
+ result = m_node_proxy.elements_box(elements.begin(), elements.end());
}
inline void operator()(leaf const& n)
@@ -43,13 +51,13 @@
typedef typename rtree::elements_type<leaf>::type elements_type;
elements_type const& elements = rtree::elements(n);
- result = rtree::elements_box<Box>(elements.begin(), elements.end(), m_tr);
+ result = m_node_proxy.elements_box(elements.begin(), elements.end());
}
- Box result;
+ box_type result;
private:
- Translator const& m_tr;
+ NodeProxy const& m_node_proxy;
};
}}} // namespace detail::rtree::visitors
Modified: sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/visitors/copy.hpp
==============================================================================
--- sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/visitors/copy.hpp (original)
+++ sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/visitors/copy.hpp 2012-09-30 07:11:50 EDT (Sun, 30 Sep 2012)
@@ -17,24 +17,31 @@
namespace detail { namespace rtree { namespace visitors {
-template <typename Value, typename Options, typename Translator, typename Box, typename Allocators>
+template <typename Value, typename NodeProxy>
class copy
- : public rtree::visitor<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag, false>::type
+ : public rtree::visitor<
+ Value,
+ typename NodeProxy::parameters_type,
+ typename NodeProxy::box_type,
+ typename NodeProxy::allocators_type,
+ typename NodeProxy::node_tag,
+ false
+ >::type
, boost::noncopyable
{
public:
- typedef typename rtree::node<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type node;
- typedef typename rtree::internal_node<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type internal_node;
- typedef typename rtree::leaf<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type leaf;
+ typedef typename NodeProxy::node node;
+ typedef typename NodeProxy::internal_node internal_node;
+ typedef typename NodeProxy::leaf leaf;
- explicit inline copy(Allocators & allocators)
+ explicit inline copy(NodeProxy & node_proxy)
: result(0)
- , m_allocators(allocators)
+ , m_node_proxy(node_proxy)
{}
inline void operator()(internal_node & n)
{
- node * new_node = rtree::create_node<Allocators, internal_node>::apply(m_allocators);
+ node * new_node = m_node_proxy.template create<internal_node>();
typedef typename rtree::elements_type<internal_node>::type elements_type;
elements_type & elements = rtree::elements(n);
@@ -54,7 +61,7 @@
inline void operator()(leaf & l)
{
- node * new_node = rtree::create_node<Allocators, leaf>::apply(m_allocators);
+ node * new_node = m_node_proxy.template create<leaf>();
typedef typename rtree::elements_type<leaf>::type elements_type;
elements_type & elements = rtree::elements(l);
@@ -73,7 +80,7 @@
node * result;
private:
- Allocators & m_allocators;
+ NodeProxy & m_node_proxy;
};
}}} // namespace detail::rtree::visitors
Modified: sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/visitors/destroy.hpp
==============================================================================
--- sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/visitors/destroy.hpp (original)
+++ sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/visitors/destroy.hpp 2012-09-30 07:11:50 EDT (Sun, 30 Sep 2012)
@@ -17,19 +17,26 @@
namespace detail { namespace rtree { namespace visitors {
-template <typename Value, typename Options, typename Translator, typename Box, typename Allocators>
+template <typename Value, typename NodeProxy>
class destroy
- : public rtree::visitor<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag, false>::type
+ : public rtree::visitor<
+ Value,
+ typename NodeProxy::parameters_type,
+ typename NodeProxy::box_type,
+ typename NodeProxy::allocators_type,
+ typename NodeProxy::node_tag,
+ false
+ >::type
, boost::noncopyable
{
public:
- typedef typename rtree::node<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type node;
- typedef typename rtree::internal_node<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type internal_node;
- typedef typename rtree::leaf<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type leaf;
+ typedef typename NodeProxy::node node;
+ typedef typename NodeProxy::internal_node internal_node;
+ typedef typename NodeProxy::leaf leaf;
- inline destroy(node * root_node, Allocators & allocators)
+ inline destroy(node * root_node, NodeProxy & node_proxy)
: m_current_node(root_node)
- , m_allocators(allocators)
+ , m_node_proxy(node_proxy)
{}
inline void operator()(internal_node & n)
@@ -48,19 +55,19 @@
rtree::apply_visitor(*this, *m_current_node);
}
- rtree::destroy_node<Allocators, internal_node>::apply(m_allocators, node_to_destroy);
+ m_node_proxy.template destroy<internal_node>(node_to_destroy);
}
inline void operator()(leaf & l)
{
BOOST_GEOMETRY_INDEX_ASSERT(&l == rtree::get<leaf>(m_current_node), "invalid pointers");
- rtree::destroy_node<Allocators, leaf>::apply(m_allocators, m_current_node);
+ m_node_proxy.template destroy<leaf>(m_current_node);
}
private:
node * m_current_node;
- Allocators & m_allocators;
+ NodeProxy & m_node_proxy;
};
}}} // namespace detail::rtree::visitors
Modified: sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/visitors/insert.hpp
==============================================================================
--- sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/visitors/insert.hpp (original)
+++ sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/visitors/insert.hpp 2012-09-30 07:11:50 EDT (Sun, 30 Sep 2012)
@@ -22,26 +22,28 @@
namespace detail {
// Default choose_next_node
-template <typename Value, typename Options, typename Box, typename Allocators, typename ChooseNextNodeTag>
-struct choose_next_node;
+template <typename Value, typename NodeProxy, typename ChooseNextNodeTag>
+class choose_next_node;
-template <typename Value, typename Options, typename Box, typename Allocators>
-struct choose_next_node<Value, Options, Box, Allocators, choose_by_content_diff_tag>
+template <typename Value, typename NodeProxy>
+class choose_next_node<Value, NodeProxy, choose_by_content_diff_tag>
{
- typedef typename Options::parameters_type parameters_type;
+ typedef typename NodeProxy::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 NodeProxy::node node;
+ typedef typename NodeProxy::internal_node internal_node;
+ typedef typename NodeProxy::leaf leaf;
+ typedef typename NodeProxy::box_type box_type;
typedef typename rtree::elements_type<internal_node>::type children_type;
- typedef typename index::default_content_result<Box>::type content_type;
+ typedef typename index::default_content_result<box_type>::type content_type;
+public:
template <typename Indexable>
static inline size_t apply(internal_node & n,
Indexable const& indexable,
- parameters_type const& /*parameters*/,
+ NodeProxy const& /*node_proxy*/,
size_t /*node_relative_level*/)
{
children_type & children = rtree::elements(n);
@@ -62,7 +64,7 @@
child_type const& ch_i = children[i];
// expanded child node's box
- Box box_exp(ch_i.first);
+ box_type box_exp(ch_i.first);
geometry::expand(box_exp, indexable);
// areas difference
@@ -86,7 +88,7 @@
// ----------------------------------------------------------------------- //
// Not implemented here
-template <typename Value, typename Options, typename Translator, typename Box, typename Allocators, typename RedistributeTag>
+template <typename Value, typename NodeProxy, typename RedistributeTag>
struct redistribute_elements
{
BOOST_MPL_ASSERT_MSG(
@@ -98,7 +100,7 @@
// ----------------------------------------------------------------------- //
// Split algorithm
-template <typename Value, typename Options, typename Translator, typename Box, typename Allocators, typename SplitTag>
+template <typename Value, typename NodeProxy, typename SplitTag>
class split
{
BOOST_MPL_ASSERT_MSG(
@@ -108,42 +110,40 @@
};
// Default split algorithm
-template <typename Value, typename Options, typename Translator, typename Box, typename Allocators>
-class split<Value, Options, Translator, Box, Allocators, split_default_tag>
+template <typename Value, typename NodeProxy>
+class split<Value, NodeProxy, split_default_tag>
{
protected:
- typedef typename Options::parameters_type parameters_type;
+ typedef typename NodeProxy::node node;
+ typedef typename NodeProxy::internal_node internal_node;
+ typedef typename NodeProxy::leaf 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;
+ typedef typename NodeProxy::box_type box_type;
public:
- typedef index::pushable_array<std::pair<Box, node*>, 1> nodes_container_type;
+ typedef index::pushable_array<std::pair<box_type, node*>, 1> nodes_container_type;
template <typename Node>
static inline void apply(nodes_container_type & additional_nodes,
Node & n,
- Box & n_box,
- parameters_type const& parameters,
- Translator const& translator,
- Allocators & allocators)
+ box_type & n_box,
+ NodeProxy & node_proxy)
{
// create additional node
- node * second_node = rtree::create_node<Allocators, Node>::apply(allocators);
+ node * second_node = node_proxy.template create<Node>();
Node & n2 = rtree::get<Node>(*second_node);
// redistribute elements
- Box box2;
- redistribute_elements<Value, Options, Translator, Box, Allocators, typename Options::redistribute_tag>::
- apply(n, n2, n_box, box2, parameters, translator);
+ box_type box2;
+ redistribute_elements<Value, NodeProxy, typename NodeProxy::options_type::redistribute_tag>::
+ apply(n, n2, n_box, box2, node_proxy);
// check numbers of elements
- BOOST_GEOMETRY_INDEX_ASSERT(parameters.get_min_elements() <= rtree::elements(n).size() &&
- rtree::elements(n).size() <= parameters.get_max_elements(),
+ BOOST_GEOMETRY_INDEX_ASSERT(node_proxy.parameters().get_min_elements() <= rtree::elements(n).size() &&
+ rtree::elements(n).size() <= node_proxy.parameters().get_max_elements(),
"unexpected number of elements");
- BOOST_GEOMETRY_INDEX_ASSERT(parameters.get_min_elements() <= rtree::elements(n2).size() &&
- rtree::elements(n2).size() <= parameters.get_max_elements(),
+ BOOST_GEOMETRY_INDEX_ASSERT(node_proxy.parameters().get_min_elements() <= rtree::elements(n2).size() &&
+ rtree::elements(n2).size() <= node_proxy.parameters().get_max_elements(),
"unexpected number of elements");
additional_nodes.push_back(std::make_pair(box2, second_node));
@@ -153,29 +153,34 @@
// ----------------------------------------------------------------------- //
// Default insert visitor
-template <typename Element, typename Value, typename Options, typename Translator, typename Box, typename Allocators>
+template <typename Element, typename Value, typename NodeProxy>
class insert
- : public rtree::visitor<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag, false>::type
+ : public rtree::visitor<
+ Value,
+ typename NodeProxy::parameters_type,
+ typename NodeProxy::box_type,
+ typename NodeProxy::allocators_type,
+ typename NodeProxy::node_tag,
+ false
+ >::type
, index::nonassignable
{
protected:
- 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 NodeProxy::options_type options_type;
+ typedef typename NodeProxy::parameters_type parameters_type;
+ typedef typename NodeProxy::box_type box_type;
+
+ typedef typename NodeProxy::node node;
+ typedef typename NodeProxy::internal_node internal_node;
+ typedef typename NodeProxy::leaf leaf;
inline insert(node* & root,
size_t & leafs_level,
Element const& element,
- parameters_type const& parameters,
- Translator const& translator,
- Allocators & allocators,
+ NodeProxy & node_proxy,
size_t relative_level = 0
)
: m_element(element)
- , m_parameters(parameters)
- , m_translator(translator)
, m_relative_level(relative_level)
, m_level(leafs_level - relative_level)
, m_root_node(root)
@@ -183,7 +188,7 @@
, m_parent(0)
, m_current_child_index(0)
, m_current_level(0)
- , m_allocators(allocators)
+ , m_node_proxy(node_proxy)
{
BOOST_GEOMETRY_INDEX_ASSERT(m_relative_level <= leafs_level, "unexpected level value");
BOOST_GEOMETRY_INDEX_ASSERT(m_level <= m_leafs_level, "unexpected level value");
@@ -196,13 +201,13 @@
inline void traverse(Visitor & visitor, internal_node & n)
{
// choose next node
- size_t choosen_node_index = detail::choose_next_node<Value, Options, Box, Allocators, typename Options::choose_next_node_tag>::
- apply(n, rtree::element_indexable(m_element, m_translator), m_parameters, m_leafs_level - m_current_level);
+ size_t choosen_node_index = detail::choose_next_node<Value, NodeProxy, typename NodeProxy::options_type::choose_next_node_tag>::
+ apply(n, m_node_proxy.indexable(m_element), m_node_proxy, m_leafs_level - m_current_level);
// expand the node to contain value
geometry::expand(
rtree::elements(n)[choosen_node_index].first,
- rtree::element_indexable(m_element, m_translator));
+ m_node_proxy.indexable(m_element));
// next traversing step
traverse_apply_visitor(visitor, n, choosen_node_index);
@@ -217,7 +222,7 @@
"if node isn't the root current_child_index should be valid");
// handle overflow
- if ( m_parameters.get_max_elements() < rtree::elements(n).size() )
+ if ( m_node_proxy.parameters().get_max_elements() < rtree::elements(n).size() )
{
split(n);
}
@@ -237,7 +242,7 @@
++m_current_level;
// next traversing step
- rtree::apply_visitor(visitor, *rtree::elements(n)[choosen_node_index].second);
+ index::detail::rtree::apply_visitor(visitor, *rtree::elements(n)[choosen_node_index].second);
// restore previous traverse inputs
m_parent = parent_bckup;
@@ -250,12 +255,12 @@
template <typename Node>
inline void split(Node & n) const
{
- typedef detail::split<Value, Options, Translator, Box, Allocators, typename Options::split_tag> split_algo;
+ typedef detail::split<Value, NodeProxy, typename NodeProxy::options_type::split_tag> split_algo;
typename split_algo::nodes_container_type additional_nodes;
- Box n_box;
+ box_type 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_node_proxy);
BOOST_GEOMETRY_INDEX_ASSERT(additional_nodes.size() == 1, "unexpected number of additional nodes");
@@ -282,7 +287,7 @@
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 * new_root = m_node_proxy.template create<internal_node>();
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]);
@@ -295,8 +300,6 @@
// TODO: awulkiew - implement dispatchable split::apply to enable additional nodes creation
Element const& m_element;
- parameters_type const& m_parameters;
- Translator const& m_translator;
const size_t m_relative_level;
const size_t m_level;
@@ -308,36 +311,33 @@
size_t m_current_child_index;
size_t m_current_level;
- Allocators & m_allocators;
+ NodeProxy & m_node_proxy;
};
} // namespace detail
// Insert visitor forward declaration
-template <typename Element, typename Value, typename Options, typename Translator, typename Box, typename Allocators, typename InsertTag>
-struct insert;
+template <typename Element, typename Value, typename NodeProxy, typename InsertTag>
+class insert;
// Default insert visitor used for nodes elements
-template <typename Element, typename Value, typename Options, typename Translator, typename Box, typename Allocators>
-struct insert<Element, Value, Options, Translator, Box, Allocators, insert_default_tag>
- : public detail::insert<Element, Value, Options, Translator, Box, Allocators>
+template <typename Element, typename Value, typename NodeProxy>
+class insert<Element, Value, NodeProxy, insert_default_tag>
+ : public detail::insert<Element, Value, NodeProxy>
{
- typedef detail::insert<Element, Value, Options, Translator, Box, Allocators> base;
+public:
+ typedef detail::insert<Element, Value, NodeProxy> base;
typedef typename base::node node;
typedef typename base::internal_node internal_node;
typedef typename base::leaf leaf;
- typedef typename Options::parameters_type parameters_type;
-
inline insert(node* & root,
size_t & leafs_level,
Element const& element,
- parameters_type const& parameters,
- Translator const& translator,
- Allocators & allocators,
+ NodeProxy & node_proxy,
size_t relative_level = 0
)
- : base(root, leafs_level, element, parameters, translator, allocators, relative_level)
+ : base(root, leafs_level, element, node_proxy, relative_level)
{}
inline void operator()(internal_node & n)
@@ -367,26 +367,23 @@
};
// Default insert visitor specialized for Values elements
-template <typename Value, typename Options, typename Translator, typename Box, typename Allocators>
-struct insert<Value, Value, Options, Translator, Box, Allocators, insert_default_tag>
- : public detail::insert<Value, Value, Options, Translator, Box, Allocators>
+template <typename Value, typename NodeProxy>
+class insert<Value, Value, NodeProxy, insert_default_tag>
+ : public detail::insert<Value, Value, NodeProxy>
{
- typedef detail::insert<Value, Value, Options, Translator, Box, Allocators> base;
+public:
+ typedef detail::insert<Value, Value, NodeProxy> base;
typedef typename base::node node;
typedef typename base::internal_node internal_node;
typedef typename base::leaf leaf;
- typedef typename Options::parameters_type parameters_type;
-
inline insert(node* & root,
size_t & leafs_level,
Value const& value,
- parameters_type const& parameters,
- Translator const& translator,
- Allocators & allocators,
+ NodeProxy & node_proxy,
size_t relative_level = 0
)
- : base(root, leafs_level, value, parameters, translator, allocators, relative_level)
+ : base(root, leafs_level, value, node_proxy, relative_level)
{}
inline void operator()(internal_node & n)
Modified: sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/visitors/is_leaf.hpp
==============================================================================
--- sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/visitors/is_leaf.hpp (original)
+++ sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/visitors/is_leaf.hpp 2012-09-30 07:11:50 EDT (Sun, 30 Sep 2012)
@@ -17,11 +17,19 @@
namespace detail { namespace rtree { namespace visitors {
-template <typename Value, typename Options, typename Box, typename Allocators>
-struct is_leaf : public rtree::visitor<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag, true>::type
+template <typename Value, typename NodeProxy>
+struct is_leaf
+ : public rtree::visitor<
+ Value,
+ typename NodeProxy::parameters_type,
+ typename NodeProxy::box_type,
+ typename NodeProxy::allocators_type,
+ typename NodeProxy::node_tag,
+ true
+ >::type
{
- 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 NodeProxy::internal_node internal_node;
+ typedef typename NodeProxy::leaf leaf;
inline void operator()(internal_node const&)
{
Modified: sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/visitors/nearest.hpp
==============================================================================
--- sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/visitors/nearest.hpp (original)
+++ sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/visitors/nearest.hpp 2012-09-30 07:11:50 EDT (Sun, 30 Sep 2012)
@@ -24,13 +24,13 @@
// in store() or break store to 2 functions e.g. should_store() and store()
// - well not with this algorithm of storing k-th neighbor
-template <typename Value, typename Translator, typename Point>
+template <typename Value, typename NodeProxy, typename Point>
struct nearest_one
{
public:
typedef typename geometry::default_distance_result<
Point,
- typename translator::indexable_type<Translator>::type
+ typename NodeProxy::indexable_type
>::type distance_type;
inline nearest_one()
@@ -67,13 +67,13 @@
distance_type m_comp_dist;
};
-template <typename Value, typename Translator, typename Point>
+template <typename Value, typename NodeProxy, typename Point>
struct nearest_k
{
public:
typedef typename geometry::default_distance_result<
Point,
- typename translator::indexable_type<Translator>::type
+ typename NodeProxy::indexable_type
>::type distance_type;
inline explicit nearest_k(size_t k)
@@ -112,7 +112,7 @@
inline distance_type comparable_distance() const
{
- return m_neighbors.size() < 0
+ return m_neighbors.size() == 0
? (std::numeric_limits<distance_type>::max)()
: m_neighbors.front().first;
}
@@ -144,43 +144,50 @@
template <
typename Value,
- typename Options,
- typename Translator,
- typename Box,
- typename Allocators,
+ typename NodeProxy,
typename DistancesPredicates,
typename Predicates,
typename Result
>
class nearest
- : public rtree::visitor<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag, true>::type
+ : public rtree::visitor<
+ Value,
+ typename NodeProxy::parameters_type,
+ typename NodeProxy::box_type,
+ typename NodeProxy::allocators_type,
+ typename NodeProxy::node_tag,
+ true
+ >::type
, index::nonassignable
{
public:
- typedef typename Options::parameters_type parameters_type;
+ typedef typename NodeProxy::node node;
+ typedef typename NodeProxy::internal_node internal_node;
+ typedef typename NodeProxy::leaf leaf;
+ typedef typename NodeProxy::box_type box_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 index::detail::distances_calc<DistancesPredicates, Box, rtree::node_tag> node_distances_calc;
+ typedef index::detail::distances_calc<DistancesPredicates, box_type, node_tag> node_distances_calc;
typedef typename node_distances_calc::result_type node_distances_type;
- typedef index::detail::distances_predicates_check<DistancesPredicates, Box, rtree::node_tag> node_distances_predicates_check;
+ typedef index::detail::distances_predicates_check<DistancesPredicates, box_type, rtree::node_tag> node_distances_predicates_check;
typedef index::detail::distances_calc<
DistancesPredicates,
- typename translator::indexable_type<Translator>::type,
+ typename translator::indexable_type<
+ typename NodeProxy::translator_type
+ >::type,
rtree::value_tag
> value_distances_calc;
typedef typename value_distances_calc::result_type value_distances_type;
typedef index::detail::distances_predicates_check<
DistancesPredicates,
- typename translator::indexable_type<Translator>::type,
+ typename translator::indexable_type<
+ typename NodeProxy::translator_type
+ >::type,
rtree::value_tag
> value_distances_predicates_check;
- inline nearest(parameters_type const& parameters, Translator const& translator, DistancesPredicates const& dist_pred, Predicates const& pred, Result & r)
- : m_parameters(parameters), m_translator(translator)
+ inline nearest(NodeProxy const& node_proxy, DistancesPredicates const& dist_pred, Predicates const& pred, Result & r)
+ : m_node_proxy(node_proxy)
, m_dist_pred(dist_pred), m_pred(pred)
, m_result(r)
{}
@@ -196,7 +203,7 @@
elements_type,
std::pair<node_distances_type, const node *>
>::type active_branch_list;
- active_branch_list.reserve(m_parameters.get_max_elements());
+ active_branch_list.reserve(m_node_proxy.parameters().get_max_elements());
elements_type const& elements = rtree::elements(n);
@@ -261,10 +268,10 @@
it != elements.end(); ++it)
{
// if value meets predicates
- if ( index::predicates_check<rtree::value_tag>(m_pred, *it, m_translator(*it)) )
+ if ( index::predicates_check<rtree::value_tag>(m_pred, *it, m_node_proxy.indexable(*it)) )
{
// calculate values distance for distance predicate
- value_distances_type distances = value_distances_calc::apply(m_dist_pred, m_translator(*it));
+ value_distances_type distances = value_distances_calc::apply(m_dist_pred, m_node_proxy.indexable(*it));
// TODO: awulkiew - consider at first calculating point relation distance only,
// comparing it with m_result.comparable_distance if it's valid,
@@ -321,8 +328,8 @@
::template get<index::detail::to_nearest_tag>(d);
}
- parameters_type const& m_parameters;
- Translator const& m_translator;
+ NodeProxy const& m_node_proxy;
+
DistancesPredicates const& m_dist_pred;
Predicates const& m_pred;
Modified: sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/visitors/query.hpp
==============================================================================
--- sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/visitors/query.hpp (original)
+++ sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/visitors/query.hpp 2012-09-30 07:11:50 EDT (Sun, 30 Sep 2012)
@@ -17,17 +17,28 @@
namespace detail { namespace rtree { namespace visitors {
-template <typename Value, typename Options, typename Translator, typename Box, typename Allocators, typename Predicates, typename OutIter>
-struct query
- : public rtree::visitor<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag, true>::type
+template <typename Value, typename NodeProxy, typename Predicates, typename OutIter>
+class query
+ : public rtree::visitor<
+ Value,
+ typename NodeProxy::parameters_type,
+ typename NodeProxy::box_type,
+ typename NodeProxy::allocators_type,
+ typename NodeProxy::node_tag,
+ true
+ >::type
, index::nonassignable
{
- typedef typename rtree::node<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type node;
- typedef typename rtree::internal_node<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type internal_node;
- typedef typename rtree::leaf<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type leaf;
-
- inline query(Translator const& t, Predicates const& p, OutIter out_it)
- : tr(t), pred(p), out_iter(out_it), found_count(0)
+ typedef typename NodeProxy::node node;
+ typedef typename NodeProxy::internal_node internal_node;
+ typedef typename NodeProxy::leaf leaf;
+
+public:
+ inline query(NodeProxy const& node_proxy, Predicates const& predicates, OutIter out_it)
+ : out_iter(out_it)
+ , found_count(0)
+ , m_node_proxy(node_proxy)
+ , m_predicates(predicates)
{}
inline void operator()(internal_node const& n)
@@ -41,7 +52,7 @@
{
// if node meets predicates
// 0 - dummy value
- if ( index::predicates_check<rtree::node_tag>(pred, 0, it->first) )
+ if ( index::predicates_check<rtree::node_tag>(m_predicates, 0, m_node_proxy.indexable(*it)) )
rtree::apply_visitor(*this, *it->second);
}
}
@@ -56,7 +67,7 @@
it != elements.end(); ++it)
{
// if value meets predicates
- if ( index::predicates_check<rtree::value_tag>(pred, *it, tr(*it)) )
+ if ( index::predicates_check<rtree::value_tag>(m_predicates, *it, m_node_proxy.indexable(*it)) )
{
out_iter = *it;
++out_iter;
@@ -66,10 +77,12 @@
}
}
- Translator const& tr;
- Predicates const& pred;
OutIter out_iter;
size_t found_count;
+
+private:
+ NodeProxy const& m_node_proxy;
+ Predicates const& m_predicates;
};
}}} // namespace detail::rtree::visitors
Modified: sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/visitors/remove.hpp
==============================================================================
--- sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/visitors/remove.hpp (original)
+++ sandbox-branches/geometry/index_dev/boost/geometry/extensions/index/rtree/visitors/remove.hpp 2012-09-30 07:11:50 EDT (Sun, 30 Sep 2012)
@@ -22,28 +22,33 @@
namespace detail { namespace rtree { namespace visitors {
// Default remove algorithm
-template <typename Value, typename Options, typename Translator, typename Box, typename Allocators>
+template <typename Value, typename NodeProxy>
class remove
- : public rtree::visitor<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag, false>::type
+ : public rtree::visitor<
+ Value,
+ typename NodeProxy::parameters_type,
+ typename NodeProxy::box_type,
+ typename NodeProxy::allocators_type,
+ typename NodeProxy::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 NodeProxy::options_type options_type;
+ typedef typename NodeProxy::parameters_type parameters_type;
+ typedef typename NodeProxy::box_type box_type;
+
+ typedef typename NodeProxy::node node;
+ typedef typename NodeProxy::internal_node internal_node;
+ typedef typename NodeProxy::leaf leaf;
public:
inline remove(node* & root,
size_t & leafs_level,
Value const& value,
- parameters_type const& parameters,
- Translator const& translator,
- Allocators & allocators)
+ NodeProxy & node_proxy)
: m_value(value)
- , m_parameters(parameters)
- , m_translator(translator)
- , m_allocators(allocators)
+ , m_node_proxy(node_proxy)
, m_root_node(root)
, m_leafs_level(leafs_level)
, m_is_value_removed(false)
@@ -65,7 +70,7 @@
size_t child_node_index = 0;
for ( ; child_node_index < children.size() ; ++child_node_index )
{
- if ( geometry::covered_by(m_translator(m_value), children[child_node_index].first) )
+ if ( geometry::covered_by(m_node_proxy.indexable(m_value), children[child_node_index].first) )
{
// next traversing step
traverse_apply_visitor(n, child_node_index);
@@ -92,7 +97,7 @@
elements.erase(underfl_el_it);
// calc underflow
- m_is_underflow = elements.size() < m_parameters.get_min_elements();
+ m_is_underflow = elements.size() < m_node_proxy.parameters().get_min_elements();
}
// n is not root - adjust aabb
@@ -101,10 +106,10 @@
// underflow state should be ok here
// note that there may be less than min_elems elements in root
// so this condition should be checked only here
- BOOST_GEOMETRY_INDEX_ASSERT((elements.size() < m_parameters.get_min_elements()) == m_is_underflow, "unexpected state");
+ BOOST_GEOMETRY_INDEX_ASSERT((elements.size() < m_node_proxy.parameters().get_min_elements()) == m_is_underflow, "unexpected state");
rtree::elements(*m_parent)[m_current_child_index].first
- = rtree::elements_box<Box>(elements.begin(), elements.end(), m_translator);
+ = m_node_proxy.elements_box(elements.begin(), elements.end());
}
// n is root node
else
@@ -117,19 +122,19 @@
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;
+ is_leaf<Value, NodeProxy> 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);
+ m_node_proxy.template destroy<leaf>(it->second);
}
else
{
reinsert_elements(rtree::get<internal_node>(*it->second), it->first);
- rtree::destroy_node<Allocators, internal_node>::apply(m_allocators, it->second);
+ m_node_proxy.template destroy<internal_node>(it->second);
}
}
@@ -140,7 +145,7 @@
m_root_node = rtree::elements(n)[0].second;
--m_leafs_level;
- rtree::destroy_node<Allocators, internal_node>::apply(m_allocators, root_to_destroy);
+ m_node_proxy.template destroy<internal_node>(root_to_destroy);
}
}
}
@@ -154,7 +159,7 @@
// find value and remove it
for ( typename elements_type::iterator it = elements.begin() ; it != elements.end() ; ++it )
{
- if ( m_translator.equals(*it, m_value) )
+ if ( m_node_proxy.equals(*it, m_value) )
{
elements.erase(it);
m_is_value_removed = true;
@@ -166,13 +171,13 @@
if ( m_is_value_removed )
{
// calc underflow
- m_is_underflow = elements.size() < m_parameters.get_min_elements();
+ m_is_underflow = elements.size() < m_node_proxy.parameters().get_min_elements();
// n is not root - adjust aabb
if ( 0 != m_parent )
{
rtree::elements(*m_parent)[m_current_child_index].first
- = rtree::elements_box<Box>(elements.begin(), elements.end(), m_translator);
+ = m_node_proxy.elements_box(elements.begin(), elements.end());
}
}
}
@@ -209,18 +214,13 @@
visitors::insert<
typename elements_type::value_type,
Value,
- Options,
- Translator,
- Box,
- Allocators,
- typename Options::insert_tag
+ NodeProxy,
+ typename NodeProxy::options_type::insert_tag
> insert_v(
m_root_node,
m_leafs_level,
*it,
- m_parameters,
- m_translator,
- m_allocators,
+ m_node_proxy,
node_relative_level - 1);
rtree::apply_visitor(insert_v, *m_root_node);
@@ -228,9 +228,7 @@
}
Value const& m_value;
- parameters_type const& m_parameters;
- Translator const& m_translator;
- Allocators & m_allocators;
+ NodeProxy & m_node_proxy;
node* & m_root_node;
size_t & m_leafs_level;
Modified: sandbox-branches/geometry/index_dev/test/rtree/test_rtree.hpp
==============================================================================
--- sandbox-branches/geometry/index_dev/test/rtree/test_rtree.hpp (original)
+++ sandbox-branches/geometry/index_dev/test/rtree/test_rtree.hpp 2012-09-30 07:11:50 EDT (Sun, 30 Sep 2012)
@@ -183,7 +183,7 @@
Iter test_find(Rtree const& rtree, Iter first, Iter last, Value const& value)
{
for ( ; first != last ; ++first )
- if ( rtree.translator().equals(value, *first) )
+ if ( rtree.node_proxy().equals(value, *first) )
return first;
return first;
}
@@ -215,7 +215,7 @@
typename Range2::const_iterator it2 = expected_output.begin();
for ( ; it1 != output.end() && it2 != expected_output.end() ; ++it1, ++it2 )
{
- if ( !rtree.translator().equals(*it1, *it2) )
+ if ( !rtree.node_proxy().equals(*it1, *it2) )
{
BOOST_CHECK(false && "rtree.translator().equals(*it1, *it2)");
break;
@@ -255,7 +255,7 @@
std::vector<Value> expected_output;
BOOST_FOREACH(Value const& v, input)
- if ( bg::intersects(tree.translator()(v), qbox) )
+ if ( bg::intersects(tree.node_proxy().indexable(v), qbox) )
expected_output.push_back(v);
test_query(tree, qbox, expected_output);
@@ -271,7 +271,7 @@
std::vector<Value> expected_output;
BOOST_FOREACH(Value const& v, input)
- if ( bg::covered_by(tree.translator()(v), qbox) )
+ if ( bg::covered_by(tree.node_proxy().indexable(v), qbox) )
expected_output.push_back(v);
test_query(tree, bgi::covered_by(qbox), expected_output);
@@ -286,7 +286,7 @@
std::vector<Value> expected_output;
BOOST_FOREACH(Value const& v, input)
- if ( bg::overlaps(tree.translator()(v), qbox) )
+ if ( bg::overlaps(tree.node_proxy().indexable(v), qbox) )
expected_output.push_back(v);
test_query(tree, bgi::overlaps(qbox), expected_output);
@@ -354,7 +354,7 @@
std::vector<Value> expected_output;
BOOST_FOREACH(Value const& v, input)
- if ( bg::within(tree.translator()(v), qbox) )
+ if ( bg::within(tree.node_proxy().indexable(v), qbox) )
expected_output.push_back(v);
test_query(tree, bgi::within(qbox), expected_output);
@@ -373,7 +373,7 @@
Value expected_output;
BOOST_FOREACH(Value const& v, input)
{
- D d = bgi::comparable_distance_near(pt, rtree.translator()(v));
+ D d = bgi::comparable_distance_near(pt, rtree.node_proxy().indexable(v));
if ( d < smallest_d )
{
smallest_d = d;
@@ -391,10 +391,10 @@
// TODO - perform explicit check here?
// should all objects which are closest be checked and should exactly the same be found?
- if ( !rtree.translator().equals(output, expected_output) )
+ if ( !rtree.node_proxy().equals(output, expected_output) )
{
- D d1 = bgi::comparable_distance_near(pt, rtree.translator()(output));
- D d2 = bgi::comparable_distance_near(pt, rtree.translator()(expected_output));
+ D d1 = bgi::comparable_distance_near(pt, rtree.node_proxy().indexable(output));
+ D d2 = bgi::comparable_distance_near(pt, rtree.node_proxy().indexable(expected_output));
BOOST_CHECK(d1 == d2);
}
}
@@ -437,7 +437,7 @@
// calculate test output - k closest values pairs
BOOST_FOREACH(Value const& v, input)
{
- D d = bgi::comparable_distance_near(pt, rtree.translator()(v));
+ D d = bgi::comparable_distance_near(pt, rtree.node_proxy().indexable(v));
if ( test_output.size() < k )
test_output.push_back(std::make_pair(d, v));
@@ -473,7 +473,7 @@
if ( test_find(rtree, expected_output.begin(), expected_output.end(), v) == expected_output.end() )
{
- D d = bgi::comparable_distance_near(pt, rtree.translator()(v));
+ D d = bgi::comparable_distance_near(pt, rtree.node_proxy().indexable(v));
BOOST_CHECK(d == biggest_d);
}
}
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