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

//default constructor
List::List()
{
	firstnode = 0;
}

//parametrized constructor
List::List(Type x)
{
	firstnode = 0;
	insert_first(x);
}

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

//determines if the list is empty
int List::is_empty()
{
	return(firstnode == 0);
}

//insert first item
void List::insert_first(Type x)
{
	Node *p;
	
	p = new Node(x);
	assert(p);

	p->setnext(firstnode);
	firstnode = p;
}

void List::insert(Type x)
{
	Node *p = firstnode, *r;
	if(is_empty())
		insert_first(x);
	else
	{
		while(p) {
			r = p;
			p = p->getnext();
		}
		insertafter(x, r);
	}
}

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

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

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

	p = firstnode;
	while(p) {
		if (p->getinfo() == x)
			return p;
		p = p->getnext();
	}
	return NULL;
}

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

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

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

	assert(!is_empty());

	p = firstnode;
	x = p->getinfo();
	firstnode = p->getnext();
	delete p;

	return x;
}


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

ostream &operator<< (ostream &out, const List &l)
{
	Node *p = l.firstnode;

	while(p)
	{

		out << *p << endl;
		p = p->getnext();
	}

	return out;
}