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 traits.hpp
44 * Contains an implementation class for pat_trie_.
45 */
46
47#ifndef PB_DS_PAT_TRIE_NODE_AND_IT_TRAITS_HPP
48#define PB_DS_PAT_TRIE_NODE_AND_IT_TRAITS_HPP
49
50#include <ext/pb_ds/detail/pat_trie_/node_base.hpp>
51#include <ext/pb_ds/detail/pat_trie_/head.hpp>
52#include <ext/pb_ds/detail/pat_trie_/leaf.hpp>
53#include <ext/pb_ds/detail/pat_trie_/internal_node.hpp>
54#include <ext/pb_ds/detail/pat_trie_/point_iterators.hpp>
55#include <ext/pb_ds/detail/pat_trie_/node_iterators.hpp>
56#include <ext/pb_ds/detail/pat_trie_/synth_e_access_traits.hpp>
57
58namespace pb_ds
59{
60  namespace detail
61  {
62
63    template<typename Key,
64	     typename Mapped,
65	     class E_Access_Traits,
66	     template<typename Const_Node_Iterator,
67		      class Node_Iterator,
68		      class Cmp_Fn_,
69		      class Allocator_>
70    class Node_Update,
71	     class Allocator>
72    struct trie_traits<
73      Key,
74      Mapped,
75      E_Access_Traits,
76      Node_Update,
77      pat_trie_tag,
78      Allocator>
79    {
80    private:
81      typedef types_traits< Key, Mapped, Allocator, false> type_traits;
82
83    public:
84      typedef
85      typename trie_node_metadata_selector<
86      Key,
87      Mapped,
88      E_Access_Traits,
89      Node_Update,
90      Allocator>::type
91      metadata_type;
92
93      typedef E_Access_Traits e_access_traits;
94
95      typedef
96      synth_e_access_traits<
97	type_traits,
98	false,
99	e_access_traits>
100      synth_e_access_traits;
101
102      typedef
103      pat_trie_node_base<
104	type_traits,
105	synth_e_access_traits,
106	metadata_type,
107	Allocator>
108      node;
109
110      typedef
111      pat_trie_leaf<
112	type_traits,
113	synth_e_access_traits,
114	metadata_type,
115	Allocator>
116      leaf;
117
118      typedef
119      pat_trie_head<
120	type_traits,
121	synth_e_access_traits,
122	metadata_type,
123	Allocator>
124      head;
125
126      typedef
127      pat_trie_internal_node<
128	type_traits,
129	synth_e_access_traits,
130	metadata_type,
131	Allocator>
132      internal_node;
133
134      typedef
135      pat_trie_const_it_<
136	type_traits,
137	node,
138	leaf,
139	head,
140	internal_node,
141	true,
142	Allocator>
143      const_iterator;
144
145      typedef
146      pat_trie_it_<
147	type_traits,
148	node,
149	leaf,
150	head,
151	internal_node,
152	true,
153	Allocator>
154      iterator;
155
156      typedef
157      pat_trie_const_it_<
158	type_traits,
159	node,
160	leaf,
161	head,
162	internal_node,
163	false,
164	Allocator>
165      const_reverse_iterator;
166
167      typedef
168      pat_trie_it_<
169	type_traits,
170	node,
171	leaf,
172	head,
173	internal_node,
174	false,
175	Allocator>
176      reverse_iterator;
177
178      typedef
179      pat_trie_const_node_it_<
180	node,
181	leaf,
182	head,
183	internal_node,
184	const_iterator,
185	iterator,
186	synth_e_access_traits,
187	Allocator>
188      const_node_iterator;
189
190      typedef
191      pat_trie_node_it_<
192	node,
193	leaf,
194	head,
195	internal_node,
196	const_iterator,
197	iterator,
198	synth_e_access_traits,
199	Allocator>
200      node_iterator;
201
202      typedef
203      Node_Update<
204	const_node_iterator,
205	node_iterator,
206	E_Access_Traits,
207	Allocator>
208      node_update;
209
210      typedef
211      pb_ds::null_trie_node_update<
212	const_node_iterator,
213	node_iterator,
214	E_Access_Traits,
215	Allocator>*
216      null_node_update_pointer;
217    };
218
219    template<typename Key,
220	     class E_Access_Traits,
221	     template<typename Const_Node_Iterator,
222		      class Node_Iterator,
223		      class Cmp_Fn_,
224		      class Allocator_>
225    class Node_Update,
226	     class Allocator>
227    struct trie_traits<
228      Key,
229      null_mapped_type,
230      E_Access_Traits,
231      Node_Update,
232      pat_trie_tag,
233      Allocator>
234    {
235    private:
236      typedef
237      types_traits<
238      Key,
239      null_mapped_type,
240      Allocator,
241      false>
242      type_traits;
243
244    public:
245      typedef
246      typename trie_node_metadata_selector<
247      Key,
248      null_mapped_type,
249      E_Access_Traits,
250      Node_Update,
251      Allocator>::type
252      metadata_type;
253
254      typedef E_Access_Traits e_access_traits;
255
256      typedef
257      synth_e_access_traits<
258	type_traits,
259	true,
260	e_access_traits>
261      synth_e_access_traits;
262
263      typedef
264      pat_trie_node_base<
265	type_traits,
266	synth_e_access_traits,
267	metadata_type,
268	Allocator>
269      node;
270
271      typedef
272      pat_trie_leaf<
273	type_traits,
274	synth_e_access_traits,
275	metadata_type,
276	Allocator>
277      leaf;
278
279      typedef
280      pat_trie_head<
281	type_traits,
282	synth_e_access_traits,
283	metadata_type,
284	Allocator>
285      head;
286
287      typedef
288      pat_trie_internal_node<
289	type_traits,
290	synth_e_access_traits,
291	metadata_type,
292	Allocator>
293      internal_node;
294
295      typedef
296      pat_trie_const_it_<
297	type_traits,
298	node,
299	leaf,
300	head,
301	internal_node,
302	true,
303	Allocator>
304      const_iterator;
305
306      typedef const_iterator iterator;
307
308      typedef
309      pat_trie_const_it_<
310	type_traits,
311	node,
312	leaf,
313	head,
314	internal_node,
315	false,
316	Allocator>
317      const_reverse_iterator;
318
319      typedef const_reverse_iterator reverse_iterator;
320
321      typedef
322      pat_trie_const_node_it_<
323	node,
324	leaf,
325	head,
326	internal_node,
327	const_iterator,
328	iterator,
329	synth_e_access_traits,
330	Allocator>
331      const_node_iterator;
332
333      typedef const_node_iterator node_iterator;
334
335      typedef
336      Node_Update<
337	const_node_iterator,
338	node_iterator,
339	E_Access_Traits,
340	Allocator>
341      node_update;
342
343      typedef
344      pb_ds::null_trie_node_update<
345	const_node_iterator,
346	const_node_iterator,
347	E_Access_Traits,
348	Allocator>*
349      null_node_update_pointer;
350    };
351
352  } // namespace detail
353} // namespace pb_ds
354
355#endif // #ifndef PB_DS_PAT_TRIE_NODE_AND_IT_TRAITS_HPP
356
357