libstdc++
trie_policy.hpp
Go to the documentation of this file.
1 // -*- C++ -*-
2 
3 // Copyright (C) 2005, 2006, 2007, 2009 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 <string>
46 #include <ext/pb_ds/detail/trie_policy/trie_policy_base.hpp>
47 
48 namespace __gnu_pbds
49 {
50  // A null node updator, indicating that no node updates are required.
51  template<typename Const_Node_Iterator,
52  typename Node_Iterator,
53  typename E_Access_Traits,
54  typename Allocator>
55  struct null_trie_node_update
56  { };
57 
58 #define PB_DS_CLASS_T_DEC \
59  template<typename String, typename String::value_type Min_E_Val, typename String::value_type Max_E_Val, bool Reverse, typename Allocator>
60 
61 #define PB_DS_CLASS_C_DEC \
62  string_trie_e_access_traits<String, Min_E_Val,Max_E_Val,Reverse,Allocator>
63 
64  // Element access traits for string types.
65  template<typename String = std::string,
66  typename String::value_type Min_E_Val = detail::__numeric_traits<typename String::value_type>::__min,
67  typename String::value_type Max_E_Val = detail::__numeric_traits<typename String::value_type>::__max,
68  bool Reverse = false,
69  typename Allocator = std::allocator<char> >
70  struct string_trie_e_access_traits
71  {
72  public:
73  typedef typename Allocator::size_type size_type;
74  typedef String key_type;
75  typedef typename Allocator::template rebind<key_type>::other key_rebind;
76  typedef typename key_rebind::const_reference const_key_reference;
77 
78  enum
79  {
80  reverse = Reverse
81  };
82 
83  // Element const iterator type.
84  typedef typename detail::__conditional_type<Reverse, typename String::const_reverse_iterator, typename String::const_iterator>::__type const_iterator;
85 
86  // Element type.
87  typedef typename std::iterator_traits<const_iterator>::value_type e_type;
88 
89  enum
90  {
91  min_e_val = Min_E_Val,
92  max_e_val = Max_E_Val,
93  max_size = max_e_val - min_e_val + 1
94  };
95  PB_DS_STATIC_ASSERT(min_max_size, max_size >= 2);
96 
97  // Returns a const_iterator to the first element of
98  // const_key_reference agumnet.
99  inline static const_iterator
100  begin(const_key_reference);
101 
102  // Returns a const_iterator to the after-last element of
103  // const_key_reference argument.
104  inline static const_iterator
105  end(const_key_reference);
106 
107  // Maps an element to a position.
108  inline static size_type
109  e_pos(e_type e);
110 
111  private:
112 
113  inline static const_iterator
114  begin_imp(const_key_reference, detail::false_type);
115 
116  inline static const_iterator
117  begin_imp(const_key_reference, detail::true_type);
118 
119  inline static const_iterator
120  end_imp(const_key_reference, detail::false_type);
121 
122  inline static const_iterator
123  end_imp(const_key_reference, detail::true_type);
124 
125  static detail::integral_constant<int, Reverse> s_rev_ind;
126  };
127 
128 #include <ext/pb_ds/detail/trie_policy/string_trie_e_access_traits_imp.hpp>
129 
130 #undef PB_DS_CLASS_T_DEC
131 #undef PB_DS_CLASS_C_DEC
132 
133 #define PB_DS_CLASS_T_DEC \
134  template<typename Const_Node_Iterator,typename Node_Iterator,class E_Access_Traits, typename Allocator>
135 
136 #define PB_DS_CLASS_C_DEC \
137  trie_prefix_search_node_update<Const_Node_Iterator, Node_Iterator, E_Access_Traits,Allocator>
138 
139 #define PB_DS_BASE_C_DEC \
140  detail::trie_policy_base<Const_Node_Iterator,Node_Iterator,E_Access_Traits, Allocator>
141 
142  // A node updator that allows tries to be searched for the range of
143  // values that match a certain prefix.
144  template<typename Const_Node_Iterator,
145  typename Node_Iterator,
146  typename E_Access_Traits,
147  typename Allocator>
148  class trie_prefix_search_node_update : private PB_DS_BASE_C_DEC
149  {
150  private:
151  typedef PB_DS_BASE_C_DEC base_type;
152 
153  public:
154  typedef typename base_type::key_type key_type;
155  typedef typename base_type::const_key_reference const_key_reference;
156 
157  // Element access traits.
158  typedef E_Access_Traits e_access_traits;
159 
160  // Const element iterator.
161  typedef typename e_access_traits::const_iterator const_e_iterator;
162 
163  // Allocator type.
164  typedef Allocator allocator_type;
165 
166  // Size type.
167  typedef typename allocator_type::size_type size_type;
168  typedef detail::null_node_metadata metadata_type;
169  typedef Const_Node_Iterator const_node_iterator;
170  typedef Node_Iterator node_iterator;
171  typedef typename const_node_iterator::value_type const_iterator;
172  typedef typename node_iterator::value_type iterator;
173 
174  // Finds the const iterator range corresponding to all values
175  // whose prefixes match r_key.
177  prefix_range(const_key_reference) const;
178 
179  // Finds the iterator range corresponding to all values whose
180  // prefixes match r_key.
182  prefix_range(const_key_reference);
183 
184  // Finds the const iterator range corresponding to all values
185  // whose prefixes match [b, e).
187  prefix_range(const_e_iterator, const_e_iterator) const;
188 
189  // Finds the iterator range corresponding to all values whose
190  // prefixes match [b, e).
192  prefix_range(const_e_iterator, const_e_iterator);
193 
194  protected:
195  // Called to update a node's metadata.
196  inline void
197  operator()(node_iterator node_it, const_node_iterator end_nd_it) const;
198 
199  private:
200  // Returns the const iterator associated with the just-after last element.
201  virtual const_iterator
202  end() const = 0;
203 
204  // Returns the iterator associated with the just-after last element.
205  virtual iterator
206  end() = 0;
207 
208  // Returns the const_node_iterator associated with the trie's root node.
209  virtual const_node_iterator
210  node_begin() const = 0;
211 
212  // Returns the node_iterator associated with the trie's root node.
213  virtual node_iterator
214  node_begin() = 0;
215 
216  // Returns the const_node_iterator associated with a just-after leaf node.
217  virtual const_node_iterator
218  node_end() const = 0;
219 
220  // Returns the node_iterator associated with a just-after leaf node.
221  virtual node_iterator
222  node_end() = 0;
223 
224  // Access to the cmp_fn object.
225  virtual const e_access_traits&
226  get_e_access_traits() const = 0;
227 
228  node_iterator
229  next_child(node_iterator, const_e_iterator, const_e_iterator,
230  node_iterator, const e_access_traits&);
231  };
232 
233 #include <ext/pb_ds/detail/trie_policy/prefix_search_node_update_imp.hpp>
234 
235 #undef PB_DS_CLASS_C_DEC
236 
237 #define PB_DS_CLASS_C_DEC \
238  trie_order_statistics_node_update<Const_Node_Iterator, Node_Iterator,E_Access_Traits, Allocator>
239 
240  // Functor updating ranks of entrees.
241  template<typename Const_Node_Iterator,
242  typename Node_Iterator,
243  typename E_Access_Traits,
244  typename Allocator>
245  class trie_order_statistics_node_update : private PB_DS_BASE_C_DEC
246  {
247  private:
248  typedef PB_DS_BASE_C_DEC base_type;
249 
250  public:
251  typedef E_Access_Traits e_access_traits;
252  typedef typename e_access_traits::const_iterator const_e_iterator;
253  typedef Allocator allocator_type;
254  typedef typename allocator_type::size_type size_type;
255  typedef typename base_type::key_type key_type;
256  typedef typename base_type::const_key_reference const_key_reference;
257 
258  typedef size_type metadata_type;
259  typedef Const_Node_Iterator const_node_iterator;
260  typedef Node_Iterator node_iterator;
261  typedef typename const_node_iterator::value_type const_iterator;
262  typedef typename node_iterator::value_type iterator;
263 
264  // Finds an entry by __order. Returns a const_iterator to the
265  // entry with the __order order, or a const_iterator to the
266  // container object's end if order is at least the size of the
267  // container object.
268  inline const_iterator
269  find_by_order(size_type) const;
270 
271  // Finds an entry by __order. Returns an iterator to the entry
272  // with the __order order, or an iterator to the container
273  // object's end if order is at least the size of the container
274  // object.
275  inline iterator
276  find_by_order(size_type);
277 
278  // Returns the order of a key within a sequence. For exapmle, if
279  // r_key is the smallest key, this method will return 0; if r_key
280  // is a key between the smallest and next key, this method will
281  // return 1; if r_key is a key larger than the largest key, this
282  // method will return the size of r_c.
283  inline size_type
284  order_of_key(const_key_reference) const;
285 
286  // Returns the order of a prefix within a sequence. For exapmle,
287  // if [b, e] is the smallest prefix, this method will return 0; if
288  // r_key is a key between the smallest and next key, this method
289  // will return 1; if r_key is a key larger than the largest key,
290  // this method will return the size of r_c.
291  inline size_type
292  order_of_prefix(const_e_iterator, const_e_iterator) const;
293 
294  private:
295  typedef typename base_type::const_reference const_reference;
296  typedef typename base_type::const_pointer const_pointer;
297 
298  typedef typename Allocator::template rebind<metadata_type>::other metadata_rebind;
299  typedef typename metadata_rebind::const_reference const_metadata_reference;
300  typedef typename metadata_rebind::reference metadata_reference;
301 
302  // Returns true if the container is empty.
303  virtual bool
304  empty() const = 0;
305 
306  // Returns the iterator associated with the trie's first element.
307  virtual iterator
308  begin() = 0;
309 
310  // Returns the iterator associated with the trie's
311  // just-after-last element.
312  virtual iterator
313  end() = 0;
314 
315  // Returns the const_node_iterator associated with the trie's root node.
316  virtual const_node_iterator
317  node_begin() const = 0;
318 
319  // Returns the node_iterator associated with the trie's root node.
320  virtual node_iterator
321  node_begin() = 0;
322 
323  // Returns the const_node_iterator associated with a just-after
324  // leaf node.
325  virtual const_node_iterator
326  node_end() const = 0;
327 
328  // Returns the node_iterator associated with a just-after leaf node.
329  virtual node_iterator
330  node_end() = 0;
331 
332  // Access to the cmp_fn object.
333  virtual e_access_traits&
334  get_e_access_traits() = 0;
335 
336  protected:
337  // Updates the rank of a node through a node_iterator node_it;
338  // end_nd_it is the end node iterator.
339  inline void
340  operator()(node_iterator, const_node_iterator) const;
341 
342  // Destructor.
343  virtual
344  ~trie_order_statistics_node_update();
345  };
346 
347 #include <ext/pb_ds/detail/trie_policy/order_statistics_imp.hpp>
348 
349 #undef PB_DS_CLASS_T_DEC
350 #undef PB_DS_CLASS_C_DEC
351 #undef PB_DS_BASE_C_DEC
352 
353 } // namespace __gnu_pbds
354 
355 #endif
pair holds two objects of arbitrary type.
Definition: stl_pair.h:67
The "standard" allocator, as per [20.4].Further details: http://gcc.gnu.org/onlinedocs/libstdc++/manu...
Definition: allocator.h:60
integral_constant< bool, true > true_type
typedef for true_type
integral_constant< bool, false > false_type
typedef for false_type