internal_priority_queue.h

Go to the documentation of this file.

// -*- mode: c++; tab-width: 4; indent-tabs-mode: t; eval: (progn (c-set-style "stroustrup") (c-set-offset 'innamespace 0)); -*-
// vi:set ts=4 sts=4 sw=4 noet :
// Copyright 2008, 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_INTERNAL_PRIORITY_QUEUE_H__
#define __TPIE_INTERNAL_PRIORITY_QUEUE_H__
#include <tpie/array.h>
#include <algorithm>
#include <tpie/util.h>
namespace tpie {

template <typename T, typename comp_t = std::less<T> >
class internal_priority_queue: public linear_memory_base< internal_priority_queue<T, comp_t> > {
public:
    typedef memory_size_type size_type;

    internal_priority_queue(size_type max_size, comp_t c=comp_t()): pq(max_size), sz(0), comp(c) {}

    template <typename IT>
    internal_priority_queue(size_type max_size, const IT & start, const IT & end,
                            comp_t c=comp_t()): pq(max_size), sz(0), comp(c) {
        insert(start, end);
    }

    template <typename IT>
    void insert(const IT & start, const IT & end) {
        std::copy(start, end, pq.find(sz));
        sz += (end - start);
        make_safe();
    }

    void unsafe_push(const T & v) { 
        pq[sz++] = v; 
    }

    void make_safe() {
        std::make_heap(pq.begin(), pq.find(sz), comp);
    }
  
    bool empty() const {return sz == 0;}

    inline size_type size() const {return sz;}

    inline void push(const T & v) { 
        assert(size() < pq.size());
        pq[sz++] = v; 
        std::push_heap(pq.begin(), pq.find(sz), comp);
    }

    inline void pop() { 
        assert(!empty());
        std::pop_heap(pq.begin(), pq.find(sz), comp);
        --sz;
    }

    inline void pop_and_push(const T & v) {
        assert(!empty());
        pq[0] = v;
        pop_and_push_heap(pq.begin(), pq.find(sz), comp);
    }

    inline const T & top() const {return pq[0];}

    inline static double memory_coefficient() {
        return tpie::array<T>::memory_coefficient();
    }

    inline static double memory_overhead() {
        return tpie::array<T>::memory_overhead() - sizeof(tpie::array<T>) + sizeof(internal_priority_queue);
    }

    tpie::array<T> & get_array() {
        return pq;
    }

    inline void clear() {sz=0;}

    inline void resize(size_t s) {sz=0; pq.resize(s);}
private:    
    tpie::array<T> pq; 
    size_type sz;
    binary_argument_swap<comp_t> comp;
};

}  //  tpie namespace
#endif //__TPIE_INTERNAL_PRIORITY_QUEUE_H__