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

Go to the documentation of this file.

#include "RlistSet.h"

namespace grafalgo {

RlistSet::RlistSet(int nn) : Adt(nn) { makeSpace(n()); }

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

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

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

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

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

void RlistSet::clear() {
        for (index x = 0; x <= n(); x++) {
                node[x].p1 = node[x].p2 = x; canon[x] = true;
        }
}

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

index RlistSet::pop(index t) {
        index h = first(t);
        if (h == t) return h;
        index nuHead = suc(h,t);
        if (node[h].p2 == t)    node[t].p1 = node[h].p1;
        else                    node[t].p1 = node[h].p2;
        if (node[nuHead].p1 == h) node[nuHead].p1 = t;
        else                      node[nuHead].p2 = t;
        node[h].p1 = node[h].p2 = h;
        canon[h] = true;
        return t;
}

index RlistSet::join(index t1, index t2) {
        if (t1 == 0) return t2;
        else if (t2 == 0 || t2 == t1) return t1;

        index h1 = node[t1].p1; index h2 = node[t2].p1;
        node[t1].p1 = h2; node[t2].p1 = h1;
        if (t1 == node[h1].p2)  node[h1].p2 = t2;
        else                    node[h1].p1 = t2;
        if (t2 == node[h2].p2)  node[h2].p2 = t1;
        else                    node[h2].p1 = t1;

        canon[t1] = false;
        return t2;
}

index RlistSet::reverse(index t) {
        index h = first(t);
        if (t == 0 || h == t) return t;
        if (t == node[h].p2) node[h].p2 = node[h].p1;
        node[h].p1 = t;
        canon[h] = true; canon[t] = false;
        return h;
}

string& RlistSet::toString(string& s) const {
        s = "";
        for (index x = 1; x <= n(); x++) {
                if (canon[x] && first(x) != x) {
                        string s1; s += toString(x,s1) + "\n";
                }
        }
        return s;
}

string& RlistSet::toString(index t, string& s) const {
        index h = first(t);
        s = "[ "; string s1;
        if (t == 0) s += "-";
        else if (h == t) s += Adt::item2string(h,s1) + " ";
        else {
                index x = h; index y = t;
                do {
                        s += item2string(x,s1) + " ";
                        advance(x,y);
                } while (x != h);
        }
        s += "]";
        return s;
}

} // ends namespace