| // (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 */ |