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