Computer Panoráma/computer_panorama_1997-12-hibas.iso/SHARE/GRAPH/PTC051.ZIP/SRC/LIST.H

C/C++ Source or Header | 1997-09-20 | 6KB | 341 lines

////////////////////////
// simple linked list //
////////////////////////

#ifndef __LIST_H
#define __LIST_H

#include "misc.h"







template <class T> class List
{
    // friend class
    friend class Iterator<T>;

    public:

        // setup
        List();
        ~List();

        // management
        inline int add(T const &object);
        inline int add(T *object);
        //inline int insert(T *object,int position);
        inline int replace(T *object,T *replacement);
        inline int remove(T *object);
        inline void remove();
        inline int free(T *object);
        inline void free();

        // list merger
        inline void merge(List<T> &other);

        // node access
        inline T* head() const;
        inline T* tail() const;

        // information
        inline int size() const;

        // operators
        inline void operator =(List<T> &other);

    private:

        // node structure
        struct NODE
        {
            T *object;
            NODE *next;
            NODE *prev;
        };

        // nodes
        NODE Root;
};








// iterator
#include "iterator.h"









template <class T> List<T>::List()
{
    // initialize root node
    Root.next=&Root;
    Root.prev=&Root;
    Root.object=NULL;
}


template <class T> List<T>::~List()
{
    // free list
    free();
}









template <class T> inline int List<T>::add(T const &object)
{
    // alloc object
    T *store=new T;
    if (!store) return 0;

    // assign
    *store=object;

    // add to list
    if (!add(store))
    {
        delete store;
        return 0 ;
    }
    else return 1;
}


template <class T> inline int List<T>::add(T *object)
{
    // fail on null object
    if (object==NULL) return 0;

    // create node
    NODE *node=new NODE;
    if (!node) return 0;
    node->object=object;

    // add at tail
    node->prev=Root.prev;
    node->next=&Root;
    Root.prev->next=node;
    Root.prev=node;
    return 1;
}


template <class T> inline int List<T>::replace(T *object,T *replacement)
{
    // seach through list for matching object
    NODE *node=Root.next;
    while (node->object)
    {
        // check for match
        if (node->object==object)
        {
            // delete object
            delete node->object;

            // replace it
            node->object=replacement;
            return 1;
        }

        // move to next node
        node=node->next;
    }

    // no match
    return 0;
}


template <class T> inline int List<T>::remove(T *object)
{
    // seach through list for matching object
    NODE *node=Root.next;
    while (node->object)
    {
        // check for match
        if (node->object==object)
        {
            // remove from list
            node->prev->next=node->next;
            node->next->prev=node->prev;

            // delete node
            delete node;
            return 1;
        }

        // move to next node
        node=node->next;
    }

    // no match
    return 0;
}


template <class T> inline void List<T>::remove()
{
    // remove all list nodes
    NODE *node=Root.next;
    while (node->object)
    {
        NODE *old=node;
        node=node->next;
        delete old;
    }

    // reset list
    Root.next=&Root;
    Root.prev=&Root;
}


template <class T> inline int List<T>::free(T *object)
{
    // remove the object from list
    if (!remove(object)) return 0;

    // delete the object
    delete object;
    return 1;
}


template <class T> inline void List<T>::free()
{
    // free all list nodes
    NODE *node=Root.next;
    while (node->object)
    {
        NODE *old=node;
        node=node->next;
        delete old->object;
        delete old;
    }

    // clear list nodes
    Root.next=&Root;
    Root.prev=&Root;
}








template <class T> inline void List<T>::merge(List<T> &other)            // rename to add(list) ?
{
    // merge items another list with this list
    Iterator<T> iterator(other);
    T *object=iterator.current();
    while (object)
    {
        add(object);
        object=iterator.next();
    }

    // remove all items from other list
    other.remove();
}







template <class T> inline T* List<T>::head() const
{
    // return head object
    return Root.next->object;
}


template <class T> inline T* List<T>::tail() const
{
    // return tail object
    return Root.prev->object;
}







template <class T> inline int List<T>::size() const
{
    // return the number of objects stored in the list
    int count=0;
    NODE *node=Root.next;
    while (node->object)
    {
        node=node->next;
        count++;
    }
    return count;
}







template <class T> inline void List<T>::operator =(List<T> &other)
{
    // free list
    free();

    // add items from other list to this list
    Iterator<T> iterator(other);
    T *current=iterator.current();
    while (current)
    {
        // copy to this list
        T *copy=new T;
        if (copy)
        {
            *copy=*current;
            add(copy);
        }

        // move to next item
        current=iterator.next();
    }
}











#endif