coDLList.h

Go to the documentation of this file.

/* This file is part of COVISE.

   You can use it under the terms of the GNU Lesser General Public License
   version 2.1 or later, see lgpl-2.1.txt.

 * License: LGPL 2+ */

#ifndef _YAC_DL_LIST_H
#define _YAC_DL_LIST_H

// this is needed for NULL
#include <stddef.h>
#include <list>

// some need this for bool type
#include "coExport.h"
#include "coErr.h"

//    ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
//   ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
//  ++                                                                      ++
// ++                                                                        ++
// ++ Description: Double-Linked list class                                  ++
// ++                                                                        ++
// ++   class coDLListElem<T>  Element of type T  + prev/next pointer        ++
// ++   class coDLList<T>      List of Elements of type T                    ++
// ++   class coDLListIter<T>  Iterator working on coDLList                  ++
// ++   class coDLPtrList<T>   List of T elements, which can be deleted on   ++
// ++                          remove: MUST BE POINTERS !!!!!                ++
// ++                                                                        ++
// ++                             (C)1999 RUS                                ++
// ++                Computing Center University of Stuttgart                ++
// ++                            Allmandring 30                              ++
// ++                            70550 Stuttgart                             ++
// ++    Author: A. Werner                                                   ++
//  ++   Date:  15.08.97  V1.0                                              ++
//   ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
//    ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
namespace covise
{

template <class T>
class coDLListIter;

template <class T>
class coDLListSafeIter;

#ifndef INLINE
#define INLINE inline
#endif

/* struct needed to link items together
 * @author Andreas Werner
 */
template <class T>
struct coDLListElem
{
    // the data
    T item;

    // pointer to previous and next element
    coDLListElem<T> *prev, *next;

    // constructor with given data element
    coDLListElem(const T &data)
    {
        item = data;
        prev = next = NULL;
    }
};

template <class T>
class coDLListCompare
{
public:
    virtual ~coDLListCompare()
    {
    }
    virtual bool equal(const T &op1, const T &op2) const
    {
        return op1 == op2;
    }
};

// +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
// +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
// ++++++
// ++++++    class coDLList<T>
// ++++++
// +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
// +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

template <class T>
class coDLList
{
    friend class coDLListIter<T>;
    friend class coDLListSafeIter<T>;

protected:
    // the this->head and this->tail of the list
    coDLListElem<T> *head, *tail;

    // number of items in list
    int listItems;

    // for "safe" iterators
    std::list<coDLListSafeIter<T> *> m_iterators;

    void addIter(coDLListSafeIter<T> *iter)
    {
        m_iterators.push_back(iter);
    }

    void removeIter(coDLListSafeIter<T> *iter)
    {
        if (m_iterators.empty())
            return;
        m_iterators.remove(iter);
    }

    void invalidateIterators(void)
    {
        if (m_iterators.empty())
            return;
        typename std::list<coDLListSafeIter<T> *>::iterator iter;
        LOGWARNING("Invalidating iterators !!! (%d iterators attached)", m_iterators.size());
        for (iter = m_iterators.begin(); iter != m_iterators.end(); iter++)
        {
            (*iter)->d_actElem = NULL;
        }
    }

    void correctIteratorsFor(coDLListElem<T> *whichElem)
    {
        if (m_iterators.empty())
            return;
        typename std::list<coDLListSafeIter<T> *>::iterator iter;
        for (iter = m_iterators.begin(); iter != m_iterators.end(); iter++)
        {
            if ((*iter)->d_actElem == whichElem)
            {
                if (m_iterators.size() > 1) // no warning if there is only one iterator
                {
                    LOGWARNING("Adjusting iterators in list 0x%x!", this);
                }
                (*iter)->backstep();
            }
        }
    }

public:
    coDLList(void);

    virtual ~coDLList(void);

    // +++++++++++++ status query functions ++++++++++++++++++++++++++++++++++

    int num(void) const
    {
        return this->listItems;
    }

    operator bool()
    {
        return (this->listItems != 0);
    }

    // +++++++++++++ adding or removing items from the list ++++++++++++++++++

    virtual void remove(coDLListElem<T> *whichElem);

    coDLList<T> &append(const T &);

    // +++++++++++++ access list +++++++++++++++++++++++++++++++++++++++++++++

    T item(int); // USE  BRACKET OPERATOR !!!!!

    T &operator[](int);

    const T &operator[](int) const;

    virtual void clean();

    // +++++++++++++ iterator routines ++++++++++++++++++++++++++++++++++++++

    coDLListIter<T> first();

    coDLListIter<T> last();

    coDLListIter<T> findElem(const T &);

    coDLListIter<T> findElem(const T &, const coDLListCompare<T> &comp);

    coDLListIter<T> findElem(int i);

    // +++++++++++++ access internal pointers ++++++++++++++++++++++++++++++++

    coDLListElem<T> *getHeadStruct()
    {
        return this->head;
    }

    coDLListElem<T> *getTailStruct()
    {
        return this->tail;
    }
};

// +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
// +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
// ++++++
// ++++++    class coDLPtrList<T> : public coDLList<T*>
// ++++++
// +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
// +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

template <class T>
class coDLPtrList : public coDLList<T>
{
private:
    bool d_doDelete;

    // 'current' element -> for old-style list access : only for Pointer Lists
    coDLListElem<T> *curr;

    // NULL element : needed for old-style calls as "empty" return value
    T d_nullElem;

public:
    coDLPtrList(bool doDelete = true)
        : coDLList<T>()
    {
        d_doDelete = doDelete;
        d_nullElem = NULL;
        curr = NULL;
    }

    void setNullElem(const T &nullElem)
    {
        d_nullElem = nullElem;
    }

    void setNoDelete(bool doDelete = false)
    {
        d_doDelete = doDelete;
    }

    virtual void remove(coDLListElem<T> *whichElem);

    virtual void clean();

    virtual ~coDLPtrList()
    {
        coDLListElem<T> *elem = this->head;
        while (elem)
        {
            coDLListElem<T> *nextElem;
            nextElem = elem->next;
            if (d_doDelete)
            {
                delete elem->item;
            }
            elem = nextElem;
        }
    };

    coDLPtrList<T> &append(const T &a);

    // +++++++++++++ obsolete old-time stuff - do not use ++++++++++++++++++++

    void remove()
    {
        LOGWARNING("coDLPtrList::remove(void) called in 0x%x ! This method is obsolete !!!", this);
        if (curr)
        {
            coDLListElem<T> *oldCurr = curr;
            curr = curr->next;
            remove(oldCurr);
        }
    }

    T current(void);

    //T getLast(void);

    T get(void)
    {
        T retval = current();
        next();
        return retval;
    }

    coDLPtrList<T> &set(int);

    int find(const T &);

    coDLList<T> &reset(void)
    {
        if (this->head)
            curr = this->head;
        else
            curr = NULL;
        return *this;
    }

    coDLList<T> &next(void)
    {
        if (curr)
            curr = curr->next;
        return *this;
    }

    /***
      coDLList<T>& prev(void)
      {
         if (curr)
            curr = curr->prev;
         return *this;
      }

      coDLList<T>& clear(void)
      {
         curr = (coDLListElem<T> *)0;
         return *this;
      }

      int is_current(void)
      {
         return (curr != ((coDLListElem<T> *)0));
      }
      ***/
};

// +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
// +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
// ++++++
// ++++++    class coDLListIter<T>
// ++++++
// +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
// +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

template <class T>
class coDLListIter
{
protected:
    // the list we are running on
    coDLList<T> *d_myList;

    // my active element
    coDLListElem<T> *d_actElem;

    // this might be overridden by derived class for selective Iterators

    // advance pointer by one element
    virtual void advance()
    {
        if (d_actElem)
            d_actElem = d_actElem->next;
    }

    // step back one step
    virtual void backstep()
    {
        if (d_actElem)
            d_actElem = d_actElem->prev;
    }

    // forward to next valid element if current is not valid
    virtual void nextValid(){};

    // forward to prev valid element if current is not valid
    virtual void prevValid(){};

public:
    coDLListIter<T>()
    {
        d_myList = NULL;
        d_actElem = NULL;
    }

    coDLListIter<T>(coDLList<T> &list)
    {
        d_myList = &list;
        d_actElem = list.head;
        nextValid();
    }

    coDLListIter<T> &operator=(const coDLListIter<T> &old)
    {
        d_myList = old.d_myList;
        d_actElem = old.d_actElem;
        nextValid();
        return *this;
    }

    coDLListIter<T>(const coDLListIter<T> &old)
    {
        d_myList = old.d_myList;
        d_actElem = old.d_actElem;
        nextValid();
    }

    coDLListIter<T>(coDLList<T> &list, coDLListElem<T> *actElem)
    {
        d_myList = &list;
        d_actElem = actElem;
        nextValid();
    }

    virtual ~coDLListIter(){};

    operator bool()
    {
        return (d_actElem != NULL);
    }

    void operator++()
    {
        advance();
    }

    void operator++(int)
    {
        advance();
    }

    void operator--()
    {
        backstep();
    }

    void operator--(int)
    {
        backstep();
    }

    T &operator()()
    {
        T *res;
        if (d_actElem)
            res = &(d_actElem->item);
        else
        {
            static T dummy;
            res = &dummy;
            LOGWARNING("!!!! Accessing dummy-elem with: T &coDLListIter<T>::operator(); !!!!");
        }
        return *res;
    }

    T &operator*()
    {
        T *res;
        if (d_actElem)
            res = &(d_actElem->item);
        else
        {
            static T dummy;
            res = &dummy;
            LOGWARNING("!!!! Accessing dummy-elem with: T &coDLListIter<T>::operator*(); !!!!");
        }
        return *res;
    }

    T operator->()
    {
        T *res;
        if (d_actElem)
            res = &(d_actElem->item);
        else
        {
            static T dummy;
            res = &dummy;
            LOGWARNING("!!!! Accessing dummy-elem with: T coDLListIter<T>::operator->(); !!!!");
        }
        return *res;
    }

    void setFirst()
    {
        if (d_myList)
        {
            d_actElem = d_myList->head;
            nextValid();
        }
    }

    void setLast()
    {
        if (d_myList)
        {
            d_actElem = d_myList->tail;
            prevValid();
        }
    }

    coDLListIter<T> &insertAfter(const T &newElem);

    coDLListIter<T> &insertBefore(const T &newElem);

    virtual void remove()
    {
        if (d_actElem)
        {
            coDLListElem<T> *newNext = d_actElem->next;
            d_myList->remove(d_actElem);
            d_actElem = newNext;
            nextValid();
        }
    }

    void operator=(const T &elem)
    {
        if (d_myList)
        {
            d_actElem = d_myList->head;
            nextValid();
            while ((d_actElem) && !(d_actElem->item == elem))
                advance();
        }
    }

    void operator=(int num)
    {
        if (d_myList)
        {
            d_actElem = d_myList->head;
            nextValid();
            while ((d_actElem) && (num))
            {
                advance();
                num--;
            }
        }
    }
};

// +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
// +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
// ++++++
// ++++++    class coDLListSafeIter<T>
// ++++++
// +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
// +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

template <class T>
class coDLListSafeIter : public coDLListIter<T>
{
    friend class coDLList<T>;

public:
    coDLListSafeIter<T>()
        : coDLListIter<T>()
    {
    }

    coDLListSafeIter<T>(coDLList<T> &list)
        : coDLListIter<T>(list)
    {
        this->d_myList->addIter(this);
    }

    coDLListSafeIter<T> &operator=(const coDLListSafeIter<T> &old)
    {
        this->d_myList = old.d_myList;
        this->d_actElem = old.d_actElem;
        this->nextValid();
        this->d_myList->addIter(this);
        return *this;
    }

    coDLListSafeIter<T>(const coDLListSafeIter<T> &old)
        : coDLListIter<T>(old)
    {
        //this->d_myList = old.d_myList;
        //this->d_actElem = old.d_actElem;
        //this->nextValid();
        this->d_myList->addIter(this);
    }

    coDLListSafeIter<T>(coDLList<T> &list, coDLListElem<T> *actElem)
    {
        this->d_myList = &list;
        this->d_actElem = actElem;
        this->nextValid();
        this->d_myList->addIter(this);
    }

    virtual ~coDLListSafeIter()
    {
        this->d_myList->removeIter(this);
    }

    virtual void remove()
    {
        if (this->d_actElem)
        {
            this->d_myList->remove(this->d_actElem);
            this->nextValid();
        }
    }
};

// -------------- End coDLListSafeIter ------------------------------

//==========================================================================
// INLINE implementation of coDLList member functions
//==========================================================================

template <class T>
INLINE coDLListIter<T> coDLList<T>::first()
{
    return coDLListIter<T>(*this, this->head);
}

template <class T>
INLINE coDLListIter<T> coDLList<T>::last()
{
    return coDLListIter<T>(*this, this->tail);
}

template <class T>
INLINE coDLList<T>::coDLList(void)
{
    this->head = this->tail = NULL;
    this->listItems = 0;
}

template <class T>
INLINE coDLListIter<T> coDLList<T>::findElem(const T &searchItem)
{
    coDLListIter<T> iter(*this, this->head);
    while ((iter) && !((*iter) == searchItem))
    {
        iter++;
    }
    return iter;
}

template <class T>
INLINE coDLListIter<T> coDLList<T>::findElem(const T &searchItem,
                                             const coDLListCompare<T> &comp)
{
    coDLListIter<T> iter(*this, this->head);
    while ((iter) && !comp.equal((*iter), searchItem))
    {
        iter++;
    }
    return iter;
}

template <class T>
INLINE coDLListIter<T> coDLList<T>::findElem(int idx)
{
    coDLListIter<T> iter(*this, this->head);
    while ((iter) && (idx))
    {
        iter++;
        idx--;
    }
    return iter;
}

//==========================================================================
// Destructor: cleanup everything, but NO things pointered on
//==========================================================================
template <class T>
INLINE coDLList<T>::~coDLList(void)
{
    clean();
}

//==========================================================================
// Cleanup: cleanup everything, but NO things pointered on
//==========================================================================
template <class T>
INLINE void coDLList<T>::clean(void)
{
    coDLListElem<T> *curr = this->head;
    while (curr)
    {
        this->head = curr;
        curr = curr->next;
        delete this->head;
    }
    this->head = this->tail = curr = NULL;
    this->listItems = 0;
    invalidateIterators();
}

//==========================================================================
// Cleanup: cleanup everything, dependend on d_doDelete delete things pointered on
//==========================================================================
template <class T>
INLINE void coDLPtrList<T>::clean(void)
{
    coDLListElem<T> *cur = this->head;
    while (cur)
    {
        this->head = cur;
        cur = cur->next;
        if (d_doDelete)
            delete this->head->item;
        delete this->head;
    }
    this->head = this->tail = cur = NULL;
    this->listItems = 0;
    this->invalidateIterators();
}

//==========================================================================
// add new item to end of list
//==========================================================================
template <class T>
INLINE coDLList<T> &coDLList<T>::append(const T &a)
{
    coDLListElem<T> *newlink = new coDLListElem<T>(a);
    newlink->next = NULL;
    newlink->prev = this->tail;
    this->tail = newlink;
    if (newlink->prev)
        (newlink->prev)->next = newlink;
    else
        this->head = newlink;
    this->listItems++;
    return *this;
}

//==========================================================================
// add new item to end of list
//==========================================================================
template <class T>
INLINE coDLPtrList<T> &coDLPtrList<T>::append(const T &a)
{
    coDLListElem<T> *newlink = new coDLListElem<T>(a);
    newlink->next = NULL;
    newlink->prev = this->tail;
    this->tail = newlink;
    if (newlink->prev)
        (newlink->prev)->next = newlink;
    else
        this->head = curr = newlink;
    this->listItems++;
    return *this;
}

//==========================================================================
//  remove specific item from list
//==========================================================================
template <class T>
INLINE void coDLList<T>::remove(coDLListElem<T> *removeElem)
{
    if (removeElem)
    {
        this->correctIteratorsFor(removeElem);
        if (removeElem->prev)
            (removeElem->prev)->next = removeElem->next;
        if (removeElem->next)
            (removeElem->next)->prev = removeElem->prev;
        if (this->head == removeElem)
            this->head = removeElem->next;
        if (this->tail == removeElem)
            this->tail = removeElem->prev;
        delete removeElem;
        this->listItems--;
    }
}

//==========================================================================
//  remove specific item from list : PTR version
//==========================================================================
template <class T>
INLINE void coDLPtrList<T>::remove(coDLListElem<T> *removeElem)
{
    if (removeElem)
    {
        this->correctIteratorsFor(removeElem);
        if (d_doDelete)
            delete removeElem->item;
        if (removeElem->prev)
            (removeElem->prev)->next = removeElem->next;
        if (removeElem->next)
            (removeElem->next)->prev = removeElem->prev;
        if (this->head == removeElem)
            this->head = removeElem->next;
        if (this->tail == removeElem)
            this->tail = removeElem->prev;
        delete removeElem;
        this->listItems--;
    }
}

//==========================================================================
// return the Nth item; do not change current item position : CONST
//==========================================================================
template <class T>
INLINE const T &coDLList<T>::operator[](int n) const
{
    coDLListElem<T> *link = this->head;
    while (link && n > 0)
    {
        link = link->next;
        n--;
    }
    if (link && n == 0)
        return link->item;
    else
        return this->head->item; // problem if NO items in list
}

//==========================================================================
// return the Nth item; do not change current item position
//==========================================================================
template <class T>
INLINE T &coDLList<T>::operator[](int n)
{
    coDLListElem<T> *link = this->head;
    while (link && n > 0)
    {
        link = link->next;
        n--;
    }
    if (link && n == 0)
        return link->item;
    else
        return this->head->item; // problem if NO items in list
}

//==========================================================================
// return the Nth item; do not change current item position
//==========================================================================
template <class T>
INLINE T coDLList<T>::item(int n)
{
    coDLListElem<T> *link = this->head;
    while (link && n > 0)
    {
        link = link->next;
        n--;
    }
    if (link && n == 0)
        return link->item;
    else
        return this->head->item; // problem if NO items in list
}

//==========================================================================
// just return the current item, do not change which item is current
//==========================================================================
template <class T>
INLINE T coDLPtrList<T>::current(void)
{
    coDLListElem<T> *link = curr;
    if (!link)
    {
        reset();
        return d_nullElem;
    }
    return link->item;
}

//==========================================================================
// just return the current item, do not change which item is current
//==========================================================================
//template<class T>
//INLINE T coDLList<T>::getLast(void)
//{
//  coDLListElem<T> *link = this->tail;
//  if(!link) {
//    reset();
//    return(NULL);
//  }
//  return link->item;
//}

//==========================================================================
// move the current item pointer to the Nth item
//==========================================================================
template <class T>
INLINE coDLPtrList<T> &coDLPtrList<T>::set(int N)
{
    reset();
    for (int i = 0; i < N; i++)
        next();
    return *this;
}

//==========================================================================
// move the current item pointer to the item which matches the given one
// return TRUE if found, or FALSE otherwise
//==========================================================================
template <class T>
INLINE int coDLPtrList<T>::find(const T &a)
{
    reset();
    while (curr && !(curr->item == a))
        next();
    return (curr != NULL);
}

// +++++++++++++++++ coDLListIter ++++++++++++++++++++++++++++++++++++++++++

//==========================================================================
//  append new item after the current item : Iterator version
//==========================================================================
template <class T>
INLINE coDLListIter<T> &coDLListIter<T>::insertAfter(const T &a)
{
    if (d_actElem)
    { // yes, there is a current item
        coDLListElem<T> *newlink = new coDLListElem<T>(a);
        newlink->next = d_actElem->next;
        newlink->prev = d_actElem;
        d_actElem->next = newlink;
        if (newlink->next == NULL)
            d_myList->tail = newlink;
        else
            newlink->next->prev = newlink;
        d_myList->listItems++;
    }
    else // no current item; just append at end
        d_myList->append(a);

    return *this;
}

//==========================================================================
//  append new item before the current item : Iterator version
//==========================================================================
template <class T>
INLINE coDLListIter<T> &coDLListIter<T>::insertBefore(const T &a)
{
    if (d_actElem)
    { // yes, there is a current item
        coDLListElem<T> *newlink = new coDLListElem<T>(a);
        newlink->next = d_actElem;
        newlink->prev = d_actElem->prev;
        d_actElem->prev = newlink;
        if (newlink->prev == NULL)
            d_myList->head = newlink;
        else
            newlink->prev->next = newlink;
        d_myList->listItems++;
    }
    else // no current item; just append at end
        d_myList->append(a);

    return *this;
}
}
#endif //YAC_LINK_LIST_H