]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | // Boost.Geometry Index |
2 | // | |
3 | // R-tree iterator visitor implementation | |
4 | // | |
5 | // Copyright (c) 2011-2015 Adam Wulkiewicz, Lodz, Poland. | |
6 | // | |
1e59de90 TL |
7 | // This file was modified by Oracle on 2021. |
8 | // Modifications copyright (c) 2021 Oracle and/or its affiliates. | |
9 | // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle | |
10 | // | |
7c673cae FG |
11 | // Use, modification and distribution is subject to the Boost Software License, |
12 | // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at | |
13 | // http://www.boost.org/LICENSE_1_0.txt) | |
14 | ||
15 | #ifndef BOOST_GEOMETRY_INDEX_DETAIL_RTREE_VISITORS_ITERATOR_HPP | |
16 | #define BOOST_GEOMETRY_INDEX_DETAIL_RTREE_VISITORS_ITERATOR_HPP | |
17 | ||
1e59de90 TL |
18 | #include <boost/geometry/index/detail/rtree/node/concept.hpp> |
19 | #include <boost/geometry/index/detail/rtree/node/node_elements.hpp> | |
20 | ||
7c673cae FG |
21 | namespace boost { namespace geometry { namespace index { |
22 | ||
23 | namespace detail { namespace rtree { namespace visitors { | |
24 | ||
25 | template <typename Value, typename Options, typename Translator, typename Box, typename Allocators> | |
26 | class iterator | |
27 | : public rtree::visitor<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag, true>::type | |
28 | { | |
29 | public: | |
30 | typedef typename rtree::node<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type node; | |
31 | typedef typename rtree::internal_node<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type internal_node; | |
32 | typedef typename rtree::leaf<Value, typename Options::parameters_type, Box, Allocators, typename Options::node_tag>::type leaf; | |
33 | ||
34 | typedef typename Allocators::size_type size_type; | |
35 | typedef typename Allocators::const_reference const_reference; | |
36 | typedef typename Allocators::node_pointer node_pointer; | |
37 | ||
38 | typedef typename rtree::elements_type<internal_node>::type::const_iterator internal_iterator; | |
39 | typedef typename rtree::elements_type<leaf>::type leaf_elements; | |
40 | typedef typename rtree::elements_type<leaf>::type::const_iterator leaf_iterator; | |
41 | ||
42 | inline iterator() | |
43 | : m_values(NULL) | |
44 | , m_current() | |
45 | {} | |
46 | ||
47 | inline void operator()(internal_node const& n) | |
48 | { | |
49 | typedef typename rtree::elements_type<internal_node>::type elements_type; | |
50 | elements_type const& elements = rtree::elements(n); | |
51 | ||
52 | m_internal_stack.push_back(std::make_pair(elements.begin(), elements.end())); | |
53 | } | |
54 | ||
55 | inline void operator()(leaf const& n) | |
56 | { | |
57 | m_values = ::boost::addressof(rtree::elements(n)); | |
58 | m_current = rtree::elements(n).begin(); | |
59 | } | |
60 | ||
61 | const_reference dereference() const | |
62 | { | |
63 | BOOST_GEOMETRY_INDEX_ASSERT(m_values, "not dereferencable"); | |
64 | return *m_current; | |
65 | } | |
66 | ||
67 | void initialize(node_pointer root) | |
68 | { | |
69 | rtree::apply_visitor(*this, *root); | |
70 | search_value(); | |
71 | } | |
72 | ||
73 | void increment() | |
74 | { | |
75 | ++m_current; | |
76 | search_value(); | |
77 | } | |
78 | ||
79 | void search_value() | |
80 | { | |
81 | for (;;) | |
82 | { | |
83 | // if leaf is choosen, move to the next value in leaf | |
84 | if ( m_values ) | |
85 | { | |
86 | // there are more values in the current leaf | |
87 | if ( m_current != m_values->end() ) | |
88 | { | |
89 | return; | |
90 | } | |
91 | // no more values, clear current leaf | |
92 | else | |
93 | { | |
94 | m_values = 0; | |
95 | } | |
96 | } | |
97 | // if leaf isn't choosen, move to the next leaf | |
98 | else | |
99 | { | |
100 | // return if there is no more nodes to traverse | |
101 | if ( m_internal_stack.empty() ) | |
102 | return; | |
103 | ||
104 | // no more children in current node, remove it from stack | |
105 | if ( m_internal_stack.back().first == m_internal_stack.back().second ) | |
106 | { | |
107 | m_internal_stack.pop_back(); | |
108 | continue; | |
109 | } | |
110 | ||
111 | internal_iterator it = m_internal_stack.back().first; | |
112 | ++m_internal_stack.back().first; | |
113 | ||
114 | // push the next node to the stack | |
115 | rtree::apply_visitor(*this, *(it->second)); | |
116 | } | |
117 | } | |
118 | } | |
119 | ||
120 | bool is_end() const | |
121 | { | |
122 | return 0 == m_values; | |
123 | } | |
124 | ||
125 | friend bool operator==(iterator const& l, iterator const& r) | |
126 | { | |
127 | return (l.m_values == r.m_values) && (0 == l.m_values || l.m_current == r.m_current ); | |
128 | } | |
129 | ||
130 | private: | |
131 | ||
132 | std::vector< std::pair<internal_iterator, internal_iterator> > m_internal_stack; | |
133 | const leaf_elements * m_values; | |
134 | leaf_iterator m_current; | |
135 | }; | |
136 | ||
137 | }}} // namespace detail::rtree::visitors | |
138 | ||
139 | }}} // namespace boost::geometry::index | |
140 | ||
141 | #endif // BOOST_GEOMETRY_INDEX_DETAIL_RTREE_VISITORS_ITERATOR_HPP |