boost/pending/fenced_priority_queue.hpp

0001 //  (C) Copyright Jeremiah Willcock 2004
0002 //  Distributed under the Boost Software License, Version 1.0. (See
0003 //  accompanying file LICENSE_1_0.txt or copy at
0004 //  http://www.boost.org/LICENSE_1_0.txt)
0005
0006 #ifndef BOOST_FENCED_PRIORITY_QUEUE_HPP
0007 #define BOOST_FENCED_PRIORITY_QUEUE_HPP
0008
0009 #include <vector>
0010 #include <queue>
0011 #include <functional>
0012 #include <boost/pending/queue.hpp>
0013
0014 // Fenced priority queue
0015 // Jeremiah Willcock
0016
0017 // This class implements a fenced priority queue.  This is similar to
0018 // a normal priority queue (sorts its members, and only returns the
0019 // first), except that members cannot be sorted around a "fence" that
0020 // can be placed into the buffer.  This fence is inserted using the
0021 // fence() member function or (possibly) implicitly by the top() and
0022 // pop() methods, and is removed automatically when the elements
0023 // around it are popped.
0024
0025 // The implementation is as follows:  Q is an unsorted queue that
0026 // contains the already-sorted list data, and PQ is a priority queue
0027 // that contains new elements (since the last fence) that have yet to
0028 // be sorted.  New elements are inserted into PQ, and a fence moves
0029 // all elements in PQ into the back of Q in sorted order.  Elements
0030 // are then popped from the front of Q, and if that is empty the front
0031 // of PQ.
0032
0033 namespace boost
0034 {
0035
0036 template < class T, class Compare = std::less< T >, bool implicit_fence = true,
0037     class Buffer = boost::queue< T > >
0038 class fenced_priority_queue
0039 {
0040 public:
0041     typedef T value_type;
0042     typedef typename Buffer::size_type size_type;
0043
0044     fenced_priority_queue(const Compare _comp = Compare()) : PQ(_comp) {}
0045
0046     void push(const T& data);
0047     void pop(void);
0048     T& top(void);
0049     const T& top(void) const;
0050     size_type size(void) const;
0051     bool empty(void) const;
0052     void fence(void);
0053
0054 private:
0055     void fence(void) const;
0056
0057     // let them mutable to allow const version of top and the same
0058     // semantics with non-constant version. Rich Lee
0059     mutable std::priority_queue< T, std::vector< T >, Compare > PQ;
0060     mutable Buffer Q;
0061 };
0062
0063 template < class T, class Compare, bool implicit_fence, class Buffer >
0064 inline void fenced_priority_queue< T, Compare, implicit_fence, Buffer >::push(
0065     const T& t)
0066 {
0067     // Push a new element after the last fence.  This puts it into the
0068     // priority queue to be sorted with all other elements in its
0069     // partition.
0070     PQ.push(t);
0071 }
0072
0073 template < class T, class Compare, bool implicit_fence, class Buffer >
0074 inline void fenced_priority_queue< T, Compare, implicit_fence, Buffer >::pop(
0075     void)
0076 {
0077     // Pop one element from the front of the queue.  Removes from the
0078     // already-sorted part of the queue if it is non-empty, otherwise
0079     // removes from the new-element priority queue.  Runs an implicit
0080     // "fence" operation if the implicit_fence template argument is
0081     // true.
0082     if (implicit_fence)
0083         fence();
0084     if (!Q.empty())
0085         Q.pop();
0086     else
0087         PQ.pop();
0088 }
0089
0090 template < class T, class Compare, bool implicit_fence, class Buffer >
0091 inline T& fenced_priority_queue< T, Compare, implicit_fence, Buffer >::top(void)
0092 {
0093     // Get the top element from the queue.  This element comes from Q if
0094     // possible, otherwise from PQ.  Causes an implicit "fence"
0095     // operation if the implicit_fence template argument is true.
0096     if (implicit_fence)
0097         fence();
0098     if (!Q.empty())
0099         return Q.top();
0100     else
0101         // std::priority_queue only have const version of top. Rich Lee
0102         return const_cast< T& >(PQ.top());
0103 }
0104
0105 template < class T, class Compare, bool implicit_fence, class Buffer >
0106 inline const T&
0107 fenced_priority_queue< T, Compare, implicit_fence, Buffer >::top(void) const
0108 {
0109     if (implicit_fence)
0110         fence();
0111     if (!Q.empty())
0112         return Q.top();
0113     else
0114         return PQ.top();
0115 }
0116
0117 template < class T, class Compare, bool implicit_fence, class Buffer >
0118 inline typename fenced_priority_queue< T, Compare, implicit_fence,
0119     Buffer >::size_type
0120 fenced_priority_queue< T, Compare, implicit_fence, Buffer >::size(void) const
0121 {
0122     // Returns the size of the queue (both parts together).
0123     return Q.size() + PQ.size();
0124 }
0125
0126 template < class T, class Compare, bool implicit_fence, class Buffer >
0127 inline bool fenced_priority_queue< T, Compare, implicit_fence, Buffer >::empty(
0128     void) const
0129 {
0130     // Returns if the queue is empty, i.e. both parts are empty.
0131     return Q.empty() && PQ.empty();
0132 }
0133
0134 template < class T, class Compare, bool implicit_fence, class Buffer >
0135 inline void fenced_priority_queue< T, Compare, implicit_fence, Buffer >::fence(
0136     void)
0137 {
0138     // Perform a fence operation.  Remove elements from PQ in sorted
0139     // order and insert them in the back of Q.
0140     while (!PQ.empty())
0141     {
0142         Q.push(PQ.top());
0143         PQ.pop();
0144     }
0145 }
0146 template < class T, class Compare, bool implicit_fence, class Buffer >
0147 inline void fenced_priority_queue< T, Compare, implicit_fence, Buffer >::fence(
0148     void) const
0149 {
0150     // Perform a fence operation.  Remove elements from PQ in sorted
0151     // order and insert them in the back of Q.
0152     while (!PQ.empty())
0153     {
0154         Q.push(PQ.top());
0155         PQ.pop();
0156     }
0157 }
0158
0159 }
0160 #endif /* BOOST_FENCED_PRIORITY_QUEUE_HPP */