#include "WimpLib:List.h"

#include "WimpLib:std.h"
#include <stdlib.h>

#include "WimpLib:Exception.h"
#include "WimpLib:mem.h"

struct ListNode
{
	struct ListNode* pPrevious;
	struct ListNode* pNext;
	const void*      pData;
};

struct List
{
	int       nr_nodes;
	ListNode* pFirst;
	ListNode* pLast;
};

static const char Err_InvalidNode[] = "List invalid node";
static const char Err_InvalidIndex[] = "List index out of bounds";

/**
 * Creates a new list.
 *
 * @returns        Pointer to a new list.
 */
List* New_List(void) throws(mem)
{
	return throw_mem_calloc(1, sizeof(List));
}

/**
 * Deletes a list.
 * This function DOES NOT delete the data pointed by each node.
 */
void Delete_List(List* This)
{
	if (This)
	{
		List_Clear(This);
		mem_free(This);
	}
}

/**
 * Returns the number of nodes in the list.
 */
int List_Count(const List* This)
{
	return This->nr_nodes;
}

/**
 * Inserts a new node in the list.
 *
 * @param  pNode  Pointer to the node to insert after.
 *                Use NULL to insert before all existing elements.
 * @param  pData  Pointer to the data to insert in the list.
 *
 * @returns       Pointer to a node from the list.
 */
ListNode* List_InsertAfter(List* This, ListNode* pNode, const void* pData) throws(mem)
{
	ListNode* pNew = throw_mem_alloc(sizeof(ListNode));
	ListNode* pNext;

	if (pNode == NULL)
		pNext  = This->pFirst;
	else
		pNext  = pNode->pNext;

	pNew->pPrevious = pNode;
	pNew->pNext = pNext;
	pNew->pData = pData;

	if (pNode == NULL)
		This->pFirst = pNew;
	else
		pNode->pNext = pNew;

	if (pNext == NULL)
		This->pLast = pNew;
	else
		pNext->pPrevious = pNew;

	This->nr_nodes++;

	return pNew;
}

/**
 * Inserts a new node in the list.
 *
 * @param  pNode  Pointer to the node to insert before.
 *                Use NULL to insert after all elements.
 * @param  pData  Pointer to the data to insert in the list.
 *
 * @returns       Pointer to a node from the list.
 */
ListNode* List_InsertBefore(List* This, ListNode* pNode, const void* pData) throws(mem)
{
	ListNode* pNew = throw_mem_alloc(sizeof(ListNode));
	ListNode* pPrev;

	if (pNode == NULL)
		pPrev = This->pLast;
	else
		pPrev = pNode->pPrevious;

	pNew->pPrevious = pPrev;
	pNew->pNext = pNode;
	pNew->pData = pData;

	if (pNode == NULL)
		This->pLast = pNew;
	else
		pNode->pPrevious = pNew;

	if (pPrev == NULL)
		This->pFirst = pNew;
	else
		pPrev->pNext = pNew;

	This->nr_nodes++;

	return pNew;
}

/**
 * Sets the data associated to a given node.
 *
 * @param  pNode  Pointer to the node.
 * @param  pData  Pointer to the data to set in the node.
 */
void List_SetNodeData(List* This, ListNode* pNode, const void* pData) throws(null)
{
	IGNORE(This);

	if (pNode == NULL)
		throw_runtime(Err_InvalidNode);

	pNode->pData = pData;
}

/**
 * Removes the node from the list without deleting the associated data.
 *
 * @param  pNode  Pointer to node to remove, ignores NULL.
 */
void List_RemoveNode(List* This, ListNode* pNode)
{
	if (pNode == NULL)
		return;

	if (pNode->pPrevious == NULL)
		This->pFirst = pNode->pNext;
	else
		pNode->pPrevious->pNext = pNode->pNext;

	if (pNode->pNext == NULL)
		This->pLast = pNode->pPrevious;
	else
		pNode->pNext->pPrevious = pNode->pPrevious;

	mem_free(pNode);

	This->nr_nodes--;
}

/**
 * Inserts a new node in the list.
 *
 * @param  index  Index at which the data is to be inderted.
 *                Use -1 to insert after all existing elements.
 * @param  pData  Pointer to the data to insert in the list.
 *
 * @returns       Pointer to a node from the list.
 */

ListNode* List_Insert(List* This, int index, const void* pData) throws(mem index)
{
	ListNode* pNode;

	if ((index < -1) || (index > This->nr_nodes))
		throw_runtime(Err_InvalidIndex);

	if ((index == -1) || (index == This->nr_nodes))
	{
		pNode = NULL;
		index = This->nr_nodes;
	}
	else
		pNode = List_GetNode(This, index);

	pNode = List_InsertBefore(This, pNode, pData);

	return pNode;
}

/**
 * Sets the data associated to a given node.
 *
 * @param  pNode  Pointer to the node.
 * @param  pData  Pointer to the data to set in the node.
 */
void List_Set(List* This, int index, const void* pData) throws(index)
{
	ListNode* pNode = List_GetNode(This, index);

	pNode->pData = pData;
}

/**
 * Removes the node from the list without deleting the associated data.
 *
 * @param  index  Index of the node to remove.
 *                Must be a valid index, -1 is ignored.
 */
void List_Remove(List* This, int index) throws(index)
{
	if (index == -1)
		return;

	List_RemoveNode(This, List_GetNode(This, index));
}

/**
 * Recursively deletes all the nodes.
 * This function DOES NOT delete the data pointed by each node.
 */
void List_Clear(List* This)
{
	ListNode* pNode = This->pFirst;
	ListNode* pNext;

	while(pNode != NULL)
	{
		pNext = pNode->pNext;
		mem_free(pNode);
		pNode = pNext;
	}

	This->nr_nodes = 0;
	This->pFirst = NULL;
	This->pLast  = NULL;
}

/**
 * Returns the order of a node in the list, index starts at 0 for the lowest node.
 *
 * @param  pNode  Pointer to the node.
 *
 * @returns       Index.
 */
int List_GetNodeIndex(const List* This, const ListNode* pNode) throws(null)
{
	int index = 0;
	const ListNode* pNext;

	if (pNode == NULL)
		throw_runtime(Err_InvalidNode);

	index = 0;
	pNext = This->pFirst;

	while(pNext)
	{
		if (pNext == pNode)
			return index;

		pNext = pNext->pNext;
		index++;
	}

	return -1;
}

/**
 * Gets the data associated to a given node.
 *
 * @param  pNode  Pointer to the node.
 * @returns       Pointer to the data in the node.
 */
void* List_GetNodeData(const List* This, const ListNode* pNode) throws(null)
{
	IGNORE(This);

	if (pNode == NULL)
		throw_runtime(Err_InvalidNode);

	return (void*) pNode->pData;
}

/**
 * Returns the next node in order (>=) to a given node.
 *
 * @param  pNode  Pointer to the node or NULL to get the pFirst (lowest) node.
 *
 * @returns       Pointer to the next node or NULL if none.
 */
ListNode* List_GetSuccessor(const List* This, const ListNode* pNode)
{
	if (pNode)
		return pNode->pNext;

	return This->pFirst;
}

/**
 * Returns the pPrevious node in order (<=) to a given node.
 *
 * @param  pNode  Pointer to the node or NULL to get the pLast (highest) node.
 *
 * @returns       Pointer to the pPrevious node or NULL if none.
 */
ListNode* List_GetPredecessor(const List* This, const ListNode* pNode)
{
	if (pNode)
		return pNode->pPrevious;

	return This->pLast;
}

/**
 * Attempts to locate data in a list.
 *
 * @param  pNode  Pointer to the node to start from or NULL to start from the beginning.
 * @param  pData  Pointer to data to locate.
 *
 * @returns       Pointer to the list's node containing the data or NULL if not found.
 */
ListNode* List_FindNode(const List* This, const ListNode* pNode, const void* pData)
{
	if (!pNode) pNode = This->pFirst;

	while (pNode != NULL)
	{
		if (pNode->pData == pData) return (ListNode*) pNode;
		pNode = pNode->pNext;
	}

	return NULL;
}

/**
 * Returns the data associated to a the node with the given index.
 *
 * @param  index  Index of the node to locate.
 *
 * @returns       Pointer to the data associated to the node.
 */
void* List_Get(const List* This, int index) throws(index)
{
	ListNode* pNode = List_GetNode(This, index);

	if (!pNode) return NULL;

	return (void*) pNode->pData;
}

/**
 * Returns the node with the given index.
 *
 * @param  index  Index of the node to locate.
 *
 * @returns       Pointer to the node.
 */
ListNode* List_GetNode(const List* This, int index) throws(index)
{
	int j;
	ListNode* pNode = This->pFirst;

	if ((index < 0) || (index >= This->nr_nodes))
		throw_runtime(Err_InvalidIndex);

	for (j = 0; j < index; j++)
		pNode = pNode->pNext;

	return pNode;
}

/**
 * Attempts to locate data in a list.
 *
 * @param  index  Index to start from.
 * @param  pData  Pointer to data to locate.
 *
 * @returns       Index of the node containing the data or -1 if not found.
 */
int List_Find(const List* This, int index, const void* pData) throws(index)
{
	if (index != This->nr_nodes)
	{
		ListNode* pNode = List_GetNode(This, index);

		while (pNode != NULL)
		{
			if (pNode->pData == pData)
				return List_GetNodeIndex(This, pNode);

			pNode = pNode->pNext;
		}
	}

	return -1;
}
