MRFewSmallest.h

Go to the documentation of this file.

#pragma once
 
#include "MRMeshFwd.h"
#include <algorithm>
#include <cassert>
#include <vector>
 
namespace MR
{
 
 
template<typename T>
class FewSmallest
{
public:
    FewSmallest() {}
 
    explicit FewSmallest( size_t maxElms ) { reset( maxElms ); }
 
    void reset( size_t maxElms );
 
    size_t maxElms() const { return maxElms_; }
 
    bool empty() const { return heap_.empty(); }
 
    size_t size() const { return heap_.size(); }
 
    bool full() const { return size() == maxElms(); }
 
    const std::vector<T> & get() const { return heap_; }
 
    const T & top() const { assert( !heap_.empty() ); return heap_.front(); }
 
    const T & topOr( const T & emptyRes ) const { return !heap_.empty() ? heap_.front() : emptyRes; }
 
    void push( T t );
 
    void clear() { heap_.clear(); }
 
private:
    std::vector<T> heap_;
    size_t maxElms_ = 0;
};
 
template<typename T>
void FewSmallest<T>::reset( size_t maxElms )
{
    heap_.clear();
    heap_.reserve( maxElms );
    maxElms_ = maxElms;
}
 
template<typename T>
void FewSmallest<T>::push( T t )
{
    assert( heap_.size() <= maxElms() );
    if ( heap_.size() == maxElms() )
    {
        if ( t < heap_.front() )
        {
            std::pop_heap( heap_.begin(), heap_.end() );
            assert( t < heap_.back() );
            heap_.back() = std::move( t );
            std::push_heap( heap_.begin(), heap_.end() );
        }
        return;
    }
    heap_.push_back( std::move( t ) );
    std::push_heap( heap_.begin(), heap_.end() );
}
 
}