3 // Copyright (C) 2005, 2006, 2009, 2010 Free Software Foundation, Inc.
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
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.
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.
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/>.
25 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
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
37 * @file point_iterators.hpp
38 * Contains an implementation class for bin_search_tree_.
41 #ifndef PB_DS_BIN_SEARCH_TREE_FIND_ITERATORS_HPP
42 #define PB_DS_BIN_SEARCH_TREE_FIND_ITERATORS_HPP
44 #include <ext/pb_ds/tag_and_trait.hpp>
45 #include <debug/debug.h>
52 #define PB_DS_TREE_CONST_IT_C_DEC \
53 bin_search_tree_const_it_< \
60 Is_Forward_Iterator, \
63 #define PB_DS_TREE_CONST_ODIR_IT_C_DEC \
64 bin_search_tree_const_it_< \
71 !Is_Forward_Iterator, \
74 #define PB_DS_TREE_IT_C_DEC \
75 bin_search_tree_it_< \
82 Is_Forward_Iterator, \
85 #define PB_DS_TREE_ODIR_IT_C_DEC \
86 bin_search_tree_it_< \
93 !Is_Forward_Iterator, \
97 template<typename Node_Pointer
,
100 typename Const_Pointer
,
102 typename Const_Reference
,
103 bool Is_Forward_Iterator
,
105 class bin_search_tree_const_it_
110 typedef std::bidirectional_iterator_tag iterator_category
;
112 typedef typename
Allocator::difference_type difference_type
;
114 typedef Value_Type value_type
;
116 typedef Pointer pointer
;
118 typedef Const_Pointer const_pointer
;
120 typedef Reference reference
;
122 typedef Const_Reference const_reference
;
127 bin_search_tree_const_it_(const Node_Pointer p_nd
= 0)
128 : m_p_nd(const_cast<Node_Pointer
>(p_nd
))
132 bin_search_tree_const_it_(const PB_DS_TREE_CONST_ODIR_IT_C_DEC
& other
)
133 : m_p_nd(other
.m_p_nd
)
137 PB_DS_TREE_CONST_IT_C_DEC
&
138 operator=(const PB_DS_TREE_CONST_IT_C_DEC
& other
)
140 m_p_nd
= other
.m_p_nd
;
145 PB_DS_TREE_CONST_IT_C_DEC
&
146 operator=(const PB_DS_TREE_CONST_ODIR_IT_C_DEC
& other
)
148 m_p_nd
= other
.m_p_nd
;
155 _GLIBCXX_DEBUG_ASSERT(m_p_nd
!= 0);
156 return &m_p_nd
->m_value
;
159 inline const_reference
162 _GLIBCXX_DEBUG_ASSERT(m_p_nd
!= 0);
163 return m_p_nd
->m_value
;
167 operator==(const PB_DS_TREE_CONST_IT_C_DEC
& other
) const
168 { return m_p_nd
== other
.m_p_nd
; }
171 operator==(const PB_DS_TREE_CONST_ODIR_IT_C_DEC
& other
) const
172 { return m_p_nd
== other
.m_p_nd
; }
175 operator!=(const PB_DS_TREE_CONST_IT_C_DEC
& other
) const
176 { return m_p_nd
!= other
.m_p_nd
; }
179 operator!=(const PB_DS_TREE_CONST_ODIR_IT_C_DEC
& other
) const
180 { return m_p_nd
!= other
.m_p_nd
; }
182 inline PB_DS_TREE_CONST_IT_C_DEC
&
185 _GLIBCXX_DEBUG_ASSERT(m_p_nd
!= 0);
186 inc(integral_constant
<int,Is_Forward_Iterator
>());
190 inline PB_DS_TREE_CONST_IT_C_DEC
193 PB_DS_TREE_CONST_IT_C_DEC
ret_it(m_p_nd
);
198 inline PB_DS_TREE_CONST_IT_C_DEC
&
201 dec(integral_constant
<int,Is_Forward_Iterator
>());
205 inline PB_DS_TREE_CONST_IT_C_DEC
208 PB_DS_TREE_CONST_IT_C_DEC
ret_it(m_p_nd
);
216 { dec(true_type()); }
221 if (m_p_nd
->special()&&
222 m_p_nd
->m_p_parent
->m_p_parent
== m_p_nd
)
224 m_p_nd
= m_p_nd
->m_p_left
;
228 if (m_p_nd
->m_p_right
!= 0)
230 m_p_nd
= m_p_nd
->m_p_right
;
231 while (m_p_nd
->m_p_left
!= 0)
232 m_p_nd
= m_p_nd
->m_p_left
;
236 Node_Pointer p_y
= m_p_nd
->m_p_parent
;
237 while (m_p_nd
== p_y
->m_p_right
)
240 p_y
= p_y
->m_p_parent
;
243 if (m_p_nd
->m_p_right
!= p_y
)
249 { inc(true_type()); }
254 if (m_p_nd
->special() && m_p_nd
->m_p_parent
->m_p_parent
== m_p_nd
)
256 m_p_nd
= m_p_nd
->m_p_right
;
260 if (m_p_nd
->m_p_left
!= 0)
262 Node_Pointer p_y
= m_p_nd
->m_p_left
;
263 while (p_y
->m_p_right
!= 0)
264 p_y
= p_y
->m_p_right
;
269 Node_Pointer p_y
= m_p_nd
->m_p_parent
;
270 while (m_p_nd
== p_y
->m_p_left
)
273 p_y
= p_y
->m_p_parent
;
275 if (m_p_nd
->m_p_left
!= p_y
)
284 template<typename Node_Pointer
,
287 typename Const_Pointer
,
289 typename Const_Reference
,
290 bool Is_Forward_Iterator
,
292 class bin_search_tree_it_
:
293 public PB_DS_TREE_CONST_IT_C_DEC
300 bin_search_tree_it_(const Node_Pointer p_nd
= 0)
301 : PB_DS_TREE_CONST_IT_C_DEC((Node_Pointer
)p_nd
)
305 bin_search_tree_it_(const PB_DS_TREE_ODIR_IT_C_DEC
& other
)
306 : PB_DS_TREE_CONST_IT_C_DEC(other
.m_p_nd
)
311 operator=(const PB_DS_TREE_IT_C_DEC
& other
)
313 base_it_type::m_p_nd
= other
.m_p_nd
;
319 operator=(const PB_DS_TREE_ODIR_IT_C_DEC
& other
)
321 base_it_type::m_p_nd
= other
.m_p_nd
;
325 inline typename
PB_DS_TREE_CONST_IT_C_DEC::pointer
328 _GLIBCXX_DEBUG_ASSERT(base_it_type::m_p_nd
!= 0);
329 return &base_it_type::m_p_nd
->m_value
;
332 inline typename
PB_DS_TREE_CONST_IT_C_DEC::reference
335 _GLIBCXX_DEBUG_ASSERT(base_it_type::m_p_nd
!= 0);
336 return base_it_type::m_p_nd
->m_value
;
339 inline PB_DS_TREE_IT_C_DEC
&
342 PB_DS_TREE_CONST_IT_C_DEC:: operator++();
346 inline PB_DS_TREE_IT_C_DEC
349 PB_DS_TREE_IT_C_DEC
ret_it(base_it_type::m_p_nd
);
354 inline PB_DS_TREE_IT_C_DEC
&
357 PB_DS_TREE_CONST_IT_C_DEC:: operator--();
361 inline PB_DS_TREE_IT_C_DEC
364 PB_DS_TREE_IT_C_DEC
ret_it(base_it_type::m_p_nd
);
370 typedef PB_DS_TREE_CONST_IT_C_DEC base_it_type
;
373 #undef PB_DS_TREE_CONST_IT_C_DEC
374 #undef PB_DS_TREE_CONST_ODIR_IT_C_DEC
375 #undef PB_DS_TREE_IT_C_DEC
376 #undef PB_DS_TREE_ODIR_IT_C_DEC
378 } // namespace detail
379 } // namespace __gnu_pbds