3 // Copyright (C) 2005, 2006 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 2, 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 // 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.
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
31 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
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
43 * @file point_iterators.hpp
44 * Contains an implementation class for bin_search_tree_.
47 #ifndef PB_DS_BIN_SEARCH_TREE_FIND_ITERATORS_HPP
48 #define PB_DS_BIN_SEARCH_TREE_FIND_ITERATORS_HPP
50 #include <ext/pb_ds/tag_and_trait.hpp>
51 #include <debug/debug.h>
58 #define PB_DS_TREE_CONST_IT_C_DEC \
59 bin_search_tree_const_it_< \
66 Is_Forward_Iterator, \
69 #define PB_DS_TREE_CONST_ODIR_IT_C_DEC \
70 bin_search_tree_const_it_< \
77 !Is_Forward_Iterator, \
80 #define PB_DS_TREE_IT_C_DEC \
81 bin_search_tree_it_< \
88 Is_Forward_Iterator, \
91 #define PB_DS_TREE_ODIR_IT_C_DEC \
92 bin_search_tree_it_< \
99 !Is_Forward_Iterator, \
103 template<typename Node_Pointer
,
106 typename Const_Pointer
,
108 typename Const_Reference
,
109 bool Is_Forward_Iterator
,
111 class bin_search_tree_const_it_
116 typedef std::bidirectional_iterator_tag iterator_category
;
118 typedef typename
Allocator::difference_type difference_type
;
120 typedef Value_Type value_type
;
122 typedef Pointer pointer
;
124 typedef Const_Pointer const_pointer
;
126 typedef Reference reference
;
128 typedef Const_Reference const_reference
;
133 bin_search_tree_const_it_(const Node_Pointer p_nd
= NULL
)
134 : m_p_nd(const_cast<Node_Pointer
>(p_nd
))
138 bin_search_tree_const_it_(const PB_DS_TREE_CONST_ODIR_IT_C_DEC
& other
)
139 : m_p_nd(other
.m_p_nd
)
143 PB_DS_TREE_CONST_IT_C_DEC
&
144 operator=(const PB_DS_TREE_CONST_IT_C_DEC
& other
)
146 m_p_nd
= other
.m_p_nd
;
151 PB_DS_TREE_CONST_IT_C_DEC
&
152 operator=(const PB_DS_TREE_CONST_ODIR_IT_C_DEC
& other
)
154 m_p_nd
= other
.m_p_nd
;
161 _GLIBCXX_DEBUG_ASSERT(m_p_nd
!= NULL
);
162 return &m_p_nd
->m_value
;
165 inline const_reference
168 _GLIBCXX_DEBUG_ASSERT(m_p_nd
!= NULL
);
169 return m_p_nd
->m_value
;
173 operator==(const PB_DS_TREE_CONST_IT_C_DEC
& other
) const
174 { return m_p_nd
== other
.m_p_nd
; }
177 operator==(const PB_DS_TREE_CONST_ODIR_IT_C_DEC
& other
) const
178 { return m_p_nd
== other
.m_p_nd
; }
181 operator!=(const PB_DS_TREE_CONST_IT_C_DEC
& other
) const
182 { return m_p_nd
!= other
.m_p_nd
; }
185 operator!=(const PB_DS_TREE_CONST_ODIR_IT_C_DEC
& other
) const
186 { return m_p_nd
!= other
.m_p_nd
; }
188 inline PB_DS_TREE_CONST_IT_C_DEC
&
191 _GLIBCXX_DEBUG_ASSERT(m_p_nd
!= NULL
);
192 inc(integral_constant
<int,Is_Forward_Iterator
>());
196 inline PB_DS_TREE_CONST_IT_C_DEC
199 PB_DS_TREE_CONST_IT_C_DEC
ret_it(m_p_nd
);
204 inline PB_DS_TREE_CONST_IT_C_DEC
&
207 dec(integral_constant
<int,Is_Forward_Iterator
>());
211 inline PB_DS_TREE_CONST_IT_C_DEC
214 PB_DS_TREE_CONST_IT_C_DEC
ret_it(m_p_nd
);
222 { dec(true_type()); }
227 if (m_p_nd
->special()&&
228 m_p_nd
->m_p_parent
->m_p_parent
== m_p_nd
)
230 m_p_nd
= m_p_nd
->m_p_left
;
234 if (m_p_nd
->m_p_right
!= NULL
)
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
;
242 Node_Pointer p_y
= m_p_nd
->m_p_parent
;
243 while (m_p_nd
== p_y
->m_p_right
)
246 p_y
= p_y
->m_p_parent
;
249 if (m_p_nd
->m_p_right
!= p_y
)
255 { inc(true_type()); }
260 if (m_p_nd
->special() && m_p_nd
->m_p_parent
->m_p_parent
== m_p_nd
)
262 m_p_nd
= m_p_nd
->m_p_right
;
266 if (m_p_nd
->m_p_left
!= NULL
)
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
;
275 Node_Pointer p_y
= m_p_nd
->m_p_parent
;
276 while (m_p_nd
== p_y
->m_p_left
)
279 p_y
= p_y
->m_p_parent
;
281 if (m_p_nd
->m_p_left
!= p_y
)
290 template<typename Node_Pointer
,
293 typename Const_Pointer
,
295 typename Const_Reference
,
296 bool Is_Forward_Iterator
,
298 class bin_search_tree_it_
:
299 public PB_DS_TREE_CONST_IT_C_DEC
306 bin_search_tree_it_(const Node_Pointer p_nd
= NULL
)
307 : PB_DS_TREE_CONST_IT_C_DEC((Node_Pointer
)p_nd
)
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
)
317 operator=(const PB_DS_TREE_IT_C_DEC
& other
)
319 base_it_type::m_p_nd
= other
.m_p_nd
;
325 operator=(const PB_DS_TREE_ODIR_IT_C_DEC
& other
)
327 base_it_type::m_p_nd
= other
.m_p_nd
;
331 inline typename
PB_DS_TREE_CONST_IT_C_DEC::pointer
334 _GLIBCXX_DEBUG_ASSERT(base_it_type::m_p_nd
!= NULL
);
335 return &base_it_type::m_p_nd
->m_value
;
338 inline typename
PB_DS_TREE_CONST_IT_C_DEC::reference
341 _GLIBCXX_DEBUG_ASSERT(base_it_type::m_p_nd
!= NULL
);
342 return base_it_type::m_p_nd
->m_value
;
345 inline PB_DS_TREE_IT_C_DEC
&
348 PB_DS_TREE_CONST_IT_C_DEC:: operator++();
352 inline PB_DS_TREE_IT_C_DEC
355 PB_DS_TREE_IT_C_DEC
ret_it(base_it_type::m_p_nd
);
360 inline PB_DS_TREE_IT_C_DEC
&
363 PB_DS_TREE_CONST_IT_C_DEC:: operator--();
367 inline PB_DS_TREE_IT_C_DEC
370 PB_DS_TREE_IT_C_DEC
ret_it(base_it_type::m_p_nd
);
376 typedef PB_DS_TREE_CONST_IT_C_DEC base_it_type
;
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
384 } // namespace detail
385 } // namespace __gnu_pbds