1// -*- C++ -*-
2
3// Copyright (C) 2005-2015 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
48using namespace std;
49using namespace __gnu_pbds;
50
51template<class DS_Category>
52void
53print_container_category(DS_Category);
54
55template<>
56void
57print_container_category(binary_heap_tag)
58{ cout << "Binary heap:" << endl; }
59
60template<>
61void
62print_container_category(binomial_heap_tag)
63{ cout << "Binomial heap:" << endl; }
64
65template<>
66void
67print_container_category(rc_binomial_heap_tag)
68{ cout << "Redundant-counter binomial heap:" << endl; }
69
70template<>
71void
72print_container_category(pairing_heap_tag)
73{ cout << "Pairing heap:" << endl; }
74
75template<>
76void
77print_container_category(thin_heap_tag)
78{ cout << "Thin heap:" << endl; }
79
80template<class Invalidation_Guarantee>
81void
82print_invalidation_guarantee(Invalidation_Guarantee);
83
84template<>
85void
86print_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
93template<>
94void
95print_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
102template<>
103void
104print_invalidation_guarantee(range_invalidation_guarantee)
105{
106  cout << "Guarantees that iterators remain valid even if the "
107    "container object is modified" << endl;
108}
109
110void
111print_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
121template<class DS_Traits>
122void
123print_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
134int 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}
201