EList.h

Go to the documentation of this file.

/*
 * $Revision: 2579 $
 *
 * last checkin:
 *   $Author: gutwenger $
 *   $Date: 2012-07-11 15:28:17 +0200 (Mi, 11. Jul 2012) $
 ***************************************************************/

#ifdef _MSC_VER
#pragma once
#endif

#ifndef OGDF_ELIST_H
#define OGDF_ELIST_H

namespace ogdf {

// EStack forward declaration
template<typename S, typename E, E* S::*first, E* E::*next> class EStack;
// EListIterator forward declaration
template<typename E, E* E::*prev, E* E::*next> class EListIterator;
// EList forward declaration
template<typename L, typename E, int L::*numElem, E* L::*first, E* L::*last, E* E::*next, E* E::*prev> class EList;

template<typename S, typename E, E* S::*first, E* E::*next>
class EStack
{
public:
    static inline void init(S* pStack)
    {
        pStack->*first = 0;
    }

    static inline void pop(S* pStack)
    {
        pStack->*first = pStack->*first->*next;
    }

    static inline E* popRet(S* pStack)
    {
        E* res = pStack->*first;
        pStack->*first = pStack->*first->*next;
        return res;
    }

    static inline void push(S* pStack, E* pElem)
    {
        pElem->*next = pStack->*first;
        pStack->*first = pElem;
    }

    static inline E* top(const S* pStack)
    {
        return pStack->*first;
    }

    static inline bool empty(const S* pStack)
    {
        return (pStack->*first == 0);
    }
};


template<typename E, E* E::*prev, E* E::*next>
class EListIterator
{
public:
    inline EListIterator( ) : m_ptr(0) {}

    inline EListIterator(E* ptr) : m_ptr(ptr) {}

    inline EListIterator(const EListIterator<E, prev, next>& other) : m_ptr(other.m_ptr) {}

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

    inline bool operator==(const EListIterator<E, prev, next>& other) const { return m_ptr == other.m_ptr; }

    inline bool operator!=(const EListIterator<E, prev, next>& other) const { return m_ptr != other.m_ptr; }

    inline EListIterator<E, prev, next> succ() const { return m_ptr->*next; }

    inline EListIterator<E, prev, next> pred() const { return m_ptr->*prev; }

    //E& operator*() const { return *m_ptr; }

    E* operator*() const { return m_ptr; }

    inline EListIterator<E, prev, next> &operator=(const EListIterator<E, prev, next>& other)
    {
        m_ptr = other.m_ptr;
        return *this;
    }

    inline EListIterator<E, prev, next>& operator++()
    {
        m_ptr = m_ptr->*next;
        return *this;
    }

    inline EListIterator<E, prev, next> operator++(int)
    {
        EListIterator<E, prev, next> it = *this;
        m_ptr = m_ptr->*next;
        return it;
    }

    inline EListIterator<E, prev, next>& operator--()
    {
        m_ptr = m_ptr->*prev;
        return *this;
    }

    inline EListIterator<E, prev, next> operator--(int)
    {
        EListIterator<E, prev, next> it = *this;
        m_ptr = m_ptr->*prev;
        return it;
    }

private:
    E* m_ptr;
};


template<
    typename L,
    typename E,
    int L::*numElem,
    E* L::*first,
    E* L::*last,
    E* E::*next,
    E* E::*prev
>
class EList
{
public:
    typedef EListIterator<E, prev, next> iterator;

    static inline void init(L* pList)
    {
        pList->*first = 0;
        pList->*last = 0;
        pList->*numElem = 0;
    }

    static inline int size(const L* pList) { return (pList->*numElem); }

    static inline bool empty(const L* pList) { return (pList->*first == 0); }

    static inline E* front(const L* pList) { return pList->*first; }

    static inline E* back(const L* pList)   { return pList->*last; }

    static inline iterator pushBack(L* pList, E* elem)
    {
        elem->*next = 0;
        elem->*prev = pList->*last;
        if (pList->*last)
            pList->*last = pList->*last->*next = elem;
        else
            pList->*last = pList->*first = elem;

        (pList->*numElem)++;
        return iterator(elem);
    }

    static inline iterator pushFront(L* pList, E* elem)
    {
        elem->*next = pList->*first;
        elem->*prev = 0;

        if (pList->*first)
            pList->*first = pList->*first->*prev = elem;
        else
            pList->*first = pList->*last = elem;

        (pList->*numElem)++;

        return iterator(elem);
    }

    static inline iterator insertBefore(L* pList, E* elem, E* pNext)
    {
        E* pPrev;

        if (pNext)
            pPrev = pNext->*prev;
        else
            pPrev = 0;

        elem->*next = pNext;
        elem->*prev = pPrev;

        if (pNext)
            pNext->*prev = elem;
        else
            pList->*last = elem;
        if (pPrev)
            pPrev->*next = elem;
        else
            pList->*first = elem;

        (pList->*numElem)++;
        return iterator(elem);
    }

    static inline iterator insertBefore(L* pList, E* elem, const iterator& itNext)
    {
        return insertBefore(pList, elem, (E*)(*itNext));
    }

    static inline iterator insertAfter(L* pList, E* elem, E* pPrev)
    {
        E* pNext;

        if (pPrev)
            pNext = pPrev->*next;
        else
            pNext = 0;

        elem->*next = pNext;
        elem->*prev = pPrev;

        if (pNext)
            pNext->*prev = elem;
        else
            pList->*last = elem;
        if (pPrev)
            pPrev->*next = elem;
        else
            pList->*first = elem;

        (pList->*numElem)++;
        return iterator(elem);
    }

    static inline iterator insertAfter(L* pList, E* elem, const iterator& itPrev)
    {
        return insertAfter(pList, elem, (E*)(*itPrev));
    }

    inline static void popFront(L* pList)
    {
        if (front(pList))
            remove(pList, front(pList));
    }

    inline static void popBack(L* pList)
    {
        if (back(pList))
            remove(pList, back(pList));
    }

    static inline iterator remove(L* pList, E* elem)
    {
        E* pPrev = elem->*prev;
        E* pNext = elem->*next;
        if (pPrev)
            pPrev->*next = pNext;
        else
            pList->*first = pNext;
        if (pNext)
            pNext->*prev = pPrev;
        else
            pList->*last = pPrev;

        (pList->*numElem)--;
        return iterator(pNext);
    }

    static inline iterator remove(L* pList, const iterator& it)
    {
        return remove(pList, (E*)(*it));
    }

    template<
        typename L_other,
        E* L_other::*other_first,
        E* L_other::*other_last,
        int L_other::*other_numElem
    >
    inline static void appendFrom( L* pList, L_other* pListOther )
    {
        if (!pListOther->*other_first)
            return;

        if (empty(pList))
        {
            pList->*first = pListOther->*other_first;
            pList->*last = pListOther->*other_last;
        } else
        {
            // link the pList->last element to other->first
            pList->*last->*next = pListOther->*other_first;
            pListOther->*other_first->*prev = pList->*last;

            // link the pList->last element to other->first
            pList->*last = pListOther->*other_first;
        }

        // add the size of the other pList
        pList->*numElem += pListOther->*other_numElem;
        // clear other pList
        pListOther->*other_numElem = 0;
        pListOther->*other_first = 0;
        pListOther->*other_last = 0;
    }

    static inline iterator begin(const L* pList) { return iterator(pList->*first); }

    static inline iterator end(const L* pList) { return iterator(); }

    static inline iterator rbegin(const L* pList) { return iterator(pList->*last); }

    static inline iterator rend(const L* pList) { return iterator(); }

    template<typename Func>
    static inline void forall(const L* pList, const Func& func)
    {
        for(iterator it = begin(pList);it.valid();it++)
        {
            func(*it);
        }
    }

    template<typename A1>
    static inline void forall_call(const L* pList, void (E::*func)( A1 ), const A1& a1)
    {
        for(iterator it = begin(pList);it.valid();it++)
        {
            ((*it)->*func)(a1);
        }
    }

    inline EList(L* pList) : m_pList(pList) { }

    inline void init() { init(m_pList); }

    inline int size() const { return size(m_pList); }
    inline bool empty() const { return empty(m_pList); }

    inline E* front() const { return front(m_pList); }
    inline E* back() const { return back(m_pList); }

    inline iterator pushBack(E* elem) { return pushBack(m_pList, elem); }
    inline iterator pushFront(E* elem) { return pushFront(m_pList, elem); }

    inline iterator insertBefore(E* elem, E* pNext) { return insertBefore(m_pList, elem, pNext); }
    inline iterator insertBefore(E* elem, const iterator& it) { return insertBefore(m_pList, elem, it); }

    inline iterator insertAfter(E* elem, E* pPrev) { return insertAfter(m_pList, elem, pPrev); } ;
    inline iterator insertAfter(E* elem, const iterator& it) { return insertAfter(m_pList, elem, it); } ;

    inline void popFront() { popFront(m_pList); }
    inline void popBack() { popBack(m_pList); }

    void operator<<(E* elem) { pushBack(elem); }

    inline iterator remove(E* elem) { return remove(m_pList, elem); }
    inline iterator remove(const iterator& it)  { return remove(m_pList, (E*)(*it)); }

    inline iterator begin() const { return begin(m_pList); }
    inline iterator end() const { return end(m_pList); }
    inline iterator rbegin() const { return rbegin(m_pList); }
    inline iterator rend() const { return rend(m_pList); }

private:
    L* m_pList;
};


} // end of namespace ogdf

#endif