libstdc++
point_iterators.hpp
Go to the documentation of this file.
1// -*- C++ -*-
2
3// Copyright (C) 2005-2021 Free Software Foundation, Inc.
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
8// Foundation; either version 3, or (at your option) any later
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
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.
19
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/>.
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/**
37 * @file bin_search_tree_/point_iterators.hpp
38 * Contains an implementation class for bin_search_tree_.
39 */
40
41#ifndef PB_DS_BIN_SEARCH_TREE_FIND_ITERATORS_HPP
42#define PB_DS_BIN_SEARCH_TREE_FIND_ITERATORS_HPP
43
44#include <ext/pb_ds/tag_and_trait.hpp>
45#include <debug/debug.h>
46
47namespace __gnu_pbds
48{
49 namespace detail
50 {
51
52#define PB_DS_TREE_CONST_IT_C_DEC \
53 bin_search_tree_const_it_< \
54 Node_Pointer, \
55 Value_Type, \
56 Pointer, \
57 Const_Pointer, \
58 Reference, \
59 Const_Reference, \
60 Is_Forward_Iterator, \
61 _Alloc>
62
63#define PB_DS_TREE_CONST_ODIR_IT_C_DEC \
64 bin_search_tree_const_it_< \
65 Node_Pointer, \
66 Value_Type, \
67 Pointer, \
68 Const_Pointer, \
69 Reference, \
70 Const_Reference, \
71 !Is_Forward_Iterator, \
72 _Alloc>
73
74#define PB_DS_TREE_IT_C_DEC \
75 bin_search_tree_it_< \
76 Node_Pointer, \
77 Value_Type, \
78 Pointer, \
79 Const_Pointer, \
80 Reference, \
81 Const_Reference, \
82 Is_Forward_Iterator, \
83 _Alloc>
84
85#define PB_DS_TREE_ODIR_IT_C_DEC \
86 bin_search_tree_it_< \
87 Node_Pointer, \
88 Value_Type, \
89 Pointer, \
90 Const_Pointer, \
91 Reference, \
92 Const_Reference, \
93 !Is_Forward_Iterator, \
94 _Alloc>
95
96 /// Const iterator.
97 template<typename Node_Pointer,
98 typename Value_Type,
99 typename Pointer,
100 typename Const_Pointer,
101 typename Reference,
102 typename Const_Reference,
103 bool Is_Forward_Iterator,
104 typename _Alloc>
105 class bin_search_tree_const_it_
106 {
107 public:
108 typedef std::bidirectional_iterator_tag iterator_category;
109 typedef typename _Alloc::difference_type difference_type;
110 typedef Value_Type value_type;
111 typedef Pointer pointer;
112 typedef Const_Pointer const_pointer;
113 typedef Reference reference;
114 typedef Const_Reference const_reference;
115
116 inline
117 bin_search_tree_const_it_(const Node_Pointer p_nd = 0)
118 : m_p_nd(const_cast<Node_Pointer>(p_nd))
119 { }
120
121 inline
122 bin_search_tree_const_it_(const PB_DS_TREE_CONST_ODIR_IT_C_DEC& other)
123 : m_p_nd(other.m_p_nd)
124 { }
125
126 inline
127 PB_DS_TREE_CONST_IT_C_DEC&
128 operator=(const PB_DS_TREE_CONST_IT_C_DEC& other)
129 {
130 m_p_nd = other.m_p_nd;
131 return *this;
132 }
133
134 inline
135 PB_DS_TREE_CONST_IT_C_DEC&
136 operator=(const PB_DS_TREE_CONST_ODIR_IT_C_DEC& other)
137 {
138 m_p_nd = other.m_p_nd;
139 return *this;
140 }
141
142 inline const_pointer
143 operator->() const
144 {
145 _GLIBCXX_DEBUG_ASSERT(m_p_nd != 0);
146 return &m_p_nd->m_value;
147 }
148
149 inline const_reference
150 operator*() const
151 {
152 _GLIBCXX_DEBUG_ASSERT(m_p_nd != 0);
153 return m_p_nd->m_value;
154 }
155
156 inline bool
157 operator==(const PB_DS_TREE_CONST_IT_C_DEC & other) const
158 { return m_p_nd == other.m_p_nd; }
159
160 inline bool
161 operator==(const PB_DS_TREE_CONST_ODIR_IT_C_DEC & other) const
162 { return m_p_nd == other.m_p_nd; }
163
164 inline bool
165 operator!=(const PB_DS_TREE_CONST_IT_C_DEC& other) const
166 { return m_p_nd != other.m_p_nd; }
167
168 inline bool
169 operator!=(const PB_DS_TREE_CONST_ODIR_IT_C_DEC& other) const
170 { return m_p_nd != other.m_p_nd; }
171
172 inline PB_DS_TREE_CONST_IT_C_DEC&
173 operator++()
174 {
175 _GLIBCXX_DEBUG_ASSERT(m_p_nd != 0);
176 inc(integral_constant<int,Is_Forward_Iterator>());
177 return *this;
178 }
179
180 inline PB_DS_TREE_CONST_IT_C_DEC
181 operator++(int)
182 {
183 PB_DS_TREE_CONST_IT_C_DEC ret_it(m_p_nd);
184 operator++();
185 return ret_it;
186 }
187
188 inline PB_DS_TREE_CONST_IT_C_DEC&
189 operator--()
190 {
191 dec(integral_constant<int,Is_Forward_Iterator>());
192 return *this;
193 }
194
195 inline PB_DS_TREE_CONST_IT_C_DEC
196 operator--(int)
197 {
198 PB_DS_TREE_CONST_IT_C_DEC ret_it(m_p_nd);
199 operator--();
200 return ret_it;
201 }
202
203 protected:
204 inline void
205 inc(false_type)
206 { dec(true_type()); }
207
208 void
209 inc(true_type)
210 {
211 if (m_p_nd->special()&&
212 m_p_nd->m_p_parent->m_p_parent == m_p_nd)
213 {
214 m_p_nd = m_p_nd->m_p_left;
215 return;
216 }
217
218 if (m_p_nd->m_p_right != 0)
219 {
220 m_p_nd = m_p_nd->m_p_right;
221 while (m_p_nd->m_p_left != 0)
222 m_p_nd = m_p_nd->m_p_left;
223 return;
224 }
225
226 Node_Pointer p_y = m_p_nd->m_p_parent;
227 while (m_p_nd == p_y->m_p_right)
228 {
229 m_p_nd = p_y;
230 p_y = p_y->m_p_parent;
231 }
232
233 if (m_p_nd->m_p_right != p_y)
234 m_p_nd = p_y;
235 }
236
237 inline void
238 dec(false_type)
239 { inc(true_type()); }
240
241 void
242 dec(true_type)
243 {
244 if (m_p_nd->special() && m_p_nd->m_p_parent->m_p_parent == m_p_nd)
245 {
246 m_p_nd = m_p_nd->m_p_right;
247 return;
248 }
249
250 if (m_p_nd->m_p_left != 0)
251 {
252 Node_Pointer p_y = m_p_nd->m_p_left;
253 while (p_y->m_p_right != 0)
254 p_y = p_y->m_p_right;
255 m_p_nd = p_y;
256 return;
257 }
258
259 Node_Pointer p_y = m_p_nd->m_p_parent;
260 while (m_p_nd == p_y->m_p_left)
261 {
262 m_p_nd = p_y;
263 p_y = p_y->m_p_parent;
264 }
265 if (m_p_nd->m_p_left != p_y)
266 m_p_nd = p_y;
267 }
268
269 public:
270 Node_Pointer m_p_nd;
271 };
272
273 /// Iterator.
274 template<typename Node_Pointer,
275 typename Value_Type,
276 typename Pointer,
277 typename Const_Pointer,
278 typename Reference,
279 typename Const_Reference,
280 bool Is_Forward_Iterator,
281 typename _Alloc>
282 class bin_search_tree_it_ : public PB_DS_TREE_CONST_IT_C_DEC
283 {
284 public:
285 inline
286 bin_search_tree_it_(const Node_Pointer p_nd = 0)
287 : PB_DS_TREE_CONST_IT_C_DEC((Node_Pointer)p_nd)
288 { }
289
290 inline
291 bin_search_tree_it_(const PB_DS_TREE_ODIR_IT_C_DEC& other)
292 : PB_DS_TREE_CONST_IT_C_DEC(other.m_p_nd)
293 { }
294
295 inline
296 PB_DS_TREE_IT_C_DEC&
297 operator=(const PB_DS_TREE_IT_C_DEC& other)
298 {
299 base_it_type::m_p_nd = other.m_p_nd;
300 return *this;
301 }
302
303 inline
304 PB_DS_TREE_IT_C_DEC&
305 operator=(const PB_DS_TREE_ODIR_IT_C_DEC& other)
306 {
307 base_it_type::m_p_nd = other.m_p_nd;
308 return *this;
309 }
310
311 inline typename PB_DS_TREE_CONST_IT_C_DEC::pointer
312 operator->() const
313 {
314 _GLIBCXX_DEBUG_ASSERT(base_it_type::m_p_nd != 0);
315 return &base_it_type::m_p_nd->m_value;
316 }
317
318 inline typename PB_DS_TREE_CONST_IT_C_DEC::reference
319 operator*() const
320 {
321 _GLIBCXX_DEBUG_ASSERT(base_it_type::m_p_nd != 0);
322 return base_it_type::m_p_nd->m_value;
323 }
324
325 inline PB_DS_TREE_IT_C_DEC&
326 operator++()
327 {
328 PB_DS_TREE_CONST_IT_C_DEC:: operator++();
329 return *this;
330 }
331
332 inline PB_DS_TREE_IT_C_DEC
333 operator++(int)
334 {
335 PB_DS_TREE_IT_C_DEC ret_it(base_it_type::m_p_nd);
336 operator++();
337 return ret_it;
338 }
339
340 inline PB_DS_TREE_IT_C_DEC&
341 operator--()
342 {
343 PB_DS_TREE_CONST_IT_C_DEC:: operator--();
344 return *this;
345 }
346
347 inline PB_DS_TREE_IT_C_DEC
348 operator--(int)
349 {
350 PB_DS_TREE_IT_C_DEC ret_it(base_it_type::m_p_nd);
351 operator--();
352 return ret_it;
353 }
354
355 protected:
356 typedef PB_DS_TREE_CONST_IT_C_DEC base_it_type;
357 };
358
359#undef PB_DS_TREE_CONST_IT_C_DEC
360#undef PB_DS_TREE_CONST_ODIR_IT_C_DEC
361#undef PB_DS_TREE_IT_C_DEC
362#undef PB_DS_TREE_ODIR_IT_C_DEC
363
364 } // namespace detail
365} // namespace __gnu_pbds
366
367#endif
__gnu_pbds
GNU extensions for policy-based data structures for public use.
Definition: assoc_container.hpp:52
std::bidirectional_iterator_tag
Bidirectional iterators support a superset of forward iterator operations.
Definition: stl_iterator_base_types.h:103