PriorityQueue.h

#ifndef theplu_yat_utility_priority_queue
#define theplu_yat_utility_priority_queue

// $Id: PriorityQueue.h 3999 2020-10-08 23:22:32Z peter $
//
// Copyright (C) 2015, 2016, 2017, 2018, 2019, 2020 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 "BasicQueue.h"
#include "utility.h"
#include "yat_assert.h"

#include <mutex>
#include <set>
#include <utility>

namespace theplu {
namespace yat {
namespace utility {

  template<typename T, class Compare = std::less<T> >
  class PriorityQueue
    : public detail::BasicQueue<PriorityQueue<T, Compare>
                                , T
                                , std::multiset<T, Compare> >
  {
    friend class detail::BasicQueue<PriorityQueue<T, Compare>
                                    ,T,std::multiset<T,Compare> >;
    typedef detail::BasicQueue<PriorityQueue<T, Compare>
                               , T
                               , std::multiset<T,Compare> > Base;
  public:
    PriorityQueue(void) {}

    explicit PriorityQueue(const Compare& comp)
      : Base(std::multiset<T, Compare>(comp)) {}

    PriorityQueue(const PriorityQueue& other)
      : Base(other) {}

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

  private:
    void pop_impl(T& value, const std::unique_lock<std::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::multiset<T, Compare>::iterator it = this->q_.end();
      YAT_ASSERT(this->q_.size());
      --it;
      value = std::move_if_noexcept(*it);
      this->q_.erase(it);
    }

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


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

}}}
#endif