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

Go to the documentation of this file.

#include "Dlist.h"

namespace grafalgo {

Dlist::Dlist(int n1) : List(n1) {
        assert(n() >= 0); makeSpace(n());
}

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

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

void Dlist::freeSpace() { delete [] prv; }

void Dlist::resize(int size) {
        List::resize(size); freeSpace(); makeSpace(size);
}

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

index Dlist::get(int i) const {
        if (i >= 0) return List::get(i);
        index j;
        for (j = last(); j != 0 && ++i; j = prv[j]) {}
        return j;
}

bool Dlist::insert(index i, index j) {
        if (!List::insert(i,j)) return false;
        // now update prv
        prv[i] = j;
        if (next(i) != 0) prv[next(i)] = i;
        return true;
}

bool Dlist::remove(index i) {
        if (i == 0 || !List::removeNext(prev(i)))
                return false;
        if (prv[i] == 0) prv[first()] = 0;
        else {
                index j = prv[i];
                if (next(j) != 0) prv[next(j)] = j;
        }
        prv[i] = -1;
        return true;
}

} // ends namespace