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

Go to the documentation of this file.

#include "ClistSet.h"

namespace grafalgo {

ClistSet::ClistSet(int n1) : Adt(n1) { makeSpace(n()); }

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

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

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

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

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

void ClistSet::clear() {
        for (index i = 0; i <= n(); i++) {
                node[i].next = node[i].prev = i;
        }
}

void ClistSet::copyFrom(const ClistSet& source) {
        if (&source == this) return;
        if (source.n() > n()) resize(source.n());
        else clear();
        for (index x = 0; x <= source.n(); x++) {
                node[x].next = source.suc(x);
                node[x].prev = source.pred(x);
        }
}

void ClistSet::remove(index i) {
        assert(0 <= i && i <= n());
        node[node[i].prev].next = node[i].next;
        node[node[i].next].prev = node[i].prev;
        node[i].next = node[i].prev = i;
}


void ClistSet::join(index i, index j) {
        assert(0 <= i && i <= n() && 0 <= j && j <= n());
        if (i == 0 || j == 0) return;
        node[node[i].next].prev = node[j].prev;
        node[node[j].prev].next = node[i].next;
        node[i].next = j; node[j].prev = i;
}

string& ClistSet::toString(string& s) const {
        index i, j; string s1;
        int *mark = new int[n()+1];
        s = "{";
        int cnt = 0;
        for (i = 1; i <= n(); i++) mark[i] = 0;
        for (i = 1; i <= n(); i++) {
                if (mark[i]) continue; 
                mark[i] = 1;
                if (node[i].next == i) continue;
                if (++cnt > 1) s += ", ";
                s += "[";
                s += Adt::item2string(i,s1);
                for (j = node[i].next; j != i; j = node[j].next) {
                        mark[j] = 1;
                        s += " ";
                        s += Adt::item2string(j,s1);
                }
                s += "]";
        }
        s += "}";
        delete [] mark;
        return s;
}

} // ends namespace