SList.h

Go to the documentation of this file.

/*
 * $Revision: 2615 $
 *
 * last checkin:
 *   $Author: gutwenger $
 *   $Date: 2012-07-16 14:23:36 +0200 (Mo, 16. Jul 2012) $
 ***************************************************************/

#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();
        }
        OGDF_ALLOCATOR::deallocateList(sizeof(SListElement<E>),m_head,m_tail);

#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;
        }
        swap(m_head,m_tail);
    }

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

    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 bucketSort(BucketFunc<E> &f);

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

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

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

    template<class COMPARER>
    void quicksort(const COMPARER &comp) {
        ogdf::quicksortTemplate(*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);
    }

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

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

    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->m_next)
    {
        int i = f.getBucket(pX->m_x);
        if (i < l) l = i;
        if (i > h) h = i;
    }

    bucketSort(l,h,f);
}


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

    Array<SListElement<E> *> head(l,h,0), tail(l,h);

    SListElement<E> *pX;
    for (pX = m_head; pX; pX = pX->m_next) {
        int i = f.getBucket(pX->m_x);
        if (head[i])
            tail[i] = (tail[i]->m_next = pX);
        else
            head[i] = tail[i] = pX;
    }

    SListElement<E> *pY = 0;
    for (int i = l; i <= h; i++) {
        pX = head[i];
        if (pX) {
            if (pY)
                pY->m_next = pX;
            else
                m_head = pX;
            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 SListPure<E>::permute(const int n)
{
    Array<SListElement<E> *> A(n+1);
    A[n] = 0;

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

    A.permute(0,n-1);

    for (i = 0; i < n; i++) {
        A[i]->m_next = A[i+1];
    }

    m_head = A[0];
    m_tail = A[n-1];
}

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

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

// output operator
template<class E>
ostream &operator<<(ostream &os, const SListPure<E> &L)
{
    print(os,L);
    return os;
}

template<class E>
ostream &operator<<(ostream &os, const SList<E> &L)
{
    return operator<<(os,L.getListPure());
}


// sort array using bucket sort and bucket object f;
// the values of f must be in the interval [min,max]
template<class E>
void bucketSort(Array<E> &a, int min, int max, BucketFunc<E> &f)
{
    if (a.low() >= a.high()) return;

    Array<SListPure<E> > bucket(min,max);

    int i;
    for(i = a.low(); i <= a.high(); ++i)
        bucket[f.getBucket(a[i])].pushBack(a[i]);

    i = a.low();
    for(int j = min; j <= max; ++j) {
        SListConstIterator<E> it = bucket[j].begin();
        for(; it.valid(); ++it)
            a[i++] = *it;
    }
}




} // namespace ogdf


#endif