155714Skris// -*- C++ -*- 255714Skris 3279264Sdelphij// Copyright (C) 2005, 2006, 2009 Free Software Foundation, Inc. 455714Skris// 555714Skris// This file is part of the GNU ISO C++ Library. This library is free 655714Skris// software; you can redistribute it and/or modify it under the terms 755714Skris// of the GNU General Public License as published by the Free Software 855714Skris// Foundation; either version 3, or (at your option) any later 955714Skris// version. 10296341Sdelphij 1155714Skris// This library is distributed in the hope that it will be useful, but 1255714Skris// WITHOUT ANY WARRANTY; without even the implied warranty of 1355714Skris// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 1455714Skris// General Public License for more details. 1555714Skris 1655714Skris// You should have received a copy of the GNU General Public License 1755714Skris// along with this library; see the file COPYING3. If not see 1855714Skris// <http://www.gnu.org/licenses/>. 1955714Skris 2055714Skris 2155714Skris// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 2255714Skris 2355714Skris// Permission to use, copy, modify, sell, and distribute this software 2455714Skris// is hereby granted without fee, provided that the above copyright 2555714Skris// notice appears in all copies, and that both that copyright notice 2655714Skris// and this permission notice appear in supporting documentation. None 2755714Skris// of the above authors, nor IBM Haifa Research Laboratories, make any 2855714Skris// representation about the suitability of this software for any 2955714Skris// purpose. It is provided "as is" without express or implied 3055714Skris// warranty. 3155714Skris 3255714Skris/** 3355714Skris * This example shows how to use priority queues. It defines a 3455714Skris * function performing a sequence of operations on 3555714Skris * a generic container. It then calls this function with some containers. 3655714Skris */ 3755714Skris 3855714Skris#include <ext/pb_ds/priority_queue.hpp> 3955714Skris#include <iostream> 4055714Skris#include <cassert> 4155714Skris 4255714Skrisusing namespace std; 4355714Skrisusing namespace __gnu_pbds; 4455714Skrisusing namespace __gnu_pbds; 4555714Skris 4655714Skristemplate<typename Cntnr> 4755714Skrisvoid 4855714Skrissome_op_sequence(Cntnr& r_c) 4955714Skris{ 5055714Skris assert(r_c.empty()); 5155714Skris assert(r_c.size() == 0); 5255714Skris 5355714Skris for (size_t i = 0; i < 10; ++i) 5455714Skris r_c.push(i); 5555714Skris 56296341Sdelphij cout << endl << "All values in the container:" << endl; 57296341Sdelphij for (typename Cntnr::const_iterator it = r_c.begin(); it != r_c.end(); 5859191Skris ++it) 5959191Skris cout <<* it << endl; 6055714Skris 6155714Skris assert(!r_c.empty()); 6255714Skris assert(r_c.size() == 10); 6355714Skris 6455714Skris cout << "Popping all values: " << endl; 6555714Skris 6655714Skris while (!r_c.empty()) 67109998Smarkm { 68160814Ssimon cout << r_c.top() << endl; 69296341Sdelphij 70296341Sdelphij r_c.pop(); 71160814Ssimon } 72296341Sdelphij 73296341Sdelphij assert(r_c.empty()); 74296341Sdelphij assert(r_c.size() == 0); 75296341Sdelphij 76296341Sdelphij cout << endl; 77296341Sdelphij} 78296341Sdelphij 79296341Sdelphijvoid 80296341Sdelphijpriority_queue_link_regression_test_0() 81296341Sdelphij{ 82296341Sdelphij { 83296341Sdelphij /* 84296341Sdelphij * Perform operations on a pairing-heap queue. 85296341Sdelphij */ 86296341Sdelphij cout << "Pairing heap" << endl; 87296341Sdelphij __gnu_pbds::priority_queue<int, less<int>, pairing_heap_tag> c; 88296341Sdelphij some_op_sequence(c); 89296341Sdelphij } 90296341Sdelphij 91296341Sdelphij { 92296341Sdelphij /* 93296341Sdelphij * Perform operations on a binomial-heap queue. 94296341Sdelphij */ 95296341Sdelphij cout << "Binomial heap" << endl; 96296341Sdelphij __gnu_pbds::priority_queue<int, less<int>, binomial_heap_tag> c; 97296341Sdelphij some_op_sequence(c); 98296341Sdelphij } 99296341Sdelphij 100296341Sdelphij { 101296341Sdelphij /* 102296341Sdelphij * Perform operations on a binomial-heap queue. 103296341Sdelphij */ 104296341Sdelphij cout << "Redundant-counter binomial heap" << endl; 105296341Sdelphij __gnu_pbds::priority_queue<int, less<int>, rc_binomial_heap_tag> c; 106296341Sdelphij some_op_sequence(c); 107296341Sdelphij } 108296341Sdelphij 109296341Sdelphij { 110296341Sdelphij /* 111296341Sdelphij * Perform operations on a binomial-heap queue. 112296341Sdelphij */ 113296341Sdelphij cout << "Binary heap" << endl; 114296341Sdelphij __gnu_pbds::priority_queue<int, less<int>, binary_heap_tag> c; 115296341Sdelphij some_op_sequence(c); 116296341Sdelphij } 117296341Sdelphij 118296341Sdelphij { 119296341Sdelphij /* 120296341Sdelphij * Perform operations on a thin-heap queue. 121296341Sdelphij */ 122296341Sdelphij cout << "Thin heap" << endl; 123296341Sdelphij __gnu_pbds::priority_queue<int, less<int>, thin_heap_tag> c; 124296341Sdelphij some_op_sequence(c); 125296341Sdelphij } 126296341Sdelphij} 127296341Sdelphij 128296341Sdelphij 129296341Sdelphijvoid 130296341Sdelphijpriority_queue_link_regression_test_1() 131296341Sdelphij{ 132296341Sdelphij { 133296341Sdelphij /* 134296341Sdelphij * Perform operations on a pairing-heap queue. 135296341Sdelphij */ 136296341Sdelphij cout << "Pairing heap" << endl; 137296341Sdelphij __gnu_pbds::priority_queue<int, less<int>, pairing_heap_tag> c; 138296341Sdelphij some_op_sequence(c); 139296341Sdelphij } 140296341Sdelphij 141296341Sdelphij { 142296341Sdelphij /* 143296341Sdelphij * Perform operations on a binomial-heap queue. 144296341Sdelphij */ 145296341Sdelphij cout << "Binomial heap" << endl; 146296341Sdelphij __gnu_pbds::priority_queue<int, less<int>, binomial_heap_tag> c; 147296341Sdelphij some_op_sequence(c); 148296341Sdelphij } 149296341Sdelphij 150296341Sdelphij { 151296341Sdelphij /* 152296341Sdelphij * Perform operations on a binomial-heap queue. 153296341Sdelphij */ 154296341Sdelphij cout << "Redundant-counter binomial heap" << endl; 155296341Sdelphij __gnu_pbds::priority_queue<int, less<int>, rc_binomial_heap_tag> c; 156296341Sdelphij some_op_sequence(c); 157296341Sdelphij } 158296341Sdelphij 159296341Sdelphij { 160296341Sdelphij /* 161296341Sdelphij * Perform operations on a binomial-heap queue. 162296341Sdelphij */ 163296341Sdelphij cout << "Binary heap" << endl; 164296341Sdelphij __gnu_pbds::priority_queue<int, less<int>, binary_heap_tag> c; 165296341Sdelphij some_op_sequence(c); 166296341Sdelphij } 167296341Sdelphij 168296341Sdelphij { 169296341Sdelphij /* 170296341Sdelphij * Perform operations on a thin-heap queue. 171296341Sdelphij */ 172296341Sdelphij cout << "Thin heap" << endl; 173296341Sdelphij __gnu_pbds::priority_queue<int, less<int>, thin_heap_tag> c; 174296341Sdelphij some_op_sequence(c); 175296341Sdelphij } 176296341Sdelphij} 177296341Sdelphij 178296341Sdelphijint 179296341Sdelphijmain() 180296341Sdelphij{ 181296341Sdelphij priority_queue_link_regression_test_0(); 182296341Sdelphij priority_queue_link_regression_test_1(); 183296341Sdelphij return 0; 184296341Sdelphij} 185296341Sdelphij