]>
Commit | Line | Data |
---|---|---|
4569a895 AT |
1 | // -*- C++ -*- |
2 | ||
748086b7 | 3 | // Copyright (C) 2005, 2006, 2007, 2009 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 pat_trie_.hpp | |
38 | * Contains an implementation class for a patricia tree. | |
39 | */ | |
40 | ||
41 | /** | |
42 | * This implementation loosely borrows ideas from: | |
2a60a9f6 BK |
43 | * 1) Fast Mergeable Integer Maps, Okasaki, Gill 1998 |
44 | * 2) Ptset: Sets of integers implemented as Patricia trees, | |
4569a895 AT |
45 | * Jean-Christophe Filliatr, 2000 |
46 | **/ | |
47 | ||
48 | #include <ext/pb_ds/detail/pat_trie_/synth_e_access_traits.hpp> | |
49 | #include <ext/pb_ds/detail/pat_trie_/node_base.hpp> | |
50 | #include <ext/pb_ds/exception.hpp> | |
51 | #include <ext/pb_ds/tag_and_trait.hpp> | |
52 | #include <ext/pb_ds/detail/eq_fn/eq_by_less.hpp> | |
53 | #include <ext/pb_ds/detail/types_traits.hpp> | |
54 | #include <ext/pb_ds/tree_policy.hpp> | |
55 | #include <ext/pb_ds/detail/cond_dealtor.hpp> | |
56 | #include <ext/pb_ds/detail/type_utils.hpp> | |
57 | #include <iterator> | |
58 | #include <utility> | |
59 | #include <algorithm> | |
60 | #include <functional> | |
61 | #include <assert.h> | |
62 | #include <list> | |
47bea7b8 | 63 | #ifdef _GLIBCXX_DEBUG |
551fe1a2 | 64 | #include <ext/pb_ds/detail/debug_map_base.hpp> |
47bea7b8 BK |
65 | #endif |
66 | #include <debug/debug.h> | |
4569a895 | 67 | |
5e11f978 | 68 | namespace __gnu_pbds |
4569a895 AT |
69 | { |
70 | namespace detail | |
71 | { | |
1b24692f BK |
72 | #define PB_DS_CLASS_T_DEC \ |
73 | template<typename Key, typename Mapped, typename Node_And_It_Traits, \ | |
74 | typename Allocator> | |
4569a895 AT |
75 | |
76 | #ifdef PB_DS_DATA_TRUE_INDICATOR | |
1b24692f | 77 | #define PB_DS_CLASS_NAME pat_trie_data_ |
47bea7b8 | 78 | #endif |
4569a895 AT |
79 | |
80 | #ifdef PB_DS_DATA_FALSE_INDICATOR | |
1b24692f | 81 | #define PB_DS_CLASS_NAME pat_trie_no_data_ |
47bea7b8 | 82 | #endif |
4569a895 | 83 | |
1b24692f BK |
84 | #define PB_DS_CLASS_C_DEC \ |
85 | PB_DS_CLASS_NAME<Key, Mapped, Node_And_It_Traits, Allocator> | |
4569a895 | 86 | |
1b24692f BK |
87 | #define PB_DS_TYPES_TRAITS_C_DEC \ |
88 | types_traits<Key, Mapped, Allocator, false> | |
4569a895 | 89 | |
47bea7b8 | 90 | #ifdef _GLIBCXX_DEBUG |
551fe1a2 BK |
91 | #define PB_DS_DEBUG_MAP_BASE_C_DEC \ |
92 | debug_map_base<Key, eq_by_less<Key, \ | |
47bea7b8 BK |
93 | std::less<Key> >, typename Allocator::template rebind<Key>::other::const_reference> |
94 | #endif | |
4569a895 AT |
95 | |
96 | #ifdef PB_DS_DATA_TRUE_INDICATOR | |
97 | #define PB_DS_V2F(X) (X).first | |
98 | #define PB_DS_V2S(X) (X).second | |
99 | #define PB_DS_EP2VP(X)& ((X)->m_value) | |
47bea7b8 | 100 | #endif |
4569a895 AT |
101 | |
102 | #ifdef PB_DS_DATA_FALSE_INDICATOR | |
103 | #define PB_DS_V2F(X) (X) | |
104 | #define PB_DS_V2S(X) Mapped_Data() | |
105 | #define PB_DS_EP2VP(X)& ((X)->m_value.first) | |
47bea7b8 | 106 | #endif |
4569a895 | 107 | |
4569a895 AT |
108 | /** |
109 | * class description = PATRICIA trie implementation."> | |
110 | **/ | |
111 | template<typename Key, | |
112 | typename Mapped, | |
1b24692f BK |
113 | typename Node_And_It_Traits, |
114 | typename Allocator> | |
4569a895 | 115 | class PB_DS_CLASS_NAME : |
47bea7b8 | 116 | #ifdef _GLIBCXX_DEBUG |
551fe1a2 | 117 | public PB_DS_DEBUG_MAP_BASE_C_DEC, |
47bea7b8 | 118 | #endif |
4569a895 AT |
119 | public Node_And_It_Traits::synth_e_access_traits, |
120 | public Node_And_It_Traits::node_update, | |
121 | public PB_DS_TYPES_TRAITS_C_DEC | |
122 | { | |
4569a895 | 123 | private: |
1b24692f | 124 | typedef PB_DS_TYPES_TRAITS_C_DEC traits_base; |
4569a895 | 125 | |
1b24692f BK |
126 | typedef typename Node_And_It_Traits::synth_e_access_traits synth_e_access_traits; |
127 | typedef typename Allocator::template rebind<synth_e_access_traits>::other::const_pointer const_e_access_traits_pointer; | |
128 | typedef typename synth_e_access_traits::const_iterator const_e_iterator; | |
4569a895 AT |
129 | |
130 | typedef typename Node_And_It_Traits::node node; | |
1b24692f | 131 | typedef typename Allocator::template rebind<node>::other::const_pointer const_node_pointer; |
4569a895 | 132 | |
1b24692f | 133 | typedef typename Allocator::template rebind<node>::other::pointer node_pointer; |
4569a895 AT |
134 | |
135 | typedef typename Node_And_It_Traits::head head; | |
1b24692f | 136 | typedef typename Allocator::template rebind<head>::other head_allocator; |
4569a895 AT |
137 | typedef typename head_allocator::pointer head_pointer; |
138 | ||
139 | typedef typename Node_And_It_Traits::leaf leaf; | |
1b24692f | 140 | typedef typename Allocator::template rebind<leaf>::other leaf_allocator; |
4569a895 | 141 | typedef typename leaf_allocator::const_pointer const_leaf_pointer; |
4569a895 AT |
142 | typedef typename leaf_allocator::pointer leaf_pointer; |
143 | ||
144 | typedef typename Node_And_It_Traits::internal_node internal_node; | |
1b24692f BK |
145 | typedef typename Allocator::template rebind<internal_node>::other internal_node_allocator; |
146 | typedef typename internal_node_allocator::const_pointer const_internal_node_pointer; | |
147 | typedef typename internal_node_allocator::pointer internal_node_pointer; | |
4569a895 AT |
148 | |
149 | #include <ext/pb_ds/detail/pat_trie_/cond_dtor_entry_dealtor.hpp> | |
150 | ||
47bea7b8 | 151 | #ifdef _GLIBCXX_DEBUG |
551fe1a2 | 152 | typedef PB_DS_DEBUG_MAP_BASE_C_DEC debug_base; |
47bea7b8 | 153 | #endif |
4569a895 AT |
154 | |
155 | #include <ext/pb_ds/detail/pat_trie_/split_join_branch_bag.hpp> | |
156 | ||
1b24692f | 157 | typedef typename Node_And_It_Traits::null_node_update_pointer null_node_update_pointer; |
4569a895 AT |
158 | |
159 | public: | |
160 | typedef pat_trie_tag container_category; | |
b67758fe | 161 | typedef Allocator allocator_type; |
4569a895 | 162 | typedef typename Allocator::size_type size_type; |
4569a895 AT |
163 | typedef typename Allocator::difference_type difference_type; |
164 | ||
1b24692f BK |
165 | typedef typename traits_base::key_type key_type; |
166 | typedef typename traits_base::key_pointer key_pointer; | |
167 | typedef typename traits_base::const_key_pointer const_key_pointer; | |
168 | typedef typename traits_base::key_reference key_reference; | |
169 | typedef typename traits_base::const_key_reference const_key_reference; | |
170 | typedef typename traits_base::mapped_type mapped_type; | |
171 | typedef typename traits_base::mapped_pointer mapped_pointer; | |
172 | typedef typename traits_base::const_mapped_pointer const_mapped_pointer; | |
173 | typedef typename traits_base::mapped_reference mapped_reference; | |
174 | typedef typename traits_base::const_mapped_reference const_mapped_reference; | |
175 | typedef typename traits_base::value_type value_type; | |
176 | typedef typename traits_base::pointer pointer; | |
177 | typedef typename traits_base::const_pointer const_pointer; | |
178 | typedef typename traits_base::reference reference; | |
179 | typedef typename traits_base::const_reference const_reference; | |
180 | ||
181 | typedef typename Node_And_It_Traits::const_iterator const_point_iterator; | |
4569a895 | 182 | typedef typename Node_And_It_Traits::iterator point_iterator; |
4569a895 | 183 | typedef const_point_iterator const_iterator; |
4569a895 AT |
184 | typedef point_iterator iterator; |
185 | ||
1b24692f | 186 | typedef typename Node_And_It_Traits::const_reverse_iterator const_reverse_iterator; |
4569a895 | 187 | typedef typename Node_And_It_Traits::reverse_iterator reverse_iterator; |
1b24692f | 188 | typedef typename Node_And_It_Traits::const_node_iterator const_node_iterator; |
4569a895 | 189 | typedef typename Node_And_It_Traits::node_iterator node_iterator; |
4569a895 | 190 | typedef typename Node_And_It_Traits::e_access_traits e_access_traits; |
4569a895 AT |
191 | typedef typename Node_And_It_Traits::node_update node_update; |
192 | ||
4569a895 AT |
193 | PB_DS_CLASS_NAME(); |
194 | ||
1b24692f | 195 | PB_DS_CLASS_NAME(const e_access_traits&); |
4569a895 | 196 | |
1b24692f | 197 | PB_DS_CLASS_NAME(const PB_DS_CLASS_C_DEC&); |
4569a895 AT |
198 | |
199 | void | |
1b24692f | 200 | swap(PB_DS_CLASS_C_DEC&); |
4569a895 AT |
201 | |
202 | ~PB_DS_CLASS_NAME(); | |
203 | ||
204 | inline bool | |
205 | empty() const; | |
206 | ||
207 | inline size_type | |
208 | size() const; | |
209 | ||
210 | inline size_type | |
211 | max_size() const; | |
212 | ||
213 | e_access_traits& | |
214 | get_e_access_traits(); | |
215 | ||
216 | const e_access_traits& | |
217 | get_e_access_traits() const; | |
218 | ||
219 | node_update& | |
220 | get_node_update(); | |
221 | ||
222 | const node_update& | |
223 | get_node_update() const; | |
224 | ||
1b24692f BK |
225 | inline std::pair<point_iterator, bool> |
226 | insert(const_reference); | |
4569a895 AT |
227 | |
228 | inline mapped_reference | |
229 | operator[](const_key_reference r_key) | |
230 | { | |
231 | #ifdef PB_DS_DATA_TRUE_INDICATOR | |
1b24692f BK |
232 | return insert(std::make_pair(r_key, mapped_type())).first->second; |
233 | #else | |
4569a895 | 234 | insert(r_key); |
1b24692f BK |
235 | return traits_base::s_null_mapped; |
236 | #endif | |
4569a895 AT |
237 | } |
238 | ||
239 | inline point_iterator | |
1b24692f | 240 | find(const_key_reference); |
4569a895 AT |
241 | |
242 | inline const_point_iterator | |
1b24692f | 243 | find(const_key_reference) const; |
4569a895 AT |
244 | |
245 | inline point_iterator | |
1b24692f | 246 | lower_bound(const_key_reference); |
4569a895 AT |
247 | |
248 | inline const_point_iterator | |
1b24692f | 249 | lower_bound(const_key_reference) const; |
4569a895 AT |
250 | |
251 | inline point_iterator | |
1b24692f | 252 | upper_bound(const_key_reference); |
4569a895 AT |
253 | |
254 | inline const_point_iterator | |
1b24692f | 255 | upper_bound(const_key_reference) const; |
4569a895 AT |
256 | |
257 | void | |
258 | clear(); | |
259 | ||
260 | inline bool | |
1b24692f | 261 | erase(const_key_reference); |
4569a895 AT |
262 | |
263 | inline const_iterator | |
1b24692f | 264 | erase(const_iterator); |
4569a895 AT |
265 | |
266 | #ifdef PB_DS_DATA_TRUE_INDICATOR | |
267 | inline iterator | |
1b24692f BK |
268 | erase(iterator); |
269 | #endif | |
4569a895 AT |
270 | |
271 | inline const_reverse_iterator | |
1b24692f | 272 | erase(const_reverse_iterator); |
4569a895 AT |
273 | |
274 | #ifdef PB_DS_DATA_TRUE_INDICATOR | |
275 | inline reverse_iterator | |
1b24692f BK |
276 | erase(reverse_iterator); |
277 | #endif | |
4569a895 AT |
278 | |
279 | template<typename Pred> | |
280 | inline size_type | |
1b24692f | 281 | erase_if(Pred); |
4569a895 AT |
282 | |
283 | void | |
1b24692f | 284 | join(PB_DS_CLASS_C_DEC&); |
4569a895 AT |
285 | |
286 | void | |
1b24692f | 287 | split(const_key_reference, PB_DS_CLASS_C_DEC&); |
4569a895 AT |
288 | |
289 | inline iterator | |
290 | begin(); | |
291 | ||
292 | inline const_iterator | |
293 | begin() const; | |
294 | ||
295 | inline iterator | |
296 | end(); | |
297 | ||
298 | inline const_iterator | |
299 | end() const; | |
300 | ||
301 | inline reverse_iterator | |
302 | rbegin(); | |
303 | ||
304 | inline const_reverse_iterator | |
305 | rbegin() const; | |
306 | ||
307 | inline reverse_iterator | |
308 | rend(); | |
309 | ||
310 | inline const_reverse_iterator | |
311 | rend() const; | |
312 | ||
313 | inline const_node_iterator | |
314 | node_begin() const; | |
315 | ||
316 | inline node_iterator | |
317 | node_begin(); | |
318 | ||
319 | inline const_node_iterator | |
320 | node_end() const; | |
321 | ||
322 | inline node_iterator | |
323 | node_end(); | |
324 | ||
325 | #ifdef PB_DS_PAT_TRIE_TRACE_ | |
4569a895 AT |
326 | void |
327 | trace() const; | |
1b24692f | 328 | #endif |
4569a895 AT |
329 | |
330 | protected: | |
331 | ||
332 | template<typename It> | |
333 | void | |
1b24692f | 334 | copy_from_range(It, It); |
4569a895 AT |
335 | |
336 | void | |
1b24692f | 337 | value_swap(PB_DS_CLASS_C_DEC&); |
4569a895 AT |
338 | |
339 | node_pointer | |
1b24692f | 340 | recursive_copy_node(const_node_pointer); |
4569a895 AT |
341 | |
342 | private: | |
343 | ||
344 | void | |
345 | initialize(); | |
346 | ||
347 | inline void | |
1b24692f | 348 | apply_update(node_pointer, null_node_update_pointer); |
4569a895 AT |
349 | |
350 | template<typename Node_Update_> | |
351 | inline void | |
1b24692f | 352 | apply_update(node_pointer, Node_Update_*); |
4569a895 AT |
353 | |
354 | bool | |
1b24692f | 355 | join_prep(PB_DS_CLASS_C_DEC&, split_join_branch_bag&); |
4569a895 AT |
356 | |
357 | void | |
1b24692f BK |
358 | rec_join_prep(const_node_pointer, const_node_pointer, |
359 | split_join_branch_bag&); | |
4569a895 AT |
360 | |
361 | void | |
1b24692f BK |
362 | rec_join_prep(const_leaf_pointer, const_leaf_pointer, |
363 | split_join_branch_bag&); | |
4569a895 AT |
364 | |
365 | void | |
1b24692f BK |
366 | rec_join_prep(const_leaf_pointer, const_internal_node_pointer, |
367 | split_join_branch_bag&); | |
4569a895 AT |
368 | |
369 | void | |
1b24692f BK |
370 | rec_join_prep(const_internal_node_pointer, const_leaf_pointer, |
371 | split_join_branch_bag&); | |
4569a895 AT |
372 | |
373 | void | |
1b24692f BK |
374 | rec_join_prep(const_internal_node_pointer, const_internal_node_pointer, |
375 | split_join_branch_bag&); | |
4569a895 AT |
376 | |
377 | node_pointer | |
1b24692f | 378 | rec_join(node_pointer, node_pointer, size_type, split_join_branch_bag&); |
4569a895 AT |
379 | |
380 | node_pointer | |
1b24692f | 381 | rec_join(leaf_pointer, leaf_pointer, split_join_branch_bag&); |
4569a895 AT |
382 | |
383 | node_pointer | |
1b24692f BK |
384 | rec_join(leaf_pointer, internal_node_pointer, size_type, |
385 | split_join_branch_bag&); | |
4569a895 AT |
386 | |
387 | node_pointer | |
1b24692f BK |
388 | rec_join(internal_node_pointer, leaf_pointer, size_type, |
389 | split_join_branch_bag&); | |
4569a895 AT |
390 | |
391 | node_pointer | |
1b24692f BK |
392 | rec_join(internal_node_pointer, internal_node_pointer, |
393 | split_join_branch_bag&); | |
4569a895 AT |
394 | |
395 | size_type | |
1b24692f | 396 | keys_diff_ind(typename e_access_traits::const_iterator, typename e_access_traits::const_iterator, typename e_access_traits::const_iterator, typename e_access_traits::const_iterator); |
4569a895 AT |
397 | |
398 | internal_node_pointer | |
1b24692f | 399 | insert_branch(node_pointer, node_pointer, split_join_branch_bag&); |
4569a895 AT |
400 | |
401 | void | |
1b24692f | 402 | update_min_max_for_inserted_leaf(leaf_pointer); |
4569a895 AT |
403 | |
404 | void | |
1b24692f | 405 | erase_leaf(leaf_pointer); |
4569a895 AT |
406 | |
407 | inline void | |
1b24692f | 408 | actual_erase_leaf(leaf_pointer); |
4569a895 AT |
409 | |
410 | void | |
1b24692f | 411 | clear_imp(node_pointer); |
4569a895 AT |
412 | |
413 | void | |
1b24692f | 414 | erase_fixup(internal_node_pointer); |
4569a895 AT |
415 | |
416 | void | |
1b24692f | 417 | update_min_max_for_erased_leaf(leaf_pointer); |
4569a895 AT |
418 | |
419 | static inline const_e_iterator | |
1b24692f | 420 | pref_begin(const_node_pointer); |
4569a895 AT |
421 | |
422 | static inline const_e_iterator | |
1b24692f | 423 | pref_end(const_node_pointer); |
4569a895 AT |
424 | |
425 | inline node_pointer | |
1b24692f | 426 | find_imp(const_key_reference); |
4569a895 AT |
427 | |
428 | inline node_pointer | |
1b24692f | 429 | lower_bound_imp(const_key_reference); |
4569a895 AT |
430 | |
431 | inline node_pointer | |
1b24692f | 432 | upper_bound_imp(const_key_reference); |
4569a895 AT |
433 | |
434 | inline static const_leaf_pointer | |
1b24692f | 435 | leftmost_descendant(const_node_pointer); |
4569a895 AT |
436 | |
437 | inline static leaf_pointer | |
1b24692f | 438 | leftmost_descendant(node_pointer); |
4569a895 AT |
439 | |
440 | inline static const_leaf_pointer | |
1b24692f | 441 | rightmost_descendant(const_node_pointer); |
4569a895 AT |
442 | |
443 | inline static leaf_pointer | |
1b24692f | 444 | rightmost_descendant(node_pointer); |
4569a895 | 445 | |
47bea7b8 | 446 | #ifdef _GLIBCXX_DEBUG |
4569a895 AT |
447 | void |
448 | assert_valid() const; | |
449 | ||
450 | void | |
451 | assert_iterators() const; | |
452 | ||
453 | void | |
454 | assert_reverse_iterators() const; | |
455 | ||
456 | static size_type | |
1b24692f | 457 | recursive_count_leafs(const_node_pointer); |
47bea7b8 | 458 | #endif |
4569a895 AT |
459 | |
460 | #ifdef PB_DS_PAT_TRIE_TRACE_ | |
4569a895 | 461 | static void |
1b24692f | 462 | trace_node(const_node_pointer, size_type); |
4569a895 AT |
463 | |
464 | template<typename Metadata_> | |
465 | static void | |
1b24692f | 466 | trace_node_metadata(const_node_pointer, type_to_type<Metadata_>); |
4569a895 AT |
467 | |
468 | static void | |
1b24692f | 469 | trace_node_metadata(const_node_pointer, type_to_type<null_node_metadata>); |
47bea7b8 | 470 | #endif |
4569a895 AT |
471 | |
472 | leaf_pointer | |
1b24692f BK |
473 | split_prep(const_key_reference, PB_DS_CLASS_C_DEC&, |
474 | split_join_branch_bag&); | |
4569a895 AT |
475 | |
476 | node_pointer | |
1b24692f BK |
477 | rec_split(node_pointer, const_e_iterator, const_e_iterator, |
478 | PB_DS_CLASS_C_DEC&, split_join_branch_bag&); | |
4569a895 AT |
479 | |
480 | void | |
1b24692f BK |
481 | split_insert_branch(size_type, const_e_iterator, |
482 | typename internal_node::iterator, | |
483 | size_type, split_join_branch_bag&); | |
4569a895 | 484 | |
4569a895 | 485 | static head_allocator s_head_allocator; |
4569a895 | 486 | static internal_node_allocator s_internal_node_allocator; |
4569a895 AT |
487 | static leaf_allocator s_leaf_allocator; |
488 | ||
489 | head_pointer m_p_head; | |
4569a895 AT |
490 | size_type m_size; |
491 | }; | |
492 | ||
493 | #include <ext/pb_ds/detail/pat_trie_/constructors_destructor_fn_imps.hpp> | |
494 | #include <ext/pb_ds/detail/pat_trie_/iterators_fn_imps.hpp> | |
495 | #include <ext/pb_ds/detail/pat_trie_/insert_join_fn_imps.hpp> | |
496 | #include <ext/pb_ds/detail/pat_trie_/erase_fn_imps.hpp> | |
497 | #include <ext/pb_ds/detail/pat_trie_/find_fn_imps.hpp> | |
498 | #include <ext/pb_ds/detail/pat_trie_/info_fn_imps.hpp> | |
499 | #include <ext/pb_ds/detail/pat_trie_/policy_access_fn_imps.hpp> | |
500 | #include <ext/pb_ds/detail/pat_trie_/split_fn_imps.hpp> | |
501 | #include <ext/pb_ds/detail/pat_trie_/debug_fn_imps.hpp> | |
502 | #include <ext/pb_ds/detail/pat_trie_/trace_fn_imps.hpp> | |
503 | #include <ext/pb_ds/detail/pat_trie_/update_fn_imps.hpp> | |
504 | ||
505 | #undef PB_DS_CLASS_C_DEC | |
4569a895 | 506 | #undef PB_DS_CLASS_T_DEC |
4569a895 | 507 | #undef PB_DS_CLASS_NAME |
4569a895 | 508 | #undef PB_DS_TYPES_TRAITS_C_DEC |
551fe1a2 | 509 | #undef PB_DS_DEBUG_MAP_BASE_C_DEC |
4569a895 AT |
510 | #undef PB_DS_V2F |
511 | #undef PB_DS_EP2VP | |
512 | #undef PB_DS_V2S | |
4569a895 AT |
513 | |
514 | } // namespace detail | |
5e11f978 | 515 | } // namespace __gnu_pbds |