/Users/jst/src/grafalgo/cpp/dataStructures/basic/Partition.cpp

Go to the documentation of this file.

#include "Partition.h"

#define p(x) node[x].p
#define rank(x) node[x].rank

namespace grafalgo {

Partition::Partition(int nn, int noOpt1) : Adt(nn) {
        makeSpace(n());
}

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

void Partition::makeSpace(int size) {
        try { node = new pnode[size+1]; } catch (std::bad_alloc e) {
                stringstream ss;
                ss << "Partition::makeSpace: insufficient space for "
                   << size << "elements";
                string s = ss.str();
                throw OutOfSpaceException(s);
        }
        nn = size; clear();
}

void Partition::freeSpace() { delete [] node; }

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

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

void Partition::clear() {
        for (index x = 0; x <= n(); x++) { p(x) = x; rank(x) = 0; }
}

void Partition::copyFrom(const Partition& source) {
        if (&source == this) return;
        if (source.n() > n()) resize(source.n());
        else clear();
        for (index x = 1; x <= source.n(); x++) {
                p(x) = source.node[x].p; rank(x) = source.node[x].rank;
        }
}

index Partition::find(index x) {
        index root;
        for (root = x; p(root) != root; root = p(root)) ;
        while (x != root) { int px = p(x); p(x) = root; x = px; }
        return p(x);
}

index Partition::link(index x, index y) {
        if (rank(x) > rank(y)) {
                index t = x; x = y; y = t;
        } else if (rank(x) == rank(y))
                rank(y)++;
        return p(x) = y;
}

int Partition::findroot(int x) const {
        if (x == p(x)) return(x);
        else return findroot(p(x));
}

string& Partition::toString(string& s) const {
        s = "{";
        int *size = new int[n()+1];
        int *root = new int[n()+1];
        for (int i = 1; i <= n(); i++) { root[i] = findroot(i); size[i] = 0; }
        for (int i = 1; i <= n(); i++) size[root[i]]++;
        // for root nodes x, size[x] is number of nodes in tree
        bool isFirst = true;
        for (int i = 1; i <= n(); i++) {
                if (size[i] > 1) { // i is a root of non-trivial block
                        int j;
                        for (j = 1; root[j] != i; j++) {}
                        string s1;
                        if (isFirst) isFirst = false;
                        else s += " ";
                        s += "[" + Adt::item2string(j,s1);
                        if (j == i) s += "*";
                        for (j++; j <= n(); j++) {
                                if (root[j] == i) {
                                        s += " " + Adt::item2string(j,s1);
                                        if (j == i) s += "*";
                                }
                        }
                        s += "]";
                }
        }
        s += "}";
        delete [] size; delete [] root;
        return s;
}

} // ends namespace