00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040
00041 #ifndef PB_DS_TRIE_POLICY_HPP
00042 #define PB_DS_TRIE_POLICY_HPP
00043
00044 #include <string>
00045 #include <ext/pb_ds/detail/type_utils.hpp>
00046 #include <ext/pb_ds/detail/trie_policy/trie_policy_base.hpp>
00047
00048 namespace __gnu_pbds
00049 {
00050
00051 template<typename Const_Node_Iterator,
00052 typename Node_Iterator,
00053 typename E_Access_Traits,
00054 typename Allocator>
00055 struct null_trie_node_update
00056 { };
00057
00058 #define PB_DS_CLASS_T_DEC \
00059 template<typename String, typename String::value_type Min_E_Val, typename String::value_type Max_E_Val, bool Reverse, typename Allocator>
00060
00061 #define PB_DS_CLASS_C_DEC \
00062 string_trie_e_access_traits<String, Min_E_Val,Max_E_Val,Reverse,Allocator>
00063
00064
00065 template<typename String = std::string,
00066 typename String::value_type Min_E_Val = detail::__numeric_traits<typename String::value_type>::__min,
00067 typename String::value_type Max_E_Val = detail::__numeric_traits<typename String::value_type>::__max,
00068 bool Reverse = false,
00069 typename Allocator = std::allocator<char> >
00070 struct string_trie_e_access_traits
00071 {
00072 public:
00073 typedef typename Allocator::size_type size_type;
00074 typedef String key_type;
00075 typedef typename Allocator::template rebind<key_type>::other key_rebind;
00076 typedef typename key_rebind::const_reference const_key_reference;
00077
00078 enum
00079 {
00080 reverse = Reverse
00081 };
00082
00083
00084 typedef typename detail::__conditional_type<Reverse, typename String::const_reverse_iterator, typename String::const_iterator>::__type const_iterator;
00085
00086
00087 typedef typename std::iterator_traits<const_iterator>::value_type e_type;
00088
00089 enum
00090 {
00091 min_e_val = Min_E_Val,
00092 max_e_val = Max_E_Val,
00093 max_size = max_e_val - min_e_val + 1
00094 };
00095 PB_DS_STATIC_ASSERT(min_max_size, max_size >= 2);
00096
00097
00098
00099 inline static const_iterator
00100 begin(const_key_reference);
00101
00102
00103
00104 inline static const_iterator
00105 end(const_key_reference);
00106
00107
00108 inline static size_type
00109 e_pos(e_type e);
00110
00111 private:
00112
00113 inline static const_iterator
00114 begin_imp(const_key_reference, detail::false_type);
00115
00116 inline static const_iterator
00117 begin_imp(const_key_reference, detail::true_type);
00118
00119 inline static const_iterator
00120 end_imp(const_key_reference, detail::false_type);
00121
00122 inline static const_iterator
00123 end_imp(const_key_reference, detail::true_type);
00124
00125 static detail::integral_constant<int, Reverse> s_rev_ind;
00126 };
00127
00128 #include <ext/pb_ds/detail/trie_policy/string_trie_e_access_traits_imp.hpp>
00129
00130 #undef PB_DS_CLASS_T_DEC
00131 #undef PB_DS_CLASS_C_DEC
00132
00133 #define PB_DS_CLASS_T_DEC \
00134 template<typename Const_Node_Iterator,typename Node_Iterator,class E_Access_Traits, typename Allocator>
00135
00136 #define PB_DS_CLASS_C_DEC \
00137 trie_prefix_search_node_update<Const_Node_Iterator, Node_Iterator, E_Access_Traits,Allocator>
00138
00139 #define PB_DS_BASE_C_DEC \
00140 detail::trie_policy_base<Const_Node_Iterator,Node_Iterator,E_Access_Traits, Allocator>
00141
00142
00143
00144 template<typename Const_Node_Iterator,
00145 typename Node_Iterator,
00146 typename E_Access_Traits,
00147 typename Allocator>
00148 class trie_prefix_search_node_update : private PB_DS_BASE_C_DEC
00149 {
00150 private:
00151 typedef PB_DS_BASE_C_DEC base_type;
00152
00153 public:
00154 typedef typename base_type::key_type key_type;
00155 typedef typename base_type::const_key_reference const_key_reference;
00156
00157
00158 typedef E_Access_Traits e_access_traits;
00159
00160
00161 typedef typename e_access_traits::const_iterator const_e_iterator;
00162
00163
00164 typedef Allocator allocator_type;
00165
00166
00167 typedef typename allocator_type::size_type size_type;
00168 typedef detail::null_node_metadata metadata_type;
00169 typedef Const_Node_Iterator const_node_iterator;
00170 typedef Node_Iterator node_iterator;
00171 typedef typename const_node_iterator::value_type const_iterator;
00172 typedef typename node_iterator::value_type iterator;
00173
00174
00175
00176 std::pair<const_iterator, const_iterator>
00177 prefix_range(const_key_reference) const;
00178
00179
00180
00181 std::pair<iterator, iterator>
00182 prefix_range(const_key_reference);
00183
00184
00185
00186 std::pair<const_iterator, const_iterator>
00187 prefix_range(const_e_iterator, const_e_iterator) const;
00188
00189
00190
00191 std::pair<iterator, iterator>
00192 prefix_range(const_e_iterator, const_e_iterator);
00193
00194 protected:
00195
00196 inline void
00197 operator()(node_iterator node_it, const_node_iterator end_nd_it) const;
00198
00199 private:
00200
00201 virtual const_iterator
00202 end() const = 0;
00203
00204
00205 virtual iterator
00206 end() = 0;
00207
00208
00209 virtual const_node_iterator
00210 node_begin() const = 0;
00211
00212
00213 virtual node_iterator
00214 node_begin() = 0;
00215
00216
00217 virtual const_node_iterator
00218 node_end() const = 0;
00219
00220
00221 virtual node_iterator
00222 node_end() = 0;
00223
00224
00225 virtual const e_access_traits&
00226 get_e_access_traits() const = 0;
00227
00228 node_iterator
00229 next_child(node_iterator, const_e_iterator, const_e_iterator,
00230 node_iterator, const e_access_traits&);
00231 };
00232
00233 #include <ext/pb_ds/detail/trie_policy/prefix_search_node_update_imp.hpp>
00234
00235 #undef PB_DS_CLASS_C_DEC
00236
00237 #define PB_DS_CLASS_C_DEC \
00238 trie_order_statistics_node_update<Const_Node_Iterator, Node_Iterator,E_Access_Traits, Allocator>
00239
00240
00241 template<typename Const_Node_Iterator,
00242 typename Node_Iterator,
00243 typename E_Access_Traits,
00244 typename Allocator>
00245 class trie_order_statistics_node_update : private PB_DS_BASE_C_DEC
00246 {
00247 private:
00248 typedef PB_DS_BASE_C_DEC base_type;
00249
00250 public:
00251 typedef E_Access_Traits e_access_traits;
00252 typedef typename e_access_traits::const_iterator const_e_iterator;
00253 typedef Allocator allocator_type;
00254 typedef typename allocator_type::size_type size_type;
00255 typedef typename base_type::key_type key_type;
00256 typedef typename base_type::const_key_reference const_key_reference;
00257
00258 typedef size_type metadata_type;
00259 typedef Const_Node_Iterator const_node_iterator;
00260 typedef Node_Iterator node_iterator;
00261 typedef typename const_node_iterator::value_type const_iterator;
00262 typedef typename node_iterator::value_type iterator;
00263
00264
00265
00266
00267
00268 inline const_iterator
00269 find_by_order(size_type) const;
00270
00271
00272
00273
00274
00275 inline iterator
00276 find_by_order(size_type);
00277
00278
00279
00280
00281
00282
00283 inline size_type
00284 order_of_key(const_key_reference) const;
00285
00286
00287
00288
00289
00290
00291 inline size_type
00292 order_of_prefix(const_e_iterator, const_e_iterator) const;
00293
00294 private:
00295 typedef typename base_type::const_reference const_reference;
00296 typedef typename base_type::const_pointer const_pointer;
00297
00298 typedef typename Allocator::template rebind<metadata_type>::other metadata_rebind;
00299 typedef typename metadata_rebind::const_reference const_metadata_reference;
00300 typedef typename metadata_rebind::reference metadata_reference;
00301
00302
00303 virtual bool
00304 empty() const = 0;
00305
00306
00307 virtual iterator
00308 begin() = 0;
00309
00310
00311
00312 virtual iterator
00313 end() = 0;
00314
00315
00316 virtual const_node_iterator
00317 node_begin() const = 0;
00318
00319
00320 virtual node_iterator
00321 node_begin() = 0;
00322
00323
00324
00325 virtual const_node_iterator
00326 node_end() const = 0;
00327
00328
00329 virtual node_iterator
00330 node_end() = 0;
00331
00332
00333 virtual e_access_traits&
00334 get_e_access_traits() = 0;
00335
00336 protected:
00337
00338
00339 inline void
00340 operator()(node_iterator, const_node_iterator) const;
00341
00342
00343 virtual
00344 ~trie_order_statistics_node_update();
00345 };
00346
00347 #include <ext/pb_ds/detail/trie_policy/order_statistics_imp.hpp>
00348
00349 #undef PB_DS_CLASS_T_DEC
00350 #undef PB_DS_CLASS_C_DEC
00351 #undef PB_DS_BASE_C_DEC
00352
00353 }
00354
00355 #endif