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// Under Section 7 of GPL version 3, you are granted additional 17// permissions described in the GCC Runtime Library Exception, version 18// 3.1, as published by the Free Software Foundation. 19 20// You should have received a copy of the GNU General Public License and 21// a copy of the GCC Runtime Library Exception along with this program; 22// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 23// <http://www.gnu.org/licenses/>. 24 25// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 26 27// Permission to use, copy, modify, sell, and distribute this software 28// is hereby granted without fee, provided that the above copyright 29// notice appears in all copies, and that both that copyright notice 30// and this permission notice appear in supporting documentation. None 31// of the above authors, nor IBM Haifa Research Laboratories, make any 32// representation about the suitability of this software for any 33// purpose. It is provided "as is" without express or implied 34// warranty. 35 36/** 37 * @file priority_queue.hpp 38 * Contains priority_queues. 39 */ 40 41#ifndef PB_DS_PRIORITY_QUEUE_HPP 42#define PB_DS_PRIORITY_QUEUE_HPP 43 44#include <ext/pb_ds/tag_and_trait.hpp> 45#include <ext/pb_ds/detail/priority_queue_base_dispatch.hpp> 46#include <ext/pb_ds/detail/standard_policies.hpp> 47 48namespace __gnu_pbds 49{ 50 // A priority queue. 51 template<typename Value_Type, 52 typename Cmp_Fn = std::less<Value_Type>, 53 typename Tag = pairing_heap_tag, 54 typename Allocator = std::allocator<char> > 55 class priority_queue 56 : public detail::priority_queue_base_dispatch<Value_Type,Cmp_Fn,Tag,Allocator>::type 57 { 58 private: 59 typedef typename detail::priority_queue_base_dispatch<Value_Type,Cmp_Fn,Tag,Allocator>::type base_type; 60 61 public: 62 typedef Value_Type value_type; 63 typedef Cmp_Fn cmp_fn; 64 typedef Tag container_category; 65 typedef Allocator allocator_type; 66 typedef typename allocator_type::size_type size_type; 67 typedef typename allocator_type::difference_type difference_type; 68 69 typedef typename allocator_type::template rebind<value_type>::other value_rebind; 70 typedef typename value_rebind::reference reference; 71 typedef typename value_rebind::const_reference const_reference; 72 typedef typename value_rebind::pointer pointer; 73 typedef typename value_rebind::const_pointer const_pointer; 74 75 typedef typename base_type::const_point_iterator const_point_iterator; 76 typedef typename base_type::point_iterator point_iterator; 77 typedef typename base_type::const_iterator const_iterator; 78 typedef typename base_type::iterator iterator; 79 80 priority_queue() { } 81 82 // Constructor taking some policy objects. r_cmp_fn will be copied 83 // by the Cmp_Fn object of the container object. 84 priority_queue(const cmp_fn& r_cmp_fn) : base_type(r_cmp_fn) { } 85 86 // Constructor taking __iterators to a range of value_types. The 87 // value_types between first_it and last_it will be inserted into 88 // the container object. 89 template<typename It> 90 priority_queue(It first_it, It last_it) 91 { base_type::copy_from_range(first_it, last_it); } 92 93 // Constructor taking __iterators to a range of value_types and 94 // some policy objects The value_types between first_it and 95 // last_it will be inserted into the container object. r_cmp_fn 96 // will be copied by the cmp_fn object of the container object. 97 template<typename It> 98 priority_queue(It first_it, It last_it, const cmp_fn& r_cmp_fn) 99 : base_type(r_cmp_fn) 100 { base_type::copy_from_range(first_it, last_it); } 101 102 priority_queue(const priority_queue& other) 103 : base_type((const base_type& )other) { } 104 105 virtual 106 ~priority_queue() { } 107 108 priority_queue& 109 operator=(const priority_queue& other) 110 { 111 if (this != &other) 112 { 113 priority_queue tmp(other); 114 swap(tmp); 115 } 116 return *this; 117 } 118 119 void 120 swap(priority_queue& other) 121 { base_type::swap(other); } 122 }; 123} // namespace __gnu_pbds 124 125#endif 126