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
00048 #ifndef PB_DS_TAG_AND_TRAIT_HPP
00049 #define PB_DS_TAG_AND_TRAIT_HPP
00050
00051 #include <ext/pb_ds/detail/type_utils.hpp>
00052
00053 namespace pb_ds
00054 {
00055
00056
00057 struct trivial_iterator_tag
00058 { };
00059
00060
00061 typedef void trivial_iterator_difference_type;
00062
00063
00064
00065
00066
00067 struct basic_invalidation_guarantee
00068 { };
00069
00070
00071
00072
00073
00074
00075 struct point_invalidation_guarantee : public basic_invalidation_guarantee
00076 { };
00077
00078
00079
00080
00081
00082
00083
00084 struct range_invalidation_guarantee : public point_invalidation_guarantee
00085 { };
00086
00087
00088
00089
00090 struct null_mapped_type { };
00091
00092
00093
00094 struct container_tag
00095 { };
00096
00097
00098 struct associative_container_tag : public container_tag { };
00099
00100
00101 struct basic_hash_tag : public associative_container_tag { };
00102
00103
00104 struct cc_hash_tag : public basic_hash_tag { };
00105
00106
00107 struct gp_hash_tag : public basic_hash_tag { };
00108
00109
00110 struct basic_tree_tag : public associative_container_tag { };
00111
00112
00113 struct tree_tag : public basic_tree_tag { };
00114
00115
00116 struct rb_tree_tag : public tree_tag { };
00117
00118
00119 struct splay_tree_tag : public tree_tag { };
00120
00121
00122 struct ov_tree_tag : public tree_tag { };
00123
00124
00125 struct trie_tag : public basic_tree_tag { };
00126
00127
00128 struct pat_trie_tag : public trie_tag { };
00129
00130
00131 struct list_update_tag : public associative_container_tag { };
00132
00133
00134 struct priority_queue_tag : public container_tag { };
00135
00136
00137 struct pairing_heap_tag : public priority_queue_tag { };
00138
00139
00140 struct binomial_heap_tag : public priority_queue_tag { };
00141
00142
00143 struct rc_binomial_heap_tag : public priority_queue_tag { };
00144
00145
00146 struct binary_heap_tag : public priority_queue_tag { };
00147
00148
00149 struct thin_heap_tag : public priority_queue_tag { };
00150
00151
00152 template<typename Tag>
00153 struct container_traits_base;
00154
00155 template<>
00156 struct container_traits_base<cc_hash_tag>
00157 {
00158 typedef cc_hash_tag container_category;
00159 typedef point_invalidation_guarantee invalidation_guarantee;
00160
00161 enum
00162 {
00163 order_preserving = false,
00164 erase_can_throw = false,
00165 split_join_can_throw = false,
00166 reverse_iteration = false
00167 };
00168 };
00169
00170 template<>
00171 struct container_traits_base<gp_hash_tag>
00172 {
00173 typedef gp_hash_tag container_category;
00174 typedef basic_invalidation_guarantee invalidation_guarantee;
00175
00176 enum
00177 {
00178 order_preserving = false,
00179 erase_can_throw = false,
00180 split_join_can_throw = false,
00181 reverse_iteration = false
00182 };
00183 };
00184
00185 template<>
00186 struct container_traits_base<rb_tree_tag>
00187 {
00188 typedef rb_tree_tag container_category;
00189 typedef range_invalidation_guarantee invalidation_guarantee;
00190
00191 enum
00192 {
00193 order_preserving = true,
00194 erase_can_throw = false,
00195 split_join_can_throw = false,
00196 reverse_iteration = true
00197 };
00198 };
00199
00200 template<>
00201 struct container_traits_base<splay_tree_tag>
00202 {
00203 typedef splay_tree_tag container_category;
00204 typedef range_invalidation_guarantee invalidation_guarantee;
00205
00206 enum
00207 {
00208 order_preserving = true,
00209 erase_can_throw = false,
00210 split_join_can_throw = false,
00211 reverse_iteration = true
00212 };
00213 };
00214
00215 template<>
00216 struct container_traits_base<ov_tree_tag>
00217 {
00218 typedef ov_tree_tag container_category;
00219 typedef basic_invalidation_guarantee invalidation_guarantee;
00220
00221 enum
00222 {
00223 order_preserving = true,
00224 erase_can_throw = true,
00225 split_join_can_throw = true,
00226 reverse_iteration = false
00227 };
00228 };
00229
00230 template<>
00231 struct container_traits_base<pat_trie_tag>
00232 {
00233 typedef pat_trie_tag container_category;
00234 typedef range_invalidation_guarantee invalidation_guarantee;
00235
00236 enum
00237 {
00238 order_preserving = true,
00239 erase_can_throw = false,
00240 split_join_can_throw = true,
00241 reverse_iteration = true
00242 };
00243 };
00244
00245 template<>
00246 struct container_traits_base<list_update_tag>
00247 {
00248 typedef list_update_tag container_category;
00249 typedef point_invalidation_guarantee invalidation_guarantee;
00250
00251 enum
00252 {
00253 order_preserving = false,
00254 erase_can_throw = false,
00255 split_join_can_throw = false,
00256 reverse_iteration = false
00257 };
00258 };
00259
00260
00261 template<>
00262 struct container_traits_base<pairing_heap_tag>
00263 {
00264 typedef pairing_heap_tag container_category;
00265 typedef point_invalidation_guarantee invalidation_guarantee;
00266
00267 enum
00268 {
00269 order_preserving = false,
00270 erase_can_throw = false,
00271 split_join_can_throw = false,
00272 reverse_iteration = false
00273 };
00274 };
00275
00276 template<>
00277 struct container_traits_base<thin_heap_tag>
00278 {
00279 typedef thin_heap_tag container_category;
00280 typedef point_invalidation_guarantee invalidation_guarantee;
00281
00282 enum
00283 {
00284 order_preserving = false,
00285 erase_can_throw = false,
00286 split_join_can_throw = false,
00287 reverse_iteration = false
00288 };
00289 };
00290
00291 template<>
00292 struct container_traits_base<binomial_heap_tag>
00293 {
00294 typedef binomial_heap_tag container_category;
00295 typedef point_invalidation_guarantee invalidation_guarantee;
00296
00297 enum
00298 {
00299 order_preserving = false,
00300 erase_can_throw = false,
00301 split_join_can_throw = false,
00302 reverse_iteration = false
00303 };
00304 };
00305
00306 template<>
00307 struct container_traits_base<rc_binomial_heap_tag>
00308 {
00309 typedef rc_binomial_heap_tag container_category;
00310 typedef point_invalidation_guarantee invalidation_guarantee;
00311
00312 enum
00313 {
00314 order_preserving = false,
00315 erase_can_throw = false,
00316 split_join_can_throw = false,
00317 reverse_iteration = false
00318 };
00319 };
00320
00321 template<>
00322 struct container_traits_base<binary_heap_tag>
00323 {
00324 typedef binary_heap_tag container_category;
00325 typedef basic_invalidation_guarantee invalidation_guarantee;
00326
00327 enum
00328 {
00329 order_preserving = false,
00330 erase_can_throw = false,
00331 split_join_can_throw = true,
00332 reverse_iteration = false
00333 };
00334 };
00335
00336
00337
00338 template<typename Cntnr>
00339 struct container_traits
00340 : public container_traits_base<typename Cntnr::container_category>
00341 {
00342 typedef Cntnr container_type;
00343 typedef typename Cntnr::container_category container_category;
00344 typedef container_traits_base<container_category> base_type;
00345 typedef typename base_type::invalidation_guarantee invalidation_guarantee;
00346
00347 enum
00348 {
00349 order_preserving = base_type::order_preserving,
00350 erase_can_throw = base_type::erase_can_throw,
00351 split_join_can_throw = base_type::split_join_can_throw,
00352 reverse_iteration = base_type::reverse_iteration
00353 };
00354 };
00355 }
00356
00357 #endif