/*
LinkedList.h
Written by Matthew Fisher

The LinkedList class contains linked lists of a template type.  There is also a STL equivalent that I
choose not to use.  Only the LinkedList class should be referenced directly.
*/

#ifndef __LL

#define __LL

//The LinkedItem class is rather trivial.  It is a single element in a linked list and 
//stores the data at the element and a pointer to the next element.  Also initalizes the pointer to NULL.
template <class type> class LinkedItem
{
public:
	LinkedItem();

	type Data;
	LinkedItem *Next;
};

template <class type> class LinkedList
{
public:
	//Initalization
	LinkedList();
	LinkedList(const LinkedList<type> &LL);

	//Destruction
	~LinkedList();
	void FreeMemory();

	/* Parser */
	//The Parser functions allow fast and easy iteration through all elements of the linked list
	//by moving a pointer along the list.  For example:
	//LinkedList<double> LL;
	//(initalize LL with things)
	//LL.Reset();
	//while(!LL.AtEnd()) {
	//	cout << LL.GetCurrent() << endl;
	//	LL.GoNext();
	//}
	//Displays every element in the linked list.

	__forceinline void Reset()
	{
		Current = Root;		//resets the current pointer to the beginning of the list
	}
	__forceinline void GoNext()
	{
		Current = Current->Next;	//advances to the next element in the list
	}
	__forceinline type& GetCurrent()
	{
		return Current->Data;	//gets the current element by reference
	}
	__forceinline type* GetCurrentPointer()
	{
		return &(Current->Data);	//gets a pointer to the current element
	}
	__forceinline bool AtEnd()
	{
		return (Current == NULL);	//true if we have gotten every element (and are currently sitting on a NULL pointer.)
	}
	
	//Accessors
	__forceinline int Length()
	{
		return Size;
	}
	type& operator [] (int k);	//returns the k'th element in the linked list.  Note that this is O(n), not O(1)
	LinkedList<type>& operator = (const LinkedList<type> &LL);

	void Push();				//pushes a new element at the beginning of the list
	void Push(const type &t);	//pushes t at the beginning of the list
	void Pop();					//removes the initial element in the list
	void Pop(type &t);			//pops the initial element and stores it in t
	void Remove(int i);			//removes the i'th element in the list.  Remove(0) is equivalent to Pop.
	
	type* Dump();				//dumps, as a leaked pointer, all data in the linked list into an array
	void Dump(Vector<type> &V);	//dumps this linked list into a Vector

private:
	LinkedItem<type>* GetPtr(int k);	//gets a pointer to the k'th element

	int Size;
	LinkedItem<type> *Root;		//the initial node in the list
	LinkedItem<type> *Current;	//the current node in the parsing of the list
};

#include "LinkedList.cpp"

#endif