// The list data-structure is fundamental and used as building blocks
// for other data-structures.  The inheritance and template
// mechanisms in C++ allows for generic list classes with minimum
// duplication of code.

// This technique first defines the simplest list node emptyNode as a
// pointer to the next node.

class emptyNode {
public:
	emptyNode *next;
	emptyNode () { next = 0; }
	emptyNode (emptyNode *p) { next = p; }
};

// With emptyNode, the simplest list is two pointers to the front and
// rear emptyNode instances.  In addition, an integer counter len allows
// for the length of the list to be determined efficiently.

class emptyList {
protected:
	emptyNode *head, *tail;
	int len;
public:
	int empty() { return(head == 0); }
	int length() { return len; }
	void insert(emptyNode *);
	void append(emptyNode *);
	emptyNode *get();
	emptyList() { head = tail = 0; len = 0; }
	~emptyList();
friend	class emptyListIter;
};

// A list iterator allows items of a list to be traversed conveniently.
// It needs a pointer to a list node to indicate how much of a list has
// been processed.

class emptyListIter {
	emptyNode *current;
public:
	emptyListIter(emptyList *l) { current = l->head; }
	void init(emptyList *l) { current = l->head; }
	emptyNode *operator() () {
		if (!current) return 0;
		emptyNode *p = current;
		current = current->next;
		return p;
	}
};

// With the simplest nodes, lists and iterators, template subclass of
// these may be defined.  The classes node and listIter define the nodes
// and iterators for the generic list class by using the template
// mechanism.

// As an example, a list of integers intList may be defined as:
//    list<int> intList;
//
// Similarly, an integer list iterator forEachInt is defined as:
//    listIter<int> forEach(&intList);
//
// Subsequently, items in that list are processed via:
//     int *p;
//     while (p = forEach())
//         printf("%d\n", *p);

template<class T>
class node : public emptyNode {
public:
	T item;
	node(const T &i) : item(i) { }
};

template<class T>
class list : public emptyList {
public:
	void insert(const T &i)
		{ emptyList::insert(new node<T>(i)); }
	void append(const T &i)
		{ emptyList::append(new node<T>(i)); }

// The get() member function receives the first item in the list.  It
// relies on its base class, but also performs housekeeping by deleting
// the unused node.

	inline T get();

// The find() member function relies on the iterator to scan the list.

	inline T *find(const T &target);

// The remove() member function removes the node that corresponds to the
// target.

	inline void remove(const T &target);

// As with the find() member function, contains() and setUnion() relies
// on the iterator to appropriately process items of a list.

	inline int contains(list<T> &a);
	inline void setUnion(list<T> &a);
};

template<class T>
class listIter : emptyListIter {
public:
	listIter(list<T> *s) : emptyListIter(s) { }
	void init(list<T> *s) { emptyListIter::init(s); }
	T* operator() () {
		node<T> *l = (node<T> *) emptyListIter::operator() ();
		return(l ? &l->item : 0);
	}
};


template <class T>
inline
T list<T>::get()
	{
		node<T> *p = (node<T> *) emptyList::get();
		T i = p->item;
		delete p;
		return i;
	}

// The find() member function relies on the iterator to scan the list.

template <class T>
inline
T *list<T>::find(const T &target)
	{
		listIter<T> forEach(this);
		T *p;

		while (p = forEach())
			if (*p == target)
				return(p);
		return 0;
	}

// The remove() member function removes the node that corresponds to the
// target.

template <class T>
inline
void list<T>::remove(const T &target)
	{
		node<T> *p = (node<T> *) head;
		node<T> *previous = 0;

		while (p) {
			if (target == p->item) {
				if (tail == p)
					tail = previous;
				if (previous == 0)
					head = p->next;
				else
					previous->next = p->next;
				delete p;
				--len;
				return;
			}
			previous = p;
			p = (node<T> *) p->next;
		}
	}

// As with the find() member function, contains() and setUnion() relies
// on the iterator to appropriately process items of a list.

template <class T>
inline
int list<T>::contains(list<T> &a)
	{
		listIter<T> forEach(&a);
		T *p;

		while (p = forEach())
			if (!find(*p))
				return FALSE;
		return TRUE;
	}

template <class T>
inline
void list<T>::setUnion(list<T> &a)
	{
		listIter<T> forEach(&a);
		T *p;

		while (p = forEach())
			if (!find(*p))
				append(*p);
	}