/Users/jst/src/grafalgo/cpp/include/DheapSet.h

Go to the documentation of this file.

#ifndef DHEAPSET_H
#define DHEAPSET_H

#include <list>
#include "stdinc.h"
#include "Adt.h"

namespace grafalgo {

typedef int keytyp;

class DheapSet : public Adt {
public:         DheapSet(int,int,int=8);
                ~DheapSet();

        // common methods
        void    clear();
        void    resize(int,int,int=8);
        void    resize(int size) { resize(size,size,8); }
        void    expand(int,int,int=8);
        void    expand(int size) { expand(size,max(size,maxHeap),d); }
        void    copyFrom(const DheapSet&);

        // access methods
        index   findMin(int) const;
        keytyp  getKey(index) const;
        int     heapSize(int) const;

        // predicates 
        bool    empty(int) const;       

        // modifiers 
        bool    insert(index, keytyp, int);
        index   deleteMin(int);
        void    changeKeyMin(keytyp, int);

        string& toString(int, string&) const;
        string& toString(string&) const;
private:
        int     maxHeap;                
        int     d = 8;                  
        int     numNodes;               

        index   *heaps;                 
        keytyp  *key;                   

        int     *root;                  
        int     *bot;                   
        int     *hSize;                 
        
        int     *child;                 
        int     *parent;                
        int     *pred;                  
        
        int     free;                   

        index   nodeMinPos(int) const;  
        void    siftup(index,int);      
        void    siftdown(index,int);    

        void    makeSpace(int,int,int=8);
        void    freeSpace();
};

inline int DheapSet::nodeMinPos(int p) const {
        if (p == -1 || heaps[p] == 0) return -1;
        int minPos = p;
        for (int q = p+1; q < p+d && heaps[q] != 0; q++)
                if (key[heaps[q]] < key[heaps[minPos]])
                        minPos = q;
        return minPos;
}

// Return item at top of heap
inline int DheapSet::findMin(int h) const {
        if (hSize[h] == 0) return 0;
        int p = nodeMinPos(root[h]);
        return (p < 0 ? 0 : heaps[p]);
}

// Return key of i.
inline keytyp DheapSet::getKey(index i) const { return key[i]; }

// Return true if heap is empty, else false.
inline bool DheapSet::empty(int h) const { return hSize[h] == 0; };

// Return the size of a heap.
inline int DheapSet::heapSize(int h) const { return hSize[h]; };

} // ends namespace

#endif