_C PROGRAMMING COLUMN_
by Al Stevens

[LISTING ONE]

// ------------ emblist.h
// a linked list class embedded in the listed class

#ifndef EMBLIST_H
#define EMBLIST_H

class LinkedList;

// --- the linked list entry
class ListEntry    {
    void *thisentry;
    ListEntry *nextentry;
    ListEntry *preventry;
    LinkedList *listhead;
    friend class LinkedList;
public:
    ListEntry(void *entry, LinkedList *lh = 0);
    ~ListEntry() { RemoveEntry(); }
    void AppendEntry(LinkedList *lh = 0);
    void RemoveEntry();
    void *NextEntry()
        { return nextentry ? nextentry->thisentry : 0; }
    void *PrevEntry()
        { return preventry ? preventry->thisentry : 0; }
};
// ---- the linked list
class LinkedList    {
    // --- the listhead
    ListEntry *firstentry;
    ListEntry *lastentry;
    friend class ListEntry;
public:
    LinkedList();
    ~LinkedList();
    void *FirstEntry() { return firstentry->thisentry; }
    void *LastEntry()  { return lastentry->thisentry; }
};
#endif


[LISTING TWO]

// ------------ emblist.cpp
// linked list class

#include "emblist.h"

// ---- construct a linked list
LinkedList::LinkedList()
{
    firstentry = 0;
    lastentry = 0;
}
// ---- destroy a linked list
LinkedList::~LinkedList()
{
    while (firstentry)
        firstentry->RemoveEntry();
}
// ---- construct a linked list entry
ListEntry::ListEntry(void *entry, LinkedList *lh)
{
    thisentry = entry;
    listhead = lh;
    nextentry = 0;
    preventry = 0;
}
// ---- append an entry to the linked list
void ListEntry::AppendEntry(LinkedList *lh)
{
    if (lh)
        listhead = lh;
    if (listhead != 0)    {
        preventry = listhead->lastentry;
        if (listhead->lastentry)
            listhead->lastentry->nextentry = this;
        if (listhead->firstentry == 0)
            listhead->firstentry = this;
        listhead->lastentry = this;
    }
}
// ---- remove an entry from the linked list
void ListEntry::RemoveEntry()
{
       // ---- repair any break made by this removal
       if (nextentry)
           nextentry->preventry = preventry;
       if (preventry)
           preventry->nextentry = nextentry;
    if (listhead)    {
        // --- maintain listhead if this is last and/or first
        if (this == listhead->lastentry)
            listhead->lastentry = preventry;
        if (this == listhead->firstentry)
            listhead->firstentry = nextentry;
    }
    preventry = 0;
    nextentry = 0;
}



[LISTING THREE]

// -------- testemp.cpp

#include <iostream.h>
#include "emblist.h"

class Date {
    int mo, da, yr;
public:
    ListEntry le;
    Date(int m=0, int d=0, int y=0) : le(this)
        { mo = m; da = d; yr = y; }
    friend ostream& operator << (ostream& os, Date& dt)
    { os << dt.da << '/' << dt.mo << '/' << dt.yr; return os; }
};
void main()
{
    LinkedList dtlist;
    int d = 0, m, y;
    Date *dt;
    while (d != 99)    {
        cout << "Enter dd mm yy (99 .. .. when done): ";
        cout << flush;
        cin >> d >> m >> y;
        if (d != 99)    {
            dt = new Date(m,d,y);
            dt->le.AppendEntry(&dtlist);
        }
    }
    dt = (Date *) dtlist.FirstEntry();
    while (dt != 0)    {
        cout << '\n' << *dt;
        dt = (Date *) dt->le.NextEntry();
    }
}


[LISTING FOUR]

// ------------ inhlist.h
// a linked list base class 

#ifndef INHLIST_H
#define INHLIST_H

class LinkedList;

// --- the linked list entry
class ListEntry    {
    ListEntry *nextentry;
    ListEntry *preventry;
    LinkedList *listhead;
    friend class LinkedList;
protected:
    ListEntry(LinkedList *lh = 0);
    virtual ~ListEntry() { RemoveEntry(); }
public:
    void AppendEntry(LinkedList *lh = 0);
    void RemoveEntry();
    ListEntry *NextEntry() { return nextentry; }
    ListEntry *PrevEntry() { return preventry; }
};
// ---- the linked list
class LinkedList    {
    // --- the listhead
    ListEntry *firstentry;
    ListEntry *lastentry;
    friend class ListEntry;
public:
    LinkedList();
    ~LinkedList();
    ListEntry *FirstEntry() { return firstentry; }
    ListEntry *LastEntry()  { return lastentry; }
};

#endif


[LISTING FIVE]

// ------------ inhlist.cpp
// linked list base class

#include "inhlist.h"

// ---- construct a linked list
LinkedList::LinkedList()
{
    firstentry = 0;
    lastentry = 0;
}
// ---- destroy a linked list
LinkedList::~LinkedList()
{
    while (firstentry)
        firstentry->RemoveEntry();
}
// ---- construct a linked list entry
ListEntry::ListEntry(LinkedList *lh)
{
    listhead = lh;
    nextentry = 0;
    preventry = 0;
}
// ---- append an entry to the linked list
void ListEntry::AppendEntry(LinkedList *lh)
{
    if (lh)
        listhead = lh;
    if (listhead != 0)    {
        preventry = listhead->lastentry;
        if (listhead->lastentry)
            listhead->lastentry->nextentry = this;
        if (listhead->firstentry == 0)
            listhead->firstentry = this;
        listhead->lastentry = this;
    }
}
// ---- remove an entry from the linked list
void ListEntry::RemoveEntry()
{
       // ---- repair any break made by this removal
       if (nextentry)
           nextentry->preventry = preventry;
       if (preventry)
           preventry->nextentry = nextentry;
    if (listhead)    {
        // --- maintain listhead if this is last and/or first
        if (this == listhead->lastentry)
            listhead->lastentry = preventry;
        if (this == listhead->firstentry)
            listhead->firstentry = nextentry;
    }
    preventry = 0;
    nextentry = 0;
}



[LISTING SIX]

// -------- testinh.cpp

#include <iostream.h>
#include "inhlist.h"

class Date : public ListEntry {
    int mo, da, yr;
public:
    Date(int m=0, int d=0, int y=0)
        { mo = m; da = d; yr = y; }
    friend ostream& operator << (ostream& os, Date& dt)
    { os << dt.da << '/' << dt.mo << '/' << dt.yr; return os; }
};
void main()
{
    LinkedList dtlist;
    int d = 0, m, y;
    Date *dt;
    while (d != 99)    {
        cout << "Enter dd mm yy (99 .. .. when done): ";
        cout << flush;
        cin >> d >> m >> y;
        if (d != 99)    {
            dt = new Date(m,d,y);
            dt->AppendEntry(&dtlist);
        }
    }
    dt = (Date *) dtlist.FirstEntry();
    while (dt != 0)    {
        cout << '\n' << *dt;
        dt = (Date *) dt->NextEntry();
    }
}


[LISTING SEVEN]

// ------------ linklist.h
// a template for a linked list

#ifndef LINKLIST_H
#define LINKLIST_H

template <class T>
// --- the linked list entry
class ListEntry    {
    T thisentry;
    ListEntry<T> *nextentry;
    ListEntry<T> *preventry;
    ListEntry(T& entry);
    friend class LinkedList<T>;
};
template <class T>
// ---- construct a linked list entry
ListEntry<T>::ListEntry(T &entry)
{
    thisentry = entry;
    nextentry = 0;
    preventry = 0;
}
template <class T>
// ---- the linked list
class LinkedList    {
    // --- the listhead
    ListEntry<T> *firstentry;
    ListEntry<T> *lastentry;
    ListEntry<T> *iterator;
    void RemoveEntry(ListEntry<T> *lentry);
    void InsertEntry(T& entry, ListEntry<T> *lentry);
public:
    LinkedList();
    ~LinkedList();
    void AppendEntry(T& entry);
    void RemoveEntry(int pos = -1);
    void InsertEntry(T&entry, int pos = -1);
    T *FindEntry(int pos);
    T *CurrentEntry();
    T *FirstEntry();
    T *LastEntry();
    T *NextEntry();
    T *PrevEntry();
};
template <class T>
// ---- construct a linked list
LinkedList<T>::LinkedList()
{
    iterator = 0;
    firstentry = 0;
    lastentry = 0;
}
template <class T>
// ---- destroy a linked list
LinkedList<T>::~LinkedList()
{
    while (firstentry)
        RemoveEntry(firstentry);
}
template <class T>
// ---- append an entry to the linked list
void LinkedList<T>::AppendEntry(T& entry)
{
    ListEntry<T> *newentry = new ListEntry<T>(entry);
    newentry->preventry = lastentry;
    if (lastentry)
        lastentry->nextentry = newentry;
    if (firstentry == 0)
        firstentry = newentry;
    lastentry = newentry;
}
template <class T>
// ---- remove an entry from the linked list
void LinkedList<T>::RemoveEntry(ListEntry<T> *lentry)
{
    if (lentry == 0)
        return;
    if (lentry == iterator)
        iterator = lentry->preventry;
    // ---- repair any break made by this removal
    if (lentry->nextentry)
        lentry->nextentry->preventry = lentry->preventry;
    if (lentry->preventry)
        lentry->preventry->nextentry = lentry->nextentry;
    // --- maintain listhead if this is last and/or first
    if (lentry == lastentry)
        lastentry = lentry->preventry;
    if (lentry == firstentry)
        firstentry = lentry->nextentry;
    delete lentry;
}
template <class T>
// ---- insert an entry into the linked list
void LinkedList<T>::InsertEntry(T& entry, ListEntry<T> *lentry)
{
    ListEntry<T> *newentry = new ListEntry<T>(entry);
    newentry->nextentry = lentry;
    if (lentry)    {
        newentry->preventry = lentry->preventry;
        lentry->preventry = newentry;
    }
    if (newentry->preventry)
        newentry->preventry->nextentry = newentry;
    if (lentry == firstentry)
        firstentry = newentry;
}
template <class T>
// ---- remove an entry from the linked list
void LinkedList<T>::RemoveEntry(int pos)
{
    FindEntry(pos);
    RemoveEntry(iterator);
}
template <class T>
// ---- insert an entry into the linked list
void LinkedList<T>::InsertEntry(T& entry, int pos)
{
    FindEntry(pos);
    InsertEntry(entry, iterator);
}
template <class T>
// ---- return the current linked list entry
T *LinkedList<T>::CurrentEntry()
{
    return iterator ? &(iterator->thisentry) : 0;
}
template <class T>
// ---- return a specific linked list entry
T *LinkedList<T>::FindEntry(int pos)
{
    if (pos != -1)    {
        iterator = firstentry;
        if (iterator)    {
            while (pos--)
                iterator = iterator->nextentry;
        }
    }
    return CurrentEntry();
}
template <class T>
// ---- return the first entry in the linked list
T *LinkedList<T>::FirstEntry()
{
    iterator = firstentry;
    return CurrentEntry();
}
template <class T>
// ---- return the last entry in the linked list
T *LinkedList<T>::LastEntry()
{
    iterator = lastentry;
    return CurrentEntry();
}
template <class T>
// ---- return the next entry in the linked list
T *LinkedList<T>::NextEntry()
{
    if (iterator == 0)
        iterator = firstentry;
    else
        iterator = iterator->nextentry;
    return CurrentEntry();
}
template <class T>
// ---- return the previous entry in the linked list
T *LinkedList<T>::PrevEntry()
{
    if (iterator == 0)
        iterator = lastentry;
    else
        iterator = iterator->preventry;
    return CurrentEntry();
}
#endif


[LISTING EIGHT]

// -------- testtmpl.cpp
#include <iostream.h>
#include "linklist.h"

class Date {
    int mo, da, yr;
public:
    Date(int m=0, int d=0, int y=0)
        { mo = m; da = d; yr = y; }
    friend ostream& operator << (ostream& os, Date& dt)
    { os << dt.da << '/' << dt.mo << '/' << dt.yr; return os; }
};
void main()
{
    LinkedList<Date> dtlist;
    int d = 0, m, y;
    while (d != 99)    {
        cout << "Enter dd mm yy (99 .. .. when done): ";
        cout << flush;
        cin >> d >> m >> y;
        if (d != 99)
            dtlist.AppendEntry(Date(m,d,y));
    }
    Date *dt = dtlist.FirstEntry();
    while (dt != 0)    {
        cout << '\n' << *dt;
        dt = dtlist.NextEntry();
    }
}