---

List.cc

Go to the documentation of this file.

/*
    File:           List.cc

    Function:       See header file

    Author(s):      Andrew Willmott

    Copyright:      (c) 1995-2000, A. Willmott

    Notes:          
*/

#include "cl/List.h"
#include <iostream.h>


// --- Simple linked list methods ---------------------------------------------

Void List::Prepend(List list)
{
    list.Append(SELF);
    first = list.first;
}

Void List::Append(List list)
{
    if (list.first != 0)
    { 
        // this is just an unrolled version of: 
        // if (isEmpty) SELF = list; else tail.Append(list);
        if (IsEmpty())
            SELF = list;
        else
        {
            List t;
            for(t = SELF; !t.Tail().IsEmpty(); t = t.Tail())
                ;
            t.Tail() = list;
        }
    }
}

Void List::Append(Node *node)
{
    List t;
    t.first = node;
    node->next = 0;
    Append(t);
}

Void List::Free()
{
    if (first)
    {
        first->FreeAfter();
        delete first;
        first = 0;
    }
}

List List::Clone()
{
    List result;

    result.first = first->CloneList();
    
    return(result);
}

Int List::NumItems()
// ain't recursion wonderful
{
    if (IsEmpty())
        return(0);
    else
        return(1 + Tail().NumItems());
}

// --- single-link Node methods -----------------------------------------------


Node *Node::Clone() 
{
    return(new Node(SELF));
}

Node *Node::CloneList()         
{
    Node *t = Clone();
    
    if (next)
        t->next = next->CloneList();
    else
        t->next = 0;
        
    return(t);
};

Void Node::FreeAfter()
{
    if (next)
    {
        next->FreeAfter();
        delete next;
        next = 0;
    }
}
       

// --- Double-link node methods -----------------------------------------------


DblNode *DblNode::CloneAfter() 
{
    if (!next) return(next);
    
    DblNode *result = next->Clone();
    
    result->next = next->CloneAfter();
    result->next->prev = result;
    
    return(result);
}
        
DblNode *DblNode::CloneBefore() 
{
    if (!prev) return(prev);
    
    DblNode *result = prev->Clone();
    
    result->prev = prev->CloneBefore();
    result->prev->next = result;
    
    return(result);
}
        
DblNode *DblNode::CloneList()
{
    DblNode *result = Clone();
    
    result->next = CloneAfter();
    result->prev = CloneBefore();
    
    return(result);
}

Void DblNode::FreeAfter() 
{
    next->FreeAfter();
    delete next;
}
        
Void DblNode::FreeBefore() 
{
    prev->FreeBefore();
    delete prev;
}
        

// --- Test code --------------------------------------------------------------


#ifdef TEST

class iNode : public Node
{
public:
    iNode(int i) : data(i), Node() {};
    iNode() : Node() {};
    int data;
    Node *Clone() {return(new iNode(data));};
};

class iDNode : public DblNode
{
public:
    iDNode(int i) : data(i), DblNode() {};
    iDNode() : DblNode() {};
    int data;
    DblNode *Clone() {return(new iDNode(data));};
};

ostream &operator << (ostream &s, iNode &i)
{
    s << i.data;
    return(s);
}

class fNode : public Node
{
public:
    fNode(float i) : data(i), Node() {};
    fNode() : Node() {};
    float data;
    Node *Clone() {return(new fNode(data));};
};

ostream &operator << (ostream &s, fNode &i)
{
    s << i.data;
    return(s);
}

Void ListTest()
{
    TypedList<iNode>    myList;
    TypedList<iNode>    t;
    TypedList<fNode>    myFList;
    Iter<iNode>         iter;
    Iter<fNode>         fIter;
    
    myList.Prepend(new iNode(1));
    myList.Prepend(new iNode(2));
    myList.Prepend(new iNode(3));
    myList.Prepend(new iNode(4));
    myList.Prepend(new iNode(5));
        
    cout << myList << endl;
        
    myList.DeleteFirst();
    myList.Tail().Tail().DeleteFirst();
        
    cout << "0: " << myList << endl;
    
    iter.Begin(myList);
    iter.Inc();
    iter.InsertAfter(new iNode(33));

    cout << "1: " << myList << endl;
    
    iter.Inc();
    iter.Delete();

    cout << "2: " << myList << endl;

    iter.InsertBefore(new iNode(-3));

    cout << "3: " << myList << endl;

    // cloning etc.
    
    TypedList<iNode> list2;
    
    list2.Prepend(myList.Clone());
    cout << "b: " << list2 << endl;
    list2.Append(myList.DisconnectFirst()); 

    cout << "a: " << myList << endl;
    cout << "b: " << list2 << endl;
    
    // polymorphic list

    myFList.Prepend((TypedList<fNode> &) myList);
    myFList.Append(new fNode(1));
    myFList.Append(new fNode(2));
    myFList.Append(new fNode(3));
    myFList.Append(new fNode(4));
    myFList.Append(new fNode(5));
        
    int i = 0;
    
    for (fIter.Begin(myFList); !fIter.AtEnd(); fIter.Inc(), i++)
        if (i < 3)
            cout << ((iNode &) fIter.Data()).data << endl;
        else
            cout << fIter.Data() << endl;
}

Void DblListTest()
{
    iDNode *list, *list2;
    DblIter<iDNode> i;
    
    list = new iDNode(20);
    i.Begin(list);
    list->InsertAfter(new iDNode(24));
    list->InsertAfter(new iDNode(23));
    list->InsertAfter(new iDNode(22));
    list->InsertAfter(new iDNode(21));
    i.Inc();
    i.Inc();
    i.Inc();
    i.Inc();
    i.Data().InsertAfter(new iDNode(30));
    i.Inc();
    i.Data().InsertAfter(new iDNode(31));
    i.Inc();
    i.Data().InsertAfter(new iDNode(32));
    i.Inc();
    list2 = (iDNode *) &i.Data();
    
    for (i.Begin(list); !i.AtEnd(); i.Inc())
        cout << i.Data().data << endl;
        
    cout << "--------------" << endl;
    
    for (i.Begin(list2); !i.AtEnd(); i.Dec())
        cout << i.Data().data << endl;
    
    list2 = (iDNode *) list->next->next->CloneList();

    for (i.Begin(list); !i.AtEnd(); i.Inc())
        i.Data().data += 10;

    cout << "--------------" << endl;

    for (i.Begin(list2); !i.AtEnd(); i.Inc())
        cout << i.Data().data << endl;
        
    cout << "--------------" << endl;
    
    for (i.Begin(list2); !i.AtEnd(); i.Dec())
        cout << i.Data().data << endl;
    
    
}

int main(int argc, char **argv)
{
    ListTest();
    return(0);
}
#endif

---