xref: /openbsd-src/gnu/gcc/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/traits.hpp (revision 404b540a9034ac75a6199ad1a32d1bbc7a0d4210)
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 
58 namespace 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