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

Go to the documentation of this file.

#include "LheapSet.h"

#define kee(x) node[x].kee
#define rank(x) node[x].rank
#define left(x) node[x].left
#define right(x) node[x].right

namespace grafalgo {

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

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

void LheapSet::makeSpace(int size) {
        try {
                node = new hnode[size+1];
        } 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 LheapSet::freeSpace() { delete [] node; }

void LheapSet::copyFrom(const LheapSet& source) {
        if (&source == this) return;
        if (source.n() > n()) resize(source.n());
        else clear();
        for (int i = 1; i <= source.n(); i++) {
                node[i] = source.node[i];
        }
}

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

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

void LheapSet::clear() {
        for (int i = 1; i <= n(); i++) {
                left(i) = right(i) = 0; rank(i) = 1; kee(i) = 0;
        }
        rank(0) = 0; left(0) = right(0) = 0;
}

lheap LheapSet::meld(lheap h1, lheap h2) {
        assert(0 <= h1 && h1 <= n() && 0 <= h2 && h2 <= n());
             if (h1 == 0) return h2;
        else if (h2 == 0) return h1;
        if (kee(h1) > kee(h2)) {
                lheap t = h1; h1 = h2; h2 = t;
        }
        right(h1) = meld(right(h1),h2);
        if (rank(left(h1)) < rank(right(h1))) {
                lheap t = left(h1); left(h1) = right(h1); right(h1) = t;
        }
        rank(h1) = rank(right(h1)) + 1;
        return h1;
}

lheap LheapSet::insert(index i, lheap h) {
        assert(0 <= i && i <= n() && 0 <= h && h <= n());
        assert(left(i) == 0 && right(i) == 0 && rank(i) ==1);
        return meld(i,h);
}

index LheapSet::deletemin(lheap h) {
        lheap h1 = meld(left(h),right(h));
        left(h) = right(h) = 0; rank(h) = 1;
        return h1;
}

string& LheapSet::toString(string& s) const {
        s = "";
        int i; bool *isroot = new bool[n()+1];
        for (i = 1; i <= n(); i++) isroot[i] = true;
        for (i = 1; i <= n(); i++)
                isroot[left(i)] = isroot[right(i)] = false;
        for (i = 1; i <= n(); i++) {
                if (isroot[i] && (left(i) != 0 || right(i) != 0)) {
                        string s1; s += heap2string(i,s1) + "\n";
                }
        }
        delete [] isroot;
        return s;
}

string& LheapSet::heap2string(lheap h, bool isroot, string& s) const {
        s = "";
        if (h == 0) return s;
        stringstream ss;
        if (left(h) == 0 && right(h) == 0) {
                ss << item2string(h,s) << ":" << kee(h) << "," << rank(h);
        } else {
                ss << "(";
                if (left(h) != 0) ss << heap2string(left(h),false,s) << " ";
                ss << item2string(h,s) << ":" << kee(h) << "," << rank(h);
                if (isroot) ss << "*";
                if (right(h) != 0) ss << " " << heap2string(right(h),false,s);
                ss << ")";
        }
        s = ss.str();
        return s;
}

} // ends namespace