/*------------------------------------------------------------------*/
/* list.c                                                           */
/*------------------------------------------------------------------*/

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

struct Node
{
      void *pvItem;
      struct Node *psNextNode;
      struct Node *psPrevNode;
};

struct List
{
      unsigned long ulLength;
      struct Node *psMarkerNode;
};

struct ListIter
{
      struct List *psList;
      struct Node *psCurrentNode;
};

struct List *List_new()
{
   struct Node *psMarkerNode;
   struct List *psList;
   
   psMarkerNode = (struct Node*)malloc(sizeof(struct Node));
   assert(psMarkerNode != NULL);
   psMarkerNode->psNextNode = psMarkerNode;
   psMarkerNode->psPrevNode = psMarkerNode;
   psMarkerNode->pvItem = NULL;

   psList = (struct List*)malloc(sizeof(struct List));
   assert(psList != NULL);
   psList->ulLength = 0;
   psList->psMarkerNode = psMarkerNode;

   return psList;
}

void List_free(struct List *psList)
{
   struct Node *psNode;
   struct Node *psNextNode;
   struct Node *psMarkerNode;

   assert(psList != NULL);

   psMarkerNode = psList->psMarkerNode;
   
   for (psNode = psMarkerNode->psNextNode;
        psNode != psMarkerNode;
        psNode = psNextNode)
   {
      psNextNode = psNode->psNextNode;
      free(psNode);
   }
   free(psMarkerNode);
   free(psList);
}

unsigned long List_length(struct List *psList)
{
   assert(psList != NULL);
   return psList->ulLength;
}

void *List_getFirst(struct List *psList)
{
   assert(psList != NULL);
   assert(psList->ulLength > 0UL);
   return psList->psMarkerNode->psNextNode->pvItem;
}

void *List_getLast(struct List *psList)
{
   assert(psList != NULL);
   assert(psList->ulLength > 0UL);
   return psList->psMarkerNode->psPrevNode->pvItem;
}

void List_addFirst(struct List *psList, void *pvItem)
{
   struct Node *psNewNode;
   struct Node *psMarkerNode;
   assert(psList != NULL);
   psMarkerNode = psList->psMarkerNode;
   psNewNode = (struct Node*)malloc(sizeof(struct Node));
   assert(psNewNode != NULL);
   psNewNode->pvItem = pvItem;
   psNewNode->psPrevNode = psMarkerNode;
   psNewNode->psNextNode = psMarkerNode->psNextNode;
   psMarkerNode->psNextNode->psPrevNode = psNewNode;
   psMarkerNode->psNextNode = psNewNode;
   ++psList->ulLength;
}

void List_addLast(struct List *psList, void *pvItem)
{
   struct Node *psNewNode;
   struct Node *psMarkerNode;
   assert(psList != NULL);
   psMarkerNode = psList->psMarkerNode;
   psNewNode = (struct Node*)malloc(sizeof(struct Node));
   assert(psNewNode != NULL);
   psNewNode->pvItem = pvItem;
   psNewNode->psNextNode = psMarkerNode;
   psNewNode->psPrevNode = psMarkerNode->psPrevNode;
   psMarkerNode->psPrevNode->psNextNode = psNewNode;
   psMarkerNode->psPrevNode = psNewNode;
   ++psList->ulLength;
}

void List_removeFirst(struct List *psList)
{
   struct Node *psOldNode;
   struct Node *psMarkerNode;
   assert(psList != NULL);
   assert(psList->ulLength > 0UL);
   psMarkerNode = psList->psMarkerNode;
   psOldNode = psMarkerNode->psNextNode;
   psMarkerNode->psNextNode = psOldNode->psNextNode;
   psOldNode->psNextNode->psPrevNode = psMarkerNode;
   free(psOldNode);
   --psList->ulLength;
}

void List_removeLast(struct List *psList)
{
   struct Node *psOldNode;
   struct Node *psMarkerNode;
   assert(psList != NULL);
   assert(psList->ulLength > 0UL);
   psMarkerNode = psList->psMarkerNode;
   psOldNode = psMarkerNode->psPrevNode;
   psMarkerNode->psPrevNode = psOldNode->psPrevNode;
   psOldNode->psPrevNode->psNextNode = psMarkerNode;
   free(psOldNode);
   --psList->ulLength;
}

void List_map(struct List *psList, 
   void (*pfApply)(void **ppvItem, void *pvExtra),
   void *pvExtra)
{
   struct Node *psNode;
   struct Node *psMarkerNode;
   assert(psList != NULL);
   assert(pfApply != NULL);
   psMarkerNode = psList->psMarkerNode;
   for (psNode = psMarkerNode->psNextNode;
        psNode != psMarkerNode;
      psNode = psNode->psNextNode)
      (*pfApply)(&(psNode->pvItem), pvExtra);
}

void List_toArray(struct List *psList, void **ppvArray)
{
   struct Node *psNode;
   struct Node *psMarkerNode;
   unsigned long ul = 0UL;

   assert(psList != NULL);
   assert(ppvArray != NULL);

   psMarkerNode = psList->psMarkerNode;
   for (psNode = psMarkerNode->psNextNode;
        psNode != psMarkerNode;
      psNode = psNode->psNextNode)
   {
      ppvArray[ul] = psNode->pvItem;
      ++ul;
   }
}
   
struct ListIter *ListIter_new(struct List *psList)
{
   struct ListIter *psListIter;
   assert(psList != NULL);
   psListIter = (struct ListIter*)malloc(sizeof(struct ListIter));
   assert(psListIter != NULL);
   psListIter->psList = psList;
   psListIter->psCurrentNode = psList->psMarkerNode;
   return psListIter;
}

void ListIter_free(struct ListIter *psListIter)
{
   assert(psListIter != NULL);
   free(psListIter);
}

int ListIter_isValid(struct ListIter *psListIter)
{
   assert(psListIter != NULL);
   return psListIter->psCurrentNode != psListIter->psList->psMarkerNode;
}

void ListIter_moveToFirst(struct ListIter *psListIter)
{
   assert(psListIter != NULL);
   psListIter->psCurrentNode = psListIter->psList->psMarkerNode->psNextNode;
}

void ListIter_moveToLast(struct ListIter *psListIter)
{
   assert(psListIter != NULL);
   psListIter->psCurrentNode = psListIter->psList->psMarkerNode->psPrevNode;
}

void ListIter_moveToNext(struct ListIter *psListIter)
{
   assert(psListIter != NULL);
   assert(ListIter_isValid(psListIter));
   psListIter->psCurrentNode = psListIter->psCurrentNode->psNextNode;
}

void ListIter_moveToPrev(struct ListIter *psListIter)
{
   assert(psListIter != NULL);
   assert(ListIter_isValid(psListIter));
   psListIter->psCurrentNode = psListIter->psCurrentNode->psPrevNode;
}

void *ListIter_getCurrent(struct ListIter *psListIter)
{
   assert(psListIter != NULL);
   assert(ListIter_isValid(psListIter));
   return psListIter->psCurrentNode->pvItem;
}

void ListIter_deleteCurrent(struct ListIter *psListIter)
{
   struct Node *psPrevNode;
   struct Node *psNextNode;
   assert(psListIter != NULL);
   assert(ListIter_isValid(psListIter));
   psPrevNode = psListIter->psCurrentNode->psPrevNode;
   psNextNode = psListIter->psCurrentNode->psNextNode;
   psPrevNode->psNextNode = psNextNode;
   psNextNode->psPrevNode = psPrevNode;
   free(psListIter->psCurrentNode);
   psListIter->psCurrentNode = psNextNode;  /* arbitrary */
   --(psListIter->psList->ulLength);
}

void ListIter_insertBefore(struct ListIter *psListIter)
{
   struct Node *psNewNode;
   struct Node *psPrevNode;
   struct Node *psCurrentNode;
   
   assert(psListIter != NULL);
   assert(ListIter_isValid(psListIter));
   
   psNewNode = (struct Node*)malloc(sizeof(struct Node));
   assert(psNewNode != NULL);
   psNewNode->pvItem = pvItem;
   
   psCurrentNode = psListIter->psCurrentNode;
   psPrevNode = psCurrentNode->psPrevNode;
   
   psNewNode->psNextNode = psCurrentNode;
   psNewNode->psPrevNode = psPrevNode;

   psPrevNode->psNextNode = psNewNode;
   psCurrentNode->psPrevNode = psNewNode
   
   ++(psListIter->psList->ulLength);
}

void ListIter_insertAfter(struct ListIter *psListIter)
{
   struct Node *psNewNode;
   struct Node *psNextNode;
   struct Node *psCurrentNode;
   
   assert(psListIter != NULL);
   assert(ListIter_isValid(psListIter));
   
   psNewNode = (struct Node*)malloc(sizeof(struct Node));
   assert(psNewNode != NULL);
   psNewNode->pvItem = pvItem;
   
   psCurrentNode = psListIter->psCurrentNode;
   psNextNode = psCurrentNode->psNextNode;
   
   psNewNode->psPrevNode = psCurrentNode;
   psNewNode->psNextNode = psNextNode;

   psNextNode->psPrevNode = psNewNode;
   psCurrentNode->psNextNode = psNewNode
   
   ++(psListIter->psList->ulLength);
}