libstdc++
|
00001 // -*- C++ -*- 00002 00003 // Copyright (C) 2005, 2006, 2008, 2009 Free Software Foundation, Inc. 00004 // 00005 // This file is part of the GNU ISO C++ Library. This library is free 00006 // software; you can redistribute it and/or modify it under the terms 00007 // of the GNU General Public License as published by the Free Software 00008 // Foundation; either version 3, or (at your option) any later 00009 // version. 00010 00011 // This library is distributed in the hope that it will be useful, but 00012 // WITHOUT ANY WARRANTY; without even the implied warranty of 00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 00014 // General Public License for more details. 00015 00016 // Under Section 7 of GPL version 3, you are granted additional 00017 // permissions described in the GCC Runtime Library Exception, version 00018 // 3.1, as published by the Free Software Foundation. 00019 00020 // You should have received a copy of the GNU General Public License and 00021 // a copy of the GCC Runtime Library Exception along with this program; 00022 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 00023 // <http://www.gnu.org/licenses/>. 00024 00025 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 00026 00027 // Permission to use, copy, modify, sell, and distribute this software 00028 // is hereby granted without fee, provided that the above copyright 00029 // notice appears in all copies, and that both that copyright notice 00030 // and this permission notice appear in supporting documentation. None 00031 // of the above authors, nor IBM Haifa Research Laboratories, make any 00032 // representation about the suitability of this software for any 00033 // purpose. It is provided "as is" without express or implied 00034 // warranty. 00035 00036 /** 00037 * @file tag_and_trait.hpp 00038 * Contains tags and traits, e.g., ones describing underlying 00039 * data structures. 00040 */ 00041 00042 #ifndef PB_DS_TAG_AND_TRAIT_HPP 00043 #define PB_DS_TAG_AND_TRAIT_HPP 00044 00045 #include <ext/pb_ds/detail/type_utils.hpp> 00046 00047 /** 00048 * @namespace __gnu_pbds 00049 * @brief GNU extensions for policy-based data structures for public use. 00050 */ 00051 namespace __gnu_pbds 00052 { 00053 // A trivial iterator tag. Signifies that the iterators has none of 00054 // the STL's movement abilities. 00055 struct trivial_iterator_tag 00056 { }; 00057 00058 // Prohibit moving trivial iterators. 00059 typedef void trivial_iterator_difference_type; 00060 00061 00062 // Signifies a basic invalidation guarantee that any iterator, 00063 // pointer, or reference to a container object's mapped value type 00064 // is valid as long as the container is not modified. 00065 struct basic_invalidation_guarantee 00066 { }; 00067 00068 // Signifies an invalidation guarantee that includes all those of 00069 // its base, and additionally, that any point-type iterator, 00070 // pointer, or reference to a container object's mapped value type 00071 // is valid as long as its corresponding entry has not be erased, 00072 // regardless of modifications to the container object. 00073 struct point_invalidation_guarantee : public basic_invalidation_guarantee 00074 { }; 00075 00076 // Signifies an invalidation guarantee that includes all those of 00077 // its base, and additionally, that any range-type iterator 00078 // (including the returns of begin() and end()) is in the correct 00079 // relative positions to other range-type iterators as long as its 00080 // corresponding entry has not be erased, regardless of 00081 // modifications to the container object. 00082 struct range_invalidation_guarantee : public point_invalidation_guarantee 00083 { }; 00084 00085 00086 /// A mapped-policy indicating that an associative container is a set. 00087 // XXX should this be a trait of the form is_set<T> ?? 00088 struct null_mapped_type { }; 00089 00090 00091 /// Base data structure tag. 00092 struct container_tag 00093 { }; 00094 00095 /// Basic string container, inclusive of strings, ropes, etc. 00096 struct string_tag : public container_tag { }; 00097 00098 /// Basic sequence. 00099 struct sequence_tag : public container_tag { }; 00100 00101 /// Basic associative-container. 00102 struct associative_container_tag : public container_tag { }; 00103 00104 /// Basic hash. 00105 struct basic_hash_tag : public associative_container_tag { }; 00106 00107 /// Collision-chaining hash. 00108 struct cc_hash_tag : public basic_hash_tag { }; 00109 00110 /// General-probing hash. 00111 struct gp_hash_tag : public basic_hash_tag { }; 00112 00113 /// Basic tree. 00114 struct basic_tree_tag : public associative_container_tag { }; 00115 00116 /// tree. 00117 struct tree_tag : public basic_tree_tag { }; 00118 00119 /// Red-black tree. 00120 struct rb_tree_tag : public tree_tag { }; 00121 00122 /// Splay tree. 00123 struct splay_tree_tag : public tree_tag { }; 00124 00125 /// Ordered-vector tree. 00126 struct ov_tree_tag : public tree_tag { }; 00127 00128 /// trie. 00129 struct trie_tag : public basic_tree_tag { }; 00130 00131 /// PATRICIA trie. 00132 struct pat_trie_tag : public trie_tag { }; 00133 00134 /// List-update. 00135 struct list_update_tag : public associative_container_tag { }; 00136 00137 /// Basic priority-queue. 00138 struct priority_queue_tag : public container_tag { }; 00139 00140 /// Pairing-heap. 00141 struct pairing_heap_tag : public priority_queue_tag { }; 00142 00143 /// Binomial-heap. 00144 struct binomial_heap_tag : public priority_queue_tag { }; 00145 00146 /// Redundant-counter binomial-heap. 00147 struct rc_binomial_heap_tag : public priority_queue_tag { }; 00148 00149 /// Binary-heap (array-based). 00150 struct binary_heap_tag : public priority_queue_tag { }; 00151 00152 /// Thin heap. 00153 struct thin_heap_tag : public priority_queue_tag { }; 00154 00155 00156 /// Base traits type for containers. 00157 template<typename Tag> 00158 struct container_traits_base; 00159 00160 template<> 00161 struct container_traits_base<cc_hash_tag> 00162 { 00163 typedef cc_hash_tag container_category; 00164 typedef point_invalidation_guarantee invalidation_guarantee; 00165 00166 enum 00167 { 00168 order_preserving = false, 00169 erase_can_throw = false, 00170 split_join_can_throw = false, 00171 reverse_iteration = false 00172 }; 00173 }; 00174 00175 template<> 00176 struct container_traits_base<gp_hash_tag> 00177 { 00178 typedef gp_hash_tag container_category; 00179 typedef basic_invalidation_guarantee invalidation_guarantee; 00180 00181 enum 00182 { 00183 order_preserving = false, 00184 erase_can_throw = false, 00185 split_join_can_throw = false, 00186 reverse_iteration = false 00187 }; 00188 }; 00189 00190 template<> 00191 struct container_traits_base<rb_tree_tag> 00192 { 00193 typedef rb_tree_tag container_category; 00194 typedef range_invalidation_guarantee invalidation_guarantee; 00195 00196 enum 00197 { 00198 order_preserving = true, 00199 erase_can_throw = false, 00200 split_join_can_throw = false, 00201 reverse_iteration = true 00202 }; 00203 }; 00204 00205 template<> 00206 struct container_traits_base<splay_tree_tag> 00207 { 00208 typedef splay_tree_tag container_category; 00209 typedef range_invalidation_guarantee invalidation_guarantee; 00210 00211 enum 00212 { 00213 order_preserving = true, 00214 erase_can_throw = false, 00215 split_join_can_throw = false, 00216 reverse_iteration = true 00217 }; 00218 }; 00219 00220 template<> 00221 struct container_traits_base<ov_tree_tag> 00222 { 00223 typedef ov_tree_tag container_category; 00224 typedef basic_invalidation_guarantee invalidation_guarantee; 00225 00226 enum 00227 { 00228 order_preserving = true, 00229 erase_can_throw = true, 00230 split_join_can_throw = true, 00231 reverse_iteration = false 00232 }; 00233 }; 00234 00235 template<> 00236 struct container_traits_base<pat_trie_tag> 00237 { 00238 typedef pat_trie_tag container_category; 00239 typedef range_invalidation_guarantee invalidation_guarantee; 00240 00241 enum 00242 { 00243 order_preserving = true, 00244 erase_can_throw = false, 00245 split_join_can_throw = true, 00246 reverse_iteration = true 00247 }; 00248 }; 00249 00250 template<> 00251 struct container_traits_base<list_update_tag> 00252 { 00253 typedef list_update_tag container_category; 00254 typedef point_invalidation_guarantee invalidation_guarantee; 00255 00256 enum 00257 { 00258 order_preserving = false, 00259 erase_can_throw = false, 00260 split_join_can_throw = false, 00261 reverse_iteration = false 00262 }; 00263 }; 00264 00265 00266 template<> 00267 struct container_traits_base<pairing_heap_tag> 00268 { 00269 typedef pairing_heap_tag container_category; 00270 typedef point_invalidation_guarantee invalidation_guarantee; 00271 00272 enum 00273 { 00274 order_preserving = false, 00275 erase_can_throw = false, 00276 split_join_can_throw = false, 00277 reverse_iteration = false 00278 }; 00279 }; 00280 00281 template<> 00282 struct container_traits_base<thin_heap_tag> 00283 { 00284 typedef thin_heap_tag container_category; 00285 typedef point_invalidation_guarantee invalidation_guarantee; 00286 00287 enum 00288 { 00289 order_preserving = false, 00290 erase_can_throw = false, 00291 split_join_can_throw = false, 00292 reverse_iteration = false 00293 }; 00294 }; 00295 00296 template<> 00297 struct container_traits_base<binomial_heap_tag> 00298 { 00299 typedef binomial_heap_tag container_category; 00300 typedef point_invalidation_guarantee invalidation_guarantee; 00301 00302 enum 00303 { 00304 order_preserving = false, 00305 erase_can_throw = false, 00306 split_join_can_throw = false, 00307 reverse_iteration = false 00308 }; 00309 }; 00310 00311 template<> 00312 struct container_traits_base<rc_binomial_heap_tag> 00313 { 00314 typedef rc_binomial_heap_tag container_category; 00315 typedef point_invalidation_guarantee invalidation_guarantee; 00316 00317 enum 00318 { 00319 order_preserving = false, 00320 erase_can_throw = false, 00321 split_join_can_throw = false, 00322 reverse_iteration = false 00323 }; 00324 }; 00325 00326 template<> 00327 struct container_traits_base<binary_heap_tag> 00328 { 00329 typedef binary_heap_tag container_category; 00330 typedef basic_invalidation_guarantee invalidation_guarantee; 00331 00332 enum 00333 { 00334 order_preserving = false, 00335 erase_can_throw = false, 00336 split_join_can_throw = true, 00337 reverse_iteration = false 00338 }; 00339 }; 00340 00341 00342 /// container_traits 00343 // See Matt Austern for the name, S. Meyers MEFC++ #2, others. 00344 template<typename Cntnr> 00345 struct container_traits 00346 : public container_traits_base<typename Cntnr::container_category> 00347 { 00348 typedef Cntnr container_type; 00349 typedef typename Cntnr::container_category container_category; 00350 typedef container_traits_base<container_category> base_type; 00351 typedef typename base_type::invalidation_guarantee invalidation_guarantee; 00352 00353 enum 00354 { 00355 order_preserving = base_type::order_preserving, 00356 erase_can_throw = base_type::erase_can_throw, 00357 split_join_can_throw = base_type::split_join_can_throw, 00358 reverse_iteration = base_type::reverse_iteration 00359 }; 00360 }; 00361 } // namespace __gnu_pbds 00362 00363 #endif