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

Go to the documentation of this file.

#ifndef FHEAPS_H
#define FHEAPS_H

#include "stdinc.h"
#include "Adt.h"
#include "Util.h"
#include "List.h"
#include "ClistSet.h"

namespace grafalgo {

typedef int keytyp;
typedef int fheap;

class FheapSet : public Adt {
public:         FheapSet(int=26);
                ~FheapSet();

        // common methods
        void    clear();
        void    resize(int);
        void    expand(int);
        void    copyFrom(const FheapSet&);

        keytyp  key(index) const;               
        void    setKey(index,keytyp);
        fheap   findmin(fheap) const;   
        fheap   meld(fheap,fheap);
        fheap   decreasekey(index,keytyp,fheap);
        fheap   deletemin(fheap);       
        fheap   insert(index,fheap);
        fheap   insert(index,fheap,keytyp);
        fheap   remove(index, fheap);   

        string& toString(string&) const;
        string& heap2string(fheap,string&) const;
private:
        static const int MAXRANK = 32;
        struct Fnode {                  
        keytyp  kee;                    
        int     rank;                   
        bool    mark;                   
        fheap   p, c;                   
        };
        Fnode   *node;                  
        ClistSet *sibs;                 
        int     rvec[MAXRANK+1];        
        List    *tmpq;                  

        string& heap2string(fheap,bool,string&) const;
        void    makeSpace(int);
        void    freeSpace();
};

inline keytyp FheapSet::key(index i) const { return node[i].kee; }

inline void FheapSet::setKey(index i, keytyp k) {
        assert(sibs->suc(i) == i && node[i].p == 0 && node[i].c == 0);
        node[i].kee = k;
}

inline fheap FheapSet::insert(index i, fheap h) { return meld(i,h); }
        
inline fheap FheapSet::findmin(fheap h) const { return h; }

} // ends namespace

#endif