3 // Copyright (C) 2005-2015 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 bin_search_tree_/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_
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;
117 bin_search_tree_const_it_(const Node_Pointer p_nd = 0)
118 : m_p_nd(const_cast<Node_Pointer>(p_nd))
122 bin_search_tree_const_it_(const PB_DS_TREE_CONST_ODIR_IT_C_DEC& other)
123 : m_p_nd(other.m_p_nd)
127 PB_DS_TREE_CONST_IT_C_DEC&
128 operator=(const PB_DS_TREE_CONST_IT_C_DEC& other)
130 m_p_nd = other.m_p_nd;
135 PB_DS_TREE_CONST_IT_C_DEC&
136 operator=(const PB_DS_TREE_CONST_ODIR_IT_C_DEC& other)
138 m_p_nd = other.m_p_nd;
145 _GLIBCXX_DEBUG_ASSERT(m_p_nd != 0);
146 return &m_p_nd->m_value;
149 inline const_reference
152 _GLIBCXX_DEBUG_ASSERT(m_p_nd != 0);
153 return m_p_nd->m_value;
157 operator==(const PB_DS_TREE_CONST_IT_C_DEC & other) const
158 { return m_p_nd == other.m_p_nd; }
161 operator==(const PB_DS_TREE_CONST_ODIR_IT_C_DEC & other) const
162 { return m_p_nd == other.m_p_nd; }
165 operator!=(const PB_DS_TREE_CONST_IT_C_DEC& other) const
166 { return m_p_nd != other.m_p_nd; }
169 operator!=(const PB_DS_TREE_CONST_ODIR_IT_C_DEC& other) const
170 { return m_p_nd != other.m_p_nd; }
172 inline PB_DS_TREE_CONST_IT_C_DEC&
175 _GLIBCXX_DEBUG_ASSERT(m_p_nd != 0);
176 inc(integral_constant<int,Is_Forward_Iterator>());
180 inline PB_DS_TREE_CONST_IT_C_DEC
183 PB_DS_TREE_CONST_IT_C_DEC ret_it(m_p_nd);
188 inline PB_DS_TREE_CONST_IT_C_DEC&
191 dec(integral_constant<int,Is_Forward_Iterator>());
195 inline PB_DS_TREE_CONST_IT_C_DEC
198 PB_DS_TREE_CONST_IT_C_DEC ret_it(m_p_nd);
206 { dec(true_type()); }
211 if (m_p_nd->special()&&
212 m_p_nd->m_p_parent->m_p_parent == m_p_nd)
214 m_p_nd = m_p_nd->m_p_left;
218 if (m_p_nd->m_p_right != 0)
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;
226 Node_Pointer p_y = m_p_nd->m_p_parent;
227 while (m_p_nd == p_y->m_p_right)
230 p_y = p_y->m_p_parent;
233 if (m_p_nd->m_p_right != p_y)
239 { inc(true_type()); }
244 if (m_p_nd->special() && m_p_nd->m_p_parent->m_p_parent == m_p_nd)
246 m_p_nd = m_p_nd->m_p_right;
250 if (m_p_nd->m_p_left != 0)
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;
259 Node_Pointer p_y = m_p_nd->m_p_parent;
260 while (m_p_nd == p_y->m_p_left)
263 p_y = p_y->m_p_parent;
265 if (m_p_nd->m_p_left != p_y)
274 template<typename Node_Pointer,
277 typename Const_Pointer,
279 typename Const_Reference,
280 bool Is_Forward_Iterator,
282 class bin_search_tree_it_ : public PB_DS_TREE_CONST_IT_C_DEC
286 bin_search_tree_it_(const Node_Pointer p_nd = 0)
287 : PB_DS_TREE_CONST_IT_C_DEC((Node_Pointer)p_nd)
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)
297 operator=(const PB_DS_TREE_IT_C_DEC& other)
299 base_it_type::m_p_nd = other.m_p_nd;
305 operator=(const PB_DS_TREE_ODIR_IT_C_DEC& other)
307 base_it_type::m_p_nd = other.m_p_nd;
311 inline typename PB_DS_TREE_CONST_IT_C_DEC::pointer
314 _GLIBCXX_DEBUG_ASSERT(base_it_type::m_p_nd != 0);
315 return &base_it_type::m_p_nd->m_value;
318 inline typename PB_DS_TREE_CONST_IT_C_DEC::reference
321 _GLIBCXX_DEBUG_ASSERT(base_it_type::m_p_nd != 0);
322 return base_it_type::m_p_nd->m_value;
325 inline PB_DS_TREE_IT_C_DEC&
328 PB_DS_TREE_CONST_IT_C_DEC:: operator++();
332 inline PB_DS_TREE_IT_C_DEC
335 PB_DS_TREE_IT_C_DEC ret_it(base_it_type::m_p_nd);
340 inline PB_DS_TREE_IT_C_DEC&
343 PB_DS_TREE_CONST_IT_C_DEC:: operator--();
347 inline PB_DS_TREE_IT_C_DEC
350 PB_DS_TREE_IT_C_DEC ret_it(base_it_type::m_p_nd);
356 typedef PB_DS_TREE_CONST_IT_C_DEC base_it_type;
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
364 } // namespace detail
365 } // namespace __gnu_pbds