source: trunk/yat/utility/PriorityQueue.h @ 3751

#ifndef theplu_yat_utility_priority_queue
#define theplu_yat_utility_priority_queue

// $Id: PriorityQueue.h 3751 2018-10-17 01:49:41Z peter $
//
// Copyright (C) 2015, 2016, 2017 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 yat. If not, see <http://www.gnu.org/licenses/>.

#include "config_public.h"
#include "BasicQueue.h"
#include "utility.h"
#include "yat_assert.h"

#include <set>
#include <utility>

namespace theplu {
namespace yat {
namespace utility {

  /**
     \brief Multi-thread safe priority queue

     This class provides a multi-thread safe priority_queue. The
     PriorityQueue is typically shared by multiple threads such that
     some threads push elements and some pop elements. The
     PriorityQueue is a specifically designed so you can only access
     the greatest element similar to<a
     href="http://www.sgi.com/tech/stl/priority_queue.html">std::priority_queue</a>. The
     difference is that Queue is multi-thread safe, in other words,
     when one thread access the Queue, other threads are locked out
     from access so that only one thread touches the Queue at a time
     and its behaviour is well defined. In a single-thread application
     there is no point in using the class as std::queue should be
     prefereble.

     \note Copy constructor and assignment are available but they are
     not thread safe in the current implementation.

     \since New in yat 0.13
   */
  template<typename T, class Compare = std::less<T> >
  class PriorityQueue
    : public detail::BasicQueue<PriorityQueue<T, Compare>
                                , T
                                , std::set<T, Compare> >
  {
    friend class detail::BasicQueue<PriorityQueue<T, Compare>
                                    ,T,std::set<T,Compare> >;
    typedef detail::BasicQueue<PriorityQueue<T, Compare>
                               , T
                               , std::set<T,Compare> > Base;
  public:
    /**
       \brief Create a PriorityQueue with no elements
    */
    PriorityQueue(void) {}

    /**
       \brief Create a PriorityQueue with \a comp as Compare functor
    */
    explicit PriorityQueue(const Compare& comp)
      : Base(std::set<T, Compare>(comp)) {}

    /**
       \brief Copy constructor
    */
    PriorityQueue(const PriorityQueue& other)
      : Base(other) {}

    /**
       \brief assignment operator
     */
    PriorityQueue& operator=(const PriorityQueue& lhs)
    {
      this->assign(lhs);
      return *this;
    }

  private:
    void pop_impl(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 = this->q_.end();
      YAT_ASSERT(this->q_.size());
      --it;
      value = YAT_MOVE_IF_NOEXCEPT(*it);
      this->q_.erase(it);
    }

    void push_impl(const T& value, boost::unique_lock<boost::mutex>& lock)
    {
      this->q_.insert(value);
    }


#ifdef YAT_HAVE_RVALUE
    void push_impl(T&& value, boost::unique_lock<boost::mutex>& lock)
    {
      this->q_.insert(std::move(value));
    }
#endif
  };

}}}
#endif