//Header File:	linked.h
#ifndef    LINKED_H
#define    LINKED_H

#include <iostream>
using namespace std;

//THIS VERSION DECLARES THREE DISTINCT CLASSES, node, myList, and ListIterator
//ALL OF THESE CLASSES MUST BE TEMPLATED

template <class T>
struct node
{
	T	data;
	node	*next;
};

//FORWARD DECLARATION IS NECESSARY
template <class T> class ListIterator;  //Forward declaration

template <class T>
class myList
{
friend class ListIterator<T>;

private:
	node<T> *front;
	node<T> *rear;

public:
	myList();		//Constructor
	myList(const myList &); //Copy Constructor
	
	~myList(); 		//Destructor	
	
	// Mutators	
	myList & add_front (const T);
	myList & remove_front ();
	myList & add_rear (const T);
	myList & remove_rear ();

	// Accessor
	bool empty() const;
};

// Companion to class list
template <class T>
class ListIterator
{
private:
	node<T> *current;

public:
	ListIterator(const myList<T> &); //Constructor
	ListIterator(const ListIterator<T> &); //Copy Constructor
	
	//"next" places data from current node into
	//parameter and advances current pointer
	//returns true if successful
	//false if at end of list
	bool next(T &);
};


/****************************************************************************/

//list IMPLEMENTATION
template <class T> 
myList<T>::myList()	//Constructor
:	front(NULL), rear(NULL) //member initializer list
{
}

template <class T> 
myList<T>::myList(const myList & L) //Copy Constructor
{
	
	front=rear=NULL;
	for (node<T> *temp = L.front; temp!=NULL; temp=temp->next)
	{
		add_rear(temp->data);
	}
}
		

template <class T> 
myList<T>::~myList() //Destructor
{
	node <T> *temp;
	while (front!=NULL)
	{
		temp = front->next;
		delete front;
		front = temp;
	}
}

	
template <class T> 
myList<T> & myList<T>::add_front (const T number)
{
	node <T> * temp=new node <T>;

	temp->data=number;
	temp->next=front;
	front=temp;

	if (rear==NULL)	//list empty to start
		rear=front;

	return *this;
}


//Pre-Condition:  Non-empty list
template <class T> 
myList<T> & myList<T>::remove_front ()
{
	node <T> * temp=front;

	front=front->next;
	delete temp;

	if (front==NULL)	//list empty
		rear=NULL;

	return *this;
}

template <class T> 
myList<T> & myList<T>::add_rear (const T number)
{
	node <T> * temp = new node <T>;

	temp->data=number;
	temp->next=0;
	if (rear!=NULL)
		rear->next=temp;
	rear=temp;

	if (front==NULL)	//list empty to start
		front=rear;

	return *this;
}
	
//Pre-Condition:  Non-empty list
template <class T> 
myList<T> & myList<T>::remove_rear ()
{
	node <T> *p, *followp=NULL;

	for (p=front; p!=rear; p=p->next)
		followp=p;

	if (followp!=NULL)
		followp->next=0;
	delete p;

	rear=followp;
	if (rear==NULL)	//list empty
		front=NULL;

	return *this;
}

template <class T> 
bool myList<T>::empty() const
{
	return (front==NULL);
}


/*************************************************************************/
// ListIterator IMPLEMENTATION
template <class T>
ListIterator<T>::ListIterator(const myList<T> & L) //Constructor
:	current(L.front)
{
}

template <class T>
ListIterator<T>::ListIterator(const ListIterator<T> & I) //Copy Constructor
:	current(I.current)
{
}
	
	//"next" places data from current node <T> into
	//parameter and advances current pointer
	//returns true if successful
	//false if at end of list

template <class T>
bool ListIterator<T>::next(T & number)
{
	if (current==NULL)
		return false;

	number = current->data;
	current = current->next;

	return true;
}
/**********************************AUXILIARY FUNCTION *****************************/
template <class T>
ostream & operator<< (ostream & out, const myList<T> & L)
{
	T data;
	
	ListIterator<T>	i(L);
	while (i.next(data))
	{
		out << data << endl;
	}

	return out;
}
/************************************************************************************/
#endif