1129511Spjd// -*- C++ -*-
2129511Spjd
3129511Spjd// Copyright (C) 2005, 2006 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 2, 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// You should have received a copy of the GNU General Public License
17// along with this library; see the file COPYING.  If not, write to
18// the Free Software Foundation, 59 Temple Place - Suite 330, Boston,
19// MA 02111-1307, USA.
20
21// As a special exception, you may use this file as part of a free
22// software library without restriction.  Specifically, if other files
23// instantiate templates or use macros or inline functions from this
24// file, or you compile this file and link it with other files to
25// produce an executable, this file does not by itself cause the
26// resulting executable to be covered by the GNU General Public
27// License.  This exception does not however invalidate any other
28// reasons why the executable file might be covered by the GNU General
29// Public License.
30
31// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
32
33// Permission to use, copy, modify, sell, and distribute this software
34// is hereby granted without fee, provided that the above copyright
35// notice appears in all copies, and that both that copyright notice
36// and this permission notice appear in supporting documentation. None
37// of the above authors, nor IBM Haifa Research Laboratories, make any
38// representation about the suitability of this software for any
39// purpose. It is provided "as is" without express or implied
40// warranty.
41
42/**
43 * @file point_iterators.hpp
44 * Contains an implementation class for bin_search_tree_.
45 */
46
47#ifndef PB_DS_BIN_SEARCH_TREE_FIND_ITERATORS_HPP
48#define PB_DS_BIN_SEARCH_TREE_FIND_ITERATORS_HPP
49
50#include <ext/pb_ds/tag_and_trait.hpp>
51#include <debug/debug.h>
52
53namespace pb_ds
54{
55  namespace detail
56  {
57
58#define PB_DS_TREE_CONST_IT_C_DEC					\
59    bin_search_tree_const_it_<						\
60						Node_Pointer,		\
61						Value_Type,		\
62						Pointer,		\
63						Const_Pointer,		\
64						Reference,		\
65						Const_Reference,	\
66						Is_Forward_Iterator,	\
67						Allocator>
68
69#define PB_DS_TREE_CONST_ODIR_IT_C_DEC					\
70    bin_search_tree_const_it_<						\
71						Node_Pointer,		\
72						Value_Type,		\
73						Pointer,		\
74						Const_Pointer,		\
75						Reference,		\
76						Const_Reference,	\
77						!Is_Forward_Iterator,	\
78						Allocator>
79
80#define PB_DS_TREE_IT_C_DEC						\
81    bin_search_tree_it_<						\
82						Node_Pointer,		\
83						Value_Type,		\
84						Pointer,		\
85						Const_Pointer,		\
86						Reference,		\
87						Const_Reference,	\
88						Is_Forward_Iterator,	\
89						Allocator>
90
91#define PB_DS_TREE_ODIR_IT_C_DEC					\
92    bin_search_tree_it_<						\
93							Node_Pointer,	\
94							Value_Type,	\
95							Pointer,	\
96							Const_Pointer,	\
97							Reference,	\
98							Const_Reference, \
99							!Is_Forward_Iterator, \
100							Allocator>
101
102    // Const iterator.
103    template<typename Node_Pointer,
104	     typename Value_Type,
105	     typename Pointer,
106	     typename Const_Pointer,
107	     typename Reference,
108	     typename Const_Reference,
109	     bool Is_Forward_Iterator,
110	     class Allocator>
111    class bin_search_tree_const_it_
112    {
113
114    public:
115
116      typedef std::bidirectional_iterator_tag iterator_category;
117
118      typedef typename Allocator::difference_type difference_type;
119
120      typedef Value_Type value_type;
121
122      typedef Pointer pointer;
123
124      typedef Const_Pointer const_pointer;
125
126      typedef Reference reference;
127
128      typedef Const_Reference const_reference;
129
130    public:
131
132      inline
133      bin_search_tree_const_it_(const Node_Pointer p_nd = NULL)
134      : m_p_nd(const_cast<Node_Pointer>(p_nd))
135      { }
136
137      inline
138      bin_search_tree_const_it_(const PB_DS_TREE_CONST_ODIR_IT_C_DEC& other)
139      : m_p_nd(other.m_p_nd)
140      { }
141
142      inline
143      PB_DS_TREE_CONST_IT_C_DEC&
144      operator=(const PB_DS_TREE_CONST_IT_C_DEC& other)
145      {
146	m_p_nd = other.m_p_nd;
147	return *this;
148      }
149
150      inline
151      PB_DS_TREE_CONST_IT_C_DEC&
152      operator=(const PB_DS_TREE_CONST_ODIR_IT_C_DEC& other)
153      {
154	m_p_nd = other.m_p_nd;
155	return *this;
156      }
157
158      inline const_pointer
159      operator->() const
160      {
161	_GLIBCXX_DEBUG_ASSERT(m_p_nd != NULL);
162	return &m_p_nd->m_value;
163      }
164
165      inline const_reference
166      operator*() const
167      {
168	_GLIBCXX_DEBUG_ASSERT(m_p_nd != NULL);
169	return m_p_nd->m_value;
170      }
171
172      inline bool
173      operator==(const PB_DS_TREE_CONST_IT_C_DEC & other) const
174      { return m_p_nd == other.m_p_nd; }
175
176      inline bool
177      operator==(const PB_DS_TREE_CONST_ODIR_IT_C_DEC & other) const
178      { return m_p_nd == other.m_p_nd; }
179
180      inline bool
181      operator!=(const PB_DS_TREE_CONST_IT_C_DEC& other) const
182      { return m_p_nd != other.m_p_nd; }
183
184      inline bool
185      operator!=(const PB_DS_TREE_CONST_ODIR_IT_C_DEC& other) const
186      { return m_p_nd != other.m_p_nd; }
187
188      inline PB_DS_TREE_CONST_IT_C_DEC&
189      operator++()
190      {
191	_GLIBCXX_DEBUG_ASSERT(m_p_nd != NULL);
192	inc(integral_constant<int,Is_Forward_Iterator>());
193	return *this;
194      }
195
196      inline PB_DS_TREE_CONST_IT_C_DEC
197      operator++(int)
198      {
199	PB_DS_TREE_CONST_IT_C_DEC ret_it(m_p_nd);
200	operator++();
201	return ret_it;
202      }
203
204      inline PB_DS_TREE_CONST_IT_C_DEC&
205      operator--()
206      {
207	dec(integral_constant<int,Is_Forward_Iterator>());
208	return *this;
209      }
210
211      inline PB_DS_TREE_CONST_IT_C_DEC
212      operator--(int)
213      {
214	PB_DS_TREE_CONST_IT_C_DEC ret_it(m_p_nd);
215	operator--();
216	return ret_it;
217      }
218
219    protected:
220      inline void
221      inc(false_type)
222      { dec(true_type()); }
223
224      void
225      inc(true_type)
226      {
227	if (m_p_nd->special()&&
228	    m_p_nd->m_p_parent->m_p_parent == m_p_nd)
229	  {
230	    m_p_nd = m_p_nd->m_p_left;
231	    return;
232	  }
233
234	if (m_p_nd->m_p_right != NULL)
235	  {
236	    m_p_nd = m_p_nd->m_p_right;
237	    while (m_p_nd->m_p_left != NULL)
238	      m_p_nd = m_p_nd->m_p_left;
239	    return;
240	  }
241
242	Node_Pointer p_y = m_p_nd->m_p_parent;
243	while (m_p_nd == p_y->m_p_right)
244	  {
245	    m_p_nd = p_y;
246	    p_y = p_y->m_p_parent;
247	  }
248
249	if (m_p_nd->m_p_right != p_y)
250	  m_p_nd = p_y;
251      }
252
253      inline void
254      dec(false_type)
255      { inc(true_type()); }
256
257      void
258      dec(true_type)
259      {
260	if (m_p_nd->special() && m_p_nd->m_p_parent->m_p_parent == m_p_nd)
261	  {
262	    m_p_nd = m_p_nd->m_p_right;
263	    return;
264	  }
265
266	if (m_p_nd->m_p_left != NULL)
267	  {
268	    Node_Pointer p_y = m_p_nd->m_p_left;
269	    while (p_y->m_p_right != NULL)
270	      p_y = p_y->m_p_right;
271	    m_p_nd = p_y;
272	    return;
273	  }
274
275	Node_Pointer p_y = m_p_nd->m_p_parent;
276	while (m_p_nd == p_y->m_p_left)
277	  {
278	    m_p_nd = p_y;
279	    p_y = p_y->m_p_parent;
280	  }
281	if (m_p_nd->m_p_left != p_y)
282	  m_p_nd = p_y;
283      }
284
285    public:
286      Node_Pointer m_p_nd;
287    };
288
289    // Iterator.
290    template<typename Node_Pointer,
291	     typename Value_Type,
292	     typename Pointer,
293	     typename Const_Pointer,
294	     typename Reference,
295	     typename Const_Reference,
296	     bool Is_Forward_Iterator,
297	     class Allocator>
298    class bin_search_tree_it_ :
299      public PB_DS_TREE_CONST_IT_C_DEC
300
301    {
302
303    public:
304
305      inline
306      bin_search_tree_it_(const Node_Pointer p_nd = NULL)
307      : PB_DS_TREE_CONST_IT_C_DEC((Node_Pointer)p_nd)
308      { }
309
310      inline
311      bin_search_tree_it_(const PB_DS_TREE_ODIR_IT_C_DEC& other)
312      : PB_DS_TREE_CONST_IT_C_DEC(other.m_p_nd)
313      { }
314
315      inline
316      PB_DS_TREE_IT_C_DEC&
317      operator=(const PB_DS_TREE_IT_C_DEC& other)
318      {
319	base_it_type::m_p_nd = other.m_p_nd;
320	return *this;
321      }
322
323      inline
324      PB_DS_TREE_IT_C_DEC&
325      operator=(const PB_DS_TREE_ODIR_IT_C_DEC& other)
326      {
327	base_it_type::m_p_nd = other.m_p_nd;
328	return *this;
329      }
330
331      inline typename PB_DS_TREE_CONST_IT_C_DEC::pointer
332      operator->() const
333      {
334	_GLIBCXX_DEBUG_ASSERT(base_it_type::m_p_nd != NULL);
335	return &base_it_type::m_p_nd->m_value;
336      }
337
338      inline typename PB_DS_TREE_CONST_IT_C_DEC::reference
339      operator*() const
340      {
341	_GLIBCXX_DEBUG_ASSERT(base_it_type::m_p_nd != NULL);
342	return base_it_type::m_p_nd->m_value;
343      }
344
345      inline PB_DS_TREE_IT_C_DEC&
346      operator++()
347      {
348	PB_DS_TREE_CONST_IT_C_DEC:: operator++();
349	return *this;
350      }
351
352      inline PB_DS_TREE_IT_C_DEC
353      operator++(int)
354      {
355	PB_DS_TREE_IT_C_DEC ret_it(base_it_type::m_p_nd);
356	operator++();
357	return ret_it;
358      }
359
360      inline PB_DS_TREE_IT_C_DEC&
361      operator--()
362      {
363	PB_DS_TREE_CONST_IT_C_DEC:: operator--();
364	return *this;
365      }
366
367      inline PB_DS_TREE_IT_C_DEC
368      operator--(int)
369      {
370	PB_DS_TREE_IT_C_DEC ret_it(base_it_type::m_p_nd);
371	operator--();
372	return ret_it;
373      }
374
375    protected:
376      typedef PB_DS_TREE_CONST_IT_C_DEC base_it_type;
377    };
378
379#undef PB_DS_TREE_CONST_IT_C_DEC
380#undef PB_DS_TREE_CONST_ODIR_IT_C_DEC
381#undef PB_DS_TREE_IT_C_DEC
382#undef PB_DS_TREE_ODIR_IT_C_DEC
383
384  } // namespace detail
385} // namespace pb_ds
386
387#endif
388