|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r70964 - in sandbox-branches/geometry/index_080_new: boost/geometry/extensions/index/algorithms boost/geometry/extensions/index/rtree boost/geometry/extensions/index/rtree/rstar boost/geometry/extensions/index/rtree/visitors tests
From: adam.wulkiewicz_at_[hidden]
Date: 2011-04-03 19:07:35
Author: awulkiew
Date: 2011-04-03 19:07:34 EDT (Sun, 03 Apr 2011)
New Revision: 70964
URL: http://svn.boost.org/trac/boost/changeset/70964
Log:
reinsert implemented
Added:
sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rstar/insert_impl.hpp (contents, props changed)
Text files modified:
sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/algorithms/area.hpp | 8 ++--
sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/algorithms/margin.hpp | 16 ++++----
sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/algorithms/overlap.hpp | 6 +-
sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/algorithms/union_area.hpp | 2
sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/node.hpp | 6 +++
sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rstar/choose_next_node.hpp | 4 +-
sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rstar/insert.hpp | 66 +++++----------------------------------
sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rstar/split.hpp | 14 ++++---
sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rtree.hpp | 4 +-
sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/are_boxes_ok.hpp | 2
sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/gl_draw.hpp | 2 -
sandbox-branches/geometry/index_080_new/tests/additional_sizes_and_times.cpp | 10 +++---
12 files changed, 49 insertions(+), 91 deletions(-)
Modified: sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/algorithms/area.hpp
==============================================================================
--- sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/algorithms/area.hpp (original)
+++ sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/algorithms/area.hpp 2011-04-03 19:07:34 EDT (Sun, 03 Apr 2011)
@@ -13,7 +13,7 @@
namespace boost { namespace geometry { namespace index {
template <typename Box>
-struct area_result
+struct default_area_result
{
typedef typename select_most_precise<
typename coordinate_type<Box>::type,
@@ -29,7 +29,7 @@
BOOST_STATIC_ASSERT(0 < CurrentDimension);
BOOST_STATIC_ASSERT(CurrentDimension <= traits::dimension<Box>::value);
- static inline typename area_result<Box>::type apply(Box const& b)
+ static inline typename default_area_result<Box>::type apply(Box const& b)
{
return area_for_each_dimension<Box, CurrentDimension - 1>::apply(b) *
( geometry::get<max_corner, CurrentDimension - 1>(b) - geometry::get<min_corner, CurrentDimension - 1>(b) );
@@ -39,7 +39,7 @@
template <typename Box>
struct area_for_each_dimension<Box, 1>
{
- static inline typename area_result<Box>::type apply(Box const& b)
+ static inline typename default_area_result<Box>::type apply(Box const& b)
{
return geometry::get<max_corner, 0>(b) - geometry::get<min_corner, 0>(b);
}
@@ -48,7 +48,7 @@
} // namespace detail
template <typename Box>
-typename area_result<Box>::type area(Box const& b)
+typename default_area_result<Box>::type area(Box const& b)
{
return detail::area_for_each_dimension<Box, traits::dimension<Box>::value>::apply(b);
}
Modified: sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/algorithms/margin.hpp
==============================================================================
--- sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/algorithms/margin.hpp (original)
+++ sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/algorithms/margin.hpp 2011-04-03 19:07:34 EDT (Sun, 03 Apr 2011)
@@ -13,7 +13,7 @@
namespace boost { namespace geometry { namespace index {
template <typename Box>
-struct margin_result
+struct default_margin_result
{
typedef typename select_most_precise<
typename coordinate_type<Box>::type,
@@ -29,7 +29,7 @@
BOOST_STATIC_ASSERT(0 < CurrentDimension);
BOOST_STATIC_ASSERT(0 < EdgeDimension);
- static inline typename margin_result<Box>::type apply(Box const& b)
+ static inline typename default_margin_result<Box>::type apply(Box const& b)
{
return margin_for_each_edge<Box, CurrentDimension, EdgeDimension - 1>::apply(b) *
( geometry::get<max_corner, EdgeDimension - 1>(b) - geometry::get<min_corner, EdgeDimension - 1>(b) );
@@ -41,7 +41,7 @@
{
BOOST_STATIC_ASSERT(0 < CurrentDimension);
- static inline typename margin_result<Box>::type apply(Box const& b)
+ static inline typename default_margin_result<Box>::type apply(Box const& b)
{
return margin_for_each_edge<Box, CurrentDimension, CurrentDimension - 1>::apply(b);
}
@@ -52,7 +52,7 @@
{
BOOST_STATIC_ASSERT(0 < CurrentDimension);
- static inline typename margin_result<Box>::type apply(Box const& b)
+ static inline typename default_margin_result<Box>::type apply(Box const& b)
{
return geometry::get<max_corner, 0>(b) - geometry::get<min_corner, 0>(b);
}
@@ -61,7 +61,7 @@
template <typename Box>
struct margin_for_each_edge<Box, 1, 1>
{
- static inline typename margin_result<Box>::type apply(Box const& b)
+ static inline typename default_margin_result<Box>::type apply(Box const& b)
{
return 1;
}
@@ -73,7 +73,7 @@
BOOST_STATIC_ASSERT(0 < CurrentDimension);
BOOST_STATIC_ASSERT(CurrentDimension <= traits::dimension<Box>::value);
- static inline typename margin_result<Box>::type apply(Box const& b)
+ static inline typename default_margin_result<Box>::type apply(Box const& b)
{
return margin_for_each_dimension<Box, CurrentDimension - 1>::apply(b) +
2 * margin_for_each_edge<Box, CurrentDimension, traits::dimension<Box>::value>::apply(b);
@@ -83,7 +83,7 @@
template <typename Box>
struct margin_for_each_dimension<Box, 1>
{
- static inline typename margin_result<Box>::type apply(Box const& b)
+ static inline typename default_margin_result<Box>::type apply(Box const& b)
{
return 2 * margin_for_each_edge<Box, 1, traits::dimension<Box>::value>::apply(b);
}
@@ -92,7 +92,7 @@
} // namespace detail
template <typename Box>
-typename margin_result<Box>::type margin(Box const& b)
+typename default_margin_result<Box>::type margin(Box const& b)
{
return detail::margin_for_each_dimension<Box, traits::dimension<Box>::value>::apply(b);
}
Modified: sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/algorithms/overlap.hpp
==============================================================================
--- sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/algorithms/overlap.hpp (original)
+++ sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/algorithms/overlap.hpp 2011-04-03 19:07:34 EDT (Sun, 03 Apr 2011)
@@ -16,13 +16,13 @@
namespace boost { namespace geometry { namespace index {
template <typename Box>
-struct overlap_result
+struct default_overlap_result
{
- typedef typename area_result<Box>::type type;
+ typedef typename default_area_result<Box>::type type;
};
template <typename Box>
-typename overlap_result<Box>::type overlap(Box const& b1, Box const& b2)
+typename default_overlap_result<Box>::type overlap(Box const& b1, Box const& b2)
{
Box inters;
geometry::assign_zero(inters);
Modified: sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/algorithms/union_area.hpp
==============================================================================
--- sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/algorithms/union_area.hpp (original)
+++ sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/algorithms/union_area.hpp 2011-04-03 19:07:34 EDT (Sun, 03 Apr 2011)
@@ -20,7 +20,7 @@
* \brief Compute the area of the union of b1 and b2
*/
template <typename Box, typename Geometry>
-inline typename area_result<Box>::type union_area(Box const& b, Geometry const& g)
+inline typename default_area_result<Box>::type union_area(Box const& b, Geometry const& g)
{
Box expanded_box(b);
geometry::expand(expanded_box, g);
Modified: sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/node.hpp
==============================================================================
--- sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/node.hpp (original)
+++ sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/node.hpp 2011-04-03 19:07:34 EDT (Sun, 03 Apr 2011)
@@ -107,6 +107,12 @@
return n.values;
}
+template <typename Node>
+struct element_type
+{
+ typedef typename elements_type<Node>::type::value_type type;
+};
+
// uniform indexable type for child node element's box and value's indexable
template <typename Value, typename Translator>
Modified: sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rstar/choose_next_node.hpp
==============================================================================
--- sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rstar/choose_next_node.hpp (original)
+++ sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rstar/choose_next_node.hpp 2011-04-03 19:07:34 EDT (Sun, 03 Apr 2011)
@@ -34,8 +34,8 @@
typedef typename internal_node::children_type children_type;
- typedef typename index::area_result<Box>::type area_type;
- typedef typename index::overlap_result<Box>::type overlap_type;
+ typedef typename index::default_area_result<Box>::type area_type;
+ typedef typename index::default_overlap_result<Box>::type overlap_type;
public:
template <typename Indexable>
Modified: sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rstar/insert.hpp
==============================================================================
--- sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rstar/insert.hpp (original)
+++ sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rstar/insert.hpp 2011-04-03 19:07:34 EDT (Sun, 03 Apr 2011)
@@ -10,10 +10,6 @@
#ifndef BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_RSTAR_INSERT_HPP
#define BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_RSTAR_INSERT_HPP
-#include <algorithm>
-
-#include <boost/tuple/tuple.hpp>
-
#include <boost/geometry/extensions/index/algorithms/area.hpp>
#include <boost/geometry/extensions/index/algorithms/margin.hpp>
#include <boost/geometry/extensions/index/algorithms/overlap.hpp>
@@ -23,8 +19,7 @@
#include <boost/geometry/extensions/index/rtree/visitors/insert.hpp>
#include <boost/geometry/extensions/index/rtree/visitors/is_leaf.hpp>
-#include <boost/geometry/extensions/index/rtree/rstar/choose_next_node.hpp>
-#include <boost/geometry/extensions/index/rtree/rstar/split.hpp>
+#include <boost/geometry/extensions/index/rtree/rstar/insert_impl.hpp>
namespace boost { namespace geometry { namespace index {
@@ -39,68 +34,25 @@
public:
inline explicit insert(node* & root, 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_parent(0), m_current_child_index(0), m_current_level(0)
+ : m_root(root)
+ , m_impl(root, v, min_elements, max_elements, t)
{}
inline void operator()(internal_node & n)
{
- // save previous traverse inputs and set new ones
- internal_node * parent_bckup = m_parent;
- m_parent = &n;
- size_t current_child_index_bckup = m_current_child_index;
- size_t current_level_bckup = m_current_level;
-
- // choose next node, where value insert traversing should go
- m_current_child_index =
- rstar::choose_next_node<Value, Box>::
- apply(n, m_tr(m_value));
-
- // expand the node to contain value
- geometry::expand(n.children[m_current_child_index].first, m_tr(m_value));
-
- // next traversing step
- boost::apply_visitor(*this, *n.children[m_current_child_index].second);
-
- // restore previous traverse inputs
- m_parent = parent_bckup;
- m_current_child_index = current_child_index_bckup;
- m_current_level = current_level_bckup;
-
- if ( m_max_elems_per_node < n.children.size() )
- overflow_treatment(n);
+ assert(&n == &boost::get<internal_node>(*m_root));
+ boost::apply_visitor(m_impl, *m_root);
}
inline void operator()(leaf & n)
{
- n.values.push_back(m_value);
-
- if ( m_max_elems_per_node < n.values.size() )
- overflow_treatment(n);
+ assert(&n == &boost::get<leaf>(*m_root));
+ boost::apply_visitor(m_impl, *m_root);
}
private:
- template <typename Node>
- inline void overflow_treatment(Node & n)
- {
- // TODO: awulkiew - reinsert
-
- rstar::split<Value, Translator, Box>::
- apply(n, m_parent, m_current_child_index, m_root_node, m_min_elems_per_node, m_max_elems_per_node, m_tr);
- }
-
- Value const& m_value;
- Translator const& m_tr;
- size_t m_min_elems_per_node;
- size_t m_max_elems_per_node;
-
- node* & m_root_node;
-
- // traversing input parameters
- internal_node *m_parent;
- size_t m_current_child_index;
- size_t m_current_level;
+ node* & m_root;
+ index::detail::rtree::rstar::insert_impl<Value, Translator, Box, Value> m_impl;
};
}}} // namespace detail::rtree::visitors
Added: sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rstar/insert_impl.hpp
==============================================================================
--- (empty file)
+++ sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rstar/insert_impl.hpp 2011-04-03 19:07:34 EDT (Sun, 03 Apr 2011)
@@ -0,0 +1,307 @@
+// Boost.Geometry (aka GGL, Generic Geometry Library)
+//
+// Boost.Index - R*-tree reinsert algorithm implementation
+//
+// 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_RSTAR_INSERT_IMPL_HPP
+#define BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_RSTAR_INSERT_IMPL_HPP
+
+#include <algorithm>
+
+#include <boost/geometry/strategies/strategies.hpp>
+#include <boost/geometry/algorithms/centroid.hpp>
+#include <boost/geometry/algorithms/distance.hpp>
+
+#include <boost/geometry/extensions/index/algorithms/area.hpp>
+#include <boost/geometry/extensions/index/algorithms/margin.hpp>
+#include <boost/geometry/extensions/index/algorithms/overlap.hpp>
+#include <boost/geometry/extensions/index/algorithms/union_area.hpp>
+
+#include <boost/geometry/extensions/index/rtree/node.hpp>
+#include <boost/geometry/extensions/index/rtree/visitors/insert.hpp>
+#include <boost/geometry/extensions/index/rtree/visitors/is_leaf.hpp>
+
+#include <boost/geometry/extensions/index/rtree/rstar/choose_next_node.hpp>
+#include <boost/geometry/extensions/index/rtree/rstar/split.hpp>
+
+namespace boost { namespace geometry { namespace index {
+
+namespace detail { namespace rtree { namespace rstar {
+
+template <typename Value, typename Translator, typename Box, typename Element>
+class insert_base;
+
+template <typename Value, typename Translator, typename Box, typename Element>
+class insert_impl : public insert_base<Value, Translator, Box, Element>
+{
+ typedef insert_base<Value, Translator, Box, Element> base;
+
+public:
+ inline insert_impl(
+ node* & root,
+ Element const& el,
+ size_t min_elements,
+ size_t max_elements,
+ Translator const& t,
+ size_t level = std::numeric_limits<size_t>::max()
+ )
+ : base(root, el, min_elements, max_elements, t, level)
+ {}
+
+ inline void operator()(internal_node & n)
+ {
+ if ( m_current_level < m_level )
+ {
+ // next traversing step
+ base::traverse(*this, n);
+ }
+ else
+ {
+ assert( m_level == m_current_level );
+
+ // push new child node
+ n.children.push_back(m_element);
+ }
+
+ if ( m_max_elems_per_node < n.children.size() )
+ base::overflow_treatment(n);
+ }
+
+ inline void operator()(leaf & n)
+ {
+ assert(false);
+ }
+};
+
+template <typename Value, typename Translator, typename Box>
+class insert_impl<Value, Translator, Box, Value> : public insert_base<Value, Translator, Box, Value>
+{
+ typedef insert_base<Value, Translator, Box, Value> base;
+
+public:
+ inline insert_impl(
+ node* & root,
+ Value const& v,
+ size_t min_elements,
+ size_t max_elements,
+ Translator const& t,
+ size_t level = std::numeric_limits<size_t>::max()
+ )
+ : base(root, v, min_elements, max_elements, t, level)
+ {}
+
+ inline void operator()(internal_node & n)
+ {
+ assert(m_current_level < m_level);
+
+ // next traversing step
+ base::traverse(*this, n);
+
+ if ( m_max_elems_per_node < n.children.size() )
+ base::overflow_treatment(n);
+ }
+
+ inline void operator()(leaf & n)
+ {
+ assert( m_level == m_current_level ||
+ m_level == std::numeric_limits<size_t>::max() );
+
+ n.values.push_back(m_element);
+
+ if ( m_max_elems_per_node < n.values.size() )
+ base::overflow_treatment(n);
+ }
+};
+
+template <typename Value, typename Translator, typename Box, typename Element>
+class insert_base : public boost::static_visitor<>
+{
+protected:
+ typedef typename rtree::node<Value, Box, rstar_tag>::type node;
+ typedef typename rtree::internal_node<Value, Box, rstar_tag>::type internal_node;
+ typedef typename rtree::leaf<Value, Box, rstar_tag>::type leaf;
+
+ inline insert_base(
+ node* & root,
+ Element const& el,
+ size_t min_elements,
+ size_t max_elements,
+ Translator const& t,
+ size_t level = std::numeric_limits<size_t>::max()
+ )
+ : m_element(el)
+ , m_tr(t)
+ , m_min_elems_per_node(min_elements)
+ , m_max_elems_per_node(max_elements)
+ , m_reinserted_elements_count(size_t(max_elements * 0.3f))
+ , m_level(level)
+ , m_root_node(root)
+ , m_parent(0), m_current_child_index(0), m_current_level(0)
+ {}
+
+ template <typename Derived>
+ inline void traverse(Derived & d, internal_node & n)
+ {
+ // choose next node, where value insert traversing should go
+ size_t choosen_node_index = rstar::choose_next_node<Value, Box>::
+ apply(n, rtree::element_indexable(m_element, m_tr));
+
+ // expand the node to contain value
+ geometry::expand(
+ n.children[choosen_node_index].first,
+ rtree::element_indexable(m_element, m_tr));
+
+ // apply traversing visitor
+ traverse_apply_visitor(d, n, choosen_node_index);
+ }
+
+ template <typename Derived>
+ inline void traverse_apply_visitor(Derived & d, internal_node &n, size_t choosen_node_index)
+ {
+ // save previous traverse inputs and set new ones
+ internal_node * parent_bckup = m_parent;
+ size_t current_child_index_bckup = m_current_child_index;
+ size_t current_level_bckup = m_current_level;
+
+ m_parent = &n;
+ m_current_child_index = choosen_node_index;
+ ++m_current_level;
+
+ // next traversing step
+ boost::apply_visitor(d, *n.children[choosen_node_index].second);
+
+ // restore previous traverse inputs
+ m_parent = parent_bckup;
+ m_current_child_index = current_child_index_bckup;
+ m_current_level = current_level_bckup;
+ }
+
+ // before calling overflow_treatment all nodes have aabbs expanded
+ // and the number of elements in the current node is max + 1
+ template <typename Node>
+ inline void overflow_treatment(Node & n)
+ {
+ // TODO: awulkiew - replace this condition with tag dispatched template
+
+ // first time insert
+ if ( m_parent != 0 &&
+ m_level == std::numeric_limits<size_t>::max() &&
+ 0 < m_reinserted_elements_count )
+ {
+ reinsert(n);
+ }
+ // second time insert
+ else
+ {
+ rstar::split<Value, Translator, Box>::
+ apply(n, m_parent, m_current_child_index, m_root_node, m_min_elems_per_node, m_max_elems_per_node, m_tr);
+ }
+ }
+
+ template <typename Distance, typename Element>
+ static inline bool distances_asc(
+ std::pair<Distance, Element> const& d1,
+ std::pair<Distance, Element> const& d2)
+ {
+ return d1.first < d2.first;
+ }
+
+ template <typename Distance, typename Element>
+ static inline bool distances_dsc(
+ std::pair<Distance, Element> const& d1,
+ std::pair<Distance, Element> const& d2)
+ {
+ return d1.first > d2.first;
+ }
+
+ template <typename Node>
+ inline void reinsert(Node & n)
+ {
+ typedef typename index::detail::rtree::elements_type<Node>::type elements_type;
+ typedef typename index::detail::rtree::element_type<Node>::type element_type;
+ typedef typename geometry::point_type<Box>::type point_type;
+ // TODO: awulkiew - use distance_result
+ typedef typename index::traits::coordinate_type<point_type>::type distance_type;
+
+ assert(m_parent != 0);
+ assert(0 < m_reinserted_elements_count);
+
+ point_type node_center;
+ geometry::centroid(m_parent->children[m_current_child_index].first, node_center);
+
+ elements_type & elements = index::detail::rtree::elements_get(n);
+
+ size_t elements_count = elements.size();
+ std::vector< std::pair<distance_type, element_type> > distances(elements_count);
+ for ( size_t i = 0 ; i < elements_count ; ++i )
+ {
+ // TODO: awulkiew - use distance_sqr
+ // (use select_calculation_type if distance_sqr must be implemented in geometry::index)
+ // change point type for this geometry
+ point_type element_center;
+ geometry::centroid( index::detail::rtree::element_indexable(
+ elements[i],
+ m_tr
+ ), element_center);
+
+ distances[i].first = geometry::distance(node_center, element_center);
+ distances[i].second = elements[i];
+ }
+
+ // sort elements by distances from center
+ std::partial_sort(
+ distances.begin(),
+ distances.begin() + m_reinserted_elements_count,
+ distances.end(),
+ distances_dsc<distance_type, element_type>);
+
+ // copy elements which will be reinserted
+ elements_type elements_to_reinsert(m_reinserted_elements_count);
+ for ( size_t i = 0 ; i < m_reinserted_elements_count ; ++i )
+ elements_to_reinsert[i] = distances[i].second;
+
+ // copy elements to the current node
+ elements.resize(elements_count - m_reinserted_elements_count);
+ for ( size_t i = m_reinserted_elements_count ; i < elements_count ; ++i )
+ elements[i - m_reinserted_elements_count] = distances[i].second;
+
+ // calulate node's new box
+ m_parent->children[m_current_child_index].first =
+ elements_box<Box>(elements.begin(), elements.end(), m_tr);
+
+ // reinsert children starting from the minimum distance
+ for ( size_t i = m_reinserted_elements_count ; 0 < i ; --i )
+ {
+ insert_impl<Value, Translator, Box, element_type> insert_v(
+ m_root_node, elements_to_reinsert[i - 1],
+ m_min_elems_per_node, m_max_elems_per_node,
+ m_tr, m_current_level);
+ boost::apply_visitor(insert_v, *m_root_node);
+ }
+ }
+
+ 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_reinserted_elements_count;
+
+ const size_t m_level;
+
+ node* & m_root_node;
+
+ // traversing input parameters
+ internal_node *m_parent;
+ size_t m_current_child_index;
+ size_t m_current_level;
+};
+
+}}} // namespace detail::rtree::rstar
+
+}}} // namespace boost::geometry::index
+
+#endif // BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_RSTAR_INSERT_IMPL_HPP
Modified: sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rstar/split.hpp
==============================================================================
--- sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rstar/split.hpp (original)
+++ sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rstar/split.hpp 2011-04-03 19:07:34 EDT (Sun, 03 Apr 2011)
@@ -59,9 +59,9 @@
template <typename Box>
struct split_axis_data
{
- typedef typename margin_result<Box>::type margin_type;
- typedef typename overlap_result<Box>::type overlap_type;
- typedef typename area_result<Box>::type area_type;
+ typedef typename default_margin_result<Box>::type margin_type;
+ typedef typename default_overlap_result<Box>::type overlap_type;
+ typedef typename default_area_result<Box>::type area_type;
inline split_axis_data()
: margins_sum(0)
@@ -141,9 +141,9 @@
template <typename Elements, typename Box>
struct split_data
{
- typedef typename margin_result<Box>::type margin_type;
- typedef typename overlap_result<Box>::type overlap_type;
- typedef typename area_result<Box>::type area_type;
+ typedef typename default_margin_result<Box>::type margin_type;
+ typedef typename default_overlap_result<Box>::type overlap_type;
+ typedef typename default_area_result<Box>::type area_type;
inline split_data()
: smallest_margins_sum(std::numeric_limits<margin_type>::max())
@@ -314,6 +314,7 @@
sd.choosen_distribution.begin() + sd.choosen_median_index,
elements.begin());
+ // node is not the root
if ( parent != 0 )
{
// update old node's box
@@ -321,6 +322,7 @@
// add new node to the parent's children
parent->children.push_back(std::make_pair(sd.choosen_right_box, right_node));
}
+ // node is the root
else
{
assert(&n == boost::get<Node>(root));
Modified: sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rtree.hpp
==============================================================================
--- sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rtree.hpp (original)
+++ sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rtree.hpp 2011-04-03 19:07:34 EDT (Sun, 03 Apr 2011)
@@ -42,8 +42,8 @@
typedef typename detail::rtree::leaf<value_type, box_type, tag_type>::type leaf;
inline explicit rtree(
- size_t max_elems_per_node = 2,
- size_t min_elems_per_node = 1,
+ size_t max_elems_per_node = 4,
+ size_t min_elems_per_node = 2,
translator_type const& translator = translator_type()
)
: m_values_count(0)
Modified: sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/are_boxes_ok.hpp
==============================================================================
--- sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/are_boxes_ok.hpp (original)
+++ sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/are_boxes_ok.hpp 2011-04-03 19:07:34 EDT (Sun, 03 Apr 2011)
@@ -10,7 +10,7 @@
#ifndef BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_VISITORS_ARE_BOXES_OK_HPP
#define BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_VISITORS_ARE_BOXES_OK_HPP
-#include <boost/geometry/algorithms//equals.hpp>
+#include <boost/geometry/algorithms/equals.hpp>
#include <boost/geometry/extensions/index/rtree/node.hpp>
namespace boost { namespace geometry { namespace index {
Modified: sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/gl_draw.hpp
==============================================================================
--- sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/gl_draw.hpp (original)
+++ sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/gl_draw.hpp 2011-04-03 19:07:34 EDT (Sun, 03 Apr 2011)
@@ -10,8 +10,6 @@
#ifndef BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_VISITORS_GL_DRAW_HPP
#define BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_VISITORS_GL_DRAW_HPP
-#include <iostream>
-
#include <boost/geometry/extensions/index/rtree/node.hpp>
namespace boost { namespace geometry { namespace index {
Modified: sandbox-branches/geometry/index_080_new/tests/additional_sizes_and_times.cpp
==============================================================================
--- sandbox-branches/geometry/index_080_new/tests/additional_sizes_and_times.cpp (original)
+++ sandbox-branches/geometry/index_080_new/tests/additional_sizes_and_times.cpp 2011-04-03 19:07:34 EDT (Sun, 03 Apr 2011)
@@ -35,14 +35,14 @@
typedef boost::geometry::model::box<P> B;
// randomize boxes
- const size_t n = 10000;
+ const size_t n = 100000;
std::vector<B> v(n);
for ( size_t i = 0 ; i < n ; ++i )
{
- float x = float( rand() % 1000 );
- float y = float( rand() % 1000 );
- float w = float( rand() % 10 ) / 10.0f;
- float h = float( rand() % 10 ) / 10.0f;
+ float x = float( rand() % 100000 );
+ float y = float( rand() % 100000 );
+ float w = float( rand() % 100 );
+ float h = float( rand() % 100 );
v[i] = B(P(x - w, y - h),P(x + w, y + h));
}
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