1// -*- C++ -*- 2 3// Copyright (C) 2005, 2006, 2008, 2009, 2010 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 <bits/c++config.h> 46#include <ext/pb_ds/detail/type_utils.hpp> 47 48/** 49 * @namespace __gnu_pbds 50 * @brief GNU extensions for policy-based data structures for public use. 51 */ 52namespace __gnu_pbds 53{ 54 // A trivial iterator tag. Signifies that the iterators has none of 55 // the STL's movement abilities. 56 struct trivial_iterator_tag 57 { }; 58 59 // Prohibit moving trivial iterators. 60 typedef void trivial_iterator_difference_type; 61 62 63 // Signifies a basic invalidation guarantee that any iterator, 64 // pointer, or reference to a container object's mapped value type 65 // is valid as long as the container is not modified. 66 struct basic_invalidation_guarantee 67 { }; 68 69 // Signifies an invalidation guarantee that includes all those of 70 // its base, and additionally, that any point-type iterator, 71 // pointer, or reference to a container object's mapped value type 72 // is valid as long as its corresponding entry has not be erased, 73 // regardless of modifications to the container object. 74 struct point_invalidation_guarantee : public basic_invalidation_guarantee 75 { }; 76 77 // Signifies an invalidation guarantee that includes all those of 78 // its base, and additionally, that any range-type iterator 79 // (including the returns of begin() and end()) is in the correct 80 // relative positions to other range-type iterators as long as its 81 // corresponding entry has not be erased, regardless of 82 // modifications to the container object. 83 struct range_invalidation_guarantee : public point_invalidation_guarantee 84 { }; 85 86 87 /// A mapped-policy indicating that an associative container is a set. 88 // XXX should this be a trait of the form is_set<T> ?? 89 struct null_mapped_type { }; 90 91 92 /// Base data structure tag. 93 struct container_tag 94 { }; 95 96 /// Basic string container, inclusive of strings, ropes, etc. 97 struct string_tag : public container_tag { }; 98 99 /// Basic sequence. 100 struct sequence_tag : public container_tag { }; 101 102 /// Basic associative-container. 103 struct associative_container_tag : public container_tag { }; 104 105 /// Basic hash. 106 struct basic_hash_tag : public associative_container_tag { }; 107 108 /// Collision-chaining hash. 109 struct cc_hash_tag : public basic_hash_tag { }; 110 111 /// General-probing hash. 112 struct gp_hash_tag : public basic_hash_tag { }; 113 114 /// Basic tree. 115 struct basic_tree_tag : public associative_container_tag { }; 116 117 /// tree. 118 struct tree_tag : public basic_tree_tag { }; 119 120 /// Red-black tree. 121 struct rb_tree_tag : public tree_tag { }; 122 123 /// Splay tree. 124 struct splay_tree_tag : public tree_tag { }; 125 126 /// Ordered-vector tree. 127 struct ov_tree_tag : public tree_tag { }; 128 129 /// trie. 130 struct trie_tag : public basic_tree_tag { }; 131 132 /// PATRICIA trie. 133 struct pat_trie_tag : public trie_tag { }; 134 135 /// List-update. 136 struct list_update_tag : public associative_container_tag { }; 137 138 /// Basic priority-queue. 139 struct priority_queue_tag : public container_tag { }; 140 141 /// Pairing-heap. 142 struct pairing_heap_tag : public priority_queue_tag { }; 143 144 /// Binomial-heap. 145 struct binomial_heap_tag : public priority_queue_tag { }; 146 147 /// Redundant-counter binomial-heap. 148 struct rc_binomial_heap_tag : public priority_queue_tag { }; 149 150 /// Binary-heap (array-based). 151 struct binary_heap_tag : public priority_queue_tag { }; 152 153 /// Thin heap. 154 struct thin_heap_tag : public priority_queue_tag { }; 155 156 157 /// Base traits type for containers. 158 template<typename Tag> 159 struct container_traits_base; 160 161 template<> 162 struct container_traits_base<cc_hash_tag> 163 { 164 typedef cc_hash_tag container_category; 165 typedef point_invalidation_guarantee invalidation_guarantee; 166 167 enum 168 { 169 order_preserving = false, 170 erase_can_throw = false, 171 split_join_can_throw = false, 172 reverse_iteration = false 173 }; 174 }; 175 176 template<> 177 struct container_traits_base<gp_hash_tag> 178 { 179 typedef gp_hash_tag container_category; 180 typedef basic_invalidation_guarantee invalidation_guarantee; 181 182 enum 183 { 184 order_preserving = false, 185 erase_can_throw = false, 186 split_join_can_throw = false, 187 reverse_iteration = false 188 }; 189 }; 190 191 template<> 192 struct container_traits_base<rb_tree_tag> 193 { 194 typedef rb_tree_tag container_category; 195 typedef range_invalidation_guarantee invalidation_guarantee; 196 197 enum 198 { 199 order_preserving = true, 200 erase_can_throw = false, 201 split_join_can_throw = false, 202 reverse_iteration = true 203 }; 204 }; 205 206 template<> 207 struct container_traits_base<splay_tree_tag> 208 { 209 typedef splay_tree_tag container_category; 210 typedef range_invalidation_guarantee invalidation_guarantee; 211 212 enum 213 { 214 order_preserving = true, 215 erase_can_throw = false, 216 split_join_can_throw = false, 217 reverse_iteration = true 218 }; 219 }; 220 221 template<> 222 struct container_traits_base<ov_tree_tag> 223 { 224 typedef ov_tree_tag container_category; 225 typedef basic_invalidation_guarantee invalidation_guarantee; 226 227 enum 228 { 229 order_preserving = true, 230 erase_can_throw = true, 231 split_join_can_throw = true, 232 reverse_iteration = false 233 }; 234 }; 235 236 template<> 237 struct container_traits_base<pat_trie_tag> 238 { 239 typedef pat_trie_tag container_category; 240 typedef range_invalidation_guarantee invalidation_guarantee; 241 242 enum 243 { 244 order_preserving = true, 245 erase_can_throw = false, 246 split_join_can_throw = true, 247 reverse_iteration = true 248 }; 249 }; 250 251 template<> 252 struct container_traits_base<list_update_tag> 253 { 254 typedef list_update_tag container_category; 255 typedef point_invalidation_guarantee invalidation_guarantee; 256 257 enum 258 { 259 order_preserving = false, 260 erase_can_throw = false, 261 split_join_can_throw = false, 262 reverse_iteration = false 263 }; 264 }; 265 266 267 template<> 268 struct container_traits_base<pairing_heap_tag> 269 { 270 typedef pairing_heap_tag container_category; 271 typedef point_invalidation_guarantee invalidation_guarantee; 272 273 enum 274 { 275 order_preserving = false, 276 erase_can_throw = false, 277 split_join_can_throw = false, 278 reverse_iteration = false 279 }; 280 }; 281 282 template<> 283 struct container_traits_base<thin_heap_tag> 284 { 285 typedef thin_heap_tag container_category; 286 typedef point_invalidation_guarantee invalidation_guarantee; 287 288 enum 289 { 290 order_preserving = false, 291 erase_can_throw = false, 292 split_join_can_throw = false, 293 reverse_iteration = false 294 }; 295 }; 296 297 template<> 298 struct container_traits_base<binomial_heap_tag> 299 { 300 typedef binomial_heap_tag container_category; 301 typedef point_invalidation_guarantee invalidation_guarantee; 302 303 enum 304 { 305 order_preserving = false, 306 erase_can_throw = false, 307 split_join_can_throw = false, 308 reverse_iteration = false 309 }; 310 }; 311 312 template<> 313 struct container_traits_base<rc_binomial_heap_tag> 314 { 315 typedef rc_binomial_heap_tag container_category; 316 typedef point_invalidation_guarantee invalidation_guarantee; 317 318 enum 319 { 320 order_preserving = false, 321 erase_can_throw = false, 322 split_join_can_throw = false, 323 reverse_iteration = false 324 }; 325 }; 326 327 template<> 328 struct container_traits_base<binary_heap_tag> 329 { 330 typedef binary_heap_tag container_category; 331 typedef basic_invalidation_guarantee invalidation_guarantee; 332 333 enum 334 { 335 order_preserving = false, 336 erase_can_throw = false, 337 split_join_can_throw = true, 338 reverse_iteration = false 339 }; 340 }; 341 342 343 /// container_traits 344 // See Matt Austern for the name, S. Meyers MEFC++ #2, others. 345 template<typename Cntnr> 346 struct container_traits 347 : public container_traits_base<typename Cntnr::container_category> 348 { 349 typedef Cntnr container_type; 350 typedef typename Cntnr::container_category container_category; 351 typedef container_traits_base<container_category> base_type; 352 typedef typename base_type::invalidation_guarantee invalidation_guarantee; 353 354 enum 355 { 356 order_preserving = base_type::order_preserving, 357 erase_can_throw = base_type::erase_can_throw, 358 split_join_can_throw = base_type::split_join_can_throw, 359 reverse_iteration = base_type::reverse_iteration 360 }; 361 }; 362} // namespace __gnu_pbds 363 364#endif 365