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

Go to the documentation of this file.

#include "Dheap.h"

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

namespace grafalgo {

Dheap::Dheap(int size, int dd) : Adt(size), d(dd) {
        makeSpace(size);
}

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

void Dheap::makeSpace(int size) {
        try {
                h = new index[size+1]; pos = new int[size+1];
                kee = 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; kee[0] = 0;
        hn = 0; nn = size;
}

void Dheap::freeSpace() { delete [] h; delete [] pos; delete [] kee; }

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

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

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

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

void Dheap::insert(index i, keytyp k) {
        kee[i] = k; hn++; siftup(i,hn);
}

void Dheap::remove(index i) {
        int j = h[hn--];
        if (i != j) {
                if (kee[j] <= kee[i]) siftup(j,pos[i]);
                else siftdown(j,pos[i]);
        }
        pos[i] = 0;
}

void Dheap::siftup(index i, int x) {
        int px = p(x);
        while (x > 1 && kee[i] < kee[h[px]]) {
                h[x] = h[px]; pos[h[x]] = x;
                x = px; px = p(x);
        }
        h[x] = i; pos[i] = x;
}

void Dheap::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);
        }
        h[x] = i; pos[i] = x;
}

int Dheap::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 Dheap::changekey(index i, keytyp k) {
        keytyp ki = kee[i]; kee[i] = k;
        if (k == ki) return;
        if (k < ki) siftup(i,pos[i]);
        else siftdown(i,pos[i]);
}

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

} // ends namespace