Open Graph Drawing Framework  v.2007.11

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

SList.h

Go to the documentation of this file.

/*
 * $Revision: 1.5 $
 * 
 * last checkin:
 *   $Author: gutwenger $ 
 *   $Date: 2007-11-08 16:10:37 +0100 (Do, 08 Nov 2007) $ 
 ***************************************************************/
 
#ifdef _MSC_VER
#pragma once
#endif

#ifndef OGDF_SLIST_H
#define OGDF_SLIST_H


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


namespace ogdf {


template<class E> class SListPure;
template<class E> class StackPure;
template<class E> class SListIterator;
template<class E> class SListConstIterator;


template<class E>
class SListElement {
    friend class SListPure<E>;
    friend class StackPure<E>;
    friend class SListIterator<E>;
    friend class SListConstIterator<E>;

    SListElement<E> *m_next; 
    E m_x; 

    SListElement() : m_next(0) { }
    SListElement(const E &x) : m_next(0), m_x(x) { }
    SListElement(const E &x, SListElement<E> *next) :
        m_next(next), m_x(x) { }
    
    OGDF_NEW_DELETE
}; // class SListElement




template<class E> class SListIterator {
    SListElement<E> *m_pX; 

    friend class SListConstIterator<E>;
    friend class SListPure<E>;

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

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

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

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

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

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

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

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

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

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

    OGDF_NEW_DELETE
}; // class SListIterator




template<class E> class SListConstIterator {
    const SListElement<E> *m_pX; 

    friend class SListPure<E>;

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

public:
    SListConstIterator() : m_pX(0) { }
    
    SListConstIterator(const SListElement<E> *pX) : m_pX(pX) { }
    
    SListConstIterator(const SListIterator<E> &it) : m_pX((const SListElement<E> *)it) { }
    SListConstIterator(const SListConstIterator &it) : m_pX(it.m_pX) { }

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

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

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

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

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

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


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

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

    OGDF_NEW_DELETE
}; // class SListConstIterator



template<class E> class SListPure {
    SListElement<E> *m_head; 
    SListElement<E> *m_tail; 

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

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

    typedef E value_type;
    typedef SListElement<E> element_type;
    typedef SListConstIterator<E> const_iterator;
    typedef SListIterator<E> iterator;

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


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


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


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


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


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


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


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



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


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


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

    

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


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


    SListIterator<E> cyclicSucc(SListIterator<E> it) {
        SListElement<E> *pX = it;
        return (pX->m_next) ? pX->m_next : m_head;
    }

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

    SListIterator<E> pushFront(const E &x) {
        m_head = OGDF_NEW SListElement<E>(x,m_head);
        if (m_tail == 0) m_tail = m_head;
        return m_head;
    }

    SListIterator<E> pushBack(const E &x) {
        SListElement<E> *pNew = OGDF_NEW SListElement<E>(x);
        if (m_head == 0)
            m_head = m_tail = pNew;
        else
            m_tail = m_tail->m_next = pNew;
        return m_tail;
    }


    SListIterator<E> insertAfter(const E &x, SListIterator<E> itBefore) {
        SListElement<E> *pBefore = itBefore;
        OGDF_ASSERT(pBefore != 0)
        SListElement<E> *pNew = OGDF_NEW SListElement<E>(x,pBefore->m_next);
        if (pBefore == m_tail) m_tail = pNew;
        return (pBefore->m_next = pNew);
    }


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


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


    void delSucc(SListIterator<E> itBefore) {
        SListElement<E> *pBefore = itBefore;
        OGDF_ASSERT(pBefore != 0)
        SListElement<E> *pDel = pBefore->m_next;
        OGDF_ASSERT(pDel != 0)
        if ((pBefore->m_next = pDel->m_next) == 0) m_tail = pBefore;
        delete pDel;
    }

    void moveFrontToFront(SListPure<E> &L2) {
        OGDF_ASSERT(m_head != 0)
        OGDF_ASSERT(this != &L2)
        SListElement<E> *pX = m_head;
        if ((m_head = m_head->m_next) == 0) m_tail = 0;
        pX->m_next = L2.m_head;
        L2.m_head = pX;
        if (L2.m_tail == 0) L2.m_tail = L2.m_head;
    }

    void moveFrontToBack(SListPure<E> &L2) {
        OGDF_ASSERT(m_head != 0)
        OGDF_ASSERT(this != &L2)
        SListElement<E> *pX = m_head;
        if ((m_head = m_head->m_next) == 0) m_tail = 0;
        pX->m_next = 0;
        if (L2.m_head == 0)
            L2.m_head = L2.m_tail = pX;
        else
            L2.m_tail = L2.m_tail->m_next = pX;
    }


    void moveFrontToSucc(SListPure<E> &L2, SListIterator<E> itBefore) {
        OGDF_ASSERT(m_head != 0)
        OGDF_ASSERT(this != &L2)
        SListElement<E> *pBefore = itBefore;
        SListElement<E> *pX = m_head;
        if ((m_head = m_head->m_next) == 0) m_tail = 0;
        pX->m_next = pBefore->m_next;
        pBefore->m_next = pX;
        if (pBefore == L2.m_tail) L2.m_tail = pX;
    }

    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(SListElement<E> *pX = m_head; pX != 0; pX = pX->m_next)
                pX->m_x.~E();
        }
        g_memory.deallocateList(m_head,m_tail,sizeof(SListElement<E>));

#endif

        m_head = m_tail = 0;
    }

    void conc(SListPure<E> &L2) {
        if (m_head)
            m_tail->m_next = L2.m_head;
        else
            m_head = L2.m_head;
        if (L2.m_tail != 0) m_tail = L2.m_tail;
        L2.m_head = L2.m_tail = 0;
    }

    void reverse() {
        SListElement<E> *p, *pNext, *pPred = 0;
        for(p = m_head; p; p = pNext) {
            pNext = p->m_next;
            p->m_next = pPred;
            pPred = p;
        }
        ogdf::swap(m_head,m_tail);
    }

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

    void quicksort() {
        ogdf::quicksortTemplate(*this);
    }

    void quicksort(Comparer<E> &comp) {
        ogdf::quicksortTemplate(*this,comp);
    }

    template<class C>
    void quicksortCT(C &comp) {
        ogdf::quicksortCTTemplate(*this,comp);
    }


    void bucketSort(int l, int h, BucketFunc<E> &f);

    void bucketSort(BucketFunc<E> &f);

    void permute() {
        permute(size());
    }

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

    void permute(const int n);

    OGDF_NEW_DELETE
}; // class SListPure




template<class E>
class SList : private SListPure<E> {

    int m_count; 

public:
    SList() : m_count(0) { }
    
    SList(const SList<E> &L) : SListPure<E>(L), m_count(L.m_count) { }

    // destruction
    ~SList() { }

    typedef E value_type;
    typedef SListElement<E> element_type;
    typedef SListConstIterator<E> const_iterator;
    typedef SListIterator<E> iterator;

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

    int size() const { return m_count; }


    const SListConstIterator<E> begin() const { return SListPure<E>::begin(); }


    SListIterator<E> begin() { return SListPure<E>::begin(); }


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


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


    const SListConstIterator<E> rbegin() const { return SListPure<E>::rbegin(); }


    SListIterator<E> rbegin() { return SListPure<E>::rbegin(); }



    SListConstIterator<E> get(int pos) const {
        return SListPure<E>::get(pos);
    }


    SListIterator<E> get(int pos) {
        return SListPure<E>::get(pos);
    }


    int pos(SListConstIterator<E> it) const {
        return SListPure<E>::pos(it);;
    }

    

    const E &front() const { return SListPure<E>::front(); }


    E &front() { return SListPure<E>::front(); }


    const E &back() const { return SListPure<E>::back(); }


    E &back() { return SListPure<E>::back(); }


    SListConstIterator<E> cyclicSucc(SListConstIterator<E> it) const {
        return SListPure<E>::cyclicSucc(it);
    }


    SListIterator<E> cyclicSucc(SListIterator<E> it) {
        return SListPure<E>::cyclicSucc(it);
    }

    SList<E> &operator=(const SList<E> &L) {
        SListPure<E>::operator=(L);
        m_count = L.m_count;
        return *this;
    }

    SListIterator<E> pushFront(const E &x) {
        ++m_count;
        return SListPure<E>::pushFront(x);
    }

    SListIterator<E> pushBack(const E &x) {
        ++m_count;
        return SListPure<E>::pushBack(x);
    }


    SListIterator<E> insertAfter(const E &x, SListIterator<E> itBefore) {
        ++m_count;
        return SListPure<E>::insertAfter(x, itBefore);
    }


    void popFront() {
        --m_count;
        SListPure<E>::popFront();
    }


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


    void delSucc(SListIterator<E> itBefore) {
        --m_count;
        SListPure<E>::delSucc(itBefore);
    }

    void moveFrontToFront(SList<E> &L2) {
        SListPure<E>::moveFrontToFront(L2);
        --m_count; ++L2.m_count;
    }

    void moveFrontToBack(SList<E> &L2) {
        SListPure<E>::moveFrontToBack(L2);
        --m_count; ++L2.m_count;
    }


    void moveFrontToSucc(SList<E> &L2, SListIterator<E> itBefore) {
        SListPure<E>::moveFrontToSucc(L2,itBefore);
        --m_count; ++L2.m_count;
    }

    void clear() {
        m_count = 0;
        SListPure<E>::clear();
    }

    void conc(SList<E> &L2) {
        SListPure<E>::conc(L2);
        m_count += L2.m_count;
        L2.m_count = 0;
    }

    void reverse() {
        SListPure<E>::reverse();
    }

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

    void quicksort() {
        ogdf::quicksortTemplate(*this);
    }

    void quicksort(Comparer<E> &comp) {
        ogdf::quicksortTemplate(*this,comp);
    }

    template<class C>
    void quicksortCT(C &comp) {
        ogdf::quicksortCTTemplate(*this,comp);
    }


    void bucketSort(int l, int h, BucketFunc<E> &f) {
        SListPure<E>::bucketSort(l,h,f);
    }

    void bucketSort(BucketFunc<E> &f) {
        SListPure<E>::bucketSort(f);
    }

    void permute() {
        SListPure<E>::permute(m_count);
    }

    OGDF_NEW_DELETE
}; // class SList




// sorts list L using bucket sort
// computes l and h value
template<class E>
void SListPure<E>::bucketSort(BucketFunc<E> &f)
{
    // if less than two elements, nothing to do
    if (m_head == m_tail) return;

    int l, h;
    l = h = f.getBucket(m_head->m_x);
    
    SListElement<E> *pX;
    for(pX = m_head->m_next; pX; pX = pX->