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