3 // Copyright (C) 2005, 2006, 2007, 2009, 2010 Free Software Foundation, Inc.
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 3, or (at your option) any later
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.
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.
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/>.
25 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
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
38 * Contains an implementation class for a patricia tree.
42 * This implementation loosely borrows ideas from:
43 * 1) Fast Mergeable Integer Maps, Okasaki, Gill 1998
44 * 2) Ptset: Sets of integers implemented as Patricia trees,
45 * Jean-Christophe Filliatr, 2000
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>
64 #include <ext/pb_ds/detail/debug_map_base.hpp>
66 #include <debug/debug.h>
72 #define PB_DS_CLASS_T_DEC \
73 template<typename Key, typename Mapped, typename Node_And_It_Traits, \
76 #ifdef PB_DS_DATA_TRUE_INDICATOR
77 #define PB_DS_CLASS_NAME pat_trie_data_
80 #ifdef PB_DS_DATA_FALSE_INDICATOR
81 #define PB_DS_CLASS_NAME pat_trie_no_data_
84 #define PB_DS_CLASS_C_DEC \
85 PB_DS_CLASS_NAME<Key, Mapped, Node_And_It_Traits, Allocator>
87 #define PB_DS_TYPES_TRAITS_C_DEC \
88 types_traits<Key, Mapped, Allocator, false>
91 #define PB_DS_DEBUG_MAP_BASE_C_DEC \
92 debug_map_base<Key, eq_by_less<Key, \
93 std::less<Key> >, typename Allocator::template rebind<Key>::other::const_reference>
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)
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)
109 * class description = PATRICIA trie implementation.">
111 template<typename Key,
113 typename Node_And_It_Traits,
115 class PB_DS_CLASS_NAME :
116 #ifdef _GLIBCXX_DEBUG
117 public PB_DS_DEBUG_MAP_BASE_C_DEC,
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
124 typedef PB_DS_TYPES_TRAITS_C_DEC traits_base;
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;
130 typedef typename Node_And_It_Traits::node node;
131 typedef typename Allocator::template rebind<node>::other::const_pointer const_node_pointer;
133 typedef typename Allocator::template rebind<node>::other::pointer node_pointer;
135 typedef typename Node_And_It_Traits::head head;
136 typedef typename Allocator::template rebind<head>::other head_allocator;
137 typedef typename head_allocator::pointer head_pointer;
139 typedef typename Node_And_It_Traits::leaf leaf;
140 typedef typename Allocator::template rebind<leaf>::other leaf_allocator;
141 typedef typename leaf_allocator::const_pointer const_leaf_pointer;
142 typedef typename leaf_allocator::pointer leaf_pointer;
144 typedef typename Node_And_It_Traits::internal_node internal_node;
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;
149 #include <ext/pb_ds/detail/pat_trie_/cond_dtor_entry_dealtor.hpp>
151 #ifdef _GLIBCXX_DEBUG
152 typedef PB_DS_DEBUG_MAP_BASE_C_DEC debug_base;
155 #include <ext/pb_ds/detail/pat_trie_/split_join_branch_bag.hpp>
157 typedef typename Node_And_It_Traits::null_node_update_pointer null_node_update_pointer;
160 typedef pat_trie_tag container_category;
161 typedef Allocator allocator_type;
162 typedef typename Allocator::size_type size_type;
163 typedef typename Allocator::difference_type difference_type;
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;
181 typedef typename Node_And_It_Traits::const_iterator const_point_iterator;
182 typedef typename Node_And_It_Traits::iterator point_iterator;
183 typedef const_point_iterator const_iterator;
184 typedef point_iterator iterator;
186 typedef typename Node_And_It_Traits::const_reverse_iterator const_reverse_iterator;
187 typedef typename Node_And_It_Traits::reverse_iterator reverse_iterator;
188 typedef typename Node_And_It_Traits::const_node_iterator const_node_iterator;
189 typedef typename Node_And_It_Traits::node_iterator node_iterator;
190 typedef typename Node_And_It_Traits::e_access_traits e_access_traits;
191 typedef typename Node_And_It_Traits::node_update node_update;
195 PB_DS_CLASS_NAME(const e_access_traits&);
197 PB_DS_CLASS_NAME(const PB_DS_CLASS_C_DEC&);
200 swap(PB_DS_CLASS_C_DEC&);
214 get_e_access_traits();
216 const e_access_traits&
217 get_e_access_traits() const;
223 get_node_update() const;
225 inline std::pair<point_iterator, bool>
226 insert(const_reference);
228 inline mapped_reference
229 operator[](const_key_reference r_key)
231 #ifdef PB_DS_DATA_TRUE_INDICATOR
232 return insert(std::make_pair(r_key, mapped_type())).first->second;
235 return traits_base::s_null_mapped;
239 inline point_iterator
240 find(const_key_reference);
242 inline const_point_iterator
243 find(const_key_reference) const;
245 inline point_iterator
246 lower_bound(const_key_reference);
248 inline const_point_iterator
249 lower_bound(const_key_reference) const;
251 inline point_iterator
252 upper_bound(const_key_reference);
254 inline const_point_iterator
255 upper_bound(const_key_reference) const;
261 erase(const_key_reference);
263 inline const_iterator
264 erase(const_iterator);
266 #ifdef PB_DS_DATA_TRUE_INDICATOR
271 inline const_reverse_iterator
272 erase(const_reverse_iterator);
274 #ifdef PB_DS_DATA_TRUE_INDICATOR
275 inline reverse_iterator
276 erase(reverse_iterator);
279 template<typename Pred>
284 join(PB_DS_CLASS_C_DEC&);
287 split(const_key_reference, PB_DS_CLASS_C_DEC&);
292 inline const_iterator
298 inline const_iterator
301 inline reverse_iterator
304 inline const_reverse_iterator
307 inline reverse_iterator
310 inline const_reverse_iterator
313 inline const_node_iterator
319 inline const_node_iterator
325 #ifdef PB_DS_PAT_TRIE_TRACE_
332 template<typename It>
334 copy_from_range(It, It);
337 value_swap(PB_DS_CLASS_C_DEC&);
340 recursive_copy_node(const_node_pointer);
348 apply_update(node_pointer, null_node_update_pointer);
350 template<typename Node_Update_>
352 apply_update(node_pointer, Node_Update_*);
355 join_prep(PB_DS_CLASS_C_DEC&, split_join_branch_bag&);
358 rec_join_prep(const_node_pointer, const_node_pointer,
359 split_join_branch_bag&);
362 rec_join_prep(const_leaf_pointer, const_leaf_pointer,
363 split_join_branch_bag&);
366 rec_join_prep(const_leaf_pointer, const_internal_node_pointer,
367 split_join_branch_bag&);
370 rec_join_prep(const_internal_node_pointer, const_leaf_pointer,
371 split_join_branch_bag&);
374 rec_join_prep(const_internal_node_pointer, const_internal_node_pointer,
375 split_join_branch_bag&);
378 rec_join(node_pointer, node_pointer, size_type, split_join_branch_bag&);
381 rec_join(leaf_pointer, leaf_pointer, split_join_branch_bag&);
384 rec_join(leaf_pointer, internal_node_pointer, size_type,
385 split_join_branch_bag&);
388 rec_join(internal_node_pointer, leaf_pointer, size_type,
389 split_join_branch_bag&);
392 rec_join(internal_node_pointer, internal_node_pointer,
393 split_join_branch_bag&);
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);
398 internal_node_pointer
399 insert_branch(node_pointer, node_pointer, split_join_branch_bag&);
402 update_min_max_for_inserted_leaf(leaf_pointer);
405 erase_leaf(leaf_pointer);
408 actual_erase_leaf(leaf_pointer);
411 clear_imp(node_pointer);
414 erase_fixup(internal_node_pointer);
417 update_min_max_for_erased_leaf(leaf_pointer);
419 static inline const_e_iterator
420 pref_begin(const_node_pointer);
422 static inline const_e_iterator
423 pref_end(const_node_pointer);
426 find_imp(const_key_reference);
429 lower_bound_imp(const_key_reference);
432 upper_bound_imp(const_key_reference);
434 inline static const_leaf_pointer
435 leftmost_descendant(const_node_pointer);
437 inline static leaf_pointer
438 leftmost_descendant(node_pointer);
440 inline static const_leaf_pointer
441 rightmost_descendant(const_node_pointer);
443 inline static leaf_pointer
444 rightmost_descendant(node_pointer);
446 #ifdef _GLIBCXX_DEBUG
448 assert_valid() const;
451 assert_iterators() const;
454 assert_reverse_iterators() const;
457 recursive_count_leafs(const_node_pointer);
460 #ifdef PB_DS_PAT_TRIE_TRACE_
462 trace_node(const_node_pointer, size_type);
464 template<typename Metadata_>
466 trace_node_metadata(const_node_pointer, type_to_type<Metadata_>);
469 trace_node_metadata(const_node_pointer, type_to_type<null_node_metadata>);
473 split_prep(const_key_reference, PB_DS_CLASS_C_DEC&,
474 split_join_branch_bag&);
477 rec_split(node_pointer, const_e_iterator, const_e_iterator,
478 PB_DS_CLASS_C_DEC&, split_join_branch_bag&);
481 split_insert_branch(size_type, const_e_iterator,
482 typename internal_node::iterator,
483 size_type, split_join_branch_bag&);
485 static head_allocator s_head_allocator;
486 static internal_node_allocator s_internal_node_allocator;
487 static leaf_allocator s_leaf_allocator;
489 head_pointer m_p_head;
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>
505 #undef PB_DS_CLASS_C_DEC
506 #undef PB_DS_CLASS_T_DEC
507 #undef PB_DS_CLASS_NAME
508 #undef PB_DS_TYPES_TRAITS_C_DEC
509 #undef PB_DS_DEBUG_MAP_BASE_C_DEC
514 } // namespace detail
515 } // namespace __gnu_pbds