/*------------------------------------------------------------------*/
/* 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
{
      int iLength;
      struct Node *psMarkerNode;
};

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

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

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

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

struct ListIter *ListIter_new(struct List *psList)

/* Return a new ListIter_T that can iterate over *psList.  The 
   ListIter_T is in an invalid state.
   It is a checked runtime error for psList to be NULL. */

{
   struct ListIter *psListIter;

   assert(psList != NULL);

   psListIter = (struct ListIter*)malloc(sizeof(*psListIter));
   assert(psListIter != NULL);

   psListIter->psList = psList;
   psListIter->psSelectedNode = psList->psMarkerNode;
   return psListIter;
}

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

void ListIter_free(struct ListIter *psListIter)

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

{
   assert(psListIter != NULL);
   free(psListIter);
}

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

void ListIter_selectFirst(struct ListIter *psListIter)

/* Set *psListIter to select the first item of its List_T.  If there
   is a first item, then set *psListIter to be in a valid state. 
   Otherwise set *psListIter to be in an invalid state.
   It is a checked runtime error for psListIter to be NULL. */
   
{
   assert(psListIter != NULL);
   psListIter->psSelectedNode = 
      psListIter->psList->psMarkerNode->psNextNode;
}

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

void ListIter_selectLast(struct ListIter *psListIter)

/* Set *psListIter to select the last item of its List_T.  If there
   is a last item, then set *psListIter to be in a valid state. 
   Otherwise set *psListIter to be in an invalid state.
   It is a checked runtime error for psListIter to be NULL. */

{
   assert(psListIter != NULL);
   psListIter->psSelectedNode = 
      psListIter->psList->psMarkerNode->psPrevNode;
}

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

void ListIter_selectNext(struct ListIter *psListIter)

/* Set psListIter to select the next item of its List_T.
   It is a checked runtime error for psListIter to be NULL or for
   *psListIter to be in an invalid state. */

{
   assert(psListIter != NULL);
   assert(ListIter_selectionIsValid(psListIter));
   psListIter->psSelectedNode = psListIter->psSelectedNode->psNextNode;
}

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

void ListIter_selectPrev(struct ListIter *psListIter)

/* Set *psListIter to select the previous item of its List_T.
   It is a checked runtime error for psListIter to be NULL or for
   *psListIter to be in an invalid state. */

{
   assert(psListIter != NULL);
   assert(ListIter_selectionIsValid(psListIter));
   psListIter->psSelectedNode = psListIter->psSelectedNode->psPrevNode;
}

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

int ListIter_selectionIsValid(struct ListIter *psListIter)

/* Return 1 (TRUE) if and only if *psListIter is in a valid state. 
   It is a checked runtime error for psListIter to be NULL. */

{
   assert(psListIter != NULL);
   return psListIter->psSelectedNode != psListIter->psList->psMarkerNode;
}

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

void *ListIter_get(struct ListIter *psListIter)

/* Return the item which *psListIter is selecting.
   It is a checked runtime error for psListIter to be NULL or for
   *psListIter to be in an invalid state. */

{
   assert(psListIter != NULL);
   assert(ListIter_selectionIsValid(psListIter));
   return psListIter->psSelectedNode->pvItem;
}

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

void ListIter_insertNext(struct ListIter *psListIter, void *pvItem)

/* Insert pvItem into *psListIter's List_T after the selected item.
   It is a checked runtime error for psListIter to be NULL or for
   *psListIter to be in an invalid state. */

{
   struct Node *psNewNode;
   struct Node *psSelectedNode;
   struct Node *psNextNode;

   assert(psListIter != NULL);
   assert(ListIter_selectionIsValid(psListIter));

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

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

void ListIter_insertPrev(struct ListIter *psListIter, void *pvItem)

/* Insert pvItem into *psListIter's List_T before the selected item.
   It is a checked runtime error for psListIter to be NULL or for
   *psListIter to be in an invalid state. */

{
   struct Node *psNewNode;
   struct Node *psSelectedNode;
   struct Node *psPrevNode;

   assert(psListIter != NULL);
   assert(ListIter_selectionIsValid(psListIter));

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

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

void ListIter_removeAndSelectNext(struct ListIter *psListIter)

/* Remove the selected item from *psListIter's List_T, and select
   the next item.  If there is a next item, set *psListIter to be in 
   a valid state.  Otherwise set *psListIter to be in an invalid 
   state. 
   It is a checked runtime error for psListIter to be NULL or for
   *psListIter to be in an invalid state. */

{
   struct Node *psPrevNode;
   struct Node *psNextNode;
   struct Node *psSelectedNode;

   assert(psListIter != NULL);
   assert(ListIter_selectionIsValid(psListIter));

   psSelectedNode = psListIter->psSelectedNode;
   psPrevNode = psSelectedNode->psPrevNode;
   psNextNode = psSelectedNode->psNextNode;
   
   psPrevNode->psNextNode = psNextNode;
   psNextNode->psPrevNode = psPrevNode;
   
   free(psSelectedNode);

   psListIter->psSelectedNode = psNextNode;
   --psListIter->psList->iLength;
}

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

void ListIter_removeAndSelectPrev(struct ListIter *psListIter)

/* Remove the selected item from *psListIter's List_T, and select
   the previous item.  If there is a previous item, set *psListIter 
   to be in a valid state.  Otherwise set *psListIter to be in an 
   invalid state.
   It is a checked runtime error for psListIter to be NULL or for
   *psListIter to be in an invalid state. */

{
   struct Node *psPrevNode;
   struct Node *psNextNode;
   struct Node *psSelectedNode;

   assert(psListIter != NULL);
   assert(ListIter_selectionIsValid(psListIter));

   psSelectedNode = psListIter->psSelectedNode;
   psPrevNode = psSelectedNode->psPrevNode;
   psNextNode = psSelectedNode->psNextNode;
   
   psPrevNode->psNextNode = psNextNode;
   psNextNode->psPrevNode = psPrevNode;
   
   free(psSelectedNode);

   psListIter->psSelectedNode = psPrevNode;
   --psListIter->psList->iLength;
}