---

List.h

Go to the documentation of this file.

/*
    File:           List.h
    
    Function:       Provides linked list primitives.

    Author(s):      Andrew Willmott

    Copyright:      (c) 1995-2000, Andrew Willmott
 */

#ifndef __List__
#define __List__

#include "cl/Basics.h"


// --- Simple Linked List ---------------------------------------------------


//  A node in the list.

class Node
{
public:
    Node    *next;          // Next item in the list
    
    Node() : next(0) {};

    Void            InsertAfter(Node *node) { node->next = next; next = node;};

    Void            FreeAfter();
    
    virtual Node    *Clone();
    Node            *CloneList();
};


// A list : essentially a (Node *) with associated methods. Imitates 
// Lisp/Prolog lists, in that it has head & tail methods. Has pointer
// semantics: you must call Clone() to copy it, and Free() to delete it. 

class List
{
public:
    Node        *first;     // Pointer to the first node in the list.
    
                List() : first(0) {};
    
    Bool        IsEmpty()   { return first == 0; };
    Node        &Head()     { return *first; };
    List        &Tail()     { return (List &) first->next; };
    
    Void        Prepend(Node *node)
                { node->next = first; first = node; };
    Void        Prepend(List list);
    Void        Append(Node *node);
    Void        Append(List list);
    
    Void        Free();
    List        Clone();

    Void        DeleteFirst()
                { Node *t = first; first = first->next; delete t; }; 
    Node        *DisconnectFirst()
                { Node *t = first; first = first->next; return(t); }; 

    Int         NumItems();
};

template <class T> 
    class TypedList : public List
{
public:
    T               &Head()     { return (T &) *first; };
    TypedList<T>    &Tail()     { return (TypedList<T> &) first->next; };
};

template <class T> ostream &operator << (ostream &s, TypedList<T> list);

//  Associated iterator. 

template <class T> class Iter
{
public:
    List    *cursor;
    
    Void    Begin(List &list)
            { cursor = &list; };
    Void    Inc()                   
            { Assert(!cursor->IsEmpty(), "Moved past end of list");
            cursor = (List *) cursor->first; };
                                            
    Bool    AtEnd()
            { return cursor->first == 0; };
    T       &Data()
            { return (T &) cursor->Head(); };
    
    Void    Delete()
            { cursor->DeleteFirst();};
    Void    InsertBefore(Node *node)
            { cursor->Prepend(node); cursor = (List *) cursor->first;};
    Void    InsertAfter(Node *node)
            { cursor->Tail().Prepend(node);};
};


// --- Doubly-linked list -----------------------------------------------------


class DblNode
{
public:
    DblNode *prev;          // Previous item in the list
    DblNode *next;          // Next item in the list
    
    DblNode() : prev(0), next(0) {};

    Void            InsertAfter(DblNode *node)
                    { 
                        node->next = next; 
                        node->prev = this; 
                        if (next) next->prev = node; 
                        next = node; 
                    };
    Void            InsertBefore(DblNode *node)
                    { 
                        node->next = this; 
                        node->prev = prev;
                        if (prev) prev->next = node; 
                        prev = node;
                    };
    Void            Delete()
                    { delete Disconnect(); };
    DblNode         *Disconnect()
                    { 
                        if (prev) prev->next = next; 
                        if (next) next->prev = prev; 
                        return(this);
                    };
    
    Bool            AtStart()       { return(prev == 0); };
    Bool            AtEnd()         { return(next == 0); };

    Void            FreeAfter();
    Void            FreeBefore();
    Void            FreeList()      { FreeAfter(); FreeBefore(); delete this; }
    
    virtual DblNode *Clone()        { return new DblNode(SELF); };
    
    DblNode         *CloneAfter();
    DblNode         *CloneBefore();
    DblNode         *CloneList();
};

// Associated iterator

template <class T> class DblIter
{
public:
    DblNode *cursor;
    
    Void    Begin(DblNode *list)    { cursor = list; };
    Void    Inc()
            { Assert(!cursor->AtEnd(), "Moved past end of list");
            cursor = cursor->next; };
    Void    Dec()
            { Assert(!cursor->AtStart(), "Moved past end of list");
            cursor = cursor->prev; };
                                            
    Bool    AtEnd()                 { return cursor == 0; };
    
    T       &Data()                 { return (T &) *cursor; };
    
    Void    Delete()
            { DblNode *t = cursor; cursor->Delete(); cursor = t;};
    Void    InsertBefore(DblNode *node)
            { cursor->InsertBefore(node); };
    Void    InsertAfter(DblNode *node)
            { cursor->InsertAfter(node); };
};


// --- Templated functions ----------------------------------------------------

template <class T> 
    ostream &operator << (ostream &s, TypedList<T> list)
{
    s << "(";
    
    if (!list.IsEmpty())
    {
        s << list.Head();
        list = list.Tail();

        while (!list.IsEmpty())
        {
            s << " " << list.Head();
            list = list.Tail();
        }
    }
        
    s << ")";
    return(s);
};


#endif

---