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
158
159
160
|
// (C) Copyright Jeremiah Willcock 2004
// Distributed under the Boost Software License, Version 1.0. (See
// accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
#ifndef BOOST_FENCED_PRIORITY_QUEUE_HPP
#define BOOST_FENCED_PRIORITY_QUEUE_HPP
#include <vector>
#include <queue>
#include <functional>
#include <boost/pending/queue.hpp>
// Fenced priority queue
// Jeremiah Willcock
// This class implements a fenced priority queue. This is similar to
// a normal priority queue (sorts its members, and only returns the
// first), except that members cannot be sorted around a "fence" that
// can be placed into the buffer. This fence is inserted using the
// fence() member function or (possibly) implicitly by the top() and
// pop() methods, and is removed automatically when the elements
// around it are popped.
// The implementation is as follows: Q is an unsorted queue that
// contains the already-sorted list data, and PQ is a priority queue
// that contains new elements (since the last fence) that have yet to
// be sorted. New elements are inserted into PQ, and a fence moves
// all elements in PQ into the back of Q in sorted order. Elements
// are then popped from the front of Q, and if that is empty the front
// of PQ.
namespace boost
{
template < class T, class Compare = std::less< T >, bool implicit_fence = true,
class Buffer = boost::queue< T > >
class fenced_priority_queue
{
public:
typedef T value_type;
typedef typename Buffer::size_type size_type;
fenced_priority_queue(const Compare _comp = Compare()) : PQ(_comp) {}
void push(const T& data);
void pop(void);
T& top(void);
const T& top(void) const;
size_type size(void) const;
bool empty(void) const;
void fence(void);
private:
void fence(void) const;
// let them mutable to allow const version of top and the same
// semantics with non-constant version. Rich Lee
mutable std::priority_queue< T, std::vector< T >, Compare > PQ;
mutable Buffer Q;
};
template < class T, class Compare, bool implicit_fence, class Buffer >
inline void fenced_priority_queue< T, Compare, implicit_fence, Buffer >::push(
const T& t)
{
// Push a new element after the last fence. This puts it into the
// priority queue to be sorted with all other elements in its
// partition.
PQ.push(t);
}
template < class T, class Compare, bool implicit_fence, class Buffer >
inline void fenced_priority_queue< T, Compare, implicit_fence, Buffer >::pop(
void)
{
// Pop one element from the front of the queue. Removes from the
// already-sorted part of the queue if it is non-empty, otherwise
// removes from the new-element priority queue. Runs an implicit
// "fence" operation if the implicit_fence template argument is
// true.
if (implicit_fence)
fence();
if (!Q.empty())
Q.pop();
else
PQ.pop();
}
template < class T, class Compare, bool implicit_fence, class Buffer >
inline T& fenced_priority_queue< T, Compare, implicit_fence, Buffer >::top(void)
{
// Get the top element from the queue. This element comes from Q if
// possible, otherwise from PQ. Causes an implicit "fence"
// operation if the implicit_fence template argument is true.
if (implicit_fence)
fence();
if (!Q.empty())
return Q.top();
else
// std::priority_queue only have const version of top. Rich Lee
return const_cast< T& >(PQ.top());
}
template < class T, class Compare, bool implicit_fence, class Buffer >
inline const T&
fenced_priority_queue< T, Compare, implicit_fence, Buffer >::top(void) const
{
if (implicit_fence)
fence();
if (!Q.empty())
return Q.top();
else
return PQ.top();
}
template < class T, class Compare, bool implicit_fence, class Buffer >
inline typename fenced_priority_queue< T, Compare, implicit_fence,
Buffer >::size_type
fenced_priority_queue< T, Compare, implicit_fence, Buffer >::size(void) const
{
// Returns the size of the queue (both parts together).
return Q.size() + PQ.size();
}
template < class T, class Compare, bool implicit_fence, class Buffer >
inline bool fenced_priority_queue< T, Compare, implicit_fence, Buffer >::empty(
void) const
{
// Returns if the queue is empty, i.e. both parts are empty.
return Q.empty() && PQ.empty();
}
template < class T, class Compare, bool implicit_fence, class Buffer >
inline void fenced_priority_queue< T, Compare, implicit_fence, Buffer >::fence(
void)
{
// Perform a fence operation. Remove elements from PQ in sorted
// order and insert them in the back of Q.
while (!PQ.empty())
{
Q.push(PQ.top());
PQ.pop();
}
}
template < class T, class Compare, bool implicit_fence, class Buffer >
inline void fenced_priority_queue< T, Compare, implicit_fence, Buffer >::fence(
void) const
{
// Perform a fence operation. Remove elements from PQ in sorted
// order and insert them in the back of Q.
while (!PQ.empty())
{
Q.push(PQ.top());
PQ.pop();
}
}
}
#endif /* BOOST_FENCED_PRIORITY_QUEUE_HPP */
|
