|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r71726 - in sandbox-branches/geometry/index_080_new: boost/geometry/extensions/index/algorithms boost/geometry/extensions/index/rtree boost/geometry/extensions/index/rtree/linear boost/geometry/extensions/index/rtree/quadratic boost/geometry/extensions/index/rtree/rstar boost/geometry/extensions/index/rtree/visitors boost/geometry/extensions/index/translator tests
From: adam.wulkiewicz_at_[hidden]
Date: 2011-05-04 17:33:17
Author: awulkiew
Date: 2011-05-04 17:33:15 EDT (Wed, 04 May 2011)
New Revision: 71726
URL: http://svn.boost.org/trac/boost/changeset/71726
Log:
remove algorithm added + some other changes
Added:
sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/quadratic/
sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/quadratic/quadratic.hpp (contents, props changed)
sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/quadratic/redistribute_elements.hpp (contents, props changed)
sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rstar/insert.hpp
- copied, changed from r71544, /sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rstar/insert_impl.hpp
Removed:
sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rstar/insert_impl.hpp
Text files modified:
sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/algorithms/area.hpp | 42 ++
sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/linear/redistribute_elements.hpp | 110 ++++----
sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rstar/choose_next_node.hpp | 10
sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rstar/insert.hpp | 521 +++++++++++++++++----------------------
sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rstar/rstar.hpp | 2
sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rtree.hpp | 47 +++
sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/insert.hpp | 179 +++++++++++--
sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/remove.hpp | 191 ++++++++++++++
sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/translator/def.hpp | 16
sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/translator/helpers.hpp | 104 +++---
sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/translator/index.hpp | 6
sandbox-branches/geometry/index_080_new/tests/additional_glut_vis.cpp | 27 +
sandbox-branches/geometry/index_080_new/tests/additional_sizes_and_times.cpp | 126 ++++++---
sandbox-branches/geometry/index_080_new/tests/main.cpp | 41 ++
14 files changed, 901 insertions(+), 521 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-05-04 17:33:15 EDT (Wed, 04 May 2011)
@@ -12,11 +12,11 @@
namespace boost { namespace geometry { namespace index {
-template <typename Box>
+template <typename Indexable>
struct default_area_result
{
typedef typename select_most_precise<
- typename coordinate_type<Box>::type,
+ typename traits::coordinate_type<Indexable>::type,
long double
>::type type;
};
@@ -32,7 +32,7 @@
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) );
+ ( index::get<max_corner, CurrentDimension - 1>(b) - index::get<min_corner, CurrentDimension - 1>(b) );
}
};
@@ -41,16 +41,44 @@
{
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);
+ return index::get<max_corner, 0>(b) - index::get<min_corner, 0>(b);
}
};
} // namespace detail
-template <typename Box>
-typename default_area_result<Box>::type area(Box const& b)
+namespace dispatch {
+
+template <typename Indexable, typename Tag>
+struct area
+{
+ // TODO: awulkiew - static assert?
+};
+
+template <typename Indexable>
+struct area<Indexable, point_tag>
+{
+ static typename default_area_result<Indexable>::type apply(Indexable const&)
+ {
+ return 0;
+ }
+};
+
+template <typename Indexable>
+struct area<Indexable, box_tag>
+{
+ static typename default_area_result<Indexable>::type apply(Indexable const& b)
+ {
+ return detail::area_for_each_dimension<Indexable, traits::dimension<Indexable>::value>::apply(b);
+ }
+};
+
+} // namespace dispatch
+
+template <typename Indexable>
+typename default_area_result<Indexable>::type area(Indexable const& b)
{
- return detail::area_for_each_dimension<Box, traits::dimension<Box>::value>::apply(b);
+ return dispatch::area<Indexable, typename index::traits::tag<Indexable>::type>::apply(b);
}
}}} // namespace boost::geometry::index
Modified: sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/linear/redistribute_elements.hpp
==============================================================================
--- sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/linear/redistribute_elements.hpp (original)
+++ sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/linear/redistribute_elements.hpp 2011-05-04 17:33:15 EDT (Wed, 04 May 2011)
@@ -30,6 +30,10 @@
namespace linear {
+// TODO: awulkiew - there are loops inside find_greatest_normalized_separation::apply()
+// iteration is done for each DimensionIndex.
+// Separations and seeds for all DimensionIndex(es) could be calculated at once, stored, then the greatest would be choosen.
+
// 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>
@@ -96,7 +100,7 @@
};
template <typename Elements, typename Translator, size_t DimensionIndex>
-struct choose_axis_impl
+struct pick_seeds_impl
{
BOOST_STATIC_ASSERT(0 < DimensionIndex);
@@ -106,30 +110,28 @@
static inline void apply(Elements const& elements,
Translator const& tr,
- size_t & axis,
coordinate_type & separation,
size_t & seed1,
size_t & seed2)
{
- choose_axis_impl<Elements, Translator, DimensionIndex - 1>::apply(elements, tr, axis, separation, seed1, seed2);
+ pick_seeds_impl<Elements, 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);
- // in the old implementation different operator was used: <=
+ // in the old implementation different operator was used: <= (y axis prefered)
if ( separation < current_separation )
{
separation = current_separation;
seed1 = s1;
seed2 = s2;
- axis = DimensionIndex - 1;
}
}
};
template <typename Elements, typename Translator>
-struct choose_axis_impl<Elements, Translator, 1>
+struct pick_seeds_impl<Elements, Translator, 1>
{
typedef typename Elements::value_type element_type;
typedef typename rtree::element_indexable_type<element_type, Translator>::type indexable_type;
@@ -137,36 +139,32 @@
static inline void apply(Elements const& elements,
Translator const& tr,
- size_t & axis,
coordinate_type & separation,
size_t & seed1,
size_t & seed2)
{
find_greatest_normalized_separation<Elements, Translator, 0>::apply(elements, tr, separation, seed1, seed2);
- axis = 0;
}
};
// from void linear_pick_seeds(node_pointer const& n, unsigned int &seed1, unsigned int &seed2) const
template <typename Elements, typename Translator>
-struct choose_axis
+struct pick_seeds
{
typedef typename Elements::value_type element_type;
typedef typename rtree::element_indexable_type<element_type, Translator>::type indexable_type;
typedef typename index::traits::coordinate_type<indexable_type>::type coordinate_type;
-
+
static const size_t dimension = index::traits::dimension<indexable_type>::value;
- static inline size_t apply(Elements const& elements,
- Translator const& tr,
- size_t & seed1,
- size_t & seed2)
+ static inline void apply(Elements const& elements,
+ Translator const& tr,
+ size_t & seed1,
+ size_t & seed2)
{
- size_t axis = 0;
coordinate_type separation = 0;
- choose_axis_impl<Elements, Translator, dimension>::apply(elements, tr, axis, separation, seed1, seed2);
- return axis;
+ pick_seeds_impl<Elements, Translator, dimension>::apply(elements, tr, separation, seed1, seed2);
}
};
@@ -205,7 +203,7 @@
// calculate initial seeds
size_t seed1 = 0;
size_t seed2 = 0;
- linear::choose_axis<elements_type, Translator>::apply(elements_copy, tr, seed1, seed2);
+ linear::pick_seeds<elements_type, Translator>::apply(elements_copy, tr, seed1, seed2);
// prepare nodes' elements containers
elements_type & elements1 = rtree::elements_get(n);
@@ -236,59 +234,45 @@
element_type const& elem = elements_copy[i];
indexable_type const& indexable = rtree::element_indexable(elem, tr);
- // TODO: awulkiew - is this needed?
+ // 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 )
{
elements1.push_back(elem);
geometry::expand(box1, indexable);
area1 = index::area(box1);
- continue;
}
- if ( elements2.size() + remaining == min_elems )
+ else if ( elements2.size() + remaining == min_elems )
{
elements2.push_back(elem);
geometry::expand(box2, indexable);
area2 = index::area(box2);
- continue;
}
+ // choose better node and insert element
+ else
+ {
+ assert(0 < remaining);
+ remaining--;
- assert(0 < remaining);
- remaining--;
-
- // calculate enlarged boxes and areas
- Box enlarged_box1(box1);
- Box enlarged_box2(box2);
- geometry::expand(enlarged_box1, indexable);
- geometry::expand(enlarged_box2, indexable);
- area_type enlarged_area1 = index::area(enlarged_box1);
- area_type enlarged_area2 = index::area(enlarged_box2);
+ // calculate enlarged boxes and areas
+ Box enlarged_box1(box1);
+ Box enlarged_box2(box2);
+ geometry::expand(enlarged_box1, indexable);
+ geometry::expand(enlarged_box2, indexable);
+ area_type enlarged_area1 = index::area(enlarged_box1);
+ area_type enlarged_area2 = index::area(enlarged_box2);
- area_type areas_diff1 = enlarged_area1 - area1;
- area_type areas_diff2 = enlarged_area2 - area2;
+ area_type areas_diff1 = enlarged_area1 - area1;
+ area_type areas_diff2 = enlarged_area2 - area2;
- // choose group which box area have to be enlarged least
- if ( areas_diff1 < areas_diff2 )
- {
- elements1.push_back(elem);
- box1 = enlarged_box1;
- area1 = enlarged_area1;
- }
- else if ( areas_diff2 < areas_diff1 )
- {
- elements2.push_back(elem);
- box2 = enlarged_box2;
- area2 = enlarged_area2;
- }
- else
- {
- // choose group which box has smaller area
- if ( area1 < area2 )
+ // choose group which box area have to be enlarged least
+ if ( areas_diff1 < areas_diff2 )
{
elements1.push_back(elem);
box1 = enlarged_box1;
area1 = enlarged_area1;
}
- else if ( area2 < area1 )
+ else if ( areas_diff2 < areas_diff1 )
{
elements2.push_back(elem);
box2 = enlarged_box2;
@@ -296,19 +280,35 @@
}
else
{
- // choose group with fewer elements
- if ( elements1.size() <= elements2.size() )
+ // choose group which box has smaller area
+ if ( area1 < area2 )
{
elements1.push_back(elem);
box1 = enlarged_box1;
area1 = enlarged_area1;
}
- else
+ else if ( area2 < area1 )
{
elements2.push_back(elem);
box2 = enlarged_box2;
area2 = enlarged_area2;
}
+ else
+ {
+ // choose group with fewer elements
+ if ( elements1.size() <= elements2.size() )
+ {
+ elements1.push_back(elem);
+ box1 = enlarged_box1;
+ area1 = enlarged_area1;
+ }
+ else
+ {
+ elements2.push_back(elem);
+ box2 = enlarged_box2;
+ area2 = enlarged_area2;
+ }
+ }
}
}
}
Added: sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/quadratic/quadratic.hpp
==============================================================================
--- (empty file)
+++ sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/quadratic/quadratic.hpp 2011-05-04 17:33:15 EDT (Wed, 04 May 2011)
@@ -0,0 +1,21 @@
+// Boost.Geometry (aka GGL, Generic Geometry Library)
+//
+// Boost.Index - R-tree
+//
+// 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_QUADRATIC_QUADRATIC_HPP
+#define BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_QUADRATIC_QUADRATIC_HPP
+
+namespace boost { namespace geometry { namespace index {
+
+struct quadratic_tag {};
+
+}}} // namespace boost::geometry::index
+
+#include <boost/geometry/extensions/index/rtree/quadratic/redistribute_elements.hpp>
+
+#endif // BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_QUADRATIC_QUADRATIC_HPP
Added: sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/quadratic/redistribute_elements.hpp
==============================================================================
--- (empty file)
+++ sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/quadratic/redistribute_elements.hpp 2011-05-04 17:33:15 EDT (Wed, 04 May 2011)
@@ -0,0 +1,87 @@
+// Boost.Geometry (aka GGL, Generic Geometry Library)
+//
+// Boost.Index - R-tree quadratic 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_QUADRATIC_REDISTRIBUTE_ELEMENTS_HPP
+#define BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_QUADRATIC_REDISTRIBUTE_ELEMENTS_HPP
+
+#include <algorithm>
+
+#include <boost/tuple/tuple.hpp>
+
+#include <boost/geometry/extensions/index/algorithms/area.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 visitors {
+
+namespace detail {
+
+namespace quadratic {
+
+template <typename Elements, typename Translator, typename Box>
+struct pick_seeds
+{
+ typedef typename Elements::value_type element_type;
+ typedef typename rtree::element_indexable_type<element_type, Translator>::type indexable_type;
+ typedef typename index::traits::coordinate_type<indexable_type>::type coordinate_type;
+ typedef Box box_type;
+ typedef typename index::default_area_result<box_type>::type area_type;
+
+ static inline void apply(Elements const& elements,
+ Translator const& tr,
+ size_t & seed1,
+ size_t & seed2)
+ {
+ size_t elements_count = elements.size();
+
+ assert(2 <= elements_count);
+
+ seed1 = 0;
+ seed2 = 1;
+ area_type greatest_free_area = 0;
+ for ( size_t i = 0 ; i < elements_count ; ++i )
+ {
+ for ( size_t j = i + 1 ; j < elements_count ; ++j )
+ {
+ indexable_type & ind1 = rtree::element_indexable(elements[i], tr);
+ indexable_type & ind2 = rtree::element_indexable(elements[j], tr);
+
+ box_type enlarged_box;
+ geometry::convert(ind1);
+ geometry::expand(enlarged_box, ind2);
+
+ area_type free_area = index::area(enlarged_box) - index::area(ind1) - index::area(ind2);
+
+ if ( greatest_free_area < free_area )
+ {
+ greatest_free_area = free_area;
+ seed1 = i;
+ seed2 = j;
+ }
+ }
+ }
+ }
+};
+
+} // namespace quadratic
+
+// TODO: awulkiew - redistribute
+
+} // namespace detail
+
+}}} // namespace detail::rtree::visitors
+
+}}} // namespace boost::geometry::index
+
+#endif // BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_QUADRATIC_REDISTRIBUTE_ELEMENTS_HPP
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-05-04 17:33:15 EDT (Wed, 04 May 2011)
@@ -23,10 +23,12 @@
namespace boost { namespace geometry { namespace index {
-namespace detail { namespace rtree { namespace rstar {
+namespace detail { namespace rtree { namespace visitors {
+
+namespace detail {
template <typename Value, typename Box>
-class choose_next_node
+class choose_next_node<Value, Box, rstar_tag>
{
typedef typename rtree::node<Value, Box, rstar_tag>::type node;
typedef typename rtree::internal_node<Value, Box, rstar_tag>::type internal_node;
@@ -235,7 +237,9 @@
//};
};
-}}} // namespace detail::rtree:rstar
+} // namespace detail
+
+}}} // namespace detail::rtree::visitors
}}} // namespace boost::geometry::index
Copied: sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rstar/insert.hpp (from r71544, /sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rstar/insert_impl.hpp)
==============================================================================
--- /sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rstar/insert_impl.hpp (original)
+++ sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rstar/insert.hpp 2011-05-04 17:33:15 EDT (Wed, 04 May 2011)
@@ -1,14 +1,14 @@
// Boost.Geometry (aka GGL, Generic Geometry Library)
//
-// Boost.Index - R*-tree reinsert algorithm implementation
+// Boost.Index - R*-tree insert 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
+#ifndef BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_RSTAR_INSERT_HPP
+#define BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_RSTAR_INSERT_HPP
#include <algorithm>
@@ -34,305 +34,228 @@
namespace boost { namespace geometry { namespace index {
-namespace detail { namespace rtree { namespace rstar {
+namespace detail { namespace rtree { namespace visitors {
-template <typename Value, typename Translator, typename Box, typename Element>
-class insert_base;
+namespace detail {
-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;
- typedef typename base::node node;
- typedef typename base::internal_node internal_node;
- typedef typename base::leaf leaf;
-
-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 ( base::m_current_level < base::m_level )
- {
- // next traversing step
- base::traverse(*this, n);
- }
- else
- {
- assert( base::m_level == base::m_current_level );
-
- // push new child node
- n.children.push_back(base::m_element);
- }
-
- if ( base::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;
- typedef typename base::node node;
- typedef typename base::internal_node internal_node;
- typedef typename base::leaf leaf;
-
-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(base::m_current_level < base::m_level);
-
- // next traversing step
- base::traverse(*this, n);
-
- if ( base::m_max_elems_per_node < n.children.size() )
- base::overflow_treatment(n);
- }
-
- inline void operator()(leaf & n)
- {
- assert( base::m_level == base::m_current_level ||
- base::m_level == std::numeric_limits<size_t>::max() );
-
- n.values.push_back(base::m_element);
-
- if ( base::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));
-
- //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 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;
-};
+//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 detail
-}}} // namespace detail::rtree::rstar
+}}} // namespace detail::rtree::visitors
}}} // namespace boost::geometry::index
-#endif // BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_RSTAR_INSERT_IMPL_HPP
+#endif // BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_RSTAR_INSERT_HPP
Deleted: sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rstar/insert_impl.hpp
==============================================================================
--- sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rstar/insert_impl.hpp 2011-05-04 17:33:15 EDT (Wed, 04 May 2011)
+++ (empty file)
@@ -1,338 +0,0 @@
-// 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>
-
-//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 {
-
-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;
- typedef typename base::node node;
- typedef typename base::internal_node internal_node;
- typedef typename base::leaf leaf;
-
-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 ( base::m_current_level < base::m_level )
- {
- // next traversing step
- base::traverse(*this, n);
- }
- else
- {
- assert( base::m_level == base::m_current_level );
-
- // push new child node
- n.children.push_back(base::m_element);
- }
-
- if ( base::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;
- typedef typename base::node node;
- typedef typename base::internal_node internal_node;
- typedef typename base::leaf leaf;
-
-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(base::m_current_level < base::m_level);
-
- // next traversing step
- base::traverse(*this, n);
-
- if ( base::m_max_elems_per_node < n.children.size() )
- base::overflow_treatment(n);
- }
-
- inline void operator()(leaf & n)
- {
- assert( base::m_level == base::m_current_level ||
- base::m_level == std::numeric_limits<size_t>::max() );
-
- n.values.push_back(base::m_element);
-
- if ( base::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));
-
- //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 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 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/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-05-04 17:33:15 EDT (Wed, 04 May 2011)
@@ -16,6 +16,8 @@
}}} // namespace boost::geometry::index
+#include <boost/geometry/extensions/index/rtree/rstar/choose_next_node.hpp>
+
#include <boost/geometry/extensions/index/rtree/rstar/insert.hpp>
#endif // BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_RSTAR_RSTAR_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-05-04 17:33:15 EDT (Wed, 04 May 2011)
@@ -17,9 +17,14 @@
#include <boost/geometry/extensions/index/rtree/visitors/find.hpp>
#include <boost/geometry/extensions/index/rtree/visitors/destroy.hpp>
+#include <boost/geometry/extensions/index/rtree/visitors/insert.hpp>
+#include <boost/geometry/extensions/index/rtree/visitors/remove.hpp>
#include <boost/geometry/extensions/index/rtree/linear/linear.hpp>
-#include <boost/geometry/extensions/index/rtree/rstar/rstar.hpp>
+
+// TODO: awulkiew - correct implementation
+//#include <boost/geometry/extensions/index/rtree/quadratic/quadratic.hpp>
+//#include <boost/geometry/extensions/index/rtree/rstar/rstar.hpp>
namespace boost { namespace geometry { namespace index {
@@ -80,7 +85,9 @@
void insert(value_type const& value)
{
- detail::rtree::visitors::insert<value_type, translator_type, box_type, tag_type>
+ // 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);
boost::apply_visitor(insert_v, *m_root);
@@ -88,6 +95,36 @@
++m_values_count;
}
+ void remove(value_type const& value)
+ {
+ // TODO: awulkiew - assert for correct value
+ 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);
+
+ boost::apply_visitor(remove_v, *m_root);
+
+ --m_values_count;
+ }
+
+ size_t size() const
+ {
+ return m_values_count;
+ }
+
+ bool empty() const
+ {
+ // TODO: awulkiew - take root into consideration
+ return 0 == m_values_count;
+ }
+
+ void clear()
+ {
+ // TODO: awulkiew - implement
+ assert(false);
+ }
+
template <typename Visitor>
typename Visitor::result_type apply_visitor(Visitor & visitor) const
{
@@ -118,6 +155,12 @@
tree.insert(v);
}
+template <typename Value, typename Translator, typename Tag>
+void remove(rtree<Value, Translator, Tag> & tree, Value const& v)
+{
+ tree.remove(v);
+}
+
}}} // namespace boost::geometry::index
#endif // BOOST_GEOMETRY_EXTENSIONS_INDEX_RSTREE_RSTREE_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-05-04 17:33:15 EDT (Wed, 04 May 2011)
@@ -10,6 +10,8 @@
#ifndef BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_VISITORS_INSERT_HPP
#define BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_VISITORS_INSERT_HPP
+#include <boost/geometry/extensions/index/algorithms/area.hpp>
+
#include <boost/geometry/extensions/index/rtree/node.hpp>
namespace boost { namespace geometry { namespace index {
@@ -26,16 +28,18 @@
typedef typename rtree::internal_node<Value, Box, Tag>::type internal_node;
typedef typename rtree::leaf<Value, Box, Tag>::type leaf;
- typedef typename internal_node::children_type children_type;
+ typedef typename rtree::elements_type<internal_node>::type children_type;
typedef typename index::default_area_result<Box>::type area_type;
template <typename Indexable>
static inline size_t apply(internal_node & n, Indexable const& indexable)
{
- assert(!n.children.empty());
+ children_type & children = rtree::elements_get(n);
+
+ assert(!children.empty());
- size_t children_count = n.children.size();
+ size_t children_count = children.size();
// choose index with smallest area change or smallest area
size_t choosen_index = 0;
@@ -46,7 +50,7 @@
for ( size_t i = 0 ; i < children_count ; ++i )
{
typedef typename children_type::value_type child_type;
- child_type const& ch_i = n.children[i];
+ child_type const& ch_i = children[i];
Box box_exp(ch_i.first);
geometry::expand(box_exp, indexable);
@@ -73,7 +77,7 @@
// Default split algorithm
template <typename Value, typename Translator, typename Box, typename Tag>
-class split
+struct split
{
typedef typename rtree::node<Value, Box, Tag>::type node;
typedef typename rtree::internal_node<Value, Box, Tag>::type internal_node;
@@ -81,7 +85,6 @@
static const size_t dimension = index::traits::dimension<Box>::value;
-public:
template <typename Node>
static inline void apply(
Node & n,
@@ -131,7 +134,6 @@
typedef typename rtree::internal_node<Value, Box, Tag>::type internal_node;
typedef typename rtree::leaf<Value, Box, Tag>::type leaf;
-public:
template <typename Node>
static inline void apply(
Node & n,
@@ -146,21 +148,31 @@
}
};
-} // namespace detail
-
-// Default insert algorithm
-template <typename Value, typename Translator, typename Box, typename Tag>
+// Default insert visitor
+template <typename Element, typename Value, typename Translator, typename Box, typename Tag>
class insert : public boost::static_visitor<>
{
+public:
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;
-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)
+ inline insert(node* & root,
+ Element const& element,
+ size_t min_elements,
+ size_t max_elements,
+ Translator const& t,
+ size_t level = std::numeric_limits<size_t>::max()
+ )
+ : m_element(element)
+ , m_tr(t)
+ , m_min_elems_per_node(min_elements)
+ , m_max_elems_per_node(max_elements)
+ , m_level(level)
, m_root_node(root)
- , m_parent(0), m_current_child_index(0), m_current_level(0)
+ , m_parent(0)
+ , m_current_child_index(0)
+ , m_current_level(0)
{
// TODO
// assert - check if Box is correct
@@ -168,39 +180,52 @@
inline void operator()(internal_node & n)
{
+ // traverse
+ traverse(*this, n);
+
+ post_traverse(n);
+ }
+
+ inline void operator()(leaf & n)
+ {
+ // push value
+ rtree::elements_get(n).push_back(m_element);
+
+ post_traverse(n);
+ }
+
+protected:
+ template <typename Visitor>
+ inline void traverse(Visitor & visitor, internal_node & n)
+ {
// choose next node
size_t choosen_node_index = detail::choose_next_node<Value, Box, Tag>::
- apply(n, rtree::element_indexable(m_value, m_tr));
+ apply(n, rtree::element_indexable(m_element, m_tr));
// expand the node to contain value
- geometry::expand(n.children[choosen_node_index].first, m_tr(m_value));
+ geometry::expand(
+ n.children[choosen_node_index].first,
+ rtree::element_indexable(m_element, m_tr));
// next traversing step
- traverse_apply_visitor(n, choosen_node_index);
-
- // handle overflow
- if ( m_max_elems_per_node < n.children.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);
- }
+ traverse_apply_visitor(visitor, n, choosen_node_index);
}
- inline void operator()(leaf & n)
- {
- // push value
- n.values.push_back(m_value);
+ // TODO: awulkiew - change name to handle_overflow or overflow_treatment?
+ template <typename Node>
+ inline void post_traverse(Node &n)
+ {
// handle overflow
- if ( m_max_elems_per_node < n.values.size() )
+ 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);
}
}
-private:
- inline void traverse_apply_visitor(internal_node &n, size_t choosen_node_index)
+ template <typename Visitor>
+ inline void traverse_apply_visitor(Visitor & visitor, internal_node &n, size_t choosen_node_index)
{
// save previous traverse inputs and set new ones
internal_node * parent_bckup = m_parent;
@@ -212,7 +237,7 @@
++m_current_level;
// next traversing step
- boost::apply_visitor(*this, *n.children[choosen_node_index].second);
+ boost::apply_visitor(visitor, *rtree::elements_get(n)[choosen_node_index].second);
// restore previous traverse inputs
m_parent = parent_bckup;
@@ -220,10 +245,11 @@
m_current_level = current_level_bckup;
}
- Value const& m_value;
+ 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_level;
node* & m_root_node;
@@ -233,6 +259,91 @@
size_t m_current_level;
};
+} // namespace detail
+
+// Default insert visitor
+template <typename Element, typename Value, typename Translator, typename Box, typename Tag>
+struct insert : public detail::insert<Element, Value, Translator, Box, Tag>
+{
+ typedef detail::insert<Element, Value, Translator, Box, Tag> base;
+ typedef typename base::node node;
+ typedef typename base::internal_node internal_node;
+ typedef typename base::leaf leaf;
+
+ inline insert(node* & root,
+ Element const& element,
+ size_t min_elements,
+ size_t max_elements,
+ Translator const& tr,
+ size_t level = std::numeric_limits<size_t>::max()
+ )
+ : base(root, element, min_elements, max_elements, tr, level)
+ {}
+
+ inline void operator()(internal_node & n)
+ {
+ if ( base::m_current_level < base::m_level )
+ {
+ // next traversing step
+ base::traverse(*this, n);
+ }
+ else
+ {
+ assert( base::m_level == base::m_current_level );
+
+ // push new child node
+ rtree::elements_get(n).push_back(base::m_element);
+ }
+
+ base::post_traverse(n);
+ }
+
+ inline void operator()(leaf & n)
+ {
+ assert(false);
+ }
+};
+
+// Default insert visitor specialized for Values elements
+template <typename Value, typename Translator, typename Box, typename Tag>
+struct insert<Value, Value, Translator, Box, Tag> : public detail::insert<Value, Value, Translator, Box, Tag>
+{
+ typedef detail::insert<Value, Value, Translator, Box, Tag> base;
+ typedef typename base::node node;
+ typedef typename base::internal_node internal_node;
+ typedef typename base::leaf leaf;
+
+ inline insert(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(base::m_current_level < base::m_level);
+
+ // next traversing step
+ base::traverse(*this, n);
+
+ base::post_traverse(n);
+ }
+
+ inline void operator()(leaf & n)
+ {
+ assert( base::m_level == base::m_current_level ||
+ base::m_level == std::numeric_limits<size_t>::max() );
+
+ rtree::elements_get(n).push_back(base::m_element);
+
+ base::post_traverse(n);
+ }
+};
+
}}} // namespace detail::rtree::visitors
}}} // namespace boost::geometry::index
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-05-04 17:33:15 EDT (Wed, 04 May 2011)
@@ -12,14 +12,201 @@
#include <boost/geometry/extensions/index/rtree/node.hpp>
+#include <boost/geometry/extensions/index/rtree/visitors/is_leaf.hpp>
+
namespace boost { namespace geometry { namespace index {
namespace detail { namespace rtree { namespace visitors {
+// Default remove algorithm
template <typename Value, typename Translator, typename Box, typename Tag>
-struct rtree_remove
+class remove : public boost::static_visitor<>
{
- // not implemented here
+ 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;
+
+public:
+ inline explicit remove(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_is_value_removed(false)
+ , m_parent(0)
+ , m_current_child_index(0)
+ , m_current_level(0)
+ , m_is_underflow(false)
+ {
+ // TODO
+ // assert - check if Value/Box is correct
+ }
+
+ inline void operator()(internal_node & n)
+ {
+ typedef typename rtree::elements_type<internal_node>::type children_type;
+ children_type & children = rtree::elements_get(n);
+
+ size_t child_node_index = 0;
+ for ( ; child_node_index < children.size() ; ++child_node_index )
+ {
+ if ( geometry::intersects(children[child_node_index].first, m_tr(m_value)) )
+ {
+ // next traversing step
+ traverse_apply_visitor(n, child_node_index);
+
+ if ( m_is_value_removed )
+ break;
+ }
+ }
+
+ // value was found and removed
+ if ( m_is_value_removed )
+ {
+ typedef typename rtree::elements_type<internal_node>::type elements_type;
+ typedef typename elements_type::iterator element_iterator;
+ elements_type & elements = rtree::elements_get(n);
+
+ // underflow occured - child node should be removed
+ if ( m_is_underflow )
+ {
+ 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));
+ elements.erase(underfl_el_it);
+
+ // calc underflow
+ m_is_underflow = elements.size() < m_min_elems_per_node;
+ }
+
+ // test - underflow state should be ok here
+ assert(elements.size() < m_min_elems_per_node == m_is_underflow);
+
+ // n is not root - adjust aabb
+ if ( 0 != m_parent )
+ {
+ rtree::elements_get(*m_parent)[m_current_child_index].first
+ = rtree::elements_box<Box>(elements.begin(), elements.end(), m_tr);
+ }
+ // n is root node
+ else
+ {
+ // current node must be a root
+ assert(&n == boost::get<internal_node>(m_root_node));
+
+ // value not found
+ assert(m_is_value_removed);
+
+ // reinsert elements from removed nodes
+ // begin with levels closer to the root
+ for ( std::vector< std::pair<size_t, node*> >::reverse_iterator it = m_underflowed_nodes.rbegin();
+ it != m_underflowed_nodes.rend() ; ++it )
+ {
+ if ( boost::apply_visitor(is_leaf<Value, Box, Tag>(), *it->second) )
+ reinsert_elements(boost::get<leaf>(*it->second), it->first);
+ else
+ reinsert_elements(boost::get<internal_node>(*it->second), it->first);
+ }
+
+ // shorten the tree
+ if ( rtree::elements_get(n).size() == 1 )
+ {
+ m_root_node = rtree::elements_get(n)[0].second;
+ }
+ }
+ }
+ }
+
+ inline void operator()(leaf & n)
+ {
+ typedef typename rtree::elements_type<leaf>::type elements_type;
+ elements_type & elements = rtree::elements_get(n);
+
+ // find value and remove it
+ for ( elements_type::iterator it = elements.begin() ; it != elements.end() ; ++it )
+ {
+ if ( m_tr.equals(*it, m_value) )
+ {
+ elements.erase(it);
+ m_is_value_removed = true;
+ break;
+ }
+ }
+
+ // if value was removed
+ if ( m_is_value_removed )
+ {
+ // calc underflow
+ m_is_underflow = elements.size() < m_min_elems_per_node;
+
+ // n is not root - adjust aabb
+ if ( 0 != m_parent )
+ {
+ rtree::elements_get(*m_parent)[m_current_child_index].first
+ = rtree::elements_box<Box>(elements.begin(), elements.end(), m_tr);
+ }
+ }
+ }
+
+private:
+ inline void traverse_apply_visitor(internal_node &n, size_t choosen_node_index)
+ {
+ // save previous traverse inputs and set new ones
+ internal_node * parent_bckup = m_parent;
+ 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(*this, *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;
+ }
+
+ template <typename Node>
+ void reinsert_elements(Node &n, size_t level)
+ {
+ typedef typename rtree::elements_type<Node>::type elements_type;
+ elements_type & elements = rtree::elements_get(n);
+ for ( typename elements_type::iterator it = elements.begin();
+ it != elements.end() ; ++it )
+ {
+ visitors::insert<elements_type::value_type, Value, Translator, Box, Tag> insert_v(
+ m_root_node,
+ *it,
+ m_min_elems_per_node,
+ m_max_elems_per_node,
+ m_tr,
+ level);
+
+ boost::apply_visitor(insert_v, *m_root_node);
+ }
+ }
+
+ 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;
+ bool m_is_value_removed;
+ std::vector< std::pair<size_t, node*> > m_underflowed_nodes;
+
+ // traversing input parameters
+ internal_node *m_parent;
+ size_t m_current_child_index;
+ size_t m_current_level;
+
+ // traversing output parameters
+ bool m_is_underflow;
};
}}} // namespace detail::rtree::visitors
Modified: sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/translator/def.hpp
==============================================================================
--- sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/translator/def.hpp (original)
+++ sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/translator/def.hpp 2011-05-04 17:33:15 EDT (Wed, 04 May 2011)
@@ -29,10 +29,10 @@
return detail::extract_indexable<Value>::get(v);
}
- /*bool equals(Value const& v1, Value const& v2) const
+ bool equals(Value const& v1, Value const& v2) const
{
return detail::equals<Value>::apply(v1, v2);
- }*/
+ }
};
// Iterator
@@ -46,10 +46,10 @@
return detail::extract_indexable<typename Value::value_type>::get(*v);
}
- /*bool equals(Value const& v1, Value const& v2) const
+ bool equals(Value const& v1, Value const& v2) const
{
return v1 == v2;
- }*/
+ }
};
// SmartPtr
@@ -63,10 +63,10 @@
return detail::extract_indexable<typename Value::element_type>::get(*v);
}
- /*bool equals(Value const& v1, Value const& v2) const
+ bool equals(Value const& v1, Value const& v2) const
{
return v1 == v2;
- }*/
+ }
};
} // namespace dispatch
@@ -92,10 +92,10 @@
return detail::extract_indexable<Value>::get(*v);
}
- /*bool equals(const Value* v1, const Value* v2) const
+ bool equals(const Value* v1, const Value* v2) const
{
return v1 == v2;
- }*/
+ }
};
}}}} // namespace boost::geometry::index::translator
Modified: sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/translator/helpers.hpp
==============================================================================
--- sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/translator/helpers.hpp (original)
+++ sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/translator/helpers.hpp 2011-05-04 17:33:15 EDT (Wed, 04 May 2011)
@@ -17,6 +17,8 @@
#include <boost/mpl/has_xxx.hpp>
#include <boost/mpl/and.hpp>
+#include <boost/geometry/algorithms/equals.hpp>
+
#include <boost/geometry/extensions/index/indexable.hpp>
namespace boost { namespace geometry { namespace index { namespace translator {
@@ -132,60 +134,58 @@
} // namespace detail
-//namespace dispatch {
-//
-//template <typename Geometry, typename Tag>
-//struct equals
-//{
-// static bool apply(Geometry const& g1, Geometry const& g2)
-// {
-// return geometry::equals(g1, g2);
-// }
-//};
-//
-//template <typename T>
-//struct equals<T, void>
-//{
-// static bool apply(T const& v1, T const& v2)
-// {
-// return v1 == v2;
-// }
-//};
-//
-//} // namespace dispatch
-//
-//namespace detail {
-//
-//template <typename Geometry>
-//struct equals
-//{
-// static bool apply(Geometry const& g1, Geometry const& g2)
-// {
-// return geometry::equals(g1, g2);
-// }
-//};
-//
-//template <typename First, typename Second>
-//struct equals< std::pair<First, Second> >
-//{
-// static bool apply(std::pair<First, Second> const& p1, std::pair<First, Second> const& p2)
-// {
-// return
-// dispatch::equals<
-// First,
-// typename traits::tag<First>::type
-// >::apply(p1.first, p2.first)
-// &&
-// dispatch::equals<
-// Second,
-// typename traits::tag<Second>::type
-// >::apply(p1.second, p2.second);
-// }
-//};
-//
-//} // namespace detail
+namespace dispatch {
+template <typename Geometry, typename Tag>
+struct equals
+{
+ static bool apply(Geometry const& g1, Geometry const& g2)
+ {
+ return geometry::equals(g1, g2);
+ }
+};
+template <typename T>
+struct equals<T, void>
+{
+ static bool apply(T const& v1, T const& v2)
+ {
+ return v1 == v2;
+ }
+};
+
+} // namespace dispatch
+
+namespace detail {
+
+template <typename Geometry>
+struct equals
+{
+ static bool apply(Geometry const& g1, Geometry const& g2)
+ {
+ return geometry::equals(g1, g2);
+ }
+};
+
+template <typename First, typename Second>
+struct equals< std::pair<First, Second> >
+{
+ static bool apply(std::pair<First, Second> const& p1, std::pair<First, Second> const& p2)
+ {
+ return
+ dispatch::equals<
+ First,
+ typename traits::tag<First>::type
+ >::apply(p1.first, p2.first)
+ &&
+ dispatch::equals<
+ Second,
+ typename traits::tag<Second>::type
+ >::apply(p1.second, p2.second);
+ }
+};
+
+} // namespace detail
}}}} // namespace boost::geometry::index::translator
Modified: sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/translator/index.hpp
==============================================================================
--- sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/translator/index.hpp (original)
+++ sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/translator/index.hpp 2011-05-04 17:33:15 EDT (Wed, 04 May 2011)
@@ -29,10 +29,10 @@
<typename Container::value_type>::get(m_c[i]);
}
- /*bool equals(size_t i1, size_t i2) const
+ bool equals(size_t i1, size_t i2) const
{
- return i1 == i2;
- }*/
+ return i1 == i2;
+ }
private:
Container const& m_c;
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-05-04 17:33:15 EDT (Wed, 04 May 2011)
@@ -10,6 +10,7 @@
typedef boost::geometry::model::box<P> B;
//boost::geometry::index::rtree<B> t(2, 1);
boost::geometry::index::rtree<B> t(4, 2);
+std::vector<B> vect;
void render_scene(void)
{
@@ -39,7 +40,7 @@
void mouse(int button, int state, int x, int y)
{
- if ( state == GLUT_DOWN )
+ if ( button == GLUT_LEFT_BUTTON && state == GLUT_DOWN )
{
float x = ( rand() % 100 );
float y = ( rand() % 100 );
@@ -49,13 +50,35 @@
B b(P(x - w, y - h),P(x + w, y + h));
boost::geometry::index::insert(t, b);
+ vect.push_back(b);
- std::cout << "\n\n\n" << 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";*/
+
+ glutPostRedisplay();
+ }
+ else if ( button == GLUT_RIGHT_BUTTON && state == GLUT_DOWN )
+ {
+ if ( vect.empty() )
+ return;
+
+ size_t i = rand() % vect.size();
+ B b = vect[i];
+
+ boost::geometry::index::remove(t, b);
+ vect.erase(vect.begin() + i);
+
+ /*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";*/
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-05-04 17:33:15 EDT (Wed, 04 May 2011)
@@ -43,39 +43,21 @@
}
std::cout << "loaded\n";
- std::cout << "inserting time test...\n";
- tim.restart();
RT t(max_elems, min_elems);
- for (size_t i = 0 ; i < values_count ; ++i )
- {
- float x = coords[i].first;
- float y = coords[i].second;
- B b(P(x - 0.5f, y - 0.5f), P(x + 0.5f, y + 0.5f));
-
- // Zle wyswietla dane, obcina czesc ulamkowa
- // Zle buduje drzewo dla i == 228
-
- //TEST
- /*if ( i == 228 )
- {
- std::cout << std::fixed << x << ", " << y << "\n";
- boost::geometry::index::detail::rtree::visitors::detail::print_indexable(std::cout, b);
- }*/
-
- t.insert(std::make_pair(b, i));
- //TEST
- /*if ( !boost::geometry::index::are_boxes_ok(t) )
+ {
+ std::cout << "inserting time test...\n";
+ tim.restart();
+ for (size_t i = 0 ; i < values_count ; ++i )
{
- std::ofstream log("log1.txt", std::ofstream::trunc);
- log << std::fixed << i << " - " << x << ", " << y << " - inserted: ";
- boost::geometry::index::detail::rtree::visitors::detail::print_indexable(log, b);
- log << '\n';
- log << ( boost::geometry::index::are_boxes_ok(t) ? "boxes OK" : "WRONG BOXES!" );
- log << '\n' << t;
- }*/
+ float x = coords[i].first;
+ float y = coords[i].second;
+ B b(P(x - 0.5f, y - 0.5f), P(x + 0.5f, y + 0.5f));
+
+ t.insert(std::make_pair(b, i));
+ }
+ std::cout << "time: " << tim.elapsed() << "s\n";
}
- std::cout << "time: " << tim.elapsed() << "s\n";
if ( save_ch == 's' )
{
@@ -92,19 +74,81 @@
std::cout << "saved...\n";
}
- std::cout << "searching time test...\n";
- tim.restart();
- size_t temp = 0;
- for (size_t i = 0 ; i < queries_count ; ++i )
- {
- float x = coords[i].first;
- float y = coords[i].second;
- std::deque< std::pair<B, size_t> > result;
- t.find(B(P(x - 10, y - 10), P(x + 10, y + 10)), std::back_inserter(result));
- temp += result.size();
+ {
+ std::cout << "searching time test...\n";
+ tim.restart();
+ size_t temp = 0;
+ for (size_t i = 0 ; i < queries_count ; ++i )
+ {
+ float x = coords[i].first;
+ float y = coords[i].second;
+ std::deque< std::pair<B, size_t> > result;
+ t.find(B(P(x - 10, y - 10), P(x + 10, y + 10)), std::back_inserter(result));
+ temp += result.size();
+ }
+ std::cout << "time: " << tim.elapsed() << "s\n";
+ std::cout << temp << "\n";
+ }
+
+ {
+ std::cout << "removing time test...\n";
+ tim.restart();
+ for (size_t i = 0 ; i < values_count / 2 ; ++i )
+ {
+ float x = coords[i].first;
+ float y = coords[i].second;
+ B b(P(x - 0.5f, y - 0.5f), P(x + 0.5f, y + 0.5f));
+
+ t.remove(std::make_pair(b, i));
+ }
+ std::cout << "time: " << tim.elapsed() << "s\n";
+ }
+
+ {
+ std::cout << "searching time test...\n";
+ tim.restart();
+ size_t temp = 0;
+ for (size_t i = 0 ; i < queries_count ; ++i )
+ {
+ float x = coords[i].first;
+ float y = coords[i].second;
+ std::deque< std::pair<B, size_t> > result;
+ t.find(B(P(x - 10, y - 10), P(x + 10, y + 10)), std::back_inserter(result));
+ temp += result.size();
+ }
+ std::cout << "time: " << tim.elapsed() << "s\n";
+ std::cout << temp << "\n";
+ }
+
+ {
+ std::cout << "inserting time test...\n";
+ tim.restart();
+ for (size_t i = 0 ; i < values_count / 2 ; ++i )
+ {
+ float x = coords[i].first;
+ float y = coords[i].second;
+ B b(P(x - 0.5f, y - 0.5f), P(x + 0.5f, y + 0.5f));
+
+ t.insert(std::make_pair(b, i));
+ }
+ std::cout << "time: " << tim.elapsed() << "s\n";
+ }
+
+ {
+ std::cout << "searching time test...\n";
+ tim.restart();
+ size_t temp = 0;
+ for (size_t i = 0 ; i < queries_count ; ++i )
+ {
+ float x = coords[i].first;
+ float y = coords[i].second;
+ std::deque< std::pair<B, size_t> > result;
+ t.find(B(P(x - 10, y - 10), P(x + 10, y + 10)), std::back_inserter(result));
+ temp += result.size();
+ }
+ std::cout << "time: " << tim.elapsed() << "s\n";
+ std::cout << temp << "\n";
}
- std::cout << "time: " << tim.elapsed() << "s\n";
- std::cout << temp << "\n";
std::cin.get();
Modified: sandbox-branches/geometry/index_080_new/tests/main.cpp
==============================================================================
--- sandbox-branches/geometry/index_080_new/tests/main.cpp (original)
+++ sandbox-branches/geometry/index_080_new/tests/main.cpp 2011-05-04 17:33:15 EDT (Wed, 04 May 2011)
@@ -2,25 +2,40 @@
#include <tests/rtree_native.hpp>
#include <tests/rtree_filters.hpp>
+#include <boost/geometry/extensions/index/rtree/visitors/are_boxes_ok.hpp>
+
int main()
{
tests_translators_hpp();
tests_rtree_native_hpp<boost::geometry::index::linear_tag>();
- tests_rtree_native_hpp<boost::geometry::index::rstar_tag>();
+ //tests_rtree_native_hpp<boost::geometry::index::rstar_tag>();
tests_rtree_filters_hpp();
- /*namespace g = boost::geometry;
- typedef g::model::point<float, 2, g::cs::cartesian> P;
- typedef g::model::box<P> B;
-
- g::index::rtree<B> tree(4, 2);
- g::index::insert(tree, B(P(1, 6),P(6, 19)));
- g::index::insert(tree, B(P(10, 1),P(18, 18)));
- g::index::insert(tree, B(P(22, 6),P(27, 20)));
- g::index::insert(tree, B(P(29, 2),P(34, 18)));
- g::index::insert(tree, B(P(35, 3),P(39, 19)));
-
- std::cout << tree;*/
+ {
+ namespace bg = boost::geometry;
+ namespace bgi = boost::geometry::index;
+ typedef bg::model::point<float, 2, bg::cs::cartesian> P;
+ typedef bg::model::box<P> B;
+ typedef std::pair<B, int> V;
+
+ bgi::rtree<V, bgi::default_parameter, bgi::linear_tag> t(4, 2);
+ const int m = 15;
+ for ( int i = 0 ; i < m ; ++i )
+ {
+ bgi::insert(t, V(B(P(i*2, i*2), P(i*2+1, i*2+1)), i));
+ }
+ std::cout << t << "\n------------------------------------\n";
+ std::cin.get();
+
+ for ( int i = 0 ; i < m ; ++i )
+ {
+ bgi::remove(t, V(B(P(i*2, i*2), P(i*2+1, i*2+1)), i));
+ std::cout << t << '\n';
+ std::cout << ( boost::geometry::index::are_boxes_ok(t) ? "boxes OK" : "WRONG BOXES!" );
+ std::cout << "\n------------------------------------\n";
+ std::cin.get();
+ }
+ }
#ifdef _MSC_VER
std::cin.get();
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