//list.inl
//methods for class List template

#include <assert.h>
#include <iostream.h>

template <class Type>
List<Type>::List ()
{
	head = 0;
}

template <class Type>
Node<Type> *List<Type>::firstnode()
{
	return head;
}

template <class Type>
void List<Type>::insertfront(Type x)
{
	Node<Type> *p;

	p = new Node<Type> (x, head);
	assert(p);
	head = p;
}

template <class Type>
void List<Type>::insertend(Type x)
{
	Node<Type> *p, *q;

	p = new Node<Type> (x);
	assert(p);

	q = findlast();
	if (!q)
		head = p;
	else
		q->setnext(p);
}

template <class Type>
void List<Type>::insertafter(Type x, Node<Type> *p)
{
	Node<Type> *q;

	assert (p);
	q = new Node<Type> (x);
	assert (q);
	q->setnext(p->getnext());
	p->setnext(q);
}

template <class Type>
Type List<Type>::removefront()
{
	Node<Type> *p;
	Type x;

	assert(!isempty());

	p = head;
	x = p->getinfo();
	head = p->getnext();

	delete p;
	return x;
}

template <class Type>
Type List<Type>::removeafter(Node<Type> *p)
{
	Type x;
	Node<Type> *q;

	assert(p);
	q = p->getnext();
	assert(q);
	x = q->getinfo();
	p->setnext(q->getnext());

	delete q;
	return x;
}

template <class Type>
Type List<Type>::removeend()
{
	Node<Type> *p,*q;

	assert(!isempty());

	p = head;
	q = NULL;

	while (p->getnext()){
		q = p;
		p = p->getnext();
	}

	if (!q)
		return(removefront());
	else
		return(removeafter(q));
}

template <class Type>
int List<Type>::isempty()
{
	return (head == NULL);
}

template <class Type>
Node<Type> *List<Type>::findlast()
{
	Node<Type> *p;

	if (isempty())
		return NULL;

	p = head;
	while (p->getnext())
		p = p->getnext();

	return p;
}

template <class Type>
void List<Type>::print()
{
	Node<Type> *p;

	p = head;
	while (p) {
		cout<<p->getinfo()<<' ';
		p = p->getnext();
	}
	cout<<endl;
}

template <class Type>
int List<Type>::find(Type x)
{
	Node<Type> *p;

	p = head;
	while (p) {
		if (p->getinfo() == x)
			return 1;
		p = p->getnext();
	}
	return 0;
}


template <class Type>
List<Type>::~List()
{
	Node<Type> *p, *q;

	p = head;
	while (p) {
		q = p;
		p = p->getnext();
		delete q;
	}
	head = 0;
}