SList.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/Array.h>
#include <ogdf/basic/basic.h>
#include <ogdf/basic/internal/config_autogen.h>
#include <ogdf/basic/internal/list_templates.h>
#include <ogdf/basic/memory.h>
 
#include <functional>
#include <initializer_list>
#include <ostream>
#include <random>
#include <type_traits>
#include <utility>
 
namespace ogdf {
 
template<class E, bool isConst>
class SListIteratorBase;
template<class E>
class SListPure;
 
template<class E>
using SListConstIterator = SListIteratorBase<E, true>;
template<class E>
using SListIterator = SListIteratorBase<E, false>;
 
template<class E>
class SListElement {
    friend class SListPure<E>;
    friend class SListIteratorBase<E, true>;
    friend class SListIteratorBase<E, false>;
 
    SListElement<E>* m_next; 
    E m_x; 
#ifdef OGDF_DEBUG
    SListPure<E>* m_list; 
#endif
 
    SListElement(SListPure<E>* list, const E& x, SListElement<E>* next) : m_next(next), m_x(x) {
#ifdef OGDF_DEBUG
        m_list = list;
#endif
    }
 
    SListElement(SListPure<E>* list, const E& x) : SListElement(list, x, nullptr) { }
 
    SListElement() : SListElement(nullptr, E()) { }
 
    template<class... Args>
    SListElement(SListPure<E>* list, SListElement<E>* next, Args&&... args)
        : SListElement(list, E(std::forward<Args>(args)...), next) { }
 
    OGDF_NEW_DELETE
};
 
 
template<class E, bool isConst>
class SListIteratorBase {
    friend class SListIteratorBase<E, !isConst>;
    friend class SListPure<E>;
 
    using ListElem = typename std::conditional<isConst, const SListElement<E>, SListElement<E>>::type;
    using Elem = typename std::conditional<isConst, const E, E>::type;
 
    ListElem* m_pX; 
 
    operator ListElem*() { return m_pX; }
 
public:
    SListIteratorBase(ListElem* pX) : m_pX(pX) { }
 
    SListIteratorBase() : SListIteratorBase(nullptr) { }
 
    template<bool isArgConst, typename std::enable_if<isConst || !isArgConst, int>::type = 0>
    SListIteratorBase(const SListIteratorBase<E, isArgConst>& it) : SListIteratorBase(it.m_pX) { }
 
    // gcc9 complains since it cannot match the templated constructor above (-Werror=deprecated-copy).
    SListIteratorBase(const SListIterator<E>& it) : SListIteratorBase(it.m_pX) { }
 
    bool valid() const { return m_pX != nullptr; }
 
#ifdef OGDF_DEBUG
    SListPure<E>* listOf() {
        OGDF_ASSERT(valid());
        return m_pX->m_list;
    }
#endif
 
    bool operator==(const SListIteratorBase<E, isConst>& it) const { return m_pX == it.m_pX; }
 
    bool operator!=(const SListIteratorBase<E, isConst>& it) const { return m_pX != it.m_pX; }
 
    SListIteratorBase<E, isConst> succ() const { return m_pX->m_next; }
 
    Elem& operator*() const { return m_pX->m_x; }
 
    SListIteratorBase<E, isConst>& operator=(const SListIterator<E>& it) {
        m_pX = it.m_pX;
        return *this;
    }
 
    SListIteratorBase<E, isConst>& operator++() {
        m_pX = m_pX->m_next;
        return *this;
    }
 
    SListIteratorBase<E, isConst> operator++(int) {
        SListIteratorBase<E, isConst> it = *this;
        m_pX = m_pX->m_next;
        return it;
    }
 
    OGDF_NEW_DELETE
};
 
 
template<class E>
class SListPure {
    SListElement<E>* m_head; 
    SListElement<E>* m_tail; 
 
public:
    using value_type = E;
    using reference = E&;
    using const_reference = const E&;
    using const_iterator = SListConstIterator<E>;
    using iterator = SListIterator<E>;
 
    SListPure() : m_head(nullptr), m_tail(nullptr) { }
 
    SListPure(std::initializer_list<E> init) : m_head(nullptr), m_tail(nullptr) {
        for (const E& x : init) {
            pushBack(x);
        }
    }
 
    SListPure(const SListPure<E>& L) : m_head(nullptr), m_tail(nullptr) { copy(L); }
 
 
    SListPure(SListPure<E>&& L) noexcept : m_head(L.m_head), m_tail(L.m_tail) {
        L.m_head = L.m_tail = nullptr;
    }
 
    virtual ~SListPure() { clear(); }
 
 
    bool empty() const { return m_head == nullptr; }
 
 
    virtual int size() const {
        int count = 0;
        for (SListElement<E>* pX = m_head; pX != nullptr; pX = pX->m_next) {
            ++count;
        }
        return count;
    }
 
 
    const_reference front() const {
        OGDF_ASSERT(m_head != nullptr);
        return m_head->m_x;
    }
 
 
    reference front() {
        OGDF_ASSERT(m_head != nullptr);
        return m_head->m_x;
    }
 
 
    const_reference back() const {
        OGDF_ASSERT(m_tail != nullptr);
        return m_tail->m_x;
    }
 
 
    reference back() {
        OGDF_ASSERT(m_tail != nullptr);
        return m_tail->m_x;
    }
 
 
    const_iterator get(int pos) const {
        SListElement<E>* pX;
        for (pX = m_head; pX != nullptr; pX = pX->m_next) {
            if (pos-- == 0) {
                break;
            }
        }
        return pX;
    }
 
 
    iterator get(int pos) {
        SListElement<E>* pX;
        for (pX = m_head; pX != nullptr; pX = pX->m_next) {
            if (pos-- == 0) {
                break;
            }
        }
        return pX;
    }
 
 
    int pos(const_iterator it) const {
        OGDF_ASSERT(it.listOf() == this);
        int p = 0;
        for (SListElement<E>* pX = m_head; pX != nullptr; pX = pX->m_next, ++p) {
            if (pX == it) {
                break;
            }
        }
        return p;
    }
 
 
 
 
    iterator begin() { return m_head; }
 
 
    const_iterator begin() const { return m_head; }
 
 
    const_iterator cbegin() const { return m_head; }
 
 
    iterator end() { return SListIterator<E>(); }
 
 
    const_iterator end() const { return SListConstIterator<E>(); }
 
 
    const_iterator cend() const { return SListConstIterator<E>(); }
 
 
    iterator backIterator() { return m_tail; }
 
 
    const_iterator backIterator() const { return m_tail; }
 
 
    const_iterator cyclicSucc(const_iterator it) const {
        OGDF_ASSERT(it.listOf() == this);
        const SListElement<E>* pX = it;
        return (pX->m_next) ? pX->m_next : m_head;
    }
 
 
    iterator cyclicSucc(iterator it) {
        OGDF_ASSERT(it.listOf() == this);
        SListElement<E>* pX = it;
        return (pX->m_next) ? pX->m_next : m_head;
    }
 
 
 
    SListPure<E>& operator=(const SListPure<E>& L) {
        clear();
        copy(L);
        return *this;
    }
 
 
    SListPure<E>& operator=(SListPure<E>&& L) {
        clear();
        m_head = L.m_head;
        m_tail = L.m_tail;
        L.m_head = L.m_tail = nullptr;
        reassignListRefs();
        return *this;
    }
 
    bool operator==(const SListPure<E>& L) const {
        SListElement<E>*pX = m_head, *pY = L.m_head;
        while (pX != nullptr && pY != nullptr) {
            if (pX->m_x != pY->m_x) {
                return false;
            }
            pX = pX->m_next;
            pY = pY->m_next;
        }
        return pX == nullptr && pY == nullptr;
    }
 
    bool operator!=(const SListPure<E>& L) const { return !operator==(L); }
 
 
 
    iterator pushFront(const E& x) {
        m_head = new SListElement<E>(this, x, m_head);
        if (m_tail == nullptr) {
            m_tail = m_head;
        }
        return m_head;
    }
 
 
    template<class... Args>
    iterator emplaceFront(Args&&... args) {
        m_head = new SListElement<E>(this, m_head, std::forward<Args>(args)...);
        if (m_tail == nullptr) {
            m_tail = m_head;
        }
        return m_head;
    }
 
    iterator pushBack(const E& x) {
        SListElement<E>* pNew = new SListElement<E>(this, x);
        if (m_head == nullptr) {
            m_head = m_tail = pNew;
        } else {
            m_tail = m_tail->m_next = pNew;
        }
        return m_tail;
    }
 
 
    template<class... Args>
    iterator emplaceBack(Args&&... args) {
        SListElement<E>* pNew = new SListElement<E>(this, nullptr, std::forward<Args>(args)...);
        if (m_head == nullptr) {
            m_head = m_tail = pNew;
        } else {
            m_tail = m_tail->m_next = pNew;
        }
        return m_tail;
    }
 
 
    iterator insertAfter(const E& x, iterator itBefore) {
        OGDF_ASSERT(itBefore.listOf() == this);
        SListElement<E>* pBefore = itBefore;
        SListElement<E>* pNew = new SListElement<E>(this, x, pBefore->m_next);
        if (pBefore == m_tail) {
            m_tail = pNew;
        }
        return (pBefore->m_next = pNew);
    }
 
 
 
 
    void popFront() {
        OGDF_ASSERT(m_head != nullptr);
        SListElement<E>* pX = m_head;
        if ((m_head = m_head->m_next) == nullptr) {
            m_tail = nullptr;
        }
        delete pX;
    }
 
 
    E popFrontRet() {
        E el = front();
        popFront();
        return el;
    }
 
 
    void delSucc(iterator itBefore) {
        OGDF_ASSERT(itBefore.listOf() == this);
        SListElement<E>* pBefore = itBefore;
        OGDF_ASSERT(pBefore != nullptr);
        SListElement<E>* pDel = pBefore->m_next;
        OGDF_ASSERT(pDel != nullptr);
        if ((pBefore->m_next = pDel->m_next) == nullptr) {
            m_tail = pBefore;
        }
        delete pDel;
    }
 
    void clear() {
        if (m_head == nullptr) {
            return;
        }
 
        if (!std::is_trivially_destructible<E>::value) {
            for (SListElement<E>* pX = m_head; pX != nullptr; pX = pX->m_next) {
                pX->m_x.~E();
            }
        }
        OGDF_ALLOCATOR::deallocateList(sizeof(SListElement<E>), m_head, m_tail);
 
        m_head = m_tail = nullptr;
    }
 
 
 
    void moveFrontToFront(SListPure<E>& L2) {
        OGDF_ASSERT(m_head != nullptr);
        OGDF_ASSERT(this != &L2);
 
        SListElement<E>* pX = m_head;
        if ((m_head = m_head->m_next) == nullptr) {
            m_tail = nullptr;
        }
        pX->m_next = L2.m_head;
        L2.m_head = pX;
        if (L2.m_tail == nullptr) {
            L2.m_tail = L2.m_head;
        }
 
        L2.m_head->m_list = &L2;
    }
 
    void moveFrontToBack(SListPure<E>& L2) {
        OGDF_ASSERT(m_head != nullptr);
        OGDF_ASSERT(this != &L2);
 
        SListElement<E>* pX = m_head;
        if ((m_head = m_head->m_next) == nullptr) {
            m_tail = nullptr;
        }
        pX->m_next = nullptr;
        if (L2.m_head == nullptr) {
            L2.m_head = L2.m_tail = pX;
        } else {
            L2.m_tail = L2.m_tail->m_next = pX;
        }
 
        L2.m_tail->m_list = &L2;
    }
 
 
    void moveFrontToSucc(SListPure<E>& L2, iterator itBefore) {
        OGDF_ASSERT(m_head != nullptr);
        OGDF_ASSERT(this != &L2);
        OGDF_ASSERT(itBefore.listOf() == &L2);
 
        SListElement<E>* pBefore = itBefore;
        SListElement<E>* pX = m_head;
        if ((m_head = m_head->m_next) == nullptr) {
            m_tail = nullptr;
        }
        pX->m_next = pBefore->m_next;
        pBefore->m_next = pX;
        if (pBefore == L2.m_tail) {
            L2.m_tail = pX;
        }
 
        pX->m_list = &L2;
    }
 
    void conc(SListPure<E>& L2) {
        if (m_head) {
            m_tail->m_next = L2.m_head;
        } else {
            m_head = L2.m_head;
        }
        if (L2.m_tail != nullptr) {
            m_tail = L2.m_tail;
        }
 
        reassignListRefs(L2.m_head);
 
        L2.m_head = L2.m_tail = nullptr;
    }
 
    void reverse() {
        SListElement<E>*p, *pNext, *pPred = nullptr;
        for (p = m_head; p; p = pNext) {
            pNext = p->m_next;
            p->m_next = pPred;
            pPred = p;
        }
        std::swap(m_head, m_tail);
    }
 
 
 
    SListConstIterator<E> search(const E& e) const {
        SListConstIterator<E> i;
        for (i = begin(); i.valid(); ++i) {
            if (*i == e) {
                return i;
            }
        }
        return i;
    }
 
    SListIterator<E> search(const E& e) {
        SListIterator<E> i;
        for (i = begin(); i.valid(); ++i) {
            if (*i == e) {
                return i;
            }
        }
        return i;
    }
 
    template<class COMPARER>
    SListConstIterator<E> search(const E& e, const COMPARER& comp) const {
        SListConstIterator<E> i;
        for (i = begin(); i.valid(); ++i) {
            if (comp.equal(*i, e)) {
                return i;
            }
        }
        return i;
    }
 
    template<class COMPARER>
    SListIterator<E> search(const E& e, const COMPARER& comp) {
        SListIterator<E> i;
        for (i = begin(); i.valid(); ++i) {
            if (comp.equal(*i, e)) {
                return i;
            }
        }
        return i;
    }
 
    void quicksort() { ogdf::quicksortTemplate(*this); }
 
    template<class COMPARER>
    void quicksort(const COMPARER& comp) {
        ogdf::quicksortTemplate(*this, comp);
    }
 
 
    void bucketSort(int l, int h, BucketFunc<E>& f);
 
    void bucketSort(BucketFunc<E>& f);
 
 
 
    const_iterator chooseIterator(
            std::function<bool(const E&)> includeElement = [](const E&) { return true; },
            bool isFastTest = true) const {
        return chooseIteratorFrom(*this, includeElement, isFastTest);
    }
 
    iterator chooseIterator(
            std::function<bool(const E&)> includeElement = [](const E&) { return true; },
            bool isFastTest = true) {
        return chooseIteratorFrom(*this, includeElement, isFastTest);
    }
 
    const_reference chooseElement(
            std::function<bool(const E&)> includeElement = [](const E&) { return true; },
            bool isFastTest = true) const {
        const_iterator result = chooseIterator(includeElement, isFastTest);
        OGDF_ASSERT(result.valid());
        return *result;
    }
 
    reference chooseElement(
            std::function<bool(const E&)> includeElement = [](const E&) { return true; },
            bool isFastTest = true) {
        iterator result = chooseIterator(includeElement, isFastTest);
        OGDF_ASSERT(result.valid());
        return *result;
    }
 
    void permute() {
        std::minstd_rand rng(randomSeed());
        permute(size(), rng);
    }
 
    template<class RNG>
    void permute(RNG& rng) {
        permute(size(), rng);
    }
 
 
protected:
    void copy(const SListPure<E>& L) {
        for (SListElement<E>* pX = L.m_head; pX != nullptr; pX = pX->m_next) {
            pushBack(pX->m_x);
        }
    }
 
    template<class RNG>
    void permute(const int n, RNG& rng);
 
    inline void reassignListRefs(SListElement<E>* start = nullptr) {
#ifdef OGDF_DEBUG
        for (auto e = start == nullptr ? m_head : start; e != nullptr; e = e->m_next) {
            e->m_list = this;
        }
#endif
    }
 
    OGDF_NEW_DELETE
};
 
 
template<class E>
class SList : private SListPure<E> {
    int m_count; 
 
public:
    using typename SListPure<E>::value_type;
    using typename SListPure<E>::reference;
    using typename SListPure<E>::const_reference;
    using typename SListPure<E>::const_iterator;
    using typename SListPure<E>::iterator;
 
    SList() : m_count(0) { }
 
    SList(std::initializer_list<E> init) : SListPure<E>(init), m_count((int)init.size()) { }
 
    SList(const SList<E>& L) : SListPure<E>(L), m_count(L.m_count) { }
 
 
    SList(SList<E>&& L) noexcept : SListPure<E>(std::move(L)), m_count(L.m_count) { L.m_count = 0; }
 
 
 
    int size() const { return m_count; }
 
    const SListPure<E>& getSListPure() const { return *this; }
 
 
 
    SList<E>& operator=(const SList<E>& L) {
        SListPure<E>::operator=(L);
        m_count = L.m_count;
        return *this;
    }
 
 
    SList<E>& operator=(SList<E>&& L) {
        m_count = L.m_count;
        SListPure<E>::operator=(std::move(L));
        L.m_count = 0;
        return *this;
    }
 
    bool operator==(const SList<E>& L) const {
        return (m_count == L.m_count) && SListPure<E>::operator==(L);
    }
 
    bool operator!=(const SList<E>& L) const { return !operator==(L); }
 
 
 
    SListIterator<E> pushFront(const E& x) {
        ++m_count;
        return SListPure<E>::pushFront(x);
    }
 
    template<class... Args>
    iterator emplaceFront(Args&&... args) {
        ++m_count;
        return SListPure<E>::emplaceFront(std::forward<Args>(args)...);
    }
 
    SListIterator<E> pushBack(const E& x) {
        ++m_count;
        return SListPure<E>::pushBack(x);
    }
 
    template<class... Args>
    iterator emplaceBack(Args&&... args) {
        ++m_count;
        return SListPure<E>::emplaceBack(std::forward<Args>(args)...);
    }
 
    SListIterator<E> insertAfter(const E& x, SListIterator<E> itBefore) {
        ++m_count;
        return SListPure<E>::insertAfter(x, itBefore);
    }
 
 
 
    void popFront() {
        --m_count;
        SListPure<E>::popFront();
    }
 
    E popFrontRet() {
        E el = front();
        popFront();
        return el;
    }
 
    void delSucc(SListIterator<E> itBefore) {
        --m_count;
        SListPure<E>::delSucc(itBefore);
    }
 
    void clear() {
        m_count = 0;
        SListPure<E>::clear();
    }
 
 
 
    void moveFrontToFront(SList<E>& L2) {
        SListPure<E>::moveFrontToFront(L2);
        --m_count;
        ++L2.m_count;
    }
 
    void moveFrontToBack(SList<E>& L2) {
        SListPure<E>::moveFrontToBack(L2);
        --m_count;
        ++L2.m_count;
    }
 
    void moveFrontToSucc(SList<E>& L2, SListIterator<E> itBefore) {
        SListPure<E>::moveFrontToSucc(L2, itBefore);
        --m_count;
        ++L2.m_count;
    }
 
    void conc(SList<E>& L2) {
        SListPure<E>::conc(L2);
        m_count += L2.m_count;
        L2.m_count = 0;
    }
 
    using SListPure<E>::empty;
    using SListPure<E>::front;
    using SListPure<E>::back;
    using SListPure<E>::get;
    using SListPure<E>::pos;
    using SListPure<E>::begin;
    using SListPure<E>::cbegin;
    using SListPure<E>::end;
    using SListPure<E>::cend;
    using SListPure<E>::backIterator;
    using SListPure<E>::cyclicSucc;
    using SListPure<E>::reverse;
    using SListPure<E>::search;
    using SListPure<E>::quicksort;
    using SListPure<E>::bucketSort;
    using SListPure<E>::chooseIterator;
    using SListPure<E>::chooseElement;
    using SListPure<E>::permute;
 
    OGDF_NEW_DELETE
};
 
template<class E>
void SListPure<E>::bucketSort(BucketFunc<E>& f) {
    // if less than two elements, nothing to do
    if (m_head == m_tail) {
        return;
    }
 
    int l, h;
    l = h = f.getBucket(m_head->m_x);
 
    SListElement<E>* pX;
    for (pX = m_head->m_next; pX; pX = pX->m_next) {
        int i = f.getBucket(pX->m_x);
        if (i < l) {
            l = i;
        }
        if (i > h) {
            h = i;
        }
    }
 
    bucketSort(l, h, f);
}
 
template<class E>
void SListPure<E>::bucketSort(int l, int h, BucketFunc<E>& f) {
    // if less than two elements, nothing to do
    if (m_head == m_tail) {
        return;
    }
 
    Array<SListElement<E>*> head(l, h, nullptr), tail(l, h);
 
    SListElement<E>* pX;
    for (pX = m_head; pX; pX = pX->m_next) {
        int i = f.getBucket(pX->m_x);
        if (head[i]) {
            tail[i] = (tail[i]->m_next = pX);
        } else {
            head[i] = tail[i] = pX;
        }
    }
 
    SListElement<E>* pY = nullptr;
    for (int i = l; i <= h; i++) {
        pX = head[i];
        if (pX) {
            if (pY) {
                pY->m_next = pX;
            } else {
                m_head = pX;
            }
            pY = tail[i];
        }
    }
 
    m_tail = pY;
    pY->m_next = nullptr;
}
 
template<class E>
template<class RNG>
void SListPure<E>::permute(const int n, RNG& rng) {
    if (n == 0) {
        return;
    }
 
    Array<SListElement<E>*> A(n + 1);
    A[n] = nullptr;
 
    int i = 0;
    SListElement<E>* pX;
    for (pX = m_head; pX; pX = pX->m_next) {
        A[i++] = pX;
    }
 
    A.permute(0, n - 1, rng);
 
    for (i = 0; i < n; i++) {
        A[i]->m_next = A[i + 1];
    }
 
    m_head = A[0];
    m_tail = A[n - 1];
}
 
template<class E>
void print(std::ostream& os, const SListPure<E>& L, char delim = ' ') {
    SListConstIterator<E> pX = L.begin();
    if (pX.valid()) {
        os << *pX;
        for (++pX; pX.valid(); ++pX) {
            os << delim << *pX;
        }
    }
}
 
template<class E>
void print(std::ostream& os, const SList<E>& L, char delim = ' ') {
    print(os, L.getSListPure(), delim);
}
 
template<class E>
std::ostream& operator<<(std::ostream& os, const SListPure<E>& L) {
    print(os, L);
    return os;
}
 
template<class E>
std::ostream& operator<<(std::ostream& os, const SList<E>& L) {
    return operator<<(os, L.getSListPure());
}
 
template<class E>
void bucketSort(Array<E>& a, int min, int max, BucketFunc<E>& f) {
    if (a.low() >= a.high()) {
        return;
    }
 
    Array<SListPure<E>> bucket(min, max);
 
    int i;
    for (i = a.low(); i <= a.high(); ++i) {
        bucket[f.getBucket(a[i])].pushBack(a[i]);
    }
 
    i = a.low();
    for (int j = min; j <= max; ++j) {
        SListConstIterator<E> it = bucket[j].begin();
        for (; it.valid(); ++it) {
            a[i++] = *it;
        }
    }
}
 
}