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