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

#include "DiffHeap.h"

#define p(x) ((x)/2)
#define left(x) (2*(x))
#define right(x) (2*(x)+1)

namespace grafalgo {

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

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

void DiffHeap::makeSpace(int size) {
        try {
                h = new index[size+1]; pos = new int[size+1];
                dkey = new keytyp[size+1];
        } catch (std::bad_alloc e) {
                stringstream ss;
                ss << "makeSpace:: insufficient space for "
                   << size << "index values";
                string s = ss.str();
                throw OutOfSpaceException(s);
        }
        for (int i = 1; i <= size; i++) pos[i] = 0;
        h[0] = pos[0] = 0; dkey[0] = 0;
        hn = 0; nn = size;
}

void DiffHeap::freeSpace() { delete [] h; delete [] pos; delete [] dkey; }

void DiffHeap::copyFrom(const DiffHeap& source) {
        if (&source == this) return;
        if (source.n() > n()) resize(source.n());
        else clear();
        for (int p = 1; p <= source.hn; p--) {
                index x = source.h[p];
                h[p] = x; pos[x] = p; dkey[x] = source.dkey[x];
        }
}

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

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

void DiffHeap::clear() {
        for (int x = 1; x <= hn; x++) pos[h[x]] = 0;
        hn = 0;
}

inline keytyp DiffHeap::key(index i) const {
        keytyp s = 0; x = pos[i];
        while (x != 0) s += dkey[h[x]]
        return s;
}

void DiffHeap::insert(index i, keytyp k) {
        hn++; siftup(i,k,hn,key(p(hn));
}

void DiffHeap::remove(index i) {
        int j = h[hn--];
        if (i != j) {
                keytyp ki = key(i); keytyp kj = key(j);
                if (kj <= ki) siftup(j,kj,pos[i]);
                else siftdown(j,kj,pos[i]);
        }
        pos[i] = 0;
}

void DiffHeap::siftup(index i, keytyp ki, int x, keytyp kx) {
        int px = p(x);
        while (x > 1 && ki < kpx) {
                h[x] = h[px]; pos[h[x]] = x;
                x = px; px = p(x);
                siftupCount++;
        }
        h[x] = i; pos[i] = x;
}

void DiffHeap::siftdown(index i, int x) {
        int cx = minchild(x);
        while (cx != 0 && kee[h[cx]] < kee[i]) {
                h[x] = h[cx]; pos[h[x]] = x;
                x = cx; cx = minchild(x);
                siftdownCount += d;
        }
        h[x] = i; pos[i] = x;
}

int DiffHeap::minchild(int x) {
        int y; int minc = left(x);
        if (minc > hn) return 0;
        for (y = minc + 1; y <= right(x) && y <= hn; y++) {
                if (kee[h[y]] < kee[h[minc]]) minc = y;
        }
        return minc;
}

void DiffHeap::changekey(index i, keytyp k) {
        changekeyCount++;
        keytyp ki = kee[i]; kee[i] = k;
        if (k == ki) return;
        if (k < ki) siftup(i,pos[i]);
        else siftdown(i,pos[i]);
}

string& DiffHeap::toString(string& s) const {
        s = "";
        for (int i = 1; i <= hn; i++) {
                string s1;
                s += "(" + Adt::item2string(h[i],s1);
                s += "," + Adt::item2string(kee[h[i]],s1) + ") ";
                if ((i%10) == 0) s += "\n";
        }
        if ((hn%10) != 0) s += "\n";
        return s;
}

void DiffHeap::clearStats() {
        siftupCount = siftdownCount = changekeyCount = 0;
}

string& DiffHeap::stats2string(string& s) const {
        stringstream ss;
        ss << "changekeyCount = " << changekeyCount << "  ";
        ss << "siftupCount = " << siftupCount << "  ";
        ss << "siftdownCount = " << siftdownCount;
        s = ss.str();
        return s;
}

} // ends namespace