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

#include "list.h"

list::list() : head(NULL)
{}

list::~list()
{destroy( head );}

list::list( list& cl )
{head = copy( cl.head );}

list& list::operator =( const list& cl )
{	if ( this != &cl )
	{
		destroy( head );
		head = copy( cl.head );
	}
	return *this;
}

inline bool list::empty( void )
{return (head == NULL);}

bool list::find( int x )
{	node* p = head;
	while ( p != NULL && p->data != x )
	{p = p->next;
	}
	return (p != NULL && p->data == x);
}

void list::insertFirst( int x )
{assert( (head = new node( x, head)) != NULL );}

void list::orderedInsert( int x )
{	if ( empty() || x < head->data )
		insertFirst(x);
	else
	{	node*	p1	= head;
		node*	p2	= NULL;
		while ( p1 != NULL && x > p1->data )
		{	p2 = p1;
			p1 = p1->next;
		}
		assert( ( p2->next = new node( x, p1 ) ) != NULL );
	}
}

int list::removeFirst( void )
{	assert( !empty() );
	int		value = head->data;
	node*	doomed = head;
	head = head->next;
	delete doomed;
	return value;
}

void list::remove( int x )
{	assert( !empty() );
	node*	p1 = head;
	node*	p2 = NULL;
	while ( p1 != NULL && p1->data != x )
	{	p2 = p1;
		p1 = p1->next;
	}
	assert( p1 != NULL );		// x is not in the list
	if ( p1 == head )
		head = head->next;		// x is first in the list
	else
		p2->next = p1->next;	// x is farther down in the list
	delete p1;
}

void list::destroy( node* l )
{	while ( l != NULL )
	{	node* doomed = l;
		l = l->next;
		delete doomed;
	}
}

node* list::copy( node* l )
{	node* tmp1 = NULL;		// pointer to the beginning of the copied list
	node* tmp2 = NULL;		// pointer to the last item insert in the copy
	if ( l != NULL )
	{	assert( (tmp1 = tmp2 = new node( l->data, NULL )) != NULL );

		for (node* tmp3=l->next;tmp3!=NULL;tmp3=tmp3->next,tmp2=tmp2->next)
		{	assert( (tmp2->next = new node( tmp3->data, NULL )) != NULL );
		}
	}
	return tmp1;
}

ostream& operator<<( ostream& os, const list& l )
{	listItr	lt( l );
	for ( lt.start(); lt.more(); lt.next() )
		os << lt.value() << " ";
	return os;
}


list list::operator +( const list& l )
{	list	concatList;
	// insert your solution
	return concatList;
}


int *list::operator[](int idx)
{	node *p=head;
	for (int i=0;p && i<idx;p=p->next,i++);
	return((p ? &(p->data) : NULL));
}

int  list::operator+()
{	int sum=0;
	for (node *p=head;p;p=p->next)
		sum+=p->data;
	return(sum);
}

int list::countNodes(node *p)
{return ((p) ?	1+countNodes(p->next) : 0);}


int list::countNodesInList()
{return(countNodes(head));}

void list::sort(void)
{	//insert your solution
}


void list::mystery()
{	if (!head)	// list empty
		return;
	node *p,*trailp;
	for (p=head,trailp=NULL;p->next;trailp=p,p=p->next);
	if (p==head) 
		head=NULL;
	else
		trailp->next=NULL;
	delete p;
}