// Boost.Geometry Index
|
//
|
// R-tree iterator visitor implementation
|
//
|
// Copyright (c) 2011-2015 Adam Wulkiewicz, Lodz, Poland.
|
//
|
// 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_INDEX_DETAIL_RTREE_VISITORS_ITERATOR_HPP
|
#define BOOST_GEOMETRY_INDEX_DETAIL_RTREE_VISITORS_ITERATOR_HPP
|
|
namespace boost { namespace geometry { namespace index {
|
|
namespace detail { namespace rtree { namespace visitors {
|
|
template <typename Value, typename Options, typename Translator, typename Box, typename Allocators>
|
class iterator
|
: public rtree::visitor<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag, true>::type
|
{
|
public:
|
typedef typename rtree::node<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type node;
|
typedef typename rtree::internal_node<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type internal_node;
|
typedef typename rtree::leaf<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type leaf;
|
|
typedef typename Allocators::size_type size_type;
|
typedef typename Allocators::const_reference const_reference;
|
typedef typename Allocators::node_pointer node_pointer;
|
|
typedef typename rtree::elements_type<internal_node>::type::const_iterator internal_iterator;
|
typedef typename rtree::elements_type<leaf>::type leaf_elements;
|
typedef typename rtree::elements_type<leaf>::type::const_iterator leaf_iterator;
|
|
inline iterator()
|
: m_values(NULL)
|
, m_current()
|
{}
|
|
inline void operator()(internal_node const& n)
|
{
|
typedef typename rtree::elements_type<internal_node>::type elements_type;
|
elements_type const& elements = rtree::elements(n);
|
|
m_internal_stack.push_back(std::make_pair(elements.begin(), elements.end()));
|
}
|
|
inline void operator()(leaf const& n)
|
{
|
m_values = ::boost::addressof(rtree::elements(n));
|
m_current = rtree::elements(n).begin();
|
}
|
|
const_reference dereference() const
|
{
|
BOOST_GEOMETRY_INDEX_ASSERT(m_values, "not dereferencable");
|
return *m_current;
|
}
|
|
void initialize(node_pointer root)
|
{
|
rtree::apply_visitor(*this, *root);
|
search_value();
|
}
|
|
void increment()
|
{
|
++m_current;
|
search_value();
|
}
|
|
void search_value()
|
{
|
for (;;)
|
{
|
// if leaf is choosen, move to the next value in leaf
|
if ( m_values )
|
{
|
// there are more values in the current leaf
|
if ( m_current != m_values->end() )
|
{
|
return;
|
}
|
// no more values, clear current leaf
|
else
|
{
|
m_values = 0;
|
}
|
}
|
// if leaf isn't choosen, move to the next leaf
|
else
|
{
|
// return if there is no more nodes to traverse
|
if ( m_internal_stack.empty() )
|
return;
|
|
// no more children in current node, remove it from stack
|
if ( m_internal_stack.back().first == m_internal_stack.back().second )
|
{
|
m_internal_stack.pop_back();
|
continue;
|
}
|
|
internal_iterator it = m_internal_stack.back().first;
|
++m_internal_stack.back().first;
|
|
// push the next node to the stack
|
rtree::apply_visitor(*this, *(it->second));
|
}
|
}
|
}
|
|
bool is_end() const
|
{
|
return 0 == m_values;
|
}
|
|
friend bool operator==(iterator const& l, iterator const& r)
|
{
|
return (l.m_values == r.m_values) && (0 == l.m_values || l.m_current == r.m_current );
|
}
|
|
private:
|
|
std::vector< std::pair<internal_iterator, internal_iterator> > m_internal_stack;
|
const leaf_elements * m_values;
|
leaf_iterator m_current;
|
};
|
|
}}} // namespace detail::rtree::visitors
|
|
}}} // namespace boost::geometry::index
|
|
#endif // BOOST_GEOMETRY_INDEX_DETAIL_RTREE_VISITORS_ITERATOR_HPP
|
