libstdc++-v3/include/ext/pb_ds/tag_and_trait.hpp

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2005-2018 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  */
  52 namespace __gnu_pbds
  53 {
  54   /** @defgroup pbds Policy-Based Data Structures
  55    *  @ingroup extensions
  56    *
  57    *  This is a library of policy-based elementary data structures:
  58    *  associative containers and priority queues. It is designed for
  59    *  high-performance, flexibility, semantic safety, and conformance
  60    *  to the corresponding containers in std (except for some points
  61    *  where it differs by design).
  62    *
  63    *  For details, see:
  64    *  http://gcc.gnu.org/onlinedocs/libstdc++/ext/pb_ds/index.html
  65    *
  66    *  @{
  67    */
  68
  69   /**
  70    *  @defgroup tags Tags
  71    *  @{
  72    */
  73   /// A trivial iterator tag. Signifies that the iterators has none of
  74   /// std::iterators's movement abilities.
  75   struct trivial_iterator_tag
  76   { };
  77
  78   /// Prohibit moving trivial iterators.
  79   typedef void trivial_iterator_difference_type;
  80
  81
  82   /**
  83    *  @defgroup invalidation_tags  Invalidation Guarantees
  84    *  @ingroup tags
  85    *  @{
  86    */
  87
  88   /**
  89    *  Signifies a basic invalidation guarantee that any iterator,
  90    *  pointer, or reference to a container object's mapped value type
  91    *  is valid as long as the container is not modified.
  92    */
  93   struct basic_invalidation_guarantee
  94   { };
  95
  96   /**
  97    *  Signifies an invalidation guarantee that includes all those of
  98    *  its base, and additionally, that any point-type iterator,
  99    *  pointer, or reference to a container object's mapped value type
 100    *  is valid as long as its corresponding entry has not be erased,
 101    *  regardless of modifications to the container object.
 102    */
 103   struct point_invalidation_guarantee : public basic_invalidation_guarantee
 104   { };
 105
 106   /**
 107    *  Signifies an invalidation guarantee that includes all those of
 108    *  its base, and additionally, that any range-type iterator
 109    *  (including the returns of begin() and end()) is in the correct
 110    *  relative positions to other range-type iterators as long as its
 111    *  corresponding entry has not be erased, regardless of
 112    *  modifications to the container object.
 113    */
 114   struct range_invalidation_guarantee : public point_invalidation_guarantee
 115   { };
 116   //@}
 117
 118
 119   /**
 120    *  @defgroup ds_tags Data Structure Type
 121    *  @ingroup tags
 122    *  @{
 123    */
 124   /// Base data structure tag.
 125   struct container_tag
 126   { };
 127
 128   /// Basic sequence.
 129   struct sequence_tag : public container_tag { };
 130
 131   /// Basic string container, inclusive of strings, ropes, etc.
 132   struct string_tag : public sequence_tag { };
 133
 134   /// Basic associative-container.
 135   struct associative_tag : public container_tag { };
 136
 137   /// Basic hash structure.
 138   struct basic_hash_tag : public associative_tag { };
 139
 140   /// Collision-chaining hash.
 141   struct cc_hash_tag : public basic_hash_tag { };
 142
 143   /// General-probing hash.
 144   struct gp_hash_tag : public basic_hash_tag { };
 145
 146   /// Basic branch structure.
 147   struct basic_branch_tag : public associative_tag { };
 148
 149   /// Basic tree structure.
 150   struct tree_tag : public basic_branch_tag { };
 151
 152   /// Red-black tree.
 153   struct rb_tree_tag : public tree_tag { };
 154
 155   /// Splay tree.
 156   struct splay_tree_tag : public tree_tag { };
 157
 158   /// Ordered-vector tree.
 159   struct ov_tree_tag : public tree_tag { };
 160
 161   /// Basic trie structure.
 162   struct trie_tag : public basic_branch_tag { };
 163
 164   /// PATRICIA trie.
 165   struct pat_trie_tag : public trie_tag { };
 166
 167   /// List-update.
 168   struct list_update_tag : public associative_tag { };
 169
 170   /// Basic priority-queue.
 171   struct priority_queue_tag : public container_tag { };
 172
 173   /// Pairing-heap.
 174   struct pairing_heap_tag : public priority_queue_tag { };
 175
 176   /// Binomial-heap.
 177   struct binomial_heap_tag : public priority_queue_tag { };
 178
 179   /// Redundant-counter binomial-heap.
 180   struct rc_binomial_heap_tag : public priority_queue_tag { };
 181
 182   /// Binary-heap (array-based).
 183   struct binary_heap_tag : public priority_queue_tag { };
 184
 185   /// Thin heap.
 186   struct thin_heap_tag : public priority_queue_tag { };
 187   //@}
 188   //@}
 189
 190
 191   /**
 192    *  @defgroup traits Traits
 193    *  @{
 194    */
 195
 196   /**
 197    *  @brief Represents no type, or absence of type, for template tricks.
 198    *
 199    *  In a mapped-policy, indicates that an associative container is a set.
 200    *
 201    *  In a list-update policy, indicates that each link does not need
 202    *  metadata.
 203    *
 204    *  In a hash policy, indicates that the combining hash function
 205    *  is actually a ranged hash function.
 206    *
 207    *  In a probe policy, indicates that the combining probe function
 208    *  is actually a ranged probe function.
 209    */
 210   struct null_type { };
 211
 212   /// A null node updator, indicating that no node updates are required.
 213   template<typename _Tp1, typename _Tp2, typename _Tp3, typename _Tp4>
 214     struct null_node_update : public null_type
 215     { };
 216
 217
 218   /// Primary template, container traits base.
 219   template<typename _Tag>
 220     struct container_traits_base;
 221
 222   /// Specialization, cc hash.
 223   template<>
 224   struct container_traits_base<cc_hash_tag>
 225   {
 226     typedef cc_hash_tag                                 container_category;
 227     typedef point_invalidation_guarantee                invalidation_guarantee;
 228
 229     enum
 230       {
 231         order_preserving = false,
 232         erase_can_throw = false,
 233         split_join_can_throw = false,
 234         reverse_iteration = false
 235       };
 236   };
 237
 238   /// Specialization, gp hash.
 239   template<>
 240   struct container_traits_base<gp_hash_tag>
 241   {
 242     typedef gp_hash_tag                                 container_category;
 243     typedef basic_invalidation_guarantee                invalidation_guarantee;
 244
 245     enum
 246       {
 247         order_preserving = false,
 248         erase_can_throw = false,
 249         split_join_can_throw = false,
 250         reverse_iteration = false
 251       };
 252   };
 253
 254   /// Specialization, rb tree.
 255   template<>
 256   struct container_traits_base<rb_tree_tag>
 257   {
 258     typedef rb_tree_tag                                 container_category;
 259     typedef range_invalidation_guarantee                invalidation_guarantee;
 260
 261     enum
 262       {
 263         order_preserving = true,
 264         erase_can_throw = false,
 265         split_join_can_throw = false,
 266         reverse_iteration = true
 267       };
 268   };
 269
 270   /// Specialization, splay tree.
 271   template<>
 272   struct container_traits_base<splay_tree_tag>
 273   {
 274     typedef splay_tree_tag                              container_category;
 275     typedef range_invalidation_guarantee                invalidation_guarantee;
 276
 277     enum
 278       {
 279         order_preserving = true,
 280         erase_can_throw = false,
 281         split_join_can_throw = false,
 282         reverse_iteration = true
 283       };
 284   };
 285
 286   /// Specialization, ov tree.
 287   template<>
 288   struct container_traits_base<ov_tree_tag>
 289   {
 290     typedef ov_tree_tag                                 container_category;
 291     typedef basic_invalidation_guarantee                invalidation_guarantee;
 292
 293     enum
 294       {
 295         order_preserving = true,
 296         erase_can_throw = true,
 297         split_join_can_throw = true,
 298         reverse_iteration = false
 299       };
 300   };
 301
 302   /// Specialization, pat trie.
 303   template<>
 304   struct container_traits_base<pat_trie_tag>
 305   {
 306     typedef pat_trie_tag                                container_category;
 307     typedef range_invalidation_guarantee                invalidation_guarantee;
 308
 309     enum
 310       {
 311         order_preserving = true,
 312         erase_can_throw = false,
 313         split_join_can_throw = true,
 314         reverse_iteration = true
 315       };
 316   };
 317
 318   /// Specialization, list update.
 319   template<>
 320   struct container_traits_base<list_update_tag>
 321   {
 322     typedef list_update_tag                             container_category;
 323     typedef point_invalidation_guarantee                invalidation_guarantee;
 324
 325     enum
 326       {
 327         order_preserving = false,
 328         erase_can_throw = false,
 329         split_join_can_throw = false,
 330         reverse_iteration = false
 331       };
 332   };
 333
 334   /// Specialization, pairing heap.
 335   template<>
 336   struct container_traits_base<pairing_heap_tag>
 337   {
 338     typedef pairing_heap_tag                            container_category;
 339     typedef point_invalidation_guarantee                invalidation_guarantee;
 340
 341     enum
 342       {
 343         order_preserving = false,
 344         erase_can_throw = false,
 345         split_join_can_throw = false,
 346         reverse_iteration = false
 347       };
 348   };
 349
 350   /// Specialization, thin heap.
 351   template<>
 352   struct container_traits_base<thin_heap_tag>
 353   {
 354     typedef thin_heap_tag                               container_category;
 355     typedef point_invalidation_guarantee                invalidation_guarantee;
 356
 357     enum
 358       {
 359         order_preserving = false,
 360         erase_can_throw = false,
 361         split_join_can_throw = false,
 362         reverse_iteration = false
 363       };
 364   };
 365
 366   /// Specialization, binomial heap.
 367   template<>
 368   struct container_traits_base<binomial_heap_tag>
 369   {
 370     typedef binomial_heap_tag                           container_category;
 371     typedef point_invalidation_guarantee                invalidation_guarantee;
 372
 373     enum
 374       {
 375         order_preserving = false,
 376         erase_can_throw = false,
 377         split_join_can_throw = false,
 378         reverse_iteration = false
 379       };
 380   };
 381
 382   /// Specialization, rc binomial heap.
 383   template<>
 384   struct container_traits_base<rc_binomial_heap_tag>
 385   {
 386     typedef rc_binomial_heap_tag                        container_category;
 387     typedef point_invalidation_guarantee                invalidation_guarantee;
 388
 389     enum
 390       {
 391         order_preserving = false,
 392         erase_can_throw = false,
 393         split_join_can_throw = false,
 394         reverse_iteration = false
 395       };
 396   };
 397
 398   /// Specialization, binary heap.
 399   template<>
 400   struct container_traits_base<binary_heap_tag>
 401   {
 402     typedef binary_heap_tag                             container_category;
 403     typedef basic_invalidation_guarantee                invalidation_guarantee;
 404
 405     enum
 406       {
 407         order_preserving = false,
 408         erase_can_throw = false,
 409         split_join_can_throw = true,
 410         reverse_iteration = false
 411       };
 412   };
 413
 414
 415   /// Container traits.
 416   // See Matt Austern for the name, S. Meyers MEFC++ #2, others.
 417   template<typename Cntnr>
 418   struct container_traits
 419   : public container_traits_base<typename Cntnr::container_category>
 420   {
 421     typedef Cntnr                                      container_type;
 422     typedef typename Cntnr::container_category         container_category;
 423     typedef container_traits_base<container_category>  base_type;
 424     typedef typename base_type::invalidation_guarantee invalidation_guarantee;
 425
 426     enum
 427       {
 428         /// True only if Cntnr objects guarantee storing  keys by order.
 429         order_preserving = base_type::order_preserving,
 430
 431         /// True only if erasing a key can throw.
 432         erase_can_throw = base_type::erase_can_throw,
 433
 434         /// True only if split or join operations can throw.
 435         split_join_can_throw = base_type::split_join_can_throw,
 436
 437         /// True only reverse iterators are supported.
 438         reverse_iteration = base_type::reverse_iteration
 439       };
 440   };
 441   //@}
 442
 443
 444   namespace detail
 445   {
 446     /// Dispatch mechanism, primary template for associative types.
 447     template<typename Key, typename Mapped, typename _Alloc, typename Tag,
 448              typename Policy_Tl = null_type>
 449       struct container_base_dispatch;
 450   } // namespace detail
 451   //@}
 452 } // namespace __gnu_pbds
 453
 454 #endif