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

Go to the documentation of this file.

#include "ListSet.h"

namespace grafalgo {

ListSet::ListSet(int nitems, int nlists) : Adt(nitems), nlst(nlists) {
        makeSpace(nitems,nlists);
}

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

void ListSet::makeSpace(int nitems, int nlists) {
        try {
                nxt = new index[nitems+1]; lh = new listhdr[nlists+1];
        } catch (std::bad_alloc e) {
                stringstream ss;
                ss << "ListSet::makeSpace: insufficient space for "
                   << nitems << "index values and " << nlists << " lists";
                string s = ss.str();
                throw OutOfSpaceException(s);
        }
        for (int i = 0; i <= nlst; i++) { lh[i].head = lh[i].tail = 0; }
        for (int i = 0; i <= nitems; i++) nxt[i] = -1;
        nn = nitems; nlst = nlists;
}

void ListSet::freeSpace() { delete [] lh; delete [] nxt; }

void ListSet::clear() {
        for (alist ll = 1; ll <= nlst; ll++) {
                while (!empty(ll)) removeFirst(ll);
        }
}

void ListSet::resize(int nitems, int nlists) {
        freeSpace();
        try { makeSpace(nitems,nlists); } catch(OutOfSpaceException e) {
                string s; s = "ListSet::resize:" + e.toString(s);
                throw OutOfSpaceException(s);
        }
}

void ListSet::expand(int nitems, int nlists) {
        if (nitems <= n() && nlists <= nlst) return;
        ListSet old(this->n(),this->nlst); old.copyFrom(*this);
        resize(nitems,nlists); this->copyFrom(old);
}

void ListSet::copyFrom(const ListSet& src) {
        if (&src == this) return;
        if (src.n() > n() || src.nlst > nlst) resize(src.n(),src.nlst);
        else clear();
        for (alist ll = 1; ll <= src.nlst; ll++) {
                for (index x = src.first(ll); x != 0; x = src.next(ll))
                        addLast(x,ll);
        }
}

void ListSet::addLast(index i, alist j) {
        if (i == 0) return;
        if (lh[j].head == 0) lh[j].head = i;
        else nxt[lh[j].tail] = i;
        lh[j].tail = i; nxt[i] = 0;
}

int ListSet::removeFirst(alist j) {
        int i = lh[j].head;
        if (i == 0) return 0;
        lh[j].head = nxt[i]; nxt[i] = -1;
        return i;
}

void ListSet::addFirst(index i, alist j) {
        if (i == 0) return;
        if (lh[j].head == 0) lh[j].tail = i;
        nxt[i] = lh[j].head;
        lh[j].head = i;
}

string& ListSet::list2string(alist j, string& s) const {
        int i;
        s = "";
        s += j + ": ";
        for (i = first(j); i != 0; i = next(i)) {
                string s1;
                s += item2string(i,s1) + " ";
        }
        s += "\n";
        return s;
}

string& ListSet::toString(string& s) const {
        alist j;
        s = "";
        for (j = 1; j <= nlst; j++) {
                string s1;
                if (lh[j].head != 0) s += list2string(j,s1);
        }
        return s;
}

} // ends namespace