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