libstdc++
|
00001 // -*- C++ -*- 00002 00003 // Copyright (C) 2005, 2006, 2008, 2009, 2010 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 <bits/c++config.h> 00046 #include <ext/pb_ds/detail/type_utils.hpp> 00047 00048 /** 00049 * @namespace __gnu_pbds 00050 * @brief GNU extensions for policy-based data structures for public use. 00051 */ 00052 namespace __gnu_pbds 00053 { 00054 // A trivial iterator tag. Signifies that the iterators has none of 00055 // the STL's movement abilities. 00056 struct trivial_iterator_tag 00057 { }; 00058 00059 // Prohibit moving trivial iterators. 00060 typedef void trivial_iterator_difference_type; 00061 00062 00063 // Signifies a basic invalidation guarantee that any iterator, 00064 // pointer, or reference to a container object's mapped value type 00065 // is valid as long as the container is not modified. 00066 struct basic_invalidation_guarantee 00067 { }; 00068 00069 // Signifies an invalidation guarantee that includes all those of 00070 // its base, and additionally, that any point-type iterator, 00071 // pointer, or reference to a container object's mapped value type 00072 // is valid as long as its corresponding entry has not be erased, 00073 // regardless of modifications to the container object. 00074 struct point_invalidation_guarantee : public basic_invalidation_guarantee 00075 { }; 00076 00077 // Signifies an invalidation guarantee that includes all those of 00078 // its base, and additionally, that any range-type iterator 00079 // (including the returns of begin() and end()) is in the correct 00080 // relative positions to other range-type iterators as long as its 00081 // corresponding entry has not be erased, regardless of 00082 // modifications to the container object. 00083 struct range_invalidation_guarantee : public point_invalidation_guarantee 00084 { }; 00085 00086 00087 /// A mapped-policy indicating that an associative container is a set. 00088 // XXX should this be a trait of the form is_set<T> ?? 00089 struct null_mapped_type { }; 00090 00091 00092 /// Base data structure tag. 00093 struct container_tag 00094 { }; 00095 00096 /// Basic string container, inclusive of strings, ropes, etc. 00097 struct string_tag : public container_tag { }; 00098 00099 /// Basic sequence. 00100 struct sequence_tag : public container_tag { }; 00101 00102 /// Basic associative-container. 00103 struct associative_container_tag : public container_tag { }; 00104 00105 /// Basic hash. 00106 struct basic_hash_tag : public associative_container_tag { }; 00107 00108 /// Collision-chaining hash. 00109 struct cc_hash_tag : public basic_hash_tag { }; 00110 00111 /// General-probing hash. 00112 struct gp_hash_tag : public basic_hash_tag { }; 00113 00114 /// Basic tree. 00115 struct basic_tree_tag : public associative_container_tag { }; 00116 00117 /// tree. 00118 struct tree_tag : public basic_tree_tag { }; 00119 00120 /// Red-black tree. 00121 struct rb_tree_tag : public tree_tag { }; 00122 00123 /// Splay tree. 00124 struct splay_tree_tag : public tree_tag { }; 00125 00126 /// Ordered-vector tree. 00127 struct ov_tree_tag : public tree_tag { }; 00128 00129 /// trie. 00130 struct trie_tag : public basic_tree_tag { }; 00131 00132 /// PATRICIA trie. 00133 struct pat_trie_tag : public trie_tag { }; 00134 00135 /// List-update. 00136 struct list_update_tag : public associative_container_tag { }; 00137 00138 /// Basic priority-queue. 00139 struct priority_queue_tag : public container_tag { }; 00140 00141 /// Pairing-heap. 00142 struct pairing_heap_tag : public priority_queue_tag { }; 00143 00144 /// Binomial-heap. 00145 struct binomial_heap_tag : public priority_queue_tag { }; 00146 00147 /// Redundant-counter binomial-heap. 00148 struct rc_binomial_heap_tag : public priority_queue_tag { }; 00149 00150 /// Binary-heap (array-based). 00151 struct binary_heap_tag : public priority_queue_tag { }; 00152 00153 /// Thin heap. 00154 struct thin_heap_tag : public priority_queue_tag { }; 00155 00156 00157 /// Base traits type for containers. 00158 template<typename Tag> 00159 struct container_traits_base; 00160 00161 template<> 00162 struct container_traits_base<cc_hash_tag> 00163 { 00164 typedef cc_hash_tag container_category; 00165 typedef point_invalidation_guarantee invalidation_guarantee; 00166 00167 enum 00168 { 00169 order_preserving = false, 00170 erase_can_throw = false, 00171 split_join_can_throw = false, 00172 reverse_iteration = false 00173 }; 00174 }; 00175 00176 template<> 00177 struct container_traits_base<gp_hash_tag> 00178 { 00179 typedef gp_hash_tag container_category; 00180 typedef basic_invalidation_guarantee invalidation_guarantee; 00181 00182 enum 00183 { 00184 order_preserving = false, 00185 erase_can_throw = false, 00186 split_join_can_throw = false, 00187 reverse_iteration = false 00188 }; 00189 }; 00190 00191 template<> 00192 struct container_traits_base<rb_tree_tag> 00193 { 00194 typedef rb_tree_tag container_category; 00195 typedef range_invalidation_guarantee invalidation_guarantee; 00196 00197 enum 00198 { 00199 order_preserving = true, 00200 erase_can_throw = false, 00201 split_join_can_throw = false, 00202 reverse_iteration = true 00203 }; 00204 }; 00205 00206 template<> 00207 struct container_traits_base<splay_tree_tag> 00208 { 00209 typedef splay_tree_tag container_category; 00210 typedef range_invalidation_guarantee invalidation_guarantee; 00211 00212 enum 00213 { 00214 order_preserving = true, 00215 erase_can_throw = false, 00216 split_join_can_throw = false, 00217 reverse_iteration = true 00218 }; 00219 }; 00220 00221 template<> 00222 struct container_traits_base<ov_tree_tag> 00223 { 00224 typedef ov_tree_tag container_category; 00225 typedef basic_invalidation_guarantee invalidation_guarantee; 00226 00227 enum 00228 { 00229 order_preserving = true, 00230 erase_can_throw = true, 00231 split_join_can_throw = true, 00232 reverse_iteration = false 00233 }; 00234 }; 00235 00236 template<> 00237 struct container_traits_base<pat_trie_tag> 00238 { 00239 typedef pat_trie_tag container_category; 00240 typedef range_invalidation_guarantee invalidation_guarantee; 00241 00242 enum 00243 { 00244 order_preserving = true, 00245 erase_can_throw = false, 00246 split_join_can_throw = true, 00247 reverse_iteration = true 00248 }; 00249 }; 00250 00251 template<> 00252 struct container_traits_base<list_update_tag> 00253 { 00254 typedef list_update_tag container_category; 00255 typedef point_invalidation_guarantee invalidation_guarantee; 00256 00257 enum 00258 { 00259 order_preserving = false, 00260 erase_can_throw = false, 00261 split_join_can_throw = false, 00262 reverse_iteration = false 00263 }; 00264 }; 00265 00266 00267 template<> 00268 struct container_traits_base<pairing_heap_tag> 00269 { 00270 typedef pairing_heap_tag container_category; 00271 typedef point_invalidation_guarantee invalidation_guarantee; 00272 00273 enum 00274 { 00275 order_preserving = false, 00276 erase_can_throw = false, 00277 split_join_can_throw = false, 00278 reverse_iteration = false 00279 }; 00280 }; 00281 00282 template<> 00283 struct container_traits_base<thin_heap_tag> 00284 { 00285 typedef thin_heap_tag container_category; 00286 typedef point_invalidation_guarantee invalidation_guarantee; 00287 00288 enum 00289 { 00290 order_preserving = false, 00291 erase_can_throw = false, 00292 split_join_can_throw = false, 00293 reverse_iteration = false 00294 }; 00295 }; 00296 00297 template<> 00298 struct container_traits_base<binomial_heap_tag> 00299 { 00300 typedef binomial_heap_tag container_category; 00301 typedef point_invalidation_guarantee invalidation_guarantee; 00302 00303 enum 00304 { 00305 order_preserving = false, 00306 erase_can_throw = false, 00307 split_join_can_throw = false, 00308 reverse_iteration = false 00309 }; 00310 }; 00311 00312 template<> 00313 struct container_traits_base<rc_binomial_heap_tag> 00314 { 00315 typedef rc_binomial_heap_tag container_category; 00316 typedef point_invalidation_guarantee invalidation_guarantee; 00317 00318 enum 00319 { 00320 order_preserving = false, 00321 erase_can_throw = false, 00322 split_join_can_throw = false, 00323 reverse_iteration = false 00324 }; 00325 }; 00326 00327 template<> 00328 struct container_traits_base<binary_heap_tag> 00329 { 00330 typedef binary_heap_tag container_category; 00331 typedef basic_invalidation_guarantee invalidation_guarantee; 00332 00333 enum 00334 { 00335 order_preserving = false, 00336 erase_can_throw = false, 00337 split_join_can_throw = true, 00338 reverse_iteration = false 00339 }; 00340 }; 00341 00342 00343 /// container_traits 00344 // See Matt Austern for the name, S. Meyers MEFC++ #2, others. 00345 template<typename Cntnr> 00346 struct container_traits 00347 : public container_traits_base<typename Cntnr::container_category> 00348 { 00349 typedef Cntnr container_type; 00350 typedef typename Cntnr::container_category container_category; 00351 typedef container_traits_base<container_category> base_type; 00352 typedef typename base_type::invalidation_guarantee invalidation_guarantee; 00353 00354 enum 00355 { 00356 order_preserving = base_type::order_preserving, 00357 erase_can_throw = base_type::erase_can_throw, 00358 split_join_can_throw = base_type::split_join_can_throw, 00359 reverse_iteration = base_type::reverse_iteration 00360 }; 00361 }; 00362 } // namespace __gnu_pbds 00363 00364 #endif