|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r72618 - in sandbox-branches/geometry/index: boost/geometry/extensions/index boost/geometry/extensions/index/algorithms 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 tests
From: adam.wulkiewicz_at_[hidden]
Date: 2011-06-16 17:15:09
Author: awulkiew
Date: 2011-06-16 17:15:06 EDT (Thu, 16 Jun 2011)
New Revision: 72618
URL: http://svn.boost.org/trac/boost/changeset/72618
Log:
min and max elements numbers are now template parameters. New node type added - with arrays of static size. Various parameters are the first template parameter of options::rtree.
Added:
sandbox-branches/geometry/index/boost/geometry/extensions/index/pushable_array.hpp (contents, props changed)
sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/node/node_default_static.hpp (contents, props changed)
Text files modified:
sandbox-branches/geometry/index/boost/geometry/extensions/index/algorithms/margin.hpp | 2
sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/linear/redistribute_elements.hpp | 68 +++++++++++++-----------
sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/node/node.hpp | 2
sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/node/node_default.hpp | 98 ++++++++++++++++++------------------
sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/node/node_default_variant.hpp | 88 ++++++++++++++++----------------
sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/options.hpp | 107 +++++++++++++++++++++++++++++++--------
sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/quadratic/redistribute_elements.hpp | 6 +-
sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/rstar/choose_next_node.hpp | 23 +++++++-
sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/rstar/insert.hpp | 73 +++++++++++---------------
sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/rstar/redistribute_elements.hpp | 91 ++++++++++++++++-----------------
sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/rtree.hpp | 12 ++--
sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/are_boxes_ok.hpp | 6 +-
sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/are_levels_ok.hpp | 6 +-
sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/destroy.hpp | 6 +-
sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/find.hpp | 8 +-
sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/insert.hpp | 40 ++++++--------
sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/is_leaf.hpp | 6 +-
sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/remove.hpp | 28 +++------
sandbox-branches/geometry/index/tests/additional_sizes_and_times.cpp | 12 ++--
19 files changed, 369 insertions(+), 313 deletions(-)
Modified: sandbox-branches/geometry/index/boost/geometry/extensions/index/algorithms/margin.hpp
==============================================================================
--- sandbox-branches/geometry/index/boost/geometry/extensions/index/algorithms/margin.hpp (original)
+++ sandbox-branches/geometry/index/boost/geometry/extensions/index/algorithms/margin.hpp 2011-06-16 17:15:06 EDT (Thu, 16 Jun 2011)
@@ -61,7 +61,7 @@
template <typename Box>
struct margin_for_each_edge<Box, 1, 1>
{
- static inline typename default_margin_result<Box>::type apply(Box const& b)
+ static inline typename default_margin_result<Box>::type apply(Box const& /*b*/)
{
return 1;
}
Added: sandbox-branches/geometry/index/boost/geometry/extensions/index/pushable_array.hpp
==============================================================================
--- (empty file)
+++ sandbox-branches/geometry/index/boost/geometry/extensions/index/pushable_array.hpp 2011-06-16 17:15:06 EDT (Thu, 16 Jun 2011)
@@ -0,0 +1,139 @@
+// Boost.Geometry (aka GGL, Generic Geometry Library)
+//
+// Boost.Index - pushable array
+//
+// Copyright 2011 Adam Wulkiewicz.
+// Use, modification and distribution is subject to the Boost Software License,
+// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+#ifndef BOOST_GEOMETRY_EXTENSIONS_INDEX_PUSHABLE_ARRAY_HPP
+#define BOOST_GEOMETRY_EXTENSIONS_INDEX_PUSHABLE_ARRAY_HPP
+
+#include <boost/array.hpp>
+
+#include <boost/geometry/extensions/index/assert.hpp>
+
+namespace boost { namespace geometry { namespace index {
+
+template <typename Element, size_t Capacity>
+class pushable_array
+{
+ typedef typename boost::array<Element, Capacity> array_type;
+
+public:
+ typedef typename array_type::value_type value_type;
+ typedef typename array_type::size_type size_type;
+ typedef typename array_type::iterator iterator;
+ typedef typename array_type::const_iterator const_iterator;
+
+ inline pushable_array()
+ : m_size(0)
+ {}
+
+ inline pushable_array(size_type s, Element const& v)
+ : m_size(s)
+ {
+ BOOST_GEOMETRY_INDEX_ASSERT(s < Capacity, "size too big");
+ std::fill(m_array.begin(), m_array.begin() + s, v);
+ }
+
+ inline Element & operator[](size_type i)
+ {
+ BOOST_GEOMETRY_INDEX_ASSERT(i < m_size, "index of the element outside the container");
+ return m_array[i];
+ }
+
+ inline Element const& operator[](size_type i) const
+ {
+ BOOST_GEOMETRY_INDEX_ASSERT(i < m_size, "index of the element outside the container");
+ return m_array[i];
+ }
+
+ inline Element const& front() const
+ {
+ BOOST_GEOMETRY_INDEX_ASSERT(0 < m_size, "there are no elements in the container");
+ return m_array.front();
+ }
+
+ inline Element & front()
+ {
+ BOOST_GEOMETRY_INDEX_ASSERT(0 < m_size, "there are no elements in the container");
+ return m_array.front();
+ }
+
+ inline Element const& back() const
+ {
+ BOOST_GEOMETRY_INDEX_ASSERT(0 < m_size, "there are no elements in the container");
+ return *(begin() + (m_size - 1));
+ }
+
+ inline Element & back()
+ {
+ BOOST_GEOMETRY_INDEX_ASSERT(0 < m_size, "there are no elements in the container");
+ return *(begin() + (m_size - 1));
+ }
+
+ inline iterator begin()
+ {
+ return m_array.begin();
+ }
+
+ inline iterator end()
+ {
+ return m_array.begin() + m_size;
+ }
+
+ inline const_iterator begin() const
+ {
+ return m_array.begin();
+ }
+
+ inline const_iterator end() const
+ {
+ return m_array.begin() + m_size;
+ }
+
+ inline void clear()
+ {
+ m_size = 0;
+ }
+
+ inline void erase(iterator it)
+ {
+ BOOST_GEOMETRY_INDEX_ASSERT(0 < m_size, "there are no elements in the container");
+ BOOST_GEOMETRY_INDEX_ASSERT(begin() <= it && it < end(), "iterator points on the element outside the container");
+ //std::copy(it + 1, end(), it);
+ *it = back();
+ --m_size;
+ }
+
+ inline void push_back(Element const& v)
+ {
+ BOOST_GEOMETRY_INDEX_ASSERT(m_size < Capacity, "can't further increase the size of the container");
+ m_array[m_size++] = v;
+ }
+
+ inline bool empty() const
+ {
+ return m_size == 0;
+ }
+
+ inline size_t size() const
+ {
+ return m_size;
+ }
+
+ inline size_t capacity() const
+ {
+ return Capacity;
+ }
+
+private:
+ boost::array<Element, Capacity> m_array;
+ size_type m_size;
+};
+
+}}} // namespace boost::geometry::index
+
+#endif // BOOST_GEOMETRY_EXTENSIONS_INDEX_PUSHABLE_ARRAY_HPP
Modified: sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/linear/redistribute_elements.hpp
==============================================================================
--- sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/linear/redistribute_elements.hpp (original)
+++ sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/linear/redistribute_elements.hpp 2011-06-16 17:15:06 EDT (Thu, 16 Jun 2011)
@@ -36,7 +36,7 @@
// from void find_normalized_separations(std::vector<Box> const& boxes, T& separation, unsigned int& first, unsigned int& second) const
-template <typename Elements, typename Translator, size_t DimensionIndex>
+template <typename Elements, typename Parameters, typename Translator, size_t DimensionIndex>
struct find_greatest_normalized_separation
{
typedef typename Elements::value_type element_type;
@@ -49,9 +49,9 @@
size_t & seed1,
size_t & seed2)
{
- size_t elements_count = elements.size();
-
- BOOST_GEOMETRY_INDEX_ASSERT(2 <= elements_count, "wrong number of elements");
+ const size_t elements_count = Parameters::max_elements + 1;
+ BOOST_GEOMETRY_INDEX_ASSERT(elements.size() == elements_count, "unexpected number of elements");
+ BOOST_STATIC_ASSERT(2 <= elements_count);
// find the lowest low, highest high
coordinate_type lowest_low = index::get<min_corner, DimensionIndex>(rtree::element_indexable(elements[0], tr));
@@ -99,7 +99,7 @@
}
};
-template <typename Elements, typename Translator, size_t DimensionIndex>
+template <typename Elements, typename Parameters, typename Translator, size_t DimensionIndex>
struct pick_seeds_impl
{
BOOST_STATIC_ASSERT(0 < DimensionIndex);
@@ -114,11 +114,11 @@
size_t & seed1,
size_t & seed2)
{
- pick_seeds_impl<Elements, Translator, DimensionIndex - 1>::apply(elements, tr, separation, seed1, seed2);
+ pick_seeds_impl<Elements, Parameters, Translator, DimensionIndex - 1>::apply(elements, tr, separation, seed1, seed2);
coordinate_type current_separation;
size_t s1, s2;
- find_greatest_normalized_separation<Elements, Translator, DimensionIndex - 1>::apply(elements, tr, current_separation, s1, s2);
+ find_greatest_normalized_separation<Elements, Parameters, Translator, DimensionIndex - 1>::apply(elements, tr, current_separation, s1, s2);
// in the old implementation different operator was used: <= (y axis prefered)
if ( separation < current_separation )
@@ -130,8 +130,8 @@
}
};
-template <typename Elements, typename Translator>
-struct pick_seeds_impl<Elements, Translator, 1>
+template <typename Elements, typename Parameters, typename Translator>
+struct pick_seeds_impl<Elements, Parameters, Translator, 1>
{
typedef typename Elements::value_type element_type;
typedef typename rtree::element_indexable_type<element_type, Translator>::type indexable_type;
@@ -143,13 +143,13 @@
size_t & seed1,
size_t & seed2)
{
- find_greatest_normalized_separation<Elements, Translator, 0>::apply(elements, tr, separation, seed1, seed2);
+ find_greatest_normalized_separation<Elements, Parameters, Translator, 0>::apply(elements, tr, separation, seed1, seed2);
}
};
// from void linear_pick_seeds(node_pointer const& n, unsigned int &seed1, unsigned int &seed2) const
-template <typename Elements, typename Translator>
+template <typename Elements, typename Parameters, typename Translator>
struct pick_seeds
{
typedef typename Elements::value_type element_type;
@@ -159,12 +159,12 @@
static const size_t dimension = index::traits::dimension<indexable_type>::value;
static inline void apply(Elements const& elements,
- Translator const& tr,
- size_t & seed1,
- size_t & seed2)
+ Translator const& tr,
+ size_t & seed1,
+ size_t & seed2)
{
coordinate_type separation = 0;
- pick_seeds_impl<Elements, Translator, dimension>::apply(elements, tr, separation, seed1, seed2);
+ pick_seeds_impl<Elements, Parameters, Translator, dimension>::apply(elements, tr, separation, seed1, seed2);
}
};
@@ -175,17 +175,17 @@
template <typename Value, typename Options, typename Translator, typename Box>
struct redistribute_elements<Value, Options, Translator, Box, linear_tag>
{
- typedef typename rtree::node<Value, Box, typename Options::node_tag>::type node;
- typedef typename rtree::internal_node<Value, Box, typename Options::node_tag>::type internal_node;
- typedef typename rtree::leaf<Value, Box, typename Options::node_tag>::type leaf;
+ typedef typename rtree::node<Value, typename Options::parameters_type, Box, typename Options::node_tag>::type node;
+ typedef typename rtree::internal_node<Value, typename Options::parameters_type, Box, typename Options::node_tag>::type internal_node;
+ typedef typename rtree::leaf<Value, typename Options::parameters_type, Box, typename Options::node_tag>::type leaf;
+
+ typedef typename Options::parameters_type parameters_type;
template <typename Node>
static inline void apply(Node & n,
Node & second_node,
Box & box1,
Box & box2,
- size_t min_elems,
- size_t max_elems,
Translator const& tr)
{
typedef typename rtree::elements_type<Node>::type elements_type;
@@ -194,18 +194,24 @@
typedef typename index::traits::coordinate_type<indexable_type>::type coordinate_type;
typedef typename index::default_area_result<Box>::type area_type;
- // copy original elements
- elements_type elements_copy = rtree::elements(n);
- size_t elements_count = elements_copy.size();
+ elements_type & elements1 = rtree::elements(n);
+ elements_type & elements2 = rtree::elements(second_node);
+ const size_t elements1_count = parameters_type::max_elements + 1;
+
+ BOOST_GEOMETRY_INDEX_ASSERT(elements1.size() == elements1_count, "unexpected number of elements");
+
+ typedef boost::array<element_type, elements1_count> elements_copy_type;
+
+ // copy original elements
+ elements_copy_type elements_copy;
+ std::copy(elements1.begin(), elements1.end(), elements_copy.begin());
// calculate initial seeds
size_t seed1 = 0;
size_t seed2 = 0;
- linear::pick_seeds<elements_type, Translator>::apply(elements_copy, tr, seed1, seed2);
+ linear::pick_seeds<elements_copy_type, parameters_type, Translator>::apply(elements_copy, tr, seed1, seed2);
// prepare nodes' elements containers
- elements_type & elements1 = rtree::elements(n);
- elements_type & elements2 = rtree::elements(second_node);
elements1.clear();
assert(elements2.empty());
@@ -221,11 +227,11 @@
area_type area1 = index::area(box1);
area_type area2 = index::area(box2);
- assert(2 <= elements_count);
- size_t remaining = elements_count - 2;
+ BOOST_STATIC_ASSERT(2 <= elements1_count);
+ size_t remaining = elements1_count - 2;
// redistribute the rest of the elements
- for ( size_t i = 0 ; i < elements_count ; ++i )
+ for ( size_t i = 0 ; i < elements1_count ; ++i )
{
if (i != seed1 && i != seed2)
{
@@ -234,13 +240,13 @@
// 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 <= min_elems )
+ if ( elements1.size() + remaining <= parameters_type::min_elements )
{
elements1.push_back(elem);
geometry::expand(box1, indexable);
area1 = index::area(box1);
}
- else if ( elements2.size() + remaining <= min_elems )
+ else if ( elements2.size() + remaining <= parameters_type::min_elements )
{
elements2.push_back(elem);
geometry::expand(box2, indexable);
Modified: sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/node/node.hpp
==============================================================================
--- sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/node/node.hpp (original)
+++ sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/node/node.hpp 2011-06-16 17:15:06 EDT (Thu, 16 Jun 2011)
@@ -13,4 +13,6 @@
#include <boost/geometry/extensions/index/rtree/node/node_default.hpp>
#include <boost/geometry/extensions/index/rtree/node/node_default_variant.hpp>
+#include <boost/geometry/extensions/index/rtree/node/node_default_static.hpp>
+
#endif // BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_NODE_NODE_HPP
Modified: sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/node/node_default.hpp
==============================================================================
--- sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/node/node_default.hpp (original)
+++ sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/node/node_default.hpp 2011-06-16 17:15:06 EDT (Thu, 16 Jun 2011)
@@ -19,74 +19,74 @@
namespace detail { namespace rtree {
// visitor forward declaration
-template <typename Value, typename Box, typename Tag, bool IsVisitableConst>
+template <typename Value, typename Parameters, typename Box, typename Tag, bool IsVisitableConst>
struct visitor_poly;
// nodes types
-template <typename Value, typename Box, typename Tag>
+template <typename Value, typename Parameters, typename Box, typename Tag>
struct node_poly
{
virtual ~node_poly() {}
- virtual void apply_visitor(visitor_poly<Value, Box, Tag, false> &) = 0;
- virtual void apply_visitor(visitor_poly<Value, Box, Tag, true> &) const = 0;
+ virtual void apply_visitor(visitor_poly<Value, Parameters, Box, Tag, false> &) = 0;
+ virtual void apply_visitor(visitor_poly<Value, Parameters, Box, Tag, true> &) const = 0;
};
-template <typename Value, typename Box, typename Tag>
-struct internal_node_poly : public node_poly<Value, Box, Tag>
+template <typename Value, typename Parameters, typename Box, typename Tag>
+struct internal_node_poly : public node_poly<Value, Parameters, Box, Tag>
{
typedef std::vector<
- std::pair<Box, node_poly<Value, Box, Tag> *>
+ std::pair<Box, node_poly<Value, Parameters, Box, Tag> *>
> elements_type;
- void apply_visitor(visitor_poly<Value, Box, Tag, false> & v) { v(*this); }
- void apply_visitor(visitor_poly<Value, Box, Tag, true> & v) const { v(*this); }
+ void apply_visitor(visitor_poly<Value, Parameters, Box, Tag, false> & v) { v(*this); }
+ void apply_visitor(visitor_poly<Value, Parameters, Box, Tag, true> & v) const { v(*this); }
elements_type elements;
};
-template <typename Value, typename Box, typename Tag>
-struct leaf_poly : public node_poly<Value, Box, Tag>
+template <typename Value, typename Parameters, typename Box, typename Tag>
+struct leaf_poly : public node_poly<Value, Parameters, Box, Tag>
{
typedef std::vector<Value> elements_type;
- void apply_visitor(visitor_poly<Value, Box, Tag, false> & v) { v(*this); }
- void apply_visitor(visitor_poly<Value, Box, Tag, true> & v) const { v(*this); }
+ void apply_visitor(visitor_poly<Value, Parameters, Box, Tag, false> & v) { v(*this); }
+ void apply_visitor(visitor_poly<Value, Parameters, Box, Tag, true> & v) const { v(*this); }
elements_type elements;
};
// nodes traits
-template <typename Value, typename Box, typename Tag>
+template <typename Value, typename Parameters, typename Box, typename Tag>
struct node
{
- typedef node_poly<Value, Box, Tag> type;
+ typedef node_poly<Value, Parameters, Box, Tag> type;
};
-template <typename Value, typename Box, typename Tag>
+template <typename Value, typename Parameters, typename Box, typename Tag>
struct internal_node
{
- typedef internal_node_poly<Value, Box, Tag> type;
+ typedef internal_node_poly<Value, Parameters, Box, Tag> type;
};
-template <typename Value, typename Box, typename Tag>
+template <typename Value, typename Parameters, typename Box, typename Tag>
struct leaf
{
- typedef leaf_poly<Value, Box, Tag> type;
+ typedef leaf_poly<Value, Parameters, Box, Tag> type;
};
// nodes conversion
-template <typename Derived, typename Value, typename Box, typename Tag>
-inline Derived & get(node_poly<Value, Box, Tag> & n)
+template <typename Derived, typename Parameters, typename Value, typename Box, typename Tag>
+inline Derived & get(node_poly<Value, Parameters, Box, Tag> & n)
{
assert(dynamic_cast<Derived*>(&n));
return static_cast<Derived&>(n);
}
-template <typename Derived, typename Value, typename Box, typename Tag>
-inline Derived * get(node_poly<Value, Box, Tag> * n)
+template <typename Derived, typename Parameters, typename Value, typename Box, typename Tag>
+inline Derived * get(node_poly<Value, Parameters, Box, Tag> * n)
{
assert(dynamic_cast<Derived*>(n));
return static_cast<Derived*>(n);
@@ -94,11 +94,11 @@
// visitor
-template <typename Value, typename Box, typename Tag>
-struct visitor_poly<Value, Box, Tag, true>
+template <typename Value, typename Parameters, typename Box, typename Tag>
+struct visitor_poly<Value, Parameters, Box, Tag, true>
{
- typedef typename internal_node<Value, Box, Tag>::type internal_node;
- typedef typename leaf<Value, Box, Tag>::type leaf;
+ typedef typename internal_node<Value, Parameters, Box, Tag>::type internal_node;
+ typedef typename leaf<Value, Parameters, Box, Tag>::type leaf;
virtual ~visitor_poly() {}
@@ -106,11 +106,11 @@
virtual void operator()(leaf const&) = 0;
};
-template <typename Value, typename Box, typename Tag>
-struct visitor_poly<Value, Box, Tag, false>
+template <typename Value, typename Parameters, typename Box, typename Tag>
+struct visitor_poly<Value, Parameters, Box, Tag, false>
{
- typedef typename internal_node<Value, Box, Tag>::type internal_node;
- typedef typename leaf<Value, Box, Tag>::type leaf;
+ typedef typename internal_node<Value, Parameters, Box, Tag>::type internal_node;
+ typedef typename leaf<Value, Parameters, Box, Tag>::type leaf;
virtual ~visitor_poly() {}
@@ -120,10 +120,10 @@
// visitor traits
-template <typename Value, typename Box, typename Tag, bool IsVisitableConst>
+template <typename Value, typename Parameters, typename Box, typename Tag, bool IsVisitableConst>
struct visitor
{
- typedef visitor_poly<Value, Box, Tag, IsVisitableConst> type;
+ typedef visitor_poly<Value, Parameters, Box, Tag, IsVisitableConst> type;
};
template <typename Visitor, typename Visitable>
@@ -140,9 +140,9 @@
typedef typename Translator::indexable_type type;
};
-template <typename Value, typename Box, typename Tag, typename Translator>
+template <typename Value, typename Parameters, typename Box, typename Tag, typename Translator>
struct element_indexable_type<
- std::pair<Box, node_poly<Value, Box, Tag> *>,
+ std::pair<Box, node_poly<Value, Parameters, Box, Tag> *>,
Translator
>
{
@@ -158,10 +158,10 @@
return tr(el);
};
-template <typename Value, typename Box, typename Tag, typename Translator>
+template <typename Value, typename Parameters, typename Box, typename Tag, typename Translator>
inline Box const&
element_indexable(
- std::pair< Box, node_poly<Value, Box, Tag> *> const& el,
+ std::pair< Box, node_poly<Value, Parameters, Box, Tag> *> const& el,
Translator const&)
{
return el.first;
@@ -169,30 +169,30 @@
// create leaf node
-template <typename Value, typename Box, typename Tag>
-inline typename node<Value, Box, Tag>::type *
-create_node(leaf_poly<Value, Box, Tag> const& l)
+template <typename Value, typename Parameters, typename Box, typename Tag>
+inline typename node<Value, Parameters, Box, Tag>::type *
+create_node(leaf_poly<Value, Parameters, Box, Tag> const& l)
{
- typedef typename node<Value, Box, Tag>::type node;
- node * n = new leaf_poly<Value, Box, Tag>(l);
+ typedef typename node<Value, Parameters, Box, Tag>::type node;
+ node * n = new leaf_poly<Value, Parameters, Box, Tag>(l);
return n;
}
// create internal node
-template <typename Value, typename Box, typename Tag>
-inline typename node<Value, Box, Tag>::type *
-create_node(internal_node_poly<Value, Box, Tag> const& in)
+template <typename Value, typename Parameters, typename Box, typename Tag>
+inline typename node<Value, Parameters, Box, Tag>::type *
+create_node(internal_node_poly<Value, Parameters, Box, Tag> const& in)
{
- typedef typename node<Value, Box, Tag>::type node;
- node * n = new internal_node_poly<Value, Box, Tag>(in);
+ typedef typename node<Value, Parameters, Box, Tag>::type node;
+ node * n = new internal_node_poly<Value, Parameters, Box, Tag>(in);
return n;
}
// default node
-template <typename Value, typename Box, typename Tag>
-inline void delete_node(node_poly<Value, Box, Tag> * n)
+template <typename Value, typename Parameters, typename Box, typename Tag>
+inline void delete_node(node_poly<Value, Parameters, Box, Tag> * n)
{
delete n;
}
Added: sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/node/node_default_static.hpp
==============================================================================
--- (empty file)
+++ sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/node/node_default_static.hpp 2011-06-16 17:15:06 EDT (Thu, 16 Jun 2011)
@@ -0,0 +1,50 @@
+// Boost.Geometry (aka GGL, Generic Geometry Library)
+//
+// Boost.Index - R-tree polymorphic nodes with static-size containers
+//
+// Copyright 2011 Adam Wulkiewicz.
+// Use, modification and distribution is subject to the Boost Software License,
+// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+#ifndef BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_NODE_NODE_DEFAULT_STATIC_HPP
+#define BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_NODE_NODE_DEFAULT_STATIC_HPP
+
+#include <boost/geometry/extensions/index/pushable_array.hpp>
+
+namespace boost { namespace geometry { namespace index {
+
+namespace detail { namespace rtree {
+
+template <typename Value, typename Parameters, typename Box>
+struct internal_node_poly<Value, Parameters, Box, default_static_tag>
+ : public node_poly<Value, Parameters, Box, default_static_tag>
+{
+ typedef index::pushable_array<
+ std::pair<Box, node_poly<Value, Parameters, Box, default_static_tag> *>,
+ Parameters::max_elements + 1
+ > elements_type;
+
+ void apply_visitor(visitor_poly<Value, Parameters, Box, default_static_tag, false> & v) { v(*this); }
+ void apply_visitor(visitor_poly<Value, Parameters, Box, default_static_tag, true> & v) const { v(*this); }
+
+ elements_type elements;
+};
+
+template <typename Value, typename Parameters, typename Box>
+struct leaf_poly<Value, Parameters, Box, default_static_tag>
+ : public node_poly<Value, Parameters, Box, default_static_tag>
+{
+ typedef index::pushable_array<Value, Parameters::max_elements + 1> elements_type;
+
+ void apply_visitor(visitor_poly<Value, Parameters, Box, default_static_tag, false> & v) { v(*this); }
+ void apply_visitor(visitor_poly<Value, Parameters, Box, default_static_tag, true> & v) const { v(*this); }
+
+ elements_type elements;
+};
+
+}} // namespace detail::rtree
+
+}}} // namespace boost::geometry::index
+
+#endif // BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_NODE_NODE_DEFAULT_STATIC_HPP
Modified: sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/node/node_default_variant.hpp
==============================================================================
--- sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/node/node_default_variant.hpp (original)
+++ sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/node/node_default_variant.hpp 2011-06-16 17:15:06 EDT (Thu, 16 Jun 2011)
@@ -19,20 +19,20 @@
// nodes default types
-template <typename Value, typename Box, typename Tag>
+template <typename Value, typename Parameters, typename Box, typename Tag>
struct internal_node_variant
{
typedef std::vector<
std::pair<
Box,
- typename node<Value, Box, Tag>::type *
+ typename node<Value, Parameters, Box, Tag>::type *
>
> elements_type;
elements_type elements;
};
-template <typename Value, typename Box, typename Tag>
+template <typename Value, typename Parameters, typename Box, typename Tag>
struct leaf_variant
{
typedef std::vector<Value> elements_type;
@@ -41,44 +41,44 @@
// nodes traits
-template <typename Value, typename Box>
-struct node<Value, Box, default_variant_tag>
+template <typename Value, typename Parameters, typename Box>
+struct node<Value, Parameters, Box, default_variant_tag>
{
typedef boost::variant<
- leaf_variant<Value, Box, default_variant_tag>,
- internal_node_variant<Value, Box, default_variant_tag>
+ leaf_variant<Value, Parameters, Box, default_variant_tag>,
+ internal_node_variant<Value, Parameters, Box, default_variant_tag>
> type;
};
-template <typename Value, typename Box>
-struct internal_node<Value, Box, default_variant_tag>
+template <typename Value, typename Parameters, typename Box>
+struct internal_node<Value, Parameters, Box, default_variant_tag>
{
- typedef internal_node_variant<Value, Box, default_variant_tag> type;
+ typedef internal_node_variant<Value, Parameters, Box, default_variant_tag> type;
};
-template <typename Value, typename Box>
-struct leaf<Value, Box, default_variant_tag>
+template <typename Value, typename Parameters, typename Box>
+struct leaf<Value, Parameters, Box, default_variant_tag>
{
- typedef leaf_variant<Value, Box, default_variant_tag> type;
+ typedef leaf_variant<Value, Parameters, Box, default_variant_tag> type;
};
// nodes conversion
-template <typename V, typename Value, typename Box, typename Tag>
+template <typename V, typename Value, typename Parameters, typename Box, typename Tag>
inline V & get(
boost::variant<
- leaf_variant<Value, Box, Tag>,
- internal_node_variant<Value, Box, Tag>
+ leaf_variant<Value, Parameters, Box, Tag>,
+ internal_node_variant<Value, Parameters, Box, Tag>
> &v
)
{
return boost::get<V>(v);
}
-template <typename V, typename Value, typename Box, typename Tag>
+template <typename V, typename Value, typename Parameters, typename Box, typename Tag>
inline V * get(boost::variant<
- leaf_variant<Value, Box, Tag>,
- internal_node_variant<Value, Box, Tag>
+ leaf_variant<Value, Parameters, Box, Tag>,
+ internal_node_variant<Value, Parameters, Box, Tag>
> *v)
{
return boost::get<V>(v);
@@ -86,27 +86,27 @@
// visitor traits
-template <typename Value, typename Box, bool IsVisitableConst>
-struct visitor<Value, Box, default_variant_tag, IsVisitableConst>
+template <typename Value, typename Parameters, typename Box, bool IsVisitableConst>
+struct visitor<Value, Parameters, Box, default_variant_tag, IsVisitableConst>
{
typedef static_visitor<> type;
};
-template <typename Visitor, typename Value, typename Box, typename Tag>
+template <typename Visitor, typename Value, typename Parameters, typename Box, typename Tag>
inline void apply_visitor(Visitor & v,
boost::variant<
- leaf_variant<Value, Box, Tag>,
- internal_node_variant<Value, Box, Tag>
+ leaf_variant<Value, Parameters, Box, Tag>,
+ internal_node_variant<Value, Parameters, Box, Tag>
> & n)
{
boost::apply_visitor(v, n);
}
-template <typename Visitor, typename Value, typename Box, typename Tag>
+template <typename Visitor, typename Value, typename Parameters, typename Box, typename Tag>
inline void apply_visitor(Visitor & v,
boost::variant<
- leaf_variant<Value, Box, Tag>,
- internal_node_variant<Value, Box, Tag>
+ leaf_variant<Value, Parameters, Box, Tag>,
+ internal_node_variant<Value, Parameters, Box, Tag>
> const& n)
{
boost::apply_visitor(v, n);
@@ -114,13 +114,13 @@
// element's indexable type
-template <typename Value, typename Box, typename Tag, typename Translator>
+template <typename Value, typename Parameters, typename Box, typename Tag, typename Translator>
struct element_indexable_type<
std::pair<
Box,
boost::variant<
- leaf_variant<Value, Box, Tag>,
- internal_node_variant<Value, Box, Tag>
+ leaf_variant<Value, Parameters, Box, Tag>,
+ internal_node_variant<Value, Parameters, Box, Tag>
> *
>,
Translator
@@ -131,13 +131,13 @@
// element's indexable getter
-template <typename Value, typename Box, typename Tag, typename Translator>
+template <typename Value, typename Parameters, typename Box, typename Tag, typename Translator>
inline Box const&
element_indexable(std::pair<
Box,
boost::variant<
- leaf_variant<Value, Box, Tag>,
- internal_node_variant<Value, Box, Tag>
+ leaf_variant<Value, Parameters, Box, Tag>,
+ internal_node_variant<Value, Parameters, Box, Tag>
> *
> const& el,
Translator const&)
@@ -147,32 +147,32 @@
// create leaf node
-template <typename Value, typename Box, typename Tag>
-inline typename node<Value, Box, Tag>::type *
-create_node(leaf_variant<Value, Box, Tag> const& l)
+template <typename Value, typename Parameters, typename Box, typename Tag>
+inline typename node<Value, Parameters, Box, Tag>::type *
+create_node(leaf_variant<Value, Parameters, Box, Tag> const& l)
{
- typedef typename node<Value, Box, Tag>::type node;
+ typedef typename node<Value, Parameters, Box, Tag>::type node;
node * n = new node(l);
return n;
}
// create internal node
-template <typename Value, typename Box, typename Tag>
-inline typename node<Value, Box, Tag>::type *
-create_node(internal_node_variant<Value, Box, Tag> const& in)
+template <typename Value, typename Parameters, typename Box, typename Tag>
+inline typename node<Value, Parameters, Box, Tag>::type *
+create_node(internal_node_variant<Value, Parameters, Box, Tag> const& in)
{
- typedef typename node<Value, Box, Tag>::type node;
+ typedef typename node<Value, Parameters, Box, Tag>::type node;
node * n = new node(in);
return n;
}
// default node
-template <typename Value, typename Box, typename Tag>
+template <typename Value, typename Parameters, typename Box, typename Tag>
inline void delete_node(boost::variant<
- leaf_variant<Value, Box, Tag>,
- internal_node_variant<Value, Box, Tag>
+ leaf_variant<Value, Parameters, Box, Tag>,
+ internal_node_variant<Value, Parameters, Box, Tag>
> * n)
{
delete n;
Modified: sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/options.hpp
==============================================================================
--- sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/options.hpp (original)
+++ sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/options.hpp 2011-06-16 17:15:06 EDT (Thu, 16 Jun 2011)
@@ -28,12 +28,51 @@
// NodeTag
struct default_tag {};
struct default_variant_tag {};
+struct default_static_tag {};
+
+template <size_t MaxElements, size_t MinElements>
+struct linear
+{
+ static const size_t max_elements = MaxElements;
+ static const size_t min_elements = MinElements;
+};
+
+template <size_t MaxElements, size_t MinElements>
+struct quadratic
+{
+ static const size_t max_elements = MaxElements;
+ static const size_t min_elements = MinElements;
+};
+
+namespace options { namespace detail {
+
+template <size_t MaxElements>
+struct default_rstar_reinserted_elements
+{
+ static const size_t value = MaxElements * 0.3f;
+};
+
+}} // namespace options::detail
+
+template <size_t MaxElements,
+ size_t MinElements,
+ size_t UseNearlyMinimumCost = false,
+ size_t ReinsertedElements = options::detail::default_rstar_reinserted_elements<MaxElements>::value
+ >
+struct rstar
+{
+ static const size_t max_elements = MaxElements;
+ static const size_t min_elements = MinElements;
+ static const size_t use_nearly_minimum_cost = UseNearlyMinimumCost;
+ static const size_t reinserted_elements = ReinsertedElements;
+};
namespace options {
-template <typename InsertTag, typename ChooseNextNodeTag, typename RedistributeTag, typename NodeTag>
+template <typename Parameters, typename InsertTag, typename ChooseNextNodeTag, typename RedistributeTag, typename NodeTag>
struct rtree
{
+ typedef Parameters parameters_type;
typedef InsertTag insert_tag;
typedef ChooseNextNodeTag choose_next_node_tag;
typedef RedistributeTag redistribute_tag;
@@ -50,28 +89,52 @@
typedef void type;
};
-template <typename InsertTag, typename ChooseNextNodeTag, typename RedistributeTag, typename NodeTag>
-struct options_type< options::rtree<InsertTag, ChooseNextNodeTag, RedistributeTag, NodeTag> >
-{
- typedef options::rtree<InsertTag, ChooseNextNodeTag, RedistributeTag, NodeTag> type;
-};
-
-template <>
-struct options_type<linear_tag>
-{
- typedef options::rtree<insert_tag, choose_by_area_diff_tag, linear_tag, default_tag> type;
-};
-
-template <>
-struct options_type<quadratic_tag>
-{
- typedef options::rtree<insert_tag, choose_by_area_diff_tag, quadratic_tag, default_tag> type;
-};
-
-template <>
-struct options_type<rstar_tag>
+template <typename Parameters, typename InsertTag, typename ChooseNextNodeTag, typename RedistributeTag, typename NodeTag>
+struct options_type< options::rtree<Parameters, InsertTag, ChooseNextNodeTag, RedistributeTag, NodeTag> >
{
- typedef options::rtree<reinsert_tag, choose_by_overlap_diff_tag, rstar_tag, default_tag> type;
+ typedef options::rtree<
+ Parameters,
+ InsertTag,
+ ChooseNextNodeTag,
+ RedistributeTag,
+ NodeTag
+ > type;
+};
+
+template <size_t MaxElements, size_t MinElements>
+struct options_type< linear<MaxElements, MinElements> >
+{
+ typedef options::rtree<
+ linear<MaxElements, MinElements>,
+ insert_tag,
+ choose_by_area_diff_tag,
+ linear_tag,
+ default_tag
+ > type;
+};
+
+template <size_t MaxElements, size_t MinElements>
+struct options_type< quadratic<MaxElements, MinElements> >
+{
+ typedef options::rtree<
+ quadratic<MaxElements, MinElements>,
+ insert_tag,
+ choose_by_area_diff_tag,
+ quadratic_tag,
+ default_tag
+ > type;
+};
+
+template <size_t MaxElements, size_t MinElements, bool UseNearlyMinimumCost, size_t ReinsertedElements>
+struct options_type< rstar<MaxElements, MinElements, UseNearlyMinimumCost, ReinsertedElements> >
+{
+ typedef options::rtree<
+ rstar<MaxElements, MinElements, UseNearlyMinimumCost, ReinsertedElements>,
+ reinsert_tag,
+ choose_by_overlap_diff_tag,
+ rstar_tag,
+ default_tag
+ > type;
};
}} // namespace detail::rtree
Modified: sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/quadratic/redistribute_elements.hpp
==============================================================================
--- sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/quadratic/redistribute_elements.hpp (original)
+++ sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/quadratic/redistribute_elements.hpp 2011-06-16 17:15:06 EDT (Thu, 16 Jun 2011)
@@ -78,9 +78,9 @@
template <typename Value, typename Options, typename Translator, typename Box>
struct redistribute_elements<Value, Options, Translator, Box, quadratic_tag>
{
- typedef typename rtree::node<Value, Box, typename Options::node_tag>::type node;
- typedef typename rtree::internal_node<Value, Box, typename Options::node_tag>::type internal_node;
- typedef typename rtree::leaf<Value, Box, typename Options::node_tag>::type leaf;
+ typedef typename rtree::node<Value, typename Options::parameters_type, Box, typename Options::node_tag>::type node;
+ typedef typename rtree::internal_node<Value, typename Options::parameters_type, Box, typename Options::node_tag>::type internal_node;
+ typedef typename rtree::leaf<Value, typename Options::parameters_type, Box, typename Options::node_tag>::type leaf;
typedef typename index::default_area_result<Box>::type area_type;
Modified: sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/rstar/choose_next_node.hpp
==============================================================================
--- sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/rstar/choose_next_node.hpp (original)
+++ sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/rstar/choose_next_node.hpp 2011-06-16 17:15:06 EDT (Thu, 16 Jun 2011)
@@ -30,12 +30,14 @@
template <typename Value, typename Options, typename Box>
class choose_next_node<Value, Options, Box, choose_by_overlap_diff_tag>
{
- typedef typename rtree::node<Value, Box, typename Options::node_tag>::type node;
- typedef typename rtree::internal_node<Value, Box, typename Options::node_tag>::type internal_node;
- typedef typename rtree::leaf<Value, Box, typename Options::node_tag>::type leaf;
+ typedef typename rtree::node<Value, typename Options::parameters_type, Box, typename Options::node_tag>::type node;
+ typedef typename rtree::internal_node<Value, typename Options::parameters_type, Box, typename Options::node_tag>::type internal_node;
+ typedef typename rtree::leaf<Value, typename Options::parameters_type, Box, typename Options::node_tag>::type leaf;
typedef typename rtree::elements_type<internal_node>::type children_type;
+ typedef typename Options::parameters_type parameters_type;
+
typedef typename index::default_area_result<Box>::type area_type;
typedef typename index::default_overlap_result<Box>::type overlap_type;
@@ -47,7 +49,12 @@
// children are leafs
if ( node_relative_level <= 1 )
- return choose_by_minimum_overlap_cost(children, indexable);
+ {
+ if ( parameters_type::use_nearly_minimum_cost )
+ return choose_by_nearly_minimum_overlap_cost(children, indexable);
+ else
+ return choose_by_minimum_overlap_cost(children, indexable);
+ }
// children are internal nodes
else
return choose_by_minimum_area_cost(children, indexable);
@@ -111,6 +118,14 @@
return choosen_index;
}
+ template <typename Indexable>
+ static inline size_t choose_by_nearly_minimum_overlap_cost(children_type const& children, Indexable const& indexable)
+ {
+ // TODO - awulkiew: implement this function
+
+ return choose_by_minimum_overlap_cost(children, indexable);
+ }
+
template <typename Indexable>
static inline size_t choose_by_minimum_area_cost(children_type const& children, Indexable const& indexable)
{
Modified: sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/rstar/insert.hpp
==============================================================================
--- sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/rstar/insert.hpp (original)
+++ sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/rstar/insert.hpp 2011-06-16 17:15:06 EDT (Thu, 16 Jun 2011)
@@ -27,17 +27,17 @@
class remove_elements_to_reinsert
{
public:
- typedef typename rtree::node<Value, Box, typename Options::node_tag>::type node;
- typedef typename rtree::internal_node<Value, Box, typename Options::node_tag>::type internal_node;
- typedef typename rtree::leaf<Value, Box, typename Options::node_tag>::type leaf;
+ typedef typename rtree::node<Value, typename Options::parameters_type, Box, typename Options::node_tag>::type node;
+ typedef typename rtree::internal_node<Value, typename Options::parameters_type, Box, typename Options::node_tag>::type internal_node;
+ typedef typename rtree::leaf<Value, typename Options::parameters_type, Box, typename Options::node_tag>::type leaf;
+
+ typedef typename Options::parameters_type parameters_type;
template <typename Node>
static inline void apply(typename rtree::elements_type<Node>::type & result_elements,
Node & n,
internal_node *parent,
size_t current_child_index,
- size_t min_elems,
- size_t max_elems,
Translator const& tr)
{
typedef typename rtree::elements_type<Node>::type elements_type;
@@ -46,21 +46,22 @@
// TODO: awulkiew - change second point_type to the point type of the Indexable?
typedef typename index::default_distance_sqr_result<point_type, point_type>::type distance_sqr_type;
- BOOST_GEOMETRY_INDEX_ASSERT(parent, "node shouldn't be the root node");
+ elements_type & elements = rtree::elements(n);
- const size_t reinserted_elements_count = static_cast<size_t>(max_elems * 0.3f);
- assert(0 < reinserted_elements_count);
- BOOST_GEOMETRY_INDEX_ASSERT(0 < reinserted_elements_count, "wrong value of elements to reinsert");
+ const size_t elements_count = parameters_type::max_elements + 1;
+ const size_t reinserted_elements_count = parameters_type::reinserted_elements;
+
+ BOOST_GEOMETRY_INDEX_ASSERT(parent, "node shouldn't be the root node");
+ BOOST_GEOMETRY_INDEX_ASSERT(elements.size() == elements_count, "unexpected elements number");
+ BOOST_GEOMETRY_INDEX_ASSERT(0 < reinserted_elements_count, "wrong value of elements to reinsert");
// calculate current node's center
point_type node_center;
geometry::centroid(rtree::elements(*parent)[current_child_index].first, node_center);
// fill the container of centers' distances of children from current node's center
- elements_type & elements = rtree::elements(n);
- size_t elements_count = elements.size();
- std::vector< std::pair<distance_sqr_type, element_type> > sorted_elements(elements_count);
- for ( size_t i = 0 ; i < elements_count ; ++i )
+ boost::array<std::pair<distance_sqr_type, element_type>, elements_count> sorted_elements;
+ for ( size_t i = 0 ; i < elements_count ; ++i )
{
point_type element_center;
geometry::centroid( rtree::element_indexable(elements[i], tr),
@@ -109,7 +110,7 @@
struct level_insert_elements_type
{
typedef typename rtree::elements_type<
- typename rtree::internal_node<Value, Box, typename Options::node_tag>::type
+ typename rtree::internal_node<Value, typename Options::parameters_type, Box, typename Options::node_tag>::type
>::type type;
};
@@ -117,7 +118,7 @@
struct level_insert_elements_type<0, Value, Value, Options, Box>
{
typedef typename rtree::elements_type<
- typename rtree::leaf<Value, Box, typename Options::node_tag>::type
+ typename rtree::leaf<Value, typename Options::parameters_type, Box, typename Options::node_tag>::type
>::type type;
};
@@ -131,15 +132,14 @@
typedef typename base::leaf leaf;
typedef typename level_insert_elements_type<InsertIndex, Element, Value, Options, Box>::type elements_type;
+ typedef typename Options::parameters_type parameters_type;
inline level_insert_base(node* & root,
size_t & leafs_level,
Element const& element,
- size_t min_elements,
- size_t max_elements,
Translator const& tr,
size_t relative_level)
- : base(root, leafs_level, element, min_elements, max_elements, tr, relative_level)
+ : base(root, leafs_level, element, tr, relative_level)
, result_relative_level(0)
{}
@@ -151,7 +151,7 @@
result_relative_level = base::m_leafs_level - base::m_current_level;
// overflow
- if ( base::m_max_elems_per_node < rtree::elements(n).size() )
+ if ( parameters_type::max_elements < rtree::elements(n).size() )
{
// node isn't root node
if ( base::m_parent )
@@ -159,7 +159,7 @@
rstar::remove_elements_to_reinsert<Value, Options, Translator, Box>::apply(
result_elements, n,
base::m_parent, base::m_current_child_index,
- base::m_min_elems_per_node, base::m_max_elems_per_node, base::m_tr);
+ base::m_tr);
}
// node is root node
else
@@ -174,7 +174,7 @@
inline void handle_possible_split(Node &n) const
{
// overflow
- if ( base::m_max_elems_per_node < rtree::elements(n).size() )
+ if ( parameters_type::max_elements < rtree::elements(n).size() )
{
base::split(n);
}
@@ -207,11 +207,9 @@
inline level_insert(node* & root,
size_t & leafs_level,
Element const& element,
- size_t min_elements,
- size_t max_elements,
Translator const& tr,
size_t relative_level)
- : base(root, leafs_level, element, min_elements, max_elements, tr, relative_level)
+ : base(root, leafs_level, element, tr, relative_level)
{}
inline void operator()(internal_node & n)
@@ -274,11 +272,9 @@
inline level_insert(node* & root,
size_t & leafs_level,
Value const& v,
- size_t min_elements,
- size_t max_elements,
Translator const& t,
size_t relative_level)
- : base(root, leafs_level, v, min_elements, max_elements, t, relative_level)
+ : base(root, leafs_level, v, t, relative_level)
{}
inline void operator()(internal_node & n)
@@ -322,11 +318,9 @@
inline level_insert(node* & root,
size_t & leafs_level,
Value const& v,
- size_t min_elements,
- size_t max_elements,
Translator const& t,
size_t relative_level)
- : base(root, leafs_level, v, min_elements, max_elements, t, relative_level)
+ : base(root, leafs_level, v, t, relative_level)
{}
inline void operator()(internal_node & n)
@@ -360,23 +354,20 @@
// R*-tree insert visitor
template <typename Element, typename Value, typename Options, typename Translator, typename Box>
class insert<Element, Value, Options, Translator, Box, reinsert_tag>
- : public rtree::visitor<Value, Box, typename Options::node_tag, false>::type
+ : public rtree::visitor<Value, typename Options::parameters_type, Box, typename Options::node_tag, false>::type
{
private:
- typedef typename rtree::node<Value, Box, typename Options::node_tag>::type node;
- typedef typename rtree::internal_node<Value, Box, typename Options::node_tag>::type internal_node;
- typedef typename rtree::leaf<Value, Box, typename Options::node_tag>::type leaf;
+ typedef typename rtree::node<Value, typename Options::parameters_type, Box, typename Options::node_tag>::type node;
+ typedef typename rtree::internal_node<Value, typename Options::parameters_type, Box, typename Options::node_tag>::type internal_node;
+ typedef typename rtree::leaf<Value, typename Options::parameters_type, Box, typename Options::node_tag>::type leaf;
public:
inline insert(node* & root,
size_t & leafs_level,
Element const& element,
- size_t min_elements,
- size_t max_elements,
Translator const& tr,
size_t relative_level = 0)
: m_root(root), m_leafs_level(leafs_level), m_element(element)
- , m_min_elements(min_elements), m_max_elements(max_elements)
, m_tr(tr), m_relative_level(relative_level)
{}
@@ -385,7 +376,7 @@
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> lins_v(
- m_root, m_leafs_level, m_element, m_min_elements, m_max_elements, m_tr, m_relative_level);
+ m_root, m_leafs_level, m_element, m_tr, m_relative_level);
rtree::apply_visitor(lins_v, *m_root);
@@ -400,7 +391,7 @@
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> lins_v(
- m_root, m_leafs_level, m_element, m_min_elements, m_max_elements, m_tr, m_relative_level);
+ m_root, m_leafs_level, m_element, m_tr, m_relative_level);
rtree::apply_visitor(lins_v, *m_root);
@@ -419,7 +410,7 @@
it != elements.rend(); ++it)
{
detail::rstar::level_insert<1, element_type, Value, Options, Translator, Box> lins_v(
- m_root, m_leafs_level, *it, m_min_elements, m_max_elements, m_tr, relative_level);
+ m_root, m_leafs_level, *it, m_tr, relative_level);
rtree::apply_visitor(lins_v, *m_root);
@@ -436,8 +427,6 @@
node* & m_root;
size_t & m_leafs_level;
Element const& m_element;
- size_t m_min_elements;
- size_t m_max_elements;
Translator const& m_tr;
size_t m_relative_level;
};
Modified: sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/rstar/redistribute_elements.hpp
==============================================================================
--- sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/rstar/redistribute_elements.hpp (original)
+++ sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/rstar/redistribute_elements.hpp 2011-06-16 17:15:06 EDT (Thu, 16 Jun 2011)
@@ -48,7 +48,7 @@
Translator const& m_tr;
};
-template <typename Box, size_t Corner, size_t AxisIndex>
+template <typename Parameters, typename Box, size_t Corner, size_t AxisIndex>
struct choose_split_axis_and_index_for_corner
{
typedef typename index::default_margin_result<Box>::type margin_type;
@@ -60,30 +60,29 @@
margin_type & sum_of_margins,
area_type & smallest_overlap,
area_type & smallest_area,
- size_t min_elems,
- size_t max_elems,
Translator const& tr)
{
typedef typename Elements::value_type element_type;
-
+
+ BOOST_GEOMETRY_INDEX_ASSERT(elements.size() == Parameters::max_elements + 1, "wrong number of elements");
+
// copy elements
- Elements elements_copy = elements;
+ boost::array<element_type, Parameters::max_elements + 1> elements_copy;
+ std::copy(elements.begin(), elements.end(), elements_copy.begin());
- BOOST_GEOMETRY_INDEX_ASSERT(elements_copy.size() == max_elems + 1, "wrong number of elements");
-
// sort elements
element_axis_corner_less<element_type, Translator, Corner, AxisIndex> elements_less(tr);
std::sort(elements_copy.begin(), elements_copy.end(), elements_less);
// init outputs
- choosen_index = min_elems;
+ choosen_index = Parameters::min_elements;
sum_of_margins = 0;
smallest_overlap = std::numeric_limits<area_type>::max();
smallest_area = std::numeric_limits<area_type>::max();
// calculate sum of margins for all distributions
- size_t index_last = max_elems - min_elems + 2;
- for ( size_t i = min_elems ; i < index_last ; ++i )
+ size_t index_last = Parameters::max_elements - Parameters::min_elements + 2;
+ for ( size_t i = Parameters::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
@@ -106,14 +105,14 @@
}
};
-template <typename Box, size_t AxisIndex, typename ElementIndexableTag>
+template <typename Parameters, typename Box, size_t AxisIndex, typename ElementIndexableTag>
struct choose_split_axis_and_index_for_axis
{
//BOOST_STATIC_ASSERT(0);
};
-template <typename Box, size_t AxisIndex>
-struct choose_split_axis_and_index_for_axis<Box, AxisIndex, box_tag>
+template <typename Parameters, typename Box, size_t AxisIndex>
+struct choose_split_axis_and_index_for_axis<Parameters, Box, AxisIndex, box_tag>
{
typedef typename index::default_margin_result<Box>::type margin_type;
typedef typename index::default_area_result<Box>::type area_type;
@@ -125,8 +124,6 @@
margin_type & sum_of_margins,
area_type & smallest_overlap,
area_type & smallest_area,
- size_t min_elems,
- size_t max_elems,
Translator const& tr)
{
size_t index1 = 0;
@@ -134,20 +131,20 @@
area_type ovl1 = std::numeric_limits<area_type>::max();
area_type ar1 = std::numeric_limits<area_type>::max();
- choose_split_axis_and_index_for_corner<Box, min_corner, AxisIndex>::
+ choose_split_axis_and_index_for_corner<Parameters, Box, min_corner, AxisIndex>::
apply(elements, index1,
som1, ovl1, ar1,
- min_elems, max_elems, tr);
+ tr);
size_t index2 = 0;
margin_type som2 = 0;
area_type ovl2 = std::numeric_limits<area_type>::max();
area_type ar2 = std::numeric_limits<area_type>::max();
- choose_split_axis_and_index_for_corner<Box, max_corner, AxisIndex>::
+ choose_split_axis_and_index_for_corner<Parameters, Box, max_corner, AxisIndex>::
apply(elements, index2,
som2, ovl2, ar2,
- min_elems, max_elems, tr);
+ tr);
sum_of_margins = som1 + som2;
@@ -168,8 +165,8 @@
}
};
-template <typename Box, size_t AxisIndex>
-struct choose_split_axis_and_index_for_axis<Box, AxisIndex, point_tag>
+template <typename Parameters, typename Box, size_t AxisIndex>
+struct choose_split_axis_and_index_for_axis<Parameters, Box, AxisIndex, point_tag>
{
typedef typename index::default_margin_result<Box>::type margin_type;
typedef typename index::default_area_result<Box>::type area_type;
@@ -181,20 +178,18 @@
margin_type & sum_of_margins,
area_type & smallest_overlap,
area_type & smallest_area,
- size_t min_elems,
- size_t max_elems,
Translator const& tr)
{
- choose_split_axis_and_index_for_corner<Box, min_corner, AxisIndex>::
+ choose_split_axis_and_index_for_corner<Parameters, Box, min_corner, AxisIndex>::
apply(elements, choosen_index,
sum_of_margins, smallest_overlap, smallest_area,
- min_elems, max_elems, tr);
+ tr);
choosen_corner = min_corner;
}
};
-template <typename Box, size_t Dimension>
+template <typename Parameters, typename Box, size_t Dimension>
struct choose_split_axis_and_index
{
BOOST_STATIC_ASSERT(0 < Dimension);
@@ -210,15 +205,15 @@
margin_type & smallest_sum_of_margins,
area_type & smallest_overlap,
area_type & smallest_area,
- size_t min_elems,
- size_t max_elems,
Translator const& tr)
{
typedef typename rtree::element_indexable_type<typename Elements::value_type, Translator>::type element_indexable_type;
- choose_split_axis_and_index<Box, Dimension - 1>::apply(elements, choosen_axis, choosen_corner, choosen_index,
- smallest_sum_of_margins, smallest_overlap, smallest_area,
- min_elems, max_elems, tr);
+ choose_split_axis_and_index<Parameters, Box, Dimension - 1>::
+ apply(elements, choosen_axis, choosen_corner, choosen_index,
+ smallest_sum_of_margins, smallest_overlap, smallest_area,
+ tr);
+
margin_type sum_of_margins = 0;
size_t corner = min_corner;
@@ -228,10 +223,11 @@
area_type area_val = std::numeric_limits<area_type>::max();
choose_split_axis_and_index_for_axis<
+ Parameters,
Box,
Dimension - 1,
typename index::traits::tag<element_indexable_type>::type
- >::apply(elements, corner, index, sum_of_margins, overlap_val, area_val, min_elems, max_elems, tr);
+ >::apply(elements, corner, index, sum_of_margins, overlap_val, area_val, tr);
if ( sum_of_margins < smallest_sum_of_margins )
{
@@ -245,8 +241,8 @@
}
};
-template <typename Box>
-struct choose_split_axis_and_index<Box, 1>
+template <typename Parameters, typename Box>
+struct choose_split_axis_and_index<Parameters, Box, 1>
{
typedef typename index::default_margin_result<Box>::type margin_type;
typedef typename index::default_area_result<Box>::type area_type;
@@ -259,8 +255,6 @@
margin_type & smallest_sum_of_margins,
area_type & smallest_overlap,
area_type & smallest_area,
- size_t min_elems,
- size_t max_elems,
Translator const& tr)
{
typedef typename rtree::element_indexable_type<typename Elements::value_type, Translator>::type element_indexable_type;
@@ -268,10 +262,11 @@
choosen_axis = 0;
choose_split_axis_and_index_for_axis<
+ Parameters,
Box,
0,
typename index::traits::tag<element_indexable_type>::type
- >::apply(elements, choosen_corner, choosen_index, smallest_sum_of_margins, smallest_overlap, smallest_area, min_elems, max_elems, tr);
+ >::apply(elements, choosen_corner, choosen_index, smallest_sum_of_margins, smallest_overlap, smallest_area, tr);
}
};
@@ -317,9 +312,11 @@
template <typename Value, typename Options, typename Translator, typename Box>
struct redistribute_elements<Value, Options, Translator, Box, rstar_tag>
{
- typedef typename rtree::node<Value, Box, typename Options::node_tag>::type node;
- typedef typename rtree::internal_node<Value, Box, typename Options::node_tag>::type internal_node;
- typedef typename rtree::leaf<Value, Box, typename Options::node_tag>::type leaf;
+ typedef typename rtree::node<Value, typename Options::parameters_type, Box, typename Options::node_tag>::type node;
+ typedef typename rtree::internal_node<Value, typename Options::parameters_type, Box, typename Options::node_tag>::type internal_node;
+ typedef typename rtree::leaf<Value, typename Options::parameters_type, Box, typename Options::node_tag>::type leaf;
+
+ typedef typename Options::parameters_type parameters_type;
static const size_t dimension = index::traits::dimension<Box>::value;
@@ -332,8 +329,6 @@
Node & second_node,
Box & box1,
Box & box2,
- size_t min_elems,
- size_t max_elems,
Translator const& tr)
{
typedef typename rtree::elements_type<Node>::type elements_type;
@@ -343,22 +338,22 @@
size_t split_axis = 0;
size_t split_corner = 0;
- size_t split_index = min_elems;
+ size_t split_index = parameters_type::min_elements;
margin_type smallest_sum_of_margins = std::numeric_limits<margin_type>::max();
area_type smallest_overlap = std::numeric_limits<area_type>::max();
area_type smallest_area = std::numeric_limits<area_type>::max();
- rstar::choose_split_axis_and_index<Box, index::traits::dimension<Box>::value>::
+ 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_area,
- min_elems, max_elems, tr);
+ smallest_sum_of_margins, smallest_overlap, smallest_area,
+ tr);
// 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_corner == static_cast<size_t>(min_corner) || split_corner == static_cast<size_t>(max_corner), "unexpected value");
- BOOST_GEOMETRY_INDEX_ASSERT(min_elems <= split_index && split_index <= max_elems - min_elems + 1, "unexpected value");
+ BOOST_GEOMETRY_INDEX_ASSERT(parameters_type::min_elements <= split_index && split_index <= parameters_type::max_elements - parameters_type::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) )
@@ -367,7 +362,7 @@
rstar::partial_sort<max_corner, dimension>::apply(elements1, split_axis, split_index, tr);
// copy elements to node 2 and remove from node 1
- elements2.resize(max_elems + 1 - split_index);
+ elements2.resize(parameters_type::max_elements + 1 - split_index);
std::copy(elements1.begin() + split_index, elements1.end(), elements2.begin());
elements1.resize(split_index);
Modified: sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/rtree.hpp
==============================================================================
--- sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/rtree.hpp (original)
+++ sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/rtree.hpp 2011-06-16 17:15:06 EDT (Thu, 16 Jun 2011)
@@ -38,7 +38,7 @@
template <
typename Value,
- typename Options = linear_tag,
+ typename Options,
typename Translator = translator::def<Value>
>
class rtree
@@ -52,9 +52,9 @@
typedef typename detail::rtree::options_type<Options>::type options_type;
typedef typename options_type::node_tag node_tag;
- typedef typename detail::rtree::node<value_type, box_type, node_tag>::type node;
- typedef typename detail::rtree::internal_node<value_type, box_type, node_tag>::type internal_node;
- typedef typename detail::rtree::leaf<value_type, box_type, node_tag>::type leaf;
+ typedef typename detail::rtree::node<value_type, typename options_type::parameters_type, box_type, node_tag>::type node;
+ typedef typename detail::rtree::internal_node<value_type, typename options_type::parameters_type, box_type, node_tag>::type internal_node;
+ typedef typename detail::rtree::leaf<value_type, typename options_type::parameters_type, box_type, node_tag>::type leaf;
inline explicit rtree(
size_t max_elems_per_node = 4,
@@ -98,7 +98,7 @@
// TODO: awulkiew - assert for correct value
detail::rtree::visitors::insert<value_type, value_type, options_type, translator_type, box_type, typename options_type::insert_tag>
- insert_v(m_root, m_leafs_level, value, m_min_elems_per_node, m_max_elems_per_node, m_translator);
+ insert_v(m_root, m_leafs_level, value, m_translator);
detail::rtree::apply_visitor(insert_v, *m_root);
@@ -112,7 +112,7 @@
BOOST_GEOMETRY_INDEX_ASSERT(0 < m_values_count, "can't remove, there is no elements in the rtree");
detail::rtree::visitors::remove<value_type, options_type, translator_type, box_type>
- remove_v(m_root, m_leafs_level, value, m_min_elems_per_node, m_max_elems_per_node, m_translator);
+ remove_v(m_root, m_leafs_level, value, m_translator);
detail::rtree::apply_visitor(remove_v, *m_root);
Modified: sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/are_boxes_ok.hpp
==============================================================================
--- sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/are_boxes_ok.hpp (original)
+++ sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/are_boxes_ok.hpp 2011-06-16 17:15:06 EDT (Thu, 16 Jun 2011)
@@ -18,10 +18,10 @@
namespace detail { namespace rtree { namespace visitors {
template <typename Value, typename Options, typename Translator, typename Box>
-class are_boxes_ok : public rtree::visitor<Value, Box, typename Options::node_tag, true>::type
+class are_boxes_ok : public rtree::visitor<Value, typename Options::parameters_type, Box, typename Options::node_tag, true>::type
{
- typedef typename rtree::internal_node<Value, Box, typename Options::node_tag>::type internal_node;
- typedef typename rtree::leaf<Value, Box, typename Options::node_tag>::type leaf;
+ typedef typename rtree::internal_node<Value, typename Options::parameters_type, Box, typename Options::node_tag>::type internal_node;
+ typedef typename rtree::leaf<Value, typename Options::parameters_type, Box, typename Options::node_tag>::type leaf;
public:
inline are_boxes_ok(Translator const& tr)
Modified: sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/are_levels_ok.hpp
==============================================================================
--- sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/are_levels_ok.hpp (original)
+++ sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/are_levels_ok.hpp 2011-06-16 17:15:06 EDT (Thu, 16 Jun 2011)
@@ -17,10 +17,10 @@
namespace detail { namespace rtree { namespace visitors {
template <typename Value, typename Options, typename Translator, typename Box>
-class are_levels_ok : public rtree::visitor<Value, Box, typename Options::node_tag, true>::type
+class are_levels_ok : public rtree::visitor<Value, typename Options::parameters_type, Box, typename Options::node_tag, true>::type
{
- typedef typename rtree::internal_node<Value, Box, typename Options::node_tag>::type internal_node;
- typedef typename rtree::leaf<Value, Box, typename Options::node_tag>::type leaf;
+ typedef typename rtree::internal_node<Value, typename Options::parameters_type, Box, typename Options::node_tag>::type internal_node;
+ typedef typename rtree::leaf<Value, typename Options::parameters_type, Box, typename Options::node_tag>::type leaf;
public:
inline are_levels_ok(Translator const& tr)
Modified: sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/destroy.hpp
==============================================================================
--- sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/destroy.hpp (original)
+++ sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/destroy.hpp 2011-06-16 17:15:06 EDT (Thu, 16 Jun 2011)
@@ -17,10 +17,10 @@
namespace detail { namespace rtree { namespace visitors {
template <typename Value, typename Options, typename Translator, typename Box>
-struct destroy : public rtree::visitor<Value, Box, typename Options::node_tag, false>::type
+struct destroy : public rtree::visitor<Value, typename Options::parameters_type, Box, typename Options::node_tag, false>::type
{
- typedef typename rtree::internal_node<Value, Box, typename Options::node_tag>::type internal_node;
- typedef typename rtree::leaf<Value, Box, typename Options::node_tag>::type leaf;
+ typedef typename rtree::internal_node<Value, typename Options::parameters_type, Box, typename Options::node_tag>::type internal_node;
+ typedef typename rtree::leaf<Value, typename Options::parameters_type, Box, typename Options::node_tag>::type leaf;
inline void operator()(internal_node & n)
{
Modified: sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/find.hpp
==============================================================================
--- sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/find.hpp (original)
+++ sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/find.hpp 2011-06-16 17:15:06 EDT (Thu, 16 Jun 2011)
@@ -143,11 +143,11 @@
// rtree spatial query visitor
template <typename Value, typename Options, typename Translator, typename Box, typename Geometry, typename OutIter>
-struct find : public rtree::visitor<Value, Box, typename Options::node_tag, true>::type
+struct find : public rtree::visitor<Value, typename Options::parameters_type, Box, typename Options::node_tag, true>::type
{
- typedef typename rtree::node<Value, Box, typename Options::node_tag>::type node;
- typedef typename rtree::internal_node<Value, Box, typename Options::node_tag>::type internal_node;
- typedef typename rtree::leaf<Value, Box, typename Options::node_tag>::type leaf;
+ typedef typename rtree::node<Value, typename Options::parameters_type, Box, typename Options::node_tag>::type node;
+ typedef typename rtree::internal_node<Value, typename Options::parameters_type, Box, typename Options::node_tag>::type internal_node;
+ typedef typename rtree::leaf<Value, typename Options::parameters_type, Box, typename Options::node_tag>::type leaf;
inline find(Translator const& t, Geometry const& g, OutIter out_it)
: tr(t), geom(g), out_iter(out_it)
Modified: sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/insert.hpp
==============================================================================
--- sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/insert.hpp (original)
+++ sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/insert.hpp 2011-06-16 17:15:06 EDT (Thu, 16 Jun 2011)
@@ -27,9 +27,9 @@
template <typename Value, typename Options, typename Box>
struct choose_next_node<Value, Options, Box, choose_by_area_diff_tag>
{
- typedef typename rtree::node<Value, Box, typename Options::node_tag>::type node;
- typedef typename rtree::internal_node<Value, Box, typename Options::node_tag>::type internal_node;
- typedef typename rtree::leaf<Value, Box, typename Options::node_tag>::type leaf;
+ typedef typename rtree::node<Value, typename Options::parameters_type, Box, typename Options::node_tag>::type node;
+ typedef typename rtree::internal_node<Value, typename Options::parameters_type, Box, typename Options::node_tag>::type internal_node;
+ typedef typename rtree::leaf<Value, typename Options::parameters_type, Box, typename Options::node_tag>::type leaf;
typedef typename rtree::elements_type<internal_node>::type children_type;
@@ -83,25 +83,23 @@
// Default insert visitor
template <typename Element, typename Value, typename Options, typename Translator, typename Box>
-class insert : public rtree::visitor<Value, Box, typename Options::node_tag, false>::type
+class insert : public rtree::visitor<Value, typename Options::parameters_type, Box, typename Options::node_tag, false>::type
{
protected:
- typedef typename rtree::node<Value, Box, typename Options::node_tag>::type node;
- typedef typename rtree::internal_node<Value, Box, typename Options::node_tag>::type internal_node;
- typedef typename rtree::leaf<Value, Box, typename Options::node_tag>::type leaf;
+ typedef typename rtree::node<Value, typename Options::parameters_type, Box, typename Options::node_tag>::type node;
+ typedef typename rtree::internal_node<Value, typename Options::parameters_type, Box, typename Options::node_tag>::type internal_node;
+ typedef typename rtree::leaf<Value, typename Options::parameters_type, Box, typename Options::node_tag>::type leaf;
+
+ typedef typename Options::parameters_type parameters_type;
inline insert(node* & root,
size_t & leafs_level,
Element const& element,
- size_t min_elements,
- size_t max_elements,
Translator const& t,
size_t relative_level = 0
)
: m_element(element)
, m_tr(t)
- , m_min_elems_per_node(min_elements)
- , m_max_elems_per_node(max_elements)
, m_relative_level(relative_level)
, m_level(leafs_level - relative_level)
, m_root_node(root)
@@ -141,7 +139,7 @@
"if node isn't the root current_child_index should be valid");
// handle overflow
- if ( m_max_elems_per_node < rtree::elements(n).size() )
+ if ( parameters_type::max_elements < rtree::elements(n).size() )
{
split(n);
}
@@ -179,12 +177,14 @@
// redistribute elements
Box box1, box2;
redistribute_elements<Value, Options, Translator, Box, typename Options::redistribute_tag>::
- apply(n, n2, box1, box2, m_min_elems_per_node, m_max_elems_per_node, m_tr);
+ apply(n, n2, box1, box2, m_tr);
// check numbers of elements
- BOOST_GEOMETRY_INDEX_ASSERT(m_min_elems_per_node <= rtree::elements(n).size() && rtree::elements(n).size() <= m_max_elems_per_node,
+ BOOST_GEOMETRY_INDEX_ASSERT(parameters_type::min_elements <= rtree::elements(n).size() &&
+ rtree::elements(n).size() <= parameters_type::max_elements,
"unexpected number of elements");
- BOOST_GEOMETRY_INDEX_ASSERT(m_min_elems_per_node <= rtree::elements(n2).size() && rtree::elements(n2).size() <= m_max_elems_per_node,
+ BOOST_GEOMETRY_INDEX_ASSERT(parameters_type::min_elements <= rtree::elements(n2).size() &&
+ rtree::elements(n2).size() <= parameters_type::max_elements,
"unexpected number of elements");
// node is not the root - just add the new node
@@ -213,8 +213,6 @@
Element const& m_element;
Translator const& m_tr;
- const size_t m_min_elems_per_node;
- const size_t m_max_elems_per_node;
const size_t m_relative_level;
const size_t m_level;
@@ -246,12 +244,10 @@
inline insert(node* & root,
size_t & leafs_level,
Element const& element,
- size_t min_elements,
- size_t max_elements,
Translator const& tr,
size_t relative_level = 0
)
- : base(root, leafs_level, element, min_elements, max_elements, tr, relative_level)
+ : base(root, leafs_level, element, tr, relative_level)
{}
inline void operator()(internal_node & n)
@@ -293,12 +289,10 @@
inline insert(node* & root,
size_t & leafs_level,
Value const& v,
- size_t min_elements,
- size_t max_elements,
Translator const& t,
size_t relative_level = 0
)
- : base(root, leafs_level, v, min_elements, max_elements, t, relative_level)
+ : base(root, leafs_level, v, t, relative_level)
{}
inline void operator()(internal_node & n)
Modified: sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/is_leaf.hpp
==============================================================================
--- sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/is_leaf.hpp (original)
+++ sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/is_leaf.hpp 2011-06-16 17:15:06 EDT (Thu, 16 Jun 2011)
@@ -17,10 +17,10 @@
namespace detail { namespace rtree { namespace visitors {
template <typename Value, typename Options, typename Box>
-struct is_leaf : public rtree::visitor<Value, Box, typename Options::node_tag, true>::type
+struct is_leaf : public rtree::visitor<Value, typename Options::parameters_type, Box, typename Options::node_tag, true>::type
{
- typedef typename rtree::internal_node<Value, Box, typename Options::node_tag>::type internal_node;
- typedef typename rtree::leaf<Value, Box, typename Options::node_tag>::type leaf;
+ typedef typename rtree::internal_node<Value, typename Options::parameters_type, Box, typename Options::node_tag>::type internal_node;
+ typedef typename rtree::leaf<Value, typename Options::parameters_type, Box, typename Options::node_tag>::type leaf;
inline void operator()(internal_node const&)
{
Modified: sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/remove.hpp
==============================================================================
--- sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/remove.hpp (original)
+++ sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/remove.hpp 2011-06-16 17:15:06 EDT (Thu, 16 Jun 2011)
@@ -22,23 +22,21 @@
// Default remove algorithm
template <typename Value, typename Options, typename Translator, typename Box>
-class remove : public rtree::visitor<Value, Box, typename Options::node_tag, false>::type
+class remove : public rtree::visitor<Value, typename Options::parameters_type, Box, typename Options::node_tag, false>::type
{
- typedef typename rtree::node<Value, Box, typename Options::node_tag>::type node;
- typedef typename rtree::internal_node<Value, Box, typename Options::node_tag>::type internal_node;
- typedef typename rtree::leaf<Value, Box, typename Options::node_tag>::type leaf;
+ typedef typename rtree::node<Value, typename Options::parameters_type, Box, typename Options::node_tag>::type node;
+ typedef typename rtree::internal_node<Value, typename Options::parameters_type, Box, typename Options::node_tag>::type internal_node;
+ typedef typename rtree::leaf<Value, typename Options::parameters_type, Box, typename Options::node_tag>::type leaf;
+
+ typedef typename Options::parameters_type parameters_type;
public:
inline remove(node* & root,
size_t & leafs_level,
Value const& v,
- size_t min_elements,
- size_t max_elements,
Translator const& t)
: m_value(v)
, m_tr(t)
- , m_min_elems_per_node(min_elements)
- , m_max_elems_per_node(max_elements)
, m_root_node(root)
, m_leafs_level(leafs_level)
, m_is_value_removed(false)
@@ -87,7 +85,7 @@
elements.erase(underfl_el_it);
// calc underflow
- m_is_underflow = elements.size() < m_min_elems_per_node;
+ m_is_underflow = elements.size() < parameters_type::min_elements;
}
// n is not root - adjust aabb
@@ -96,7 +94,7 @@
// 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
- assert((elements.size() < m_min_elems_per_node) == m_is_underflow);
+ assert((elements.size() < parameters_type::min_elements) == m_is_underflow);
rtree::elements(*m_parent)[m_current_child_index].first
= rtree::elements_box<Box>(elements.begin(), elements.end(), m_tr);
@@ -105,9 +103,7 @@
else
{
BOOST_GEOMETRY_INDEX_ASSERT(&n == rtree::get<internal_node>(m_root_node), "node must be the root");
-
- // value not found
- assert(m_is_value_removed);
+ BOOST_GEOMETRY_INDEX_ASSERT(m_is_value_removed, "value not found");
// reinsert elements from removed nodes
// begin with levels closer to the root
@@ -152,7 +148,7 @@
if ( m_is_value_removed )
{
// calc underflow
- m_is_underflow = elements.size() < m_min_elems_per_node;
+ m_is_underflow = elements.size() < parameters_type::min_elements;
// n is not root - adjust aabb
if ( 0 != m_parent )
@@ -196,8 +192,6 @@
m_root_node,
m_leafs_level,
*it,
- m_min_elems_per_node,
- m_max_elems_per_node,
m_tr,
node_relative_level - 1);
@@ -207,8 +201,6 @@
Value const& m_value;
Translator const& m_tr;
- const size_t m_min_elems_per_node;
- const size_t m_max_elems_per_node;
node* & m_root_node;
size_t & m_leafs_level;
Modified: sandbox-branches/geometry/index/tests/additional_sizes_and_times.cpp
==============================================================================
--- sandbox-branches/geometry/index/tests/additional_sizes_and_times.cpp (original)
+++ sandbox-branches/geometry/index/tests/additional_sizes_and_times.cpp 2011-06-16 17:15:06 EDT (Thu, 16 Jun 2011)
@@ -28,13 +28,13 @@
typedef bg::model::point<float, 2, bg::cs::cartesian> P;
typedef bg::model::box<P> B;
- //typedef bgi::rtree<std::pair<B, size_t>, bgi::linear_tag> RT;
- //typedef bgi::rtree<std::pair<B, size_t>, bgi::quadratic_tag> RT;
- //typedef bgi::rtree<std::pair<B, size_t>, bgi::rstar_tag> RT;
- typedef bgi::rtree<
+ //typedef bgi::rtree<std::pair<B, size_t>, bgi::linear<32, 8> > RT;
+ //typedef bgi::rtree<std::pair<B, size_t>, bgi::quadratic<32, 8> > RT;
+ typedef bgi::rtree<std::pair<B, size_t>, bgi::rstar<32, 8, true> > RT;
+ /*typedef bgi::rtree<
std::pair<B, size_t>,
- bgi::options::rtree<bgi::insert_tag, bgi::choose_by_area_diff_tag, bgi::rstar_tag, bgi::default_tag>
- > RT;
+ bgi::options::rtree<bgi::linear<32, 8>, bgi::insert_tag, bgi::choose_by_area_diff_tag, bgi::linear_tag, bgi::default_static_tag>
+ > RT;*/
// load config file
std::ifstream file_cfg("config.txt");
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