graph/include/boost/pending/fenced_priority_queue.hpp

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