]>
Commit | Line | Data |
---|---|---|
4569a895 AT |
1 | // -*- C++ -*- |
2 | ||
818ab71a | 3 | // Copyright (C) 2005-2016 Free Software Foundation, Inc. |
4569a895 AT |
4 | // |
5 | // This file is part of the GNU ISO C++ Library. This library is free | |
6 | // software; you can redistribute it and/or modify it under the terms | |
7 | // of the GNU General Public License as published by the Free Software | |
748086b7 | 8 | // Foundation; either version 3, or (at your option) any later |
4569a895 AT |
9 | // version. |
10 | ||
11 | // This library is distributed in the hope that it will be useful, but | |
12 | // WITHOUT ANY WARRANTY; without even the implied warranty of | |
13 | // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
14 | // General Public License for more details. | |
15 | ||
748086b7 JJ |
16 | // Under Section 7 of GPL version 3, you are granted additional |
17 | // permissions described in the GCC Runtime Library Exception, version | |
18 | // 3.1, as published by the Free Software Foundation. | |
4569a895 | 19 | |
748086b7 JJ |
20 | // You should have received a copy of the GNU General Public License and |
21 | // a copy of the GCC Runtime Library Exception along with this program; | |
22 | // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see | |
23 | // <http://www.gnu.org/licenses/>. | |
4569a895 AT |
24 | |
25 | // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. | |
26 | ||
27 | // Permission to use, copy, modify, sell, and distribute this software | |
28 | // is hereby granted without fee, provided that the above copyright | |
29 | // notice appears in all copies, and that both that copyright notice | |
30 | // and this permission notice appear in supporting documentation. None | |
31 | // of the above authors, nor IBM Haifa Research Laboratories, make any | |
32 | // representation about the suitability of this software for any | |
33 | // purpose. It is provided "as is" without express or implied | |
34 | // warranty. | |
35 | ||
36 | /** | |
a345e45d | 37 | * @file ov_tree_map_/node_iterators.hpp |
4569a895 AT |
38 | * Contains an implementation class for ov_tree_. |
39 | */ | |
40 | ||
41 | #ifndef PB_DS_OV_TREE_NODE_ITERATORS_HPP | |
42 | #define PB_DS_OV_TREE_NODE_ITERATORS_HPP | |
43 | ||
4569a895 AT |
44 | #include <ext/pb_ds/tag_and_trait.hpp> |
45 | #include <ext/pb_ds/detail/type_utils.hpp> | |
47bea7b8 | 46 | #include <debug/debug.h> |
4569a895 | 47 | |
5e11f978 | 48 | namespace __gnu_pbds |
4569a895 AT |
49 | { |
50 | namespace detail | |
51 | { | |
e894edef | 52 | #define PB_DS_OV_TREE_CONST_NODE_ITERATOR_C_DEC \ |
a345e45d | 53 | ov_tree_node_const_it_<Value_Type, Metadata_Type, _Alloc> |
4569a895 | 54 | |
a345e45d BK |
55 | /// Const node reference. |
56 | template<typename Value_Type, typename Metadata_Type, typename _Alloc> | |
4569a895 AT |
57 | class ov_tree_node_const_it_ |
58 | { | |
59 | ||
60 | protected: | |
61 | typedef | |
a345e45d | 62 | typename _Alloc::template rebind< |
4569a895 AT |
63 | Value_Type>::other::pointer |
64 | pointer; | |
65 | ||
66 | typedef | |
a345e45d | 67 | typename _Alloc::template rebind< |
4569a895 AT |
68 | Value_Type>::other::const_pointer |
69 | const_pointer; | |
70 | ||
71 | typedef | |
a345e45d | 72 | typename _Alloc::template rebind< |
4569a895 AT |
73 | Metadata_Type>::other::const_pointer |
74 | const_metadata_pointer; | |
75 | ||
76 | typedef PB_DS_OV_TREE_CONST_NODE_ITERATOR_C_DEC this_type; | |
77 | ||
78 | protected: | |
79 | ||
80 | template<typename Ptr> | |
81 | inline static Ptr | |
82 | mid_pointer(Ptr p_begin, Ptr p_end) | |
83 | { | |
47bea7b8 | 84 | _GLIBCXX_DEBUG_ASSERT(p_end >= p_begin); |
4569a895 AT |
85 | return (p_begin + (p_end - p_begin) / 2); |
86 | } | |
87 | ||
88 | public: | |
89 | ||
90 | typedef trivial_iterator_tag iterator_category; | |
91 | ||
92 | typedef trivial_iterator_difference_type difference_type; | |
93 | ||
94 | typedef | |
a345e45d | 95 | typename _Alloc::template rebind< |
4569a895 AT |
96 | Value_Type>::other::const_pointer |
97 | value_type; | |
98 | ||
99 | typedef | |
a345e45d | 100 | typename _Alloc::template rebind< |
4569a895 AT |
101 | typename remove_const< |
102 | Value_Type>::type>::other::const_pointer | |
103 | reference; | |
104 | ||
105 | typedef | |
a345e45d | 106 | typename _Alloc::template rebind< |
4569a895 AT |
107 | typename remove_const< |
108 | Value_Type>::type>::other::const_pointer | |
109 | const_reference; | |
110 | ||
111 | typedef Metadata_Type metadata_type; | |
112 | ||
113 | typedef | |
a345e45d | 114 | typename _Alloc::template rebind< |
4569a895 | 115 | metadata_type>::other::const_reference |
a345e45d | 116 | metadata_const_reference; |
4569a895 AT |
117 | |
118 | public: | |
119 | inline | |
8fc81078 | 120 | ov_tree_node_const_it_(const_pointer p_nd = 0, const_pointer p_begin_nd = 0, const_pointer p_end_nd = 0, const_metadata_pointer p_metadata = 0) : m_p_value(const_cast<pointer>(p_nd)), m_p_begin_value(const_cast<pointer>(p_begin_nd)), m_p_end_value(const_cast<pointer>(p_end_nd)), m_p_metadata(p_metadata) |
4569a895 AT |
121 | { } |
122 | ||
123 | inline const_reference | |
124 | operator*() const | |
47bea7b8 | 125 | { return m_p_value; } |
4569a895 | 126 | |
a345e45d | 127 | inline metadata_const_reference |
4569a895 AT |
128 | get_metadata() const |
129 | { | |
130 | enum | |
131 | { | |
a345e45d | 132 | has_metadata = !is_same<Metadata_Type, null_type>::value |
4569a895 AT |
133 | }; |
134 | ||
135 | PB_DS_STATIC_ASSERT(should_have_metadata, has_metadata); | |
8fc81078 | 136 | _GLIBCXX_DEBUG_ASSERT(m_p_metadata != 0); |
47bea7b8 | 137 | return *m_p_metadata; |
4569a895 AT |
138 | } |
139 | ||
30a96b3b | 140 | /// Returns the node iterator associated with the left node. |
4569a895 AT |
141 | inline this_type |
142 | get_l_child() const | |
143 | { | |
144 | if (m_p_begin_value == m_p_value) | |
47bea7b8 | 145 | return (this_type(m_p_begin_value, m_p_begin_value, m_p_begin_value)); |
4569a895 AT |
146 | |
147 | const_metadata_pointer p_begin_metadata = | |
148 | m_p_metadata - (m_p_value - m_p_begin_value); | |
149 | ||
47bea7b8 | 150 | return (this_type(mid_pointer(m_p_begin_value, m_p_value), |
4569a895 AT |
151 | m_p_begin_value, |
152 | m_p_value, | |
153 | mid_pointer(p_begin_metadata, m_p_metadata))); | |
154 | } | |
155 | ||
30a96b3b | 156 | /// Returns the node iterator associated with the right node. |
4569a895 AT |
157 | inline this_type |
158 | get_r_child() const | |
159 | { | |
160 | if (m_p_value == m_p_end_value) | |
30a96b3b | 161 | return (this_type(m_p_end_value, m_p_end_value, m_p_end_value)); |
4569a895 AT |
162 | |
163 | const_metadata_pointer p_end_metadata = | |
164 | m_p_metadata + (m_p_end_value - m_p_value); | |
165 | ||
47bea7b8 | 166 | return (this_type(mid_pointer(m_p_value + 1, m_p_end_value), |
4569a895 | 167 | m_p_value + 1, |
8fc81078 PC |
168 | m_p_end_value,(m_p_metadata == 0) ? |
169 | 0 : mid_pointer(m_p_metadata + 1, p_end_metadata))); | |
4569a895 AT |
170 | } |
171 | ||
172 | inline bool | |
173 | operator==(const this_type& other) const | |
174 | { | |
175 | const bool is_end = m_p_begin_value == m_p_end_value; | |
176 | const bool is_other_end = other.m_p_begin_value == other.m_p_end_value; | |
177 | ||
178 | if (is_end) | |
179 | return (is_other_end); | |
180 | ||
181 | if (is_other_end) | |
182 | return (is_end); | |
183 | ||
47bea7b8 | 184 | return m_p_value == other.m_p_value; |
4569a895 AT |
185 | } |
186 | ||
187 | inline bool | |
188 | operator!=(const this_type& other) const | |
47bea7b8 | 189 | { return !operator==(other); } |
4569a895 AT |
190 | |
191 | public: | |
192 | pointer m_p_value; | |
193 | pointer m_p_begin_value; | |
194 | pointer m_p_end_value; | |
195 | ||
196 | const_metadata_pointer m_p_metadata; | |
197 | }; | |
198 | ||
e894edef | 199 | #define PB_DS_OV_TREE_NODE_ITERATOR_C_DEC \ |
a345e45d | 200 | ov_tree_node_it_<Value_Type, Metadata_Type, _Alloc> |
4569a895 | 201 | |
a345e45d BK |
202 | /// Node reference. |
203 | template<typename Value_Type, typename Metadata_Type, typename _Alloc> | |
4569a895 AT |
204 | class ov_tree_node_it_ : public PB_DS_OV_TREE_CONST_NODE_ITERATOR_C_DEC |
205 | { | |
4569a895 AT |
206 | private: |
207 | typedef PB_DS_OV_TREE_NODE_ITERATOR_C_DEC this_type; | |
208 | ||
209 | typedef PB_DS_OV_TREE_CONST_NODE_ITERATOR_C_DEC base_type; | |
210 | ||
211 | typedef typename base_type::pointer pointer; | |
212 | ||
213 | typedef typename base_type::const_pointer const_pointer; | |
214 | ||
215 | typedef | |
216 | typename base_type::const_metadata_pointer | |
217 | const_metadata_pointer; | |
218 | ||
219 | public: | |
4569a895 AT |
220 | typedef trivial_iterator_tag iterator_category; |
221 | ||
222 | typedef trivial_iterator_difference_type difference_type; | |
223 | ||
224 | typedef | |
a345e45d | 225 | typename _Alloc::template rebind< |
4569a895 AT |
226 | Value_Type>::other::pointer |
227 | value_type; | |
228 | ||
229 | typedef | |
a345e45d | 230 | typename _Alloc::template rebind< |
4569a895 AT |
231 | typename remove_const< |
232 | Value_Type>::type>::other::pointer | |
233 | reference; | |
234 | ||
235 | typedef | |
a345e45d | 236 | typename _Alloc::template rebind< |
4569a895 AT |
237 | typename remove_const< |
238 | Value_Type>::type>::other::pointer | |
239 | const_reference; | |
240 | ||
4569a895 | 241 | inline |
8fc81078 | 242 | ov_tree_node_it_(const_pointer p_nd = 0, const_pointer p_begin_nd = 0, const_pointer p_end_nd = 0, const_metadata_pointer p_metadata = 0) : base_type(p_nd, p_begin_nd, p_end_nd, p_metadata) |
4569a895 AT |
243 | { } |
244 | ||
30a96b3b | 245 | /// Access. |
4569a895 AT |
246 | inline reference |
247 | operator*() const | |
47bea7b8 | 248 | { return reference(base_type::m_p_value); } |
4569a895 | 249 | |
30a96b3b | 250 | /// Returns the node reference associated with the left node. |
4569a895 AT |
251 | inline ov_tree_node_it_ |
252 | get_l_child() const | |
253 | { | |
254 | if (base_type::m_p_begin_value == base_type::m_p_value) | |
47bea7b8 | 255 | return (this_type(base_type::m_p_begin_value, base_type::m_p_begin_value, base_type::m_p_begin_value)); |
4569a895 AT |
256 | |
257 | const_metadata_pointer p_begin_metadata = | |
258 | base_type::m_p_metadata - (base_type::m_p_value - base_type::m_p_begin_value); | |
259 | ||
47bea7b8 | 260 | return (this_type(base_type::mid_pointer(base_type::m_p_begin_value, base_type::m_p_value), |
4569a895 AT |
261 | base_type::m_p_begin_value, |
262 | base_type::m_p_value, | |
263 | base_type::mid_pointer(p_begin_metadata, base_type::m_p_metadata))); | |
264 | } | |
265 | ||
30a96b3b | 266 | /// Returns the node reference associated with the right node. |
4569a895 AT |
267 | inline ov_tree_node_it_ |
268 | get_r_child() const | |
269 | { | |
270 | if (base_type::m_p_value == base_type::m_p_end_value) | |
30a96b3b | 271 | return this_type(base_type::m_p_end_value, base_type::m_p_end_value, |
a345e45d | 272 | base_type::m_p_end_value); |
4569a895 AT |
273 | |
274 | const_metadata_pointer p_end_metadata = | |
275 | base_type::m_p_metadata + (base_type::m_p_end_value - base_type::m_p_value); | |
276 | ||
47bea7b8 | 277 | return (this_type(base_type::mid_pointer(base_type::m_p_value + 1, base_type::m_p_end_value), |
4569a895 | 278 | base_type::m_p_value + 1, |
8fc81078 PC |
279 | base_type::m_p_end_value,(base_type::m_p_metadata == 0)? |
280 | 0 : base_type::mid_pointer(base_type::m_p_metadata + 1, p_end_metadata))); | |
4569a895 AT |
281 | } |
282 | ||
283 | }; | |
284 | ||
285 | #undef PB_DS_OV_TREE_NODE_ITERATOR_C_DEC | |
4569a895 | 286 | #undef PB_DS_OV_TREE_CONST_NODE_ITERATOR_C_DEC |
4569a895 | 287 | |
47bea7b8 | 288 | } // namespace detail |
5e11f978 | 289 | } // namespace __gnu_pbds |
4569a895 | 290 | |
47bea7b8 | 291 | #endif |