[857] | 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 */
|
---|