l4/pkg/libstdc++-v3/contrib/libstdc++-v3-4.3.3/include/ext/pb_ds/tag_and_trait.hpp

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2005, 2006 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 2, 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 // You should have received a copy of the GNU General Public License
  17 // along with this library; see the file COPYING.  If not, write to
  18 // the Free Software Foundation, 59 Temple Place - Suite 330, Boston,
  19 // MA 02111-1307, USA.
  20
  21 // As a special exception, you may use this file as part of a free
  22 // software library without restriction.  Specifically, if other files
  23 // instantiate templates or use macros or inline functions from this
  24 // file, or you compile this file and link it with other files to
  25 // produce an executable, this file does not by itself cause the
  26 // resulting executable to be covered by the GNU General Public
  27 // License.  This exception does not however invalidate any other
  28 // reasons why the executable file might be covered by the GNU General
  29 // Public License.
  30
  31 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
  32
  33 // Permission to use, copy, modify, sell, and distribute this software
  34 // is hereby granted without fee, provided that the above copyright
  35 // notice appears in all copies, and that both that copyright notice
  36 // and this permission notice appear in supporting documentation. None
  37 // of the above authors, nor IBM Haifa Research Laboratories, make any
  38 // representation about the suitability of this software for any
  39 // purpose. It is provided "as is" without express or implied
  40 // warranty.
  41
  42 /**
  43  * @file tag_and_trait.hpp
  44  * Contains tags and traits, e.g., ones describing underlying
  45  *    data structures.
  46  */
  47
  48 #ifndef PB_DS_TAG_AND_TRAIT_HPP
  49 #define PB_DS_TAG_AND_TRAIT_HPP
  50
  51 #include <ext/pb_ds/detail/type_utils.hpp>
  52
  53 /**
  54  * @namespace __gnu_pbds
  55  * @brief GNU extensions for policy-based data structures for public use.
  56  */
  57 namespace __gnu_pbds
  58 {
  59   // A trivial iterator tag. Signifies that the iterators has none of
  60   // the STL's movement abilities.
  61   struct trivial_iterator_tag
  62   { };
  63
  64   // Prohibit moving trivial iterators.
  65   typedef void trivial_iterator_difference_type;
  66
  67
  68   // Signifies a basic invalidation guarantee that any iterator,
  69   // pointer, or reference to a container object's mapped value type
  70   // is valid as long as the container is not modified.
  71   struct basic_invalidation_guarantee
  72   { };
  73
  74   // Signifies an invalidation guarantee that includes all those of
  75   // its base, and additionally, that any point-type iterator,
  76   // pointer, or reference to a container object's mapped value type
  77   // is valid as long as its corresponding entry has not be erased,
  78   // regardless of modifications to the container object.
  79   struct point_invalidation_guarantee : public basic_invalidation_guarantee
  80   { };
  81
  82   // Signifies an invalidation guarantee that includes all those of
  83   // its base, and additionally, that any range-type iterator
  84   // (including the returns of begin() and end()) is in the correct
  85   // relative positions to other range-type iterators as long as its
  86   // corresponding entry has not be erased, regardless of
  87   // modifications to the container object.
  88   struct range_invalidation_guarantee : public point_invalidation_guarantee
  89   { };
  90
  91
  92   // A mapped-policy indicating that an associative container is a set.
  93   // XXX should this be a trait of the form is_set<T> ??
  94   struct null_mapped_type { };
  95
  96
  97   // Base data structure tag.
  98   struct container_tag
  99   { };
 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   template<typename Tag>
 157   struct container_traits_base;
 158
 159   template<>
 160   struct container_traits_base<cc_hash_tag>
 161   {
 162     typedef cc_hash_tag container_category;
 163     typedef point_invalidation_guarantee invalidation_guarantee;
 164
 165     enum
 166       {
 167         order_preserving = false,
 168         erase_can_throw = false,
 169         split_join_can_throw = false,
 170         reverse_iteration = false
 171       };
 172   };
 173
 174   template<>
 175   struct container_traits_base<gp_hash_tag>
 176   {
 177     typedef gp_hash_tag container_category;
 178     typedef basic_invalidation_guarantee invalidation_guarantee;
 179
 180     enum
 181       {
 182         order_preserving = false,
 183         erase_can_throw = false,
 184         split_join_can_throw = false,
 185         reverse_iteration = false
 186       };
 187   };
 188
 189   template<>
 190   struct container_traits_base<rb_tree_tag>
 191   {
 192     typedef rb_tree_tag container_category;
 193     typedef range_invalidation_guarantee invalidation_guarantee;
 194
 195     enum
 196       {
 197         order_preserving = true,
 198         erase_can_throw = false,
 199         split_join_can_throw = false,
 200         reverse_iteration = true
 201       };
 202   };
 203
 204   template<>
 205   struct container_traits_base<splay_tree_tag>
 206   {
 207     typedef splay_tree_tag container_category;
 208     typedef range_invalidation_guarantee invalidation_guarantee;
 209
 210     enum
 211       {
 212         order_preserving = true,
 213         erase_can_throw = false,
 214         split_join_can_throw = false,
 215         reverse_iteration = true
 216       };
 217   };
 218
 219   template<>
 220   struct container_traits_base<ov_tree_tag>
 221   {
 222     typedef ov_tree_tag container_category;
 223     typedef basic_invalidation_guarantee invalidation_guarantee;
 224
 225     enum
 226       {
 227         order_preserving = true,
 228         erase_can_throw = true,
 229         split_join_can_throw = true,
 230         reverse_iteration = false
 231       };
 232   };
 233
 234   template<>
 235   struct container_traits_base<pat_trie_tag>
 236   {
 237     typedef pat_trie_tag container_category;
 238     typedef range_invalidation_guarantee invalidation_guarantee;
 239
 240     enum
 241       {
 242         order_preserving = true,
 243         erase_can_throw = false,
 244         split_join_can_throw = true,
 245         reverse_iteration = true
 246       };
 247   };
 248
 249   template<>
 250   struct container_traits_base<list_update_tag>
 251   {
 252     typedef list_update_tag container_category;
 253     typedef point_invalidation_guarantee invalidation_guarantee;
 254
 255     enum
 256       {
 257         order_preserving = false,
 258         erase_can_throw = false,
 259         split_join_can_throw = false,
 260         reverse_iteration = false
 261       };
 262   };
 263
 264
 265   template<>
 266   struct container_traits_base<pairing_heap_tag>
 267   {
 268     typedef pairing_heap_tag container_category;
 269     typedef point_invalidation_guarantee invalidation_guarantee;
 270
 271     enum
 272       {
 273         order_preserving = false,
 274         erase_can_throw = false,
 275         split_join_can_throw = false,
 276         reverse_iteration = false
 277       };
 278   };
 279
 280   template<>
 281   struct container_traits_base<thin_heap_tag>
 282   {
 283     typedef thin_heap_tag container_category;
 284     typedef point_invalidation_guarantee invalidation_guarantee;
 285
 286     enum
 287       {
 288         order_preserving = false,
 289         erase_can_throw = false,
 290         split_join_can_throw = false,
 291         reverse_iteration = false
 292       };
 293   };
 294
 295   template<>
 296   struct container_traits_base<binomial_heap_tag>
 297   {
 298     typedef binomial_heap_tag container_category;
 299     typedef point_invalidation_guarantee invalidation_guarantee;
 300
 301     enum
 302       {
 303         order_preserving = false,
 304         erase_can_throw = false,
 305         split_join_can_throw = false,
 306         reverse_iteration = false
 307       };
 308   };
 309
 310   template<>
 311   struct container_traits_base<rc_binomial_heap_tag>
 312   {
 313     typedef rc_binomial_heap_tag container_category;
 314     typedef point_invalidation_guarantee invalidation_guarantee;
 315
 316     enum
 317       {
 318         order_preserving = false,
 319         erase_can_throw = false,
 320         split_join_can_throw = false,
 321         reverse_iteration = false
 322       };
 323   };
 324
 325   template<>
 326   struct container_traits_base<binary_heap_tag>
 327   {
 328     typedef binary_heap_tag container_category;
 329     typedef basic_invalidation_guarantee invalidation_guarantee;
 330
 331     enum
 332       {
 333         order_preserving = false,
 334         erase_can_throw = false,
 335         split_join_can_throw = true,
 336         reverse_iteration = false
 337       };
 338   };
 339
 340
 341   // See Matt Austern for the name, S. Meyers MEFC++ #2, others.
 342   template<typename Cntnr>
 343   struct container_traits
 344   : public container_traits_base<typename Cntnr::container_category>
 345   {
 346     typedef Cntnr container_type;
 347     typedef typename Cntnr::container_category container_category;
 348     typedef container_traits_base<container_category> base_type;
 349     typedef typename base_type::invalidation_guarantee invalidation_guarantee;
 350
 351     enum
 352       {
 353         order_preserving = base_type::order_preserving,
 354         erase_can_throw = base_type::erase_can_throw,
 355         split_join_can_throw = base_type::split_join_can_throw,
 356         reverse_iteration = base_type::reverse_iteration
 357       };
 358   };
 359 } // namespace __gnu_pbds
 360
 361 #endif