Open Graph Drawing Framework  v.2007.11

Overview Class Hierarchy Class Index Class List Members Namespaces Source Files Search for:

List.h

Go to the documentation of this file.

/*
 * $Revision: 1.17 $
 * 
 * last checkin:
 *   $Author: gutwenger $ 
 *   $Date: 2007-11-08 16:10:37 +0100 (Do, 08 Nov 2007) $ 
 ***************************************************************/

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

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

    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;

        swap(pX->m_next,pY->m_next);
        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))
            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))
            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 =