1 // (C) Copyright Jeremiah Willcock 2004
2 // Distributed under the Boost Software License, Version 1.0. (See
3 // accompanying file LICENSE_1_0.txt or copy at
4 // http://www.boost.org/LICENSE_1_0.txt)
5
6 #ifndef BOOST_FENCED_PRIORITY_QUEUE_HPP
7 #define BOOST_FENCED_PRIORITY_QUEUE_HPP
8
9 #include <vector>
10 #include <queue>
11 #include <functional>
12 #include <boost/pending/queue.hpp>
13
14 // Fenced priority queue
15 // Jeremiah Willcock
16
17 // This class implements a fenced priority queue. This is similar to
18 // a normal priority queue (sorts its members, and only returns the
19 // first), except that members cannot be sorted around a "fence" that
20 // can be placed into the buffer. This fence is inserted using the
21 // fence() member function or (possibly) implicitly by the top() and
22 // pop() methods, and is removed automatically when the elements
23 // around it are popped.
24
25 // The implementation is as follows: Q is an unsorted queue that
26 // contains the already-sorted list data, and PQ is a priority queue
27 // that contains new elements (since the last fence) that have yet to
28 // be sorted. New elements are inserted into PQ, and a fence moves
29 // all elements in PQ into the back of Q in sorted order. Elements
30 // are then popped from the front of Q, and if that is empty the front
31 // of PQ.
32
33 namespace boost
34 {
35
36 template < class T, class Compare = std::less< T >, bool implicit_fence = true,
37 class Buffer = boost::queue< T > >
38 class fenced_priority_queue
39 {
40 public:
41 typedef T value_type;
42 typedef typename Buffer::size_type size_type;
43
fenced_priority_queue(const Compare _comp=Compare ())44 fenced_priority_queue(const Compare _comp = Compare()) : PQ(_comp) {}
45
46 void push(const T& data);
47 void pop(void);
48 T& top(void);
49 const T& top(void) const;
50 size_type size(void) const;
51 bool empty(void) const;
52 void fence(void);
53
54 private:
55 void fence(void) const;
56
57 // let them mutable to allow const version of top and the same
58 // semantics with non-constant version. Rich Lee
59 mutable std::priority_queue< T, std::vector< T >, Compare > PQ;
60 mutable Buffer Q;
61 };
62
63 template < class T, class Compare, bool implicit_fence, class Buffer >
push(const T & t)64 inline void fenced_priority_queue< T, Compare, implicit_fence, Buffer >::push(
65 const T& t)
66 {
67 // Push a new element after the last fence. This puts it into the
68 // priority queue to be sorted with all other elements in its
69 // partition.
70 PQ.push(t);
71 }
72
73 template < class T, class Compare, bool implicit_fence, class Buffer >
pop(void)74 inline void fenced_priority_queue< T, Compare, implicit_fence, Buffer >::pop(
75 void)
76 {
77 // Pop one element from the front of the queue. Removes from the
78 // already-sorted part of the queue if it is non-empty, otherwise
79 // removes from the new-element priority queue. Runs an implicit
80 // "fence" operation if the implicit_fence template argument is
81 // true.
82 if (implicit_fence)
83 fence();
84 if (!Q.empty())
85 Q.pop();
86 else
87 PQ.pop();
88 }
89
90 template < class T, class Compare, bool implicit_fence, class Buffer >
top(void)91 inline T& fenced_priority_queue< T, Compare, implicit_fence, Buffer >::top(void)
92 {
93 // Get the top element from the queue. This element comes from Q if
94 // possible, otherwise from PQ. Causes an implicit "fence"
95 // operation if the implicit_fence template argument is true.
96 if (implicit_fence)
97 fence();
98 if (!Q.empty())
99 return Q.top();
100 else
101 // std::priority_queue only have const version of top. Rich Lee
102 return const_cast< T& >(PQ.top());
103 }
104
105 template < class T, class Compare, bool implicit_fence, class Buffer >
106 inline const T&
top(void) const107 fenced_priority_queue< T, Compare, implicit_fence, Buffer >::top(void) const
108 {
109 if (implicit_fence)
110 fence();
111 if (!Q.empty())
112 return Q.top();
113 else
114 return PQ.top();
115 }
116
117 template < class T, class Compare, bool implicit_fence, class Buffer >
118 inline typename fenced_priority_queue< T, Compare, implicit_fence,
119 Buffer >::size_type
size(void) const120 fenced_priority_queue< T, Compare, implicit_fence, Buffer >::size(void) const
121 {
122 // Returns the size of the queue (both parts together).
123 return Q.size() + PQ.size();
124 }
125
126 template < class T, class Compare, bool implicit_fence, class Buffer >
empty(void) const127 inline bool fenced_priority_queue< T, Compare, implicit_fence, Buffer >::empty(
128 void) const
129 {
130 // Returns if the queue is empty, i.e. both parts are empty.
131 return Q.empty() && PQ.empty();
132 }
133
134 template < class T, class Compare, bool implicit_fence, class Buffer >
fence(void)135 inline void fenced_priority_queue< T, Compare, implicit_fence, Buffer >::fence(
136 void)
137 {
138 // Perform a fence operation. Remove elements from PQ in sorted
139 // order and insert them in the back of Q.
140 while (!PQ.empty())
141 {
142 Q.push(PQ.top());
143 PQ.pop();
144 }
145 }
146 template < class T, class Compare, bool implicit_fence, class Buffer >
fence(void) const147 inline void fenced_priority_queue< T, Compare, implicit_fence, Buffer >::fence(
148 void) const
149 {
150 // Perform a fence operation. Remove elements from PQ in sorted
151 // order and insert them in the back of Q.
152 while (!PQ.empty())
153 {
154 Q.push(PQ.top());
155 PQ.pop();
156 }
157 }
158
159 }
160 #endif /* BOOST_FENCED_PRIORITY_QUEUE_HPP */
161