/* 

stack_as_linked_list.c 

Author: W. M. Farmer
Revised: November 18, 2008

Description: A simple implementation of a stack ADT in 
             which stacks are represented as linked lists.

*/

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

/* Types and constants */

typedef int nat; 

typedef char * element;

typedef struct n_rec {
  element data;
  struct n_rec * previous;
} node_rec;

typedef node_rec * node;

typedef struct {
  node top_node;
  nat height;
} stack_rec;

typedef stack_rec * stack;

node make_new_node(element e, node n) {
  node new = malloc(sizeof(node_rec));
  new->data = e;
  new->previous = n;
  return new;
}

void free_node(node old) {
  free(old);
}

/* Primitive operators */

stack bottom() {
  stack new = malloc(sizeof(stack_rec));
  new->top_node = NULL;
  new->height = 0;
  return new;
}

nat height(stack s) {
  return s->height;
}

element top(stack s) {
  nat ht = height(s);
  if (ht == 0) {
    printf("Error in top: stack is empty.\n");
    return 0;
  }
  else {
    return (s->top_node)->data;
  }
}

void push(element e, stack s) {
  nat ht = height(s);
  node top_node = s->top_node;
  node new = make_new_node(e, top_node);
  s->top_node = new;
  s->height = ht + 1;
}

void pop(stack s) {
  nat ht = height(s);
  if (ht == 0) {
    printf("Error in pop: stack is empty.\n");
    return ;
  }
  else {
    node top_node = s->top_node;
    s->top_node = top_node->previous;
    s->height = ht - 1;
    free_node(top_node);
  }
}

element string_of_element(element e) {
  return e;
}

element * get_element_array(nat h, node n) {
  element * a = malloc(sizeof(element[h]));
  int i = h;
  node m = n;
  while (i > 0) {
    a[i - 1] = m->data;
    m = m->previous;
    i = i - 1;
  }
  return a;
}

void print(stack s) {
  nat ht = s->height;
  element * a = get_element_array(ht, s->top_node); 
  int i;
  printf("Stack contents: [");
  for (i = 0; i < ht; i++)
    if (i + 1 == ht)
      printf("%s", a[i]);
    else 
      printf("%s,", a[i]);
  printf("].\n");
  free(a);
}

/* Derived operators */

bool is_empty (stack s) {
  return height(s) == 0;
}

void reset (stack s) {
  while (!is_empty(s)) {
    pop(s);
  }
}

/* Main function */

int main() {
  stack s = bottom();
  print(s);
  top(s);
  pop(s);
  push("a",s);
  print(s);
  printf("Top is %s.\n",top(s));
  push("b",s);
  print(s);
  push("c",s);
  print(s);
  pop(s);
  print(s);
  reset(s);
  print(s);
  return 0;


}