MNList.h

Go to the documentation of this file.

/* Copyright (C) 2000 KOM/Darmstadt University of Technology
 *
 * You are allowed to use all other parts of the code under the following terms:
 *
 * For non-commercial use, code may be used in unmodified form provided
 * that this copyright notice and this permission notice appear in
 * supporting documentation.
 *
 * This software is provided "as is" and without any express or implied
 * warranties, including, without limitation, the implied warranty of
 * fitness for a particular purpose.
 *
 * The code may be subjected to the GNU General Public License, Version 2,
 * and re-distributed under the terms of this license.
 * As a special exception, permission is granted to link this code
 * with the Qt library and distribute executables, as long as you
 * follow the requirements of the GNU GPL in regard to all of the
 * software in the executable aside from Qt.
 *
 * Commercial use other than under the terms of the GNU General Public
 * License is allowed only after express negotiation of conditions
 * with the authors.
 */
#ifndef OS_UTIL_MNLIST_H
#define OS_UTIL_MNLIST_H

#include <assert.h>
#include <string.h>

/*
 * We have successfully used the LEDA lists in the recent
 * past. Unfortunately, some of our projects can not make use
 * of this set of tools due to its licensing restrictions.
 * This list is supposed to be one of the drop-on replacements
 * for the most basic uses of LEDA.
 */

#ifdef __cplusplus

#ifndef ASSERT_NON_NULL
#define ASSERT_NON_NULL(a)
#endif

/*************************************************************
 * MNForall_items() macro
 *************************************************************/

template <class T, class M>
inline void* MNForall_assign(T& r, void* p, const M& l) {
    if(p)
    {
        r = l.inf(p);
        ASSERT_NON_NULL(r);
    }
    return p;
}

#define MNForall_items(r,l) \
    for ( r = l.first(); \
          r != NULL; \
          r = l.succ(r) )

#define MNForall_var MNForall_runner##__LINE__

#define MNForall(r,l) \
    for ( void* \
          MNForall_var = MNForall_assign(r,l.first(),l); \
          MNForall_var != NULL; \
          MNForall_var = MNForall_assign(r,l.succ(MNForall_var),l) )

/*************************************************************
 * MNVPListItem
 *
 * This basic Item class can be overridden by the template
 * classes. Its basic functionality remains
 */

class MNVPListItem
{
    MNVPListItem* _succ;
    MNVPListItem* _pred;
public:
    MNVPListItem( );
    virtual ~MNVPListItem() { }

    MNVPListItem* succ() const;
    MNVPListItem* pred() const;
    void setPred( MNVPListItem* pred );
    void setSucc( MNVPListItem* succ );
    void validityCheck();

    virtual MNVPListItem* clone() const = 0;
};

/*************************************************************
 * MNVPList
 *
 * This is a basic list class. Its implementation is
 * template-free and made in a library. This
 * implements a plain double-linked list.
 *************************************************************/

class MNVPList
{
private:
    int           _len;
    MNVPListItem* _first;
    MNVPListItem* _last;

protected:
    void clone ( const MNVPList& orig );

public:
    MNVPList ( const MNVPList& orig );
    MNVPList ( );

    ~MNVPList ( );

    MNVPList& operator=( const MNVPList& orig );

    MNVPListItem* first() const;
    MNVPListItem* last() const;
    MNVPListItem* pred(MNVPListItem* item) const;
    MNVPListItem* succ(MNVPListItem* item) const;
    bool  empty() const;
    int   length() const;

    void  del_item( MNVPListItem* x );
    void  del_back();
    void  del_front();
    void  push_front( MNVPListItem* x );
    void  push_back( MNVPListItem* x );
    void  ins_before ( MNVPListItem* x, MNVPListItem* y );
    void  ins_after ( MNVPListItem* x, MNVPListItem* y );
    void  clear ( );
};

/*************************************************************
 * MNList
 *************************************************************/

template <class T> class MNList
{
    MNVPList l;
private:
    /*********************************************************
     * MNList::Item
     *********************************************************/

    class Item : public MNVPListItem
    {
    public:
        T _data;
        Item(const T& t) : _data(t) {
            ASSERT_NON_NULL ( _data );
        }

        virtual ~Item() { }

        virtual const T* data() const {
            return &_data;
        }

        virtual MNVPListItem* clone() const {
            ASSERT_NON_NULL ( _data );
            return new Item(_data);
        }
    };

public:
    MNList ( const MNList<T>& orig ) : l(orig.l) {
    }
    MNList ( ) {
    }

    ~MNList ( ) { }

    MNList<T>& operator=( const MNList<T>& orig ) {
        l=orig.l;
        return *this;
    }

    inline void* first() const          { return l.first(); }
    inline void* last() const           { return l.last(); }
    inline void* pred(void* item) const { return l.pred((MNVPListItem*)item); }
    inline void* succ(void* item) const { return l.succ((MNVPListItem*)item); }
    inline bool  empty() const          { return l.empty(); }
    inline int   length() const         { return l.length(); }

    inline const T& peek_front() const       { return ((Item*)l.first())->_data; }
    inline T peek_front()                    { return ((Item*)l.first())->_data; }
    inline const T& peek_back() const        { return ((Item*)l.last())->_data; }
    inline T peek_back()                     { return ((Item*)l.last())->_data; }
    inline const T& peek_here(void* r) const { return ((Item*)r)->_data; }

    inline const T& inf(void* r) const {
        assert ( r );
            Item* rc = (Item*)r;
        ASSERT_NON_NULL ( rc->_data );
        // return rc->_data;
        return *(rc->data());
    }
    inline T inf(void* r) {
        assert ( r );
            Item* rc = (Item*)r;
        ASSERT_NON_NULL ( rc->_data );
        // return rc->_data;
        return *(rc->data());
    }
    inline void del_item(void* item)  { l.del_item((MNVPListItem*)item); }
    inline void del_front() { l.del_front(); }
    inline void del_back()  { l.del_back(); }
    inline void clear()     { l.clear(); }

    inline T pop() {
            T ret = peek_front();
            l.del_front();
        ASSERT_NON_NULL ( ret );
            return ret;
    }

    inline void push_front( T x ) {
        ASSERT_NON_NULL ( x );
        l.push_front(new Item(x));
    }
    inline void prepend( T x )    {
        ASSERT_NON_NULL ( x );
        l.push_front(new Item(x));
    }
    inline void push_back( T x )  {
        ASSERT_NON_NULL ( x );
        l.push_back(new Item(x));
    }
    inline void append( T x )     {
        ASSERT_NON_NULL ( x );
        l.push_back(new Item(x));
    }
    inline void ins_before(  void* x, T y )     {
        ASSERT_NON_NULL ( y );
        l.ins_before((MNVPListItem*)x, new Item(y));
    }
    inline void ins_after(  void* x, T y )     {
        ASSERT_NON_NULL ( y );
        l.ins_after((MNVPListItem*)x, new Item(y));
    }
};

#endif /* __cplusplus */

#endif /* OS_UTIL_MNLIST_H */

---