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
|
/*
* barrier -- mouse and keyboard sharing utility
* Copyright (C) 2012-2016 Symless Ltd.
* Copyright (C) 2003 Chris Schoeneman
*
* This package is free software; you can redistribute it and/or
* modify it under the terms of the GNU General Public License
* found in the file LICENSE that should have accompanied this file.
*
* This package 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.
*
* You should have received a copy of the GNU General Public License
* along with this program. If not, see <http://www.gnu.org/licenses/>.
*/
#pragma once
#include "common/stdvector.h"
#include <algorithm>
#include <functional>
//! A priority queue with an iterator
/*!
This priority queue is the same as a standard priority queue except:
it sorts by std::greater, it has a forward iterator through the elements
(which can appear in any order), and its contents can be swapped.
*/
template <class T, class Container = std::vector<T>,
#if defined(_MSC_VER)
class Compare = std::greater<Container::value_type> >
#else
class Compare = std::greater<typename Container::value_type> >
#endif
class PriorityQueue {
public:
typedef typename Container::value_type value_type;
typedef typename Container::size_type size_type;
typedef typename Container::iterator iterator;
typedef typename Container::const_iterator const_iterator;
typedef Container container_type;
PriorityQueue() { }
PriorityQueue(Container& swappedIn) { swap(swappedIn); }
~PriorityQueue() { }
//! @name manipulators
//@{
//! Add element
void push(const value_type& v)
{
c.push_back(v);
std::push_heap(c.begin(), c.end(), comp);
}
//! Remove head element
void pop()
{
std::pop_heap(c.begin(), c.end(), comp);
c.pop_back();
}
//! Erase element
void erase(iterator i)
{
c.erase(i);
std::make_heap(c.begin(), c.end(), comp);
}
//! Get start iterator
iterator begin()
{
return c.begin();
}
//! Get end iterator
iterator end()
{
return c.end();
}
//! Swap contents with another priority queue
void swap(PriorityQueue<T, Container, Compare>& q)
{
c.swap(q.c);
}
//! Swap contents with another container
void swap(Container& c2)
{
c.swap(c2);
std::make_heap(c.begin(), c.end(), comp);
}
//@}
//! @name accessors
//@{
//! Returns true if there are no elements
bool empty() const
{
return c.empty();
}
//! Returns the number of elements
size_type size() const
{
return c.size();
}
//! Returns the head element
const value_type& top() const
{
return c.front();
}
//! Get start iterator
const_iterator begin() const
{
return c.begin();
}
//! Get end iterator
const_iterator end() const
{
return c.end();
}
//@}
private:
Container c;
Compare comp;
};
|
