/*
 * FILE: list.h - List ADT template class definition
 *                Uses linked-list representation
 *
 */

#ifndef __LIST
#define __LIST

#include <iostream>
#include <cassert>

using namespace std;

template <class item> class list;

template <class item>
class node
{	// All data members *and* constructor are private. Why?
	private:
		// Constructor
		node( const item&, node* );
		item 	data;
		node* 	link;

	// Why does this need to be here????
friend ostream& operator<<(ostream &,const list<item> &);
	// Means only lists, which are containers of nodes, can access into nodes
	friend class list<item>;
};

template <class item>
class list
{
	public:

		// Construct an empty list
		list();
		// Destroy a list by eliminating all nodes
		~list();

		// Set the list's data to initial state
		void init();

		// Destroy all nodes!
		void destroy();

		// Insertion
		void insertFirst(const item&);
		void insertLast(const item&);
		void insertInOrder(const item&);

		// Single node removal
		void removeFirst();
		void removeLast();
		void removeInOrder(const item&);

		// Inspectors
		item firstValue();	
		item lastValue();
		int size();
		
	private:
		node<item>* first;
		node<item>* last;
		int count;

	friend ostream& operator<<(ostream &,const list<item> &);

};

// Construct a node
template <class item> node<item>::node( const item& itm, node<item>* ptr )
{
	data = itm;
	link = ptr;
}

// Construct a list
template <class item> list<item>::list()
{	init();}

// Cause a list's nodes to be freed
template <class item> list<item>::~list()
{destroy();}

// Set data members to initialization condition
template <class item> void list<item>::init()
{	first = last = NULL;
	count = 0;
}

// Reset list
template <class item> void list<item>::destroy()
{	node<item>* doomed;
	while ( first != NULL )
	{	doomed = first;
		first = first->link;
		delete doomed;
	}
	init();
}

// Insert at head
template <class item> void list<item>::insertFirst( const item& itm )
{
	assert((first = new node<item>(itm,first)) != NULL);
	if ( last == NULL )
	{	last = first;
	}
	count++;
}

// Insert at Tail
template <class item> void list<item>::insertLast( const item& itm )
{
	if ( last == NULL )
	{
		insertFirst( itm );
	}
	else
	{
		assert( (last = last->link = new node<item>(itm, NULL)) != NULL );
		count++;
	}
}

// Insert in order
template <class item> void list<item>::insertInOrder(const item &elt)
{	if ( !first || elt < first->data )
		insertFirst(elt);
	else
	{	node<item>*	p	= first;
		node<item>*	trailp	= NULL;
		while ( p != NULL && elt > p->data )
		{	// Two pointer search
			trailp = p;
			p = p->link;
		}
		trailp->link = new node<item>(elt,p);
	}
}

// Remove from head
template <class item> void list<item>::removeFirst()
{
	assert( size() > 0 );
	node<item>* doomed = first;
	if ( first == last )
		first = last = NULL;
	else
		first = first->link;
	delete doomed;
	count--;
}

// Remove from tail
template <class item> void list<item>::removeLast()
{
	node<item>* doomed = last;
	if ( first == last )
		first = last = NULL;
	else
	{
		node<item>* tmp;
		for ( tmp = first; tmp->link != last; tmp = tmp->link ) ;
		tmp->link = NULL;
		last = tmp;
	}
	delete doomed;
	count--;
}

// Remove a node in the list: No precondition on node being in list
// Precondition: List not empty
template <class item> void list<item>::removeInOrder(const item &elt)
{	node<item>*	p = first;
	node<item>*	trailp = NULL;
	// Search for data
	while (p!=NULL && p->data!=elt)
	{	trailp = p;
		p = p->link;
	}
	if (p==NULL)		// x is not in the list; return
		return;
	if ( p == first )
		first = first->link;		// x is first in the list
	else
		trailp->link = p->link;	// x is farther down in the list
	delete p;
}

// Return copy of data in first node
template <class item> item list<item>::firstValue()
{
	assert( size() > 0 );
	return first->data;
}

// Return copy of data in last node
template <class item> item list<item>::lastValue()
{
	assert( size() > 0 );
	return last->data;
}

// Return number of nodes
template <class item> int list<item>::size()
{	return count;}

// Print
template <class item> ostream &operator<<(ostream &out,const list<item> &l)
{	for ( node<item> *p=l.first;p;p=p->link)
		out << p->data << endl;
	return(out);
}

#endif

// Things to try: 
//	Implement [] to get ith element
//	Implement copy constructor and = (deep copy)
//	Implement insertLast() as +=
//	Implement + to concatenate two linked lists
//	Implement other overloaded operators
//	Iterators?