/*------------------------------------------------------------------*/
/* list.c  (Version 2:  Indexed Access)                             */
/*------------------------------------------------------------------*/

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

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

static struct Node *findNode(struct List *psList, int iIndex)

/* Return the address of the iIndex'th node of *psList. */

{
   int i;
   struct Node *psNode;

   psNode = psList->psMarkerNode;
   psNode = psNode->psNextNode;
   i = 0;
   while (i < iIndex)
   {
      psNode = psNode->psNextNode;
      ++i;
   }
   return psNode;
}

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

void *List_get(struct List *psList, int iIndex)

/* Return the iIndex'th item of *psList.
   It is a checked runtime error for psList to be NULL, for iIndex
   to be negative, or for iIndex to be greater than or equal to 
   *psList's length. */

{
   struct Node *psNode;

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

   psNode = findNode(psList, iIndex);
   return psNode->pvItem;
}

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

void List_insertNext(struct List *psList, void *pvItem, int iIndex)

/* Insert pvItem into *psList after the iIndex'th item.
   It is a checked runtime error for psList to be NULL, for iIndex
   to be negative, or for iIndex to be greater than or equal to 
   *psList's length. */

{
   struct Node *psNode;
   struct Node *psNextNode;
   struct Node *psNewNode;

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

   psNode = findNode(psList, iIndex);

   psNextNode = psNode->psNextNode;
   psNewNode = (struct Node*)malloc(sizeof(*psNewNode));
   assert(psNewNode != NULL);
   
   psNewNode->pvItem = pvItem;
   psNewNode->psPrevNode = psNode;
   psNewNode->psNextNode = psNextNode;
   
   psNextNode->psPrevNode = psNewNode;
   psNode->psNextNode = psNewNode;

   ++psList->iLength;
}

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

void List_insertPrev(struct List *psList, void *pvItem, int iIndex)

/* Insert pvItem into *psList before the iIndex'th item.
   It is a checked runtime error for psList to be NULL, for iIndex
   to be negative, or for iIndex to be greater than or equal to 
   *psList's length. */

{
   struct Node *psNode;
   struct Node *psPrevNode;
   struct Node *psNewNode;

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

   psNode = findNode(psList, iIndex);

   psPrevNode = psNode->psPrevNode;
   psNewNode = (struct Node*)malloc(sizeof(*psNewNode));
   assert(psNewNode != NULL);
   
   psNewNode->pvItem = pvItem;
   psNewNode->psNextNode = psNode;
   psNewNode->psPrevNode = psPrevNode;
   
   psPrevNode->psNextNode = psNewNode;
   psNode->psPrevNode = psNewNode;

   ++psList->iLength;
}

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

void List_remove(struct List *psList, int iIndex)

/* Remove the iIndex'th item from *psList.
   It is a checked runtime error for psList to be NULL, for iIndex
   to be negative, or for iIndex to be greater than or equal to 
   *psList's length. */

{
   struct Node *psNode;
   struct Node *psPrevNode;
   struct Node *psNextNode;

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

   psNode = findNode(psList, iIndex);

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