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

Go to the documentation of this file.

#include "LlheapSet.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

#define deleted(x)((x > n()) || (delf != 0 && (*delf)(x)))

namespace grafalgo {

LlheapSet::LlheapSet(int size, delftyp f) : LheapSet(2*size) {
        makeSpace(size); delf = f;
}

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

void LlheapSet::makeSpace(int size) {
        try {
                tmplst = 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 LlheapSet::freeSpace() { delete tmplst; }

void LlheapSet::copyFrom(const LlheapSet& source) {
        if (&source == this) return;
        if (source.n() > n()) resize(source.n());
        else clear();
        for (index i = n()+1; i <= 2*n() ; i++)
                node[i] = source.node[i];
        dummy = source.dummy; delf = source.delf;
}

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

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

void LlheapSet::clear() {
        // build list of dummy nodes linked using left pointers
        LheapSet::clear(); tmplst->clear();
        for (index i = n()+1; i <= 2*n() ; i++) left(i) = i+1;
        dummy = n()+1; left(2*n()) = 0;
        rank(0) = 0; left(0) = right(0) = 0;
}

lheap LlheapSet::lmeld(lheap h1, lheap h2) {
        assert(0 <= h1 && h1 <= 2*n() && 0 <= h2 && h2 <= 2*n() && dummy != 0);
        int i = dummy; dummy = left(dummy);
        left(i) = h1; right(i) = h2;
        return i;
}

lheap LlheapSet::insert(index i, lheap h) {
        assert(0 <= i && i <= n() && 0 <= h && h <= 2*n());
        assert(left(i) == 0 && right(i) == 0 && rank(i) ==1);
        tmplst->clear(); purge(h,*tmplst); h = heapify(*tmplst);
        return meld(i,h);
}

index LlheapSet::findmin(lheap h) {
        assert(0 <= h && h <= 2*n());
        tmplst->clear(); purge(h,*tmplst); return heapify(*tmplst);
}

lheap LlheapSet::heapify(List& hlst) {
        if (hlst.empty()) return 0;
        while (hlst.get(2) != 0) {
                lheap h = meld(hlst.get(1), hlst.get(2));
                hlst.removeFirst(); hlst.removeFirst(); hlst.addLast(h);
        }
        return hlst.first();
}

void LlheapSet::purge(lheap h, List& hlst) {
        if (h == 0) return;
        if (!deleted(h)) {
                hlst.addLast(h);
        } else {
                purge(left(h),hlst); purge(right(h),hlst);
                if (h > n()) {
                        left(h) = dummy; dummy = h; right(h) = 0;
                } else {
                        left(h) = right(h) = 0; rank(h) = 1;
                }
        }
}

lheap LlheapSet::makeheap(List& hlst) {
        assert(hlst.n() <= tmplst->n());
        tmplst->clear();
        for (int i = hlst.first(); i != 0; i = hlst.next(i))
                tmplst->addLast(i);
        return heapify(*tmplst);
}

string& LlheapSet::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& LlheapSet::heap2string(lheap h, bool isroot, string& s) const {
        s = "";
        if (h == 0) return s;
        stringstream ss;
        if (left(h) == 0 && right(h) == 0) {
                if (deleted(h)) ss << "- ";
                else ss << item2string(h,s) << ":" << kee(h) << "," << rank(h);
        } else {
                ss << "(";
                if (left(h) != 0) ss << heap2string(left(h),false,s) << " ";
                if (deleted(h)) {
                        ss << "- ";
                } else {
                        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