boost/pending/fenced_priority_queue.hpp

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