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
37 * @file trie_policy.hpp
38 * Contains trie-related policies.
41 #ifndef PB_DS_TRIE_POLICY_HPP
42 #define PB_DS_TRIE_POLICY_HPP
44 #include <bits/c++config.h>
46 #include <ext/pb_ds/detail/type_utils.hpp>
47 #include <ext/pb_ds/detail/trie_policy/trie_policy_base.hpp>
51 // A null node updator, indicating that no node updates are required.
52 template<typename Const_Node_Iterator
,
53 typename Node_Iterator
,
54 typename E_Access_Traits
,
56 struct null_trie_node_update
59 #define PB_DS_CLASS_T_DEC \
60 template<typename String, typename String::value_type Min_E_Val, typename String::value_type Max_E_Val, bool Reverse, typename Allocator>
62 #define PB_DS_CLASS_C_DEC \
63 string_trie_e_access_traits<String, Min_E_Val,Max_E_Val,Reverse,Allocator>
65 // Element access traits for string types.
66 template<typename String
= std::string
,
67 typename
String::value_type Min_E_Val
= detail::__numeric_traits
<typename
String::value_type
>::__min
,
68 typename
String::value_type Max_E_Val
= detail::__numeric_traits
<typename
String::value_type
>::__max
,
70 typename Allocator
= std::allocator
<char> >
71 struct string_trie_e_access_traits
74 typedef typename
Allocator::size_type size_type
;
75 typedef String key_type
;
76 typedef typename
Allocator::template rebind
<key_type
>::other key_rebind
;
77 typedef typename
key_rebind::const_reference const_key_reference
;
84 // Element const iterator type.
85 typedef typename
detail::__conditional_type
<Reverse
, typename
String::const_reverse_iterator
, typename
String::const_iterator
>::__type const_iterator
;
88 typedef typename
std::iterator_traits
<const_iterator
>::value_type e_type
;
92 min_e_val
= Min_E_Val
,
93 max_e_val
= Max_E_Val
,
94 max_size
= max_e_val
- min_e_val
+ 1
96 PB_DS_STATIC_ASSERT(min_max_size
, max_size
>= 2);
98 // Returns a const_iterator to the first element of
99 // const_key_reference agumnet.
100 inline static const_iterator
101 begin(const_key_reference
);
103 // Returns a const_iterator to the after-last element of
104 // const_key_reference argument.
105 inline static const_iterator
106 end(const_key_reference
);
108 // Maps an element to a position.
109 inline static size_type
114 inline static const_iterator
115 begin_imp(const_key_reference
, detail::false_type
);
117 inline static const_iterator
118 begin_imp(const_key_reference
, detail::true_type
);
120 inline static const_iterator
121 end_imp(const_key_reference
, detail::false_type
);
123 inline static const_iterator
124 end_imp(const_key_reference
, detail::true_type
);
126 static detail::integral_constant
<int, Reverse
> s_rev_ind
;
129 #include <ext/pb_ds/detail/trie_policy/string_trie_e_access_traits_imp.hpp>
131 #undef PB_DS_CLASS_T_DEC
132 #undef PB_DS_CLASS_C_DEC
134 #define PB_DS_CLASS_T_DEC \
135 template<typename Const_Node_Iterator,typename Node_Iterator,class E_Access_Traits, typename Allocator>
137 #define PB_DS_CLASS_C_DEC \
138 trie_prefix_search_node_update<Const_Node_Iterator, Node_Iterator, E_Access_Traits,Allocator>
140 #define PB_DS_BASE_C_DEC \
141 detail::trie_policy_base<Const_Node_Iterator,Node_Iterator,E_Access_Traits, Allocator>
143 // A node updator that allows tries to be searched for the range of
144 // values that match a certain prefix.
145 template<typename Const_Node_Iterator
,
146 typename Node_Iterator
,
147 typename E_Access_Traits
,
149 class trie_prefix_search_node_update
: private PB_DS_BASE_C_DEC
152 typedef PB_DS_BASE_C_DEC base_type
;
155 typedef typename
base_type::key_type key_type
;
156 typedef typename
base_type::const_key_reference const_key_reference
;
158 // Element access traits.
159 typedef E_Access_Traits e_access_traits
;
161 // Const element iterator.
162 typedef typename
e_access_traits::const_iterator const_e_iterator
;
165 typedef Allocator allocator_type
;
168 typedef typename
allocator_type::size_type size_type
;
169 typedef detail::null_node_metadata metadata_type
;
170 typedef Const_Node_Iterator const_node_iterator
;
171 typedef Node_Iterator node_iterator
;
172 typedef typename
const_node_iterator::value_type const_iterator
;
173 typedef typename
node_iterator::value_type iterator
;
175 // Finds the const iterator range corresponding to all values
176 // whose prefixes match r_key.
177 std::pair
<const_iterator
, const_iterator
>
178 prefix_range(const_key_reference
) const;
180 // Finds the iterator range corresponding to all values whose
181 // prefixes match r_key.
182 std::pair
<iterator
, iterator
>
183 prefix_range(const_key_reference
);
185 // Finds the const iterator range corresponding to all values
186 // whose prefixes match [b, e).
187 std::pair
<const_iterator
, const_iterator
>
188 prefix_range(const_e_iterator
, const_e_iterator
) const;
190 // Finds the iterator range corresponding to all values whose
191 // prefixes match [b, e).
192 std::pair
<iterator
, iterator
>
193 prefix_range(const_e_iterator
, const_e_iterator
);
196 // Called to update a node's metadata.
198 operator()(node_iterator node_it
, const_node_iterator end_nd_it
) const;
201 // Returns the const iterator associated with the just-after last element.
202 virtual const_iterator
205 // Returns the iterator associated with the just-after last element.
209 // Returns the const_node_iterator associated with the trie's root node.
210 virtual const_node_iterator
211 node_begin() const = 0;
213 // Returns the node_iterator associated with the trie's root node.
214 virtual node_iterator
217 // Returns the const_node_iterator associated with a just-after leaf node.
218 virtual const_node_iterator
219 node_end() const = 0;
221 // Returns the node_iterator associated with a just-after leaf node.
222 virtual node_iterator
225 // Access to the cmp_fn object.
226 virtual const e_access_traits
&
227 get_e_access_traits() const = 0;
230 next_child(node_iterator
, const_e_iterator
, const_e_iterator
,
231 node_iterator
, const e_access_traits
&);
234 #include <ext/pb_ds/detail/trie_policy/prefix_search_node_update_imp.hpp>
236 #undef PB_DS_CLASS_C_DEC
238 #define PB_DS_CLASS_C_DEC \
239 trie_order_statistics_node_update<Const_Node_Iterator, Node_Iterator,E_Access_Traits, Allocator>
241 // Functor updating ranks of entrees.
242 template<typename Const_Node_Iterator
,
243 typename Node_Iterator
,
244 typename E_Access_Traits
,
246 class trie_order_statistics_node_update
: private PB_DS_BASE_C_DEC
249 typedef PB_DS_BASE_C_DEC base_type
;
252 typedef E_Access_Traits e_access_traits
;
253 typedef typename
e_access_traits::const_iterator const_e_iterator
;
254 typedef Allocator allocator_type
;
255 typedef typename
allocator_type::size_type size_type
;
256 typedef typename
base_type::key_type key_type
;
257 typedef typename
base_type::const_key_reference const_key_reference
;
259 typedef size_type metadata_type
;
260 typedef Const_Node_Iterator const_node_iterator
;
261 typedef Node_Iterator node_iterator
;
262 typedef typename
const_node_iterator::value_type const_iterator
;
263 typedef typename
node_iterator::value_type iterator
;
265 // Finds an entry by __order. Returns a const_iterator to the
266 // entry with the __order order, or a const_iterator to the
267 // container object's end if order is at least the size of the
269 inline const_iterator
270 find_by_order(size_type
) const;
272 // Finds an entry by __order. Returns an iterator to the entry
273 // with the __order order, or an iterator to the container
274 // object's end if order is at least the size of the container
277 find_by_order(size_type
);
279 // Returns the order of a key within a sequence. For exapmle, if
280 // r_key is the smallest key, this method will return 0; if r_key
281 // is a key between the smallest and next key, this method will
282 // return 1; if r_key is a key larger than the largest key, this
283 // method will return the size of r_c.
285 order_of_key(const_key_reference
) const;
287 // Returns the order of a prefix within a sequence. For exapmle,
288 // if [b, e] is the smallest prefix, this method will return 0; if
289 // r_key is a key between the smallest and next key, this method
290 // will return 1; if r_key is a key larger than the largest key,
291 // this method will return the size of r_c.
293 order_of_prefix(const_e_iterator
, const_e_iterator
) const;
296 typedef typename
base_type::const_reference const_reference
;
297 typedef typename
base_type::const_pointer const_pointer
;
299 typedef typename
Allocator::template rebind
<metadata_type
>::other metadata_rebind
;
300 typedef typename
metadata_rebind::const_reference const_metadata_reference
;
301 typedef typename
metadata_rebind::reference metadata_reference
;
303 // Returns true if the container is empty.
307 // Returns the iterator associated with the trie's first element.
311 // Returns the iterator associated with the trie's
312 // just-after-last element.
316 // Returns the const_node_iterator associated with the trie's root node.
317 virtual const_node_iterator
318 node_begin() const = 0;
320 // Returns the node_iterator associated with the trie's root node.
321 virtual node_iterator
324 // Returns the const_node_iterator associated with a just-after
326 virtual const_node_iterator
327 node_end() const = 0;
329 // Returns the node_iterator associated with a just-after leaf node.
330 virtual node_iterator
333 // Access to the cmp_fn object.
334 virtual e_access_traits
&
335 get_e_access_traits() = 0;
338 // Updates the rank of a node through a node_iterator node_it;
339 // end_nd_it is the end node iterator.
341 operator()(node_iterator
, const_node_iterator
) const;
345 ~trie_order_statistics_node_update();
348 #include <ext/pb_ds/detail/trie_policy/order_statistics_imp.hpp>
350 #undef PB_DS_CLASS_T_DEC
351 #undef PB_DS_CLASS_C_DEC
352 #undef PB_DS_BASE_C_DEC
354 } // namespace __gnu_pbds