/Users/jst/src/grafalgo/cpp/dataStructures/advanced/Dtrees.cpp

Go to the documentation of this file.

#include "Dtrees.h"

#define p(x) parentOf[x]
#define succ(x) successor[x]

namespace grafalgo {

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

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

void Dtrees::makeSpace(int size) {
        try {
                ps = new PathSet(size);
                parentOf = new index[size+1];
                successor = new index[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 Dtrees::freeSpace() {
        delete ps; delete [] parentOf; delete [] successor;
}

void Dtrees::clear() {
        ps->clear();
        for (index x = 1; x <= n(); x++) {
                p(x) = succ(x) = 0;
        }
}

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

void Dtrees::expand(int size) {
        if (size <= n()) return;
        Dtrees old(this->n()); old.copyFrom(*this);
        resize(size); this->copyFrom(old);
}
void Dtrees::copyFrom(const Dtrees& source) {
        if (&source == this) return;
        if (source.n() > n()) resize(source.n());
        else clear();

        ps->copyFrom(*(source.ps));
        for (index x = 1; x <= n(); x++) {
                p(x) = source.parentOf[x];
                succ(x) = source.successor[x];
        }
}

path Dtrees::expose(index i) {
        PathNodePair pnPair(0,i);
        while (pnPair.i != 0) pnPair = splice(pnPair);
        succ(pnPair.p) = 0;
        return pnPair.p;
}

Dtrees::PathNodePair Dtrees::splice(PathNodePair pnPair) {
        index w = succ(ps->findpath(pnPair.i));
        PathSet::PathPair pp = ps->split(pnPair.i);
        if (pp.p1 != 0) succ(pp.p1) = pnPair.i;
        pnPair.p = ps->join(pnPair.p,pnPair.i,pp.p2); pnPair.i = w;
        return pnPair;
}

index Dtrees::findroot(index i) {
        index x;
        x = ps->findtail(expose(i));
        succ(x) = 0; // relies on fact that x is canonical element on return
        return x;
}

NodeCostPair Dtrees::findcost(index i) {
        NodeCostPair cp = ps->findpathcost(expose(i));
        succ(cp.x) = 0;
        return cp;
}

void Dtrees::addcost(index i, cost x) {
        ps->addpathcost(expose(i),x);
}

void Dtrees::link(tree t, index i) {
        p(t) = i;
        succ(ps->join(0,expose(t),expose(i))) = 0;
}

void Dtrees::cut(index i) {
        p(i) = 0;
        expose(i);
        PathSet::PathPair pp = ps->split(i);
        succ(i) = 0;
        if (pp.p2 != 0) succ(pp.p2) = 0;
        return;
}

string& Dtrees::path2string(path q, string& s) const {
        string s1;
        s = ps->path2string(q,s1);
        s += " succ(" + Adt::item2string(q,s1);
        s += ")=" + Adt::item2string(succ(q),s1) + "\n";
        return s;
}

string& Dtrees::toString(string& s) const {
        string s1;
        s = "";
        for (index i = 1; i <= n(); i++) {
                index j = ps->findtreeroot(i);
                if (i == j) s += path2string(i,s1);
        }
        return s;
}

} // ends namespace