/*
LinkedList.cpp
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.  See LinkedList.h for a
complete definition of the Linked List class.
*/

#ifndef __LL_CPP
#define __LL_CPP

#include "LinkedList.h"

template <class type> LinkedItem<type>::LinkedItem()
{
	Next = NULL;
}

template <class type> LinkedList<type>::LinkedList()
{
	Size = 0;
	Root = NULL;
}

template <class type> LinkedList<type>::LinkedList(const LinkedList<type> &LL)
{
	//to initalize ourselves as the data in LL, we need to parse over all entries in LL,
	//and copy each one into our own local data
	Size = 0;
	Root = NULL;
	LinkedItem<type>	*LLCurrent = LL.Root,	//start at LL's root
						*MyFinalNode = NULL;	//we have no root node yet
	while(LLCurrent != NULL)
	{
		if(MyFinalNode == NULL)					//if this is the 1st element,
		{
			MyFinalNode = new LinkedItem<type>;
			Root = MyFinalNode;					//create a new root node for us
			MyFinalNode->Next = NULL;
			MyFinalNode->Data = LLCurrent->Data;	//the data in the root node equals the data in LL's root node
			Size++;								//we're one element bigger now
		} else {
			MyFinalNode->Next = new LinkedItem<type>;
			MyFinalNode->Next->Data = LLCurrent->Data;
			MyFinalNode = MyFinalNode->Next;	//add the current data/node in LL to our list
			Size++;
		}
		LLCurrent = LLCurrent->Next;	//go to the next element in LL
	}
}

template <class type> LinkedList<type>::~LinkedList()
{
	FreeMemory();
}

template <class type> LinkedList<type>& LinkedList<type>::operator = (const LinkedList<type> &LL)
{
	//this is equivalent to initalization with LL, except we need to free our own memory first, if we have any
	FreeMemory();
	LinkedItem<type> *LLCurrent = LL.Root, *MyFinalNode = NULL;
	while(LLCurrent != NULL)
	{
		if(MyFinalNode == NULL)
		{
			MyFinalNode = new LinkedItem<type>;
			Root = MyFinalNode;
			MyFinalNode->Next = NULL;
			MyFinalNode->Data = LLCurrent->Data;
			Size++;
		} else {
			MyFinalNode->Next = new LinkedItem<type>;
			MyFinalNode->Next->Data = LLCurrent->Data;
			MyFinalNode = MyFinalNode->Next;
			Size++;
		}

		LLCurrent = LLCurrent->Next;
	}
	return *this;
}

template <class type> void LinkedList<type>::FreeMemory()
{
	if((Root) && (Size > 0))	//if we have any memory to free up
	{
		LinkedItem<type> *Stage=Root,*ToDie;
		for(int i = 0;i < Size;i++)			//iterate through each element
		{
			ToDie = Stage;
			Stage = Stage->Next;			//go to the next element
			delete ToDie;					//delete the previous element
		}
		if(Stage) delete Stage;
	}
	Size = 0;
	Root = NULL;
}

template <class type> type* LinkedList<type>::Dump()
{
	if(Size > 0)
	{
		LinkedItem<type> *Stage=Root;
		type *Dumped = new type[Size];	//allocate space for the dumped data
		for(int i = 0;i < Size;i++)		//iterate through each element
		{
			Dumped[Size-i-1] = Stage->Data;	//load the current element into the array
			Stage = Stage->Next;			//go to the next element
		}
		return Dumped;
	} else return NULL;	//no data, so return a NULL pointer
}

template <class type> void LinkedList<type>::Dump(Vector<type> &V)
{
	//this is the exact same as Dump() for a standard array, except we put our data into the vector V instead.
	V.Allocate(Size);
	if(Size > 0)
	{
		LinkedItem<type> *Stage=Root;
		for(int i = 0;i < Size;i++)
		{
			V[Size-i-1] = Stage->Data;
			Stage = Stage->Next;
		}
	}
}

template <class type> LinkedItem<type>* LinkedList<type>::GetPtr(int k)
{
	//slow and inefficent, this function just starts at the root and progesses k times.
	LinkedItem<type>* Stage=Root;
	if(!Stage) return Stage;

	if(k >= Size)
	{	//normally I set a breakpoint here.
		cout << "Out of bounds Linked List access; Index = " << k << ", Size = " << Size << endl;
		exit(1);
	}

	for(int i = 0;i < k;i++)
		Stage = Stage->Next;
	return Stage;
}

template <class type> void LinkedList<type>::Remove(int i)
{
	if(Size > 0)
	{
		if(i == 0) Pop();
		else
		{
			LinkedItem<type> *Prev = GetPtr(i-1);	//store the (i-1)'th and the i'th,
			LinkedItem<type> *ToDie = Prev->Next;
			Prev->Next = ToDie->Next;				//and skip over the i'th
			Size--;
			delete ToDie;	//free the i'th from memory
		}
	}
}

template <class type> type& LinkedList<type>::operator [] (int k)
{
	return GetPtr(k)->Data;
}

template <class type> void LinkedList<type>::Push()
{
	LinkedItem<type> *Temp, *Store;
	Temp = new LinkedItem<type>;
	Store = Root;
	Root = Temp;
	Root->Next = Store;
	Size++;
}

template <class type> void LinkedList<type>::Pop()
{
	if(Size > 0)
	{
		LinkedItem<type> *Store = Root;
		Root = Root->Next;
		delete Store;
		Size--;
		if(Size == 0) Root = NULL;
	}
}

template <class type> void LinkedList<type>::Pop(type &t)
{
	t = (*this)[0];
	Pop();
}

template <class type> void LinkedList<type>::Push(const type &t)
{
	Push();
	Root->Data = t;
}

#endif