//list.cpp
//methods for class List

#include "list.h"
#include <assert.h>
#include <stdlib.h>
#include <iostream.h>

List::List()
{
	head = NULL;
}

Node *List::firstnode()
{
	return head;
}

void List::insertfront(Type x)
{
	Node *p;

	p = new Node;
	assert(p);
	p->setinfo(x);
	p->setnext(head);
	head = p;
}

void List::insertend(Type x)
{
	Node *p, *q;

	p = new Node;
	assert(p);
	p->setinfo(x);

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

void List::insertafter(Type x, Node *p)
{
	Node *q;

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

Type List::removefront()
{
	Node *p;
	Type x;

	assert(!isempty());
	
	p = head;
	x = p->getinfo();
	head = p->getnext();

	delete p;
	return x;
}

Type List::removeafter(Node *p)
{
	Type x;
	Node *q;

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

	delete q;
	return x;
}

Type List::removeend()
{
	Node *p,*q;

	assert(!isempty());

	p = head;
	q = NULL;

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

	if (q == NULL)
		return(removefront());
	else
		return(removeafter(q));
}

int List::isempty()
{
	return (head == NULL);
}

Node *List::findlast()
{
	Node *p;

	if (isempty()) return NULL;

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

	return p;
}

void List::print()
{
	Node *p;
	int i = 0;

	p = head;
	while (p) {
		cout << p->getinfo();
		cout << ' ';
		p = p->getnext();
		if(++i%20 == 0)
			cout<<"\n";
	}
   	cout << endl;
}

List::~List()
{
	Node *p, *q;

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

int List::find(Type x)
{
	Node *p;

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