]>
Commit | Line | Data |
---|---|---|
4569a895 AT |
1 | // -*- C++ -*- |
2 | ||
3 | // Copyright (C) 2005, 2006 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 2, 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 | // You should have received a copy of the GNU General Public License | |
17 | // along with this library; see the file COPYING. If not, write to | |
18 | // the Free Software Foundation, 59 Temple Place - Suite 330, Boston, | |
19 | // MA 02111-1307, USA. | |
20 | ||
21 | // As a special exception, you may use this file as part of a free | |
22 | // software library without restriction. Specifically, if other files | |
23 | // instantiate templates or use macros or inline functions from this | |
24 | // file, or you compile this file and link it with other files to | |
25 | // produce an executable, this file does not by itself cause the | |
26 | // resulting executable to be covered by the GNU General Public | |
27 | // License. This exception does not however invalidate any other | |
28 | // reasons why the executable file might be covered by the GNU General | |
29 | // Public License. | |
30 | ||
31 | // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. | |
32 | ||
33 | // Permission to use, copy, modify, sell, and distribute this software | |
34 | // is hereby granted without fee, provided that the above copyright | |
35 | // notice appears in all copies, and that both that copyright notice | |
36 | // and this permission notice appear in supporting documentation. None | |
37 | // of the above authors, nor IBM Haifa Research Laboratories, make any | |
38 | // representation about the suitability of this software for any | |
39 | // purpose. It is provided "as is" without express or implied | |
40 | // warranty. | |
41 | ||
42 | /** | |
43 | * @file trie_policy.hpp | |
44 | * Contains trie-related policies. | |
45 | */ | |
46 | ||
47 | #ifndef PB_DS_TRIE_POLICY_HPP | |
48 | #define PB_DS_TRIE_POLICY_HPP | |
49 | ||
50 | #include <string> | |
51 | #include <climits> | |
52 | #include <ext/pb_ds/detail/type_utils.hpp> | |
53 | #include <ext/pb_ds/detail/trie_policy/trie_policy_base.hpp> | |
54 | ||
55 | namespace pb_ds | |
56 | { | |
57 | // A null node updator, indicating that no node updates are required. | |
58 | template<typename Const_Node_Iterator, | |
59 | typename Node_Iterator, | |
60 | typename E_Access_Traits, | |
61 | typename Allocator> | |
62 | struct null_trie_node_update | |
63 | { }; | |
64 | ||
65 | #define PB_DS_STATIC_ASSERT(UNIQUE, E) \ | |
66 | typedef detail::static_assert_dumclass<sizeof(detail::static_assert<(bool)(E)>)> UNIQUE##static_assert_type | |
67 | ||
68 | #define PB_DS_CLASS_T_DEC \ | |
69 | template<typename String, typename String::value_type Min_E_Val, typename String::value_type Max_E_Val, bool Reverse, typename Allocator> | |
70 | ||
71 | #define PB_DS_CLASS_C_DEC \ | |
72 | string_trie_e_access_traits<String, Min_E_Val,Max_E_Val,Reverse,Allocator> | |
73 | ||
74 | // Element access traits for string types. | |
75 | template<typename String = std::string, | |
76 | typename String::value_type Min_E_Val = SCHAR_MIN, | |
77 | typename String::value_type Max_E_Val = SCHAR_MAX, | |
78 | bool Reverse = false, | |
79 | typename Allocator = std::allocator<char> > | |
80 | struct string_trie_e_access_traits | |
81 | { | |
82 | public: | |
83 | typedef typename Allocator::size_type size_type; | |
84 | typedef String key_type; | |
85 | typedef typename Allocator::template rebind<key_type>::other key_rebind; | |
86 | typedef typename key_rebind::const_reference const_key_reference; | |
87 | ||
88 | enum | |
89 | { | |
90 | reverse = Reverse | |
91 | }; | |
92 | ||
93 | // Element const iterator type. | |
94 | typedef typename detail::conditional_type<Reverse, typename String::const_reverse_iterator, typename String::const_iterator>::type const_iterator; | |
95 | ||
96 | // Element type. | |
97 | typedef typename std::iterator_traits<const_iterator>::value_type e_type; | |
98 | ||
99 | enum | |
100 | { | |
101 | min_e_val = Min_E_Val, | |
102 | max_e_val = Max_E_Val, | |
103 | max_size = max_e_val - min_e_val + 1 | |
104 | }; | |
105 | ||
106 | // Returns a const_iterator to the first element of | |
107 | // const_key_reference agumnet. | |
108 | inline static const_iterator | |
109 | begin(const_key_reference); | |
110 | ||
111 | // Returns a const_iterator to the after-last element of | |
112 | // const_key_reference argument. | |
113 | inline static const_iterator | |
114 | end(const_key_reference); | |
115 | ||
116 | // Maps an element to a position. | |
117 | inline static size_type | |
118 | e_pos(e_type e); | |
119 | ||
120 | private: | |
121 | PB_DS_STATIC_ASSERT(min_max_size, max_size >= 2); | |
122 | ||
123 | inline static const_iterator | |
124 | begin_imp(const_key_reference, detail::false_type); | |
125 | ||
126 | inline static const_iterator | |
127 | begin_imp(const_key_reference, detail::true_type); | |
128 | ||
129 | inline static const_iterator | |
130 | end_imp(const_key_reference, detail::false_type); | |
131 | ||
132 | inline static const_iterator | |
133 | end_imp(const_key_reference, detail::true_type); | |
134 | ||
135 | static detail::integral_constant<int,Reverse> s_rev_ind; | |
136 | }; | |
137 | ||
138 | #include <ext/pb_ds/detail/trie_policy/string_trie_e_access_traits_imp.hpp> | |
139 | ||
140 | #undef PB_DS_CLASS_T_DEC | |
141 | #undef PB_DS_CLASS_C_DEC | |
142 | ||
143 | #define PB_DS_CLASS_T_DEC \ | |
144 | template<typename Const_Node_Iterator,typename Node_Iterator,class E_Access_Traits, typename Allocator> | |
145 | ||
146 | #define PB_DS_CLASS_C_DEC \ | |
147 | trie_prefix_search_node_update<Const_Node_Iterator, Node_Iterator, E_Access_Traits,Allocator> | |
148 | ||
149 | #define PB_DS_BASE_C_DEC \ | |
150 | detail::trie_policy_base<Const_Node_Iterator,Node_Iterator,E_Access_Traits, Allocator> | |
151 | ||
152 | // A node updator that allows tries to be searched for the range of | |
153 | // values that match a certain prefix. | |
154 | template<typename Const_Node_Iterator, | |
155 | typename Node_Iterator, | |
156 | typename E_Access_Traits, | |
157 | typename Allocator> | |
158 | class trie_prefix_search_node_update : private PB_DS_BASE_C_DEC | |
159 | { | |
160 | private: | |
161 | typedef PB_DS_BASE_C_DEC base_type; | |
162 | ||
163 | public: | |
164 | typedef typename base_type::key_type key_type; | |
165 | typedef typename base_type::const_key_reference const_key_reference; | |
166 | ||
167 | // Element access traits. | |
168 | typedef E_Access_Traits e_access_traits; | |
169 | ||
170 | // Const element iterator. | |
171 | typedef typename e_access_traits::const_iterator const_e_iterator; | |
172 | ||
173 | // Allocator type. | |
174 | typedef Allocator allocator; | |
175 | ||
176 | // Size type. | |
177 | typedef typename allocator::size_type size_type; | |
178 | typedef detail::null_node_metadata metadata_type; | |
179 | typedef Const_Node_Iterator const_node_iterator; | |
180 | typedef Node_Iterator node_iterator; | |
181 | typedef typename const_node_iterator::value_type const_iterator; | |
182 | typedef typename node_iterator::value_type iterator; | |
183 | ||
184 | // Finds the const iterator range corresponding to all values | |
185 | // whose prefixes match r_key. | |
186 | std::pair<const_iterator, const_iterator> | |
187 | prefix_range(const_key_reference) const; | |
188 | ||
189 | // Finds the iterator range corresponding to all values whose | |
190 | // prefixes match r_key. | |
191 | std::pair<iterator, iterator> | |
192 | prefix_range(const_key_reference); | |
193 | ||
194 | // Finds the const iterator range corresponding to all values | |
195 | // whose prefixes match [b, e). | |
196 | std::pair<const_iterator, const_iterator> | |
197 | prefix_range(const_e_iterator, const_e_iterator) const; | |
198 | ||
199 | // Finds the iterator range corresponding to all values whose | |
200 | // prefixes match [b, e). | |
201 | std::pair<iterator, iterator> | |
202 | prefix_range(const_e_iterator, const_e_iterator); | |
203 | ||
204 | protected: | |
205 | // Called to update a node's metadata. | |
206 | inline void | |
207 | operator()(node_iterator node_it, const_node_iterator end_nd_it) const; | |
208 | ||
209 | private: | |
210 | // Returns the const iterator associated with the just-after last element. | |
211 | virtual const_iterator | |
212 | end() const = 0; | |
213 | ||
214 | // Returns the iterator associated with the just-after last element. | |
215 | virtual iterator | |
216 | end() = 0; | |
217 | ||
218 | // Returns the const_node_iterator associated with the trie's root node. | |
219 | virtual const_node_iterator | |
220 | node_begin() const = 0; | |
221 | ||
222 | // Returns the node_iterator associated with the trie's root node. | |
223 | virtual node_iterator | |
224 | node_begin() = 0; | |
225 | ||
226 | // Returns the const_node_iterator associated with a just-after leaf node. | |
227 | virtual const_node_iterator | |
228 | node_end() const = 0; | |
229 | ||
230 | // Returns the node_iterator associated with a just-after leaf node. | |
231 | virtual node_iterator | |
232 | node_end() = 0; | |
233 | ||
234 | // Access to the cmp_fn object. | |
235 | virtual const e_access_traits& | |
236 | get_e_access_traits() const = 0; | |
237 | ||
238 | node_iterator | |
239 | next_child(node_iterator, const_e_iterator, const_e_iterator, | |
240 | node_iterator, const e_access_traits&); | |
241 | }; | |
242 | ||
243 | #include <ext/pb_ds/detail/trie_policy/prefix_search_node_update_imp.hpp> | |
244 | ||
245 | #undef PB_DS_CLASS_C_DEC | |
246 | ||
247 | #define PB_DS_CLASS_C_DEC \ | |
248 | trie_order_statistics_node_update<Const_Node_Iterator, Node_Iterator,E_Access_Traits, Allocator> | |
249 | ||
250 | // Functor updating ranks of entrees. | |
251 | template<typename Const_Node_Iterator, | |
252 | typename Node_Iterator, | |
253 | typename E_Access_Traits, | |
254 | typename Allocator> | |
255 | class trie_order_statistics_node_update : private PB_DS_BASE_C_DEC | |
256 | { | |
257 | private: | |
258 | typedef PB_DS_BASE_C_DEC base_type; | |
259 | ||
260 | public: | |
261 | typedef E_Access_Traits e_access_traits; | |
262 | typedef typename e_access_traits::const_iterator const_e_iterator; | |
263 | typedef Allocator allocator; | |
264 | typedef typename allocator::size_type size_type; | |
265 | typedef typename base_type::key_type key_type; | |
266 | typedef typename base_type::const_key_reference const_key_reference; | |
267 | ||
268 | typedef size_type metadata_type; | |
269 | typedef Const_Node_Iterator const_node_iterator; | |
270 | typedef Node_Iterator node_iterator; | |
271 | typedef typename const_node_iterator::value_type const_iterator; | |
272 | typedef typename node_iterator::value_type iterator; | |
273 | ||
274 | // Finds an entry by __order. Returns a const_iterator to the | |
275 | // entry with the __order order, or a const_iterator to the | |
276 | // container object's end if order is at least the size of the | |
277 | // container object. | |
278 | inline const_iterator | |
279 | find_by_order(size_type) const; | |
280 | ||
281 | // Finds an entry by __order. Returns an iterator to the entry | |
282 | // with the __order order, or an iterator to the container | |
283 | // object's end if order is at least the size of the container | |
284 | // object. | |
285 | inline iterator | |
286 | find_by_order(size_type); | |
287 | ||
288 | // Returns the order of a key within a sequence. For exapmle, if | |
289 | // r_key is the smallest key, this method will return 0; if r_key | |
290 | // is a key between the smallest and next key, this method will | |
291 | // return 1; if r_key is a key larger than the largest key, this | |
292 | // method will return the size of r_c. | |
293 | inline size_type | |
294 | order_of_key(const_key_reference) const; | |
295 | ||
296 | // Returns the order of a prefix within a sequence. For exapmle, | |
297 | // if [b, e] is the smallest prefix, this method will return 0; if | |
298 | // r_key is a key between the smallest and next key, this method | |
299 | // will return 1; if r_key is a key larger than the largest key, | |
300 | // this method will return the size of r_c. | |
301 | inline size_type | |
302 | order_of_prefix(const_e_iterator, const_e_iterator) const; | |
303 | ||
304 | private: | |
305 | typedef typename base_type::const_reference const_reference; | |
306 | typedef typename base_type::const_pointer const_pointer; | |
307 | ||
308 | typedef typename Allocator::template rebind<metadata_type>::other metadata_rebind; | |
309 | typedef typename metadata_rebind::const_reference const_metadata_reference; | |
310 | typedef typename metadata_rebind::reference metadata_reference; | |
311 | ||
312 | // Returns true if the container is empty. | |
313 | virtual bool | |
314 | empty() const = 0; | |
315 | ||
316 | // Returns the iterator associated with the trie's first element. | |
317 | virtual iterator | |
318 | begin() = 0; | |
319 | ||
320 | // Returns the iterator associated with the trie's | |
321 | // just-after-last element. | |
322 | virtual iterator | |
323 | end() = 0; | |
324 | ||
325 | // Returns the const_node_iterator associated with the trie's root node. | |
326 | virtual const_node_iterator | |
327 | node_begin() const = 0; | |
328 | ||
329 | // Returns the node_iterator associated with the trie's root node. | |
330 | virtual node_iterator | |
331 | node_begin() = 0; | |
332 | ||
333 | // Returns the const_node_iterator associated with a just-after | |
334 | // leaf node. | |
335 | virtual const_node_iterator | |
336 | node_end() const = 0; | |
337 | ||
338 | // Returns the node_iterator associated with a just-after leaf node. | |
339 | virtual node_iterator | |
340 | node_end() = 0; | |
341 | ||
342 | // Access to the cmp_fn object. | |
343 | virtual e_access_traits& | |
344 | get_e_access_traits() = 0; | |
345 | ||
346 | protected: | |
347 | // Updates the rank of a node through a node_iterator node_it; | |
348 | // end_nd_it is the end node iterator. | |
349 | inline void | |
350 | operator()(node_iterator, const_node_iterator) const; | |
351 | ||
352 | // Destructor. | |
353 | virtual | |
354 | ~trie_order_statistics_node_update(); | |
355 | }; | |
356 | ||
357 | #include <ext/pb_ds/detail/trie_policy/order_statistics_imp.hpp> | |
358 | ||
359 | #undef PB_DS_CLASS_T_DEC | |
360 | #undef PB_DS_CLASS_C_DEC | |
361 | #undef PB_DS_BASE_C_DEC | |
362 | #undef PB_DS_STATIC_ASSERT | |
363 | ||
364 | } // namespace pb_ds | |
365 | ||
366 | #endif |