# tag_and_trait.hpp

Go to the documentation of this file.

    00001 // -*- C++ -*-
    00002
    00003 // Copyright (C) 2005, 2006 Free Software Foundation, Inc.
    00004 //
    00005 // This file is part of the GNU ISO C++ Library.  This library is free
    00006 // software; you can redistribute it and/or modify it under the terms
    00007 // of the GNU General Public License as published by the Free Software
    00008 // Foundation; either version 2, or (at your option) any later
    00009 // version.
    00010
    00011 // This library is distributed in the hope that it will be useful, but
    00012 // WITHOUT ANY WARRANTY; without even the implied warranty of
    00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
    00014 // General Public License for more details.
    00015
    00016 // You should have received a copy of the GNU General Public License
    00017 // along with this library; see the file COPYING.  If not, write to
    00018 // the Free Software Foundation, 59 Temple Place - Suite 330, Boston,
    00019 // MA 02111-1307, USA.
    00020
    00021 // As a special exception, you may use this file as part of a free
    00022 // software library without restriction.  Specifically, if other files
    00023 // instantiate templates or use macros or inline functions from this
    00024 // file, or you compile this file and link it with other files to
    00025 // produce an executable, this file does not by itself cause the
    00026 // resulting executable to be covered by the GNU General Public
    00027 // License.  This exception does not however invalidate any other
    00028 // reasons why the executable file might be covered by the GNU General
    00029 // Public License.
    00030
    00031 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
    00032
    00033 // Permission to use, copy, modify, sell, and distribute this software
    00034 // is hereby granted without fee, provided that the above copyright
    00035 // notice appears in all copies, and that both that copyright notice
    00036 // and this permission notice appear in supporting documentation. None
    00037 // of the above authors, nor IBM Haifa Research Laboratories, make any
    00038 // representation about the suitability of this software for any
    00039 // purpose. It is provided "as is" without express or implied
    00040 // warranty.
    00041
    00042 /**
    00043  * @file tag_and_trait.hpp
    00044  * Contains tags and traits, e.g., ones describing underlying
    00045  *    data structures.
    00046  */
    00047
    00048 #ifndef PB_DS_TAG_AND_TRAIT_HPP
    00049 #define PB_DS_TAG_AND_TRAIT_HPP
    00050
    00051 #include <ext/pb_ds/detail/type_utils.hpp>
    00052
    00053 namespace pb_ds
    00054 {
    00055   // A trivial iterator tag. Signifies that the iterators has none of
    00056   // the STL's movement abilities.
    00057   struct trivial_iterator_tag
    00058   { };
    00059
    00060   // Prohibit moving trivial iterators.
    00061   typedef void trivial_iterator_difference_type;
    00062
    00063
    00064   // Signifies a basic invalidation guarantee that any iterator,
    00065   // pointer, or reference to a container object's mapped value type
    00066   // is valid as long as the container is not modified.
    00067   struct basic_invalidation_guarantee
    00068   { };
    00069
    00070   // Signifies an invalidation guarantee that includes all those of
    00071   // its base, and additionally, that any point-type iterator,
    00072   // pointer, or reference to a container object's mapped value type
    00073   // is valid as long as its corresponding entry has not be erased,
    00074   // regardless of modifications to the container object.
    00075   struct point_invalidation_guarantee : public basic_invalidation_guarantee
    00076   { };
    00077
    00078   // Signifies an invalidation guarantee that includes all those of
    00079   // its base, and additionally, that any range-type iterator
    00080   // (including the returns of begin() and end()) is in the correct
    00081   // relative positions to other range-type iterators as long as its
    00082   // corresponding entry has not be erased, regardless of
    00083   // modifications to the container object.
    00084   struct range_invalidation_guarantee : public point_invalidation_guarantee
    00085   { };
    00086
    00087
    00088   // A mapped-policy indicating that an associative container is a set.
    00089   // XXX should this be a trait of the form is_set<T> ??
    00090   struct null_mapped_type { };
    00091
    00092
    00093   // Base data structure tag.
    00094   struct container_tag
    00095   { };
    00096
    00097   // Basic associative-container.
    00098   struct associative_container_tag : public container_tag { };
    00099
    00100   // Basic hash.
    00101   struct basic_hash_tag : public associative_container_tag { };
    00102
    00103   // Collision-chaining hash.
    00104   struct cc_hash_tag : public basic_hash_tag { };
    00105
    00106   // General-probing hash.
    00107   struct gp_hash_tag : public basic_hash_tag { };
    00108
    00109   // Basic tree.
    00110   struct basic_tree_tag : public associative_container_tag { };
    00111
    00112   // tree.
    00113   struct tree_tag : public basic_tree_tag { };
    00114
    00115   // Red-black tree.
    00116   struct rb_tree_tag : public tree_tag { };
    00117
    00118   // Splay tree.
    00119   struct splay_tree_tag : public tree_tag { };
    00120
    00121   // Ordered-vector tree.
    00122   struct ov_tree_tag : public tree_tag { };
    00123
    00124   // trie.
    00125   struct trie_tag : public basic_tree_tag { };
    00126
    00127   // PATRICIA trie.
    00128   struct pat_trie_tag : public trie_tag { };
    00129
    00130   // List-update.
    00131   struct list_update_tag : public associative_container_tag { };
    00132
    00133   // Basic priority-queue.
    00134   struct priority_queue_tag : public container_tag { };
    00135
    00136   // Pairing-heap.
    00137   struct pairing_heap_tag : public priority_queue_tag { };
    00138
    00139   // Binomial-heap.
    00140   struct binomial_heap_tag : public priority_queue_tag { };
    00141
    00142   // Redundant-counter binomial-heap.
    00143   struct rc_binomial_heap_tag : public priority_queue_tag { };
    00144
    00145   // Binary-heap (array-based).
    00146   struct binary_heap_tag : public priority_queue_tag { };
    00147
    00148   // Thin heap.
    00149   struct thin_heap_tag : public priority_queue_tag { };
    00150
    00151
    00152   template<typename Tag>
    00153   struct container_traits_base;
    00154
    00155   template<>
    00156   struct container_traits_base<cc_hash_tag>
    00157   {
    00158     typedef cc_hash_tag container_category;
    00159     typedef point_invalidation_guarantee invalidation_guarantee;
    00160
    00161     enum
    00162       {
    00163         order_preserving = false,
    00164         erase_can_throw = false,
    00165     split_join_can_throw = false,
    00166     reverse_iteration = false
    00167       };
    00168   };
    00169
    00170   template<>
    00171   struct container_traits_base<gp_hash_tag>
    00172   {
    00173     typedef gp_hash_tag container_category;
    00174     typedef basic_invalidation_guarantee invalidation_guarantee;
    00175
    00176     enum
    00177       {
    00178         order_preserving = false,
    00179     erase_can_throw = false,
    00180     split_join_can_throw = false,
    00181     reverse_iteration = false
    00182       };
    00183   };
    00184
    00185   template<>
    00186   struct container_traits_base<rb_tree_tag>
    00187   {
    00188     typedef rb_tree_tag container_category;
    00189     typedef range_invalidation_guarantee invalidation_guarantee;
    00190
    00191     enum
    00192       {
    00193         order_preserving = true,
    00194         erase_can_throw = false,
    00195     split_join_can_throw = false,
    00196         reverse_iteration = true
    00197       };
    00198   };
    00199
    00200   template<>
    00201   struct container_traits_base<splay_tree_tag>
    00202   {
    00203     typedef splay_tree_tag container_category;
    00204     typedef range_invalidation_guarantee invalidation_guarantee;
    00205
    00206     enum
    00207       {
    00208         order_preserving = true,
    00209         erase_can_throw = false,
    00210         split_join_can_throw = false,
    00211         reverse_iteration = true
    00212       };
    00213   };
    00214
    00215   template<>
    00216   struct container_traits_base<ov_tree_tag>
    00217   {
    00218     typedef ov_tree_tag container_category;
    00219     typedef basic_invalidation_guarantee invalidation_guarantee;
    00220
    00221     enum
    00222       {
    00223         order_preserving = true,
    00224         erase_can_throw = true,
    00225         split_join_can_throw = true,
    00226         reverse_iteration = false
    00227       };
    00228   };
    00229
    00230   template<>
    00231   struct container_traits_base<pat_trie_tag>
    00232   {
    00233     typedef pat_trie_tag container_category;
    00234     typedef range_invalidation_guarantee invalidation_guarantee;
    00235
    00236     enum
    00237       {
    00238         order_preserving = true,
    00239         erase_can_throw = false,
    00240         split_join_can_throw = true,
    00241         reverse_iteration = true
    00242       };
    00243   };
    00244
    00245   template<>
    00246   struct container_traits_base<list_update_tag>
    00247   {
    00248     typedef list_update_tag container_category;
    00249     typedef point_invalidation_guarantee invalidation_guarantee;
    00250
    00251     enum
    00252       {
    00253         order_preserving = false,
    00254         erase_can_throw = false,
    00255     split_join_can_throw = false,
    00256         reverse_iteration = false
    00257       };
    00258   };
    00259
    00260
    00261   template<>
    00262   struct container_traits_base<pairing_heap_tag>
    00263   {
    00264     typedef pairing_heap_tag container_category;
    00265     typedef point_invalidation_guarantee invalidation_guarantee;
    00266
    00267     enum
    00268       {
    00269         order_preserving = false,
    00270         erase_can_throw = false,
    00271     split_join_can_throw = false,
    00272         reverse_iteration = false
    00273       };
    00274   };
    00275
    00276   template<>
    00277   struct container_traits_base<thin_heap_tag>
    00278   {
    00279     typedef thin_heap_tag container_category;
    00280     typedef point_invalidation_guarantee invalidation_guarantee;
    00281
    00282     enum
    00283       {
    00284         order_preserving = false,
    00285         erase_can_throw = false,
    00286     split_join_can_throw = false,
    00287         reverse_iteration = false
    00288       };
    00289   };
    00290
    00291   template<>
    00292   struct container_traits_base<binomial_heap_tag>
    00293   {
    00294     typedef binomial_heap_tag container_category;
    00295     typedef point_invalidation_guarantee invalidation_guarantee;
    00296
    00297     enum
    00298       {
    00299         order_preserving = false,
    00300         erase_can_throw = false,
    00301     split_join_can_throw = false,
    00302         reverse_iteration = false
    00303       };
    00304   };
    00305
    00306   template<>
    00307   struct container_traits_base<rc_binomial_heap_tag>
    00308   {
    00309     typedef rc_binomial_heap_tag container_category;
    00310     typedef point_invalidation_guarantee invalidation_guarantee;
    00311
    00312     enum
    00313       {
    00314         order_preserving = false,
    00315         erase_can_throw = false,
    00316     split_join_can_throw = false,
    00317         reverse_iteration = false
    00318       };
    00319   };
    00320
    00321   template<>
    00322   struct container_traits_base<binary_heap_tag>
    00323   {
    00324     typedef binary_heap_tag container_category;
    00325     typedef basic_invalidation_guarantee invalidation_guarantee;
    00326
    00327     enum
    00328       {
    00329         order_preserving = false,
    00330         erase_can_throw = false,
    00331     split_join_can_throw = true,
    00332         reverse_iteration = false
    00333       };
    00334   };
    00335
    00336
    00337   // See Matt Austern for the name, S. Meyers MEFC++ #2, others.
    00338   template<typename Cntnr>
    00339   struct container_traits
    00340   : public container_traits_base<typename Cntnr::container_category>
    00341   {
    00342     typedef Cntnr container_type;
    00343     typedef typename Cntnr::container_category container_category;
    00344     typedef container_traits_base<container_category> base_type;
    00345     typedef typename base_type::invalidation_guarantee invalidation_guarantee;
    00346
    00347     enum
    00348       {
    00349     order_preserving = base_type::order_preserving,
    00350     erase_can_throw = base_type::erase_can_throw,
    00351     split_join_can_throw = base_type::split_join_can_throw,
    00352     reverse_iteration = base_type::reverse_iteration
    00353       };
    00354   };
    00355 } // namespace pb_ds
    00356
    00357 #endif