]>
Commit | Line | Data |
---|---|---|
4569a895 AT |
1 | // -*- C++ -*- |
2 | ||
83ffe9cd | 3 | // Copyright (C) 2005-2023 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 | /** | |
a345e45d | 37 | * @file pat_trie_/pat_trie_.hpp |
4569a895 AT |
38 | * Contains an implementation class for a patricia tree. |
39 | */ | |
40 | ||
4569a895 AT |
41 | #include <iterator> |
42 | #include <utility> | |
43 | #include <algorithm> | |
44 | #include <functional> | |
45 | #include <assert.h> | |
46 | #include <list> | |
a345e45d BK |
47 | #include <ext/pb_ds/exception.hpp> |
48 | #include <ext/pb_ds/tag_and_trait.hpp> | |
49 | #include <ext/pb_ds/tree_policy.hpp> | |
50 | #include <ext/pb_ds/detail/cond_dealtor.hpp> | |
51 | #include <ext/pb_ds/detail/type_utils.hpp> | |
52 | #include <ext/pb_ds/detail/types_traits.hpp> | |
53 | #include <ext/pb_ds/detail/eq_fn/eq_by_less.hpp> | |
54 | #include <ext/pb_ds/detail/pat_trie_/synth_access_traits.hpp> | |
55 | #include <ext/pb_ds/detail/pat_trie_/pat_trie_base.hpp> | |
47bea7b8 | 56 | #ifdef _GLIBCXX_DEBUG |
551fe1a2 | 57 | #include <ext/pb_ds/detail/debug_map_base.hpp> |
a345e45d | 58 | #endif |
47bea7b8 | 59 | #include <debug/debug.h> |
4569a895 | 60 | |
5e11f978 | 61 | namespace __gnu_pbds |
4569a895 AT |
62 | { |
63 | namespace detail | |
64 | { | |
4569a895 | 65 | #ifdef PB_DS_DATA_TRUE_INDICATOR |
a345e45d BK |
66 | #define PB_DS_PAT_TRIE_NAME pat_trie_map |
67 | #endif | |
4569a895 AT |
68 | |
69 | #ifdef PB_DS_DATA_FALSE_INDICATOR | |
a345e45d BK |
70 | #define PB_DS_PAT_TRIE_NAME pat_trie_set |
71 | #endif | |
72 | ||
73 | #define PB_DS_CLASS_T_DEC \ | |
74 | template<typename Key, typename Mapped, typename Node_And_It_Traits, \ | |
75 | typename _Alloc> | |
4569a895 | 76 | |
1b24692f | 77 | #define PB_DS_CLASS_C_DEC \ |
a345e45d | 78 | PB_DS_PAT_TRIE_NAME<Key, Mapped, Node_And_It_Traits, _Alloc> |
4569a895 | 79 | |
a345e45d BK |
80 | #define PB_DS_PAT_TRIE_TRAITS_BASE \ |
81 | types_traits<Key, Mapped, _Alloc, false> | |
4569a895 | 82 | |
47bea7b8 | 83 | #ifdef _GLIBCXX_DEBUG |
551fe1a2 | 84 | #define PB_DS_DEBUG_MAP_BASE_C_DEC \ |
a345e45d | 85 | debug_map_base<Key, eq_by_less<Key, std::less<Key> >, \ |
ec541f1b | 86 | typename rebind_traits<_Alloc, Key>::const_reference> |
a345e45d | 87 | #endif |
4569a895 | 88 | |
4569a895 | 89 | |
4569a895 | 90 | /** |
a345e45d | 91 | * @brief PATRICIA trie. |
30a96b3b | 92 | * @ingroup branch-detail |
a345e45d | 93 | * |
30a96b3b BK |
94 | * This implementation loosely borrows ideas from: |
95 | * 1) Fast Mergeable Integer Maps, Okasaki, Gill 1998 | |
96 | * 2) Ptset: Sets of integers implemented as Patricia trees, | |
97 | * Jean-Christophe Filliatr, 2000 | |
a345e45d BK |
98 | */ |
99 | template<typename Key, typename Mapped, typename Node_And_It_Traits, | |
100 | typename _Alloc> | |
101 | class PB_DS_PAT_TRIE_NAME : | |
47bea7b8 | 102 | #ifdef _GLIBCXX_DEBUG |
551fe1a2 | 103 | public PB_DS_DEBUG_MAP_BASE_C_DEC, |
a345e45d BK |
104 | #endif |
105 | public Node_And_It_Traits::synth_access_traits, | |
4569a895 | 106 | public Node_And_It_Traits::node_update, |
a345e45d BK |
107 | public PB_DS_PAT_TRIE_TRAITS_BASE, |
108 | public pat_trie_base | |
4569a895 | 109 | { |
4569a895 | 110 | private: |
a345e45d | 111 | typedef pat_trie_base base_type; |
ec541f1b | 112 | typedef PB_DS_PAT_TRIE_TRAITS_BASE traits_base; |
a345e45d BK |
113 | typedef Node_And_It_Traits traits_type; |
114 | ||
115 | typedef typename traits_type::synth_access_traits synth_access_traits; | |
116 | typedef typename synth_access_traits::const_iterator a_const_iterator; | |
117 | ||
ec541f1b JW |
118 | typedef typename traits_type::node node; |
119 | typedef rebind_traits<_Alloc, node> __rebind_n; | |
120 | typedef typename __rebind_n::const_pointer node_const_pointer; | |
121 | typedef typename __rebind_n::pointer node_pointer; | |
a345e45d | 122 | |
ec541f1b JW |
123 | typedef typename traits_type::head head; |
124 | typedef rebind_traits<_Alloc, head> __rebind_h; | |
125 | typedef typename __rebind_h::allocator_type head_allocator; | |
126 | typedef typename __rebind_h::pointer head_pointer; | |
a345e45d | 127 | |
ec541f1b JW |
128 | typedef typename traits_type::leaf leaf; |
129 | typedef rebind_traits<_Alloc, leaf> __rebind_l; | |
130 | typedef typename __rebind_l::allocator_type leaf_allocator; | |
131 | typedef typename __rebind_l::pointer leaf_pointer; | |
132 | typedef typename __rebind_l::const_pointer leaf_const_pointer; | |
a345e45d | 133 | |
ec541f1b | 134 | typedef typename traits_type::inode inode; |
a345e45d | 135 | typedef typename inode::iterator inode_iterator; |
ec541f1b JW |
136 | typedef rebind_traits<_Alloc, inode> __rebind_in; |
137 | typedef typename __rebind_in::allocator_type inode_allocator; | |
138 | typedef typename __rebind_in::pointer inode_pointer; | |
139 | typedef typename __rebind_in::const_pointer inode_const_pointer; | |
a345e45d BK |
140 | |
141 | ||
142 | /// Conditional deallocator. | |
143 | class cond_dealtor | |
144 | { | |
145 | protected: | |
146 | leaf_pointer m_p_nd; | |
147 | bool m_no_action_dtor; | |
148 | bool m_call_destructor; | |
149 | ||
150 | public: | |
151 | cond_dealtor(leaf_pointer p_nd) | |
152 | : m_p_nd(p_nd), m_no_action_dtor(false), m_call_destructor(false) | |
153 | { } | |
4569a895 | 154 | |
a345e45d BK |
155 | void |
156 | set_no_action_dtor() | |
157 | { m_no_action_dtor = true; } | |
4569a895 | 158 | |
a345e45d BK |
159 | void |
160 | set_call_destructor() | |
161 | { m_call_destructor = true; } | |
4569a895 | 162 | |
a345e45d BK |
163 | ~cond_dealtor() |
164 | { | |
165 | if (m_no_action_dtor) | |
166 | return; | |
4569a895 | 167 | |
a345e45d BK |
168 | if (m_call_destructor) |
169 | m_p_nd->~leaf(); | |
4569a895 | 170 | |
a345e45d BK |
171 | s_leaf_allocator.deallocate(m_p_nd, 1); |
172 | } | |
173 | }; | |
4569a895 | 174 | |
4569a895 | 175 | |
a345e45d BK |
176 | /// Branch bag, for split-join. |
177 | class branch_bag | |
178 | { | |
179 | private: | |
180 | typedef inode_pointer __inp; | |
ec541f1b JW |
181 | typedef typename rebind_traits<_Alloc, __inp>::allocator_type |
182 | __rebind_inp; | |
4569a895 | 183 | |
47bea7b8 | 184 | #ifdef _GLIBCXX_DEBUG |
a345e45d BK |
185 | typedef std::_GLIBCXX_STD_C::list<__inp, __rebind_inp> bag_type; |
186 | #else | |
187 | typedef std::list<__inp, __rebind_inp> bag_type; | |
188 | #endif | |
189 | ||
190 | bag_type m_bag; | |
191 | public: | |
192 | void | |
193 | add_branch() | |
194 | { | |
195 | inode_pointer p_nd = s_inode_allocator.allocate(1); | |
196 | __try | |
197 | { | |
198 | m_bag.push_back(p_nd); | |
199 | } | |
200 | __catch(...) | |
201 | { | |
202 | s_inode_allocator.deallocate(p_nd, 1); | |
203 | __throw_exception_again; | |
204 | } | |
205 | } | |
206 | ||
207 | inode_pointer | |
208 | get_branch() | |
209 | { | |
210 | _GLIBCXX_DEBUG_ASSERT(!m_bag.empty()); | |
211 | inode_pointer p_nd = *m_bag.begin(); | |
212 | m_bag.pop_front(); | |
213 | return p_nd; | |
214 | } | |
215 | ||
216 | ~branch_bag() | |
217 | { | |
218 | while (!m_bag.empty()) | |
219 | { | |
220 | inode_pointer p_nd = *m_bag.begin(); | |
221 | s_inode_allocator.deallocate(p_nd, 1); | |
222 | m_bag.pop_front(); | |
223 | } | |
224 | } | |
225 | ||
d715f554 | 226 | _GLIBCXX_NODISCARD inline bool |
a345e45d BK |
227 | empty() const |
228 | { return m_bag.empty(); } | |
229 | }; | |
4569a895 | 230 | |
a345e45d BK |
231 | #ifdef _GLIBCXX_DEBUG |
232 | typedef PB_DS_DEBUG_MAP_BASE_C_DEC debug_base; | |
233 | #endif | |
4569a895 | 234 | |
a345e45d | 235 | typedef typename traits_type::null_node_update_pointer null_node_update_pointer; |
4569a895 AT |
236 | |
237 | public: | |
a345e45d BK |
238 | typedef pat_trie_tag container_category; |
239 | typedef _Alloc allocator_type; | |
240 | typedef typename _Alloc::size_type size_type; | |
241 | typedef typename _Alloc::difference_type difference_type; | |
242 | ||
243 | typedef typename traits_base::key_type key_type; | |
244 | typedef typename traits_base::key_pointer key_pointer; | |
245 | typedef typename traits_base::key_const_pointer key_const_pointer; | |
246 | typedef typename traits_base::key_reference key_reference; | |
247 | typedef typename traits_base::key_const_reference key_const_reference; | |
248 | typedef typename traits_base::mapped_type mapped_type; | |
249 | typedef typename traits_base::mapped_pointer mapped_pointer; | |
250 | typedef typename traits_base::mapped_const_pointer mapped_const_pointer; | |
251 | typedef typename traits_base::mapped_reference mapped_reference; | |
252 | typedef typename traits_base::mapped_const_reference mapped_const_reference; | |
253 | typedef typename traits_base::value_type value_type; | |
254 | typedef typename traits_base::pointer pointer; | |
255 | typedef typename traits_base::const_pointer const_pointer; | |
256 | typedef typename traits_base::reference reference; | |
257 | typedef typename traits_base::const_reference const_reference; | |
258 | ||
259 | typedef typename traits_type::access_traits access_traits; | |
260 | typedef typename traits_type::const_iterator point_const_iterator; | |
261 | typedef typename traits_type::iterator point_iterator; | |
262 | typedef point_const_iterator const_iterator; | |
263 | typedef point_iterator iterator; | |
264 | ||
265 | typedef typename traits_type::reverse_iterator reverse_iterator; | |
266 | typedef typename traits_type::const_reverse_iterator const_reverse_iterator; | |
267 | typedef typename traits_type::node_const_iterator node_const_iterator; | |
268 | typedef typename traits_type::node_iterator node_iterator; | |
269 | typedef typename traits_type::node_update node_update; | |
270 | ||
271 | PB_DS_PAT_TRIE_NAME(); | |
272 | ||
273 | PB_DS_PAT_TRIE_NAME(const access_traits&); | |
274 | ||
275 | PB_DS_PAT_TRIE_NAME(const PB_DS_CLASS_C_DEC&); | |
4569a895 AT |
276 | |
277 | void | |
1b24692f | 278 | swap(PB_DS_CLASS_C_DEC&); |
4569a895 | 279 | |
a345e45d | 280 | ~PB_DS_PAT_TRIE_NAME(); |
4569a895 | 281 | |
d715f554 | 282 | _GLIBCXX_NODISCARD inline bool |
4569a895 AT |
283 | empty() const; |
284 | ||
285 | inline size_type | |
286 | size() const; | |
287 | ||
288 | inline size_type | |
289 | max_size() const; | |
290 | ||
a345e45d BK |
291 | access_traits& |
292 | get_access_traits(); | |
4569a895 | 293 | |
a345e45d BK |
294 | const access_traits& |
295 | get_access_traits() const; | |
4569a895 | 296 | |
a345e45d | 297 | node_update& |
4569a895 AT |
298 | get_node_update(); |
299 | ||
a345e45d | 300 | const node_update& |
4569a895 AT |
301 | get_node_update() const; |
302 | ||
1b24692f BK |
303 | inline std::pair<point_iterator, bool> |
304 | insert(const_reference); | |
4569a895 AT |
305 | |
306 | inline mapped_reference | |
a345e45d | 307 | operator[](key_const_reference r_key) |
4569a895 AT |
308 | { |
309 | #ifdef PB_DS_DATA_TRUE_INDICATOR | |
1b24692f | 310 | return insert(std::make_pair(r_key, mapped_type())).first->second; |
a345e45d | 311 | #else |
4569a895 | 312 | insert(r_key); |
a345e45d BK |
313 | return traits_base::s_null_type; |
314 | #endif | |
4569a895 AT |
315 | } |
316 | ||
317 | inline point_iterator | |
a345e45d | 318 | find(key_const_reference); |
4569a895 | 319 | |
a345e45d BK |
320 | inline point_const_iterator |
321 | find(key_const_reference) const; | |
4569a895 AT |
322 | |
323 | inline point_iterator | |
a345e45d | 324 | lower_bound(key_const_reference); |
4569a895 | 325 | |
a345e45d BK |
326 | inline point_const_iterator |
327 | lower_bound(key_const_reference) const; | |
4569a895 AT |
328 | |
329 | inline point_iterator | |
a345e45d | 330 | upper_bound(key_const_reference); |
4569a895 | 331 | |
a345e45d BK |
332 | inline point_const_iterator |
333 | upper_bound(key_const_reference) const; | |
4569a895 AT |
334 | |
335 | void | |
336 | clear(); | |
337 | ||
338 | inline bool | |
a345e45d | 339 | erase(key_const_reference); |
4569a895 AT |
340 | |
341 | inline const_iterator | |
1b24692f | 342 | erase(const_iterator); |
4569a895 AT |
343 | |
344 | #ifdef PB_DS_DATA_TRUE_INDICATOR | |
345 | inline iterator | |
1b24692f | 346 | erase(iterator); |
a345e45d | 347 | #endif |
4569a895 AT |
348 | |
349 | inline const_reverse_iterator | |
1b24692f | 350 | erase(const_reverse_iterator); |
4569a895 AT |
351 | |
352 | #ifdef PB_DS_DATA_TRUE_INDICATOR | |
353 | inline reverse_iterator | |
1b24692f | 354 | erase(reverse_iterator); |
a345e45d | 355 | #endif |
4569a895 AT |
356 | |
357 | template<typename Pred> | |
358 | inline size_type | |
1b24692f | 359 | erase_if(Pred); |
4569a895 AT |
360 | |
361 | void | |
1b24692f | 362 | join(PB_DS_CLASS_C_DEC&); |
4569a895 AT |
363 | |
364 | void | |
a345e45d | 365 | split(key_const_reference, PB_DS_CLASS_C_DEC&); |
4569a895 AT |
366 | |
367 | inline iterator | |
368 | begin(); | |
369 | ||
370 | inline const_iterator | |
371 | begin() const; | |
372 | ||
373 | inline iterator | |
374 | end(); | |
375 | ||
376 | inline const_iterator | |
377 | end() const; | |
378 | ||
379 | inline reverse_iterator | |
380 | rbegin(); | |
381 | ||
382 | inline const_reverse_iterator | |
383 | rbegin() const; | |
384 | ||
385 | inline reverse_iterator | |
386 | rend(); | |
387 | ||
388 | inline const_reverse_iterator | |
389 | rend() const; | |
390 | ||
30a96b3b BK |
391 | /// Returns a const node_iterator corresponding to the node at the |
392 | /// root of the tree. | |
a345e45d | 393 | inline node_const_iterator |
4569a895 AT |
394 | node_begin() const; |
395 | ||
30a96b3b BK |
396 | /// Returns a node_iterator corresponding to the node at the |
397 | /// root of the tree. | |
4569a895 AT |
398 | inline node_iterator |
399 | node_begin(); | |
400 | ||
30a96b3b BK |
401 | /// Returns a const node_iterator corresponding to a node just |
402 | /// after a leaf of the tree. | |
a345e45d | 403 | inline node_const_iterator |
4569a895 AT |
404 | node_end() const; |
405 | ||
30a96b3b BK |
406 | /// Returns a node_iterator corresponding to a node just |
407 | /// after a leaf of the tree. | |
4569a895 AT |
408 | inline node_iterator |
409 | node_end(); | |
410 | ||
411 | #ifdef PB_DS_PAT_TRIE_TRACE_ | |
4569a895 AT |
412 | void |
413 | trace() const; | |
a345e45d | 414 | #endif |
4569a895 AT |
415 | |
416 | protected: | |
4569a895 AT |
417 | template<typename It> |
418 | void | |
1b24692f | 419 | copy_from_range(It, It); |
4569a895 AT |
420 | |
421 | void | |
1b24692f | 422 | value_swap(PB_DS_CLASS_C_DEC&); |
4569a895 AT |
423 | |
424 | node_pointer | |
a345e45d | 425 | recursive_copy_node(node_const_pointer); |
4569a895 AT |
426 | |
427 | private: | |
4569a895 AT |
428 | void |
429 | initialize(); | |
430 | ||
431 | inline void | |
1b24692f | 432 | apply_update(node_pointer, null_node_update_pointer); |
4569a895 AT |
433 | |
434 | template<typename Node_Update_> | |
435 | inline void | |
1b24692f | 436 | apply_update(node_pointer, Node_Update_*); |
4569a895 AT |
437 | |
438 | bool | |
a345e45d | 439 | join_prep(PB_DS_CLASS_C_DEC&, branch_bag&); |
4569a895 AT |
440 | |
441 | void | |
a345e45d | 442 | rec_join_prep(node_const_pointer, node_const_pointer, branch_bag&); |
4569a895 AT |
443 | |
444 | void | |
a345e45d | 445 | rec_join_prep(leaf_const_pointer, leaf_const_pointer, branch_bag&); |
4569a895 AT |
446 | |
447 | void | |
a345e45d | 448 | rec_join_prep(leaf_const_pointer, inode_const_pointer, branch_bag&); |
4569a895 AT |
449 | |
450 | void | |
a345e45d | 451 | rec_join_prep(inode_const_pointer, leaf_const_pointer, branch_bag&); |
4569a895 AT |
452 | |
453 | void | |
a345e45d | 454 | rec_join_prep(inode_const_pointer, inode_const_pointer, branch_bag&); |
4569a895 AT |
455 | |
456 | node_pointer | |
a345e45d | 457 | rec_join(node_pointer, node_pointer, size_type, branch_bag&); |
4569a895 AT |
458 | |
459 | node_pointer | |
a345e45d | 460 | rec_join(leaf_pointer, leaf_pointer, branch_bag&); |
4569a895 AT |
461 | |
462 | node_pointer | |
a345e45d | 463 | rec_join(leaf_pointer, inode_pointer, size_type, branch_bag&); |
4569a895 AT |
464 | |
465 | node_pointer | |
a345e45d | 466 | rec_join(inode_pointer, leaf_pointer, size_type, branch_bag&); |
4569a895 AT |
467 | |
468 | node_pointer | |
a345e45d | 469 | rec_join(inode_pointer, inode_pointer, branch_bag&); |
4569a895 AT |
470 | |
471 | size_type | |
a345e45d BK |
472 | keys_diff_ind(typename access_traits::const_iterator, |
473 | typename access_traits::const_iterator, | |
474 | typename access_traits::const_iterator, | |
475 | typename access_traits::const_iterator); | |
4569a895 | 476 | |
a345e45d BK |
477 | inode_pointer |
478 | insert_branch(node_pointer, node_pointer, branch_bag&); | |
4569a895 AT |
479 | |
480 | void | |
1b24692f | 481 | update_min_max_for_inserted_leaf(leaf_pointer); |
4569a895 AT |
482 | |
483 | void | |
1b24692f | 484 | erase_leaf(leaf_pointer); |
4569a895 AT |
485 | |
486 | inline void | |
1b24692f | 487 | actual_erase_leaf(leaf_pointer); |
4569a895 AT |
488 | |
489 | void | |
1b24692f | 490 | clear_imp(node_pointer); |
4569a895 AT |
491 | |
492 | void | |
a345e45d | 493 | erase_fixup(inode_pointer); |
4569a895 AT |
494 | |
495 | void | |
1b24692f | 496 | update_min_max_for_erased_leaf(leaf_pointer); |
4569a895 | 497 | |
a345e45d BK |
498 | static inline a_const_iterator |
499 | pref_begin(node_const_pointer); | |
4569a895 | 500 | |
a345e45d BK |
501 | static inline a_const_iterator |
502 | pref_end(node_const_pointer); | |
4569a895 AT |
503 | |
504 | inline node_pointer | |
a345e45d | 505 | find_imp(key_const_reference); |
4569a895 AT |
506 | |
507 | inline node_pointer | |
a345e45d | 508 | lower_bound_imp(key_const_reference); |
4569a895 AT |
509 | |
510 | inline node_pointer | |
a345e45d | 511 | upper_bound_imp(key_const_reference); |
4569a895 | 512 | |
a345e45d BK |
513 | inline static leaf_const_pointer |
514 | leftmost_descendant(node_const_pointer); | |
4569a895 AT |
515 | |
516 | inline static leaf_pointer | |
1b24692f | 517 | leftmost_descendant(node_pointer); |
4569a895 | 518 | |
a345e45d BK |
519 | inline static leaf_const_pointer |
520 | rightmost_descendant(node_const_pointer); | |
4569a895 AT |
521 | |
522 | inline static leaf_pointer | |
1b24692f | 523 | rightmost_descendant(node_pointer); |
4569a895 | 524 | |
47bea7b8 | 525 | #ifdef _GLIBCXX_DEBUG |
4569a895 | 526 | void |
a345e45d | 527 | assert_valid(const char*, int) const; |
4569a895 AT |
528 | |
529 | void | |
a345e45d | 530 | assert_iterators(const char*, int) const; |
4569a895 AT |
531 | |
532 | void | |
a345e45d | 533 | assert_reverse_iterators(const char*, int) const; |
4569a895 AT |
534 | |
535 | static size_type | |
a345e45d BK |
536 | recursive_count_leafs(node_const_pointer, const char*, int); |
537 | #endif | |
4569a895 AT |
538 | |
539 | #ifdef PB_DS_PAT_TRIE_TRACE_ | |
4569a895 | 540 | static void |
a345e45d | 541 | trace_node(node_const_pointer, size_type); |
4569a895 AT |
542 | |
543 | template<typename Metadata_> | |
544 | static void | |
a345e45d | 545 | trace_node_metadata(node_const_pointer, type_to_type<Metadata_>); |
4569a895 AT |
546 | |
547 | static void | |
a345e45d BK |
548 | trace_node_metadata(node_const_pointer, type_to_type<null_type>); |
549 | #endif | |
4569a895 AT |
550 | |
551 | leaf_pointer | |
a345e45d | 552 | split_prep(key_const_reference, PB_DS_CLASS_C_DEC&, branch_bag&); |
4569a895 AT |
553 | |
554 | node_pointer | |
a345e45d BK |
555 | rec_split(node_pointer, a_const_iterator, a_const_iterator, |
556 | PB_DS_CLASS_C_DEC&, branch_bag&); | |
4569a895 AT |
557 | |
558 | void | |
a345e45d BK |
559 | split_insert_branch(size_type, a_const_iterator, inode_iterator, |
560 | size_type, branch_bag&); | |
4569a895 | 561 | |
a345e45d BK |
562 | static head_allocator s_head_allocator; |
563 | static inode_allocator s_inode_allocator; | |
564 | static leaf_allocator s_leaf_allocator; | |
4569a895 | 565 | |
a345e45d BK |
566 | head_pointer m_p_head; |
567 | size_type m_size; | |
4569a895 AT |
568 | }; |
569 | ||
a345e45d | 570 | #define PB_DS_ASSERT_NODE_VALID(X) \ |
f5886803 FD |
571 | _GLIBCXX_DEBUG_ONLY(X->assert_valid(this, __FILE__, __LINE__);) |
572 | ||
a345e45d | 573 | #define PB_DS_RECURSIVE_COUNT_LEAFS(X) \ |
f5886803 FD |
574 | recursive_count_leafs(X, __FILE__, __LINE__) |
575 | ||
4569a895 AT |
576 | #include <ext/pb_ds/detail/pat_trie_/constructors_destructor_fn_imps.hpp> |
577 | #include <ext/pb_ds/detail/pat_trie_/iterators_fn_imps.hpp> | |
578 | #include <ext/pb_ds/detail/pat_trie_/insert_join_fn_imps.hpp> | |
579 | #include <ext/pb_ds/detail/pat_trie_/erase_fn_imps.hpp> | |
580 | #include <ext/pb_ds/detail/pat_trie_/find_fn_imps.hpp> | |
581 | #include <ext/pb_ds/detail/pat_trie_/info_fn_imps.hpp> | |
582 | #include <ext/pb_ds/detail/pat_trie_/policy_access_fn_imps.hpp> | |
583 | #include <ext/pb_ds/detail/pat_trie_/split_fn_imps.hpp> | |
584 | #include <ext/pb_ds/detail/pat_trie_/debug_fn_imps.hpp> | |
585 | #include <ext/pb_ds/detail/pat_trie_/trace_fn_imps.hpp> | |
586 | #include <ext/pb_ds/detail/pat_trie_/update_fn_imps.hpp> | |
587 | ||
f5886803 FD |
588 | #undef PB_DS_RECURSIVE_COUNT_LEAFS |
589 | #undef PB_DS_ASSERT_NODE_VALID | |
4569a895 | 590 | #undef PB_DS_CLASS_C_DEC |
4569a895 | 591 | #undef PB_DS_CLASS_T_DEC |
a345e45d BK |
592 | #undef PB_DS_PAT_TRIE_NAME |
593 | #undef PB_DS_PAT_TRIE_TRAITS_BASE | |
551fe1a2 | 594 | #undef PB_DS_DEBUG_MAP_BASE_C_DEC |
4569a895 | 595 | } // namespace detail |
5e11f978 | 596 | } // namespace __gnu_pbds |