Subject: [Boost-commit] svn:boost r72531 - 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-06-09 19:56:00
Author: awulkiew
Date: 2011-06-09 19:55:58 EDT (Thu, 09 Jun 2011)
New Revision: 72531
URL: http://svn.boost.org/trac/boost/changeset/72531
Log:
reinserting insert visitor corrected, insert visitors now relies on relative level, levels check added, boxes check corrected.
Added:
sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/algorithms/distance_sqr.hpp (contents, props changed)
sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/are_levels_ok.hpp (contents, props changed)
Removed:
sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rstar/split.hpp
Text files modified:
sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/algorithms/within.hpp | 4
sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rstar/insert.hpp | 736 +++++++++++++++++++++++++++------------
sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rstar/redistribute_elements.hpp | 5
sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rstar/rstar.hpp | 1
sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rtree.hpp | 6
sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/are_boxes_ok.hpp | 34 +
sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/insert.hpp | 62 +-
sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/remove.hpp | 22
sandbox-branches/geometry/index_080_new/tests/additional_glut_vis.cpp | 21
sandbox-branches/geometry/index_080_new/tests/additional_sizes_and_times.cpp | 60 ++
10 files changed, 642 insertions(+), 309 deletions(-)
Added: sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/algorithms/distance_sqr.hpp
==============================================================================
--- (empty file)
+++ sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/algorithms/distance_sqr.hpp 2011-06-09 19:55:58 EDT (Thu, 09 Jun 2011)
@@ -0,0 +1,78 @@
+// Boost.Geometry (aka GGL, Generic Geometry Library)
+//
+// Boost.SpatialIndex - n-dimensional distance_sqr between points
+//
+// 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_ALGORITHMS_DISTANCE_SQR_HPP
+#define BOOST_GEOMETRY_EXTENSIONS_INDEX_ALGORITHMS_DISTANCE_SQR_HPP
+
+namespace boost { namespace geometry { namespace index {
+
+template <typename Point1, typename Point2>
+class default_distance_sqr_result
+{
+ typedef typename select_most_precise<
+ typename traits::coordinate_type<Point1>::type,
+ long double
+ >::type intermediate_type;
+
+public:
+ typedef typename select_most_precise<
+ typename traits::coordinate_type<Point2>::type,
+ intermediate_type
+ >::type type;
+};
+
+namespace detail {
+
+template <typename Point1, typename Point2, size_t CurrentDimension>
+struct distance_sqr_for_each_dimension
+{
+ BOOST_STATIC_ASSERT(0 < CurrentDimension);
+ BOOST_STATIC_ASSERT(CurrentDimension <= traits::dimension<Point1>::value);
+
+ typedef typename default_distance_sqr_result<Point1, Point2>::type result_type;
+
+ static inline result_type apply(Point1 const& p1, Point2 const& p2)
+ {
+ result_type temp = geometry::get<CurrentDimension - 1>(p1) - geometry::get<CurrentDimension - 1>(p2);
+ return distance_sqr_for_each_dimension<Point1, Point2, CurrentDimension - 1>::apply(p1, p2) +
+ temp * temp;
+ }
+};
+
+template <typename Point1, typename Point2>
+struct distance_sqr_for_each_dimension<Point1, Point2, 1>
+{
+ BOOST_STATIC_ASSERT(1 <= traits::dimension<Point1>::value);
+
+ typedef typename default_distance_sqr_result<Point1, Point2>::type result_type;
+
+ static inline result_type apply(Point1 const& p1, Point2 const& p2)
+ {
+ result_type temp = geometry::get<0>(p1) - geometry::get<0>(p2);
+ return temp * temp;
+ }
+};
+
+} // namespace detail
+
+template <typename Point1, typename Point2>
+typename default_distance_sqr_result<Point1, Point2>::type distance_sqr(Point1 const& p1, Point2 const& p2)
+{
+ BOOST_STATIC_ASSERT(traits::dimension<Point1>::value == traits::dimension<Point2>::value);
+
+ return detail::distance_sqr_for_each_dimension<
+ Point1,
+ Point2,
+ index::traits::dimension<Point1>::value
+ >::apply(p1, p2);
+}
+
+}}} // namespace boost::geometry::index
+
+#endif // BOOST_GEOMETRY_EXTENSIONS_INDEX_ALGORITHMS_DISTANCE_SQR_HPP
Modified: sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/algorithms/within.hpp
==============================================================================
--- sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/algorithms/within.hpp (original)
+++ sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/algorithms/within.hpp 2011-06-09 19:55:58 EDT (Thu, 09 Jun 2011)
@@ -46,7 +46,7 @@
template <typename Box>
static inline bool apply(Box const& b, Indexable const& p)
{
- return index::get<min_corner, DimensionIndex>(b) <= index::get<DimensionIndex>(p);
+ return index::get<min_corner, DimensionIndex>(b) <= geometry::get<DimensionIndex>(p);
}
};
@@ -56,7 +56,7 @@
template <typename Box>
static inline bool apply(Box const& b, Indexable const& p)
{
- return index::get<DimensionIndex>(p) <= index::get<max_corner, DimensionIndex>(b);
+ return geometry::get<DimensionIndex>(p) <= index::get<max_corner, DimensionIndex>(b);
}
};
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-06-09 19:55:58 EDT (Thu, 09 Jun 2011)
@@ -1,6 +1,6 @@
// Boost.Geometry (aka GGL, Generic Geometry Library)
//
-// Boost.Index - R*-tree insert algorithm implementation
+// Boost.Index - R*-tree insert
//
// Copyright 2011 Adam Wulkiewicz.
// Use, modification and distribution is subject to the Boost Software License,
@@ -10,27 +10,12 @@
#ifndef BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_RSTAR_INSERT_HPP
#define BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_RSTAR_INSERT_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/algorithms/distance_sqr.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>
-
-//TEST
-#include <boost/geometry/extensions/index/rtree/visitors/print.hpp>
-#include <boost/geometry/extensions/index/rtree/visitors/are_boxes_ok.hpp>
namespace boost { namespace geometry { namespace index {
@@ -38,222 +23,513 @@
namespace detail {
-//template <typename Element, typename Value, typename Translator, typename Box>
-//class insert<Element, Value, Translator, Box, rstar_tag> : 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(node* & root,
-// Element const& el,
-// size_t min_elements,
-// size_t max_elements,
-// Translator const& tr,
-// size_t level = std::numeric_limits<size_t>::max()
-// )
-// : m_element(el)
-// , m_tr(tr)
-// , 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));
-//
-// //TEST
-// /*{
-// std::ofstream log("log.txt", std::ofstream::trunc);
-// log << std::fixed << "internal node " << m_current_level << " " << m_level << '\n';
-// boost::geometry::index::detail::rtree::visitors::detail::print_indexable(log, rtree::element_indexable(m_element, m_tr));
-// log << '\n' << "choosen node: " << choosen_node_index << "\n";
-// log << "before: ";
-// boost::geometry::index::detail::rtree::visitors::detail::print_indexable(log, n.children[choosen_node_index].first);
-// log << "\n";
-// }*/
-//
-// // expand the node to contain value
-// geometry::expand(
-// n.children[choosen_node_index].first,
-// rtree::element_indexable(m_element, m_tr));
-//
-// //TEST
-// /*{
-// std::ofstream log("log.txt", std::ofstream::app);
-// log << std::fixed << choosen_node_index << "after: ";
-// boost::geometry::index::detail::rtree::visitors::detail::print_indexable(log, n.children[choosen_node_index].first);
-// log << '\n';
-// boost::geometry::index::detail::rtree::visitors::print<Value, Translator, Box, rstar_tag> print_v(log, m_tr);
-// boost::apply_visitor(print_v, *m_root_node);
-// }*/
-//
-// // apply traversing visitor
-// traverse_apply_visitor(d, n, choosen_node_index);
-// }
-//
-// template <typename Node>
-// inline void post_traverse_handle_oveflow(Node &n)
-// {
-// // handle overflow
-// if ( m_max_elems_per_node < rtree::elements_get(n).size() )
-// {
-// detail::overflow_treatment<Value, Translator, Box, Tag>::
-// 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 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 El>
-// static inline bool distances_asc(
-// std::pair<Distance, El> const& d1,
-// std::pair<Distance, El> const& d2)
-// {
-// return d1.first < d2.first;
-// }
-//
-// template <typename Distance, typename El>
-// static inline bool distances_dsc(
-// std::pair<Distance, El> const& d1,
-// std::pair<Distance, El> 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 rstar {
+
+template <typename Value, typename Translator, typename Box>
+class remove_elements_to_reinsert
+{
+public:
+ 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;
+
+ 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;
+ typedef typename elements_type::value_type element_type;
+ typedef typename geometry::point_type<Box>::type point_type;
+ // 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;
+
+ assert(parent != 0);
+
+ const size_t reinserted_elements_count = static_cast<size_t>(max_elems * 0.3f);
+ assert(0 < reinserted_elements_count);
+
+ // 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 )
+ {
+ point_type element_center;
+ geometry::centroid( rtree::element_indexable(elements[i], tr),
+ element_center);
+ sorted_elements[i].first = index::distance_sqr(node_center, element_center);
+ sorted_elements[i].second = elements[i];
+ }
+
+ // sort elements by distances from center
+ std::partial_sort(
+ sorted_elements.begin(),
+ sorted_elements.begin() + reinserted_elements_count,
+ sorted_elements.end(),
+ distances_dsc<distance_sqr_type, element_type>);
+
+ // copy elements which will be reinserted
+ result_elements.resize(reinserted_elements_count);
+ for ( size_t i = 0 ; i < reinserted_elements_count ; ++i )
+ result_elements[i] = sorted_elements[i].second;
+
+ // copy remaining elements to the current node
+ elements.resize(elements_count - reinserted_elements_count);
+ for ( size_t i = reinserted_elements_count ; i < elements_count ; ++i )
+ elements[i - reinserted_elements_count] = sorted_elements[i].second;
+ }
+
+private:
+ template <typename Distance, typename El>
+ static inline bool distances_asc(
+ std::pair<Distance, El> const& d1,
+ std::pair<Distance, El> const& d2)
+ {
+ return d1.first < d2.first;
+ }
+
+ template <typename Distance, typename El>
+ static inline bool distances_dsc(
+ std::pair<Distance, El> const& d1,
+ std::pair<Distance, El> const& d2)
+ {
+ return d1.first > d2.first;
+ }
+};
+
+template <typename Value, typename Translator, typename Box>
+struct reinsert_or_split_root
+{
+ 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;
+
+ template <typename Node>
+ static inline void apply(
+ typename rtree::elements_type<Node>::type & result_elements,
+ Node & n,
+ internal_node *parent,
+ size_t current_child_index,
+ node* & root_node,
+ size_t & leafs_level,
+ size_t min_elems,
+ size_t max_elems,
+ Translator const& tr)
+ {
+ // node isn't root node
+ if ( parent )
+ {
+ rstar::remove_elements_to_reinsert<Value, Translator, Box>::apply(
+ result_elements, n,
+ parent, current_child_index,
+ min_elems, max_elems, tr);
+ }
+ // node is root node
+ else
+ {
+ // it's really the root node
+ assert(&rtree::get<Node>(n) == root_node);
+
+ detail::split<Value, Translator, Box, rstar_tag>::apply(
+ n,
+ parent, current_child_index,
+ root_node, leafs_level,
+ min_elems, max_elems, tr);
+ }
+ }
+};
+
+template <size_t InsertIndex, typename Element, typename Value, typename Translator, typename Box>
+struct level_insert
+ : public detail::insert<Element, Value, Translator, Box, rstar_tag>
+{
+ typedef detail::insert<Element, Value, Translator, Box, rstar_tag> base;
+ typedef typename base::node node;
+ typedef typename base::internal_node internal_node;
+ typedef typename base::leaf leaf;
+
+ typedef typename rtree::elements_type<internal_node>::type result_type;
+
+ 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)
+ , result_relative_level(0)
+ {}
+
+ inline void operator()(internal_node & n)
+ {
+ assert(base::m_current_level < base::m_leafs_level);
+
+ if ( base::m_current_level < base::m_level )
+ {
+ // next traversing step
+ base::traverse(*this, n);
+
+ // further insert
+ if ( 0 < InsertIndex )
+ {
+ assert(0 < base::m_level);
+
+ if ( base::m_current_level == base::m_level - 1 )
+ {
+ result_relative_level = base::m_leafs_level - base::m_current_level;
+
+ // overflow
+ if ( base::m_max_elems_per_node < rtree::elements(n).size() )
+ {
+ rstar::reinsert_or_split_root<Value, Translator, Box>::apply(
+ result_elements, n,
+ base::m_parent, base::m_current_child_index,
+ base::m_root_node, base::m_leafs_level,
+ base::m_min_elems_per_node, base::m_max_elems_per_node, base::m_tr);
+ }
+ }
+ }
+ }
+ else
+ {
+ assert( base::m_level == base::m_current_level );
+
+ // push new child node
+ rtree::elements(n).push_back(base::m_element);
+
+ // first insert
+ if ( 0 == InsertIndex )
+ {
+ result_relative_level = base::m_leafs_level - base::m_current_level;
+
+ // overflow
+ if ( base::m_max_elems_per_node < rtree::elements(n).size() )
+ {
+ rstar::reinsert_or_split_root<Value, Translator, Box>::apply(
+ result_elements, n,
+ base::m_parent, base::m_current_child_index,
+ base::m_root_node, base::m_leafs_level,
+ base::m_min_elems_per_node, base::m_max_elems_per_node, base::m_tr);
+ }
+ }
+ // not the first insert
+ else
+ {
+ // overflow
+ if ( base::m_max_elems_per_node < rtree::elements(n).size() )
+ {
+ detail::split<Value, Translator, Box, rstar_tag>::apply(
+ n,
+ base::m_parent, base::m_current_child_index,
+ base::m_root_node, base::m_leafs_level,
+ base::m_min_elems_per_node, base::m_max_elems_per_node, base::m_tr);
+ }
+ }
+ }
+
+ if ( !result_elements.empty() && base::m_parent )
+ {
+ // calulate node's new box
+ rtree::elements(*base::m_parent)[base::m_current_child_index].first =
+ elements_box<Box>(rtree::elements(n).begin(), rtree::elements(n).end(), base::m_tr);
+ }
+ }
+
+ inline void operator()(leaf &)
+ {
+ assert(false);
+ }
+
+ size_t result_relative_level;
+ result_type result_elements;
+};
+
+template <size_t InsertIndex, typename Value, typename Translator, typename Box>
+struct level_insert<InsertIndex, Value, Value, Translator, Box>
+ : public detail::insert<Value, Value, Translator, Box, rstar_tag>
+{
+ typedef detail::insert<Value, Value, Translator, Box, rstar_tag> base;
+ typedef typename base::node node;
+ typedef typename base::internal_node internal_node;
+ typedef typename base::leaf leaf;
+
+ typedef typename rtree::elements_type<internal_node>::type result_type;
+
+ 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)
+ , result_relative_level(0)
+ {}
+
+ inline void operator()(internal_node & n)
+ {
+ assert(base::m_current_level < base::m_leafs_level);
+ assert(base::m_current_level < base::m_level);
+
+ // next traversing step
+ base::traverse(*this, n);
+
+ assert(0 < base::m_level);
+
+ if ( base::m_current_level == base::m_level - 1 )
+ {
+ result_relative_level = base::m_leafs_level - base::m_current_level;
+
+ // overflow
+ if ( base::m_max_elems_per_node < rtree::elements(n).size() )
+ {
+ rstar::reinsert_or_split_root<Value, Translator, Box>::apply(
+ result_elements, n,
+ base::m_parent, base::m_current_child_index,
+ base::m_root_node, base::m_leafs_level,
+ base::m_min_elems_per_node, base::m_max_elems_per_node, base::m_tr);
+ }
+ }
+
+ if ( !result_elements.empty() && base::m_parent )
+ {
+ // calulate node's new box
+ rtree::elements(*base::m_parent)[base::m_current_child_index].first =
+ elements_box<Box>(rtree::elements(n).begin(), rtree::elements(n).end(), base::m_tr);
+ }
+ }
+
+ inline void operator()(leaf & n)
+ {
+ assert(base::m_current_level == base::m_leafs_level);
+ assert(base::m_level == base::m_current_level ||
+ base::m_level == std::numeric_limits<size_t>::max());
+
+ rtree::elements(n).push_back(base::m_element);
+
+ if ( base::m_max_elems_per_node < rtree::elements(n).size() )
+ {
+ detail::split<Value, Translator, Box, rstar_tag>::apply(
+ n,
+ base::m_parent, base::m_current_child_index,
+ base::m_root_node, base::m_leafs_level,
+ base::m_min_elems_per_node, base::m_max_elems_per_node, base::m_tr);
+ }
+ }
+
+ size_t result_relative_level;
+ result_type result_elements;
+};
+
+template <typename Value, typename Translator, typename Box>
+struct level_insert<0, Value, Value, Translator, Box>
+ : public detail::insert<Value, Value, Translator, Box, rstar_tag>
+{
+ typedef detail::insert<Value, Value, Translator, Box, rstar_tag> base;
+ typedef typename base::node node;
+ typedef typename base::internal_node internal_node;
+ typedef typename base::leaf leaf;
+
+ typedef typename rtree::elements_type<leaf>::type result_type;
+
+ 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)
+ , result_relative_level(0)
+ {}
+
+ inline void operator()(internal_node & n)
+ {
+ assert(base::m_current_level < base::m_leafs_level);
+ assert(base::m_current_level < base::m_level);
+
+ // next traversing step
+ base::traverse(*this, n);
+
+ if ( !result_elements.empty() && base::m_parent )
+ {
+ // calulate node's new box
+ rtree::elements(*base::m_parent)[base::m_current_child_index].first =
+ elements_box<Box>(rtree::elements(n).begin(), rtree::elements(n).end(), base::m_tr);
+ }
+ }
+
+ inline void operator()(leaf & n)
+ {
+ assert(base::m_current_level == base::m_leafs_level);
+ assert(base::m_level == base::m_current_level ||
+ base::m_level == std::numeric_limits<size_t>::max());
+
+ rtree::elements(n).push_back(base::m_element);
+
+ result_relative_level = base::m_leafs_level - base::m_current_level;
+
+ if ( base::m_max_elems_per_node < rtree::elements(n).size() )
+ {
+ rstar::reinsert_or_split_root<Value, Translator, Box>::apply(
+ result_elements, n,
+ base::m_parent, base::m_current_child_index,
+ base::m_root_node, base::m_leafs_level,
+ base::m_min_elems_per_node, base::m_max_elems_per_node, base::m_tr);
+ }
+
+ if ( !result_elements.empty() && base::m_parent )
+ {
+ // calulate node's new box
+ rtree::elements(*base::m_parent)[base::m_current_child_index].first =
+ elements_box<Box>(rtree::elements(n).begin(), rtree::elements(n).end(), base::m_tr);
+ }
+ }
+
+ size_t result_relative_level;
+ result_type result_elements;
+};
+
+// R*-tree insert visitor
+template <typename Element, typename Value, typename Translator, typename Box>
+class insert : public rtree::visitor<Value, Box, rstar_tag, false>::type
+{
+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;
+
+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)
+ {}
+
+ inline void operator()(internal_node & n)
+ {
+ typedef typename elements_type<internal_node>::type elements_type;
+
+ rstar::level_insert<0, Element, Value, Translator, Box> lins_v(
+ m_root, m_leafs_level, m_element, m_min_elements, m_max_elements, m_tr, m_relative_level);
+
+ rtree::apply_visitor(lins_v, n);
+
+ if ( !lins_v.result_elements.empty() )
+ {
+ recursive_reinsert(lins_v.result_elements, lins_v.result_relative_level);
+ }
+ }
+
+ inline void operator()(leaf & n)
+ {
+ rstar::level_insert<0, Element, Value, Translator, Box> lins_v(
+ m_root, m_leafs_level, m_element, m_min_elements, m_max_elements, m_tr, m_relative_level);
+
+ rtree::apply_visitor(lins_v, n);
+
+ // we're in the root, so root should be split and there should be no elements to reinsert
+ assert(lins_v.result_elements.empty());
+ }
+
+protected:
+ template <typename Elements>
+ inline void recursive_reinsert(Elements const& elements, size_t relative_level)
+ {
+ typedef typename Elements::value_type element_type;
+
+ // reinsert children starting from the minimum distance
+ for ( typename Elements::const_reverse_iterator it = elements.rbegin();
+ it != elements.rend(); ++it)
+ {
+ rstar::level_insert<1, element_type, Value, Translator, Box> lins_v(
+ m_root, m_leafs_level, *it, m_min_elements, m_max_elements, m_tr, relative_level);
+
+ rtree::apply_visitor(lins_v, *m_root);
+
+ assert(relative_level + 1 == lins_v.result_relative_level);
+
+ // non-root relative level
+ if ( lins_v.result_relative_level < m_leafs_level && !lins_v.result_elements.empty())
+ {
+ recursive_reinsert(lins_v.result_elements, lins_v.result_relative_level);
+ }
+ }
+ }
+
+ node* & m_root;
+ size_t & m_leafs_level;
+ Element const& m_element;
+ size_t m_min_elements;
+ size_t m_max_elements;
+ Translator const& m_tr;
+ size_t m_relative_level;
+};
+
+} // namespace rstar
} // namespace detail
+// R*-tree insert visitor
+template <typename Element, typename Value, typename Translator, typename Box>
+class insert<Element, Value, Translator, Box, rstar_tag>
+ : public detail::rstar::insert<Element, Value, Translator, Box>
+{
+ typedef detail::rstar::insert<Element, Value, Translator, Box> base;
+ typedef typename base::node node;
+
+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
+ )
+ : base(root, leafs_level, element, min_elements, max_elements, tr, relative_level)
+ {}
+};
+
+// R*-tree insert visitor
+template <typename Value, typename Translator, typename Box>
+class insert<Value, Value, Translator, Box, rstar_tag>
+ : public detail::rstar::insert<Value, Value, Translator, Box>
+{
+ typedef detail::rstar::insert<Value, Value, Translator, Box> base;
+ typedef typename base::node node;
+
+public:
+ inline insert(node* & root,
+ size_t & leafs_level,
+ Value 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)
+ {}
+};
+
}}} // namespace detail::rtree::visitors
}}} // namespace boost::geometry::index
Modified: sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rstar/redistribute_elements.hpp
==============================================================================
--- sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rstar/redistribute_elements.hpp (original)
+++ sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rstar/redistribute_elements.hpp 2011-06-09 19:55:58 EDT (Thu, 09 Jun 2011)
@@ -1,6 +1,6 @@
// Boost.Geometry (aka GGL, Generic Geometry Library)
//
-// Boost.Index - R-tree quadratic split algorithm implementation
+// Boost.Index - R*-tree split algorithm implementation
//
// Copyright 2011 Adam Wulkiewicz.
// Use, modification and distribution is subject to the Boost Software License,
@@ -35,7 +35,8 @@
typedef typename index::default_area_result<Box>::type area_type;
template <typename Node>
- static inline void apply(Node & n,
+ static inline void apply(
+ Node & n,
Node & second_node,
Box & box1,
Box & box2,
Modified: sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rstar/rstar.hpp
==============================================================================
--- sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rstar/rstar.hpp (original)
+++ sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rstar/rstar.hpp 2011-06-09 19:55:58 EDT (Thu, 09 Jun 2011)
@@ -16,6 +16,7 @@
}}} // namespace boost::geometry::index
+#include <boost/geometry/extensions/index/rtree/rstar/insert.hpp>
#include <boost/geometry/extensions/index/rtree/rstar/choose_next_node.hpp>
#include <boost/geometry/extensions/index/rtree/rstar/redistribute_elements.hpp>
Deleted: 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 2011-06-09 19:55:58 EDT (Thu, 09 Jun 2011)
+++ (empty file)
@@ -1,345 +0,0 @@
-// Boost.Geometry (aka GGL, Generic Geometry Library)
-//
-// Boost.Index - R*-tree split 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_SPLIT_HPP
-#define BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_RSTAR_SPLIT_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>
-#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>
-
-namespace boost { namespace geometry { namespace index {
-
-namespace detail { namespace rtree { namespace rstar {
-
-// elements less
-
-template <typename Elements, typename Translator, size_t AxisIndex, size_t Corner>
-class elements_less
-{
- typedef typename Elements::value_type element_type;
-public:
- inline elements_less(Translator const& tr)
- : m_tr(tr)
- {}
-
- inline bool operator()(element_type const& e1, element_type const e2) const
- {
- return
- index::get<Corner, AxisIndex>(
- rtree::element_indexable(e1, m_tr)
- )
- <
- index::get<Corner, AxisIndex>(
- rtree::element_indexable(e2, m_tr)
- );
- }
-
-private:
- Translator const& m_tr;
-};
-
-// rstar split axis data
-
-template <typename Box>
-struct split_axis_data
-{
- 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)
- , smallest_overlap(std::numeric_limits<overlap_type>::max())
- , smallest_area(std::numeric_limits<area_type>::max())
- {}
-
- inline void update(
- size_t corner,
- size_t median_index,
- Box const& left_box,
- Box const& right_box,
- margin_type const& margin,
- overlap_type const& overlap,
- area_type const& area)
- {
- margins_sum += margin;
-
- if ( overlap < smallest_overlap ||
- ( overlap == smallest_overlap && area < smallest_area ) )
- {
- choosen_corner = corner;
- choosen_median_index = median_index;
- choosen_left_box = left_box;
- choosen_right_box = right_box;
- smallest_overlap = overlap;
- smallest_area = area;
- }
- }
-
- size_t choosen_corner;
- size_t choosen_median_index;
- Box choosen_left_box;
- Box choosen_right_box;
- margin_type margins_sum;
- overlap_type smallest_overlap;
- area_type smallest_area;
-};
-
-// update axis data for given axis and corner
-
-template <typename Value, typename Translator, typename Box, size_t Corner>
-class split_update_axis_data_for_corner
-{
- typedef typename split_axis_data<Box>::margin_type margin_type;
- typedef typename split_axis_data<Box>::overlap_type overlap_type;
- typedef typename split_axis_data<Box>::area_type area_type;
-
- BOOST_STATIC_ASSERT(Corner < 2);
-
-public:
- template <typename Elements>
- static inline void apply(
- split_axis_data<Box> & sad,
- Elements const& sorted_elements,
- size_t min_elems,
- size_t max_elems,
- Translator const& tr)
- {
- size_t median_index_last = max_elems - min_elems + 2;
- for ( size_t median_index = min_elems ; median_index < median_index_last ; ++median_index )
- {
- Box left_box = rtree::elements_box<Box>(sorted_elements.begin(), sorted_elements.begin() + median_index, tr);
- Box right_box = rtree::elements_box<Box>(sorted_elements.begin() + median_index, sorted_elements.end(), tr);
-
- margin_type margin = index::margin(left_box) + index::margin(right_box);
- overlap_type overlap = index::overlap(left_box, right_box);
- area_type area = index::area(left_box) + index::area(right_box);
-
- sad.update(Corner, median_index, left_box, right_box, margin, overlap, area);
- }
- }
-};
-
-// split data
-
-template <typename Elements, typename Box>
-struct split_data
-{
- 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())
- {}
-
- inline void update(
- size_t axis,
- size_t corner,
- size_t median_index,
- Box const& left_box,
- Box const& right_box,
- margin_type const& margins_sum,
- Elements const& distribution)
- {
- if ( margins_sum < smallest_margins_sum )
- {
- choosen_axis = axis;
- choosen_corner = corner;
- choosen_median_index = median_index;
- choosen_left_box = left_box;
- choosen_right_box = right_box;
- smallest_margins_sum = margins_sum;
- choosen_distribution = distribution;
- }
- }
-
- size_t choosen_axis;
- size_t choosen_corner;
- size_t choosen_median_index;
- Box choosen_left_box;
- Box choosen_right_box;
- margin_type smallest_margins_sum;
- Elements choosen_distribution;
-};
-
-// update split data for given axis and corner
-
-template <typename Value, typename Translator, typename Box, size_t AxisIndex, size_t Corner>
-class split_update_data_for_axis_and_corner
-{
- typedef typename split_axis_data<Box>::margin_type margin_type;
- typedef typename split_axis_data<Box>::overlap_type overlap_type;
- typedef typename split_axis_data<Box>::area_type area_type;
-
-public:
- template <typename Elements>
- static inline void apply(
- split_data<Elements, Box> & split_data,
- Elements & elements,
- size_t min_elems,
- size_t max_elems,
- Translator const& tr)
- {
- split_axis_data<Box> sad;
-
- elements_less<Elements, Translator, AxisIndex, Corner> less_min(tr);
- std::sort(elements.begin(), elements.end(), less_min);
-
- split_update_axis_data_for_corner<Value, Translator, Box, Corner>::
- apply(sad, elements, min_elems, max_elems, tr);
-
- split_data.update(
- AxisIndex,
- sad.choosen_corner,
- sad.choosen_median_index,
- sad.choosen_left_box,
- sad.choosen_right_box,
- sad.margins_sum,
- elements);
- }
-};
-
-// for each dimension and corner update split data
-
-template <typename Value, typename Translator, typename Box, size_t Dimension>
-struct split_update_data
-{
- BOOST_STATIC_ASSERT(0 < Dimension);
-
- template <typename Elements>
- static inline void apply(
- split_data<Elements, Box> & sd,
- Elements & elements,
- size_t min_elems,
- size_t max_elems,
- Translator const& tr)
- {
- split_update_data<Value, Translator, Box, Dimension - 1>::
- apply(sd, elements, min_elems, max_elems, tr);
-
- split_update_data_for_axis_and_corner<Value, Translator, Box, Dimension - 1, min_corner>::
- apply(sd, elements, min_elems, max_elems, tr);
- split_update_data_for_axis_and_corner<Value, Translator, Box, Dimension - 1, max_corner>::
- apply(sd, elements, min_elems, max_elems, tr);
- }
-};
-
-template <typename Value, typename Translator, typename Box>
-struct split_update_data<Value, Translator, Box, 1>
-{
- template <typename Elements>
- static inline void apply(
- split_data<Elements, Box> & sd,
- Elements & elements,
- size_t min_elems,
- size_t max_elems,
- Translator const& tr)
- {
- split_update_data_for_axis_and_corner<Value, Translator, Box, 0, min_corner>::
- apply(sd, elements, min_elems, max_elems, tr);
- split_update_data_for_axis_and_corner<Value, Translator, Box, 0, max_corner>::
- apply(sd, elements, min_elems, max_elems, tr);
- }
-};
-
-// split
-
-template <typename Value, typename Translator, typename Box>
-class split
-{
- 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;
-
- static const size_t dimension = index::traits::dimension<Box>::value;
-
-public:
- template <typename Node>
- static inline void apply(
- Node & n,
- internal_node *parent,
- size_t current_child_index,
- node *& root,
- size_t min_elems,
- size_t max_elems,
- Translator const& tr)
- {
- typedef typename rtree::elements_type<Node>::type elements_type;
- typedef typename elements_type::value_type element_type;
-
- elements_type & elements = rtree::elements_get(n);
-
- assert(elements.size() == max_elems + 1);
-
- // get split data
- split_data<elements_type, Box> sd;
- split_update_data<Value, Translator, Box, dimension>::
- apply(sd, elements, min_elems, max_elems, tr);
-
- assert(min_elems <= sd.choosen_median_index);
- assert(sd.choosen_median_index <= max_elems + 1 - min_elems);
-
- // create new node
- node * right_node = rtree::create_node(Node());
- elements_type & new_elems = rtree::elements_get(boost::get<Node>(*right_node));
-
- // update new node's elements
- new_elems.resize(max_elems + 1 - sd.choosen_median_index);
- std::copy(
- sd.choosen_distribution.begin() + sd.choosen_median_index,
- sd.choosen_distribution.end(),
- new_elems.begin());
-
- // update elements of the current node
- elements.resize(sd.choosen_median_index);
- std::copy(
- sd.choosen_distribution.begin(),
- sd.choosen_distribution.begin() + sd.choosen_median_index,
- elements.begin());
-
- // node is not the root
- if ( parent != 0 )
- {
- // update old node's box
- parent->children[current_child_index].first = sd.choosen_left_box;
- // 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));
-
- // create new root and add nodes
- node * new_root = rtree::create_node(internal_node());
-
- boost::get<internal_node>(*new_root).children.push_back(std::make_pair(sd.choosen_left_box, root));
- boost::get<internal_node>(*new_root).children.push_back(std::make_pair(sd.choosen_right_box, right_node));
-
- root = new_root;
- }
- }
-};
-
-}}} // namespace detail::rtree:rstar
-
-}}} // namespace boost::geometry::index
-
-#endif // BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_RSTAR_SPLIT_HPP
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-06-09 19:55:58 EDT (Thu, 09 Jun 2011)
@@ -54,6 +54,7 @@
, m_max_elems_per_node(max_elems_per_node)
, m_min_elems_per_node(min_elems_per_node)
, m_root(0)
+ , m_leafs_level(0)
, m_translator(translator)
{
if ( m_min_elems_per_node < 1 )
@@ -86,7 +87,7 @@
// TODO: awulkiew - assert for correct value
detail::rtree::visitors::insert<value_type, value_type, translator_type, box_type, tag_type>
- insert_v(m_root, value, m_min_elems_per_node, m_max_elems_per_node, m_translator);
+ insert_v(m_root, m_leafs_level, value, m_min_elems_per_node, m_max_elems_per_node, m_translator);
detail::rtree::apply_visitor(insert_v, *m_root);
@@ -99,7 +100,7 @@
assert(0 < m_values_count);
detail::rtree::visitors::remove<value_type, translator_type, box_type, tag_type>
- remove_v(m_root, value, m_min_elems_per_node, m_max_elems_per_node, m_translator);
+ remove_v(m_root, m_leafs_level, value, m_min_elems_per_node, m_max_elems_per_node, m_translator);
detail::rtree::apply_visitor(remove_v, *m_root);
@@ -144,6 +145,7 @@
size_t m_max_elems_per_node;
size_t m_min_elems_per_node;
node *m_root;
+ size_t m_leafs_level;
translator_type m_translator;
};
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-06-09 19:55:58 EDT (Thu, 09 Jun 2011)
@@ -74,21 +74,27 @@
typedef typename rtree::elements_type<leaf>::type elements_type;
elements_type const& elements = rtree::elements(n);
- if (elements.empty())
+ // non-root node
+ if (!m_is_root)
{
- result = false;
- return;
- }
-
- Box box_exp;
- geometry::convert(m_tr(elements.front()), box_exp);
- for(typename elements_type::const_iterator it = elements.begin() + 1;
- it != elements.end() ; ++it)
- {
- geometry::expand(box_exp, m_tr(*it));
- }
-
- result = m_is_root || geometry::equals(box_exp, m_box);
+ if ( elements.empty() )
+ {
+ result = false;
+ return;
+ }
+
+ Box box_exp;
+ geometry::convert(m_tr(elements.front()), box_exp);
+ for(typename elements_type::const_iterator it = elements.begin() + 1;
+ it != elements.end() ; ++it)
+ {
+ geometry::expand(box_exp, m_tr(*it));
+ }
+
+ result = geometry::equals(box_exp, m_box);
+ }
+ else
+ result = true;
}
bool result;
Added: sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/are_levels_ok.hpp
==============================================================================
--- (empty file)
+++ sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/are_levels_ok.hpp 2011-06-09 19:55:58 EDT (Thu, 09 Jun 2011)
@@ -0,0 +1,105 @@
+// Boost.Geometry (aka GGL, Generic Geometry Library)
+//
+// Boost.Index - R-tree levels checking visitor
+//
+// 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_VISITORS_ARE_LEVELS_OK_HPP
+#define BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_VISITORS_ARE_LEVELS_OK_HPP
+
+#include <boost/geometry/extensions/index/rtree/node.hpp>
+
+namespace boost { namespace geometry { namespace index {
+
+namespace detail { namespace rtree { namespace visitors {
+
+template <typename Value, typename Translator, typename Box, typename Tag>
+class are_levels_ok : public rtree::visitor<Value, Box, Tag, true>::type
+{
+ typedef typename rtree::internal_node<Value, Box, Tag>::type internal_node;
+ typedef typename rtree::leaf<Value, Box, Tag>::type leaf;
+
+public:
+ inline are_levels_ok(Translator const& tr)
+ : result(true), m_tr(tr), m_leafs_level(std::numeric_limits<size_t>::max()), m_current_level(0)
+ {}
+
+ inline void operator()(internal_node const& n)
+ {
+ typedef typename rtree::elements_type<internal_node>::type elements_type;
+ elements_type const& elements = rtree::elements(n);
+
+ if (elements.empty())
+ {
+ result = false;
+ return;
+ }
+
+ size_t current_level_backup = m_current_level;
+ ++m_current_level;
+
+ for ( typename elements_type::const_iterator it = elements.begin();
+ it != elements.end() ; ++it)
+ {
+ rtree::apply_visitor(*this, *it->second);
+
+ if ( result == false )
+ return;
+ }
+
+ m_current_level = current_level_backup;
+ }
+
+ inline void operator()(leaf const& n)
+ {
+ typedef typename rtree::elements_type<leaf>::type elements_type;
+ elements_type const& elements = rtree::elements(n);
+
+ // empty leaf in non-root node
+ if (0 < m_current_level && elements.empty())
+ {
+ result = false;
+ return;
+ }
+
+ if ( m_leafs_level == std::numeric_limits<size_t>::max() )
+ {
+ m_leafs_level = m_current_level;
+ }
+ else if ( m_leafs_level != m_current_level )
+ {
+ result = false;
+ }
+ }
+
+ bool result;
+
+private:
+ Translator const& m_tr;
+ size_t m_leafs_level;
+ size_t m_current_level;
+};
+
+}}} // namespace detail::rtree::visitors
+
+template <typename Value, typename Translator, typename Tag>
+bool are_levels_ok(rtree<Value, Translator, Tag> const& tree)
+{
+ typedef rtree<Value, Translator, Tag> rt;
+ detail::rtree::visitors::are_levels_ok<
+ typename rt::value_type,
+ typename rt::translator_type,
+ typename rt::box_type,
+ typename rt::tag_type> v(tree.get_translator());
+
+ tree.apply_visitor(v);
+
+ return v.result;
+}
+
+}}} // namespace boost::geometry::index
+
+#endif // BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_VISITORS_ARE_LEVELS_OK_HPP
Modified: sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/insert.hpp
==============================================================================
--- sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/insert.hpp (original)
+++ sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/insert.hpp 2011-06-09 19:55:58 EDT (Thu, 09 Jun 2011)
@@ -94,6 +94,7 @@
internal_node *parent,
size_t current_child_index,
node *& root,
+ size_t & leafs_level,
size_t min_elems,
size_t max_elems,
Translator const& tr)
@@ -111,7 +112,7 @@
assert(min_elems <= rtree::elements(n).size() && rtree::elements(n).size() <= max_elems);
assert(min_elems <= rtree::elements(n2).size() && rtree::elements(n2).size() <= max_elems);
- // node is not the root
+ // node is not the root - just add the new node
if ( parent != 0 )
{
// update old node's box
@@ -119,7 +120,7 @@
// add new node to the parent's children
rtree::elements(*parent).push_back(std::make_pair(box2, second_node));
}
- // node is the root
+ // node is the root - add level
else
{
assert(&n == rtree::get<Node>(root));
@@ -131,32 +132,11 @@
rtree::elements(rtree::get<internal_node>(*new_root)).push_back(std::make_pair(box2, second_node));
root = new_root;
+ ++leafs_level;
}
}
};
-// Default overflow treatment algorithm
-template <typename Value, typename Translator, typename Box, typename Tag>
-struct overflow_treatment
-{
- typedef typename rtree::node<Value, Box, Tag>::type node;
- typedef typename rtree::internal_node<Value, Box, Tag>::type internal_node;
- typedef typename rtree::leaf<Value, Box, Tag>::type leaf;
-
- template <typename Node>
- static inline void apply(
- Node & n,
- internal_node *parent,
- size_t current_child_index,
- node *& root,
- size_t min_elems,
- size_t max_elems,
- Translator const& tr)
- {
- split<Value, Translator, Box, Tag>::apply(n, parent, current_child_index, root, min_elems, max_elems, tr);
- }
-};
-
// Default insert visitor
template <typename Element, typename Value, typename Translator, typename Box, typename Tag>
class insert : public rtree::visitor<Value, Box, Tag, false>::type
@@ -167,22 +147,27 @@
typedef typename rtree::leaf<Value, Box, Tag>::type leaf;
inline insert(node* & root,
+ size_t & leafs_level,
Element const& element,
size_t min_elements,
size_t max_elements,
Translator const& t,
- size_t level = std::numeric_limits<size_t>::max()
+ 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_level(level)
+ , m_relative_level(relative_level)
+ , m_level(leafs_level - relative_level)
, m_root_node(root)
+ , m_leafs_level(leafs_level)
, m_parent(0)
, m_current_child_index(0)
, m_current_level(0)
{
+ assert(m_relative_level <= leafs_level);
+ assert(m_level <= m_leafs_level);
// TODO
// assert - check if Box is correct
}
@@ -209,11 +194,16 @@
template <typename Node>
inline void post_traverse(Node &n)
{
+ // if node isn't a root check if parent and current_child_index isn't corrupted
+ assert(0 == m_parent || &n == rtree::get<Node>(rtree::elements(*m_parent)[m_current_child_index].second));
+
// handle overflow
if ( m_max_elems_per_node < rtree::elements(n).size() )
{
- detail::overflow_treatment<Value, Translator, Box, Tag>::
- apply(n, m_parent, m_current_child_index, m_root_node, m_min_elems_per_node, m_max_elems_per_node, m_tr);
+ split<Value, Translator, Box, Tag>::apply(
+ n, m_parent, m_current_child_index,
+ m_root_node, m_leafs_level,
+ m_min_elems_per_node, m_max_elems_per_node, m_tr);
}
}
@@ -243,9 +233,11 @@
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;
node* & m_root_node;
+ size_t & m_leafs_level;
// traversing input parameters
internal_node *m_parent;
@@ -265,17 +257,20 @@
typedef typename base::leaf leaf;
inline insert(node* & root,
+ size_t & leafs_level,
Element const& element,
size_t min_elements,
size_t max_elements,
Translator const& tr,
- size_t level = std::numeric_limits<size_t>::max()
+ size_t relative_level = 0
)
- : base(root, element, min_elements, max_elements, tr, level)
+ : base(root, leafs_level, element, min_elements, max_elements, tr, relative_level)
{}
inline void operator()(internal_node & n)
{
+ assert(base::m_current_level < base::m_leafs_level);
+
if ( base::m_current_level < base::m_level )
{
// next traversing step
@@ -308,17 +303,19 @@
typedef typename base::leaf leaf;
inline insert(node* & root,
+ size_t & leafs_level,
Value const& v,
size_t min_elements,
size_t max_elements,
Translator const& t,
- size_t level = std::numeric_limits<size_t>::max()
+ size_t relative_level = 0
)
- : base(root, v, min_elements, max_elements, t, level)
+ : base(root, leafs_level, v, min_elements, max_elements, t, relative_level)
{}
inline void operator()(internal_node & n)
{
+ assert(base::m_current_level < base::m_leafs_level);
assert(base::m_current_level < base::m_level);
// next traversing step
@@ -329,6 +326,7 @@
inline void operator()(leaf & n)
{
+ assert(base::m_current_level == base::m_leafs_level);
assert( base::m_level == base::m_current_level ||
base::m_level == std::numeric_limits<size_t>::max() );
Modified: sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/remove.hpp
==============================================================================
--- sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/remove.hpp (original)
+++ sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/remove.hpp 2011-06-09 19:55:58 EDT (Thu, 09 Jun 2011)
@@ -29,12 +29,18 @@
typedef typename rtree::leaf<Value, Box, Tag>::type leaf;
public:
- inline explicit remove(node* & root, Value const& v, size_t min_elements, size_t max_elements, Translator const& t)
+ 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)
, m_parent(0)
, m_current_child_index(0)
@@ -76,8 +82,8 @@
{
element_iterator underfl_el_it = elements.begin() + child_node_index;
- // move node to the container
- m_underflowed_nodes.push_back(std::make_pair(m_current_level + 1, underfl_el_it->second));
+ // move node to the container - store node's relative level as well
+ m_underflowed_nodes.push_back(std::make_pair(m_leafs_level - m_current_level, underfl_el_it->second));
elements.erase(underfl_el_it);
// calc underflow
@@ -87,8 +93,9 @@
// n is not root - adjust aabb
if ( 0 != m_parent )
{
- // test underflow state should be ok here
+ // 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);
rtree::elements(*m_parent)[m_current_child_index].first
@@ -120,6 +127,7 @@
if ( rtree::elements(n).size() == 1 )
{
m_root_node = rtree::elements(n)[0].second;
+ --m_leafs_level;
}
}
}
@@ -178,7 +186,7 @@
}
template <typename Node>
- void reinsert_elements(Node &n, size_t level)
+ void reinsert_elements(Node &n, size_t node_relative_level)
{
typedef typename rtree::elements_type<Node>::type elements_type;
elements_type & elements = rtree::elements(n);
@@ -187,11 +195,12 @@
{
visitors::insert<typename elements_type::value_type, Value, Translator, Box, Tag> insert_v(
m_root_node,
+ m_leafs_level,
*it,
m_min_elems_per_node,
m_max_elems_per_node,
m_tr,
- level);
+ node_relative_level - 1);
rtree::apply_visitor(insert_v, *m_root_node);
}
@@ -203,6 +212,7 @@
const size_t m_max_elems_per_node;
node* & m_root_node;
+ size_t & m_leafs_level;
bool m_is_value_removed;
std::vector< std::pair<size_t, node*> > m_underflowed_nodes;
Modified: sandbox-branches/geometry/index_080_new/tests/additional_glut_vis.cpp
==============================================================================
--- sandbox-branches/geometry/index_080_new/tests/additional_glut_vis.cpp (original)
+++ sandbox-branches/geometry/index_080_new/tests/additional_glut_vis.cpp 2011-06-09 19:55:58 EDT (Thu, 09 Jun 2011)
@@ -9,16 +9,21 @@
#include <gl/glut.h>
+//#define BOOST_GEOMETRY_INDEX_USE_VARIANT_NODES
#include <boost/geometry/extensions/index/rtree/rtree.hpp>
#include <boost/geometry/extensions/index/rtree/visitors/gl_draw.hpp>
#include <boost/geometry/extensions/index/rtree/visitors/print.hpp>
#include <boost/geometry/extensions/index/rtree/visitors/are_boxes_ok.hpp>
+#include <boost/geometry/extensions/index/rtree/visitors/are_levels_ok.hpp>
typedef boost::geometry::model::point<float, 2, boost::geometry::cs::cartesian> P;
typedef boost::geometry::model::box<P> B;
//boost::geometry::index::rtree<B> t(2, 1);
-boost::geometry::index::rtree<B, boost::geometry::index::default_parameter, boost::geometry::index::quadratic_tag> t(4, 2);
+boost::geometry::index::rtree<
+ B,
+ boost::geometry::index::default_parameter,
+ boost::geometry::index::rstar_tag> t(4, 2);
std::vector<B> vect;
void render_scene(void)
@@ -61,13 +66,14 @@
boost::geometry::index::insert(t, b);
vect.push_back(b);
- /*std::cout << t << "\n\n";
+ std::cout << t << "\n\n";
std::cout << "inserted: ";
boost::geometry::index::detail::rtree::visitors::detail::print_indexable(std::cout, b);
std::cout << '\n';
- std::cout << ( boost::geometry::index::are_boxes_ok(t) ? "boxes OK" : "WRONG BOXES!" );
- std::cout << "\n\n\n";*/
+ std::cout << ( boost::geometry::index::are_boxes_ok(t) ? "boxes OK\n" : "WRONG BOXES!\n" );
+ std::cout << ( boost::geometry::index::are_levels_ok(t) ? "levels OK\n" : "WRONG LEVELS!\n" );
+ std::cout << "\n\n";
glutPostRedisplay();
}
@@ -82,12 +88,13 @@
boost::geometry::index::remove(t, b);
vect.erase(vect.begin() + i);
- /*std::cout << '\n' << t << "\n\n";
+ std::cout << '\n' << t << "\n\n";
std::cout << "removed: ";
boost::geometry::index::detail::rtree::visitors::detail::print_indexable(std::cout, b);
std::cout << '\n';
- std::cout << ( boost::geometry::index::are_boxes_ok(t) ? "boxes OK" : "WRONG BOXES!" );
- std::cout << "\n\n\n";*/
+ std::cout << ( boost::geometry::index::are_boxes_ok(t) ? "boxes OK\n" : "WRONG BOXES!\n" );
+ std::cout << ( boost::geometry::index::are_levels_ok(t) ? "levels OK\n" : "WRONG LEVELS!\n" );
+ std::cout << "\n\n";
glutPostRedisplay();
}
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-06-09 19:55:58 EDT (Thu, 09 Jun 2011)
@@ -11,6 +11,7 @@
#include <boost/geometry/extensions/index/rtree/rtree.hpp>
#include <boost/geometry/extensions/index/rtree/visitors/are_boxes_ok.hpp>
+#include <boost/geometry/extensions/index/rtree/visitors/are_levels_ok.hpp>
#include <iostream>
#include <fstream>
@@ -28,9 +29,9 @@
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::default_parameter, bgi::linear_tag> RT;
+ //typedef bgi::rtree<std::pair<B, size_t>, bgi::default_parameter, bgi::linear_tag> RT;
//typedef bgi::rtree<std::pair<B, size_t>, bgi::default_parameter, bgi::quadratic_tag> RT;
- //typedef bgi::rtree<std::pair<B, size_t>, bgi::default_parameter, bgi::rstar_tag> RT;
+ typedef bgi::rtree<std::pair<B, size_t>, bgi::default_parameter, bgi::rstar_tag> RT;
// load config file
std::ifstream file_cfg("config.txt");
@@ -89,7 +90,7 @@
else
{
boost::mt19937 rng;
- float max_val = values_count / 2;
+ float max_val = static_cast<float>(values_count / 2);
boost::uniform_real<float> range(-max_val, max_val);
boost::variate_generator<boost::mt19937&, boost::uniform_real<float> > rnd(rng, range);
@@ -114,6 +115,25 @@
float y = coords[i].second;
B b(P(x - 0.5f, y - 0.5f), P(x + 0.5f, y + 0.5f));
+ //if ( 341700 <= i )
+ // std::cout << i << "\n";
+
+ // Czy mozliwe, ze w czasie powtornego reinserta
+ // nagle drzewo sie powieksza o jeden poziom?
+ // Tak, drzewo sie rozrasta, powinno sie wstawiac w poziomie liczac od lisci
+ // TODO: relative_level zamiast level
+
+ // TODO: asserty w operator(leaf)
+ // current_level == leaf_level
+
+ // Swoja droga to dziwne ze przy drzewie 4,2
+ // dzieje sie to samo dopiero dla obiektow o indeksie 300k a nie wczesniej
+ // Dlaczego?
+ // Przy 32 obiektach powtornie wstawianych jest 9 a przy 4 tylko 1
+
+ // TODO: Zrobic kolejnego visitora sprawdzajacego czy odpowiednie wezly zostaly wstawione w dobrym miejscu
+ // Np sprawdzajacego czy wszystkie liscie sa na tym samym poziomie
+
t.insert(std::make_pair(b, i));
}
std::cout << "time: " << tim.elapsed() << "s\n";
@@ -124,6 +144,10 @@
std::cout << "BOXES OK\n";
else
std::cout << "WRONG BOXES\n";
+ if ( bgi::are_levels_ok(t) )
+ std::cout << "LEVELS OK\n";
+ else
+ std::cout << "WRONG LEVELS\n";
// searching test
{
@@ -157,11 +181,15 @@
std::cout << "time: " << tim.elapsed() << "s\n";
}
- // check
- if ( bgi::are_boxes_ok(t) )
- std::cout << "BOXES OK\n";
- else
- std::cout << "WRONG BOXES\n";
+ // check
+ if ( bgi::are_boxes_ok(t) )
+ std::cout << "BOXES OK\n";
+ else
+ std::cout << "WRONG BOXES\n";
+ if ( bgi::are_levels_ok(t) )
+ std::cout << "LEVELS OK\n";
+ else
+ std::cout << "WRONG LEVELS\n";
// searching test
{
@@ -184,7 +212,7 @@
{
std::cout << "inserting time test...\n";
tim.restart();
- for (size_t i = 0 ; i < values_count / 2 ; ++i )
+ for (size_t i = 0 ; i < remove_count ; ++i )
{
float x = coords[i].first;
float y = coords[i].second;
@@ -195,11 +223,15 @@
std::cout << "time: " << tim.elapsed() << "s\n";
}
- // test
- if ( bgi::are_boxes_ok(t) )
- std::cout << "BOXES OK\n";
- else
- std::cout << "WRONG BOXES\n";
+ // check
+ if ( bgi::are_boxes_ok(t) )
+ std::cout << "BOXES OK\n";
+ else
+ std::cout << "WRONG BOXES\n";
+ if ( bgi::are_levels_ok(t) )
+ std::cout << "LEVELS OK\n";
+ else
+ std::cout << "WRONG LEVELS\n";
// searching test
{