contrib/gcc-4.7/libstdc++-v3/include/ext/pb_ds/tag_and_trait.hpp

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2005, 2006, 2008, 2009, 2010, 2011
   4 // Free Software Foundation, Inc.
   5 //
   6 // This file is part of the GNU ISO C++ Library.  This library is free
   7 // software; you can redistribute it and/or modify it under the terms
   8 // of the GNU General Public License as published by the Free Software
   9 // Foundation; either version 3, or (at your option) any later
  10 // version.
  11
  12 // This library is distributed in the hope that it will be useful, but
  13 // WITHOUT ANY WARRANTY; without even the implied warranty of
  14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  15 // General Public License for more details.
  16
  17 // Under Section 7 of GPL version 3, you are granted additional
  18 // permissions described in the GCC Runtime Library Exception, version
  19 // 3.1, as published by the Free Software Foundation.
  20
  21 // You should have received a copy of the GNU General Public License and
  22 // a copy of the GCC Runtime Library Exception along with this program;
  23 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
  24 // <http://www.gnu.org/licenses/>.
  25
  26 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
  27
  28 // Permission to use, copy, modify, sell, and distribute this software
  29 // is hereby granted without fee, provided that the above copyright
  30 // notice appears in all copies, and that both that copyright notice
  31 // and this permission notice appear in supporting documentation. None
  32 // of the above authors, nor IBM Haifa Research Laboratories, make any
  33 // representation about the suitability of this software for any
  34 // purpose. It is provided "as is" without express or implied
  35 // warranty.
  36
  37 /**
  38  * @file tag_and_trait.hpp
  39  * Contains tags and traits, e.g., ones describing underlying
  40  * data structures.
  41  */
  42
  43 #ifndef PB_DS_TAG_AND_TRAIT_HPP
  44 #define PB_DS_TAG_AND_TRAIT_HPP
  45
  46 #include <bits/c++config.h>
  47 #include <ext/pb_ds/detail/type_utils.hpp>
  48
  49 /**
  50  * @namespace __gnu_pbds
  51  * @brief GNU extensions for policy-based data structures for public use.
  52  */
  53 namespace __gnu_pbds
  54 {
  55   /** @defgroup pbds Policy-Based Data Structures
  56    *  @ingroup extensions
  57    *
  58    *  This is a library of policy-based elementary data structures:
  59    *  associative containers and priority queues. It is designed for
  60    *  high-performance, flexibility, semantic safety, and conformance
  61    *  to the corresponding containers in std (except for some points
  62    *  where it differs by design).
  63    *
  64    *  For details, see:
  65    *  http://gcc.gnu.org/onlinedocs/libstdc++/ext/pb_ds/index.html
  66    *
  67    *  @{
  68    */
  69
  70   /**
  71    *  @defgroup tags Tags
  72    *  @{
  73    */
  74   /// A trivial iterator tag. Signifies that the iterators has none of
  75   /// std::iterators's movement abilities.
  76   struct trivial_iterator_tag
  77   { };
  78
  79   /// Prohibit moving trivial iterators.
  80   typedef void trivial_iterator_difference_type;
  81
  82
  83   /**
  84    *  @defgroup invalidation_tags  Invalidation Guarantees
  85    *  @ingroup tags
  86    *  @{
  87    */
  88
  89   /**
  90    *  Signifies a basic invalidation guarantee that any iterator,
  91    *  pointer, or reference to a container object's mapped value type
  92    *  is valid as long as the container is not modified.
  93    */
  94   struct basic_invalidation_guarantee
  95   { };
  96
  97   /**
  98    *  Signifies an invalidation guarantee that includes all those of
  99    *  its base, and additionally, that any point-type iterator,
 100    *  pointer, or reference to a container object's mapped value type
 101    *  is valid as long as its corresponding entry has not be erased,
 102    *  regardless of modifications to the container object.
 103    */
 104   struct point_invalidation_guarantee : public basic_invalidation_guarantee
 105   { };
 106
 107   /**
 108    *  Signifies an invalidation guarantee that includes all those of
 109    *  its base, and additionally, that any range-type iterator
 110    *  (including the returns of begin() and end()) is in the correct
 111    *  relative positions to other range-type iterators as long as its
 112    *  corresponding entry has not be erased, regardless of
 113    *  modifications to the container object.
 114    */
 115   struct range_invalidation_guarantee : public point_invalidation_guarantee
 116   { };
 117   //@}
 118
 119
 120   /**
 121    *  @defgroup ds_tags Data Structure Type
 122    *  @ingroup tags
 123    *  @{
 124    */
 125   /// Base data structure tag.
 126   struct container_tag
 127   { };
 128
 129   /// Basic sequence.
 130   struct sequence_tag : public container_tag { };
 131
 132   /// Basic string container, inclusive of strings, ropes, etc.
 133   struct string_tag : public sequence_tag { };
 134
 135   /// Basic associative-container.
 136   struct associative_tag : public container_tag { };
 137
 138   /// Basic hash structure.
 139   struct basic_hash_tag : public associative_tag { };
 140
 141   /// Collision-chaining hash.
 142   struct cc_hash_tag : public basic_hash_tag { };
 143
 144   /// General-probing hash.
 145   struct gp_hash_tag : public basic_hash_tag { };
 146
 147   /// Basic branch structure.
 148   struct basic_branch_tag : public associative_tag { };
 149
 150   /// Basic tree structure.
 151   struct tree_tag : public basic_branch_tag { };
 152
 153   /// Red-black tree.
 154   struct rb_tree_tag : public tree_tag { };
 155
 156   /// Splay tree.
 157   struct splay_tree_tag : public tree_tag { };
 158
 159   /// Ordered-vector tree.
 160   struct ov_tree_tag : public tree_tag { };
 161
 162   /// Basic trie structure.
 163   struct trie_tag : public basic_branch_tag { };
 164
 165   /// PATRICIA trie.
 166   struct pat_trie_tag : public trie_tag { };
 167
 168   /// List-update.
 169   struct list_update_tag : public associative_tag { };
 170
 171   /// Basic priority-queue.
 172   struct priority_queue_tag : public container_tag { };
 173
 174   /// Pairing-heap.
 175   struct pairing_heap_tag : public priority_queue_tag { };
 176
 177   /// Binomial-heap.
 178   struct binomial_heap_tag : public priority_queue_tag { };
 179
 180   /// Redundant-counter binomial-heap.
 181   struct rc_binomial_heap_tag : public priority_queue_tag { };
 182
 183   /// Binary-heap (array-based).
 184   struct binary_heap_tag : public priority_queue_tag { };
 185
 186   /// Thin heap.
 187   struct thin_heap_tag : public priority_queue_tag { };
 188   //@}
 189   //@}
 190
 191
 192   /**
 193    *  @defgroup traits Traits
 194    *  @{
 195    */
 196
 197   /**
 198    *  @brief Represents no type, or absence of type, for template tricks.
 199    *
 200    *  In a mapped-policy, indicates that an associative container is a set.
 201    *
 202    *  In a list-update policy, indicates that each link does not need
 203    *  metadata.
 204    *
 205    *  In a hash policy, indicates that the combining hash function
 206    *  is actually a ranged hash function.
 207    *
 208    *  In a probe policy, indicates that the combining probe function
 209    *  is actually a ranged probe function.
 210    */
 211   struct null_type { };
 212
 213   /// A null node updator, indicating that no node updates are required.
 214   template<typename _Tp1, typename _Tp2, typename _Tp3, typename _Tp4>
 215     struct null_node_update : public null_type
 216     { };
 217
 218
 219   /// Primary template, container traits base.
 220   template<typename _Tag>
 221     struct container_traits_base;
 222
 223   /// Specialization, cc hash.
 224   template<>
 225   struct container_traits_base<cc_hash_tag>
 226   {
 227     typedef cc_hash_tag                                 container_category;
 228     typedef point_invalidation_guarantee                invalidation_guarantee;
 229
 230     enum
 231       {
 232         order_preserving = false,
 233         erase_can_throw = false,
 234         split_join_can_throw = false,
 235         reverse_iteration = false
 236       };
 237   };
 238
 239   /// Specialization, gp hash.
 240   template<>
 241   struct container_traits_base<gp_hash_tag>
 242   {
 243     typedef gp_hash_tag                                 container_category;
 244     typedef basic_invalidation_guarantee                invalidation_guarantee;
 245
 246     enum
 247       {
 248         order_preserving = false,
 249         erase_can_throw = false,
 250         split_join_can_throw = false,
 251         reverse_iteration = false
 252       };
 253   };
 254
 255   /// Specialization, rb tree.
 256   template<>
 257   struct container_traits_base<rb_tree_tag>
 258   {
 259     typedef rb_tree_tag                                 container_category;
 260     typedef range_invalidation_guarantee                invalidation_guarantee;
 261
 262     enum
 263       {
 264         order_preserving = true,
 265         erase_can_throw = false,
 266         split_join_can_throw = false,
 267         reverse_iteration = true
 268       };
 269   };
 270
 271   /// Specialization, splay tree.
 272   template<>
 273   struct container_traits_base<splay_tree_tag>
 274   {
 275     typedef splay_tree_tag                              container_category;
 276     typedef range_invalidation_guarantee                invalidation_guarantee;
 277
 278     enum
 279       {
 280         order_preserving = true,
 281         erase_can_throw = false,
 282         split_join_can_throw = false,
 283         reverse_iteration = true
 284       };
 285   };
 286
 287   /// Specialization, ov tree.
 288   template<>
 289   struct container_traits_base<ov_tree_tag>
 290   {
 291     typedef ov_tree_tag                                 container_category;
 292     typedef basic_invalidation_guarantee                invalidation_guarantee;
 293
 294     enum
 295       {
 296         order_preserving = true,
 297         erase_can_throw = true,
 298         split_join_can_throw = true,
 299         reverse_iteration = false
 300       };
 301   };
 302
 303   /// Specialization, pat trie.
 304   template<>
 305   struct container_traits_base<pat_trie_tag>
 306   {
 307     typedef pat_trie_tag                                container_category;
 308     typedef range_invalidation_guarantee                invalidation_guarantee;
 309
 310     enum
 311       {
 312         order_preserving = true,
 313         erase_can_throw = false,
 314         split_join_can_throw = true,
 315         reverse_iteration = true
 316       };
 317   };
 318
 319   /// Specialization, list update.
 320   template<>
 321   struct container_traits_base<list_update_tag>
 322   {
 323     typedef list_update_tag                             container_category;
 324     typedef point_invalidation_guarantee                invalidation_guarantee;
 325
 326     enum
 327       {
 328         order_preserving = false,
 329         erase_can_throw = false,
 330         split_join_can_throw = false,
 331         reverse_iteration = false
 332       };
 333   };
 334
 335   /// Specialization, pairing heap.
 336   template<>
 337   struct container_traits_base<pairing_heap_tag>
 338   {
 339     typedef pairing_heap_tag                            container_category;
 340     typedef point_invalidation_guarantee                invalidation_guarantee;
 341
 342     enum
 343       {
 344         order_preserving = false,
 345         erase_can_throw = false,
 346         split_join_can_throw = false,
 347         reverse_iteration = false
 348       };
 349   };
 350
 351   /// Specialization, thin heap.
 352   template<>
 353   struct container_traits_base<thin_heap_tag>
 354   {
 355     typedef thin_heap_tag                               container_category;
 356     typedef point_invalidation_guarantee                invalidation_guarantee;
 357
 358     enum
 359       {
 360         order_preserving = false,
 361         erase_can_throw = false,
 362         split_join_can_throw = false,
 363         reverse_iteration = false
 364       };
 365   };
 366
 367   /// Specialization, binomial heap.
 368   template<>
 369   struct container_traits_base<binomial_heap_tag>
 370   {
 371     typedef binomial_heap_tag                           container_category;
 372     typedef point_invalidation_guarantee                invalidation_guarantee;
 373
 374     enum
 375       {
 376         order_preserving = false,
 377         erase_can_throw = false,
 378         split_join_can_throw = false,
 379         reverse_iteration = false
 380       };
 381   };
 382
 383   /// Specialization, rc binomial heap.
 384   template<>
 385   struct container_traits_base<rc_binomial_heap_tag>
 386   {
 387     typedef rc_binomial_heap_tag                        container_category;
 388     typedef point_invalidation_guarantee                invalidation_guarantee;
 389
 390     enum
 391       {
 392         order_preserving = false,
 393         erase_can_throw = false,
 394         split_join_can_throw = false,
 395         reverse_iteration = false
 396       };
 397   };
 398
 399   /// Specialization, binary heap.
 400   template<>
 401   struct container_traits_base<binary_heap_tag>
 402   {
 403     typedef binary_heap_tag                             container_category;
 404     typedef basic_invalidation_guarantee                invalidation_guarantee;
 405
 406     enum
 407       {
 408         order_preserving = false,
 409         erase_can_throw = false,
 410         split_join_can_throw = true,
 411         reverse_iteration = false
 412       };
 413   };
 414
 415
 416   /// Container traits.
 417   // See Matt Austern for the name, S. Meyers MEFC++ #2, others.
 418   template<typename Cntnr>
 419   struct container_traits
 420   : public container_traits_base<typename Cntnr::container_category>
 421   {
 422     typedef Cntnr                                      container_type;
 423     typedef typename Cntnr::container_category         container_category;
 424     typedef container_traits_base<container_category>  base_type;
 425     typedef typename base_type::invalidation_guarantee invalidation_guarantee;
 426
 427     enum
 428       {
 429         /// True only if Cntnr objects guarantee storing  keys by order.
 430         order_preserving = base_type::order_preserving,
 431
 432         /// True only if erasing a key can throw.
 433         erase_can_throw = base_type::erase_can_throw,
 434
 435         /// True only if split or join operations can throw.
 436         split_join_can_throw = base_type::split_join_can_throw,
 437
 438         /// True only reverse iterators are supported.
 439         reverse_iteration = base_type::reverse_iteration
 440       };
 441   };
 442   //@}
 443
 444
 445   namespace detail
 446   {
 447     /// Dispatch mechanism, primary template for associative types.
 448     template<typename Key, typename Mapped, typename _Alloc, typename Tag,
 449              typename Policy_Tl = null_type>
 450       struct container_base_dispatch;
 451   } // namespace __detail
 452   //@}
 453 } // namespace __gnu_pbds
 454
 455 #endif