1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
|
// -*- C++ -*-
// Copyright (C) 2005-2015 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library. This library is free
// software; you can redistribute it and/or modify it under the terms
// of the GNU General Public License as published by the Free Software
// Foundation; either version 3, or (at your option) any later
// version.
// This library is distributed in the hope that it will be useful, but
// WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
// General Public License for more details.
// Under Section 7 of GPL version 3, you are granted additional
// permissions described in the GCC Runtime Library Exception, version
// 3.1, as published by the Free Software Foundation.
// You should have received a copy of the GNU General Public License and
// a copy of the GCC Runtime Library Exception along with this program;
// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
// <http://www.gnu.org/licenses/>.
// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
// Permission to use, copy, modify, sell, and distribute this software
// is hereby granted without fee, provided that the above copyright
// notice appears in all copies, and that both that copyright notice
// and this permission notice appear in supporting documentation. None
// of the above authors, nor IBM Haifa Research Laboratories, make any
// representation about the suitability of this software for any
// purpose. It is provided "as is" without express or implied
// warranty.
/**
* @file priority_queue.hpp
* Contains priority_queues.
*/
#ifndef PB_DS_PRIORITY_QUEUE_HPP
#define PB_DS_PRIORITY_QUEUE_HPP
#include <bits/c++config.h>
#include <ext/pb_ds/tag_and_trait.hpp>
#include <ext/pb_ds/detail/priority_queue_base_dispatch.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>
namespace __gnu_pbds
{
/**
* @defgroup heap-based Heap-Based
* @ingroup containers-pbds
* @{
*/
/**
* @defgroup heap-detail Base and Policy Classes
* @ingroup heap-based
*/
/**
* A priority queue composed of one specific heap policy.
*
* @tparam _Tv Value type.
* @tparam Cmp_Fn Comparison functor.
* @tparam Tag Instantiating data structure type,
* see container_tag.
* @tparam _Alloc Allocator type.
*
* Base is dispatched at compile time via Tag, from the following
* choices: binary_heap_tag, binomial_heap_tag, pairing_heap_tag,
* rc_binomial_heap_tag, thin_heap_tag
*
* Base choices are: detail::binary_heap, detail::binomial_heap,
* detail::pairing_heap, detail::rc_binomial_heap,
* detail::thin_heap.
*/
template<typename _Tv,
typename Cmp_Fn = std::less<_Tv>,
typename Tag = pairing_heap_tag,
typename _Alloc = std::allocator<char> >
class priority_queue
: public detail::container_base_dispatch<_Tv, Cmp_Fn, _Alloc, Tag>::type
{
public:
typedef _Tv value_type;
typedef Cmp_Fn cmp_fn;
typedef Tag container_category;
typedef _Alloc allocator_type;
typedef typename allocator_type::size_type size_type;
typedef typename allocator_type::difference_type difference_type;
private:
typedef typename detail::container_base_dispatch<_Tv, Cmp_Fn, _Alloc,
Tag>::type
base_type;
typedef typename _Alloc::template rebind<_Tv> __rebind_v;
typedef typename __rebind_v::other __rebind_va;
public:
typedef typename __rebind_va::reference reference;
typedef typename __rebind_va::const_reference const_reference;
typedef typename __rebind_va::pointer pointer;
typedef typename __rebind_va::const_pointer const_pointer;
typedef typename base_type::point_iterator point_iterator;
typedef typename base_type::point_const_iterator point_const_iterator;
typedef typename base_type::iterator iterator;
typedef typename base_type::const_iterator const_iterator;
priority_queue() { }
/// Constructor taking some policy objects. r_cmp_fn will be
/// copied by the Cmp_Fn object of the container object.
priority_queue(const cmp_fn& r_cmp_fn) : base_type(r_cmp_fn) { }
/// Constructor taking __iterators to a range of value_types. The
/// value_types between first_it and last_it will be inserted into
/// the container object.
template<typename It>
priority_queue(It first_it, It last_it)
{ base_type::copy_from_range(first_it, last_it); }
/// Constructor taking __iterators to a range of value_types and
/// some policy objects The value_types between first_it and
/// last_it will be inserted into the container object. r_cmp_fn
/// will be copied by the cmp_fn object of the container object.
template<typename It>
priority_queue(It first_it, It last_it, const cmp_fn& r_cmp_fn)
: base_type(r_cmp_fn)
{ base_type::copy_from_range(first_it, last_it); }
priority_queue(const priority_queue& other)
: base_type((const base_type& )other) { }
virtual
~priority_queue() { }
priority_queue&
operator=(const priority_queue& other)
{
if (this != &other)
{
priority_queue tmp(other);
swap(tmp);
}
return *this;
}
void
swap(priority_queue& other)
{ base_type::swap(other); }
};
} // namespace __gnu_pbds
//@} heap-based
#endif
|
