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

Go to the documentation of this file.

#include "PathSet.h"

#define left(x) pnode[x].left
#define right(x) pnode[x].right
#define p(x) pnode[x].p
#define dcost(x) pnode[x].dcost
#define dmin(x) pnode[x].dmin

namespace grafalgo {

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

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

void PathSet::makeSpace(int size) {
        try {
                pnode = new PathNode[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 PathSet::freeSpace() {
        delete [] pnode;
}

void PathSet::clear() {
        for (index i = 0; i <= n(); i++) {
                left(i) = right(i) = p(i) = dcost(i) = dmin(i) = 0;
        }
}

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

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

        for (index x = 1; x <= n(); x++) {
                pnode[x] = source.pnode[x];
        }
}

index PathSet::splay(index x) {
        while (p(x) != 0) splaystep(x);
        return x;
}

void PathSet::splaystep(index x) {
        index y = p(x);
        if (y == 0) return;
        index z = p(y);
        if (x == left(left(z)) || x == right(right(z)))
                rotate(y);
        else if (z != 0) // x is "inner grandchild"
                rotate(x);
        rotate(x);
}

void PathSet::rotate(index x) {
        index y = p(x); if (y == 0) return;
        index a, b, c;
        if (x == left(y)) { a = left(x);  b = right(x); c = right(y); }
        else              { a = right(x); b = left(x);  c = left(y);  }

        // do the rotation
        p(x) = p(y);
             if (y == left(p(y)))  left(p(x)) = x;
        else if (y == right(p(y))) right(p(x)) = x;
        if (x == left(y)) {
                left(y) = right(x);
                if (left(y) != 0) p(left(y)) = y;
                right(x) = y;
        } else {
                right(y) = left(x);
                if (right(y) != 0) p(right(y)) = y;
                left(x) = y;
        }
        p(y) = x;

        // update dmin, dcost values
        dmin(a) += dmin(x); dmin(b) += dmin(x);

        dcost(x) = dcost(x) + dmin(x);
        cost dmx = dmin(x);
        dmin(x) = dmin(y);

        dmin(y) = dcost(y);
        if (b != 0) dmin(y) = min(dmin(y),dmin(b)+dmx);
        if (c != 0) dmin(y) = min(dmin(y),dmin(c));
        dcost(y) = dcost(y) - dmin(y);

        dmin(b) -= dmin(y); dmin(c) -= dmin(y);
}

path PathSet::findpath(index i) { 
        index x;
        for (x = i; p(x) != 0; x = p(x)) {}
        splay(i);
        return x;
}

path PathSet::findtail(path q) {
        if (q == 0) return 0;
        while (right(q) != 0) q = right(q);
        return splay(q);
}

void PathSet::addpathcost(path q, cost x) { dmin(q) += x; }

PathSet::PathCostPair PathSet::findpathcost(path q) {
        while (1) {
                if (right(q) != 0 && dmin(right(q)) == 0)
                        q = right(q);
                else if (dcost(q) > 0)
                        q = left(q);
                else
                        break;
        }
        q = splay(q);
        PathCostPair cp(q,dmin(q));
        return cp;
}

path PathSet::findtreeroot(index i) {
        while (p(i) != 0) i = p(i);
        return i;
}

path PathSet::join(path r, index i, path q) {
        cost dmin_i = dmin(i);
        left(i) = r; right(i) = q;
        if (r == 0 && q == 0) {
                ; // do nothing
        } else if (r == 0) {
                dmin(i) = min(dmin(i),dmin(q));
                dmin(q) -= dmin(i);
                p(q) = i;
        } else if (q == 0) {
                dmin(i) = min(dmin(i),dmin(r));
                dmin(r) -= dmin(i);
                p(r) = i;
        } else {
                dmin(i) = min(dmin(r),min(dmin(i),dmin(q)));
                dmin(r) -= dmin(i); dmin(q) -= dmin(i);
                p(r) = p(q) = i;
        }
        dcost(i) = dmin_i - dmin(i);
        return i;
}

PathSet::PathPair PathSet::split(index i) {
        PathPair pair(0,0);

        splay(i);
        if (left(i) == 0) 
                pair.p1 = 0;
        else {
                pair.p1 = left(i); p(pair.p1) = 0; left(i) = 0;
                dmin(pair.p1) += dmin(i);
        } 
        if (right(i) == 0) 
                pair.p2 = 0;
        else {
                pair.p2 = right(i); p(pair.p2) = 0; right(i) = 0;
                dmin(pair.p2) += dmin(i);
        } 
        dmin(i) += dcost(i);
        dcost(i) = 0;

        return pair;
}

cost PathSet::nodeCost(index i) const {
        cost s;
        s = dcost(i);
        while (i != 0) { s += dmin(i); i = p(i); }
        return s;
}

string& PathSet::path2string(path q, string& s) const {
        s = "";
        if (q == 0) return s;
        stringstream ss;
        ss << path2string(left(q),s);
        ss << Adt::item2string(q,s) << ":" << nodeCost(q) << " ";
        ss << path2string(right(q),s);
        s = ss.str();
        return s;
}

string& PathSet::pathTree2string(path q, string& s) const {
        stringstream ss;
        s = "";
        if (q == 0) return s;
        bool singleton = (left(q) = 0 && right(q) == 0);
        if (!singleton) ss << "(";
        ss << pathTree2string(left(q),s);
        ss << Adt::item2string(q,s) << ":" << nodeCost(q) << " ";
        ss << pathTree2string(right(q),s);
        if (!singleton) ss << ")";
        s = ss.str();
        return s;
}

string& PathSet::toString(string& s) const {
        s = ""; string s1;
        for (index i = 1; i <= n(); i++) {
                if (p(i) == 0) s += path2string(i,s1) + "\n";
        }
        return s;
}

} // ends namespace