List.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 <iterator>
#include <ostream>
#include <random>
#include <type_traits>
#include <utility>
 
namespace ogdf {
 
template<class E, bool isConst, bool isReverse>
class ListIteratorBase;
template<class E>
class List;
template<class E>
class ListPure;
 
template<class E>
using ListConstIterator = ListIteratorBase<E, true, false>;
template<class E>
using ListIterator = ListIteratorBase<E, false, false>;
template<class E>
using ListConstReverseIterator = ListIteratorBase<E, true, true>;
template<class E>
using ListReverseIterator = ListIteratorBase<E, false, true>;
 
template<class E>
class ListElement {
    friend class ListPure<E>;
    friend class List<E>;
    friend class ListIteratorBase<E, true, true>;
    friend class ListIteratorBase<E, false, true>;
    friend class ListIteratorBase<E, true, false>;
    friend class ListIteratorBase<E, false, false>;
 
    ListElement<E>* m_next; 
    ListElement<E>* m_prev; 
    E m_x; 
#ifdef OGDF_DEBUG
    ListPure<E>* m_list; 
#endif
 
    ListElement(ListPure<E>* list, const E& x, ListElement<E>* next, ListElement<E>* prev)
        : m_next(next), m_prev(prev), m_x(x) {
#ifdef OGDF_DEBUG
        m_list = list;
#endif
    }
 
    ListElement(ListPure<E>* list, const E& x) : ListElement(list, x, nullptr, nullptr) { }
 
    template<class... Args>
    ListElement(ListPure<E>* list, ListElement<E>* next, ListElement<E>* prev, Args&&... args)
        : ListElement(list, E(std::forward<Args>(args)...), next, prev) { }
 
    OGDF_NEW_DELETE
};
 
 
template<class E, bool isConst, bool isReverse>
class ListIteratorBase {
    friend class ListIteratorBase<E, !isConst, isReverse>;
    friend class ListIteratorBase<E, isConst, !isReverse>;
    friend class ListIteratorBase<E, !isConst, !isReverse>;
    friend class ListPure<E>;
    using ListElem = typename std::conditional<isConst, const ListElement<E>, ListElement<E>>::type;
    using Elem = typename std::conditional<isConst, const E, E>::type;
 
    ListElem* m_pX;
 
public:
    using difference_type = std::ptrdiff_t;
    using value_type = Elem;
    using iterator_category = std::bidirectional_iterator_tag;
    using pointer = value_type*;
    using reference = value_type&;
 
    operator ListElem*() { return m_pX; }
 
    ListIteratorBase(ListElem* pX) : m_pX(pX) { }
 
    ListIteratorBase() : ListIteratorBase(nullptr) { }
 
    template<bool isArgConst, typename std::enable_if<isConst || !isArgConst, int>::type = 0, bool isArgReverse>
    ListIteratorBase(const ListIteratorBase<E, isArgConst, isArgReverse>& it)
        : ListIteratorBase(it.m_pX) { }
 
    // gcc9 complains since it cannot match the templated constructor above (-Werror=deprecated-copy).
    ListIteratorBase(const ListIteratorBase<E, isConst, isReverse>& it)
        : ListIteratorBase(it.m_pX) { }
 
    bool valid() const { return m_pX != nullptr; }
 
#ifdef OGDF_DEBUG
    ListPure<E>* listOf() {
        OGDF_ASSERT(valid());
        return m_pX->m_list;
    }
#endif
    bool operator==(const ListIteratorBase<E, isConst, isReverse>& it) const {
        return m_pX == it.m_pX;
    }
 
    bool operator!=(const ListIteratorBase<E, isConst, isReverse>& it) const {
        return m_pX != it.m_pX;
    }
 
    ListIteratorBase<E, isConst, isReverse> succ() const {
        return isReverse ? m_pX->m_prev : m_pX->m_next;
    }
 
    ListIteratorBase<E, isConst, isReverse> pred() const {
        return isReverse ? m_pX->m_next : m_pX->m_prev;
    }
 
    Elem& operator*() const { return m_pX->m_x; }
 
    ListIteratorBase<E, isConst, isReverse>& operator=(
            const ListIteratorBase<E, isConst, isReverse>& it) {
        m_pX = it.m_pX;
        return *this;
    }
 
    ListIteratorBase<E, isConst, isReverse>& operator++() {
        m_pX = isReverse ? m_pX->m_prev : m_pX->m_next;
        return *this;
    }
 
    ListIteratorBase<E, isConst, isReverse> operator++(int) {
        ListIteratorBase<E, isConst, isReverse> it = *this;
        m_pX = isReverse ? m_pX->m_prev : m_pX->m_next;
        return it;
    }
 
    ListIteratorBase<E, isConst, isReverse>& operator--() {
        m_pX = isReverse ? m_pX->m_next : m_pX->m_prev;
        return *this;
    }
 
    ListIteratorBase<E, isConst, isReverse> operator--(int) {
        ListIteratorBase<E, isConst, isReverse> it = *this;
        m_pX = isReverse ? m_pX->m_next : m_pX->m_prev;
        return it;
    }
 
    OGDF_NEW_DELETE
};
 
 
template<class E>
class ListPure {
protected:
    ListElement<E>* m_head; 
    ListElement<E>* m_tail; 
 
public:
    using value_type = E;
    using reference = E&;
    using const_reference = const E&;
    using const_iterator = ListConstIterator<E>;
    using iterator = ListIterator<E>;
    using const_reverse_iterator = ListConstReverseIterator<E>;
    using reverse_iterator = ListReverseIterator<E>;
 
    ListPure() : m_head(nullptr), m_tail(nullptr) { }
 
    ListPure(std::initializer_list<E> init) : m_head(nullptr), m_tail(nullptr) {
        for (const E& x : init) {
            pushBack(x);
        }
    }
 
    ListPure(const ListPure<E>& L) : m_head(nullptr), m_tail(nullptr) { copy(L); }
 
 
    ListPure(ListPure<E>&& L) noexcept : m_head(L.m_head), m_tail(L.m_tail) {
        L.m_head = L.m_tail = nullptr;
        reassignListRefs();
    }
 
    virtual ~ListPure() { clear(); }
 
 
    bool empty() const { return m_head == nullptr; }
 
 
    virtual int size() const {
        int count = 0;
        for (ListElement<E>* pX = m_head; pX; 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 {
        ListElement<E>* pX;
        for (pX = m_head; pX != nullptr; pX = pX->m_next) {
            if (pos-- == 0) {
                break;
            }
        }
        return pX;
    }
 
 
    iterator get(int pos) {
        ListElement<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 (ListElement<E>* pX = m_head; pX != nullptr; pX = pX->m_next, ++p) {
            if (pX == (const ListElement<E>*)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 iterator(); }
 
 
    const_iterator end() const { return const_iterator(); }
 
 
    const_iterator cend() const { return const_iterator(); }
 
 
    reverse_iterator rbegin() { return m_tail; }
 
 
    const_reverse_iterator rbegin() const { return m_tail; }
 
 
    const_reverse_iterator crbegin() const { return m_tail; }
 
 
    reverse_iterator rend() { return reverse_iterator(); }
 
 
    const_reverse_iterator rend() const { return const_reverse_iterator(); }
 
 
    const_reverse_iterator crend() const { return const_reverse_iterator(); }
 
 
    const_iterator cyclicSucc(const_iterator it) const {
        OGDF_ASSERT(!it.valid() || it.listOf() == this);
        const ListElement<E>* pX = it;
        return (pX && pX->m_next) ? pX->m_next : m_head;
    }
 
 
    iterator cyclicSucc(iterator it) {
        OGDF_ASSERT(!it.valid() || it.listOf() == this);
        ListElement<E>* pX = it;
        return (pX && pX->m_next) ? pX->m_next : m_head;
    }
 
    const_reverse_iterator cyclicSucc(const_reverse_iterator it) const {
        OGDF_ASSERT(!it.valid() || it.listOf() == this);
        const ListElement<E>* pX = it;
        return (pX && pX->m_prev) ? pX->m_prev : m_tail;
    }
 
    reverse_iterator cyclicSucc(reverse_iterator it) {
        OGDF_ASSERT(!it.valid() || it.listOf() == this);
        ListElement<E>* pX = it;
        return (pX && pX->m_prev) ? pX->m_prev : m_tail;
    }
 
 
    const_iterator cyclicPred(const_iterator it) const {
        OGDF_ASSERT(!it.valid() || it.listOf() == this);
        const ListElement<E>* pX = it;
        return (pX && pX->m_prev) ? pX->m_prev : m_tail;
    }
 
 
    iterator cyclicPred(iterator it) {
        OGDF_ASSERT(!it.valid() || it.listOf() == this);
        ListElement<E>* pX = it;
        return (pX && pX->m_prev) ? pX->m_prev : m_tail;
    }
 
    const_reverse_iterator cyclicPred(const_reverse_iterator it) const {
        OGDF_ASSERT(!it.valid() || it.listOf() == this);
        const ListElement<E>* pX = it;
        return (pX && pX->m_next) ? pX->m_next : m_head;
    }
 
    reverse_iterator cyclicPred(reverse_iterator it) {
        OGDF_ASSERT(!it.valid() || it.listOf() == this);
        ListElement<E>* pX = it;
        return (pX && pX->m_next) ? pX->m_next : m_head;
    }
 
 
 
    ListPure<E>& operator=(const ListPure<E>& L) {
        clear();
        copy(L);
        return *this;
    }
 
 
    ListPure<E>& operator=(ListPure<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 ListPure<E>& L) const {
        ListElement<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 ListPure<E>& L) const { return !operator==(L); }
 
 
 
    iterator pushFront(const E& x) {
        ListElement<E>* pX = new ListElement<E>(this, x, m_head, nullptr);
        if (m_head) {
            m_head = m_head->m_prev = pX;
        } else {
            m_head = m_tail = pX;
        }
        return m_head;
    }
 
 
    template<class... Args>
    iterator emplaceFront(Args&&... args) {
        ListElement<E>* pX = new ListElement<E>(this, m_head, nullptr, std::forward<Args>(args)...);
        if (m_head) {
            m_head = m_head->m_prev = pX;
        } else {
            m_head = m_tail = pX;
        }
        return m_head;
    }
 
    iterator pushBack(const E& x) {
        ListElement<E>* pX = new ListElement<E>(this, x, nullptr, m_tail);
        if (m_head) {
            m_tail = m_tail->m_next = pX;
        } else {
            m_tail = m_head = pX;
        }
        return m_tail;
    }
 
 
    template<class... Args>
    iterator emplaceBack(Args&&... args) {
        ListElement<E>* pX = new ListElement<E>(this, nullptr, m_tail, std::forward<Args>(args)...);
        if (m_head) {
            m_tail = m_tail->m_next = pX;
        } else {
            m_tail = m_head = pX;
        }
        return m_tail;
    }
 
 
    iterator insert(const E& x, iterator it, Direction dir = Direction::after) {
        OGDF_ASSERT(it.listOf() == this);
        ListElement<E>*pY = it, *pX;
        if (dir == Direction::after) {
            ListElement<E>* pYnext = pY->m_next;
            pY->m_next = pX = new ListElement<E>(this, x, pYnext, pY);
            if (pYnext) {
                pYnext->m_prev = pX;
            } else {
                m_tail = pX;
            }
        } else {
            ListElement<E>* pYprev = pY->m_prev;
            pY->m_prev = pX = new ListElement<E>(this, x, pY, pYprev);
            if (pYprev) {
                pYprev->m_next = pX;
            } else {
                m_head = pX;
            }
        }
        return pX;
    }
 
 
    iterator insertBefore(const E& x, iterator it) {
        OGDF_ASSERT(it.listOf() == this);
        ListElement<E>*pY = it, *pX;
        ListElement<E>* pYprev = pY->m_prev;
        pY->m_prev = pX = new ListElement<E>(this, x, pY, pYprev);
        if (pYprev) {
            pYprev->m_next = pX;
        } else {
            m_head = pX;
        }
        return pX;
    }
 
 
    iterator insertAfter(const E& x, iterator it) {
        OGDF_ASSERT(it.listOf() == this);
        ListElement<E>*pY = it, *pX;
        ListElement<E>* pYnext = pY->m_next;
        pY->m_next = pX = new ListElement<E>(this, x, pYnext, pY);
        if (pYnext) {
            pYnext->m_prev = pX;
        } else {
            m_tail = pX;
        }
        return pX;
    }
 
 
 
 
    void popFront() {
        OGDF_ASSERT(m_head != nullptr);
        ListElement<E>* pX = m_head;
        m_head = m_head->m_next;
        delete pX;
        if (m_head) {
            m_head->m_prev = nullptr;
        } else {
            m_tail = nullptr;
        }
    }
 
 
    E popFrontRet() {
        E el = front();
        popFront();
        return el;
    }
 
 
    void popBack() {
        OGDF_ASSERT(m_tail != nullptr);
        ListElement<E>* pX = m_tail;
        m_tail = m_tail->m_prev;
        delete pX;
        if (m_tail) {
            m_tail->m_next = nullptr;
        } else {
            m_head = nullptr;
        }
    }
 
 
    E popBackRet() {
        E el = back();
        popBack();
        return el;
    }
 
 
    void del(iterator it) {
        OGDF_ASSERT(it.listOf() == this);
        ListElement<E>*pX = it, *pPrev = pX->m_prev, *pNext = pX->m_next;
        delete pX;
        if (pPrev) {
            pPrev->m_next = pNext;
        } else {
            m_head = pNext;
        }
        if (pNext) {
            pNext->m_prev = pPrev;
        } else {
            m_tail = pPrev;
        }
    }
 
 
    bool removeFirst(const E& x) {
        for (ListElement<E>* pX = m_head; pX != nullptr; pX = pX->m_next) {
            if (pX->m_x == x) {
                del(pX);
                return true;
            }
        }
        return false;
    }
 
    void clear() {
        if (m_head == nullptr) {
            return;
        }
 
        if (!std::is_trivially_destructible<E>::value) {
            for (ListElement<E>* pX = m_head; pX != nullptr; pX = pX->m_next) {
                pX->m_x.~E();
            }
        }
        OGDF_ALLOCATOR::deallocateList(sizeof(ListElement<E>), m_head, m_tail);
 
        m_head = m_tail = nullptr;
    }
 
 
 
 
    void exchange(iterator it1, iterator it2) {
        OGDF_ASSERT(it1.valid());
        OGDF_ASSERT(it2.valid());
        OGDF_ASSERT(it1 != it2);
        ListElement<E>*pX = it1, *pY = it2;
 
        std::swap(pX->m_next, pY->m_next);
        std::swap(pX->m_prev, pY->m_prev);
#ifdef OGDF_DEBUG
        std::swap(pX->m_list, pY->m_list);
#endif
 
        if (pX->m_next == pX) {
            pX->m_next = pY;
            pY->m_prev = pX;
        }
        if (pX->m_prev == pX) {
            pX->m_prev = pY;
            pY->m_next = pX;
        }
 
        if (pX->m_prev) {
            pX->m_prev->m_next = pX;
        } else {
            m_head = pX;
        }
 
        if (pY->m_prev) {
            pY->m_prev->m_next = pY;
        } else {
            m_head = pY;
        }
 
        if (pX->m_next) {
            pX->m_next->m_prev = pX;
        } else {
            m_tail = pX;
        }
 
        if (pY->m_next) {
            pY->m_next->m_prev = pY;
        } else {
            m_tail = pY;
        }
    }
 
 
    void moveToFront(iterator it) {
        OGDF_ASSERT(it.listOf() == this);
        // remove it
        ListElement<E>*pX = it, *pPrev = pX->m_prev, *pNext = pX->m_next;
        //already at front
        if (!pPrev) {
            return;
        }
 
        //update old position
        if (pPrev) {
            pPrev->m_next = pNext;
        }
        if (pNext) {
            pNext->m_prev = pPrev;
        } else {
            m_tail = pPrev;
        }
        // insert it at front
        pX->m_prev = nullptr;
        pX->m_next = m_head;
        m_head = m_head->m_prev = pX;
    }
 
 
    void moveToBack(iterator it) {
        OGDF_ASSERT(it.listOf() == this);
        // remove it
        ListElement<E>*pX = it, *pPrev = pX->m_prev, *pNext = pX->m_next;
        //already at back
        if (!pNext) {
            return;
        }
 
        //update old position
        if (pPrev) {
            pPrev->m_next = pNext;
        } else {
            m_head = pNext;
        }
        if (pNext) {
            pNext->m_prev = pPrev;
        }
        // insert it at back
        pX->m_prev = m_tail;
        pX->m_next = nullptr;
        m_tail = m_tail->m_next = pX;
    }
 
 
    void moveToSucc(iterator it, iterator itBefore) {
        OGDF_ASSERT(it.listOf() == this);
        OGDF_ASSERT(itBefore.listOf() == this);
        // move it
        ListElement<E>*pX = it, *pPrev = pX->m_prev, *pNext = pX->m_next;
        //the same of already in place
        ListElement<E>* pY = itBefore;
        if (pX == pY || pPrev == pY) {
            return;
        }
 
        // update old position
        if (pPrev) {
            pPrev->m_next = pNext;
        } else {
            m_head = pNext;
        }
        if (pNext) {
            pNext->m_prev = pPrev;
        } else {
            m_tail = pPrev;
        }
        // move it after itBefore
        ListElement<E>* pYnext = pX->m_next = pY->m_next;
        (pX->m_prev = pY)->m_next = pX;
        if (pYnext) {
            pYnext->m_prev = pX;
        } else {
            m_tail = pX;
        }
    }
 
 
    void moveToPrec(iterator it, iterator itAfter) {
        OGDF_ASSERT(it.listOf() == this);
        OGDF_ASSERT(itAfter.listOf() == this);
        // move it
        ListElement<E>*pX = it, *pPrev = pX->m_prev, *pNext = pX->m_next;
        //the same of already in place
        ListElement<E>* pY = itAfter;
        if (pX == pY || pNext == pY) {
            return;
        }
 
        // update old position
        if (pPrev) {
            pPrev->m_next = pNext;
        } else {
            m_head = pNext;
        }
        if (pNext) {
            pNext->m_prev = pPrev;
        } else {
            m_tail = pPrev;
        }
        // move it before itAfter
        ListElement<E>* pYprev = pX->m_prev = pY->m_prev;
        (pX->m_next = pY)->m_prev = pX;
        if (pYprev) {
            pYprev->m_next = pX;
        } else {
            m_head = pX;
        }
    }
 
 
    void moveToFront(iterator it, ListPure<E>& L2) {
        OGDF_ASSERT(it.listOf() == this);
        OGDF_ASSERT(this != &L2);
        // remove it
        ListElement<E>*pX = it, *pPrev = pX->m_prev, *pNext = pX->m_next;
        if (pPrev) {
            pPrev->m_next = pNext;
        } else {
            m_head = pNext;
        }
        if (pNext) {
            pNext->m_prev = pPrev;
        } else {
            m_tail = pPrev;
        }
        // insert it at front of L2
        pX->m_prev = nullptr;
        if ((pX->m_next = L2.m_head) != nullptr) {
            L2.m_head = L2.m_head->m_prev = pX;
        } else {
            L2.m_head = L2.m_tail = pX;
        }
 
#ifdef OGDF_DEBUG
        pX->m_list = &L2;
#endif
    }
 
 
    void moveToBack(iterator it, ListPure<E>& L2) {
        OGDF_ASSERT(it.listOf() == this);
        OGDF_ASSERT(this != &L2);
        // remove it
        ListElement<E>*pX = it, *pPrev = pX->m_prev, *pNext = pX->m_next;
        if (pPrev) {
            pPrev->m_next = pNext;
        } else {
            m_head = pNext;
        }
        if (pNext) {
            pNext->m_prev = pPrev;
        } else {
            m_tail = pPrev;
        }
        // insert it at back of L2
        pX->m_next = nullptr;
        if ((pX->m_prev = L2.m_tail) != nullptr) {
            L2.m_tail = L2.m_tail->m_next = pX;
        } else {
            L2.m_head = L2.m_tail = pX;
        }
 
#ifdef OGDF_DEBUG
        pX->m_list = this;
#endif
    }
 
 
    void moveToSucc(iterator it, ListPure<E>& L2, iterator itBefore) {
        OGDF_ASSERT(it.listOf() == this);
        OGDF_ASSERT(itBefore.listOf() == &L2);
        OGDF_ASSERT(this != &L2);
        // remove it
        ListElement<E>*pX = it, *pPrev = pX->m_prev, *pNext = pX->m_next;
        if (pPrev) {
            pPrev->m_next = pNext;
        } else {
            m_head = pNext;
        }
        if (pNext) {
            pNext->m_prev = pPrev;
        } else {
            m_tail = pPrev;
        }
        // insert it in list L2 after itBefore
        ListElement<E>* pY = itBefore;
        ListElement<E>* pYnext = pX->m_next = pY->m_next;
        (pX->m_prev = pY)->m_next = pX;
        if (pYnext) {
            pYnext->m_prev = pX;
        } else {
            L2.m_tail = pX;
        }
 
#ifdef OGDF_DEBUG
        pX->m_list = &L2;
#endif
    }
 
 
    void moveToPrec(iterator it, ListPure<E>& L2, iterator itAfter) {
        OGDF_ASSERT(it.listOf() == this);
        OGDF_ASSERT(itAfter.listOf() == &L2);
        OGDF_ASSERT(this != &L2);
        // remove it
        ListElement<E>*pX = it, *pPrev = pX->m_prev, *pNext = pX->m_next;
        if (pPrev) {
            pPrev->m_next = pNext;
        } else {
            m_head = pNext;
        }
        if (pNext) {
            pNext->m_prev = pPrev;
        } else {
            m_tail = pPrev;
        }
        // insert it in list L2 after itBefore
        ListElement<E>* pY = itAfter;
        ListElement<E>* pYprev = pX->m_prev = pY->m_prev;
        (pX->m_next = pY)->m_prev = pX;
        if (pYprev) {
            pYprev->m_next = pX;
        } else {
            L2.m_head = pX;
        }
 
#ifdef OGDF_DEBUG
        pX->m_list = &L2;
#endif
    }
 
    void conc(ListPure<E>& L2) {
        OGDF_ASSERT(this != &L2);
        if (m_head) {
            m_tail->m_next = L2.m_head;
        } else {
            m_head = L2.m_head;
        }
        if (L2.m_head) {
            L2.m_head->m_prev = m_tail;
            m_tail = L2.m_tail;
        }
 
        reassignListRefs(L2.m_head);
 
        L2.m_head = L2.m_tail = nullptr;
    }
 
    void concFront(ListPure<E>& L2) {
        OGDF_ASSERT(this != &L2);
        if (m_head) {
            m_head->m_prev = L2.m_tail;
        } else {
            m_tail = L2.m_tail;
        }
        if (L2.m_head) {
            L2.m_tail->m_next = m_head;
            m_head = L2.m_head;
        }
 
        reassignListRefs(L2.m_head);
 
        L2.m_head = L2.m_tail = nullptr;
    }
 
    void swap(ListPure<E>& other) {
        std::swap(m_head, other.m_head);
        std::swap(m_tail, other.m_tail);
 
        reassignListRefs();
        other.reassignListRefs();
    }
 
 
    void split(iterator it, ListPure<E>& L1, ListPure<E>& L2, Direction dir = Direction::before) {
        OGDF_ASSERT(!it.valid() || it.listOf() == this);
        if (&L1 != this) {
            L1.clear();
        }
        if (&L2 != this) {
            L2.clear();
        }
 
        if (it.valid()) {
            L1.m_head = m_head;
            L2.m_tail = m_tail;
            if (dir == Direction::before) {
                L2.m_head = it;
                L1.m_tail = L2.m_head->m_prev;
            } else {
                L1.m_tail = it;
                L2.m_head = L1.m_tail->m_next;
            }
            L2.m_head->m_prev = L1.m_tail->m_next = nullptr;
 
        } else {
            L1.m_head = L1.m_tail = nullptr;
            L2.m_head = m_head;
            L2.m_tail = m_tail;
        }
 
        if (this != &L1 && this != &L2) {
            m_head = m_tail = nullptr;
        }
 
        L1.reassignListRefs();
        L2.reassignListRefs();
    }
 
    void splitAfter(iterator it, ListPure<E>& L2) {
        OGDF_ASSERT(it.listOf() == this);
        OGDF_ASSERT(this != &L2);
        L2.clear();
        ListElement<E>* pX = it;
        if (pX != m_tail) {
            (L2.m_head = pX->m_next)->m_prev = nullptr;
            pX->m_next = nullptr;
            L2.m_tail = m_tail;
            m_tail = pX;
        }
 
        L2.reassignListRefs();
    }
 
    void splitBefore(iterator it, ListPure<E>& L2) {
        OGDF_ASSERT(it.listOf() == this);
        OGDF_ASSERT(this != &L2);
        L2.clear();
        ListElement<E>* pX = it;
        L2.m_head = pX;
        L2.m_tail = m_tail;
        if ((m_tail = pX->m_prev) == nullptr) {
            m_head = nullptr;
        } else {
            m_tail->m_next = nullptr;
        }
        pX->m_prev = nullptr;
 
        L2.reassignListRefs();
    }
 
    void reverse() {
        ListElement<E>* pX = m_head;
        m_head = m_tail;
        m_tail = pX;
        while (pX) {
            ListElement<E>* pY = pX->m_next;
            pX->m_next = pX->m_prev;
            pX = pX->m_prev = pY;
        }
    }
 
 
 
    ListConstIterator<E> search(const E& e) const {
        ListConstIterator<E> i;
        for (i = begin(); i.valid(); ++i) {
            if (*i == e) {
                return i;
            }
        }
        return i;
    }
 
    ListIterator<E> search(const E& e) {
        ListIterator<E> i;
        for (i = begin(); i.valid(); ++i) {
            if (*i == e) {
                return i;
            }
        }
        return i;
    }
 
    template<class COMPARER>
    ListConstIterator<E> search(const E& e, const COMPARER& comp) const {
        ListConstIterator<E> i;
        for (i = begin(); i.valid(); ++i) {
            if (comp.equal(*i, e)) {
                return i;
            }
        }
        return i;
    }
 
    template<class COMPARER>
    ListIterator<E> search(const E& e, const COMPARER& comp) {
        ListIterator<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);
 
 
 
    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 ListPure<E>& L) {
        for (ListElement<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(ListElement<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 List : private ListPure<E> {
    int m_count; 
 
public:
    using typename ListPure<E>::value_type;
    using typename ListPure<E>::reference;
    using typename ListPure<E>::const_reference;
    using typename ListPure<E>::const_iterator;
    using typename ListPure<E>::iterator;
    using typename ListPure<E>::const_reverse_iterator;
    using typename ListPure<E>::reverse_iterator;
 
    List() : m_count(0) { }
 
    List(std::initializer_list<E> init) : ListPure<E>(init), m_count((int)init.size()) { }
 
    List(const List<E>& L) : ListPure<E>(L), m_count(L.m_count) { }
 
 
    List(List<E>&& L) noexcept : ListPure<E>(std::move(L)), m_count(L.m_count) { L.m_count = 0; }
 
 
 
    int size() const { return m_count; }
 
    const ListPure<E>& getListPure() const { return *this; }
 
 
 
    List<E>& operator=(const List<E>& L) {
        ListPure<E>::operator=(L);
        m_count = L.m_count;
        return *this;
    }
 
 
    List<E>& operator=(List<E>&& L) {
        m_count = L.m_count;
        ListPure<E>::operator=(std::move(L));
        L.m_count = 0;
        return *this;
    }
 
    bool operator==(const List<E>& L) const {
        return (m_count == L.m_count) && ListPure<E>::operator==(L);
    }
 
    bool operator!=(const List<E>& L) const { return !operator==(L); }
 
 
 
    iterator pushFront(const E& x) {
        ++m_count;
        return ListPure<E>::pushFront(x);
    }
 
    template<class... Args>
    iterator emplaceFront(Args&&... args) {
        ++m_count;
        return ListPure<E>::emplaceFront(std::forward<Args>(args)...);
    }
 
    iterator pushBack(const E& x) {
        ++m_count;
        return ListPure<E>::pushBack(x);
    }
 
    template<class... Args>
    iterator emplaceBack(Args&&... args) {
        ++m_count;
        return ListPure<E>::emplaceBack(std::forward<Args>(args)...);
    }
 
    iterator insert(const E& x, iterator it, Direction dir = Direction::after) {
        ++m_count;
        return ListPure<E>::insert(x, it, dir);
    }
 
    iterator insertBefore(const E& x, iterator it) {
        ++m_count;
        return ListPure<E>::insertBefore(x, it);
    }
 
    iterator insertAfter(const E& x, iterator it) {
        ++m_count;
        return ListPure<E>::insertAfter(x, it);
    }
 
 
 
    void popFront() {
        --m_count;
        ListPure<E>::popFront();
    }
 
    E popFrontRet() {
        E el = front();
        popFront();
        return el;
    }
 
    void popBack() {
        --m_count;
        ListPure<E>::popBack();
    }
 
    E popBackRet() {
        E el = back();
        popBack();
        return el;
    }
 
    void del(iterator it) {
        --m_count;
        ListPure<E>::del(it);
    }
 
    bool removeFirst(const E& x) {
        bool hasRemoved = ListPure<E>::removeFirst(x);
        if (hasRemoved) {
            --m_count;
        }
        return hasRemoved;
    }
 
    void clear() {
        m_count = 0;
        ListPure<E>::clear();
    }
 
 
 
    void moveToFront(iterator it, List<E>& L2) {
        ListPure<E>::moveToFront(it, L2);
        --m_count;
        ++L2.m_count;
    }
 
    void moveToBack(iterator it, List<E>& L2) {
        ListPure<E>::moveToBack(it, L2);
        --m_count;
        ++L2.m_count;
    }
 
    void moveToSucc(iterator it, List<E>& L2, iterator itBefore) {
        ListPure<E>::moveToSucc(it, L2, itBefore);
        --m_count;
        ++L2.m_count;
    }
 
    void moveToPrec(iterator it, List<E>& L2, iterator itAfter) {
        ListPure<E>::moveToPrec(it, L2, itAfter);
        --m_count;
        ++L2.m_count;
    }
 
    void conc(List<E>& L2) {
        ListPure<E>::conc(L2);
        m_count += L2.m_count;
        L2.m_count = 0;
    }
 
    void concFront(List<E>& L2) {
        ListPure<E>::concFront(L2);
        m_count += L2.m_count;
        L2.m_count = 0;
    }
 
    void swap(List<E>& other) {
        ListPure<E>::swap(other);
        std::swap(m_count, other.m_count);
    }
 
    void split(iterator it, List<E>& L1, List<E>& L2, Direction dir = Direction::before) {
        ListPure<E>::split(it, L1, L2, dir);
        int countL = m_count, countL1 = 0;
        for (ListElement<E>* pX = L1.m_head; pX != nullptr; pX = pX->m_next) {
            ++countL1;
        }
 
        L1.m_count = countL1;
        L2.m_count = countL - countL1;
        if (this->m_head == nullptr) {
            m_count = 0;
        }
    }
 
    using ListPure<E>::empty;
    using ListPure<E>::front;
    using ListPure<E>::back;
    using ListPure<E>::get;
    using ListPure<E>::pos;
    using ListPure<E>::begin;
    using ListPure<E>::cbegin;
    using ListPure<E>::end;
    using ListPure<E>::cend;
    using ListPure<E>::rbegin;
    using ListPure<E>::crbegin;
    using ListPure<E>::rend;
    using ListPure<E>::crend;
    using ListPure<E>::cyclicSucc;
    using ListPure<E>::cyclicPred;
    using ListPure<E>::exchange;
    using ListPure<E>::moveToFront;
    using ListPure<E>::moveToBack;
    using ListPure<E>::moveToSucc;
    using ListPure<E>::moveToPrec;
    using ListPure<E>::reverse;
    using ListPure<E>::search;
    using ListPure<E>::quicksort;
    using ListPure<E>::bucketSort;
    using ListPure<E>::chooseIterator;
    using ListPure<E>::chooseElement;
    using ListPure<E>::permute;
 
    OGDF_NEW_DELETE
};
 
template<class E>
void ListPure<E>::bucketSort(int l, int h, BucketFunc<E>& f) {
    if (m_head == m_tail) {
        return;
    }
 
    Array<ListElement<E>*> head(l, h, nullptr), tail(l, h);
 
    ListElement<E>* pX;
    for (pX = m_head; pX; pX = pX->m_next) {
        int i = f.getBucket(pX->m_x);
        if (head[i]) {
            tail[i] = ((pX->m_prev = tail[i])->m_next = pX);
        } else {
            head[i] = tail[i] = pX;
        }
    }
 
    ListElement<E>* pY = nullptr;
    for (int i = l; i <= h; i++) {
        pX = head[i];
        if (pX) {
            if (pY) {
                (pY->m_next = pX)->m_prev = pY;
            } else {
                (m_head = pX)->m_prev = nullptr;
            }
            pY = tail[i];
        }
    }
 
    m_tail = pY;
    pY->m_next = nullptr;
}
 
template<class E>
template<class RNG>
void ListPure<E>::permute(const int n, RNG& rng) {
    //if n==0 do nothing
    if (n == 0) {
        return;
    }
 
    Array<ListElement<E>*> A(n + 2);
    A[0] = A[n + 1] = nullptr;
 
    int i = 1;
    ListElement<E>* pX;
    for (pX = m_head; pX; pX = pX->m_next) {
        A[i++] = pX;
    }
 
    A.permute(1, n, rng);
 
    for (i = 1; i <= n; i++) {
        pX = A[i];
        pX->m_next = A[i + 1];
        pX->m_prev = A[i - 1];
    }
 
    m_head = A[1];
    m_tail = A[n];
}
 
template<class E>
void print(std::ostream& os, const ListPure<E>& L, char delim = ' ') {
    typename ListPure<E>::const_iterator 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 List<E>& L, char delim = ' ') {
    print(os, L.getListPure(), delim);
}
 
template<class E>
std::ostream& operator<<(std::ostream& os, const ListPure<E>& L) {
    print(os, L);
    return os;
}
 
template<class E>
std::ostream& operator<<(std::ostream& os, const List<E>& L) {
    return os << L.getListPure();
}
 
template<class E, class Master>
class ListContainer : public List<E> {
    friend Master;
 
public:
    using iterator = typename List<E>::const_iterator;
    using reverse_iterator = typename List<E>::const_reverse_iterator;
 
    iterator begin() const { return List<E>::cbegin(); }
 
    iterator end() const { return List<E>::cend(); }
 
    reverse_iterator rbegin() const { return List<E>::crbegin(); }
 
    reverse_iterator rend() const { return List<E>::crend(); }
 
    int size() const { return List<E>::size(); }
};
 
}