3 // Copyright (C) 2005, 2006, 2009 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 = NULL)
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 != NULL);
156 return &m_p_nd->m_value;
159 inline const_reference
162 _GLIBCXX_DEBUG_ASSERT(m_p_nd != NULL);
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 != NULL);
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 != NULL)
230 m_p_nd = m_p_nd->m_p_right;
231 while (m_p_nd->m_p_left != NULL)
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 != NULL)
262 Node_Pointer p_y = m_p_nd->m_p_left;
263 while (p_y->m_p_right != NULL)
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 = NULL)
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 != NULL);
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 != NULL);
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