1#include "min_stack.h"
  2#include <stdio.h>
  3#include <stdlib.h>
  4
  5/**
  6 * The equivalent of a constructor for initialzing
  7 * a new Node in a linked list.
  8 *
  9 * @param data The data to bind to the node
 10 * @param next The next node to point to. NULL for a new head.
 11 * @return The new linked list Node.
 12 */
 13static Node *new (int data, Node *next) {
 14  Node *node = malloc(sizeof(Node));
 15  node->next = next;
 16  node->data = data;
 17  return node;
 18}
 19
 20/**
 21 * The equivalent of a constructor for initialzing
 22 * a new min Stack.
 23 *
 24 * @return The new Stack
 25 */
 26Stack *initialize(void) {
 27  Stack *self = malloc(sizeof(Stack));
 28  self->head = NULL;
 29  self->min = NULL;
 30  self->size = 0;
 31  return self;
 32}
 33
 34/**
 35 * Returns the number of items on the stack.
 36 *
 37 * @param self The stack to investigate.
 38 */
 39int size(Stack *self) { return self->size; }
 40
 41/**
 42 * Pushes a new item on to a Stack
 43 *
 44 * @param self The stack to push the data on to
 45 * @param data The data to push on to the Stack
 46 */
 47void push(Stack *self, int data) {
 48  if (!self->min || (data < self->min->data))
 49    self->min = new (data, self->min);
 50
 51  self->head = new (data, self->head);
 52  self->size++;
 53}
 54
 55/**
 56 * Iterates through each item in a linked list.
 57 *
 58 * @param head The head of the linked list
 59 * @block The callback function to invoke on each item in the list.
 60 */
 61void each(Node *head, Visitor block) {
 62  Node *tmp = head;
 63
 64  while (tmp) {
 65    (*block)(tmp);
 66    tmp = tmp->next;
 67  }
 68}
 69
 70/**
 71 * Returns the minimum value in the Stack.
 72 *
 73 * @param self The stack to investigate
 74 */
 75int min(Stack *self) {
 76  if (self->min)
 77    return self->min->data;
 78
 79  if (self->head) {
 80    int min = self->head->data;
 81    Node *tmp = self->head->next;
 82
 83    while (tmp) {
 84      if (tmp->data < min)
 85        min = tmp->data;
 86      tmp = tmp->next;
 87    }
 88    return min;
 89  }
 90
 91  return (int)NULL;
 92}
 93
 94/**
 95 * Pops off the item from the top of the Stack.
 96 *
 97 * @param self The stack to pop an item off of.
 98 */
 99int pop(Stack *self) {
100  if (!self->head)
101    return (int)NULL;
102
103  Node *current = self->head;
104  int data = current->data;
105  if (data == self->min->data)
106    self->min = self->min->next;
107  self->head = current->next;
108  self->size--;
109  current->next = NULL;
110  free(current);
111  return data;
112}
113
114/**
115 * Prints a visual representation a Node in the linked list.
116 *
117 * @param node The node to print.
118 */
119void print_node(Node *node) { printf("[%d]", node->data); }
120
121/**
122 * A helper function to print out a visual representation of a Stack.
123 *
124 * @param stack the Stack to print out.
125 */
126void inspect(Stack *stack) {
127  printf("\t");
128  each(stack->head, &print_node);
129  printf("\n");
130}