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