priority_queues.cc revision 1.1.1.1
1// -*- C++ -*- 2 3// Copyright (C) 2005, 2006, 2009 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 * This example shows how to use priority queues. It defines a 34 * function performing a sequence of operations on 35 * a generic container. It then calls this function with some containers. 36 */ 37 38#include <ext/pb_ds/priority_queue.hpp> 39#include <iostream> 40#include <cassert> 41 42using namespace std; 43using namespace __gnu_pbds; 44using namespace __gnu_pbds; 45 46template<typename Cntnr> 47void 48some_op_sequence(Cntnr& r_c) 49{ 50 assert(r_c.empty()); 51 assert(r_c.size() == 0); 52 53 for (size_t i = 0; i < 10; ++i) 54 r_c.push(i); 55 56 cout << endl << "All values in the container:" << endl; 57 for (typename Cntnr::const_iterator it = r_c.begin(); it != r_c.end(); 58 ++it) 59 cout <<* it << endl; 60 61 assert(!r_c.empty()); 62 assert(r_c.size() == 10); 63 64 cout << "Popping all values: " << endl; 65 66 while (!r_c.empty()) 67 { 68 cout << r_c.top() << endl; 69 70 r_c.pop(); 71 } 72 73 assert(r_c.empty()); 74 assert(r_c.size() == 0); 75 76 cout << endl; 77} 78 79void 80priority_queue_link_regression_test_0() 81{ 82 { 83 /* 84 * Perform operations on a pairing-heap queue. 85 */ 86 cout << "Pairing heap" << endl; 87 __gnu_pbds::priority_queue<int, less<int>, pairing_heap_tag> c; 88 some_op_sequence(c); 89 } 90 91 { 92 /* 93 * Perform operations on a binomial-heap queue. 94 */ 95 cout << "Binomial heap" << endl; 96 __gnu_pbds::priority_queue<int, less<int>, binomial_heap_tag> c; 97 some_op_sequence(c); 98 } 99 100 { 101 /* 102 * Perform operations on a binomial-heap queue. 103 */ 104 cout << "Redundant-counter binomial heap" << endl; 105 __gnu_pbds::priority_queue<int, less<int>, rc_binomial_heap_tag> c; 106 some_op_sequence(c); 107 } 108 109 { 110 /* 111 * Perform operations on a binomial-heap queue. 112 */ 113 cout << "Binary heap" << endl; 114 __gnu_pbds::priority_queue<int, less<int>, binary_heap_tag> c; 115 some_op_sequence(c); 116 } 117 118 { 119 /* 120 * Perform operations on a thin-heap queue. 121 */ 122 cout << "Thin heap" << endl; 123 __gnu_pbds::priority_queue<int, less<int>, thin_heap_tag> c; 124 some_op_sequence(c); 125 } 126} 127 128 129void 130priority_queue_link_regression_test_1() 131{ 132 { 133 /* 134 * Perform operations on a pairing-heap queue. 135 */ 136 cout << "Pairing heap" << endl; 137 __gnu_pbds::priority_queue<int, less<int>, pairing_heap_tag> c; 138 some_op_sequence(c); 139 } 140 141 { 142 /* 143 * Perform operations on a binomial-heap queue. 144 */ 145 cout << "Binomial heap" << endl; 146 __gnu_pbds::priority_queue<int, less<int>, binomial_heap_tag> c; 147 some_op_sequence(c); 148 } 149 150 { 151 /* 152 * Perform operations on a binomial-heap queue. 153 */ 154 cout << "Redundant-counter binomial heap" << endl; 155 __gnu_pbds::priority_queue<int, less<int>, rc_binomial_heap_tag> c; 156 some_op_sequence(c); 157 } 158 159 { 160 /* 161 * Perform operations on a binomial-heap queue. 162 */ 163 cout << "Binary heap" << endl; 164 __gnu_pbds::priority_queue<int, less<int>, binary_heap_tag> c; 165 some_op_sequence(c); 166 } 167 168 { 169 /* 170 * Perform operations on a thin-heap queue. 171 */ 172 cout << "Thin heap" << endl; 173 __gnu_pbds::priority_queue<int, less<int>, thin_heap_tag> c; 174 some_op_sequence(c); 175 } 176} 177 178int 179main() 180{ 181 priority_queue_link_regression_test_0(); 182 priority_queue_link_regression_test_1(); 183 return 0; 184} 185