libstdc++
trie_policy.hpp
Go to the documentation of this file.
1// -*- C++ -*-
2
3// Copyright (C) 2005-2021 Free Software Foundation, Inc.
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
8// Foundation; either version 3, or (at your option) any later
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
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/>.
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/**
37 * @file trie_policy.hpp
38 * Contains trie-related policies.
39 */
40
41#ifndef PB_DS_TRIE_POLICY_HPP
42#define PB_DS_TRIE_POLICY_HPP
43
44#include <bits/c++config.h>
45#include <string>
48
49namespace __gnu_pbds
50{
51#define PB_DS_CLASS_T_DEC \
52 template<typename String, typename String::value_type Min_E_Val, \
53 typename String::value_type Max_E_Val, bool Reverse, \
54 typename _Alloc>
55
56#define PB_DS_CLASS_C_DEC \
57 trie_string_access_traits<String, Min_E_Val,Max_E_Val,Reverse,_Alloc>
58
59 /**
60 * Element access traits for string types.
61 *
62 * @tparam String String type.
63 * @tparam Min_E_Val Minimal element value.
64 * @tparam Max_E_Val Maximum element value.
65 * @tparam Reverse Reverse iteration should be used.
66 * Default: false.
67 * @tparam _Alloc Allocator type.
68 */
69 template<typename String = std::string,
70 typename String::value_type Min_E_Val = detail::__numeric_traits<typename String::value_type>::__min,
71 typename String::value_type Max_E_Val = detail::__numeric_traits<typename String::value_type>::__max,
72 bool Reverse = false,
73 typename _Alloc = std::allocator<char> >
75 {
76 public:
77 typedef typename _Alloc::size_type size_type;
78 typedef String key_type;
79 typedef typename detail::rebind_traits<_Alloc, key_type>::const_reference
80 key_const_reference;
81
82 enum
83 {
84 reverse = Reverse
85 };
86
87 /// Element const iterator type.
88 typedef typename detail::__conditional_type<Reverse, \
89 typename String::const_reverse_iterator, \
90 typename String::const_iterator>::__type const_iterator;
91
92 /// Element type.
94
95 enum
96 {
97 min_e_val = Min_E_Val,
98 max_e_val = Max_E_Val,
99 max_size = max_e_val - min_e_val + 1
100 };
101 PB_DS_STATIC_ASSERT(min_max_size, max_size >= 2);
102
103 /// Returns a const_iterator to the first element of
104 /// key_const_reference agumnet.
105 inline static const_iterator
106 begin(key_const_reference);
107
108 /// Returns a const_iterator to the after-last element of
109 /// key_const_reference argument.
110 inline static const_iterator
111 end(key_const_reference);
112
113 /// Maps an element to a position.
114 inline static size_type
116
117 private:
118 inline static const_iterator
119 begin_imp(key_const_reference, detail::false_type);
120
121 inline static const_iterator
122 begin_imp(key_const_reference, detail::true_type);
123
124 inline static const_iterator
125 end_imp(key_const_reference, detail::false_type);
126
127 inline static const_iterator
128 end_imp(key_const_reference, detail::true_type);
129
130 static detail::integral_constant<int, Reverse> s_rev_ind;
131 };
132
134
135#undef PB_DS_CLASS_T_DEC
136#undef PB_DS_CLASS_C_DEC
137
138#define PB_DS_CLASS_T_DEC \
139 template<typename Node_CItr,typename Node_Itr, \
140 typename _ATraits, typename _Alloc>
141
142#define PB_DS_CLASS_C_DEC \
143 trie_prefix_search_node_update<Node_CItr, Node_Itr, \
144 _ATraits,_Alloc>
145
146#define PB_DS_TRIE_POLICY_BASE \
147 detail::trie_policy_base<Node_CItr,Node_Itr,_ATraits, _Alloc>
148
149 /// A node updator that allows tries to be searched for the range of
150 /// values that match a certain prefix.
151 template<typename Node_CItr,
152 typename Node_Itr,
153 typename _ATraits,
154 typename _Alloc>
155 class trie_prefix_search_node_update : private PB_DS_TRIE_POLICY_BASE
156 {
157 private:
158 typedef PB_DS_TRIE_POLICY_BASE base_type;
159
160 public:
161 typedef typename base_type::key_type key_type;
162 typedef typename base_type::key_const_reference key_const_reference;
163
164 /// Element access traits.
165 typedef _ATraits access_traits;
166
167 /// Const element iterator.
168 typedef typename access_traits::const_iterator a_const_iterator;
169
170 /// _Alloc type.
171 typedef _Alloc allocator_type;
172
173 /// Size type.
174 typedef typename allocator_type::size_type size_type;
175 typedef null_type metadata_type;
176 typedef Node_Itr node_iterator;
177 typedef Node_CItr node_const_iterator;
178 typedef typename node_iterator::value_type iterator;
179 typedef typename node_const_iterator::value_type const_iterator;
180
181 /// Finds the const iterator range corresponding to all values
182 /// whose prefixes match r_key.
184 prefix_range(key_const_reference) const;
185
186 /// Finds the iterator range corresponding to all values whose
187 /// prefixes match r_key.
189 prefix_range(key_const_reference);
190
191 /// Finds the const iterator range corresponding to all values
192 /// whose prefixes match [b, e).
195
196 /// Finds the iterator range corresponding to all values whose
197 /// prefixes match [b, e).
200
201 protected:
202 /// Called to update a node's metadata.
203 inline void
204 operator()(node_iterator node_it, node_const_iterator end_nd_it) const;
205
206 private:
207 node_iterator
208 next_child(node_iterator, a_const_iterator, a_const_iterator,
209 node_iterator, const access_traits&);
210
211 /// Returns the const iterator associated with the just-after last element.
212 virtual const_iterator
213 end() const = 0;
214
215 /// Returns the iterator associated with the just-after last element.
216 virtual iterator
217 end() = 0;
218
219 /// Returns the node_const_iterator associated with the trie's root node.
220 virtual node_const_iterator
221 node_begin() const = 0;
222
223 /// Returns the node_iterator associated with the trie's root node.
224 virtual node_iterator
225 node_begin() = 0;
226
227 /// Returns the node_const_iterator associated with a just-after leaf node.
228 virtual node_const_iterator
229 node_end() const = 0;
230
231 /// Returns the node_iterator associated with a just-after leaf node.
232 virtual node_iterator
233 node_end() = 0;
234
235 /// Access to the cmp_fn object.
236 virtual const access_traits&
237 get_access_traits() const = 0;
238 };
239
241
242#undef PB_DS_CLASS_C_DEC
243
244#define PB_DS_CLASS_C_DEC \
245 trie_order_statistics_node_update<Node_CItr, Node_Itr, \
246 _ATraits, _Alloc>
247
248 /// Functor updating ranks of entrees.
249 template<typename Node_CItr,
250 typename Node_Itr,
251 typename _ATraits,
252 typename _Alloc>
253 class trie_order_statistics_node_update : private PB_DS_TRIE_POLICY_BASE
254 {
255 private:
256 typedef PB_DS_TRIE_POLICY_BASE base_type;
257
258 public:
259 typedef _ATraits access_traits;
260 typedef typename access_traits::const_iterator a_const_iterator;
261 typedef _Alloc allocator_type;
262 typedef typename allocator_type::size_type size_type;
263 typedef typename base_type::key_type key_type;
264 typedef typename base_type::key_const_reference key_const_reference;
265
266 typedef size_type metadata_type;
267 typedef Node_CItr node_const_iterator;
268 typedef Node_Itr node_iterator;
269 typedef typename node_const_iterator::value_type const_iterator;
270 typedef typename node_iterator::value_type iterator;
271
272 /// Finds an entry by __order. Returns a const_iterator to the
273 /// entry with the __order order, or a const_iterator to the
274 /// container object's end if order is at least the size of the
275 /// container object.
276 inline const_iterator
277 find_by_order(size_type) const;
278
279 /// Finds an entry by __order. Returns an iterator to the entry
280 /// with the __order order, or an iterator to the container
281 /// object's end if order is at least the size of the container
282 /// object.
283 inline iterator
284 find_by_order(size_type);
285
286 /// Returns the order of a key within a sequence. For exapmle, if
287 /// r_key is the smallest key, this method will return 0; if r_key
288 /// is a key between the smallest and next key, this method will
289 /// return 1; if r_key is a key larger than the largest key, this
290 /// method will return the size of r_c.
291 inline size_type
292 order_of_key(key_const_reference) const;
293
294 /// Returns the order of a prefix within a sequence. For exapmle,
295 /// if [b, e] is the smallest prefix, this method will return 0; if
296 /// r_key is a key between the smallest and next key, this method
297 /// will return 1; if r_key is a key larger than the largest key,
298 /// this method will return the size of r_c.
299 inline size_type
300 order_of_prefix(a_const_iterator, a_const_iterator) const;
301
302 protected:
303 /// Updates the rank of a node through a node_iterator node_it;
304 /// end_nd_it is the end node iterator.
305 inline void
306 operator()(node_iterator, node_const_iterator) const;
307
308 private:
309 typedef typename base_type::const_reference const_reference;
310 typedef typename base_type::const_pointer const_pointer;
311
312 typedef typename _Alloc::template rebind<metadata_type> __rebind_m;
313 typedef typename __rebind_m::other __rebind_ma;
314 typedef typename __rebind_ma::const_reference metadata_const_reference;
315 typedef typename __rebind_ma::reference metadata_reference;
316
317 /// Returns true if the container is empty.
318 _GLIBCXX_NODISCARD virtual bool
319 empty() const = 0;
320
321 /// Returns the iterator associated with the trie's first element.
322 virtual iterator
323 begin() = 0;
324
325 /// Returns the iterator associated with the trie's
326 /// just-after-last element.
327 virtual iterator
328 end() = 0;
329
330 /// Returns the node_const_iterator associated with the trie's root node.
331 virtual node_const_iterator
332 node_begin() const = 0;
333
334 /// Returns the node_iterator associated with the trie's root node.
335 virtual node_iterator
336 node_begin() = 0;
337
338 /// Returns the node_const_iterator associated with a just-after
339 /// leaf node.
340 virtual node_const_iterator
341 node_end() const = 0;
342
343 /// Returns the node_iterator associated with a just-after leaf node.
344 virtual node_iterator
345 node_end() = 0;
346
347 /// Access to the cmp_fn object.
348 virtual access_traits&
349 get_access_traits() = 0;
350 };
351
353
354#undef PB_DS_CLASS_T_DEC
355#undef PB_DS_CLASS_C_DEC
356#undef PB_DS_TRIE_POLICY_BASE
357
358} // namespace __gnu_pbds
359
360#endif
basic_string< char > string
A string of char.
Definition: stringfwd.h:79
GNU extensions for policy-based data structures for public use.
The standard allocator, as per C++03 [20.4.1].
Definition: allocator.h:125
Traits class for iterators.
Struct holding two objects of arbitrary type.
Definition: stl_pair.h:213
Represents no type, or absence of type, for template tricks.
static size_type e_pos(e_type e)
Maps an element to a position.
std::iterator_traits< const_iterator >::value_type e_type
Element type.
Definition: trie_policy.hpp:93
static const_iterator end(key_const_reference)
Returns a const_iterator to the after-last element of key_const_reference argument.
static const_iterator begin(key_const_reference)
Returns a const_iterator to the first element of key_const_reference agumnet.
detail::__conditional_type< Reverse, typenameString::const_reverse_iterator, typenameString::const_iterator >::__type const_iterator
Element const iterator type.
Definition: trie_policy.hpp:90
A node updator that allows tries to be searched for the range of values that match a certain prefix.
_ATraits access_traits
Element access traits.
std::pair< const_iterator, const_iterator > prefix_range(a_const_iterator, a_const_iterator) const
Finds the const iterator range corresponding to all values whose prefixes match [b,...
void operator()(node_iterator node_it, node_const_iterator end_nd_it) const
Called to update a node's metadata.
std::pair< const_iterator, const_iterator > prefix_range(key_const_reference) const
Finds the const iterator range corresponding to all values whose prefixes match r_key.
access_traits::const_iterator a_const_iterator
Const element iterator.
std::pair< iterator, iterator > prefix_range(a_const_iterator, a_const_iterator)
Finds the iterator range corresponding to all values whose prefixes match [b, e).
allocator_type::size_type size_type
Size type.
std::pair< iterator, iterator > prefix_range(key_const_reference)
Finds the iterator range corresponding to all values whose prefixes match r_key.
Functor updating ranks of entrees.
iterator find_by_order(size_type)
Finds an entry by __order. Returns an iterator to the entry with the __order order,...
const_iterator find_by_order(size_type) const
Finds an entry by __order. Returns a const_iterator to the entry with the __order order,...
size_type order_of_prefix(a_const_iterator, a_const_iterator) const
Returns the order of a prefix within a sequence. For exapmle, if [b, e] is the smallest prefix,...
size_type order_of_key(key_const_reference) const
Returns the order of a key within a sequence. For exapmle, if r_key is the smallest key,...
void operator()(node_iterator, node_const_iterator) const
Updates the rank of a node through a node_iterator node_it; end_nd_it is the end node iterator.
Base class for trie policies.