List.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/internal/list_templates.h>
#include <ogdf/basic/Reverse.h>
#include <random>
 
namespace ogdf {
 
template<class E> class List;
template<class E> class ListPure;
template<class E, bool isConst, bool isReverse> class ListIteratorBase;
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;
 
    operator ListElem *() { return m_pX; }
 
public:
    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) : m_head(L.m_head), m_tail(L.m_tail) {
        reassignListRefs();
        L.m_head = L.m_tail = nullptr;
    }
 
    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 == 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) : 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(); }
};
 
}