1 // -*- C++ -*- 2 3 // Copyright (C) 2005, 2006, 2008, 2009 Free Software Foundation, Inc. 4 // 5 // This file is part of the GNU ISO C++ Library. This library is free 6 // software; you can redistribute it and/or modify it under the terms 7 // of the GNU General Public License as published by the Free Software 8 // Foundation; either version 3, or (at your option) any later 9 // version. 10 11 // This library is distributed in the hope that it will be useful, but 12 // WITHOUT ANY WARRANTY; without even the implied warranty of 13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 14 // General Public License for more details. 15 16 // Under Section 7 of GPL version 3, you are granted additional 17 // permissions described in the GCC Runtime Library Exception, version 18 // 3.1, as published by the Free Software Foundation. 19 20 // You should have received a copy of the GNU General Public License and 21 // a copy of the GCC Runtime Library Exception along with this program; 22 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 23 // <http://www.gnu.org/licenses/>. 24 25 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 26 27 // Permission to use, copy, modify, sell, and distribute this software 28 // is hereby granted without fee, provided that the above copyright 29 // notice appears in all copies, and that both that copyright notice 30 // and this permission notice appear in supporting documentation. None 31 // of the above authors, nor IBM Haifa Research Laboratories, make any 32 // representation about the suitability of this software for any 33 // purpose. It is provided "as is" without express or implied 34 // warranty. 35 36 /** 37 * @file tag_and_trait.hpp 38 * Contains tags and traits, e.g., ones describing underlying 39 * data structures. 40 */ 41 42 #ifndef PB_DS_TAG_AND_TRAIT_HPP 43 #define PB_DS_TAG_AND_TRAIT_HPP 44 45 #include <ext/pb_ds/detail/type_utils.hpp> 46 47 /** 48 * @namespace __gnu_pbds 49 * @brief GNU extensions for policy-based data structures for public use. 50 */ 51 namespace __gnu_pbds 52 { 53 // A trivial iterator tag. Signifies that the iterators has none of 54 // the STL's movement abilities. 55 struct trivial_iterator_tag 56 { }; 57 58 // Prohibit moving trivial iterators. 59 typedef void trivial_iterator_difference_type; 60 61 62 // Signifies a basic invalidation guarantee that any iterator, 63 // pointer, or reference to a container object's mapped value type 64 // is valid as long as the container is not modified. 65 struct basic_invalidation_guarantee 66 { }; 67 68 // Signifies an invalidation guarantee that includes all those of 69 // its base, and additionally, that any point-type iterator, 70 // pointer, or reference to a container object's mapped value type 71 // is valid as long as its corresponding entry has not be erased, 72 // regardless of modifications to the container object. 73 struct point_invalidation_guarantee : public basic_invalidation_guarantee 74 { }; 75 76 // Signifies an invalidation guarantee that includes all those of 77 // its base, and additionally, that any range-type iterator 78 // (including the returns of begin() and end()) is in the correct 79 // relative positions to other range-type iterators as long as its 80 // corresponding entry has not be erased, regardless of 81 // modifications to the container object. 82 struct range_invalidation_guarantee : public point_invalidation_guarantee 83 { }; 84 85 86 /// A mapped-policy indicating that an associative container is a set. 87 // XXX should this be a trait of the form is_set<T> ?? 88 struct null_mapped_type { }; 89 90 91 /// Base data structure tag. 92 struct container_tag 93 { }; 94 95 /// Basic string container, inclusive of strings, ropes, etc. 96 struct string_tag : public container_tag { }; 97 98 /// Basic sequence. 99 struct sequence_tag : public container_tag { }; 100 101 /// Basic associative-container. 102 struct associative_container_tag : public container_tag { }; 103 104 /// Basic hash. 105 struct basic_hash_tag : public associative_container_tag { }; 106 107 /// Collision-chaining hash. 108 struct cc_hash_tag : public basic_hash_tag { }; 109 110 /// General-probing hash. 111 struct gp_hash_tag : public basic_hash_tag { }; 112 113 /// Basic tree. 114 struct basic_tree_tag : public associative_container_tag { }; 115 116 /// tree. 117 struct tree_tag : public basic_tree_tag { }; 118 119 /// Red-black tree. 120 struct rb_tree_tag : public tree_tag { }; 121 122 /// Splay tree. 123 struct splay_tree_tag : public tree_tag { }; 124 125 /// Ordered-vector tree. 126 struct ov_tree_tag : public tree_tag { }; 127 128 /// trie. 129 struct trie_tag : public basic_tree_tag { }; 130 131 /// PATRICIA trie. 132 struct pat_trie_tag : public trie_tag { }; 133 134 /// List-update. 135 struct list_update_tag : public associative_container_tag { }; 136 137 /// Basic priority-queue. 138 struct priority_queue_tag : public container_tag { }; 139 140 /// Pairing-heap. 141 struct pairing_heap_tag : public priority_queue_tag { }; 142 143 /// Binomial-heap. 144 struct binomial_heap_tag : public priority_queue_tag { }; 145 146 /// Redundant-counter binomial-heap. 147 struct rc_binomial_heap_tag : public priority_queue_tag { }; 148 149 /// Binary-heap (array-based). 150 struct binary_heap_tag : public priority_queue_tag { }; 151 152 /// Thin heap. 153 struct thin_heap_tag : public priority_queue_tag { }; 154 155 156 /// Base traits type for containers. 157 template<typename Tag> 158 struct container_traits_base; 159 160 template<> 161 struct container_traits_base<cc_hash_tag> 162 { 163 typedef cc_hash_tag container_category; 164 typedef point_invalidation_guarantee invalidation_guarantee; 165 166 enum 167 { 168 order_preserving = false, 169 erase_can_throw = false, 170 split_join_can_throw = false, 171 reverse_iteration = false 172 }; 173 }; 174 175 template<> 176 struct container_traits_base<gp_hash_tag> 177 { 178 typedef gp_hash_tag container_category; 179 typedef basic_invalidation_guarantee invalidation_guarantee; 180 181 enum 182 { 183 order_preserving = false, 184 erase_can_throw = false, 185 split_join_can_throw = false, 186 reverse_iteration = false 187 }; 188 }; 189 190 template<> 191 struct container_traits_base<rb_tree_tag> 192 { 193 typedef rb_tree_tag container_category; 194 typedef range_invalidation_guarantee invalidation_guarantee; 195 196 enum 197 { 198 order_preserving = true, 199 erase_can_throw = false, 200 split_join_can_throw = false, 201 reverse_iteration = true 202 }; 203 }; 204 205 template<> 206 struct container_traits_base<splay_tree_tag> 207 { 208 typedef splay_tree_tag container_category; 209 typedef range_invalidation_guarantee invalidation_guarantee; 210 211 enum 212 { 213 order_preserving = true, 214 erase_can_throw = false, 215 split_join_can_throw = false, 216 reverse_iteration = true 217 }; 218 }; 219 220 template<> 221 struct container_traits_base<ov_tree_tag> 222 { 223 typedef ov_tree_tag container_category; 224 typedef basic_invalidation_guarantee invalidation_guarantee; 225 226 enum 227 { 228 order_preserving = true, 229 erase_can_throw = true, 230 split_join_can_throw = true, 231 reverse_iteration = false 232 }; 233 }; 234 235 template<> 236 struct container_traits_base<pat_trie_tag> 237 { 238 typedef pat_trie_tag container_category; 239 typedef range_invalidation_guarantee invalidation_guarantee; 240 241 enum 242 { 243 order_preserving = true, 244 erase_can_throw = false, 245 split_join_can_throw = true, 246 reverse_iteration = true 247 }; 248 }; 249 250 template<> 251 struct container_traits_base<list_update_tag> 252 { 253 typedef list_update_tag container_category; 254 typedef point_invalidation_guarantee invalidation_guarantee; 255 256 enum 257 { 258 order_preserving = false, 259 erase_can_throw = false, 260 split_join_can_throw = false, 261 reverse_iteration = false 262 }; 263 }; 264 265 266 template<> 267 struct container_traits_base<pairing_heap_tag> 268 { 269 typedef pairing_heap_tag container_category; 270 typedef point_invalidation_guarantee invalidation_guarantee; 271 272 enum 273 { 274 order_preserving = false, 275 erase_can_throw = false, 276 split_join_can_throw = false, 277 reverse_iteration = false 278 }; 279 }; 280 281 template<> 282 struct container_traits_base<thin_heap_tag> 283 { 284 typedef thin_heap_tag container_category; 285 typedef point_invalidation_guarantee invalidation_guarantee; 286 287 enum 288 { 289 order_preserving = false, 290 erase_can_throw = false, 291 split_join_can_throw = false, 292 reverse_iteration = false 293 }; 294 }; 295 296 template<> 297 struct container_traits_base<binomial_heap_tag> 298 { 299 typedef binomial_heap_tag container_category; 300 typedef point_invalidation_guarantee invalidation_guarantee; 301 302 enum 303 { 304 order_preserving = false, 305 erase_can_throw = false, 306 split_join_can_throw = false, 307 reverse_iteration = false 308 }; 309 }; 310 311 template<> 312 struct container_traits_base<rc_binomial_heap_tag> 313 { 314 typedef rc_binomial_heap_tag container_category; 315 typedef point_invalidation_guarantee invalidation_guarantee; 316 317 enum 318 { 319 order_preserving = false, 320 erase_can_throw = false, 321 split_join_can_throw = false, 322 reverse_iteration = false 323 }; 324 }; 325 326 template<> 327 struct container_traits_base<binary_heap_tag> 328 { 329 typedef binary_heap_tag container_category; 330 typedef basic_invalidation_guarantee invalidation_guarantee; 331 332 enum 333 { 334 order_preserving = false, 335 erase_can_throw = false, 336 split_join_can_throw = true, 337 reverse_iteration = false 338 }; 339 }; 340 341 342 /// container_traits 343 // See Matt Austern for the name, S. Meyers MEFC++ #2, others. 344 template<typename Cntnr> 345 struct container_traits 346 : public container_traits_base<typename Cntnr::container_category> 347 { 348 typedef Cntnr container_type; 349 typedef typename Cntnr::container_category container_category; 350 typedef container_traits_base<container_category> base_type; 351 typedef typename base_type::invalidation_guarantee invalidation_guarantee; 352 353 enum 354 { 355 order_preserving = base_type::order_preserving, 356 erase_can_throw = base_type::erase_can_throw, 357 split_join_can_throw = base_type::split_join_can_throw, 358 reverse_iteration = base_type::reverse_iteration 359 }; 360 }; 361 } // namespace __gnu_pbds 362 363 #endif 364
