41 #ifndef PB_DS_TRIE_POLICY_HPP
42 #define PB_DS_TRIE_POLICY_HPP
46 #include <ext/pb_ds/detail/trie_policy/trie_policy_base.hpp>
51 template<
typename Const_Node_Iterator,
52 typename Node_Iterator,
53 typename E_Access_Traits,
55 struct null_trie_node_update
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>
61 #define PB_DS_CLASS_C_DEC \
62 string_trie_e_access_traits<String, Min_E_Val,Max_E_Val,Reverse,Allocator>
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,
70 struct string_trie_e_access_traits
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;
84 typedef typename detail::__conditional_type<Reverse, typename String::const_reverse_iterator, typename String::const_iterator>::__type const_iterator;
87 typedef typename std::iterator_traits<const_iterator>::value_type e_type;
91 min_e_val = Min_E_Val,
92 max_e_val = Max_E_Val,
93 max_size = max_e_val - min_e_val + 1
95 PB_DS_STATIC_ASSERT(min_max_size, max_size >= 2);
99 inline static const_iterator
100 begin(const_key_reference);
104 inline static const_iterator
105 end(const_key_reference);
108 inline static size_type
113 inline static const_iterator
114 begin_imp(const_key_reference, detail::false_type);
116 inline static const_iterator
117 begin_imp(const_key_reference, detail::true_type);
119 inline static const_iterator
120 end_imp(const_key_reference, detail::false_type);
122 inline static const_iterator
123 end_imp(const_key_reference, detail::true_type);
125 static detail::integral_constant<int, Reverse> s_rev_ind;
128 #include <ext/pb_ds/detail/trie_policy/string_trie_e_access_traits_imp.hpp>
130 #undef PB_DS_CLASS_T_DEC
131 #undef PB_DS_CLASS_C_DEC
133 #define PB_DS_CLASS_T_DEC \
134 template<typename Const_Node_Iterator,typename Node_Iterator,class E_Access_Traits, typename Allocator>
136 #define PB_DS_CLASS_C_DEC \
137 trie_prefix_search_node_update<Const_Node_Iterator, Node_Iterator, E_Access_Traits,Allocator>
139 #define PB_DS_BASE_C_DEC \
140 detail::trie_policy_base<Const_Node_Iterator,Node_Iterator,E_Access_Traits, Allocator>
144 template<
typename Const_Node_Iterator,
145 typename Node_Iterator,
146 typename E_Access_Traits,
148 class trie_prefix_search_node_update :
private PB_DS_BASE_C_DEC
151 typedef PB_DS_BASE_C_DEC base_type;
154 typedef typename base_type::key_type key_type;
155 typedef typename base_type::const_key_reference const_key_reference;
158 typedef E_Access_Traits e_access_traits;
161 typedef typename e_access_traits::const_iterator const_e_iterator;
164 typedef Allocator allocator_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;
177 prefix_range(const_key_reference)
const;
182 prefix_range(const_key_reference);
187 prefix_range(const_e_iterator, const_e_iterator)
const;
192 prefix_range(const_e_iterator, const_e_iterator);
197 operator()(node_iterator node_it, const_node_iterator end_nd_it)
const;
201 virtual const_iterator
209 virtual const_node_iterator
210 node_begin()
const = 0;
213 virtual node_iterator
217 virtual const_node_iterator
218 node_end()
const = 0;
221 virtual node_iterator
225 virtual const e_access_traits&
226 get_e_access_traits()
const = 0;
229 next_child(node_iterator, const_e_iterator, const_e_iterator,
230 node_iterator,
const e_access_traits&);
233 #include <ext/pb_ds/detail/trie_policy/prefix_search_node_update_imp.hpp>
235 #undef PB_DS_CLASS_C_DEC
237 #define PB_DS_CLASS_C_DEC \
238 trie_order_statistics_node_update<Const_Node_Iterator, Node_Iterator,E_Access_Traits, Allocator>
241 template<
typename Const_Node_Iterator,
242 typename Node_Iterator,
243 typename E_Access_Traits,
245 class trie_order_statistics_node_update :
private PB_DS_BASE_C_DEC
248 typedef PB_DS_BASE_C_DEC base_type;
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;
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;
268 inline const_iterator
269 find_by_order(size_type)
const;
276 find_by_order(size_type);
284 order_of_key(const_key_reference)
const;
292 order_of_prefix(const_e_iterator, const_e_iterator)
const;
295 typedef typename base_type::const_reference const_reference;
296 typedef typename base_type::const_pointer const_pointer;
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;
316 virtual const_node_iterator
317 node_begin()
const = 0;
320 virtual node_iterator
325 virtual const_node_iterator
326 node_end()
const = 0;
329 virtual node_iterator
333 virtual e_access_traits&
334 get_e_access_traits() = 0;
340 operator()(node_iterator, const_node_iterator)
const;
344 ~trie_order_statistics_node_update();
347 #include <ext/pb_ds/detail/trie_policy/order_statistics_imp.hpp>
349 #undef PB_DS_CLASS_T_DEC
350 #undef PB_DS_CLASS_C_DEC
351 #undef PB_DS_BASE_C_DEC
The "standard" allocator, as per [20.4].Further details: http://gcc.gnu.org/onlinedocs/libstdc++/manu...
pair holds two objects of arbitrary type.
GNU extensions for policy-based data structures for public use.