Chris@16: //  (C) Copyright Jeremiah Willcock 2004 
Chris@16: //  Distributed under the Boost Software License, Version 1.0. (See
Chris@16: //  accompanying file LICENSE_1_0.txt or copy at
Chris@16: //  http://www.boost.org/LICENSE_1_0.txt)
Chris@16: 
Chris@16: #ifndef BOOST_FENCED_PRIORITY_QUEUE_HPP
Chris@16: #define BOOST_FENCED_PRIORITY_QUEUE_HPP
Chris@16: 
Chris@16: #include <vector>
Chris@16: #include <queue>
Chris@16: #include <functional>
Chris@16: #include <boost/pending/queue.hpp>
Chris@16: 
Chris@16: // Fenced priority queue
Chris@16: // Jeremiah Willcock
Chris@16: 
Chris@16: // This class implements a fenced priority queue.  This is similar to
Chris@16: // a normal priority queue (sorts its members, and only returns the
Chris@16: // first), except that members cannot be sorted around a "fence" that
Chris@16: // can be placed into the buffer.  This fence is inserted using the
Chris@16: // fence() member function or (possibly) implicitly by the top() and
Chris@16: // pop() methods, and is removed automatically when the elements
Chris@16: // around it are popped.
Chris@16: 
Chris@16: // The implementation is as follows:  Q is an unsorted queue that
Chris@16: // contains the already-sorted list data, and PQ is a priority queue
Chris@16: // that contains new elements (since the last fence) that have yet to
Chris@16: // be sorted.  New elements are inserted into PQ, and a fence moves
Chris@16: // all elements in PQ into the back of Q in sorted order.  Elements
Chris@16: // are then popped from the front of Q, and if that is empty the front
Chris@16: // of PQ.
Chris@16: 
Chris@16: namespace boost {
Chris@16: 
Chris@16:   template<class T, class Compare = std::less<T>, bool implicit_fence = true,
Chris@16:            class Buffer = boost::queue<T> >
Chris@16:   class fenced_priority_queue {
Chris@16:   public:
Chris@16:     typedef T value_type;
Chris@16:     typedef typename Buffer::size_type size_type;
Chris@16: 
Chris@16:     fenced_priority_queue(const Compare _comp = Compare() ) 
Chris@16:       : PQ(_comp) {} 
Chris@16:     
Chris@16:     void push(const T& data);
Chris@16:     void pop(void);
Chris@16:     T& top(void);
Chris@16:     const T& top(void) const;
Chris@16:     size_type size(void) const;
Chris@16:     bool empty(void) const;
Chris@16:     void fence(void);
Chris@16:     
Chris@16:   private:
Chris@16:     void fence(void) const;
Chris@16: 
Chris@16:     //let them mutable to allow const version of top and the same 
Chris@16:     //semantics with non-constant version. Rich Lee
Chris@16:     mutable std::priority_queue<T, std::vector<T>, Compare> PQ;
Chris@16:     mutable Buffer Q;
Chris@16:   };
Chris@16:   
Chris@16:   template<class T, class Compare, bool implicit_fence, class Buffer>
Chris@16:   inline void 
Chris@16:   fenced_priority_queue<T, Compare, implicit_fence, Buffer>::
Chris@16:   push(const T &t) {
Chris@16:     // Push a new element after the last fence.  This puts it into the
Chris@16:     // priority queue to be sorted with all other elements in its
Chris@16:     // partition.
Chris@16:     PQ.push(t);
Chris@16:   }
Chris@16: 
Chris@16:   template<class T, class Compare, bool implicit_fence, class Buffer>
Chris@16:   inline void fenced_priority_queue<T, Compare, implicit_fence, Buffer>::
Chris@16:   pop(void) {
Chris@16:     // Pop one element from the front of the queue.  Removes from the
Chris@16:     // already-sorted part of the queue if it is non-empty, otherwise
Chris@16:     // removes from the new-element priority queue.  Runs an implicit
Chris@16:     // "fence" operation if the implicit_fence template argument is
Chris@16:     // true.
Chris@16:     if (implicit_fence) fence();
Chris@16:     if ( !Q.empty() )
Chris@16:       Q.pop();
Chris@16:     else
Chris@16:       PQ.pop();
Chris@16:   }
Chris@16: 
Chris@16:   template<class T, class Compare, bool implicit_fence, class Buffer>
Chris@16:   inline T& fenced_priority_queue<T, Compare, implicit_fence, Buffer>::
Chris@16:   top(void) {
Chris@16:     // Get the top element from the queue.  This element comes from Q if
Chris@16:     // possible, otherwise from PQ.  Causes an implicit "fence"
Chris@16:     // operation if the implicit_fence template argument is true.
Chris@16:     if (implicit_fence) fence();
Chris@16:     if ( !Q.empty() )
Chris@16:       return Q.top();
Chris@16:     else
Chris@16:       //std::priority_queue only have const version of top. Rich Lee
Chris@16:       return const_cast<T&>(PQ.top());
Chris@16:   }
Chris@16: 
Chris@16:   template<class T, class Compare, bool implicit_fence, class Buffer>
Chris@16:   inline const T&
Chris@16:   fenced_priority_queue<T, Compare, implicit_fence, Buffer>::
Chris@16:   top(void) const {
Chris@16:     if (implicit_fence) fence();
Chris@16:     if ( !Q.empty() )
Chris@16:       return Q.top();
Chris@16:     else
Chris@16:       return PQ.top();
Chris@16:   }
Chris@16: 
Chris@16:   template<class T, class Compare, bool implicit_fence, class Buffer>
Chris@16:   inline typename fenced_priority_queue<T, Compare, implicit_fence, Buffer>::size_type 
Chris@16:   fenced_priority_queue<T, Compare, implicit_fence, Buffer>::
Chris@16:   size(void) const {
Chris@16:     // Returns the size of the queue (both parts together).
Chris@16:     return Q.size() + PQ.size();
Chris@16:   }
Chris@16: 
Chris@16:   template<class T, class Compare, bool implicit_fence, class Buffer>
Chris@16:   inline bool 
Chris@16:   fenced_priority_queue<T, Compare, implicit_fence, Buffer>::
Chris@16:   empty(void) const {
Chris@16:     // Returns if the queue is empty, i.e. both parts are empty.
Chris@16:     return Q.empty() && PQ.empty();
Chris@16:   }
Chris@16:   
Chris@16:   template<class T, class Compare, bool implicit_fence, class Buffer>
Chris@16:   inline void 
Chris@16:   fenced_priority_queue<T, Compare, implicit_fence, Buffer>::
Chris@16:   fence(void) {
Chris@16:     // Perform a fence operation.  Remove elements from PQ in sorted
Chris@16:     // order and insert them in the back of Q.
Chris@16:     while ( !PQ.empty() ) {
Chris@16:       Q.push(PQ.top());
Chris@16:       PQ.pop();
Chris@16:     }
Chris@16:   }
Chris@16:   template<class T, class Compare, bool implicit_fence, class Buffer>
Chris@16:   inline void 
Chris@16:   fenced_priority_queue<T, Compare, implicit_fence, Buffer>::
Chris@16:   fence(void) const {
Chris@16:     // Perform a fence operation.  Remove elements from PQ in sorted
Chris@16:     // order and insert them in the back of Q.
Chris@16:     while ( !PQ.empty() ) {
Chris@16:       Q.push(PQ.top());
Chris@16:       PQ.pop();
Chris@16:     }
Chris@16:   }
Chris@16: 
Chris@16: }  
Chris@16: #endif /* BOOST_FENCED_PRIORITY_QUEUE_HPP */