|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r80841 - in sandbox-branches/geometry/index: . boost/geometry/extensions/index/rtree/rstar boost/geometry/extensions/index/rtree/visitors test/rtree tests
From: adam.wulkiewicz_at_[hidden]
Date: 2012-10-04 05:37:42
Author: awulkiew
Date: 2012-10-04 05:37:39 EDT (Thu, 04 Oct 2012)
New Revision: 80841
URL: http://svn.boost.org/trac/boost/changeset/80841
Log:
merged from index_dev.
clang warnings and error in nearest_k fixed.
added insert_traverse_data.
added additional tests.
Added:
sandbox-branches/geometry/index/tests/additional_speed.cpp
- copied unchanged from r80840, /sandbox-branches/geometry/index_dev/tests/additional_speed.cpp
Properties modified:
sandbox-branches/geometry/index/ (props changed)
Text files modified:
sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/rstar/insert.hpp | 44 ++++++++++-------
sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/insert.hpp | 98 ++++++++++++++++++++++++++-------------
sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/nearest.hpp | 6 ++
sandbox-branches/geometry/index/test/rtree/test_rtree.hpp | 42 +++++++++++++++++
4 files changed, 139 insertions(+), 51 deletions(-)
Modified: sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/rstar/insert.hpp
==============================================================================
--- sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/rstar/insert.hpp (original)
+++ sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/rstar/insert.hpp 2012-10-04 05:37:39 EDT (Thu, 04 Oct 2012)
@@ -153,17 +153,17 @@
{
BOOST_GEOMETRY_INDEX_ASSERT(result_elements.empty(), "reinsert should be handled only once for level");
- result_relative_level = base::m_leafs_level - base::m_current_level;
+ result_relative_level = base::m_leafs_level - base::m_traverse_data.current_level;
// overflow
if ( base::m_parameters.get_max_elements() < rtree::elements(n).size() )
{
// node isn't root node
- if ( base::m_parent )
+ if ( !base::m_traverse_data.current_is_root() )
{
rstar::remove_elements_to_reinsert<Value, Options, Translator, Box, Allocators>::apply(
result_elements, n,
- base::m_parent, base::m_current_child_index,
+ base::m_traverse_data.parent, base::m_traverse_data.current_child_index,
base::m_parameters, base::m_translator);
}
// node is root node
@@ -188,10 +188,10 @@
template <typename Node>
inline void recalculate_aabb_if_necessary(Node &n) const
{
- if ( !result_elements.empty() && base::m_parent )
+ if ( !result_elements.empty() && !base::m_traverse_data.current_is_root() )
{
// calulate node's new box
- rtree::elements(*base::m_parent)[base::m_current_child_index].first =
+ base::m_traverse_data.current_element().first =
elements_box<Box>(rtree::elements(n).begin(), rtree::elements(n).end(), base::m_translator);
}
}
@@ -223,9 +223,9 @@
inline void operator()(internal_node & n)
{
- BOOST_GEOMETRY_INDEX_ASSERT(base::m_current_level < base::m_leafs_level, "unexpected level");
+ BOOST_GEOMETRY_INDEX_ASSERT(base::m_traverse_data.current_level < base::m_leafs_level, "unexpected level");
- if ( base::m_current_level < base::m_level )
+ if ( base::m_traverse_data.current_level < base::m_level )
{
// next traversing step
base::traverse(*this, n);
@@ -235,7 +235,7 @@
{
BOOST_GEOMETRY_INDEX_ASSERT(0 < base::m_level, "illegal level value, level shouldn't be the root level for 0 < InsertIndex");
- if ( base::m_current_level == base::m_level - 1 )
+ if ( base::m_traverse_data.current_level == base::m_level - 1 )
{
base::handle_possible_reinsert_or_split_of_root(n);
}
@@ -243,7 +243,7 @@
}
else
{
- BOOST_GEOMETRY_INDEX_ASSERT(base::m_level == base::m_current_level, "unexpected level");
+ BOOST_GEOMETRY_INDEX_ASSERT(base::m_level == base::m_traverse_data.current_level, "unexpected level");
// push new child node
rtree::elements(n).push_back(base::m_element);
@@ -292,15 +292,15 @@
inline void operator()(internal_node & n)
{
- BOOST_GEOMETRY_INDEX_ASSERT(base::m_current_level < base::m_leafs_level, "unexpected level");
- BOOST_GEOMETRY_INDEX_ASSERT(base::m_current_level < base::m_level, "unexpected level");
+ BOOST_GEOMETRY_INDEX_ASSERT(base::m_traverse_data.current_level < base::m_leafs_level, "unexpected level");
+ BOOST_GEOMETRY_INDEX_ASSERT(base::m_traverse_data.current_level < base::m_level, "unexpected level");
// next traversing step
base::traverse(*this, n);
BOOST_GEOMETRY_INDEX_ASSERT(0 < base::m_level, "illegal level value, level shouldn't be the root level for 0 < InsertIndex");
- if ( base::m_current_level == base::m_level - 1 )
+ if ( base::m_traverse_data.current_level == base::m_level - 1 )
{
base::handle_possible_reinsert_or_split_of_root(n);
}
@@ -310,8 +310,11 @@
inline void operator()(leaf & n)
{
- BOOST_GEOMETRY_INDEX_ASSERT(base::m_current_level == base::m_leafs_level, "unexpected level");
- BOOST_GEOMETRY_INDEX_ASSERT(base::m_level == base::m_current_level || base::m_level == (std::numeric_limits<size_t>::max)(), "unexpected level");
+ BOOST_GEOMETRY_INDEX_ASSERT(base::m_traverse_data.current_level == base::m_leafs_level,
+ "unexpected level");
+ BOOST_GEOMETRY_INDEX_ASSERT(base::m_level == base::m_traverse_data.current_level ||
+ base::m_level == (std::numeric_limits<size_t>::max)(),
+ "unexpected level");
rtree::elements(n).push_back(base::m_element);
@@ -342,8 +345,10 @@
inline void operator()(internal_node & n)
{
- BOOST_GEOMETRY_INDEX_ASSERT(base::m_current_level < base::m_leafs_level, "unexpected level");
- BOOST_GEOMETRY_INDEX_ASSERT(base::m_current_level < base::m_level, "unexpected level");
+ BOOST_GEOMETRY_INDEX_ASSERT(base::m_traverse_data.current_level < base::m_leafs_level,
+ "unexpected level");
+ BOOST_GEOMETRY_INDEX_ASSERT(base::m_traverse_data.current_level < base::m_level,
+ "unexpected level");
// next traversing step
base::traverse(*this, n);
@@ -353,8 +358,11 @@
inline void operator()(leaf & n)
{
- BOOST_GEOMETRY_INDEX_ASSERT(base::m_current_level == base::m_leafs_level, "unexpected level");
- BOOST_GEOMETRY_INDEX_ASSERT(base::m_level == base::m_current_level || base::m_level == (std::numeric_limits<size_t>::max)(), "unexpected level");
+ BOOST_GEOMETRY_INDEX_ASSERT(base::m_traverse_data.current_level == base::m_leafs_level,
+ "unexpected level");
+ BOOST_GEOMETRY_INDEX_ASSERT(base::m_level == base::m_traverse_data.current_level ||
+ base::m_level == (std::numeric_limits<size_t>::max)(),
+ "unexpected level");
rtree::elements(n).push_back(base::m_element);
Modified: sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/insert.hpp
==============================================================================
--- sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/insert.hpp (original)
+++ sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/insert.hpp 2012-10-04 05:37:39 EDT (Thu, 04 Oct 2012)
@@ -23,11 +23,12 @@
// Default choose_next_node
template <typename Value, typename Options, typename Box, typename Allocators, typename ChooseNextNodeTag>
-struct choose_next_node;
+class choose_next_node;
template <typename Value, typename Options, typename Box, typename Allocators>
-struct choose_next_node<Value, Options, Box, Allocators, choose_by_content_diff_tag>
+class choose_next_node<Value, Options, Box, Allocators, choose_by_content_diff_tag>
{
+public:
typedef typename Options::parameters_type parameters_type;
typedef typename rtree::node<Value, parameters_type, Box, Allocators, typename Options::node_tag>::type node;
@@ -152,6 +153,45 @@
// ----------------------------------------------------------------------- //
+template <typename InternalNode>
+struct insert_traverse_data
+{
+ typedef typename rtree::elements_type<InternalNode>::type elements_type;
+ typedef typename elements_type::value_type element_type;
+
+ insert_traverse_data()
+ : parent(0), current_child_index(0), current_level(0)
+ {}
+
+ void move_to_next_level(InternalNode * new_parent, size_t new_child_index)
+ {
+ parent = new_parent;
+ current_child_index = new_child_index;
+ ++current_level;
+ }
+
+ bool current_is_root() const
+ {
+ return 0 == parent;
+ }
+
+ elements_type & parent_elements() const
+ {
+ BOOST_GEOMETRY_INDEX_ASSERT(parent, "null pointer");
+ return rtree::elements(*parent);
+ }
+
+ element_type & current_element() const
+ {
+ BOOST_GEOMETRY_INDEX_ASSERT(parent, "null pointer");
+ return rtree::elements(*parent)[current_child_index];
+ }
+
+ InternalNode * parent;
+ size_t current_child_index;
+ size_t current_level;
+};
+
// Default insert visitor
template <typename Element, typename Value, typename Options, typename Translator, typename Box, typename Allocators>
class insert
@@ -180,9 +220,7 @@
, 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)
+ , m_traverse_data()
, m_allocators(allocators)
{
BOOST_GEOMETRY_INDEX_ASSERT(m_relative_level <= leafs_level, "unexpected level value");
@@ -197,7 +235,7 @@
{
// choose next node
size_t choosen_node_index = detail::choose_next_node<Value, Options, Box, Allocators, typename Options::choose_next_node_tag>::
- apply(n, rtree::element_indexable(m_element, m_translator), m_parameters, m_leafs_level - m_current_level);
+ apply(n, rtree::element_indexable(m_element, m_translator), m_parameters, m_leafs_level - m_traverse_data.current_level);
// expand the node to contain value
geometry::expand(
@@ -213,7 +251,8 @@
template <typename Node>
inline void post_traverse(Node &n)
{
- BOOST_GEOMETRY_INDEX_ASSERT(0 == m_parent || &n == rtree::get<Node>(rtree::elements(*m_parent)[m_current_child_index].second),
+ BOOST_GEOMETRY_INDEX_ASSERT(m_traverse_data.current_is_root() ||
+ &n == rtree::get<Node>(m_traverse_data.current_element().second),
"if node isn't the root current_child_index should be valid");
// handle overflow
@@ -227,22 +266,16 @@
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;
- size_t current_child_index_bckup = m_current_child_index;
- size_t current_level_bckup = m_current_level;
+ insert_traverse_data<internal_node> backup_traverse_data = m_traverse_data;
// calculate new traverse inputs
- m_parent = &n;
- m_current_child_index = choosen_node_index;
- ++m_current_level;
+ m_traverse_data.move_to_next_level(&n, choosen_node_index);
// next traversing step
rtree::apply_visitor(visitor, *rtree::elements(n)[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;
+ m_traverse_data = backup_traverse_data;
}
// TODO: consider - split result returned as OutIter is faster than reference to the container. Why?
@@ -269,12 +302,12 @@
// Implement template <node_tag> struct node_element_type or something like that
// node is not the root - just add the new node
- if ( m_parent != 0 )
+ if ( !m_traverse_data.current_is_root() )
{
// update old node's box
- rtree::elements(*m_parent)[m_current_child_index].first = n_box;
+ m_traverse_data.current_element().first = n_box;
// add new node to the parent's children
- rtree::elements(*m_parent).push_back(additional_nodes[0]);
+ m_traverse_data.parent_elements().push_back(additional_nodes[0]);
}
// node is the root - add level
else
@@ -304,9 +337,7 @@
size_t & m_leafs_level;
// traversing input parameters
- internal_node *m_parent;
- size_t m_current_child_index;
- size_t m_current_level;
+ insert_traverse_data<internal_node> m_traverse_data;
Allocators & m_allocators;
};
@@ -315,13 +346,14 @@
// Insert visitor forward declaration
template <typename Element, typename Value, typename Options, typename Translator, typename Box, typename Allocators, typename InsertTag>
-struct insert;
+class insert;
// Default insert visitor used for nodes elements
template <typename Element, typename Value, typename Options, typename Translator, typename Box, typename Allocators>
-struct insert<Element, Value, Options, Translator, Box, Allocators, insert_default_tag>
+class insert<Element, Value, Options, Translator, Box, Allocators, insert_default_tag>
: public detail::insert<Element, Value, Options, Translator, Box, Allocators>
{
+public:
typedef detail::insert<Element, Value, Options, Translator, Box, Allocators> base;
typedef typename base::node node;
typedef typename base::internal_node internal_node;
@@ -342,16 +374,16 @@
inline void operator()(internal_node & n)
{
- BOOST_GEOMETRY_INDEX_ASSERT(base::m_current_level < base::m_leafs_level, "unexpected level");
+ BOOST_GEOMETRY_INDEX_ASSERT(base::m_traverse_data.current_level < base::m_leafs_level, "unexpected level");
- if ( base::m_current_level < base::m_level )
+ if ( base::m_traverse_data.current_level < base::m_level )
{
// next traversing step
base::traverse(*this, n);
}
else
{
- BOOST_GEOMETRY_INDEX_ASSERT(base::m_level == base::m_current_level, "unexpected level");
+ BOOST_GEOMETRY_INDEX_ASSERT(base::m_level == base::m_traverse_data.current_level, "unexpected level");
// push new child node
rtree::elements(n).push_back(base::m_element);
@@ -368,9 +400,10 @@
// Default insert visitor specialized for Values elements
template <typename Value, typename Options, typename Translator, typename Box, typename Allocators>
-struct insert<Value, Value, Options, Translator, Box, Allocators, insert_default_tag>
+class insert<Value, Value, Options, Translator, Box, Allocators, insert_default_tag>
: public detail::insert<Value, Value, Options, Translator, Box, Allocators>
{
+public:
typedef detail::insert<Value, Value, Options, Translator, Box, Allocators> base;
typedef typename base::node node;
typedef typename base::internal_node internal_node;
@@ -391,8 +424,8 @@
inline void operator()(internal_node & n)
{
- BOOST_GEOMETRY_INDEX_ASSERT(base::m_current_level < base::m_leafs_level, "unexpected level");
- BOOST_GEOMETRY_INDEX_ASSERT(base::m_current_level < base::m_level, "unexpected level");
+ BOOST_GEOMETRY_INDEX_ASSERT(base::m_traverse_data.current_level < base::m_leafs_level, "unexpected level");
+ BOOST_GEOMETRY_INDEX_ASSERT(base::m_traverse_data.current_level < base::m_level, "unexpected level");
// next traversing step
base::traverse(*this, n);
@@ -402,8 +435,9 @@
inline void operator()(leaf & n)
{
- BOOST_GEOMETRY_INDEX_ASSERT(base::m_current_level == base::m_leafs_level, "unexpected level");
- BOOST_GEOMETRY_INDEX_ASSERT(base::m_level == base::m_current_level || base::m_level == (std::numeric_limits<size_t>::max)(), "unexpected level");
+ BOOST_GEOMETRY_INDEX_ASSERT(base::m_traverse_data.current_level == base::m_leafs_level, "unexpected level");
+ BOOST_GEOMETRY_INDEX_ASSERT(base::m_level == base::m_traverse_data.current_level ||
+ base::m_level == (std::numeric_limits<size_t>::max)(), "unexpected level");
rtree::elements(n).push_back(base::m_element);
Modified: sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/nearest.hpp
==============================================================================
--- sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/nearest.hpp (original)
+++ sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/visitors/nearest.hpp 2012-10-04 05:37:39 EDT (Thu, 04 Oct 2012)
@@ -112,7 +112,11 @@
inline distance_type comparable_distance() const
{
- return m_neighbors.size() < 0
+ // smallest distance is in the first neighbor only
+ // if there is at least m_count values found
+ // this is just for safety reasons since is_comparable_distance_valid() is checked earlier
+ // TODO - may be replaced by ASSERT
+ return m_neighbors.size() < m_count
? (std::numeric_limits<distance_type>::max)()
: m_neighbors.front().first;
}
Modified: sandbox-branches/geometry/index/test/rtree/test_rtree.hpp
==============================================================================
--- sandbox-branches/geometry/index/test/rtree/test_rtree.hpp (original)
+++ sandbox-branches/geometry/index/test/rtree/test_rtree.hpp 2012-10-04 05:37:39 EDT (Thu, 04 Oct 2012)
@@ -21,6 +21,32 @@
#include <boost/geometry/extensions/index/rtree/visitors/are_levels_ok.hpp>
#include <boost/geometry/extensions/index/rtree/visitors/are_boxes_ok.hpp>
+// Set point's coordinates
+
+template <typename Point>
+struct generate_outside_point
+{};
+
+template <typename T, typename C>
+struct generate_outside_point< bg::model::point<T, 2, C> >
+{
+ typedef bg::model::point<T, 2, C> P;
+ static P apply()
+ {
+ return P(13, 26);
+ }
+};
+
+template <typename T, typename C>
+struct generate_outside_point< bg::model::point<T, 3, C> >
+{
+ typedef bg::model::point<T, 3, C> P;
+ static P apply()
+ {
+ return P(13, 26, 13);
+ }
+};
+
// Values, input and rtree generation
template <typename Value>
@@ -480,6 +506,21 @@
}
}
+// rtree nearest not found
+
+template <typename Rtree, typename Point, typename CoordinateType>
+void test_nearest_not_found(Rtree const& rtree, Point const& pt, CoordinateType max_distance_1, CoordinateType max_distance_k)
+{
+ typename Rtree::value_type output;
+ size_t n_res = rtree.nearest(bgi::max_bounded(pt, max_distance_1), output);
+ BOOST_CHECK(0 == n_res);
+
+ std::vector<typename Rtree::value_type> output_v;
+ n_res = rtree.nearest(bgi::max_bounded(pt, max_distance_k), 5, std::back_inserter(output_v));
+ BOOST_CHECK(output_v.size() == n_res);
+ BOOST_CHECK(n_res < 5);
+}
+
// rtree copying and moving
template <typename Value, typename Algo, typename Box>
@@ -580,6 +621,7 @@
test_nearest(tree, input, pt);
test_nearest_k(tree, input, pt, 10);
+ test_nearest_not_found(tree, generate_outside_point<P>::apply(), 1, 3);
test_copy_assignment_move(tree, qbox);
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