libstdc++
point_iterators.hpp
Go to the documentation of this file.
1 // -*- C++ -*-
2 
3 // Copyright (C) 2005-2022 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 
47 namespace __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
std::true_type
integral_constant< bool, true > true_type
The type used as a compile-time boolean with true value.
Definition: type_traits:82
__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