PriorityQueue.h

#ifndef theplu_yat_utility_priority_queue
#define theplu_yat_utility_priority_queue

// $Id: PriorityQueue.h 3403 2015-03-31 05:18:45Z peter $
//
// Copyright (C) 2015 Peter Johansson
//
// This program is free software; you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation; either version 3 of the License, or
// (at your option) any later version.
//
// This program is distributed in the hope that it will be useful, but
// WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
// General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program. If not, see <http://www.gnu.org/licenses/>.

#include "yat_assert.h"

#include <boost/thread.hpp>

#include <set>
#include <utility>

namespace theplu {
namespace yat {
namespace utility {

  template<typename T, class Compare = std::less<T> >
  class PriorityQueue
  {
  public:
    typedef T value_type;

    typedef typename std::set<T, Compare>::size_type size_type;

    PriorityQueue(void) {}

    explicit PriorityQueue(const Compare& comp) : q_(comp) {}

    PriorityQueue(const PriorityQueue& other) : q_(other.q_) {}

    bool empty(void) const
    {
      boost::unique_lock<boost::mutex> lock(mutex_);
      return q_.empty();
    } // lock is released here


    void pop(T& value)
    {
      boost::unique_lock<boost::mutex> lock(mutex_);
      while (q_.empty())
        condition_.wait(lock);
      pop(value, lock);
    } // lock is released here


    void push(const T& t)
    {
      boost::unique_lock<boost::mutex> lock(mutex_);
      q_.insert(t);
      lock.unlock(); // unlock the mutex

      // Notify others that data is ready after we have unlocked
      condition_.notify_one();
    }


    size_type size(void) const
    {
      boost::unique_lock<boost::mutex> lock(mutex_);
      return q_.size();
    } // lock is released here


    bool try_pop(T& value)
    {
      boost::unique_lock<boost::mutex> lock(mutex_);
      if (q_.empty())
        return false;
      pop(value, lock);
      return true;
    } // lock is released here


    PriorityQueue& operator=(const PriorityQueue& lhs)
    {
      q_ = lhs.q_;
      return *this;
    }

  private:
    std::set<T, Compare> q_;
    mutable boost::mutex mutex_;
    boost::condition_variable condition_;

    void pop(T& value, const boost::unique_lock<boost::mutex>& lock)
    {
      // The obvious choice would be to create a temp copy of front,
      // pop the queue and then return by-value. This is, however,
      // dangerous because if the copy constructor throws, the queue
      // has been popped and the element is lost. Instead we choose to
      // return via passed reference.
      typename std::set<T, Compare>::iterator it = q_.end();
      YAT_ASSERT(q_.size());
      --it;
      value = *it;
      q_.erase(it);
    }
  };

}}}
#endif