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_PAT_TRIE_FIND_ITERATORS_HPP
48 #define PB_DS_PAT_TRIE_FIND_ITERATORS_HPP
50 #include <debug/debug.h>
57 #define PB_DS_CONST_IT_C_DEC \
64 Is_Forward_Iterator, \
67 #define PB_DS_CONST_ODIR_IT_C_DEC \
74 !Is_Forward_Iterator, \
77 #define PB_DS_IT_C_DEC \
84 Is_Forward_Iterator, \
87 #define PB_DS_ODIR_IT_C_DEC \
94 !Is_Forward_Iterator, \
99 template<typename Type_Traits,
104 bool Is_Forward_Iterator,
106 class pat_trie_const_it_
111 typename Allocator::template rebind<
112 Node>::other::pointer
116 typename Allocator::template rebind<
117 Leaf>::other::const_pointer
121 typename Allocator::template rebind<
122 Leaf>::other::pointer
126 typename Allocator::template rebind<
127 Head>::other::pointer
131 typename Allocator::template rebind<
132 Internal_Node>::other::pointer
133 internal_node_pointer;
137 typedef std::bidirectional_iterator_tag iterator_category;
139 typedef typename Allocator::difference_type difference_type;
141 typedef typename Type_Traits::value_type value_type;
143 typedef typename Type_Traits::pointer pointer;
145 typedef typename Type_Traits::const_pointer const_pointer;
147 typedef typename Type_Traits::reference reference;
149 typedef typename Type_Traits::const_reference const_reference;
154 pat_trie_const_it_(node_pointer p_nd = NULL) : m_p_nd(p_nd)
158 pat_trie_const_it_(const PB_DS_CONST_ODIR_IT_C_DEC& other)
159 : m_p_nd(other.m_p_nd)
163 PB_DS_CONST_IT_C_DEC&
164 operator=(const PB_DS_CONST_IT_C_DEC& other)
166 m_p_nd = other.m_p_nd;
171 PB_DS_CONST_IT_C_DEC&
172 operator=(const PB_DS_CONST_ODIR_IT_C_DEC& other)
174 m_p_nd = other.m_p_nd;
181 _GLIBCXX_DEBUG_ASSERT(m_p_nd->m_type == pat_trie_leaf_node_type);
182 return &static_cast<leaf_pointer>(m_p_nd)->value();
185 inline const_reference
188 _GLIBCXX_DEBUG_ASSERT(m_p_nd->m_type == pat_trie_leaf_node_type);
189 return static_cast<leaf_pointer>(m_p_nd)->value();
193 operator==(const PB_DS_CONST_IT_C_DEC& other) const
194 { return (m_p_nd == other.m_p_nd); }
197 operator==(const PB_DS_CONST_ODIR_IT_C_DEC& other) const
198 { return (m_p_nd == other.m_p_nd); }
201 operator!=(const PB_DS_CONST_IT_C_DEC& other) const
202 { return (m_p_nd != other.m_p_nd); }
205 operator!=(const PB_DS_CONST_ODIR_IT_C_DEC& other) const
206 { return (m_p_nd != other.m_p_nd); }
208 inline PB_DS_CONST_IT_C_DEC&
211 inc(integral_constant<int,Is_Forward_Iterator>());
215 inline PB_DS_CONST_IT_C_DEC
218 PB_DS_CONST_IT_C_DEC ret_it(m_p_nd);
223 inline PB_DS_CONST_IT_C_DEC&
226 dec(integral_constant<int,Is_Forward_Iterator>());
230 inline PB_DS_CONST_IT_C_DEC
233 PB_DS_CONST_IT_C_DEC ret_it(m_p_nd);
241 { dec(true_type()); }
246 if (m_p_nd->m_type == pat_trie_head_node_type)
248 m_p_nd = static_cast<head_pointer>(m_p_nd)->m_p_min;
252 node_pointer p_y = m_p_nd->m_p_parent;
253 while (p_y->m_type != pat_trie_head_node_type &&
254 get_larger_sibling(m_p_nd) == NULL)
257 p_y = p_y->m_p_parent;
260 if (p_y->m_type == pat_trie_head_node_type)
265 m_p_nd = leftmost_descendant(get_larger_sibling(m_p_nd));
270 { inc(true_type()); }
275 if (m_p_nd->m_type == pat_trie_head_node_type)
277 m_p_nd = static_cast<head_pointer>(m_p_nd)->m_p_max;
281 node_pointer p_y = m_p_nd->m_p_parent;
282 while (p_y->m_type != pat_trie_head_node_type &&
283 get_smaller_sibling(m_p_nd) == NULL)
286 p_y = p_y->m_p_parent;
289 if (p_y->m_type == pat_trie_head_node_type)
294 m_p_nd = rightmost_descendant(get_smaller_sibling(m_p_nd));
297 inline static node_pointer
298 get_larger_sibling(node_pointer p_nd)
300 internal_node_pointer p_parent =
301 static_cast<internal_node_pointer>(p_nd->m_p_parent);
303 typename Internal_Node::iterator it = p_parent->begin();
307 typename Internal_Node::iterator next_it = it;
309 return ((next_it == p_parent->end())? NULL :* next_it);
312 inline static node_pointer
313 get_smaller_sibling(node_pointer p_nd)
315 internal_node_pointer p_parent =
316 static_cast<internal_node_pointer>(p_nd->m_p_parent);
318 typename Internal_Node::iterator it = p_parent->begin();
322 typename Internal_Node::iterator prev_it;
332 _GLIBCXX_DEBUG_ASSERT(false);
336 inline static leaf_pointer
337 leftmost_descendant(node_pointer p_nd)
339 if (p_nd->m_type == pat_trie_leaf_node_type)
340 return static_cast<leaf_pointer>(p_nd);
341 return static_cast<internal_node_pointer>(p_nd)->leftmost_descendant();
344 inline static leaf_pointer
345 rightmost_descendant(node_pointer p_nd)
347 if (p_nd->m_type == pat_trie_leaf_node_type)
348 return static_cast<leaf_pointer>(p_nd);
349 return static_cast<internal_node_pointer>(p_nd)->rightmost_descendant();
357 template<typename Type_Traits,
362 bool Is_Forward_Iterator,
365 public PB_DS_CONST_IT_C_DEC
370 typename Allocator::template rebind<
371 Node>::other::pointer
375 typename Allocator::template rebind<
376 Leaf>::other::const_pointer
380 typename Allocator::template rebind<
381 Leaf>::other::pointer
385 typename Allocator::template rebind<
386 Head>::other::pointer
390 typename Allocator::template rebind<
391 Internal_Node>::other::pointer
392 internal_node_pointer;
395 typedef typename Type_Traits::value_type value_type;
397 typedef typename Type_Traits::const_pointer const_pointer;
399 typedef typename Type_Traits::pointer pointer;
401 typedef typename Type_Traits::const_reference const_reference;
403 typedef typename Type_Traits::reference reference;
406 pat_trie_it_(node_pointer p_nd = NULL) : PB_DS_CONST_IT_C_DEC((node_pointer)p_nd)
410 pat_trie_it_(const PB_DS_ODIR_IT_C_DEC& other) : PB_DS_CONST_IT_C_DEC(other.m_p_nd)
415 operator=(const PB_DS_IT_C_DEC& other)
417 base_it_type::m_p_nd = other.m_p_nd;
423 operator=(const PB_DS_ODIR_IT_C_DEC& other)
425 base_it_type::m_p_nd = other.m_p_nd;
432 _GLIBCXX_DEBUG_ASSERT(base_it_type::m_p_nd->m_type == pat_trie_leaf_node_type);
434 return &static_cast<leaf_pointer>(base_it_type::m_p_nd)->value();
440 _GLIBCXX_DEBUG_ASSERT(base_it_type::m_p_nd->m_type == pat_trie_leaf_node_type);
441 return static_cast<leaf_pointer>(base_it_type::m_p_nd)->value();
444 inline PB_DS_IT_C_DEC&
447 PB_DS_CONST_IT_C_DEC::
452 inline PB_DS_IT_C_DEC
455 PB_DS_IT_C_DEC ret_it(base_it_type::m_p_nd);
460 inline PB_DS_IT_C_DEC&
463 PB_DS_CONST_IT_C_DEC::operator--();
467 inline PB_DS_IT_C_DEC
470 PB_DS_IT_C_DEC ret_it(base_it_type::m_p_nd);
476 typedef PB_DS_CONST_IT_C_DEC base_it_type;
478 friend class PB_DS_CLASS_C_DEC;
481 #undef PB_DS_CONST_IT_C_DEC
482 #undef PB_DS_CONST_ODIR_IT_C_DEC
483 #undef PB_DS_IT_C_DEC
484 #undef PB_DS_ODIR_IT_C_DEC
486 } // namespace detail