libstdc++-v3/testsuite/ext/pb_ds/example/priority_queue_container_traits.cc

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2005-2014 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 // You should have received a copy of the GNU General Public License
  17 // along with this library; see the file COPYING3.  If not see
  18 // <http://www.gnu.org/licenses/>.
  19
  20
  21 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
  22
  23 // Permission to use, copy, modify, sell, and distribute this software
  24 // is hereby granted without fee, provided that the above copyright
  25 // notice appears in all copies, and that both that copyright notice
  26 // and this permission notice appear in supporting documentation. None
  27 // of the above authors, nor IBM Haifa Research Laboratories, make any
  28 // representation about the suitability of this software for any
  29 // purpose. It is provided "as is" without express or implied
  30 // warranty.
  31
  32 /**
  33  * @file priority_queue_container_traits_example.cpp
  34  * A basic example showing how to use container_traits for querying container types
  35  *    for their behavior.
  36  */
  37
  38 /**
  39  * The following example shows how to use container_traits in order to print
  40  * out information on an priority queue's behavior, e.g., its underlying
  41  * data structure.
  42  */
  43
  44 #include <iostream>
  45 #include <ext/pb_ds/priority_queue.hpp>
  46 #include <ext/pb_ds/tag_and_trait.hpp>
  47
  48 using namespace std;
  49 using namespace __gnu_pbds;
  50
  51 template<class DS_Category>
  52 void
  53 print_container_category(DS_Category);
  54
  55 template<>
  56 void
  57 print_container_category(binary_heap_tag)
  58 { cout << "Binary heap:" << endl; }
  59
  60 template<>
  61 void
  62 print_container_category(binomial_heap_tag)
  63 { cout << "Binomial heap:" << endl; }
  64
  65 template<>
  66 void
  67 print_container_category(rc_binomial_heap_tag)
  68 { cout << "Redundant-counter binomial heap:" << endl; }
  69
  70 template<>
  71 void
  72 print_container_category(pairing_heap_tag)
  73 { cout << "Pairing heap:" << endl; }
  74
  75 template<>
  76 void
  77 print_container_category(thin_heap_tag)
  78 { cout << "Thin heap:" << endl; }
  79
  80 template<class Invalidation_Guarantee>
  81 void
  82 print_invalidation_guarantee(Invalidation_Guarantee);
  83
  84 template<>
  85 void
  86 print_invalidation_guarantee(basic_invalidation_guarantee)
  87 {
  88   cout << "Guarantees only that found references, pointers, and "
  89     "iterators are valid as long as the container object is not "
  90     "modified" << endl;
  91 }
  92
  93 template<>
  94 void
  95 print_invalidation_guarantee(point_invalidation_guarantee)
  96 {
  97   cout << "Guarantees that found references, pointers, and "
  98     "point_iterators are valid even if the container object "
  99     "is modified" << endl;
 100 }
 101
 102 template<>
 103 void
 104 print_invalidation_guarantee(range_invalidation_guarantee)
 105 {
 106   cout << "Guarantees that iterators remain valid even if the "
 107     "container object is modified" << endl;
 108 }
 109
 110 void
 111 print_split_join_can_throw(bool can)
 112 {
 113   if (can)
 114     {
 115       cout << "Can throw exceptions if split or joined" << endl;
 116       return;
 117     }
 118   cout << "Cannot throw exceptions if split or joined" << endl;
 119 }
 120
 121 template<class DS_Traits>
 122 void
 123 print_container_attributes()
 124 {
 125   // First print out the data structure category.
 126   print_container_category(typename DS_Traits::container_category());
 127
 128   // Now print the attributes of the container.
 129   print_invalidation_guarantee(typename DS_Traits::invalidation_guarantee());
 130   print_split_join_can_throw(DS_Traits::split_join_can_throw);
 131   cout << endl << endl;
 132 }
 133
 134 int main()
 135 {
 136   {
 137     // Print the attributes of a binary heap.
 138     typedef
 139       __gnu_pbds::priority_queue<
 140       int,
 141       std::less<int>,
 142       binary_heap_tag>
 143       t;
 144
 145     print_container_attributes<container_traits<t> >();
 146   }
 147
 148   {
 149     // Print the attributes of a binomial heap.
 150     typedef
 151       __gnu_pbds::priority_queue<
 152       int,
 153       std::less<int>,
 154       binomial_heap_tag>
 155       t;
 156
 157     print_container_attributes<container_traits<t> >();
 158   }
 159
 160   {
 161     // Print the attributes of a redundant-counter binomial heap.
 162     typedef
 163       __gnu_pbds::priority_queue<
 164       int,
 165       std::less<int>,
 166       rc_binomial_heap_tag>
 167       t;
 168
 169     print_container_attributes<container_traits<t> >();
 170   }
 171
 172   {
 173     // Print the attributes of a pairing heap.
 174     typedef
 175       __gnu_pbds::priority_queue<
 176       int,
 177       std::less<int>,
 178       pairing_heap_tag>
 179       t;
 180
 181     print_container_attributes<container_traits<t> >();
 182   }
 183
 184   {
 185     /**
 186      *  Print the attributes of a thin heap.
 187      */
 188
 189     typedef
 190       __gnu_pbds::priority_queue<
 191       int,
 192       std::less<int>,
 193       thin_heap_tag>
 194       t;
 195
 196     print_container_attributes<container_traits<t> >();
 197   }
 198
 199   return 0;
 200 }