]>
Commit | Line | Data |
---|---|---|
4569a895 AT |
1 | // -*- C++ -*- |
2 | ||
7adcbafe | 3 | // Copyright (C) 2005-2022 Free Software Foundation, Inc. |
4569a895 AT |
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 | |
748086b7 | 8 | // Foundation; either version 3, or (at your option) any later |
4569a895 AT |
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 | ||
748086b7 JJ |
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. | |
19 | ||
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/>. | |
4569a895 AT |
24 | |
25 | // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. | |
26 | ||
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 | |
34 | // warranty. | |
35 | ||
36 | /** | |
37 | * @file tag_and_trait.hpp | |
38 | * Contains tags and traits, e.g., ones describing underlying | |
a345e45d | 39 | * data structures. |
4569a895 AT |
40 | */ |
41 | ||
42 | #ifndef PB_DS_TAG_AND_TRAIT_HPP | |
43 | #define PB_DS_TAG_AND_TRAIT_HPP | |
44 | ||
8fc81078 | 45 | #include <bits/c++config.h> |
4569a895 AT |
46 | #include <ext/pb_ds/detail/type_utils.hpp> |
47 | ||
551fe1a2 | 48 | /** |
5e11f978 | 49 | * @namespace __gnu_pbds |
939759fc | 50 | * @brief GNU extensions for policy-based data structures for public use. |
551fe1a2 | 51 | */ |
5e11f978 | 52 | namespace __gnu_pbds |
4569a895 | 53 | { |
a345e45d BK |
54 | /** @defgroup pbds Policy-Based Data Structures |
55 | * @ingroup extensions | |
56 | * | |
57 | * This is a library of policy-based elementary data structures: | |
58 | * associative containers and priority queues. It is designed for | |
59 | * high-performance, flexibility, semantic safety, and conformance | |
60 | * to the corresponding containers in std (except for some points | |
61 | * where it differs by design). | |
62 | * | |
63 | * For details, see: | |
64 | * http://gcc.gnu.org/onlinedocs/libstdc++/ext/pb_ds/index.html | |
65 | * | |
66 | * @{ | |
67 | */ | |
68 | ||
69 | /** | |
70 | * @defgroup tags Tags | |
71 | * @{ | |
72 | */ | |
73 | /// A trivial iterator tag. Signifies that the iterators has none of | |
30a96b3b | 74 | /// std::iterators's movement abilities. |
4569a895 AT |
75 | struct trivial_iterator_tag |
76 | { }; | |
77 | ||
a345e45d | 78 | /// Prohibit moving trivial iterators. |
4569a895 AT |
79 | typedef void trivial_iterator_difference_type; |
80 | ||
81 | ||
a345e45d | 82 | /** |
30a96b3b | 83 | * @defgroup invalidation_tags Invalidation Guarantees |
a345e45d BK |
84 | * @ingroup tags |
85 | * @{ | |
86 | */ | |
87 | ||
88 | /** | |
89 | * Signifies a basic invalidation guarantee that any iterator, | |
90 | * pointer, or reference to a container object's mapped value type | |
91 | * is valid as long as the container is not modified. | |
92 | */ | |
4569a895 AT |
93 | struct basic_invalidation_guarantee |
94 | { }; | |
95 | ||
a345e45d BK |
96 | /** |
97 | * Signifies an invalidation guarantee that includes all those of | |
98 | * its base, and additionally, that any point-type iterator, | |
99 | * pointer, or reference to a container object's mapped value type | |
100 | * is valid as long as its corresponding entry has not be erased, | |
101 | * regardless of modifications to the container object. | |
102 | */ | |
4569a895 AT |
103 | struct point_invalidation_guarantee : public basic_invalidation_guarantee |
104 | { }; | |
105 | ||
a345e45d BK |
106 | /** |
107 | * Signifies an invalidation guarantee that includes all those of | |
108 | * its base, and additionally, that any range-type iterator | |
109 | * (including the returns of begin() and end()) is in the correct | |
110 | * relative positions to other range-type iterators as long as its | |
111 | * corresponding entry has not be erased, regardless of | |
112 | * modifications to the container object. | |
113 | */ | |
4569a895 AT |
114 | struct range_invalidation_guarantee : public point_invalidation_guarantee |
115 | { }; | |
f0b88346 | 116 | ///@} |
4569a895 AT |
117 | |
118 | ||
a345e45d | 119 | /** |
30a96b3b | 120 | * @defgroup ds_tags Data Structure Type |
a345e45d BK |
121 | * @ingroup tags |
122 | * @{ | |
123 | */ | |
2e3f9c21 | 124 | /// Base data structure tag. |
4569a895 AT |
125 | struct container_tag |
126 | { }; | |
127 | ||
2e3f9c21 BK |
128 | /// Basic sequence. |
129 | struct sequence_tag : public container_tag { }; | |
130 | ||
a345e45d BK |
131 | /// Basic string container, inclusive of strings, ropes, etc. |
132 | struct string_tag : public sequence_tag { }; | |
133 | ||
2e3f9c21 | 134 | /// Basic associative-container. |
a345e45d | 135 | struct associative_tag : public container_tag { }; |
4569a895 | 136 | |
a345e45d BK |
137 | /// Basic hash structure. |
138 | struct basic_hash_tag : public associative_tag { }; | |
4569a895 | 139 | |
2e3f9c21 | 140 | /// Collision-chaining hash. |
4569a895 AT |
141 | struct cc_hash_tag : public basic_hash_tag { }; |
142 | ||
2e3f9c21 | 143 | /// General-probing hash. |
4569a895 AT |
144 | struct gp_hash_tag : public basic_hash_tag { }; |
145 | ||
a345e45d BK |
146 | /// Basic branch structure. |
147 | struct basic_branch_tag : public associative_tag { }; | |
4569a895 | 148 | |
30a96b3b | 149 | /// Basic tree structure. |
a345e45d | 150 | struct tree_tag : public basic_branch_tag { }; |
4569a895 | 151 | |
2e3f9c21 | 152 | /// Red-black tree. |
4569a895 AT |
153 | struct rb_tree_tag : public tree_tag { }; |
154 | ||
2e3f9c21 | 155 | /// Splay tree. |
4569a895 AT |
156 | struct splay_tree_tag : public tree_tag { }; |
157 | ||
2e3f9c21 | 158 | /// Ordered-vector tree. |
4569a895 AT |
159 | struct ov_tree_tag : public tree_tag { }; |
160 | ||
30a96b3b | 161 | /// Basic trie structure. |
a345e45d | 162 | struct trie_tag : public basic_branch_tag { }; |
4569a895 | 163 | |
2e3f9c21 | 164 | /// PATRICIA trie. |
4569a895 AT |
165 | struct pat_trie_tag : public trie_tag { }; |
166 | ||
2e3f9c21 | 167 | /// List-update. |
a345e45d | 168 | struct list_update_tag : public associative_tag { }; |
4569a895 | 169 | |
2e3f9c21 | 170 | /// Basic priority-queue. |
4569a895 AT |
171 | struct priority_queue_tag : public container_tag { }; |
172 | ||
2e3f9c21 | 173 | /// Pairing-heap. |
4569a895 AT |
174 | struct pairing_heap_tag : public priority_queue_tag { }; |
175 | ||
2e3f9c21 | 176 | /// Binomial-heap. |
4569a895 AT |
177 | struct binomial_heap_tag : public priority_queue_tag { }; |
178 | ||
2e3f9c21 | 179 | /// Redundant-counter binomial-heap. |
4569a895 AT |
180 | struct rc_binomial_heap_tag : public priority_queue_tag { }; |
181 | ||
2e3f9c21 | 182 | /// Binary-heap (array-based). |
4569a895 AT |
183 | struct binary_heap_tag : public priority_queue_tag { }; |
184 | ||
2e3f9c21 | 185 | /// Thin heap. |
4569a895 | 186 | struct thin_heap_tag : public priority_queue_tag { }; |
f0b88346 JW |
187 | ///@} |
188 | ///@} | |
a345e45d BK |
189 | |
190 | ||
191 | /** | |
192 | * @defgroup traits Traits | |
193 | * @{ | |
194 | */ | |
195 | ||
196 | /** | |
197 | * @brief Represents no type, or absence of type, for template tricks. | |
198 | * | |
199 | * In a mapped-policy, indicates that an associative container is a set. | |
200 | * | |
201 | * In a list-update policy, indicates that each link does not need | |
202 | * metadata. | |
203 | * | |
204 | * In a hash policy, indicates that the combining hash function | |
205 | * is actually a ranged hash function. | |
206 | * | |
207 | * In a probe policy, indicates that the combining probe function | |
208 | * is actually a ranged probe function. | |
209 | */ | |
210 | struct null_type { }; | |
211 | ||
30a96b3b BK |
212 | /// A null node updator, indicating that no node updates are required. |
213 | template<typename _Tp1, typename _Tp2, typename _Tp3, typename _Tp4> | |
214 | struct null_node_update : public null_type | |
215 | { }; | |
216 | ||
a345e45d BK |
217 | |
218 | /// Primary template, container traits base. | |
219 | template<typename _Tag> | |
220 | struct container_traits_base; | |
221 | ||
222 | /// Specialization, cc hash. | |
4569a895 AT |
223 | template<> |
224 | struct container_traits_base<cc_hash_tag> | |
225 | { | |
30a96b3b BK |
226 | typedef cc_hash_tag container_category; |
227 | typedef point_invalidation_guarantee invalidation_guarantee; | |
4569a895 AT |
228 | |
229 | enum | |
230 | { | |
a345e45d BK |
231 | order_preserving = false, |
232 | erase_can_throw = false, | |
4569a895 AT |
233 | split_join_can_throw = false, |
234 | reverse_iteration = false | |
235 | }; | |
236 | }; | |
237 | ||
a345e45d | 238 | /// Specialization, gp hash. |
4569a895 AT |
239 | template<> |
240 | struct container_traits_base<gp_hash_tag> | |
241 | { | |
30a96b3b BK |
242 | typedef gp_hash_tag container_category; |
243 | typedef basic_invalidation_guarantee invalidation_guarantee; | |
4569a895 AT |
244 | |
245 | enum | |
246 | { | |
a345e45d | 247 | order_preserving = false, |
4569a895 AT |
248 | erase_can_throw = false, |
249 | split_join_can_throw = false, | |
250 | reverse_iteration = false | |
251 | }; | |
252 | }; | |
253 | ||
a345e45d | 254 | /// Specialization, rb tree. |
4569a895 AT |
255 | template<> |
256 | struct container_traits_base<rb_tree_tag> | |
257 | { | |
30a96b3b BK |
258 | typedef rb_tree_tag container_category; |
259 | typedef range_invalidation_guarantee invalidation_guarantee; | |
4569a895 AT |
260 | |
261 | enum | |
262 | { | |
a345e45d BK |
263 | order_preserving = true, |
264 | erase_can_throw = false, | |
4569a895 | 265 | split_join_can_throw = false, |
a345e45d | 266 | reverse_iteration = true |
4569a895 AT |
267 | }; |
268 | }; | |
269 | ||
a345e45d | 270 | /// Specialization, splay tree. |
4569a895 AT |
271 | template<> |
272 | struct container_traits_base<splay_tree_tag> | |
273 | { | |
30a96b3b BK |
274 | typedef splay_tree_tag container_category; |
275 | typedef range_invalidation_guarantee invalidation_guarantee; | |
4569a895 AT |
276 | |
277 | enum | |
278 | { | |
a345e45d BK |
279 | order_preserving = true, |
280 | erase_can_throw = false, | |
281 | split_join_can_throw = false, | |
282 | reverse_iteration = true | |
4569a895 AT |
283 | }; |
284 | }; | |
285 | ||
a345e45d | 286 | /// Specialization, ov tree. |
4569a895 AT |
287 | template<> |
288 | struct container_traits_base<ov_tree_tag> | |
289 | { | |
30a96b3b BK |
290 | typedef ov_tree_tag container_category; |
291 | typedef basic_invalidation_guarantee invalidation_guarantee; | |
4569a895 AT |
292 | |
293 | enum | |
294 | { | |
a345e45d BK |
295 | order_preserving = true, |
296 | erase_can_throw = true, | |
297 | split_join_can_throw = true, | |
298 | reverse_iteration = false | |
4569a895 AT |
299 | }; |
300 | }; | |
301 | ||
a345e45d | 302 | /// Specialization, pat trie. |
4569a895 AT |
303 | template<> |
304 | struct container_traits_base<pat_trie_tag> | |
305 | { | |
30a96b3b BK |
306 | typedef pat_trie_tag container_category; |
307 | typedef range_invalidation_guarantee invalidation_guarantee; | |
4569a895 AT |
308 | |
309 | enum | |
310 | { | |
a345e45d BK |
311 | order_preserving = true, |
312 | erase_can_throw = false, | |
313 | split_join_can_throw = true, | |
314 | reverse_iteration = true | |
4569a895 AT |
315 | }; |
316 | }; | |
317 | ||
a345e45d | 318 | /// Specialization, list update. |
4569a895 AT |
319 | template<> |
320 | struct container_traits_base<list_update_tag> | |
321 | { | |
30a96b3b BK |
322 | typedef list_update_tag container_category; |
323 | typedef point_invalidation_guarantee invalidation_guarantee; | |
4569a895 AT |
324 | |
325 | enum | |
326 | { | |
a345e45d BK |
327 | order_preserving = false, |
328 | erase_can_throw = false, | |
4569a895 | 329 | split_join_can_throw = false, |
a345e45d | 330 | reverse_iteration = false |
4569a895 AT |
331 | }; |
332 | }; | |
333 | ||
a345e45d | 334 | /// Specialization, pairing heap. |
4569a895 AT |
335 | template<> |
336 | struct container_traits_base<pairing_heap_tag> | |
337 | { | |
30a96b3b BK |
338 | typedef pairing_heap_tag container_category; |
339 | typedef point_invalidation_guarantee invalidation_guarantee; | |
4569a895 AT |
340 | |
341 | enum | |
342 | { | |
a345e45d BK |
343 | order_preserving = false, |
344 | erase_can_throw = false, | |
4569a895 | 345 | split_join_can_throw = false, |
a345e45d | 346 | reverse_iteration = false |
4569a895 AT |
347 | }; |
348 | }; | |
349 | ||
a345e45d | 350 | /// Specialization, thin heap. |
4569a895 AT |
351 | template<> |
352 | struct container_traits_base<thin_heap_tag> | |
353 | { | |
30a96b3b BK |
354 | typedef thin_heap_tag container_category; |
355 | typedef point_invalidation_guarantee invalidation_guarantee; | |
4569a895 AT |
356 | |
357 | enum | |
358 | { | |
a345e45d BK |
359 | order_preserving = false, |
360 | erase_can_throw = false, | |
4569a895 | 361 | split_join_can_throw = false, |
a345e45d | 362 | reverse_iteration = false |
4569a895 AT |
363 | }; |
364 | }; | |
365 | ||
a345e45d | 366 | /// Specialization, binomial heap. |
4569a895 AT |
367 | template<> |
368 | struct container_traits_base<binomial_heap_tag> | |
369 | { | |
30a96b3b BK |
370 | typedef binomial_heap_tag container_category; |
371 | typedef point_invalidation_guarantee invalidation_guarantee; | |
4569a895 AT |
372 | |
373 | enum | |
374 | { | |
a345e45d BK |
375 | order_preserving = false, |
376 | erase_can_throw = false, | |
4569a895 | 377 | split_join_can_throw = false, |
a345e45d | 378 | reverse_iteration = false |
4569a895 AT |
379 | }; |
380 | }; | |
381 | ||
a345e45d | 382 | /// Specialization, rc binomial heap. |
4569a895 AT |
383 | template<> |
384 | struct container_traits_base<rc_binomial_heap_tag> | |
385 | { | |
30a96b3b BK |
386 | typedef rc_binomial_heap_tag container_category; |
387 | typedef point_invalidation_guarantee invalidation_guarantee; | |
4569a895 AT |
388 | |
389 | enum | |
390 | { | |
a345e45d BK |
391 | order_preserving = false, |
392 | erase_can_throw = false, | |
4569a895 | 393 | split_join_can_throw = false, |
a345e45d | 394 | reverse_iteration = false |
4569a895 AT |
395 | }; |
396 | }; | |
397 | ||
a345e45d | 398 | /// Specialization, binary heap. |
4569a895 AT |
399 | template<> |
400 | struct container_traits_base<binary_heap_tag> | |
401 | { | |
30a96b3b BK |
402 | typedef binary_heap_tag container_category; |
403 | typedef basic_invalidation_guarantee invalidation_guarantee; | |
4569a895 AT |
404 | |
405 | enum | |
406 | { | |
a345e45d BK |
407 | order_preserving = false, |
408 | erase_can_throw = false, | |
4569a895 | 409 | split_join_can_throw = true, |
a345e45d | 410 | reverse_iteration = false |
4569a895 AT |
411 | }; |
412 | }; | |
413 | ||
2e3f9c21 | 414 | |
a345e45d | 415 | /// Container traits. |
4569a895 AT |
416 | // See Matt Austern for the name, S. Meyers MEFC++ #2, others. |
417 | template<typename Cntnr> | |
a345e45d | 418 | struct container_traits |
4569a895 AT |
419 | : public container_traits_base<typename Cntnr::container_category> |
420 | { | |
a345e45d BK |
421 | typedef Cntnr container_type; |
422 | typedef typename Cntnr::container_category container_category; | |
423 | typedef container_traits_base<container_category> base_type; | |
4569a895 AT |
424 | typedef typename base_type::invalidation_guarantee invalidation_guarantee; |
425 | ||
426 | enum | |
427 | { | |
30a96b3b | 428 | /// True only if Cntnr objects guarantee storing keys by order. |
4569a895 | 429 | order_preserving = base_type::order_preserving, |
30a96b3b BK |
430 | |
431 | /// True only if erasing a key can throw. | |
4569a895 | 432 | erase_can_throw = base_type::erase_can_throw, |
30a96b3b BK |
433 | |
434 | /// True only if split or join operations can throw. | |
4569a895 | 435 | split_join_can_throw = base_type::split_join_can_throw, |
30a96b3b BK |
436 | |
437 | /// True only reverse iterators are supported. | |
4569a895 AT |
438 | reverse_iteration = base_type::reverse_iteration |
439 | }; | |
440 | }; | |
f0b88346 | 441 | ///@} |
a345e45d BK |
442 | |
443 | ||
444 | namespace detail | |
445 | { | |
446 | /// Dispatch mechanism, primary template for associative types. | |
447 | template<typename Key, typename Mapped, typename _Alloc, typename Tag, | |
448 | typename Policy_Tl = null_type> | |
449 | struct container_base_dispatch; | |
237c8b9d | 450 | } // namespace detail |
f0b88346 | 451 | ///@} |
5e11f978 | 452 | } // namespace __gnu_pbds |
4569a895 AT |
453 | |
454 | #endif |