linkedlist.cpp

Go to the documentation of this file.

#include <linkedlist.h>

#include <QtGlobal>
#include <data/linkedlist.h>

using namespace frechet;
using namespace data;

BLinkedListElement::BLinkedListElement() : link{nullptr,nullptr} { }

#ifdef LINKED_LIST_VDESTRUCTOR
BLinkedListElement::~BLinkedListElement() { }
#endif

BLinkedList::BLinkedList(bool circular)
    : _first(0), _last(0),
      _size(0), _circular(circular) {}

BLinkedList::BLinkedList(BLinkedList&& that)
    : _first(that._first),
      _last(that._last),
      _size(that._size),
      _circular(that._circular)
{
    that.clear();
}

BLinkedList::~BLinkedList() { dispose(); }

bool BLinkedList::empty() const {
    Q_ASSERT((_first==0) == (_last==0));
    Q_ASSERT((_first==0) == (_size==0));
    return _first==0;
}

int BLinkedList::size() const { return _size; }

void BLinkedList::insert_first(BLinkedListElement *el)
{
    Q_ASSERT(el);

    el->prev() = nullptr;
    el->next() = _first;
    if (_first) _first->prev() = el;
    _first = el;
    if (!_last) _last = _first;
    setCircular(_circular);
    ++_size;
}

void BLinkedList::insert_last(BLinkedListElement *el)
{
    Q_ASSERT(el);

    el->prev() = _last;
    el->next() = nullptr;
    if (_last) _last->next() = el;
    _last = el;
    if (!_first) _first = _last;
    setCircular(_circular);
    ++_size;
}

void BLinkedList::insert_before(BLinkedListElement *el, BLinkedListElement *before)
{
    Q_ASSERT(el);
    Q_ASSERT(before);

    el->next() = before;
    el->prev() = before->prev();
    if (before->prev())
        before->prev()->next() = el;
    before->prev() = el;
    if (before==_first) {
        _first = el;
        setCircular(_circular);
    }
    ++_size;
}

void BLinkedList::insert_after(BLinkedListElement *el, BLinkedListElement *after)
{
    Q_ASSERT(el);
    Q_ASSERT(after);

    el->prev() = after;
    el->next() = after->next();
    if (after->next())
        after->next()->prev() = el;
    after->next() = el;
    if (after==_last) {
        _last = el;
        setCircular(_circular);
    }
    ++_size;
}

void BLinkedList::setCircular(bool circ)
{
    if (_first) {
        Q_ASSERT(_last);
        if (circ) {
            _first->prev()=_last;
            _last->next()=_first;
        }
        else {
            _first->prev()=nullptr;
            _last->next()=nullptr;
        }
    }
    _circular = circ;
}

BLinkedListElement* BLinkedList::remove(BLinkedListElement* el)
{
    Q_ASSERT(el);

    BLinkedListElement* result = el->next();
    if (el->next()) el->next()->prev() = el->prev();
    if (el->prev()) el->prev()->next() = el->next();

    if (el==_first) {
        _first = el->next();
        setCircular(_circular);
    }
    if (el==_last) {
        _last = el->prev();
        setCircular(_circular);
    }

    delete el;
    --_size;
    Q_ASSERT(_size >= 0);
    return result;
}

void BLinkedList::clear()
{
    _first = _last = nullptr;
    _size = 0;
    _circular = false;
}

int BLinkedList::concat(BLinkedList &that)
{
    //  Don't mix lists with different allocators !!
    if (empty())
        return swap(that);

    _last->next() = that._first;
    if (that._first) that._first->prev() = _last;

    _last = that._last;
    _size += that._size;

    that._first = that._last = nullptr;
    that._size = 0;
    Q_ASSERT(that.empty());

    setCircular(_circular);
    return _size;
}

int BLinkedList::swap(BLinkedList &that)
{
    std::swap(_first,that._first);
    std::swap(_last,that._last);
    std::swap(_size,that._size);
    std::swap(_circular,that._circular);
    return _size;
}

void BLinkedList::dispose()
{
    if (empty()) return;

    setCircular(false);
    releaseAll();
    clear();
}

BLinkedListElement* BLinkedList::operator[](int i) const
{
    BLinkedListElement* res;
    if (i>=0) {
        res=_first;
        while(res && (i-- > 0)) res = res->next();
    }
    else {
        res=_last;
        while(res && (++i < 0)) res = res->prev();
    }
    return res;
}

BLinkedList& BLinkedList::operator=(BLinkedList &&that) {
    this->dispose();
    this->_first = that._first;
    this->_last = that._last;
    this->_size = that._size;
    this->_circular = that._circular;
    that.clear();
    return *this;
}

void BLinkedList::releaseAll()
{
    BLinkedListElement *obj=_first;
    BLinkedListElement *next;
    while(obj) {
        next = obj->next();
        delete obj;
        obj = next;
    }
}