MRPriorityQueue.h

Go to the documentation of this file.

#pragma once
 
#include "MRMacros.h"
#include "MRTimer.h"
#include <vector>
#include <algorithm>
 
namespace MR
{
 
 
template <typename T, typename P = std::less<T>>
class PriorityQueue
{
public:
    using value_type = T;
    using Container = std::vector<T>;
    using size_type = typename Container::size_type;
 
    PriorityQueue() {}
    explicit PriorityQueue( const P& pred ) : pred_( pred ) {}
 
    explicit PriorityQueue( const P& pred, Container&& v MR_LIFETIMEBOUND_NESTED );
 
    bool empty() const { return c.empty(); }
 
    size_type size() const { return c.size(); }
 
    const T & top() const MR_LIFETIMEBOUND { return c.front(); }
 
    void push( const value_type& value MR_LIFETIME_CAPTURE_BY_NESTED(this) ) { c.push_back( value ); onPush_(); }
    void push( value_type&& value MR_LIFETIME_CAPTURE_BY_NESTED(this) ) { c.push_back( std::move( value ) ); onPush_(); }
    template< class... Args >
    void emplace( Args&&... args ) { c.emplace_back( std::forward<Args>(args)... ); onPush_(); }
 
    void pop() { std::pop_heap( c.begin(), c.end(), pred_ ); c.pop_back(); }
 
    Container c;
 
private:
    void onPush_() { std::push_heap( c.begin(), c.end(), pred_ ); };
 
private:
    MR_NO_UNIQUE_ADDRESS P pred_;
};
 
template <typename T, typename P>
PriorityQueue<T, P>::PriorityQueue( const P& pred, Container&& v ) : c( std::move( v ) ), pred_( pred )
{
    MR_TIMER;
    std::make_heap( c.begin(), c.end(), pred_ );
}
 
}