// LinkedList.cpp: implementation of the CLinkedList class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "archimedes.h"

#include "LinkedList.h"

#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

CLinkedList::CLinkedList()
{
	TRACE("construct CLinkedList \n");
	head = NULL;
}

CLinkedList::~CLinkedList()
{
	// delete everything in list
	while(head != NULL)
	{
		LinkedListElement* oldHead = head;
		head = oldHead->nextElement;
		delete oldHead;
	}
}

// ??? update to keep tail pointer valid and use it for speed

void CLinkedList::addToTail(void* payload)
{
	// create new element
	LinkedListElement* newElement = new LinkedListElement;
	
	// set up payload for new element
	newElement->payload = payload;
	
	// if list empty
	if(head == NULL)
	{
		// empty list, so adjust head
		head = newElement;
		newElement->nextElement = NULL;
	}
	else
	{
		LinkedListElement* ptr = head;
		// find element that points to NULL (i.e. last in list)
		while(ptr->nextElement != NULL)
		{
			ptr = ptr->nextElement;
		}

		// adjust list
		ptr->nextElement = newElement;
		newElement->nextElement = NULL;
	}
}

void CLinkedList::addToHead(void *payload)
{
	// create new element
	LinkedListElement* newElement = new LinkedListElement;
	
	// set up payload for new element
	newElement->payload = payload;

	// adjust list
	LinkedListElement* oldHead = head;
	newElement->nextElement = oldHead;
	head = newElement;
}

void* CLinkedList::removeHead()
{
	if(head == NULL)
		TRACE("ERROR removeFromHead(), linked list empty\n");
	
	void* payload = head->payload;
	
	// adjust list
	LinkedListElement* newHead = head->nextElement;

	// delete old head element
	delete head;

	head = newHead;

	return payload;
}

void* CLinkedList::removeTail()
{
	if(head == NULL)
		TRACE("ERROR removeFromTails(), linked list empty\n");

	LinkedListElement* ptr = head;

	// find element that points to NULL (i.e. last in list)
	while(ptr->nextElement != NULL)
	{
		ptr = ptr->nextElement;
	}

	// get payload
	void* payload = ptr->payload;

	delete ptr;

	return payload;
}

void* CLinkedList::getHead()
{
	if(head == NULL)
		TRACE("ERROR getFromHead(), linked list empty\n");

	return head->payload;
}

BOOL CLinkedList::empty()
{
	if(head == NULL)
		return TRUE;
	else
		return FALSE;
}

//
// returns pointer to head of linked list so that the list can be examined
// without removing elements from it
//

LinkedListElement* CLinkedList::getPointerToHead()
{
	return head;
}


//
// insert an element at the given position (0...) the element that was in that
// position is put after the inserted one
//

void CLinkedList::insert(uint32 position, void *payload)
{
	uint32 counter = 0;
	LinkedListElement* ptr= head;
	LinkedListElement* oldPtr;
	
	if(position == 0 || head==NULL)
	{
		// insert at start of list
		LinkedListElement* newElement = new LinkedListElement();
		newElement->nextElement = head->nextElement;
		newElement->payload = payload;
		head = newElement;
	}
	else
	{
		// find position to insert
		while(ptr->nextElement != NULL)
		{
			counter++;
			oldPtr = ptr;
			ptr = ptr->nextElement;
			// if we've found location then insert
			if(counter == position)
			{
				LinkedListElement* newElement = new LinkedListElement();
				newElement->nextElement = ptr;
				newElement->payload = payload;
				oldPtr->nextElement = newElement;
				return;
			}
		}
		TRACE("ERROR, insertion position was outside bounds of list\n");
	}
}

//
// return the number of elements in the linked list
//

int CLinkedList::numberOfElements()
{
	// ??? should be implemented by keeping track of additions and deletions

	int counter = 0;
	LinkedListElement* ptr = head;
	while(ptr != NULL)
	{
		counter++;
		ptr = ptr->nextElement;
	}
	return counter;
}

//
// delete all elements in the linked list (and their payloads)
//

void CLinkedList::clear()
{
	LinkedListElement* ptr = head;
	while(ptr != NULL)
	{
		// delete payload
		delete ptr->payload;
		// store pointer to this element
		LinkedListElement* oldptr = ptr;
		// move to next element
		ptr = ptr->nextElement;
		// delete previous element
		delete oldptr;
	}
}