/Users/jst/src/grafalgo/cpp/dataStructures/heaps/FheapSet.cpp

#include "FheapSet.h"

namespace grafalgo {

#define left(x) sibs->pred(x)
#define right(x) sibs->suc(x)
#define kee(x) node[x].kee
#define rank(x) node[x].rank
#define mark(x) node[x].mark
#define p(x) node[x].p
#define c(x) node[x].c

FheapSet::FheapSet(int size) : Adt(size) { makeSpace(size); }

FheapSet::~FheapSet() { freeSpace(); }

void FheapSet::makeSpace(int size) {
        try {
                node = new Fnode[size+1];
                sibs = new ClistSet(size);
                tmpq = new List(size);
        } catch (std::bad_alloc e) {
                stringstream ss;
                ss << "makeSpace:: insufficient space for "
                   << size << "index values";
                string s = ss.str();
                throw OutOfSpaceException(s);
        }
        nn = size; clear();
}

void FheapSet::freeSpace() { delete [] node; delete sibs; delete tmpq; }

void FheapSet::copyFrom(const FheapSet& source) {
        if (&source == this) return;
        if (source.n() > n()) resize(source.n());
        else clear();

        (*sibs).copyFrom(*source.sibs);
        for (index x = 1; x <= source.n(); x++) {
                c(x) = source.node[x].c;
                p(x) = source.node[x].p;
                rank(x) = source.node[x].rank;
                kee(x) = source.node[x].kee;
                mark(x) = source.node[x].mark;
        }
}

void FheapSet::resize(int size) {
        freeSpace();
        try { makeSpace(size); } catch(OutOfSpaceException e) {
                string s; s = "FheapSet::resize::" + e.toString(s);
                throw OutOfSpaceException(s);
        }
}

void FheapSet::expand(int size) {
        if (size <= n()) return;
        FheapSet old(this->n()); old.copyFrom(*this);
        resize(size); this->copyFrom(old);
}

void FheapSet::clear() {
        sibs->clear();
        for (index x = 0; x <= n(); x++) {
                c(x) = p(x) = rank(x) = kee(x) = 0; mark(x) = false;
        }
        for (index x = 0; x <= FheapSet::MAXRANK; x++) rvec[x] = 0;
}

fheap FheapSet::meld(fheap h1, fheap h2) {
        assert(0 <= h1 && h1 <= n() && 0 <= h2 && h2 <= n());
        if (h1 == 0) return h2;
        if (h2 == 0) return h1;
        sibs->join(h1,h2);
        return kee(h1) <= kee(h2) ? h1 : h2;
}

fheap FheapSet::insert(index i, fheap h, keytyp x) {
        assert(0 <= i && i <= n() && 0 <= h && h <= n());
        setKey(i,x);
        return meld(i,h);
}

fheap FheapSet::decreasekey(index i, keytyp delta, fheap h) {
        assert(0 <= i && i <= n() && 0 <= h && h <= n() && delta >= 0);
        fheap pi = p(i);
        kee(i) -= delta;
        if (pi == 0) return kee(i) < kee(h) ? i : h;
        c(pi) = rank(pi) == 1 ? 0: left(i);
        rank(pi)--;
        sibs->remove(i);
        p(i) = 0;
        h = meld(i,h);
        if (p(pi) == 0) return h;
        if (!mark(pi))  mark(pi) = true;
        else            h = decreasekey(pi,0,h);
        return h;
}

fheap FheapSet::deletemin(fheap h) {
        assert(1 <= h && h <= n());
        index i,j; int k,mr;

        // Merge h's children into root list and remove it
        sibs->join(h,c(h)); c(h) = 0; rank(h) = 0;
        if (left(h) == h) return 0;
        i = left(h);
        sibs->remove(h);
        
        // Build queue of roots and find root with smallest key
        h = i; tmpq->addLast(i); p(i) = 0;
        for (j = right(i); j != i; j = right(j)) {
                if (kee(j) < kee(h)) h = j;
                tmpq->addLast(j); p(j) = 0;
        }
        mr = -1;
        while (!tmpq->empty()) {
                // scan roots, merging trees of equal rang
                i = tmpq->first(); tmpq->removeFirst();
                if (rank(i) > FheapSet::MAXRANK)
                        Util::fatal("deletemin: rank too large");
                j = rvec[rank(i)];
                if (mr < rank(i)) {
                        for (mr++; mr < rank(i); mr++) rvec[mr] = 0;
                        rvec[rank(i)] = i;
                } else if (j == 0) {
                        rvec[rank(i)] = i;
                } else if (kee(i) < kee(j)) {
                        sibs->remove(j);
                        sibs->join(c(i),j); c(i) = j;
                        rvec[rank(i)] = 0;
                        rank(i)++;
                        p(j) = i; mark(j) = false;
                        tmpq->addLast(i);
                } else {
                        sibs->remove(i);
                        sibs->join(c(j),i); c(j) = i;
                        rvec[rank(i)] = 0;
                        rank(j)++;
                        p(i) = j; mark(i) = false;
                        if (h == i) h = j;
                        tmpq->addLast(j);
                }
        }
        for (k = 0; k <= mr; k++) rvec[k] = 0;
        return h;
}

fheap FheapSet::remove(index i, fheap h) {
        assert(1 <= i && i <= n() && 1 <= h && h <= n());
        keytyp k;
        k = kee(i);
        h = decreasekey(i,(kee(i)-kee(h))+1,h);
        h = deletemin(h);
        kee(i) = k;
        return h;
}

string& FheapSet::toString(string& s) const {
        s = "";
        bool *pmark = new bool[n()+1];
        for (int i = 1; i <= n(); i++) pmark[i] = false;
        for (int i = 1; i <= n(); i++) {
                if (p(i) == 0 && !pmark[i]) {
                        // i is a root in a new heap
                        if (c(i) == 0 && left(i) == i) continue;
                        // find minkey item, mark all tree roots in this heap
                        pmark[i] = true;
                        int k = i;
                        for (int j = sibs->suc(i); j != i; j = sibs->suc(j)) {
                                if (key(j) < key(k)) k = j; 
                                pmark[j] = true;
                        }
                        string s1;
                        s += heap2string(k,s1) + "\n";
                }
        }
        delete [] pmark;
        return s;
}

string& FheapSet::heap2string(fheap h, string& s) const {
        s = "";
        if (h == 0 || (p(h) == 0 && c(h) == 0 && left(h) == h)) return s;
        stringstream ss;
        ss << "[" << item2string(h,s) << ":" << kee(h) << "," << rank(h);
        if (mark(h)) ss << "*";
        ss << heap2string(c(h),s);
        for (index i = right(h); i != h; i = right(i)) {
                ss << " " << item2string(i,s) << ":" << kee(i) << "," <<rank(i);
                if (mark(i)) ss << "*";
                ss << heap2string(c(i),s);
        }
        ss << "]";
        s = ss.str();
        return s;
}

} // ends namespace