3 // Copyright (C) 2005, 2006, 2007, 2009 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