163d1a8abSmrg // -*- C++ -*- 263d1a8abSmrg 3*ec02198aSmrg // Copyright (C) 2005-2020 Free Software Foundation, Inc. 463d1a8abSmrg // 563d1a8abSmrg // This file is part of the GNU ISO C++ Library. This library is free 663d1a8abSmrg // software; you can redistribute it and/or modify it under the terms 763d1a8abSmrg // of the GNU General Public License as published by the Free Software 863d1a8abSmrg // Foundation; either version 3, or (at your option) any later 963d1a8abSmrg // version. 1063d1a8abSmrg 1163d1a8abSmrg // This library is distributed in the hope that it will be useful, but 1263d1a8abSmrg // WITHOUT ANY WARRANTY; without even the implied warranty of 1363d1a8abSmrg // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 1463d1a8abSmrg // General Public License for more details. 1563d1a8abSmrg 1663d1a8abSmrg // Under Section 7 of GPL version 3, you are granted additional 1763d1a8abSmrg // permissions described in the GCC Runtime Library Exception, version 1863d1a8abSmrg // 3.1, as published by the Free Software Foundation. 1963d1a8abSmrg 2063d1a8abSmrg // You should have received a copy of the GNU General Public License and 2163d1a8abSmrg // a copy of the GCC Runtime Library Exception along with this program; 2263d1a8abSmrg // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 2363d1a8abSmrg // <http://www.gnu.org/licenses/>. 2463d1a8abSmrg 2563d1a8abSmrg // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 2663d1a8abSmrg 2763d1a8abSmrg // Permission to use, copy, modify, sell, and distribute this software 2863d1a8abSmrg // is hereby granted without fee, provided that the above copyright 2963d1a8abSmrg // notice appears in all copies, and that both that copyright notice 3063d1a8abSmrg // and this permission notice appear in supporting documentation. None 3163d1a8abSmrg // of the above authors, nor IBM Haifa Research Laboratories, make any 3263d1a8abSmrg // representation about the suitability of this software for any 3363d1a8abSmrg // purpose. It is provided "as is" without express or implied 3463d1a8abSmrg // warranty. 3563d1a8abSmrg 3663d1a8abSmrg /** 3763d1a8abSmrg * @file priority_queue.hpp 3863d1a8abSmrg * Contains priority_queues. 3963d1a8abSmrg */ 4063d1a8abSmrg 4163d1a8abSmrg #ifndef PB_DS_PRIORITY_QUEUE_HPP 4263d1a8abSmrg #define PB_DS_PRIORITY_QUEUE_HPP 4363d1a8abSmrg 4463d1a8abSmrg #include <bits/c++config.h> 4563d1a8abSmrg #include <ext/pb_ds/tag_and_trait.hpp> 4663d1a8abSmrg #include <ext/pb_ds/detail/priority_queue_base_dispatch.hpp> 4763d1a8abSmrg #include <ext/pb_ds/detail/standard_policies.hpp> 4863d1a8abSmrg 4963d1a8abSmrg namespace __gnu_pbds 5063d1a8abSmrg { 5163d1a8abSmrg /** 5263d1a8abSmrg * @defgroup heap-based Heap-Based 5363d1a8abSmrg * @ingroup containers-pbds 54*ec02198aSmrg * 5563d1a8abSmrg * @{ 5663d1a8abSmrg */ 5763d1a8abSmrg 5863d1a8abSmrg /** 5963d1a8abSmrg * @defgroup heap-detail Base and Policy Classes 6063d1a8abSmrg * @ingroup heap-based 6163d1a8abSmrg */ 6263d1a8abSmrg 6363d1a8abSmrg /** 6463d1a8abSmrg * A priority queue composed of one specific heap policy. 6563d1a8abSmrg * 6663d1a8abSmrg * @tparam _Tv Value type. 6763d1a8abSmrg * @tparam Cmp_Fn Comparison functor. 6863d1a8abSmrg * @tparam Tag Instantiating data structure type, 6963d1a8abSmrg * see container_tag. 7063d1a8abSmrg * @tparam _Alloc Allocator type. 7163d1a8abSmrg * 7263d1a8abSmrg * Base is dispatched at compile time via Tag, from the following 7363d1a8abSmrg * choices: binary_heap_tag, binomial_heap_tag, pairing_heap_tag, 7463d1a8abSmrg * rc_binomial_heap_tag, thin_heap_tag 7563d1a8abSmrg * 7663d1a8abSmrg * Base choices are: detail::binary_heap, detail::binomial_heap, 7763d1a8abSmrg * detail::pairing_heap, detail::rc_binomial_heap, 7863d1a8abSmrg * detail::thin_heap. 7963d1a8abSmrg */ 8063d1a8abSmrg template<typename _Tv, 8163d1a8abSmrg typename Cmp_Fn = std::less<_Tv>, 8263d1a8abSmrg typename Tag = pairing_heap_tag, 8363d1a8abSmrg typename _Alloc = std::allocator<char> > 8463d1a8abSmrg class priority_queue 8563d1a8abSmrg : public detail::container_base_dispatch<_Tv, Cmp_Fn, _Alloc, Tag>::type 8663d1a8abSmrg { 8763d1a8abSmrg public: 8863d1a8abSmrg typedef _Tv value_type; 8963d1a8abSmrg typedef Cmp_Fn cmp_fn; 9063d1a8abSmrg typedef Tag container_category; 9163d1a8abSmrg typedef _Alloc allocator_type; 9263d1a8abSmrg typedef typename allocator_type::size_type size_type; 9363d1a8abSmrg typedef typename allocator_type::difference_type difference_type; 9463d1a8abSmrg 9563d1a8abSmrg private: 9663d1a8abSmrg typedef typename detail::container_base_dispatch<_Tv, Cmp_Fn, _Alloc, 9763d1a8abSmrg Tag>::type 9863d1a8abSmrg base_type; 99*ec02198aSmrg typedef detail::rebind_traits<_Alloc, _Tv> __rebind_va; 10063d1a8abSmrg 10163d1a8abSmrg public: 10263d1a8abSmrg typedef typename __rebind_va::reference reference; 10363d1a8abSmrg typedef typename __rebind_va::const_reference const_reference; 10463d1a8abSmrg typedef typename __rebind_va::pointer pointer; 10563d1a8abSmrg typedef typename __rebind_va::const_pointer const_pointer; 10663d1a8abSmrg 10763d1a8abSmrg typedef typename base_type::point_iterator point_iterator; 10863d1a8abSmrg typedef typename base_type::point_const_iterator point_const_iterator; 10963d1a8abSmrg typedef typename base_type::iterator iterator; 11063d1a8abSmrg typedef typename base_type::const_iterator const_iterator; 11163d1a8abSmrg priority_queue()11263d1a8abSmrg priority_queue() { } 11363d1a8abSmrg 11463d1a8abSmrg /// Constructor taking some policy objects. r_cmp_fn will be 11563d1a8abSmrg /// copied by the Cmp_Fn object of the container object. priority_queue(const cmp_fn & r_cmp_fn)11663d1a8abSmrg priority_queue(const cmp_fn& r_cmp_fn) : base_type(r_cmp_fn) { } 11763d1a8abSmrg 11863d1a8abSmrg /// Constructor taking __iterators to a range of value_types. The 11963d1a8abSmrg /// value_types between first_it and last_it will be inserted into 12063d1a8abSmrg /// the container object. 12163d1a8abSmrg template<typename It> priority_queue(It first_it,It last_it)12263d1a8abSmrg priority_queue(It first_it, It last_it) 12363d1a8abSmrg { base_type::copy_from_range(first_it, last_it); } 12463d1a8abSmrg 12563d1a8abSmrg /// Constructor taking __iterators to a range of value_types and 12663d1a8abSmrg /// some policy objects The value_types between first_it and 12763d1a8abSmrg /// last_it will be inserted into the container object. r_cmp_fn 12863d1a8abSmrg /// will be copied by the cmp_fn object of the container object. 12963d1a8abSmrg template<typename It> priority_queue(It first_it,It last_it,const cmp_fn & r_cmp_fn)13063d1a8abSmrg priority_queue(It first_it, It last_it, const cmp_fn& r_cmp_fn) 13163d1a8abSmrg : base_type(r_cmp_fn) 13263d1a8abSmrg { base_type::copy_from_range(first_it, last_it); } 13363d1a8abSmrg priority_queue(const priority_queue & other)13463d1a8abSmrg priority_queue(const priority_queue& other) 13563d1a8abSmrg : base_type((const base_type& )other) { } 13663d1a8abSmrg 13763d1a8abSmrg virtual ~priority_queue()13863d1a8abSmrg ~priority_queue() { } 13963d1a8abSmrg 14063d1a8abSmrg priority_queue& operator =(const priority_queue & other)14163d1a8abSmrg operator=(const priority_queue& other) 14263d1a8abSmrg { 14363d1a8abSmrg if (this != &other) 14463d1a8abSmrg { 14563d1a8abSmrg priority_queue tmp(other); 14663d1a8abSmrg swap(tmp); 14763d1a8abSmrg } 14863d1a8abSmrg return *this; 14963d1a8abSmrg } 15063d1a8abSmrg 15163d1a8abSmrg void swap(priority_queue & other)15263d1a8abSmrg swap(priority_queue& other) 15363d1a8abSmrg { base_type::swap(other); } 15463d1a8abSmrg }; 155*ec02198aSmrg ///@} heap-based 15663d1a8abSmrg } // namespace __gnu_pbds 15763d1a8abSmrg #endif 158