]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 | template<class T, class Compare = std::less<T>, bool implicit_fence = true, | |
36 | class Buffer = boost::queue<T> > | |
37 | class fenced_priority_queue { | |
38 | public: | |
39 | typedef T value_type; | |
40 | typedef typename Buffer::size_type size_type; | |
41 | ||
42 | fenced_priority_queue(const Compare _comp = Compare() ) | |
43 | : PQ(_comp) {} | |
44 | ||
45 | void push(const T& data); | |
46 | void pop(void); | |
47 | T& top(void); | |
48 | const T& top(void) const; | |
49 | size_type size(void) const; | |
50 | bool empty(void) const; | |
51 | void fence(void); | |
52 | ||
53 | private: | |
54 | void fence(void) const; | |
55 | ||
56 | //let them mutable to allow const version of top and the same | |
57 | //semantics with non-constant version. Rich Lee | |
58 | mutable std::priority_queue<T, std::vector<T>, Compare> PQ; | |
59 | mutable Buffer Q; | |
60 | }; | |
61 | ||
62 | template<class T, class Compare, bool implicit_fence, class Buffer> | |
63 | inline void | |
64 | fenced_priority_queue<T, Compare, implicit_fence, Buffer>:: | |
65 | push(const T &t) { | |
66 | // Push a new element after the last fence. This puts it into the | |
67 | // priority queue to be sorted with all other elements in its | |
68 | // partition. | |
69 | PQ.push(t); | |
70 | } | |
71 | ||
72 | template<class T, class Compare, bool implicit_fence, class Buffer> | |
73 | inline void fenced_priority_queue<T, Compare, implicit_fence, Buffer>:: | |
74 | pop(void) { | |
75 | // Pop one element from the front of the queue. Removes from the | |
76 | // already-sorted part of the queue if it is non-empty, otherwise | |
77 | // removes from the new-element priority queue. Runs an implicit | |
78 | // "fence" operation if the implicit_fence template argument is | |
79 | // true. | |
80 | if (implicit_fence) fence(); | |
81 | if ( !Q.empty() ) | |
82 | Q.pop(); | |
83 | else | |
84 | PQ.pop(); | |
85 | } | |
86 | ||
87 | template<class T, class Compare, bool implicit_fence, class Buffer> | |
88 | inline T& fenced_priority_queue<T, Compare, implicit_fence, Buffer>:: | |
89 | top(void) { | |
90 | // Get the top element from the queue. This element comes from Q if | |
91 | // possible, otherwise from PQ. Causes an implicit "fence" | |
92 | // operation if the implicit_fence template argument is true. | |
93 | if (implicit_fence) fence(); | |
94 | if ( !Q.empty() ) | |
95 | return Q.top(); | |
96 | else | |
97 | //std::priority_queue only have const version of top. Rich Lee | |
98 | return const_cast<T&>(PQ.top()); | |
99 | } | |
100 | ||
101 | template<class T, class Compare, bool implicit_fence, class Buffer> | |
102 | inline const T& | |
103 | fenced_priority_queue<T, Compare, implicit_fence, Buffer>:: | |
104 | top(void) const { | |
105 | if (implicit_fence) fence(); | |
106 | if ( !Q.empty() ) | |
107 | return Q.top(); | |
108 | else | |
109 | return PQ.top(); | |
110 | } | |
111 | ||
112 | template<class T, class Compare, bool implicit_fence, class Buffer> | |
113 | inline typename fenced_priority_queue<T, Compare, implicit_fence, Buffer>::size_type | |
114 | fenced_priority_queue<T, Compare, implicit_fence, Buffer>:: | |
115 | size(void) const { | |
116 | // Returns the size of the queue (both parts together). | |
117 | return Q.size() + PQ.size(); | |
118 | } | |
119 | ||
120 | template<class T, class Compare, bool implicit_fence, class Buffer> | |
121 | inline bool | |
122 | fenced_priority_queue<T, Compare, implicit_fence, Buffer>:: | |
123 | empty(void) const { | |
124 | // Returns if the queue is empty, i.e. both parts are empty. | |
125 | return Q.empty() && PQ.empty(); | |
126 | } | |
127 | ||
128 | template<class T, class Compare, bool implicit_fence, class Buffer> | |
129 | inline void | |
130 | fenced_priority_queue<T, Compare, implicit_fence, Buffer>:: | |
131 | fence(void) { | |
132 | // Perform a fence operation. Remove elements from PQ in sorted | |
133 | // order and insert them in the back of Q. | |
134 | while ( !PQ.empty() ) { | |
135 | Q.push(PQ.top()); | |
136 | PQ.pop(); | |
137 | } | |
138 | } | |
139 | template<class T, class Compare, bool implicit_fence, class Buffer> | |
140 | inline void | |
141 | fenced_priority_queue<T, Compare, implicit_fence, Buffer>:: | |
142 | fence(void) const { | |
143 | // Perform a fence operation. Remove elements from PQ in sorted | |
144 | // order and insert them in the back of Q. | |
145 | while ( !PQ.empty() ) { | |
146 | Q.push(PQ.top()); | |
147 | PQ.pop(); | |
148 | } | |
149 | } | |
150 | ||
151 | } | |
152 | #endif /* BOOST_FENCED_PRIORITY_QUEUE_HPP */ |