libstdc++
trie_policy.hpp
Go to the documentation of this file.
1 // -*- C++ -*-
2 
3 // Copyright (C) 2005, 2006, 2007, 2009, 2010, 2011
4 // Free Software Foundation, Inc.
5 //
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
10 // version.
11 
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.
16 
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.
20 
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/>.
25 
26 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
27 
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
35 // warranty.
36 
37 /**
38  * @file trie_policy.hpp
39  * Contains trie-related policies.
40  */
41 
42 #ifndef PB_DS_TRIE_POLICY_HPP
43 #define PB_DS_TRIE_POLICY_HPP
44 
45 #include <bits/c++config.h>
46 #include <string>
49 
50 namespace __gnu_pbds
51 {
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, \
55  typename _Alloc>
56 
57 #define PB_DS_CLASS_C_DEC \
58  trie_string_access_traits<String, Min_E_Val,Max_E_Val,Reverse,_Alloc>
59 
60  /**
61  * Element access traits for string types.
62  *
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.
67  * Default: false.
68  * @tparam _Alloc Allocator type.
69  */
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,
73  bool Reverse = false,
74  typename _Alloc = std::allocator<char> >
76  {
77  public:
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;
82 
83  enum
84  {
85  reverse = Reverse
86  };
87 
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;
92 
93  /// Element type.
94  typedef typename std::iterator_traits<const_iterator>::value_type e_type;
95 
96  enum
97  {
98  min_e_val = Min_E_Val,
99  max_e_val = Max_E_Val,
100  max_size = max_e_val - min_e_val + 1
101  };
102  PB_DS_STATIC_ASSERT(min_max_size, max_size >= 2);
103 
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);
108 
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);
113 
114  /// Maps an element to a position.
115  inline static size_type
116  e_pos(e_type e);
117 
118  private:
119  inline static const_iterator
120  begin_imp(key_const_reference, detail::false_type);
121 
122  inline static const_iterator
123  begin_imp(key_const_reference, detail::true_type);
124 
125  inline static const_iterator
126  end_imp(key_const_reference, detail::false_type);
127 
128  inline static const_iterator
129  end_imp(key_const_reference, detail::true_type);
130 
131  static detail::integral_constant<int, Reverse> s_rev_ind;
132  };
133 
135 
136 #undef PB_DS_CLASS_T_DEC
137 #undef PB_DS_CLASS_C_DEC
138 
139 #define PB_DS_CLASS_T_DEC \
140  template<typename Node_CItr,typename Node_Itr, \
141  typename _ATraits, typename _Alloc>
142 
143 #define PB_DS_CLASS_C_DEC \
144  trie_prefix_search_node_update<Node_CItr, Node_Itr, \
145  _ATraits,_Alloc>
146 
147 #define PB_DS_TRIE_POLICY_BASE \
148  detail::trie_policy_base<Node_CItr,Node_Itr,_ATraits, _Alloc>
149 
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,
153  typename Node_Itr,
154  typename _ATraits,
155  typename _Alloc>
156  class trie_prefix_search_node_update : private PB_DS_TRIE_POLICY_BASE
157  {
158  private:
159  typedef PB_DS_TRIE_POLICY_BASE base_type;
160 
161  public:
162  typedef typename base_type::key_type key_type;
163  typedef typename base_type::key_const_reference key_const_reference;
164 
165  /// Element access traits.
166  typedef _ATraits access_traits;
167 
168  /// Const element iterator.
169  typedef typename access_traits::const_iterator a_const_iterator;
170 
171  /// _Alloc type.
172  typedef _Alloc allocator_type;
173 
174  /// Size 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;
181 
182  /// Finds the const iterator range corresponding to all values
183  /// whose prefixes match r_key.
185  prefix_range(key_const_reference) const;
186 
187  /// Finds the iterator range corresponding to all values whose
188  /// prefixes match r_key.
190  prefix_range(key_const_reference);
191 
192  /// Finds the const iterator range corresponding to all values
193  /// whose prefixes match [b, e).
196 
197  /// Finds the iterator range corresponding to all values whose
198  /// prefixes match [b, e).
201 
202  protected:
203  /// Called to update a node's metadata.
204  inline void
205  operator()(node_iterator node_it, node_const_iterator end_nd_it) const;
206 
207  private:
208  node_iterator
209  next_child(node_iterator, a_const_iterator, a_const_iterator,
210  node_iterator, const access_traits&);
211 
212  /// Returns the const iterator associated with the just-after last element.
213  virtual const_iterator
214  end() const = 0;
215 
216  /// Returns the iterator associated with the just-after last element.
217  virtual iterator
218  end() = 0;
219 
220  /// Returns the node_const_iterator associated with the trie's root node.
221  virtual node_const_iterator
222  node_begin() const = 0;
223 
224  /// Returns the node_iterator associated with the trie's root node.
225  virtual node_iterator
226  node_begin() = 0;
227 
228  /// Returns the node_const_iterator associated with a just-after leaf node.
229  virtual node_const_iterator
230  node_end() const = 0;
231 
232  /// Returns the node_iterator associated with a just-after leaf node.
233  virtual node_iterator
234  node_end() = 0;
235 
236  /// Access to the cmp_fn object.
237  virtual const access_traits&
238  get_access_traits() const = 0;
239  };
240 
242 
243 #undef PB_DS_CLASS_C_DEC
244 
245 #define PB_DS_CLASS_C_DEC \
246  trie_order_statistics_node_update<Node_CItr, Node_Itr, \
247  _ATraits, _Alloc>
248 
249  /// Functor updating ranks of entrees.
250  template<typename Node_CItr,
251  typename Node_Itr,
252  typename _ATraits,
253  typename _Alloc>
254  class trie_order_statistics_node_update : private PB_DS_TRIE_POLICY_BASE
255  {
256  private:
257  typedef PB_DS_TRIE_POLICY_BASE base_type;
258 
259  public:
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;
266 
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;
272 
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;
279 
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
283  /// object.
284  inline iterator
285  find_by_order(size_type);
286 
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.
292  inline size_type
293  order_of_key(key_const_reference) const;
294 
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.
300  inline size_type
301  order_of_prefix(a_const_iterator, a_const_iterator) const;
302 
303  protected:
304  /// Updates the rank of a node through a node_iterator node_it;
305  /// end_nd_it is the end node iterator.
306  inline void
307  operator()(node_iterator, node_const_iterator) const;
308 
309  private:
310  typedef typename base_type::const_reference const_reference;
311  typedef typename base_type::const_pointer const_pointer;
312 
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;
317 
318  /// Returns true if the container is empty.
319  virtual bool
320  empty() const = 0;
321 
322  /// Returns the iterator associated with the trie's first element.
323  virtual iterator
324  begin() = 0;
325 
326  /// Returns the iterator associated with the trie's
327  /// just-after-last element.
328  virtual iterator
329  end() = 0;
330 
331  /// Returns the node_const_iterator associated with the trie's root node.
332  virtual node_const_iterator
333  node_begin() const = 0;
334 
335  /// Returns the node_iterator associated with the trie's root node.
336  virtual node_iterator
337  node_begin() = 0;
338 
339  /// Returns the node_const_iterator associated with a just-after
340  /// leaf node.
341  virtual node_const_iterator
342  node_end() const = 0;
343 
344  /// Returns the node_iterator associated with a just-after leaf node.
345  virtual node_iterator
346  node_end() = 0;
347 
348  /// Access to the cmp_fn object.
349  virtual access_traits&
350  get_access_traits() = 0;
351  };
352 
354 
355 #undef PB_DS_CLASS_T_DEC
356 #undef PB_DS_CLASS_C_DEC
357 #undef PB_DS_TRIE_POLICY_BASE
358 
359 } // namespace __gnu_pbds
360 
361 #endif