41 #ifndef PB_DS_TRIE_POLICY_HPP 42 #define PB_DS_TRIE_POLICY_HPP 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, \ 56 #define PB_DS_CLASS_C_DEC \ 57 trie_string_access_traits<String, Min_E_Val,Max_E_Val,Reverse,_Alloc> 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,
77 typedef typename _Alloc::size_type size_type;
78 typedef String key_type;
79 typedef typename _Alloc::template rebind<key_type> __rebind_k;
80 typedef typename __rebind_k::other::const_reference key_const_reference;
88 typedef typename detail::__conditional_type<Reverse, \
89 typename String::const_reverse_iterator, \
93 typedef typename std::iterator_traits<const_iterator>::value_type
e_type;
97 min_e_val = Min_E_Val,
98 max_e_val = Max_E_Val,
99 max_size = max_e_val - min_e_val + 1
101 PB_DS_STATIC_ASSERT(min_max_size, max_size >= 2);
105 inline static const_iterator
106 begin(key_const_reference);
110 inline static const_iterator
111 end(key_const_reference);
114 inline static size_type
118 inline static const_iterator
119 begin_imp(key_const_reference, detail::false_type);
121 inline static const_iterator
122 begin_imp(key_const_reference, detail::true_type);
124 inline static const_iterator
125 end_imp(key_const_reference, detail::false_type);
127 inline static const_iterator
128 end_imp(key_const_reference, detail::true_type);
130 static detail::integral_constant<int, Reverse> s_rev_ind;
135 #undef PB_DS_CLASS_T_DEC 136 #undef PB_DS_CLASS_C_DEC 138 #define PB_DS_CLASS_T_DEC \ 139 template<typename Node_CItr,typename Node_Itr, \ 140 typename _ATraits, typename _Alloc> 142 #define PB_DS_CLASS_C_DEC \ 143 trie_prefix_search_node_update<Node_CItr, Node_Itr, \ 146 #define PB_DS_TRIE_POLICY_BASE \ 147 detail::trie_policy_base<Node_CItr,Node_Itr,_ATraits, _Alloc> 151 template<
typename Node_CItr,
158 typedef PB_DS_TRIE_POLICY_BASE
base_type;
161 typedef typename base_type::key_type key_type;
162 typedef typename base_type::key_const_reference key_const_reference;
176 typedef Node_Itr node_iterator;
177 typedef Node_CItr node_const_iterator;
178 typedef typename node_iterator::value_type iterator;
184 prefix_range(key_const_reference)
const;
189 prefix_range(key_const_reference);
194 prefix_range(a_const_iterator, a_const_iterator)
const;
199 prefix_range(a_const_iterator, a_const_iterator);
204 operator()(node_iterator node_it, node_const_iterator end_nd_it)
const;
208 next_child(node_iterator, a_const_iterator, a_const_iterator,
209 node_iterator,
const access_traits&);
212 virtual const_iterator
220 virtual node_const_iterator
221 node_begin()
const = 0;
224 virtual node_iterator
228 virtual node_const_iterator
229 node_end()
const = 0;
232 virtual node_iterator
236 virtual const access_traits&
237 get_access_traits()
const = 0;
242 #undef PB_DS_CLASS_C_DEC 244 #define PB_DS_CLASS_C_DEC \ 245 trie_order_statistics_node_update<Node_CItr, Node_Itr, \ 249 template<
typename Node_CItr,
256 typedef PB_DS_TRIE_POLICY_BASE
base_type;
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;
266 typedef size_type metadata_type;
267 typedef Node_CItr node_const_iterator;
268 typedef Node_Itr node_iterator;
270 typedef typename node_iterator::value_type iterator;
276 inline const_iterator
277 find_by_order(size_type)
const;
284 find_by_order(size_type);
292 order_of_key(key_const_reference)
const;
300 order_of_prefix(a_const_iterator, a_const_iterator)
const;
306 operator()(node_iterator, node_const_iterator)
const;
309 typedef typename base_type::const_reference const_reference;
310 typedef typename base_type::const_pointer const_pointer;
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;
318 _GLIBCXX_NODISCARD
virtual bool 331 virtual node_const_iterator
332 node_begin()
const = 0;
335 virtual node_iterator
340 virtual node_const_iterator
341 node_end()
const = 0;
344 virtual node_iterator
348 virtual access_traits&
349 get_access_traits() = 0;
354 #undef PB_DS_CLASS_T_DEC 355 #undef PB_DS_CLASS_C_DEC 356 #undef PB_DS_TRIE_POLICY_BASE Base class for trie policies.
GNU extensions for policy-based data structures for public use.
Functor updating ranks of entrees.
Represents no type, or absence of type, for template tricks.
Struct holding two objects of arbitrary type.
The standard allocator, as per [20.4].
_GLIBCXX_END_NAMESPACE_CXX11 typedef basic_string< char > string
A string of char.
_Alloc allocator_type
_Alloc type.
std::iterator_traits< const_iterator >::value_type e_type
Element type.
static const_iterator begin(key_const_reference)
Returns a const_iterator to the first element of key_const_reference agumnet.
_ATraits access_traits
Element access traits.
static const_iterator end(key_const_reference)
Returns a const_iterator to the after-last element of key_const_reference argument.
static size_type e_pos(e_type e)
Maps an element to a position.
detail::__conditional_type< Reverse, typename String::const_reverse_iterator, typename String::const_iterator >::__type const_iterator
Element const iterator type.
access_traits::const_iterator a_const_iterator
Const element iterator.
A node updator that allows tries to be searched for the range of values that match a certain prefix...
allocator_type::size_type size_type
Size type.