List.h

Go to the documentation of this file.

/*
 * $Revision: 2299 $
 * 
 * last checkin:
 *   $Author: gutwenger $ 
 *   $Date: 2012-05-07 15:57:08 +0200 (Mon, 07 May 2012) $ 
 ***************************************************************/

#ifdef _MSC_VER
#pragma once
#endif

#ifndef OGDF_LIST_H
#define OGDF_LIST_H


#include <ogdf/internal/basic/list_templates.h>


namespace ogdf {


template<class E> class List;
template<class E> class ListPure;
template<class E> class ListIterator;
template<class E> class ListConstIterator;


template<class E>
class ListElement {
    friend class ListPure<E>;
    friend class List<E>;
    friend class ListIterator<E>;
    friend class ListConstIterator<E>;

    ListElement<E> *m_next; 
    ListElement<E> *m_prev; 
    E m_x; 

    ListElement() : m_next(0), m_prev(0) { }
    ListElement(const E &x) : m_next(0), m_prev(0), m_x(x) { }
    ListElement(const E &x, ListElement<E> *next, ListElement<E> *prev) :
        m_next(next), m_prev(prev), m_x(x) { }

    OGDF_NEW_DELETE
}; // class ListElement




template<class E> class ListIterator {
    ListElement<E> *m_pX; // pointer to associated list element

    friend class ListConstIterator<E>;
    friend class ListPure<E>;

    operator ListElement<E> *() { return m_pX; }
    operator const ListElement<E> *() const { return m_pX; }

public:
    ListIterator() : m_pX(0) { }
    ListIterator(ListElement<E> *pX) : m_pX(pX) { }
    ListIterator(const ListIterator<E> &it) : m_pX(it.m_pX) { }

    bool valid() const { return m_pX != 0; }

    bool operator==(const ListIterator<E> &it) const {
        return m_pX == it.m_pX;
    }

    bool operator!=(const ListIterator<E> &it) const {
        return m_pX != it.m_pX;
    }

    ListIterator<E> succ() const { return m_pX->m_next; }

    ListIterator<E> pred() const { return m_pX->m_prev; }

    E &operator*() const { return m_pX->m_x; }

    ListIterator<E> &operator=(const ListIterator<E> &it) {
        m_pX = it.m_pX;
        return *this;
    }

    ListIterator<E> &operator++() {
        m_pX = m_pX->m_next;
        return *this;
    }

    ListIterator<E> operator++(int) {
        ListIterator<E> it = *this;
        m_pX = m_pX->m_next;
        return it;
    }

    ListIterator<E> &operator--() {
        m_pX = m_pX->m_prev;
        return *this;
    }

    ListIterator<E> operator--(int) {
        ListIterator<E> it = *this;
        m_pX = m_pX->m_prev;
        return it;
    }

    OGDF_NEW_DELETE
}; // class ListIterator



//---------------------------------------------------------
// ListConstIterator<E>
// const iterator for doubly linked lists
//---------------------------------------------------------

template<class E> class ListConstIterator {
    const ListElement<E> *m_pX; // pointer to list element

    friend class ListPure<E>;

    operator const ListElement<E> *() { return m_pX; }

public:
    ListConstIterator() : m_pX(0) { }
    
    ListConstIterator(const ListElement<E> *pX) : m_pX(pX) { }

    ListConstIterator(const ListIterator<E> &it) : m_pX((const ListElement<E> *)it) { }
    ListConstIterator(const ListConstIterator &it) : m_pX(it.m_pX) { }

    bool valid() const { return m_pX != 0; }

    bool operator==(const ListConstIterator<E> &it) const {
        return m_pX == it.m_pX;
    }

    bool operator!=(const ListConstIterator<E> &it) const {
        return m_pX != it.m_pX;
    }

    ListConstIterator<E> succ() const { return m_pX->m_next; }

    ListConstIterator<E> pred() const { return m_pX->m_prev; }

    const E &operator*() const { return m_pX->m_x; }

    ListConstIterator<E> &operator=(const ListConstIterator<E> &it) {
        m_pX = it.m_pX;
        return *this;
    }

    ListConstIterator<E> &operator++() {
        m_pX = m_pX->m_next;
        return *this;
    }

    ListConstIterator<E> operator++(int) {
        ListConstIterator<E> it = *this;
        m_pX = m_pX->m_next;
        return it;
    }

    ListConstIterator<E> &operator--() {
        m_pX = m_pX->m_prev;
        return *this;
    }

    ListConstIterator<E> operator--(int) {
        ListConstIterator<E> it = *this;
        m_pX = m_pX->m_prev;
        return it;
    }

    OGDF_NEW_DELETE
}; // class ListConstIterator




template<class E> class ListPure {
protected:

    ListElement<E> *m_head; 
    ListElement<E> *m_tail; 

public:
    ListPure() : m_head(0), m_tail(0) { }

    ListPure(const ListPure<E> &L) : m_head(0), m_tail(0) {
        copy(L);
    }

    // destruction
    ~ListPure() { clear(); }

    typedef E value_type;
    typedef ListElement<E> element_type;
    typedef ListConstIterator<E> const_iterator;
    typedef ListIterator<E> iterator;

    bool empty() const { return m_head == 0; }


    int size() const {
        int count = 0;
        for (ListElement<E> *pX = m_head; pX; pX = pX->m_next)
            ++count;
        return count;
    }


    const ListConstIterator<E> begin() const { return m_head; }

    ListIterator<E> begin() { return m_head; }


    ListConstIterator<E> end() const { return ListConstIterator<E>(); }

    ListIterator<E> end() { return ListIterator<E>(); }


    const ListConstIterator<E> rbegin() const { return m_tail; }

    ListIterator<E> rbegin() { return m_tail; }


    ListConstIterator<E> rend() const { return ListConstIterator<E>(); }

    ListIterator<E> rend() { return ListIterator<E>(); }


    const E &front() const {
        OGDF_ASSERT(m_head != 0)
        return m_head->m_x;
    }


    E &front() {
        OGDF_ASSERT(m_head != 0)
        return m_head->m_x;
    }


    const E &back() const {
        OGDF_ASSERT(m_tail != 0)
        return m_tail->m_x;
    }


    E &back() {
        OGDF_ASSERT(m_tail != 0)
        return m_tail->m_x;
    }


    ListConstIterator<E> cyclicSucc(ListConstIterator<E> it) const {
        const ListElement<E> *pX = it;
        return (pX->m_next) ? pX->m_next : m_head;
    }


    ListIterator<E> cyclicSucc(ListIterator<E> it) {
        OGDF_ASSERT(it.valid())
        ListElement<E> *pX = it;
        return (pX->m_next) ? pX->m_next : m_head;
    }


    ListConstIterator<E> cyclicPred(ListConstIterator<E> it) const {
        OGDF_ASSERT(it.valid())
        const ListElement<E> *pX = it;
        return (pX->m_prev) ? pX->m_prev : m_tail;
    }


    ListIterator<E> cyclicPred(ListIterator<E> it) {
        OGDF_ASSERT(it.valid())
        ListElement<E> *pX = it;
        return (pX->m_prev) ? pX->m_prev : m_tail;
    }


    ListConstIterator<E> get(int pos) const {
      ListElement<E> *pX;
        for(pX = m_head; pX != 0; pX = pX->m_next)
            if (pos-- == 0) break;
        return pX;
    }


    ListIterator<E> get(int pos) {
      ListElement<E> *pX;
        for(pX = m_head; pX != 0; pX = pX->m_next)
            if (pos-- == 0) break;
        return pX;
    }


    int pos(ListConstIterator<E> it) const {
        OGDF_ASSERT(it.valid())
        int p = 0;
        for(ListElement<E> *pX = m_head; pX != 0; pX = pX->m_next, ++p)
            if (pX == it) break;
        return p;
    }

    // returns random valid iterator. Note that this takes linear time (doubled).
    ListConstIterator<E> chooseIterator() const {
        return get(randomNumber(0,size()-1));
    }

    // returns random valid iterator. Note that this takes linear time (doubled).
    ListIterator<E> chooseIterator() {
        return get(randomNumber(0,size()-1));
    }

    // returns random element. Note that this takes linear time.
    const E chooseElement() const {
        return *chooseIterator();
    }

    // returns random element. Note that this takes linear time.
    E chooseElement() {
        return *chooseIterator();
    }

    ListPure<E> &operator=(const ListPure<E> &L) {
        clear(); copy(L);
        return *this;
    }

    bool operator==(const ListPure<E> &L) const {
        ListElement<E> *pX = m_head, *pY = L.m_head;
        while(pX != 0 && pY != 0) {
            if(pX->m_x != pY->m_x)
                return false;
            pX = pX->m_next;
            pY = pY->m_next;
        }
        return (pX == 0 && pY == 0);
    }

    bool operator!=(const ListPure<E> &L) const {
        return !operator==(L);
    }

    ListIterator<E> pushFront(const E &x) {
        ListElement<E> *pX = OGDF_NEW ListElement<E>(x,m_head,0);
        if (m_head)
            m_head = m_head->m_prev = pX;
        else
            m_head = m_tail = pX;
        return m_head;
    }

    ListIterator<E> pushBack(const E &x) {
        ListElement<E> *pX = OGDF_NEW ListElement<E>(x,0,m_tail);
        if (m_head)
            m_tail = m_tail->m_next = pX;
        else
            m_tail = m_head = pX;
        return m_tail;
    }


    ListIterator<E> insert(const E &x, ListIterator<E> it, Direction dir = after) {
        OGDF_ASSERT(it.valid())
        OGDF_ASSERT(dir == after || dir == before)
        ListElement<E> *pY = it, *pX;
        if (dir == after) {
            ListElement<E> *pYnext = pY->m_next;
            pY->m_next = pX = OGDF_NEW ListElement<E>(x,pYnext,pY);
            if (pYnext) pYnext->m_prev = pX;
            else m_tail = pX;
        } else {
            ListElement<E> *pYprev = pY->m_prev;
            pY->m_prev = pX = OGDF_NEW ListElement<E>(x,pY,pYprev);
            if (pYprev) pYprev->m_next = pX;
            else m_head = pX;
        }
        return pX;
    }


    ListIterator<E> insertBefore(const E &x, ListIterator<E> it) {
        OGDF_ASSERT(it.valid())
        ListElement<E> *pY = it, *pX;
        ListElement<E> *pYprev = pY->m_prev;
        pY->m_prev = pX = OGDF_NEW ListElement<E>(x,pY,pYprev);
        if (pYprev) pYprev->m_next = pX;
        else m_head = pX;
        return pX;
    }


    ListIterator<E> insertAfter(const E &x, ListIterator<E> it) {
        OGDF_ASSERT(it.valid())
        ListElement<E> *pY = it, *pX;
        ListElement<E> *pYnext = pY->m_next;
        pY->m_next = pX = OGDF_NEW ListElement<E>(x,pYnext,pY);
        if (pYnext) pYnext->m_prev = pX;
        else m_tail = pX;
        return pX;
    }


    void popFront() {
        OGDF_ASSERT(m_head != 0)
        ListElement<E> *pX = m_head;
        m_head = m_head->m_next;
        delete pX;
        if (m_head) m_head->m_prev = 0;
        else m_tail = 0;
    }


    E popFrontRet() {
        E el = front(); 
        popFront();
        return el;
    }


    void popBack() {
        OGDF_ASSERT(m_tail != 0)
        ListElement<E> *pX = m_tail;
        m_tail = m_tail->m_prev;
        delete pX;
        if (m_tail) m_tail->m_next = 0;
        else m_head = 0;
    }


    E popBackRet() {
        E el = back(); 
        popBack();
        return el;
    }


    void del(ListIterator<E> it) {
        OGDF_ASSERT(it.valid())
        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;
    }


    void exchange(ListIterator<E> it1, ListIterator<E> it2) {
        OGDF_ASSERT(it1.valid() && it2.valid() && it1 != it2)
        ListElement<E> *pX = it1, *pY = it2;

        std::swap(pX->m_next,pY->m_next);
        std::swap(pX->m_prev,pY->m_prev);

        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(ListIterator<E> it) {
        OGDF_ASSERT(it.valid())
        // 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 = 0;
        pX->m_next = m_head;
        m_head = m_head->m_prev = pX;
    }//move
    

    void moveToBack(ListIterator<E> it) {
        OGDF_ASSERT(it.valid())
        // 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 = 0;
        m_tail = m_tail->m_next = pX;
    }//move


    void moveToSucc(ListIterator<E> it, ListIterator<E> itBefore) {
        OGDF_ASSERT(it.valid() && itBefore.valid())
        // 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;
    }//move


    void moveToPrec(ListIterator<E> it, ListIterator<E> itAfter) {
        OGDF_ASSERT(it.valid() && itAfter.valid())
        // 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;
    }//move


    void moveToFront(ListIterator<E> it, ListPure<E> &L2) {
        OGDF_ASSERT(it.valid())
        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 = 0;
        if ((pX->m_next = L2.m_head) != 0)
            L2.m_head = L2.m_head->m_prev = pX;
        else
            L2.m_head = L2.m_tail = pX;
    }


    void moveToBack(ListIterator<E> it, ListPure<E> &L2) {
        OGDF_ASSERT(it.valid())
        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 = 0;
        if ((pX->m_prev = L2.m_tail) != 0)
            L2.m_tail = L2.m_tail->m_next = pX;
        else
            L2.m_head = L2.m_tail = pX;
    }


    void moveToSucc(ListIterator<E> it, ListPure<E> &L2, ListIterator<E> itBefore) {
        OGDF_ASSERT(it.valid() && itBefore.valid())
        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;
    }


    void moveToPrec(ListIterator<E> it, ListPure<E> &L2, ListIterator<E> itAfter) {
        OGDF_ASSERT(it.valid() && itAfter.valid())
        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;
    }

    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;
        }
        L2.m_head = L2.m_tail = 0;
    }

    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;
        }
        L2.m_head = L2.m_tail = 0;
    }


    void exchange(ListPure<E>& L2) {
        ListElement<E>* t;
        t = this->m_head;
        this->m_head = L2.m_head; 
        L2.m_head = t; 
        t = this->m_tail;
        this->m_tail = L2.m_tail; 
        L2.m_tail = t; 
    }


    void split(ListIterator<E> it,ListPure<E> &L1,ListPure<E> &L2,Direction dir = before) {
        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 == 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 = 0;

        } else {
            L1.m_head = L1.m_tail = 0;
            L2.m_head = m_head;
            L2.m_tail = m_tail;
        }
        
        if (this != &L1 && this != &L2) {
            m_head = m_tail = 0;
        }
    }

    void splitAfter(ListIterator<E> it, ListPure<E> &L2) {
        OGDF_ASSERT(it.valid())
        OGDF_ASSERT(this != &L2)
        L2.clear();
        ListElement<E> *pX = it;
        if (pX != m_tail) {
            (L2.m_head = pX->m_next)->m_prev = 0;
            pX->m_next = 0; 
            L2.m_tail = m_tail;
            m_tail = pX;
        }
    }

    void splitBefore(ListIterator<E> it, ListPure<E> &L2) {
        OGDF_ASSERT(it.valid())
        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) == 0)
            m_head = 0;
        else
            m_tail->m_next = 0;
        pX->m_prev = 0;
    }

    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;
        }
    }

    void clear() {
        if (m_head == 0) return;

#if (_MSC_VER == 1100)
// workaround for bug in Visual Studio 5.0

        while (!empty())
            popFront();

#else

        if (doDestruction((E*)0)) {
            for(ListElement<E> *pX = m_head; pX != 0; pX = pX->m_next)
                pX->m_x.~E();
        }
        OGDF_ALLOCATOR::deallocateList(sizeof(ListElement<E>),m_head,m_tail);

#endif

        m_head = m_tail = 0;
    }

    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 permute() {
        permute(size());
    }
    
    int search (const E& e) const {
        int x = 0;
        for(ListConstIterator<E> i = begin(); i.valid(); ++i, ++x)
            if(*i == e) return x;
        return -1;
    }
    
    template<class COMPARER>
    int search (const E& e, const COMPARER &comp) const {
        int x = 0;
        for(ListConstIterator<E> i = begin(); i.valid(); ++i, ++x)
            if(comp.equal(*i,e)) return x;
        return -1;
    }

protected:
    void copy(const ListPure<E> &L) {
        for(ListElement<E> *pX = L.m_head; pX != 0; pX = pX->m_next)
            pushBack(pX->m_x);
    }

    void permute(const int n);

    OGDF_NEW_DELETE
}; // class ListPure




#define forall_listiterators(type, it, L) \
   for(ListConstIterator< type > it = (L).begin(); it.valid(); ++it)


#define forall_rev_listiterators(type, it, L) \
   for(ListConstIterator< type > it = (L).rbegin(); it.valid(); --it)


#define forall_nonconst_listiterators(type, it, L) \
   for(ListIterator< type > it = (L).begin(); it.valid(); ++it)


#define forall_rev_nonconst_listiterators(type, it, L) \
   for(ListIterator< type > it = (L).rbegin(); it.valid(); --it)
 

#define forall_slistiterators(type, it, L) \
   for(SListConstIterator< type > it = (L).begin(); it.valid(); ++it)


#define forall_nonconst_slistiterators(type, it, L) \
   for(SListIterator< type > it = (L).begin(); it.valid(); ++it)





template<class E>
class List : private ListPure<E> {

    int m_count; 

public:
    List() : m_count(0) { }

    List(const List<E> &L) : ListPure<E>(L), m_count(L.m_count) { }

    // destruction
    ~List() { }

    typedef E value_type;
    typedef ListElement<E> element_type;
    typedef ListConstIterator<E> const_iterator;
    typedef ListIterator<E> iterator;

    bool empty() const { return ListPure<E>::empty(); }

    // returns length of list
    int size() const { return m_count; }

    // returns first element of list (0 if empty)
    const ListConstIterator<E> begin() const { return ListPure<E>::begin(); }
    // returns first element of list (0 if empty)
    ListIterator<E> begin() { return ListPure<E>::begin(); }

    // returns iterator to one-past-last element of list
    ListConstIterator<E> end() const { return ListConstIterator<E>(); }
    // returns iterator to one-past-last element of list
    ListIterator<E> end() { return ListIterator<E>(); }

    // returns last element of list (0 if empty)
    const ListConstIterator<E> rbegin() const { return ListPure<E>::rbegin(); }
    // returns last element of list (0 if empty)
    ListIterator<E> rbegin() { return ListPure<E>::rbegin(); }

    // returns iterator to one-before-first element of list
    ListConstIterator<E> rend() const { return ListConstIterator<E>(); }
    // returns iterator to one-before-first element of list
    ListIterator<E> rend() { return ListIterator<E>(); }

    // returns reference to first element
    const E &front() const { return ListPure<E>::front(); }
    // returns reference to first element
    E &front() { return ListPure<E>::front(); }

    // returns reference to last element
    const E &back() const { return ListPure<E>::back(); }
    // returns reference to last element
    E &back() { return ListPure<E>::back(); }

    // returns cyclic successor
    ListConstIterator<E> cyclicSucc(ListConstIterator<E> it) const {
        return ListPure<E>::cyclicSucc(it);
    }

    // returns cyclic successor
    ListIterator<E> cyclicSucc(ListIterator<E> it) {
        return ListPure<E>::cyclicSucc(it);
    }

    // returns cyclic predecessor
    ListConstIterator<E> cyclicPred(ListConstIterator<E> it) const {
        return ListPure<E>::cyclicPred(it);
    }

    // returns cyclic predecessor
    ListIterator<E> cyclicPred(ListIterator<E> it) {
        return ListPure<E>::cyclicPred(it);
    }

    // returns the iterator at position pos. Note that this takes time linear in pos.
    ListConstIterator<E> get(int pos) const {
        OGDF_ASSERT(0 <= pos && pos < m_count)
        return ListPure<E>::get(pos);
    }

    // returns the iterator at position pos. Note that this takes time linear in pos.
    ListIterator<E> get(int pos) {
        OGDF_ASSERT(0 <= pos && pos < m_count)
        return ListPure<E>::get(pos);
    }

    // returns the position (starting with 0) of it in the list
    int pos(ListConstIterator<E> it) const {
        return ListPure<E>::pos(it);
    }

    // returns random valid iterator. Note that this takes linear time.
    ListConstIterator<E> chooseIterator() const {
        return get(randomNumber(0,m_count-1));
    }

    // returns random valid iterator. Note that this takes linear time.
    ListIterator<E> chooseIterator() {
        return get(randomNumber(0,m_count-1));
    }

    // returns random element. Note that this takes linear time.
    const E chooseElement() const {
        return *chooseIterator();
    }

    // returns random element. Note that this takes linear time.
    E chooseElement() {
        return *chooseIterator();
    }

    // assignment
    List<E> &operator=(const List<E> &L) {
        ListPure<E>::operator=(L);
        m_count = L.m_count;
        return *this;
    }

    bool operator==(const List<E> &L) const {
        if(m_count != L.m_count)
            return false;

        ListElement<E> *pX = ListPure<E>::m_head, *pY = L.m_head;
        while(pX != 0) {
            if(pX->m_x != pY->m_x)
                return false;
            pX = pX->m_next;
            pY = pY->m_next;
        }
        return true;
    }

    bool operator!=(const List<E> &L) const {
        return !operator==(L);
    }

    // adds element x at beginning
    ListIterator<E> pushFront(const E &x) {
        ++m_count;
        return ListPure<E>::pushFront(x);
    }

    // adds element x at end
    ListIterator<E> pushBack(const E &x) {
        ++m_count;
        return ListPure<E>::pushBack(x);
    }

    // inserts x before or after it
    ListIterator<E> insert(const E &x, ListIterator<E> it, Direction dir = after) {
        ++m_count;
        return ListPure<E>::insert(x,it,dir);
    }

    // inserts x before it
    ListIterator<E> insertBefore(const E &x, ListIterator<E> it) {
        ++m_count;
        return ListPure<E>::insertBefore(x,it);
    }

    // inserts x after it
    ListIterator<E> insertAfter(const E &x, ListIterator<E> it) {
        ++m_count;
        return ListPure<E>::insertAfter(x,it);
    }

    // removes first element
    void popFront() {
        --m_count;
        ListPure<E>::popFront();
    }

    // removes first element and returns it
    E popFrontRet() {
        E el = front(); 
        popFront();
        return el;
    }

    // removes last element
    void popBack() {
        --m_count;
        ListPure<E>::popBack();
    }

    // removes last element and returns it
    E popBackRet() {
        E el = back(); 
        popBack();
        return el;
    }

    void exchange(ListIterator<E> it1, ListIterator<E> it2) {
        ListPure<E>::exchange(it1,it2);
    }


    void moveToFront(ListIterator<E> it) {
        ListPure<E>::moveToFront(it);
    }

    void moveToBack(ListIterator<E> it) {
        ListPure<E>::moveToBack(it);
    }

    void moveToSucc(ListIterator<E> it, ListIterator<E> itBefore) {
        ListPure<E>::moveToSucc(it,itBefore);
    }

    void moveToPrec(ListIterator<E> it, ListIterator<E> itAfter) {
        ListPure<E>::moveToPrec(it,itAfter);
    }


    void moveToFront(ListIterator<E> it, List<E> &L2) {
        ListPure<E>::moveToFront(it,L2);
        --m_count; ++L2.m_count;
    }

    void moveToBack(ListIterator<E> it, List<E> &L2) {
        ListPure<E>::moveToBack(it,L2);
        --m_count; ++L2.m_count;
    }


    void moveToSucc(ListIterator<E> it, List<E> &L2, ListIterator<E> itBefore) {
        ListPure<E>::moveToSucc(it,L2,itBefore);
        --m_count; ++L2.m_count;
    }

    void moveToPrec(ListIterator<E> it, List<E> &L2, ListIterator<E> itAfter) {
        ListPure<E>::moveToPrec(it,L2,itAfter);
        --m_count; ++L2.m_count;
    }

    // removes it and frees memory
    void del(ListIterator<E> it) {
        --m_count;
        ListPure<E>::del(it);
    }

    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 exchange(List<E>& L2) {
        ListPure<E>::exchange(L2);
        int t = this->m_count;
        this->m_count = L2.m_count; 
        L2.m_count = t; 
    }
    

    void split(ListIterator<E> it,List<E> &L1,List<E> &L2,Direction dir = before) {
        ListPure<E>::split(it,L1,L2,dir);
        int countL = m_count, countL1 = 0;
        for(ListElement<E> *pX = L1.m_head; pX != 0; pX = pX->m_next)
            ++countL1;

        L1.m_count = countL1;
        L2.m_count = countL - countL1;
        if (this->m_head == 0) m_count = 0;
    }

    // reverses the order of the list elements
    void reverse() { ListPure<E>::reverse(); }

    // removes all elements from list
    void clear() {
        m_count = 0;
        ListPure<E>::clear();
    }

    const ListPure<E> &getListPure() const { return *this; }

    // sorts list using quicksort
    void quicksort() {
        ogdf::quicksortTemplate(*this);
    }

    // sorts list using quicksort and parameterized compare element comp
    template<class COMPARER>
    void quicksort(const COMPARER &comp) {
        ogdf::quicksortTemplate(*this,comp);
    }

    // sorts list using bucket sort
    void bucketSort(int l, int h, BucketFunc<E> &f) {
        ListPure<E>::bucketSort(l,h,f);
    }

    // permutes elements in list randomly
    void permute() {
        ListPure<E>::permute(m_count);
    }

    int search (const E& e) const {
        return ListPure<E>::search(e);
    }

    template<class COMPARER>
    int search (const E& e, const COMPARER &comp) const {
        return ListPure<E>::search(e, comp);
    }

 
    OGDF_NEW_DELETE
}; // class List



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,0), 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 = 0;
    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 = 0;
            pY = tail[i];
        }
    }
    
    m_tail = pY;
    pY->m_next = 0;
}


// permutes elements in list randomly; n is the length of the list
template<class E>
void ListPure<E>::permute(const int n)
{
    Array<ListElement<E> *> A(n+2);
    A[0] = A[n+1] = 0;

    int i = 1;
    ListElement<E> *pX;
    for (pX = m_head; pX; pX = pX->m_next)
        A[i++] = pX;

    A.permute(1,n);

    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];
}


// prints list L to output stream os using delimiter delim
template<class E>
void print(ostream &os, const ListPure<E> &L, char delim = ' ')
{
    ListConstIterator<E> pX = L.begin();
    if (pX.valid()) {
        os << *pX;
        for(++pX; pX.valid(); ++pX)
            os << delim << *pX;
    }
}

// prints list L to output stream os using delimiter delim
template<class E>
void print(ostream &os, const List<E> &L, char delim = ' ')
{
    print(os, L.getListPure(), delim);
}

// prints list L to output stream os
template<class E>
ostream &operator<<(ostream &os, const ListPure<E> &L)
{
    print(os,L);
    return os;
}

// prints list L to output stream os
template<class E>
ostream &operator<<(ostream &os, const List<E> &L)
{
    return os << L.getListPure();
}


} // end namespace ogdf


#endif