/*--------------------------------------------------------------------*/
/* stack.c                                                            */
/* Author: Bob Dondero                                                */
/* Implementation of a generic stack ADT that uses function pointers  */
/*--------------------------------------------------------------------*/

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

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

/* Each item is stored in a StackNode.  StackNodes are linked to
   form a list.  */

struct StackNode
{
   /* The item. */
   const void *pvItem;

   /* The address of the next StackNode. */
   struct StackNode *psNextNode;
};

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

/* A Stack is a "dummy" node that points to the first StackNode. */

struct Stack
{
   /* The address of the first StackNode. */
   struct StackNode *psFirstNode;
};

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

Stack_T Stack_new(void)

/* Return a new Stack_T. */

{
  Stack_T oStack;

  oStack = (Stack_T)malloc(sizeof(struct Stack));
  assert(oStack != NULL);

  oStack->psFirstNode = NULL;
  return oStack;
}

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

void Stack_free(Stack_T oStack)

/* Free oStack. */

{
   struct StackNode *psCurrentNode;
   struct StackNode *psNextNode;

   if (oStack == NULL)
       return;

   for (psCurrentNode = oStack->psFirstNode;
        psCurrentNode != NULL;
        psCurrentNode = psNextNode)
   {
      psNextNode = psCurrentNode->psNextNode;
      free(psCurrentNode);
   }

   free(oStack);
}

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

void Stack_push(Stack_T oStack, const void *pvItem)

/* Push pvItem onto oStack.
   It is a checked runtime error for oStack to be NULL. */

{
   struct StackNode *psNewNode;

   assert(oStack != NULL);

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

   psNewNode->pvItem = pvItem;
   psNewNode->psNextNode = oStack->psFirstNode;
   oStack->psFirstNode = psNewNode;
}

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

void *Stack_top(Stack_T oStack)

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

{
   assert(oStack != NULL);
   assert(oStack->psFirstNode != NULL);

   return (void*)oStack->psFirstNode->pvItem;
}

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

void Stack_pop(Stack_T oStack)

/* Pop oStack, and discard the popped item.
   It is a checked runtime error for oStack to be NULL or empty. */

{
   struct StackNode *psNextNode;

   assert(oStack != NULL);
   assert(oStack->psFirstNode != NULL);

   psNextNode = oStack->psFirstNode->psNextNode;
   free(oStack->psFirstNode);
   oStack->psFirstNode = psNextNode;
}

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

int Stack_isEmpty(Stack_T oStack)

/* Return 1 (TRUE) iff oStack is empty.
   It is a checked runtime error for oStack to be NULL. */

{
   assert(oStack != NULL);

   return oStack->psFirstNode == NULL;
}

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

void Stack_map(Stack_T oStack,
               void (*pfApply)(void *pvItem, void *pvExtra),
               const void *pvExtra)

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

{
   struct StackNode *psCurrentNode;

   assert(oStack != NULL);
   assert(pfApply != NULL);

   for (psCurrentNode = oStack->psFirstNode;
        psCurrentNode != NULL;
        psCurrentNode = psCurrentNode->psNextNode)
      (*pfApply)((void*)psCurrentNode->pvItem, (void*)pvExtra);
}