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

   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  */
  52 namespace __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