/*------------------------------------------------------------------*/
/* list.c  (Version 1:  Fundamentals)                               */
/*------------------------------------------------------------------*/

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

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

struct List
{
      int iLength;
      struct Node *psMarkerNode;
};

/*------------------------------------------------------------------*/

struct List *List_new()

/* Return a new List_T. */

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

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

   return psList;
}

/*------------------------------------------------------------------*/

void List_free(struct List *psList)

/* Free *psList.
   It is a checked runtime error for psList to be NULL. */

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

/*------------------------------------------------------------------*/

int List_getLength(struct List *psList)

/* Return the number of items in *psList.
   It is a checked runtime error for psList to be NULL. */

{
   assert(psList != NULL);
   return psList->iLength;
}

/*------------------------------------------------------------------*/

void *List_getFirst(struct List *psList)

/* Return the first item of *psList.
   It is a checked runtime error for psList to be NULL or for
   *psList to be empty. */

{
   assert(psList != NULL);
   assert(psList->iLength > 0);
   return psList->psMarkerNode->psNextNode->pvItem;
}

/*------------------------------------------------------------------*/

void *List_getLast(struct List *psList)

/* Return the last item of *psList.
   It is a checked runtime error for psList to be NULL or for
   *psList to be empty. */

{
   assert(psList != NULL);
   assert(psList->iLength > 0);
   return psList->psMarkerNode->psPrevNode->pvItem;
}

/*------------------------------------------------------------------*/

void List_addFirst(struct List *psList, void *pvItem)

/* Add pvItem to the beginning of *psList.
   It is a checked runtime error for psList to be NULL. */

{
   struct Node *psNewNode;
   struct Node *psMarkerNode;
   struct Node *psFirstNode;

   assert(psList != NULL);

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

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

/*------------------------------------------------------------------*/

void List_addLast(struct List *psList, void *pvItem)

/* Add pvItem to the end of *psList.
   It is a checked runtime error for psList to be NULL. */

{
   struct Node *psNewNode;
   struct Node *psMarkerNode;
   struct Node *psLastNode;

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

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

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

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

   ++psList->iLength;
}

/*------------------------------------------------------------------*/

void List_removeFirst(struct List *psList)

/* Remove the first item of *psList.
   It is a checked runtime error for psList to be NULL or for
   *psList to be empty. */

{
   struct Node *psFirstNode;
   struct Node *psMarkerNode;

   assert(psList != NULL);
   assert(psList->iLength > 0);

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

/*------------------------------------------------------------------*/

void List_removeLast(struct List *psList)

/* Remove the last item of *psList.
   It is a checked runtime error for psList to be NULL or for
   *psList to be empty. */

{
   struct Node *psLastNode;
   struct Node *psMarkerNode;

   assert(psList != NULL);
   assert(psList->iLength > 0);

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

/*------------------------------------------------------------------*/

void List_toArray(struct List *psList, void **ppvArray)

/* Fill ppvArray with the items of *psList.
   It is a checked runtime error for psList or ppvArray to be NULL.
   It is an unchecked runtime error for *ppvArray to be too small
   to hold all items of *psList.  */

{
   struct Node *psNode;
   struct Node *psMarkerNode;
   int i = 0;

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

   psMarkerNode = psList->psMarkerNode;
   
   for (psNode = psMarkerNode->psNextNode;
        psNode != psMarkerNode;
        psNode = psNode->psNextNode)
   {
      ppvArray[i] = psNode->pvItem;
      ++i;
   }
}

/*------------------------------------------------------------------*/

void List_map(struct List *psList, 
              void (*pfApply)(void **ppvItem, void *pvExtra),
              void *pvExtra)

/* Apply function *pfApply to each item of *psList, passing pvExtra
   as an extra argument.  That is, for each item pvItem of *psList, 
   call (*pfApply)(&pvItem, pvExtra).
   It is a checked runtime error for psList or pfApply to be NULL. */

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