/* Copyright (c) 1993 by Sanjay Ghemawat */
#ifndef _LISTH
#define _LISTH

/*
 * A List is a generic doubly linked list.
 *
 * Usage -
 *	declareList(ListType,ElementType);
 *	implementList(ListType,ElementType);
 */

#include <generic.h>

#define _Link(LT) name2(LT,_Link)
#define _Cell(LT) name2(LT,_Cell)

/*
 * A _Link(LT) has previous and next pointers to other _Link(LT)s,
 * and has a boolean that indicates whether it is read cell
 * in the list, or just a dummy header node.
 *
 * A LT is basically a _Link(LT) set up so that the boolean
 * indicates that it is a dummy node.
 *
 * A _Cell(LT) is also a _Link(LT), but has a T field.
 */

#define declareList(LT,T)						      \
									      \
class _Link(LT);							      \
class _Cell(LT);							      \
class LT;								      \
									      \
class _Link(LT) {							      \
  public:								      \
    _Cell(LT)* Next();		/* Obtain next/prev cells.  If next/prev */   \
    _Cell(LT)* Prev();		/* field points to a dummy node, return 0 */  \
									      \
    _Link(LT)(int);		/* Only _Cell(LT) and LT should */	      \
    virtual ~_Link(LT)();	/* create/destroy _Link(LT)s */		      \
									      \
    void LinkAfter(_Cell(LT)*);	/* Append the cell after this */	      \
									      \
    _Link(LT)* next;		/* Next link */				      \
    _Link(LT)* prev;		/* Previous link */			      \
    int	     isCell;		/* Is this link a _Cell(LT)? */		      \
};									      \
									      \
/*									      \
 * A _Cell(LT) is a _Link(LT) that actually contains an element.	      \
 */									      \
class _Cell(LT) : public _Link(LT) {					      \
  public:								      \
    T& Element();		/* Get cell element */			      \
									      \
    _Cell(LT)* AddBefore(T&);	/* Add a new cell before this */	      \
    _Cell(LT)* AddAfter(T&);	/* Add a new cell after this */		      \
  protected:								      \
    _Cell(LT)(T&);		/* General users should not create _Cell(LT) */ \
    virtual ~_Cell(LT)();						      \
									      \
    T element;			/* Cell contents */			      \
									      \
    friend LT;								      \
};									      \
									      \
/*									      \
 * A LT is a _Link(LT) that does not contain any elements.		      \
 */									      \
class LT : private _Link(LT) {						      \
  public:								      \
    LT();			/* Create empty list */			      \
    virtual ~LT();		/* Destroy list */			      \
									      \
    void Clear();		/* Remove all elements */		      \
									      \
    _Cell(LT)* Prepend(T&);	/* Add new element at start */		      \
    _Cell(LT)* Append(T&);	/* Add new element at end */		      \
									      \
    void Remove(_Cell(LT)*);	/* Remove a cell */			      \
    void MoveToEnd(_Cell(LT)*);	/* Move to end of list */		      \
    void MoveToStart(_Cell(LT)*); /* Move to start of list */		      \
									      \
    _Cell(LT)* First();		/* Return first element - NULL if none */     \
    _Cell(LT)* Last();		/* Return last element - NULL if none */      \
									      \
    int Empty();		/* Is list empty */			      \
};									      \
									      \
inline _Link(LT)::_Link(LT)(int thisIsACell) {				      \
    isCell = thisIsACell;						      \
}									      \
									      \
inline _Cell(LT)* _Link(LT)::Next() {					      \
    return (next->isCell ? ((_Cell(LT)*) next) : 0);			      \
}									      \
									      \
inline _Cell(LT)* _Link(LT)::Prev() {					      \
    return (prev->isCell ? ((_Cell(LT)*) prev) : 0);			      \
}									      \
									      \
inline void _Link(LT)::LinkAfter(_Cell(LT)* newCell) {			      \
    newCell->next = next;						      \
    newCell->prev = this;						      \
    next->prev = newCell;						      \
    this->next = newCell;						      \
}									      \
									      \
inline _Cell(LT)::_Cell(LT)(T& e) : _Link(LT)(1) {			      \
    element = e;							      \
}									      \
									      \
inline T& _Cell(LT)::Element() {					      \
    return element;							      \
}									      \
									      \
inline _Cell(LT)* _Cell(LT)::AddBefore(T& e) {				      \
    _Cell(LT)* newCell = new _Cell(LT)(e);				      \
    prev->LinkAfter(newCell);						      \
    return newCell;							      \
}									      \
									      \
inline _Cell(LT)* _Cell(LT)::AddAfter(T& e) {				      \
    _Cell(LT)* newCell = new _Cell(LT)(e);				      \
    this->LinkAfter(newCell);						      \
    return newCell;							      \
}									      \
									      \
inline LT::LT() : _Link(LT)(0) {					      \
    prev = this;							      \
    next = this;							      \
}									      \
									      \
inline _Cell(LT)* LT::Prepend(T& e) {					      \
    _Cell(LT)* newCell = new _Cell(LT)(e);				      \
    this->LinkAfter(newCell);						      \
    return newCell;							      \
}									      \
									      \
inline _Cell(LT)* LT::Append(T& e) {					      \
    _Cell(LT)* newCell = new _Cell(LT)(e);				      \
    prev->LinkAfter(newCell);						      \
    return newCell;							      \
}									      \
									      \
inline void LT::Remove(_Cell(LT)* cell) {				      \
    delete cell;							      \
}									      \
									      \
inline void LT::MoveToEnd(_Cell(LT)* cell) {				      \
    cell->prev->next = cell->next;					      \
    cell->next->prev = cell->prev;					      \
    prev->LinkAfter(cell);						      \
}									      \
									      \
inline void LT::MoveToStart(_Cell(LT)* cell) {				      \
    cell->prev->next = cell->next;					      \
    cell->next->prev = cell->prev;					      \
    this->LinkAfter(cell);						      \
}									      \
									      \
inline _Cell(LT)* LT::First() {						      \
    return Next();							      \
}									      \
									      \
inline _Cell(LT)* LT::Last() {						      \
    return Prev();							      \
}									      \
									      \
inline int LT::Empty() {						      \
    return prev == this;						      \
}									      \

#define implementList(LT,T)						      \
									      \
_Link(LT)::~_Link(LT)() { }						      \
									      \
_Cell(LT)::~_Cell(LT)() {						      \
    prev->next = next;							      \
    next->prev = prev;							      \
}									      \
									      \
LT::~LT() {								      \
    Clear();								      \
}									      \
									      \
void LT::Clear() {							      \
    while (next != this) {						      \
	delete next;							      \
    }									      \
}									      \

/*
 * Macros for easy list traversal.
 */
#define List_ForEach(c,l)        for (c = l->First(); c; c = c->Next())
#define List_ForEachReverse(c,l) for (c = l->Last();  c; c = c->Prev())

#endif /* _LISTH */
