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 node_iterators.hpp
38 * Contains an implementation class for pat_trie_.
41 #ifndef PB_DS_PAT_TRIE_NODE_ITERATORS_HPP
42 #define PB_DS_PAT_TRIE_NODE_ITERATORS_HPP
44 #include <debug/debug.h>
51 #define PB_DS_PAT_TRIE_CONST_NODE_ITERATOR_C_DEC \
52 pat_trie_const_node_it_< \
62 #define PB_DS_PAT_TRIE_NODE_ITERATOR_C_DEC \
73 // Const node iterator.
74 template<typename Node
,
80 class E_Access_Traits
,
82 class pat_trie_const_node_it_
86 typename
Allocator::template rebind
<
91 typename
Allocator::template rebind
<
92 Leaf
>::other::const_pointer
96 typename
Allocator::template rebind
<
101 typename
Allocator::template rebind
<
102 Internal_Node
>::other::pointer
103 internal_node_pointer
;
106 typename
Allocator::template rebind
<
107 Internal_Node
>::other::const_pointer
108 const_internal_node_pointer
;
111 typename
Allocator::template rebind
<
112 E_Access_Traits
>::other::const_pointer
113 const_e_access_traits_pointer
;
116 inline typename
E_Access_Traits::const_iterator
119 if (m_p_nd
->m_type
== pat_trie_leaf_node_type
)
120 return (m_p_traits
->begin(
121 m_p_traits
->extract_key(
122 static_cast<const_leaf_pointer
>(m_p_nd
)->value())));
124 _GLIBCXX_DEBUG_ASSERT(m_p_nd
->m_type
== pat_trie_internal_node_type
);
126 return (static_cast<const_internal_node_pointer
>(m_p_nd
)->pref_b_it());
129 inline typename
E_Access_Traits::const_iterator
132 if (m_p_nd
->m_type
== pat_trie_leaf_node_type
)
133 return (m_p_traits
->end(
134 m_p_traits
->extract_key(
135 static_cast<const_leaf_pointer
>(m_p_nd
)->value())));
137 _GLIBCXX_DEBUG_ASSERT(m_p_nd
->m_type
== pat_trie_internal_node_type
);
139 return (static_cast<const_internal_node_pointer
>(m_p_nd
)->pref_e_it());
145 typedef typename
Allocator::size_type size_type
;
148 typedef trivial_iterator_tag iterator_category
;
151 typedef trivial_iterator_difference_type difference_type
;
153 // __Iterator's value type.
154 typedef Const_Iterator value_type
;
156 // __Iterator's reference type.
157 typedef value_type reference
;
159 // __Iterator's __const reference type.
160 typedef value_type const_reference
;
162 // Element access traits.
163 typedef E_Access_Traits e_access_traits
;
165 // A key's element __const iterator.
166 typedef typename
e_access_traits::const_iterator const_e_iterator
;
169 typedef typename
Node::metadata_type metadata_type
;
171 // Const metadata reference type.
173 typename
Allocator::template rebind
<
174 metadata_type
>::other::const_reference
175 const_metadata_reference
;
177 // Default constructor.
180 pat_trie_const_node_it_()
183 pat_trie_const_node_it_(node_pointer p_nd
= 0,
184 const_e_access_traits_pointer p_traits
= 0)
185 : m_p_nd(const_cast<node_pointer
>(p_nd
)), m_p_traits(p_traits
)
188 // Subtree valid prefix.
189 inline std::pair
<const_e_iterator
, const_e_iterator
>
191 { return std::make_pair(pref_begin(), pref_end()); }
193 // Const access; returns the __const iterator* associated with
195 inline const_reference
198 _GLIBCXX_DEBUG_ASSERT(num_children() == 0);
199 return Const_Iterator(m_p_nd
);
203 inline const_metadata_reference
205 { return m_p_nd
->get_metadata(); }
207 // Returns the number of children in the corresponding node.
211 if (m_p_nd
->m_type
== pat_trie_leaf_node_type
)
213 _GLIBCXX_DEBUG_ASSERT(m_p_nd
->m_type
== pat_trie_internal_node_type
);
214 return std::distance(static_cast<internal_node_pointer
>(m_p_nd
)->begin(), static_cast<internal_node_pointer
>(m_p_nd
)->end());
217 // Returns a __const node __iterator to the corresponding node's
219 PB_DS_PAT_TRIE_CONST_NODE_ITERATOR_C_DEC
220 get_child(size_type i
) const
222 _GLIBCXX_DEBUG_ASSERT(m_p_nd
->m_type
== pat_trie_internal_node_type
);
223 typename
Internal_Node::iterator it
=
224 static_cast<internal_node_pointer
>(m_p_nd
)->begin();
227 return PB_DS_PAT_TRIE_CONST_NODE_ITERATOR_C_DEC(*it
, m_p_traits
);
230 // Compares content to a different iterator object.
232 operator==(const PB_DS_PAT_TRIE_CONST_NODE_ITERATOR_C_DEC
& other
) const
233 { return (m_p_nd
== other
.m_p_nd
); }
235 // Compares content (negatively) to a different iterator object.
237 operator!=(const PB_DS_PAT_TRIE_CONST_NODE_ITERATOR_C_DEC
& other
) const
238 { return m_p_nd
!= other
.m_p_nd
; }
242 friend class PB_DS_CLASS_C_DEC
;
247 const_e_access_traits_pointer m_p_traits
;
251 template<typename Node
,
255 class Const_Iterator
,
257 class E_Access_Traits
,
259 class pat_trie_node_it_
:
260 public PB_DS_PAT_TRIE_CONST_NODE_ITERATOR_C_DEC
265 typename
Allocator::template rebind
<
266 Node
>::other::pointer
269 typedef Iterator iterator
;
271 typedef PB_DS_PAT_TRIE_CONST_NODE_ITERATOR_C_DEC base_type
;
274 typename
base_type::const_e_access_traits_pointer
275 const_e_access_traits_pointer
;
277 typedef typename
base_type::internal_node_pointer internal_node_pointer
;
283 typename
PB_DS_PAT_TRIE_CONST_NODE_ITERATOR_C_DEC::size_type
286 // __Iterator's value type.
287 typedef Iterator value_type
;
289 // __Iterator's reference type.
290 typedef value_type reference
;
292 // __Iterator's __const reference type.
293 typedef value_type const_reference
;
295 // Default constructor.
298 pat_trie_node_it_() ;
302 pat_trie_node_it_(node_pointer p_nd
= 0, const_e_access_traits_pointer p_traits
= 0) : base_type(p_nd
, p_traits
)
305 // Access; returns the iterator* associated with the current leaf.
309 _GLIBCXX_DEBUG_ASSERT(base_type::num_children() == 0);
310 return Iterator(base_type::m_p_nd
);
314 // Returns a node __iterator to the corresponding node's i-th child.
315 PB_DS_PAT_TRIE_NODE_ITERATOR_C_DEC
316 get_child(size_type i
) const
318 _GLIBCXX_DEBUG_ASSERT(base_type::m_p_nd
->m_type
== pat_trie_internal_node_type
);
320 typename
Internal_Node::iterator it
=
321 static_cast<internal_node_pointer
>(base_type::m_p_nd
)->begin();
324 return PB_DS_PAT_TRIE_NODE_ITERATOR_C_DEC(*it
, base_type::m_p_traits
);
328 friend class PB_DS_CLASS_C_DEC
;
331 #undef PB_DS_PAT_TRIE_CONST_NODE_ITERATOR_C_DEC
332 #undef PB_DS_PAT_TRIE_NODE_ITERATOR_C_DEC
334 } // namespace detail
335 } // namespace __gnu_pbds