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