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

Generated on Thu Nov 1 13:12:45 2007 for libstdc++ by  doxygen 1.5.1