3 // Copyright (C) 2005, 2006, 2007, 2009, 2010, 2011
4 // Free Software Foundation, Inc.
6 // This file is part of the GNU ISO C++ Library. This library is free
7 // software; you can redistribute it and/or modify it under the terms
8 // of the GNU General Public License as published by the Free Software
9 // Foundation; either version 3, or (at your option) any later
12 // This library is distributed in the hope that it will be useful, but
13 // WITHOUT ANY WARRANTY; without even the implied warranty of
14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 // General Public License for more details.
17 // Under Section 7 of GPL version 3, you are granted additional
18 // permissions described in the GCC Runtime Library Exception, version
19 // 3.1, as published by the Free Software Foundation.
21 // You should have received a copy of the GNU General Public License and
22 // a copy of the GCC Runtime Library Exception along with this program;
23 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
24 // <http://www.gnu.org/licenses/>.
26 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
28 // Permission to use, copy, modify, sell, and distribute this software
29 // is hereby granted without fee, provided that the above copyright
30 // notice appears in all copies, and that both that copyright notice
31 // and this permission notice appear in supporting documentation. None
32 // of the above authors, nor IBM Haifa Research Laboratories, make any
33 // representation about the suitability of this software for any
34 // purpose. It is provided "as is" without express or implied
38 * @file trie_policy.hpp
39 * Contains trie-related policies.
42 #ifndef PB_DS_TRIE_POLICY_HPP
43 #define PB_DS_TRIE_POLICY_HPP
45 #include <bits/c++config.h>
47 #include <ext/pb_ds/detail/type_utils.hpp>
48 #include <ext/pb_ds/detail/trie_policy/trie_policy_base.hpp>
52 #define PB_DS_CLASS_T_DEC \
53 template<typename String, typename String::value_type Min_E_Val, \
54 typename String::value_type Max_E_Val, bool Reverse, \
57 #define PB_DS_CLASS_C_DEC \
58 trie_string_access_traits<String, Min_E_Val,Max_E_Val,Reverse,_Alloc>
61 * Element access traits for string types.
63 * @tparam String String type.
64 * @tparam Min_E_Val Minimal element value.
65 * @tparam Max_E_Val Maximum element value.
66 * @tparam Reverse Reverse iteration should be used.
68 * @tparam _Alloc Allocator type.
70 template<typename String = std::string,
71 typename String::value_type Min_E_Val = detail::__numeric_traits<typename String::value_type>::__min,
72 typename String::value_type Max_E_Val = detail::__numeric_traits<typename String::value_type>::__max,
74 typename _Alloc = std::allocator<char> >
75 struct trie_string_access_traits
78 typedef typename _Alloc::size_type size_type;
79 typedef String key_type;
80 typedef typename _Alloc::template rebind<key_type> __rebind_k;
81 typedef typename __rebind_k::other::const_reference key_const_reference;
88 /// Element const iterator type.
89 typedef typename detail::__conditional_type<Reverse, \
90 typename String::const_reverse_iterator, \
91 typename String::const_iterator>::__type const_iterator;
94 typedef typename std::iterator_traits<const_iterator>::value_type e_type;
98 min_e_val = Min_E_Val,
99 max_e_val = Max_E_Val,
100 max_size = max_e_val - min_e_val + 1
102 PB_DS_STATIC_ASSERT(min_max_size, max_size >= 2);
104 /// Returns a const_iterator to the first element of
105 /// key_const_reference agumnet.
106 inline static const_iterator
107 begin(key_const_reference);
109 /// Returns a const_iterator to the after-last element of
110 /// key_const_reference argument.
111 inline static const_iterator
112 end(key_const_reference);
114 /// Maps an element to a position.
115 inline static size_type
119 inline static const_iterator
120 begin_imp(key_const_reference, detail::false_type);
122 inline static const_iterator
123 begin_imp(key_const_reference, detail::true_type);
125 inline static const_iterator
126 end_imp(key_const_reference, detail::false_type);
128 inline static const_iterator
129 end_imp(key_const_reference, detail::true_type);
131 static detail::integral_constant<int, Reverse> s_rev_ind;
134 #include <ext/pb_ds/detail/trie_policy/trie_string_access_traits_imp.hpp>
136 #undef PB_DS_CLASS_T_DEC
137 #undef PB_DS_CLASS_C_DEC
139 #define PB_DS_CLASS_T_DEC \
140 template<typename Node_CItr,typename Node_Itr, \
141 typename _ATraits, typename _Alloc>
143 #define PB_DS_CLASS_C_DEC \
144 trie_prefix_search_node_update<Node_CItr, Node_Itr, \
147 #define PB_DS_TRIE_POLICY_BASE \
148 detail::trie_policy_base<Node_CItr,Node_Itr,_ATraits, _Alloc>
150 /// A node updator that allows tries to be searched for the range of
151 /// values that match a certain prefix.
152 template<typename Node_CItr,
156 class trie_prefix_search_node_update : private PB_DS_TRIE_POLICY_BASE
159 typedef PB_DS_TRIE_POLICY_BASE base_type;
162 typedef typename base_type::key_type key_type;
163 typedef typename base_type::key_const_reference key_const_reference;
165 /// Element access traits.
166 typedef _ATraits access_traits;
168 /// Const element iterator.
169 typedef typename access_traits::const_iterator a_const_iterator;
172 typedef _Alloc allocator_type;
175 typedef typename allocator_type::size_type size_type;
176 typedef null_type metadata_type;
177 typedef Node_Itr node_iterator;
178 typedef Node_CItr node_const_iterator;
179 typedef typename node_iterator::value_type iterator;
180 typedef typename node_const_iterator::value_type const_iterator;
182 /// Finds the const iterator range corresponding to all values
183 /// whose prefixes match r_key.
184 std::pair<const_iterator, const_iterator>
185 prefix_range(key_const_reference) const;
187 /// Finds the iterator range corresponding to all values whose
188 /// prefixes match r_key.
189 std::pair<iterator, iterator>
190 prefix_range(key_const_reference);
192 /// Finds the const iterator range corresponding to all values
193 /// whose prefixes match [b, e).
194 std::pair<const_iterator, const_iterator>
195 prefix_range(a_const_iterator, a_const_iterator) const;
197 /// Finds the iterator range corresponding to all values whose
198 /// prefixes match [b, e).
199 std::pair<iterator, iterator>
200 prefix_range(a_const_iterator, a_const_iterator);
203 /// Called to update a node's metadata.
205 operator()(node_iterator node_it, node_const_iterator end_nd_it) const;
209 next_child(node_iterator, a_const_iterator, a_const_iterator,
210 node_iterator, const access_traits&);
212 /// Returns the const iterator associated with the just-after last element.
213 virtual const_iterator
216 /// Returns the iterator associated with the just-after last element.
220 /// Returns the node_const_iterator associated with the trie's root node.
221 virtual node_const_iterator
222 node_begin() const = 0;
224 /// Returns the node_iterator associated with the trie's root node.
225 virtual node_iterator
228 /// Returns the node_const_iterator associated with a just-after leaf node.
229 virtual node_const_iterator
230 node_end() const = 0;
232 /// Returns the node_iterator associated with a just-after leaf node.
233 virtual node_iterator
236 /// Access to the cmp_fn object.
237 virtual const access_traits&
238 get_access_traits() const = 0;
241 #include <ext/pb_ds/detail/trie_policy/prefix_search_node_update_imp.hpp>
243 #undef PB_DS_CLASS_C_DEC
245 #define PB_DS_CLASS_C_DEC \
246 trie_order_statistics_node_update<Node_CItr, Node_Itr, \
249 /// Functor updating ranks of entrees.
250 template<typename Node_CItr,
254 class trie_order_statistics_node_update : private PB_DS_TRIE_POLICY_BASE
257 typedef PB_DS_TRIE_POLICY_BASE base_type;
260 typedef _ATraits access_traits;
261 typedef typename access_traits::const_iterator a_const_iterator;
262 typedef _Alloc allocator_type;
263 typedef typename allocator_type::size_type size_type;
264 typedef typename base_type::key_type key_type;
265 typedef typename base_type::key_const_reference key_const_reference;
267 typedef size_type metadata_type;
268 typedef Node_CItr node_const_iterator;
269 typedef Node_Itr node_iterator;
270 typedef typename node_const_iterator::value_type const_iterator;
271 typedef typename node_iterator::value_type iterator;
273 /// Finds an entry by __order. Returns a const_iterator to the
274 /// entry with the __order order, or a const_iterator to the
275 /// container object's end if order is at least the size of the
276 /// container object.
277 inline const_iterator
278 find_by_order(size_type) const;
280 /// Finds an entry by __order. Returns an iterator to the entry
281 /// with the __order order, or an iterator to the container
282 /// object's end if order is at least the size of the container
285 find_by_order(size_type);
287 /// Returns the order of a key within a sequence. For exapmle, if
288 /// r_key is the smallest key, this method will return 0; if r_key
289 /// is a key between the smallest and next key, this method will
290 /// return 1; if r_key is a key larger than the largest key, this
291 /// method will return the size of r_c.
293 order_of_key(key_const_reference) const;
295 /// Returns the order of a prefix within a sequence. For exapmle,
296 /// if [b, e] is the smallest prefix, this method will return 0; if
297 /// r_key is a key between the smallest and next key, this method
298 /// will return 1; if r_key is a key larger than the largest key,
299 /// this method will return the size of r_c.
301 order_of_prefix(a_const_iterator, a_const_iterator) const;
304 /// Updates the rank of a node through a node_iterator node_it;
305 /// end_nd_it is the end node iterator.
307 operator()(node_iterator, node_const_iterator) const;
310 typedef typename base_type::const_reference const_reference;
311 typedef typename base_type::const_pointer const_pointer;
313 typedef typename _Alloc::template rebind<metadata_type> __rebind_m;
314 typedef typename __rebind_m::other __rebind_ma;
315 typedef typename __rebind_ma::const_reference metadata_const_reference;
316 typedef typename __rebind_ma::reference metadata_reference;
318 /// Returns true if the container is empty.
322 /// Returns the iterator associated with the trie's first element.
326 /// Returns the iterator associated with the trie's
327 /// just-after-last element.
331 /// Returns the node_const_iterator associated with the trie's root node.
332 virtual node_const_iterator
333 node_begin() const = 0;
335 /// Returns the node_iterator associated with the trie's root node.
336 virtual node_iterator
339 /// Returns the node_const_iterator associated with a just-after
341 virtual node_const_iterator
342 node_end() const = 0;
344 /// Returns the node_iterator associated with a just-after leaf node.
345 virtual node_iterator
348 /// Access to the cmp_fn object.
349 virtual access_traits&
350 get_access_traits() = 0;
353 #include <ext/pb_ds/detail/trie_policy/order_statistics_imp.hpp>
355 #undef PB_DS_CLASS_T_DEC
356 #undef PB_DS_CLASS_C_DEC
357 #undef PB_DS_TRIE_POLICY_BASE
359 } // namespace __gnu_pbds