priority_queue.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_PRIORITY_QUEUE_H_
#define _TPIE_PRIORITY_QUEUE_H_

#include <tpie/config.h>
#include "portability.h"
#include "tpie_log.h"
#include <cassert>
#include "pq_overflow_heap.h"
#include <iostream>
#include <fstream>
#include <stdexcept>
#include <cmath>
#include <string>
#include <cstring> // for memcpy
#include <sstream>
#include "pq_merge_heap.h"
#include <tpie/err.h>
#include <tpie/stream.h>
#include <tpie/array.h>
#include <boost/filesystem.hpp>

namespace tpie {

    struct priority_queue_error : public std::logic_error {
        priority_queue_error(const std::string& what) : std::logic_error(what)
        { }
    };


template<typename T, typename Comparator = std::less<T>, typename OPQType = pq_overflow_heap<T, Comparator> >
class priority_queue {
    typedef memory_size_type group_type;
    typedef memory_size_type slot_type;
public:
    static constexpr float default_blocksize = 0.0625; 
    
    priority_queue(double f=1.0, float b=default_blocksize, stream_size_type n = std::numeric_limits<stream_size_type>::max());

#ifndef DOXYGEN
    // \param mmavail Number of bytes the priority queue is allowed to use.
    // \param b Block factor
    priority_queue(memory_size_type mm_avail, float b=default_blocksize, stream_size_type n = std::numeric_limits<stream_size_type>::max());
#endif

    static memory_size_type memory_usage(stream_size_type n, float b=default_blocksize);
    
    ~priority_queue();

    void push(const T& x);

    void pop();

    const T& top();

    stream_size_type size() const;

    bool empty() const;

    template <typename F> F pop_equals(F f);

private:
    Comparator comp_;
    T dummy;

    T min;
    bool min_in_buffer;

    tpie::unique_ptr<OPQType> opq;

    tpie::array<T> buffer;

    tpie::array<T> gbuffer0;

    tpie::array<T> mergebuffer;

    tpie::array<memory_size_type> slot_state;

    tpie::array<memory_size_type> group_state;

    memory_size_type setting_k;
    memory_size_type current_r;
    memory_size_type setting_m;
    memory_size_type setting_mmark;

    memory_size_type slot_data_id;

    stream_size_type m_size;
    memory_size_type buffer_size;
    memory_size_type buffer_start;

    float block_factor;

    void init(memory_size_type mm_avail, stream_size_type n = std::numeric_limits<stream_size_type>::max() );

    void             slot_start_set(slot_type slot, memory_size_type n);
    memory_size_type slot_start(slot_type slot) const;
    void             slot_size_set(slot_type slot, memory_size_type n);
    memory_size_type slot_size(slot_type slot) const;
    void             group_start_set(group_type group, memory_size_type n);
    memory_size_type group_start(group_type group) const;
    void             group_size_set(group_type group, memory_size_type n);
    memory_size_type group_size(group_type group) const;

    array<temp_file> datafiles;
    array<temp_file> groupdatafiles;

    temp_file & slot_data(slot_type slotid);
    void slot_data_set(slot_type slotid, memory_size_type n);
    temp_file & group_data(group_type groupid);
    memory_size_type slot_max_size(slot_type slotid);
    void write_slot(slot_type slotid, T* arr, memory_size_type len);
    slot_type free_slot(group_type group);
    void empty_group(group_type group);
    void fill_buffer();
    void fill_group_buffer(group_type group);
    void compact(slot_type slot);
    void validate();
    void remove_group_buffer(group_type group);
    void dump();
};

#include "priority_queue.inl"

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

}  //  tpie namespace

#endif