#ifndef PARGEN_LIST_H
#define PARGEN_LIST_H

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

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;
};

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)); }
	
		T get()
		{
			node<T> *p = (node<T> *) emptyList::get();
			T i = p->item;
			delete p;
			return i;
		}
	
		void 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;
			}
		}

		inline T *find(const T &target);
		inline int contains(list<T> &a);
		inline void setUnion(list<T> &a);
};

class emptyListIter {
	private:
		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;
		}
};

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);
		}
};

/* inlines */

template <class Type>
inline 
Type *list<Type>::find(const Type &target) {
	listIter<Type> forEach(this);
	while (Type *p = forEach()) {
		if (*p == target)
			return(p);
	}
	return 0;
}

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);
}

#endif