1 // -*- C++ -*-
2 
3 // Copyright (C) 2005, 2006, 2009, 2010 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
368