// File: LinkedList.cpp
// Ordered Template Linked List Implementations

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

// Construct empty LinkedList
template <class eltType> LinkedList<eltType>::LinkedList() : head(NULL)
{}

// Copy constructor. copy() does the deep copy
template <class eltType> 
	LinkedList<eltType>::LinkedList(LinkedList<eltType> &cl)
{head = copy( cl.head );}

// Free all nodes
template <class eltType> LinkedList<eltType>::~LinkedList()
{destroy(head);}

// Assignment operator: copy() does the deep copy
template <class eltType> LinkedList<eltType> 
	&LinkedList<eltType>::operator =(const LinkedList<eltType>& cl)
{	if (this != &cl)
	{	destroy(head);
		head = copy(cl.head);
	}
	return *this;
}

// Place x into the list in order
template <class eltType> 
		void LinkedList<eltType>::orderedInsert(eltType x)
{	if (empty() || x < head->data)
		assert(head=new node<eltType>(x,head));
	else
	{	node<eltType>*	p	= head;
		node<eltType>*	trailp	= NULL;
		while (p != NULL && x > p->data)
		{	trailp = p;
			p = p->next;
		}
		assert((trailp->next = new node<eltType>(x,p)) != NULL);
	}
}

// Is this element in the linked list?
template <class eltType> 
		bool LinkedList<eltType>::find(eltType x)
{	node<eltType> *p = head;
	while (p != NULL && p->data != x)
		p = p->next;
	return (p != NULL && p->data == x);
}

// Inline: Look into this.
template <class eltType> inline bool LinkedList<eltType>::empty()
{return (head == NULL);}

// Remove a node in an ordered list
// Pre: Node will be found
template <class eltType> void LinkedList<eltType>::remove(eltType x)
{	assert( !empty() );
	node<eltType>*	p = head;
	node<eltType>*	trailp = NULL;
	while ( p != NULL && p->data != x )
	{	trailp = p;
		p = p->next;
	}
	assert(p != NULL);		// x is not in the LinkedList
	if (p == head)
		head = head->next;	// x is first in the LinkedList
	else
		trailp->next = p->next;	// x is farther down in the LinkedList
	delete p;
}

// Remove all nodes in the linked list, starting at l
template <class eltType> void LinkedList<eltType>::destroy(node<eltType> *l)
{	while (l != NULL)	
	{	node<eltType> *doomed = l;
		l = l->next;
		delete doomed;
	}
}

// The deep copy. Copy the source list l, one node at a time
template <class eltType> 
	node<eltType>* LinkedList<eltType>::copy(node<eltType> *l)
{	node<eltType>* first = NULL;	// ptr to beginning of copied LinkedList
	node<eltType>* last = NULL;	// ptr to last item insert in the copy
	if (l != NULL)
	{	assert((first=last=new node<eltType>(l->data,NULL)) != NULL);
		for (node<eltType>* source=l->next;source!=NULL;
					source=source->next,last=last->next)
		{	last->next = new node<eltType>(source->data,NULL);
			assert(last->next);
		}
	}
	return first;
}

// Output a linked list, using a list iterator
template <class eltType> 
	// ostream& operator<<(ostream &os, const LinkedList<eltType> &l)
	ostream& operator<<(ostream &os, LinkedList<eltType> l)
{	listItr<eltType>	lt(l);
	for (lt.start(); lt.more(); lt.next())
		os << lt.value() << " ";
	return os;
}

// One for you to do
template <class eltType> LinkedList<eltType> 
		LinkedList<eltType>::operator +(const LinkedList<eltType> &l)
{	LinkedList<eltType>	concatList;
	// insert your solution
	return concatList;
}

// Return a pointer *directly* into a node's data in the linked list
template <class eltType> eltType* LinkedList<eltType>::operator[](int idx)
{	node<eltType> *p=head;
	for (int i=0;p && i<idx;p=p->next,i++);
	return((p ? &(p->data) : NULL));
}

// Count nodes in a linked list, starting at l
template <class eltType> int LinkedList<eltType>::countNodes(node<eltType> *p)
{return ((p) ?	1+countNodes(p->next) : 0);}

// Return number of nodes in *this' list
template <class eltType> int LinkedList<eltType>::countNodesInList()
{return(countNodes(head));}

// What does it do? Replace this with an explanation
template <class eltType> void LinkedList<eltType>::mystery()
{	if (!head)	// LinkedList empty
		return;
	node<eltType> *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;
}

// Construct a list iterator. It consists of:
//	 a reference to a linked list object
//	 a pointer to the actual list, initially pointing to its head
template <class eltType> 
listItr<eltType>::listItr(const LinkedList<eltType> &l):
											itr(l),curr(l.head) 
{}

// Set curr to point at itr's head
template <class eltType> void listItr<eltType>::start(void)
{curr = itr.head;}

// Is curr at the end of the list?
template <class eltType> bool listItr<eltType>::more(void)
{return curr != NULL;}

// Move curr to next node
template <class eltType> void listItr<eltType>::next(void)
{assert( curr != NULL );
 curr = curr->next;
}

// Return data in curr's node. Regardless of assert(), this 
//	function shouldn't be called until making sure more() returns true
template <class eltType> eltType listItr<eltType>::value(void)
{assert( curr != NULL );
 return curr->data;
}

// Initializers. Necessary to be able to be able to place template class
//	function implementations in a .cpp file

template class node<int>;
template class LinkedList<int>;
template class listItr<int>;
template class ostream& operator<<(ostream &os, const LinkedList<int> &l);