Subject: [Boost-commit] svn:boost r84029 - trunk/boost/geometry/index/detail/rtree/visitors
From: adam.wulkiewicz_at_[hidden]
Date: 2013-04-24 07:22:37
Author: awulkiew
Date: 2013-04-24 07:22:36 EDT (Wed, 24 Apr 2013)
New Revision: 84029
URL: http://svn.boost.org/trac/boost/changeset/84029
Log:
geometry.index: experimental nearest iterative visitor optimized (different data structures, less complex algorithm).
Text files modified:
trunk/boost/geometry/index/detail/rtree/visitors/nearest_query.hpp | 96 ++++++++++++++++++++++++++++-----------
1 files changed, 69 insertions(+), 27 deletions(-)
Modified: trunk/boost/geometry/index/detail/rtree/visitors/nearest_query.hpp
==============================================================================
--- trunk/boost/geometry/index/detail/rtree/visitors/nearest_query.hpp (original)
+++ trunk/boost/geometry/index/detail/rtree/visitors/nearest_query.hpp 2013-04-24 07:22:36 EDT (Wed, 24 Apr 2013)
@@ -353,6 +353,7 @@
typedef index::detail::distances_calc<distance_predicates_type, Box, index::detail::bounds_tag> node_distances_calc;
typedef typename node_distances_calc::result_type node_distances_type;
typedef index::detail::distances_predicates_check<distance_predicates_type, Box, index::detail::bounds_tag> node_distances_predicates_check;
+ typedef typename index::detail::cdist_value<node_distances_type>::type node_distance_type;
typedef index::detail::distances_calc<
distance_predicates_type,
@@ -369,15 +370,26 @@
typedef typename Allocators::size_type size_type;
typedef typename Allocators::node_pointer node_pointer;
- typedef typename rtree::elements_type<internal_node>::type::const_iterator internal_iterator;
+ static const unsigned predicates_len = index::detail::predicates_length<Predicates>::value;
+
+ typedef typename rtree::elements_type<internal_node>::type internal_elements;
+ typedef typename internal_elements::const_iterator internal_iterator;
typedef typename rtree::elements_type<leaf>::type leaf_elements;
- static const unsigned predicates_len = index::detail::predicates_length<Predicates>::value;
+ typedef std::pair<node_distances_type, node_pointer> branch_data;
+ typedef typename index::detail::rtree::container_from_elements_type<
+ internal_elements, branch_data
+ >::type active_branch_list_type;
+ typedef std::vector<
+ std::pair<active_branch_list_type, typename active_branch_list_type::size_type>
+ > internal_stack_type;
inline nearest_query_incremental(Translator const& translator, Predicates const& pred)
: m_translator(translator)
, m_pred(pred)
, current_neighbor(std::numeric_limits<size_type>::max())
+
+ , next_closest_node_distance(std::numeric_limits<node_distance_type>::max())
{
BOOST_ASSERT_MSG(0 < max_count(), "k must be greather than 0");
}
@@ -393,7 +405,7 @@
{
size_type new_neighbor = current_neighbor == std::numeric_limits<size_type>::max() ? 0 : current_neighbor + 1;
- if ( active_branch_list.empty() )
+ if ( internal_stack.empty() )
{
if ( new_neighbor < neighbors.size() )
current_neighbor = new_neighbor;
@@ -408,28 +420,41 @@
}
else
{
+ active_branch_list_type & branches = internal_stack.back().first;
+ typename active_branch_list_type::size_type & current_branch = internal_stack.back().second;
+
+ if ( branches.size() <= current_branch )
+ {
+ internal_stack.pop_back();
+ continue;
+ }
+
// if there are no nodes which can have closer values, set new value
if ( new_neighbor < neighbors.size() &&
- is_node_further(neighbors[new_neighbor].first, active_branch_list.front().first) )
+ // here must be < because otherwise neighbours may be sorted in different order
+ // if there is another value with equal distance
+ neighbors[new_neighbor].first < next_closest_node_distance )
{
current_neighbor = new_neighbor;
return;
}
- std::pair<node_distances_type, node_pointer> active_branch = active_branch_list.front();
- active_branch_list.pop_front();
- rtree::apply_visitor(*this, *(active_branch.second));
-
- // remove nodes further than the furthest neighbour - not really needed
+ // if node is further than the furthest neighbour, following nodes also will be further
BOOST_ASSERT_MSG(neighbors.size() <= max_count(), "unexpected neighbours count");
- if ( max_count() <= neighbors.size() )
+ if ( max_count() <= neighbors.size() &&
+ is_node_prunable(neighbors.back().first, branches[current_branch].first) )
{
- // prune nodes which mindists are further than furthest value's dist
- while ( !active_branch_list.empty() &&
- is_node_prunable(neighbors.back().first, active_branch_list.back().first) )
- {
- active_branch_list.pop_back();
- }
+ // stop traversing current level
+ internal_stack.pop_back();
+ continue;
+ }
+ else
+ {
+ // new level - must increment current_branch before traversing of another level (mem reallocation)
+ ++current_branch;
+ rtree::apply_visitor(*this, *(branches[current_branch - 1].second));
+
+ next_closest_node_distance = calc_closest_node_distance(internal_stack.begin(), internal_stack.end());
}
}
}
@@ -452,6 +477,8 @@
typedef typename rtree::elements_type<internal_node>::type elements_type;
elements_type const& elements = rtree::elements(n);
+ internal_stack.push_back(std::make_pair(active_branch_list_type(), 0));
+
// fill active branch list array of nodes meeting predicates
for ( typename elements_type::const_iterator it = elements.begin() ; it != elements.end() ; ++it )
{
@@ -473,13 +500,16 @@
if ( node_distances_predicates_check::apply(dist_pred(), node_dist_data) )
{
// add current node's data into the list
- active_branch_list.push_front( std::make_pair(node_dist_data, it->second) );
+ internal_stack.back().first.push_back( std::make_pair(node_dist_data, it->second) );
}
}
}
- // sort array
- std::sort(active_branch_list.begin(), active_branch_list.end(), abl_less);
+ if ( internal_stack.back().first.empty() )
+ internal_stack.pop_back();
+ else
+ // sort array
+ std::sort(internal_stack.back().first.begin(), internal_stack.back().first.end(), abl_less);
}
// Put values into the list of neighbours if those values meets predicates
@@ -543,18 +573,29 @@
return p1.first < p2.first;
}
- template <typename Distance>
- static inline bool is_node_prunable(Distance const& greatest_dist, node_distances_type const& d)
+ node_distance_type
+ calc_closest_node_distance(typename internal_stack_type::const_iterator first,
+ typename internal_stack_type::const_iterator last)
{
- return greatest_dist <= index::detail::cdist_value<node_distances_type>
- ::template get<index::detail::to_nearest_tag>(d);
+ node_distance_type result = std::numeric_limits<node_distance_type>::max();
+ for ( ; first != last ; ++first )
+ {
+ if ( first->first.size() <= first->second )
+ continue;
+
+ node_distance_type curr_dist = index::detail::cdist_value<node_distances_type>
+ ::template get<index::detail::to_nearest_tag>(first->first[first->second].first);
+ if ( curr_dist < result )
+ result = curr_dist;
+ }
+ return result;
}
template <typename Distance>
- static inline bool is_node_further(Distance const& dist, node_distances_type const& d)
+ static inline bool is_node_prunable(Distance const& greatest_dist, node_distances_type const& d)
{
- return dist <= index::detail::cdist_value<node_distances_type>
- ::template get<index::detail::to_nearest_tag>(d);
+ return greatest_dist <= index::detail::cdist_value<node_distances_type>
+ ::template get<index::detail::to_nearest_tag>(d);
}
inline distance_predicates_type const& dist_pred() const
@@ -571,9 +612,10 @@
Predicates m_pred;
- std::deque< std::pair<node_distances_type, node_pointer> > active_branch_list;
+ internal_stack_type internal_stack;
std::vector< std::pair<value_distance_type, const Value *> > neighbors;
size_type current_neighbor;
+ node_distance_type next_closest_node_distance;
};
} // namespace visitors