/*------------------------------------------------------------------*/
/* list.c (Version 4: Iterator)                                     */
/*------------------------------------------------------------------*/

#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 *psSelectedNode;
};

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 = 0UL;
   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;
   struct Node *psFirstNode;

   assert(psList != NULL);

   psMarkerNode = psList->psMarkerNode;
   psFirstNode = psMarkerNode->psNextNode;

   psNewNode = (struct Node*)malloc(sizeof(struct Node));
   assert(psNewNode != NULL);
   
   psNewNode->pvItem = pvItem;
   psNewNode->psPrevNode = psMarkerNode;
   psNewNode->psNextNode = psFirstNode;
   
   psFirstNode->psPrevNode = psNewNode;
   psMarkerNode->psNextNode = psNewNode;
   
   ++psList->ulLength;
}

void List_addLast(struct List *psList, void *pvItem)
{
   struct Node *psNewNode;
   struct Node *psMarkerNode;
   struct Node *psLastNode;

   assert(psList != NULL);
   
   psMarkerNode = psList->psMarkerNode;
   psLastNode = psMarkerNode->psPrevNode;

   psNewNode = (struct Node*)malloc(sizeof(struct Node));
   assert(psNewNode != NULL);

   psNewNode->pvItem = pvItem;
   psNewNode->psNextNode = psMarkerNode;
   psNewNode->psPrevNode = psMarkerNode->psPrevNode;

   psLastNode->psNextNode = psNewNode;
   psMarkerNode->psPrevNode = psNewNode;

   ++psList->ulLength;
}

void List_removeFirst(struct List *psList)
{
   struct Node *psFirstNode;
   struct Node *psMarkerNode;

   assert(psList != NULL);
   assert(psList->ulLength > 0UL);

   psMarkerNode = psList->psMarkerNode;
   psFirstNode = psMarkerNode->psNextNode;
   
   psMarkerNode->psNextNode = psFirstNode->psNextNode;
   psFirstNode->psNextNode->psPrevNode = psMarkerNode;
   
   free(psFirstNode);
   --psList->ulLength;
}

void List_removeLast(struct List *psList)
{
   struct Node *psLastNode;
   struct Node *psMarkerNode;

   assert(psList != NULL);
   assert(psList->ulLength > 0UL);

   psMarkerNode = psList->psMarkerNode;
   psLastNode = psMarkerNode->psPrevNode;
   
   psMarkerNode->psPrevNode = psLastNode->psPrevNode;
   psLastNode->psPrevNode->psNextNode = psMarkerNode;
   
   free(psLastNode);
   --psList->ulLength;
}

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;
   }
}

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);
}

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->psSelectedNode = psList->psMarkerNode;
   return psListIter;
}

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

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

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

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

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

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

void *ListIter_selectedItem(struct ListIter *psListIter)
{
   assert(psListIter != NULL);
   assert(psListIter->psSelectedNode != psListIter->psList->psMarkerNode);
   return psListIter->psSelectedNode->pvItem;
}