// File: LinkedList.h
// Linked List class with List Iterator class

#ifndef _LinkedList_
#define _LinkedList_
#include <assert.h>
#include <iostream>

using namespace std;

// Need to prototype template classes if they are to be friends
template <typename eltType> class LinkedList;

// and also the friend...note <> in header declaration of <<
template <typename eltType> 
		ostream& operator<<(ostream&,const LinkedList<eltType> &);

template <typename eltType> class node
{	private:
		node(eltType info= 0, node* link = NULL ) : 
						data(info), next(link) {};
		eltType data;
		node*	next;
	friend class LinkedList<eltType>;
	// why does the << have to be a friend? Can this be avoided?
	friend ostream& operator<< <>(ostream&,const LinkedList<eltType> &);
};

template <typename eltType> class LinkedList
{
	public:
		// Construct empty LinkedList
		LinkedList();
		// Construct deep copy of another LinkedList
		LinkedList(LinkedList&);

		// destroy LinkedList
		~LinkedList();

		// Assign another LinkedList to this LinkedList; deep copy
		LinkedList& operator=(const LinkedList&);

		// Is the LinkedList empty?
		bool empty();

		bool find(eltType);

		// Ordered insert/remove
		void orderedInsert(eltType);
		void remove(eltType);

		// Concatenate LinkedLists
		LinkedList operator+( const LinkedList& );

		// Return pointer to data part of as node (not the data itself)
		eltType *operator[](int);

		// Quick example of recursion
		int  countNodesInList();

		// Hmmmmm......
		void mystery();

	private:
		// linked list pointer
		node<eltType>*	head;

		// Get a copy of a (deep) node
		node<eltType>*	copy(node<eltType> *);

		// Free nodes of a linked list
		void	destroy(node<eltType> *);

		// Need this to count nodes in LinkedList
		int		countNodes(node<eltType> *);

	// Linked list to ostream
	friend ostream& operator<< <>(ostream&,const LinkedList<eltType> &);

};

#endif