#include <stdio.h>
#include <stdlib.h>
#include "list.h"

#define TRUE	1
#define FALSE	0

void List_Init(tList *pList)
{
	tPosition pos;

	pList->nCount = 0;
	pos = &pList->Header;
	pos->pContent = NULL;
	pos->pNext = pos;
	pos->pPrev = pos;
}

int List_IsEmpty(tList *pList)
{
	return (pList->nCount == 0);
}

int List_GetCount(tList *pList)
{
	return (pList->nCount);
}

tPosition List_AddAfter(tList *pList, tPosition pos, void *pContent)
{
	tPosition posNew;

	posNew = (tPosition ) malloc(sizeof(tElement));
	if (posNew == NULL) {
		fprintf(stderr, "Error: out of memory!\n");
		exit(1);
	}
	posNew->pContent = pContent;
	posNew->pPrev = pos;
	posNew->pNext = pos->pNext;
	pos->pNext->pPrev = posNew;
	pos->pNext = posNew;
	pList->nCount++;
	return (posNew);
}

tPosition List_AddBefore(tList *pList, tPosition pos, void *pContent)
{
	return (List_AddAfter(pList, pos->pPrev, pContent));
}

tPosition List_AddHead(tList *pList, void *pContent)
{
	return (List_AddAfter(pList, &pList->Header, pContent));
}

tPosition List_AddTail(tList *pList, void *pContent)
{
	return (List_AddBefore(pList, &pList->Header, pContent));
}

tPosition List_GotoHead(tList *pList)
{
	if (pList->nCount == 0)
		return (NULL);
	else
		return (pList->Header.pNext);
}

tPosition List_GotoTail(tList *pList)
{
	if (pList->nCount == 0)
		return (NULL);
	else
		return (pList->Header.pPrev);
}

void *List_GetNext(tList *pList, tPosition *ppos)
{
	tPosition pos;
	tPosition posNext;

	pos = *ppos;
	if (pos == NULL)
		return (NULL);
	else if ((posNext = pos->pNext) == &pList->Header) {
		*ppos = NULL;
		return (pos->pContent);
	} else {
		*ppos = posNext;
		return (pos->pContent);
	}
}

void *List_GetPrev(tList *pList, tPosition *ppos)
{
	tPosition pos;
	tPosition posPrev;

	pos = *ppos;
	if (pos == NULL)
		return (NULL);
	else if ((posPrev = pos->pPrev) == &pList->Header) {
		*ppos = NULL;
		return (pos->pContent);
	} else {
		*ppos = posPrev;
		return (pos->pContent);
	}
}

void *List_RemoveAt(tList *pList, tPosition pos)
{
	tPosition posPrev;
	tPosition posNext;
	void *pContent;

	if (pos == NULL)
		return (NULL);
	else {
		pContent = pos->pContent;
		posNext = pos->pNext;
		posPrev = pos->pPrev;
		posNext->pPrev = posPrev;
		posPrev->pNext = posNext;
		free(pos);
		pList->nCount--;
		return (pContent);
	}
}

void *List_RemoveHead(tList *pList)
{
	if (pList->nCount == 0)
		return (NULL);
	else
		return (List_RemoveAt(pList, pList->Header.pNext));
}

void *List_RemoveTail(tList *pList)
{
	if (pList->nCount == 0)
		return (NULL);
	else
		return (List_RemoveAt(pList, pList->Header.pPrev));
}

tPosition List_Find(tList *pList, void *pContent)
{
	tPosition pos;

	pos = pList->Header.pNext;
	while (pos != &pList->Header) {
		if (pos->pContent == pContent)
			return (pos);
		pos = pos->pNext;
	}
	return (NULL);
}

void *List_GetAt(tList *pList, tPosition pos)
{
	if (pos == NULL)
		return (NULL);
	else
		return (pos->pContent);
}

tPosition List_TraverseForward(tList *pList, tPosition pos, tVisitFunc *pVisitFunc, void *pArgs)
{
	tPosition posPrev;
	void *pContent;

	while (pos != NULL) {
		posPrev = pos;
		pContent = List_GetNext(pList, &pos);
		if ((*pVisitFunc)(pContent, pArgs) == 1)
			return (posPrev);
	}
	return (NULL);
}

tPosition List_TraverseBackward(tList *pList, tPosition pos, tVisitFunc *pVisitFunc, void *pArgs)
{
	tPosition posNext;
	void *pContent;

	while (pos != NULL) {
		posNext = pos;
		pContent = List_GetPrev(pList, &pos);
		if ((*pVisitFunc)(pContent, pArgs) == 1)
			return (posNext);
	}
	return (NULL);
}

void List_Sort(tList *pList, int (*comp)(const void *pContent1, const void *pContent2))
{
	tPosition *array;
	int i, nCount;
	tPosition pos, posNew;

	nCount = pList->nCount;
	array = (tPosition *) malloc(nCount * sizeof(tPosition));
	i = 0;
	pos = pList->Header.pNext;
	while (pos != &pList->Header) {
		array[i++] = pos;
		pos = pos->pNext;
	}
	qsort(array, nCount, sizeof(tPosition), comp);
	pos = &pList->Header;
	pos->pNext = pos;
	pos->pPrev = pos;
	for (i = 0; i < nCount; i++) {
		posNew = array[i];
		posNew->pPrev = pos;
		posNew->pNext = pos->pNext;
		pos->pNext->pPrev = posNew;
		pos->pNext = posNew;
		pos = posNew;
	}
	free(array);
}