pq_merge_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_MERGE_HEAP_H_
#define _TPIE_PQ_MERGE_HEAP_H_

#include "tpie_log.h"
#include <cassert>
#include <tpie/memory.h>

namespace tpie{

template<typename T, typename Comparator = std::less<T> >
class pq_merge_heap {
    public:
        typedef memory_size_type run_type;

        pq_merge_heap(memory_size_type elements);

        ~pq_merge_heap();

        void push(const T& x, run_type run);

        void pop();

        void pop_and_push(const T& x, run_type run);

        const T& top() const;

        run_type top_run() const;

        memory_size_type size() const;

        bool empty() const;

    private:
        void fixDown();
        void validate();
        void dump();

        memory_size_type m_size;
        Comparator comp_;

        T* heap;
        run_type* runs;
        memory_size_type maxsize;
};

#include "pq_merge_heap.inl"
}

#endif