pq_overflow_heap.h

Go to the documentation of this file.

// -*- mode: c++; tab-width: 4; indent-tabs-mode: t; c-file-style: "stroustrup"; -*-
// vi:set ts=4 sts=4 sw=4 noet :
// Copyright 2008, 2012, The TPIE development team
// 
// This file is part of TPIE.
// 
// TPIE is free software: you can redistribute it and/or modify it under
// the terms of the GNU Lesser General Public License as published by the
// Free Software Foundation, either version 3 of the License, or (at your
// option) any later version.
// 
// TPIE 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 Lesser General Public
// License for more details.
// 
// You should have received a copy of the GNU Lesser General Public License
// along with TPIE.  If not, see <http://www.gnu.org/licenses/>


#ifndef _TPIE_PQ_OVERFLOW_HEAP_H_
#define _TPIE_PQ_OVERFLOW_HEAP_H_

#include <tpie/internal_priority_queue.h>

namespace tpie {

template<typename T, typename Comparator = std::less<T> >
class pq_overflow_heap {
public:
    pq_overflow_heap(memory_size_type maxsize, Comparator c=Comparator());

    void push(const T& x);

    void pop();

    const T& top();

    stream_size_type size() const;

    bool empty() const;

    static const double sorted_factor;
        
    bool full() const;

    T* sorted_array();

    memory_size_type sorted_size() const;

    void sorted_pop();

private:
    Comparator comp;
    internal_priority_queue<T, Comparator> h;
    memory_size_type maxsize;
    //T dummy;
};
    
    template<typename T, typename Comparator>
    const double pq_overflow_heap<T,Comparator>::sorted_factor = 1.0;

#include "pq_overflow_heap.inl"

    namespace ami {
        using tpie::pq_overflow_heap;
    }  //  ami namespace

}  //  tpie namespace

#endif