pqheap.h

Go to the documentation of this file.

/****************************************************************************
 *
 *  MODULE:     iostream
 *
 
 *  COPYRIGHT (C) 2007 Laura Toma
 *
 *
 
 *  Iostream is a library that implements streams, external memory
 *  sorting on streams, and an external memory priority queue on
 *  streams. These are the fundamental components used in external
 *  memory algorithms.
 
 * Credits: The library was developed by Laura Toma.  The kernel of
 * class STREAM is based on the similar class existent in the GPL TPIE
 * project developed at Duke University. The sorting and priority
 * queue have been developed by Laura Toma based on communications
 * with Rajiv Wickremesinghe. The library was developed as part of
 * porting Terraflow to GRASS in 2001.  PEARL upgrades in 2003 by
 * Rajiv Wickremesinghe as part of the Terracost project.
 
 *
 *  This program is free software; you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation; either version 2 of the License, or
 *  (at your option) any later version.
 *
 
 *  This program 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
 *  General Public License for more details.  *
 *  **************************************************************************/
 
#ifndef _PQHEAP_H
#define _PQHEAP_H
 
#include <assert.h>
#include <stdlib.h>
 
#define PQHEAP_MEM_DEBUG if (0)
 
// HEAPSTATUS can be defined at compile time
 
// this flag is currently off; we used it at some point for checking
// how many times is each element in the heap accessed or something
// like that
#ifdef HEAPSTATUS
static const int PAGESIZE = 1024;
#endif
 
// Helper functions for navigating through a binary heap.
/* for simplicity the heap structure is slightly modified as:
   0
   |
   1
   /\
  2  3
 /\  /\
4 5 6  7
 
*/
 
// The children of an element of the heap.
static inline unsigned int heap_lchild(unsigned int index)
{
    return 2 * index;
}
 
static inline unsigned int heap_rchild(unsigned int index)
{
    return 2 * index + 1;
}
 
// The parent of an element.
static inline unsigned int heap_parent(unsigned int index)
{
    return index >> 1;
}
 
// return minimum of two integers
static inline unsigned int mymin(unsigned int a, unsigned int b)
{
    return (a <= b) ? a : b;
}
 
/**************************************************************
***************************************************************
***************************************************************
 
Priority queue templated on a single type
 
assume T to be a class with getPriority() and getValue() implemented;
 
Supported operations: min, extract_min, insert in O(lg n)
 
 
***************************************************************
***************************************************************
***************************************************************/
template <class T>
class pqheap_t1 {
    // A pointer to an array of elements
    T *elements;
 
    // The number of elements currently in the queue.
    unsigned int cur_elts;
 
    // The maximum number the queue can hold.
    unsigned int max_elts;
 
private:
    void heapify(unsigned int root);
 
public:
    inline pqheap_t1(unsigned int size);
 
    // build heap from an array of elements; array a is REUSED, and NOT
    // COPIED, for efficiency; it'd better not be used after this
    // outside!!!
    inline pqheap_t1(T *a, unsigned int size);
 
    inline ~pqheap_t1(void);
 
    // build a heap from an array of elements;
    // if size > max_elts, insert first maxsize elements from array;
    // return nb of elements that did not fit;
    unsigned int fill(T *a, unsigned int size);
 
    // Is it full?
    inline bool full(void);
 
    // Is it empty?
    inline bool empty(void);
    inline bool is_empty() { return empty(); };
 
    // How many elements?
    inline unsigned int num_elts(void);
 
    // How many elements? sorry - i could never remember num_elts
    inline unsigned int size(void) const { return cur_elts; };
 
    // Min
    inline bool min(T &elt);
    T min();
 
    // Extract min and set elt = min
    inline bool extract_min(T &elt);
 
    // extract all elts with min key, add them and return their sum
    inline bool extract_all_min(T &elt);
 
    // delete min; same as extract_min, but ignore the value extracted
    inline bool delete_min();
 
    // Insert
    inline bool insert(const T &elt);
 
    // Delete the current minimum and insert the new item x;
    // the minimum item is lost (i.e. not returned to user);
    // needed to optimize merge
    inline void delete_min_and_insert(const T &x);
 
    // this function is a dirty way to allow building faster the heap
    // in case we build it from a sorted array; in that case we dont need
    // to 'insert' and then 'heapify', but it is enough to 'set'
    void set(long i, T &elt);
 
    // print
    inline friend ostream &operator<<(ostream &s, const pqheap_t1<T> &pq)
    {
        s << "PQ: ";
        s.flush();
        for (unsigned int i = 0; i < mymin(10, pq.cur_elts); i++) {
            s << "["
              //<< pq.elements[i].getPriority() << ","
              //<< pq.elements[i].getValue()
              << pq.elements[i] << "]";
        }
        return s;
    }
    // print
    void print();
 
    // print
    void print_range();
 
#ifdef HEAPSTATUS
    inline void heapstatus(int d);
    inline void heaptouch(unsigned int pos);
    unsigned int *numtouch;
#endif
};
 
//************************************************************/
template <class T>
inline pqheap_t1<T>::pqheap_t1(unsigned int size)
{
 
    elements = new T[size];
    cout << "pqheap_t1: register memory\n";
    cout.flush();
    PQHEAP_MEM_DEBUG cout << "pqheap_t1::pq_heap_t1: allocate\n";
    //  PQHEAP_MEM_DEBUG MMmanager.print();
 
    if (!elements) {
        cerr << "could not allocate priority queue: insufficient memory..\n";
        exit(1);
    }
    assert(elements);
 
    max_elts = size;
    cur_elts = 0;
 
#ifdef HEAPSTATUS
    numtouch = new unsigned int[size / PAGESIZE];
    assert(numtouch);
    for (int i = 0; i < size / PAGESIZE; i++) {
        numtouch[i] = 0;
    }
#endif
}
 
//************************************************************/
/* (this constructor is a bit nasty) Build heap from an array of
   elements; array a is reused, and not copied, for efficiency; it'd
   better not be used after this outside!!! */
template <class T>
inline pqheap_t1<T>::pqheap_t1(T *a, unsigned int size)
{
    {
        static int flag = 0;
        if (!flag) {
            cerr << "Using slow build in pqheap_t1" << endl;
            flag = 1;
        }
    }
 
    elements = a;
    max_elts = size;
    cur_elts = size;
 
    if (max_elts) {
        for (int i = heap_parent(max_elts - 1); i >= 0; i--) {
            // cout << "heapify i=" << i<<"\n";
            heapify(i);
        }
    }
}
 
//************************************************************/
template <class T>
inline pqheap_t1<T>::~pqheap_t1()
{
#ifdef HEAPSTATUS
    cout << endl << "pagesize = " << PAGESIZE << endl;
    cout << "max_elts = " << max_elts << endl;
    unsigned int n = max_elts / PAGESIZE;
    for (unsigned int i = 0; i < n; i++) {
        cout << form("PQTEMP %d\t%d", i, numtouch[i]) << endl;
    }
    delete[] numtouch;
#endif
 
    delete[] elements;
    cur_elts = 0;
    max_elts = 0;
    return;
}
 
//************************************************************/
// build a heap from an array of elements;
// if size > max_elts, insert first maxsize elements from array;
// return nb of elements that did not fit;
template <class T>
inline unsigned int pqheap_t1<T>::fill(T *a, unsigned int size)
{
    unsigned int i;
    assert(cur_elts == 0);
    for (i = 0; i < size; i++) {
        if (!insert(a[i])) {
            break;
        }
    }
    if (i < size) {
        assert(i == max_elts);
        return size - i;
    }
    else {
        return 0;
    }
}
 
//************************************************************/
template <class T>
inline bool pqheap_t1<T>::full(void)
{
    return cur_elts == max_elts;
}
 
//************************************************************/
template <class T>
inline bool pqheap_t1<T>::empty(void)
{
    return cur_elts == 0;
}
 
//************************************************************/
template <class T>
inline unsigned int pqheap_t1<T>::num_elts(void)
{
    return cur_elts;
}
 
//************************************************************/
template <class T>
inline bool pqheap_t1<T>::min(T &elt)
{
    if (!cur_elts) {
        return false;
    }
    elt = elements[0];
    return true;
}
 
//************************************************************/
template <class T>
T pqheap_t1<T>::min()
{
    T elt;
    if (min(elt)) {
        return elt;
    }
    else {
        cerr << "unguarded min failed" << endl;
        assert(0);
        exit(1);
    }
    return elt;
}
 
//************************************************************/
// this function is a dirty hack to allow building faster the heap
// in case we build it from a sorted array; in thiat case we dont need
// to 'insert' and then 'heapify', but it is enough to 'set'
template <class T>
inline void pqheap_t1<T>::set(long i, T &elt)
{
    // must always set precisely the next element
    assert(i == cur_elts);
    elements[i] = elt;
    cur_elts++;
}
 
//************************************************************/
#ifdef HEAPSTATUS
template <class T>
inline void pqheap_t1<T>::heaptouch(unsigned int pos)
{
    numtouch[pos / PAGESIZE]++;
    assert(numtouch[pos / PAGESIZE] > 0);
}
#endif
 
#ifdef HEAPSTATUS
template <class T>
inline void pqheap_t1<T>::heapstatus(int d)
{
    static int count = 0;
    static int delta = 0;
 
    delta += d;
    count++;
 
    if ((count % 10000) == 0) {
        cout << endl << form("PQHEAP %d\t%d", cur_elts, delta) << endl;
        count = 0;
        delta = 0;
    }
}
#endif
 
//************************************************************/
template <class T>
inline bool pqheap_t1<T>::extract_min(T &elt)
{
    if (!cur_elts) {
        return false;
    }
    elt = elements[0];
    elements[0] = elements[--cur_elts];
    heapify(0);
 
#ifdef HEAPSTATUS
    heaptouch(cur_elts);
    heaptouch(0);
    heapstatus(-1);
#endif
 
    return true;
}
 
//************************************************************/
// extract all elts with min key, add them and return their sum
template <class T>
inline bool pqheap_t1<T>::extract_all_min(T &elt)
{
 
    T next_elt;
    bool done = false;
 
    // extract first elt
    if (!extract_min(elt)) {
        return false;
    }
    else {
        while (!done) {
            // peek at the next min elt to see if matches
            if ((!min(next_elt)) ||
                !(next_elt.getPriority() == elt.getPriority())) {
                done = true;
            }
            else {
                extract_min(next_elt);
                elt = elt + next_elt;
            }
        }
    }
    return true;
}
 
//************************************************************/
template <class T>
inline bool pqheap_t1<T>::delete_min()
{
    T dummy;
    return extract_min(dummy);
}
 
//************************************************************/
template <class T>
inline bool pqheap_t1<T>::insert(const T &elt)
{
    unsigned int ii;
 
    if (full()) {
        return false;
    }
 
    for (ii = cur_elts++;
         ii && (elements[heap_parent(ii)].getPriority() > elt.getPriority());
         ii = heap_parent(ii)) {
        elements[ii] = elements[heap_parent(ii)];
    }
    elements[ii] = elt;
 
#ifdef HEAPSTATUS
    heaptouch(ii);
    heapstatus(+1);
#endif
 
    return true;
}
 
//************************************************************/
template <class T>
inline void pqheap_t1<T>::heapify(unsigned int root)
{
    unsigned int min_index = root;
    unsigned int lc = heap_lchild(root);
    unsigned int rc = heap_rchild(root);
 
#ifdef HEAPSTATUS
    // already did the root, so dont do it again
    if (lc < cur_elts) {
        heaptouch(lc);
    }
    if (rc < cur_elts) {
        heaptouch(rc);
    }
#endif
    if ((lc < cur_elts) &&
        ((elements[lc].getPriority()) < elements[min_index].getPriority())) {
        min_index = lc;
    }
    if ((rc < cur_elts) &&
        ((elements[rc].getPriority()) < elements[min_index].getPriority())) {
        min_index = rc;
    }
 
    if (min_index != root) {
        T tmp_q = elements[min_index];
 
        elements[min_index] = elements[root];
        elements[root] = tmp_q;
 
        heapify(min_index);
    }
}
 
//************************************************************/
// Delete the current minimum and insert the new item;
// the minimum item is lost (i.e. not returned to user);
// needed to optimize merge
template <class T>
inline void pqheap_t1<T>::delete_min_and_insert(const T &x)
{
    assert(cur_elts);
    elements[0] = x;
    heapify(0);
}
 
/************************************************************/
template <class T>
void pqheap_t1<T>::print()
{
    cout << "[";
    for (unsigned int i = 0; i < cur_elts; i++) {
        cout << elements[i].getPriority().field1() << ",";
    }
    cout << "]";
}
 
/************************************************************/
template <class T>
void pqheap_t1<T>::print_range()
{
    cout << "[";
    T a, b;
    min(a);
    max(b);
    if (cur_elts) {
        cout << a.getPriority().field1() << ".." << b.getPriority().field1();
    }
    cout << " (" << cur_elts << ")]";
}
 
#endif // _PQUEUE_HEAP_H