1// -*- C++ -*-
2
3// Copyright (C) 2005, 2006 Free Software Foundation, Inc.
4//
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
9// version.
10
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.
15
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.
20
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
29// Public License.
30
31// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
32
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
40// warranty.
41
42/**
43 * @file node_iterators.hpp
44 * Contains an implementation class for pat_trie_.
45 */
46
47#ifndef PB_DS_PAT_TRIE_NODE_ITERATORS_HPP
48#define PB_DS_PAT_TRIE_NODE_ITERATORS_HPP
49
50#include <debug/debug.h>
51
52namespace pb_ds
53{
54  namespace detail
55  {
56
57#define PB_DS_PAT_TRIE_CONST_NODE_ITERATOR_C_DEC			\
58    pat_trie_const_node_it_<						\
59							Node,		\
60							Leaf,		\
61							Head,		\
62							Internal_Node,	\
63							Const_Iterator,	\
64							Iterator,	\
65							E_Access_Traits, \
66							Allocator>
67
68#define PB_DS_PAT_TRIE_NODE_ITERATOR_C_DEC			\
69    pat_trie_node_it_<						\
70					Node,			\
71					Leaf,			\
72					Head,			\
73					Internal_Node,		\
74					Const_Iterator,		\
75					Iterator,		\
76					E_Access_Traits,	\
77					Allocator>
78
79    // Const node iterator.
80    template<typename Node,
81	     class Leaf,
82	     class Head,
83	     class Internal_Node,
84	     class Const_Iterator,
85	     class Iterator,
86	     class E_Access_Traits,
87	     class Allocator>
88    class pat_trie_const_node_it_
89    {
90    protected:
91      typedef
92      typename Allocator::template rebind<
93      Node>::other::pointer
94      node_pointer;
95
96      typedef
97      typename Allocator::template rebind<
98	Leaf>::other::const_pointer
99      const_leaf_pointer;
100
101      typedef
102      typename Allocator::template rebind<
103	Leaf>::other::pointer
104      leaf_pointer;
105
106      typedef
107      typename Allocator::template rebind<
108	Internal_Node>::other::pointer
109      internal_node_pointer;
110
111      typedef
112      typename Allocator::template rebind<
113	Internal_Node>::other::const_pointer
114      const_internal_node_pointer;
115
116      typedef
117      typename Allocator::template rebind<
118	E_Access_Traits>::other::const_pointer
119      const_e_access_traits_pointer;
120
121    private:
122      inline typename E_Access_Traits::const_iterator
123      pref_begin() const
124      {
125	if (m_p_nd->m_type == pat_trie_leaf_node_type)
126	  return (m_p_traits->begin(
127				    m_p_traits->extract_key(
128							    static_cast<const_leaf_pointer>(m_p_nd)->value())));
129
130	_GLIBCXX_DEBUG_ASSERT(m_p_nd->m_type == pat_trie_internal_node_type);
131
132	return (static_cast<const_internal_node_pointer>(m_p_nd)->pref_b_it());
133      }
134
135      inline typename E_Access_Traits::const_iterator
136      pref_end() const
137      {
138	if (m_p_nd->m_type == pat_trie_leaf_node_type)
139	  return (m_p_traits->end(
140				  m_p_traits->extract_key(
141							  static_cast<const_leaf_pointer>(m_p_nd)->value())));
142
143	_GLIBCXX_DEBUG_ASSERT(m_p_nd->m_type == pat_trie_internal_node_type);
144
145	return (static_cast<const_internal_node_pointer>(m_p_nd)->pref_e_it());
146      }
147
148    public:
149
150      // Size type.
151      typedef typename Allocator::size_type size_type;
152
153      // Category.
154      typedef trivial_iterator_tag iterator_category;
155
156      // Difference type.
157      typedef trivial_iterator_difference_type difference_type;
158
159      // __Iterator's value type.
160      typedef Const_Iterator value_type;
161
162      // __Iterator's reference type.
163      typedef value_type reference;
164
165      // __Iterator's __const reference type.
166      typedef value_type const_reference;
167
168      // Element access traits.
169      typedef E_Access_Traits e_access_traits;
170
171      // A key's element __const iterator.
172      typedef typename e_access_traits::const_iterator const_e_iterator;
173
174      // Metadata type.
175      typedef typename Node::metadata_type metadata_type;
176
177      // Const metadata reference type.
178      typedef
179      typename Allocator::template rebind<
180	metadata_type>::other::const_reference
181      const_metadata_reference;
182
183      // Default constructor.
184      /*
185	inline
186	pat_trie_const_node_it_()
187      */
188      inline
189      pat_trie_const_node_it_(node_pointer p_nd = NULL,
190			      const_e_access_traits_pointer p_traits = NULL)
191      : m_p_nd(const_cast<node_pointer>(p_nd)), m_p_traits(p_traits)
192      { }
193
194      // Subtree valid prefix.
195      inline std::pair<const_e_iterator, const_e_iterator>
196      valid_prefix() const
197      { return std::make_pair(pref_begin(), pref_end()); }
198
199      // Const access; returns the __const iterator* associated with
200      // the current leaf.
201      inline const_reference
202      operator*() const
203      {
204	_GLIBCXX_DEBUG_ASSERT(num_children() == 0);
205	return Const_Iterator(m_p_nd);
206      }
207
208      // Metadata access.
209      inline const_metadata_reference
210      get_metadata() const
211      { return m_p_nd->get_metadata(); }
212
213      // Returns the number of children in the corresponding node.
214      inline size_type
215      num_children() const
216      {
217	if (m_p_nd->m_type == pat_trie_leaf_node_type)
218	  return 0;
219	_GLIBCXX_DEBUG_ASSERT(m_p_nd->m_type == pat_trie_internal_node_type);
220	return std::distance(static_cast<internal_node_pointer>(m_p_nd)->begin(),  static_cast<internal_node_pointer>(m_p_nd)->end());
221      }
222
223      // Returns a __const node __iterator to the corresponding node's
224      // i-th child.
225      PB_DS_PAT_TRIE_CONST_NODE_ITERATOR_C_DEC
226      get_child(size_type i) const
227      {
228	_GLIBCXX_DEBUG_ASSERT(m_p_nd->m_type == pat_trie_internal_node_type);
229	typename Internal_Node::iterator it =
230	  static_cast<internal_node_pointer>(m_p_nd)->begin();
231
232	std::advance(it, i);
233	return PB_DS_PAT_TRIE_CONST_NODE_ITERATOR_C_DEC(*it, m_p_traits);
234      }
235
236      // Compares content to a different iterator object.
237      inline bool
238      operator==(const PB_DS_PAT_TRIE_CONST_NODE_ITERATOR_C_DEC& other) const
239      { return (m_p_nd == other.m_p_nd); }
240
241      // Compares content (negatively) to a different iterator object.
242      inline bool
243      operator!=(const PB_DS_PAT_TRIE_CONST_NODE_ITERATOR_C_DEC& other) const
244      { return m_p_nd != other.m_p_nd; }
245
246    private:
247
248      friend class PB_DS_CLASS_C_DEC;
249
250    public:
251      node_pointer m_p_nd;
252
253      const_e_access_traits_pointer m_p_traits;
254    };
255
256    // Node iterator.
257    template<typename Node,
258	     class Leaf,
259	     class Head,
260	     class Internal_Node,
261	     class Const_Iterator,
262	     class Iterator,
263	     class E_Access_Traits,
264	     class Allocator>
265    class pat_trie_node_it_ :
266      public PB_DS_PAT_TRIE_CONST_NODE_ITERATOR_C_DEC
267
268    {
269    private:
270      typedef
271      typename Allocator::template rebind<
272      Node>::other::pointer
273      node_pointer;
274
275      typedef Iterator iterator;
276
277      typedef PB_DS_PAT_TRIE_CONST_NODE_ITERATOR_C_DEC base_type;
278
279      typedef
280      typename base_type::const_e_access_traits_pointer
281      const_e_access_traits_pointer;
282
283      typedef typename base_type::internal_node_pointer internal_node_pointer;
284
285    public:
286
287      // Size type.
288      typedef
289      typename PB_DS_PAT_TRIE_CONST_NODE_ITERATOR_C_DEC::size_type
290      size_type;
291
292      // __Iterator's value type.
293      typedef Iterator value_type;
294
295      // __Iterator's reference type.
296      typedef value_type reference;
297
298      // __Iterator's __const reference type.
299      typedef value_type const_reference;
300
301      // Default constructor.
302      /*
303	inline
304	pat_trie_node_it_() ;
305      */
306
307      inline
308      pat_trie_node_it_(node_pointer p_nd = NULL,  const_e_access_traits_pointer p_traits = NULL) : base_type(p_nd, p_traits)
309      { }
310
311      // Access; returns the iterator*  associated with the current leaf.
312      inline reference
313      operator*() const
314      {
315	_GLIBCXX_DEBUG_ASSERT(base_type::num_children() == 0);
316	return Iterator(base_type::m_p_nd);
317
318      }
319
320      // Returns a node __iterator to the corresponding node's i-th child.
321      PB_DS_PAT_TRIE_NODE_ITERATOR_C_DEC
322      get_child(size_type i) const
323      {
324	_GLIBCXX_DEBUG_ASSERT(base_type::m_p_nd->m_type == pat_trie_internal_node_type);
325
326	typename Internal_Node::iterator it =
327	  static_cast<internal_node_pointer>(base_type::m_p_nd)->begin();
328
329	std::advance(it, i);
330	return PB_DS_PAT_TRIE_NODE_ITERATOR_C_DEC(*it, base_type::m_p_traits);
331      }
332
333    private:
334      friend class PB_DS_CLASS_C_DEC;
335    };
336
337#undef PB_DS_PAT_TRIE_CONST_NODE_ITERATOR_C_DEC
338#undef PB_DS_PAT_TRIE_NODE_ITERATOR_C_DEC
339
340  } // namespace detail
341} // namespace pb_ds
342
343#endif
344
345