1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
|
// 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
|
