#include <assert.h>
#include <stdlib.h> // for malloc() and free()
#include "stack.h"

/* node of a doubly-linked list */
struct Node {
	struct Node *next, *prev;
	void *data;
};

/*
 * stack implemented using a doubly-linked list to allow traversal from the top
 * or the bottom
 */
struct Stack {
	struct Node *top, *bottom;
	size_t size;
};

/* node_new: create a new doubly-linked list node */
static struct Node *
node_new(void)
{
	struct Node *node = malloc(sizeof *node);
	if (node == NULL) {
		return NULL;
	}
	node->next = node->prev = node->data = NULL;
	return node;
}

/* node_free: free a doubly-linked list node */
static void
node_free(struct Node *node)
{
	assert(node != NULL);
	free(node);
}

/* stack_new: create a new empty stack */
struct Stack *
stack_new(void)
{
	struct Stack *stack = malloc(sizeof *stack);
	if (stack == NULL) {
		return NULL;
	}
	stack->top = stack->bottom = NULL;
	stack->size = 0;
	return stack;
}

/*
 * stack_delete: free memory used by the stack and it's nodes. But don't free
 * any data pointed to by the stack nodes
 * good for stacks that don't store pointers to dynamically allocated buffers
 */
void
stack_delete(struct Stack *stack)
{
	assert(stack != NULL);
	for (struct Node *node = stack->top, *next_node;
		node != NULL; node = next_node)
	{
		next_node = node->next;
		node_free(node);
	}
	free(stack);
}

/*
 * stack_free: free memory used by the stack, it's nodes, and the data stored
 * inside each node
 * good for stacks that store pointers to dynamically allocated buffers
 */
void
stack_free(struct Stack *stack, void (*free_data)(void *))
{
	assert(stack != NULL);
	assert(free_data != NULL);

	for (struct Node *node = stack->top, *next_node;
		node != NULL; node = next_node)
	{
		next_node = node->next;
		free_data(node->data);
		node_free(node);
	}
	free(stack);
}

/* push_stack: push a new node of value 'data' to top of 'stack' */
void *
stack_push(struct Stack *stack, void *data)
{
	assert(stack != NULL);
	assert(data != NULL);

	// create a new node with passed 'data'
	struct Node *newtop;
	if ((newtop = node_new()) == NULL) {
		return NULL;
	}
	newtop->data = data;

	// push node to stack
	if (stack->top == NULL) {
		// first node in stack
		stack->top = stack->bottom = newtop;
	} else {
		// link new top and old top
		newtop->next = stack->top;
		stack->top->prev = newtop;
		// put new node at top of stack
		stack->top = newtop;
	}
	stack->size++;
	return newtop;
}

/* stack_pop: pop data value of top node of 'stack' */
void *
stack_pop(struct Stack *stack)
{
	assert(stack != NULL);
	struct Node *oldtop = stack->top,
		*newtop = stack->top->next;
	void *data = oldtop->data;

	// remove reference to old top and free it
	newtop->prev = NULL;
	node_free(oldtop);
	// set new stack top and size
	stack->top = newtop;
	stack->size--;
	return data;
}

/* stack_size: accessor for size of stack */
size_t
stack_size(struct Stack *stack)
{
	assert(stack != NULL);
	return stack->size;
}

/*
 * stack_iter: loop over 'stack' nodes from top to bottom, running 'apply' on
 * each node
 */
void *
stack_iter(struct Stack *stack, void *(*apply)(void *))
{
	assert(stack != NULL);
	assert(apply != NULL);
	for (struct Node *node = stack->top; node != NULL; node = node->next) {
		if (apply(node->data) == NULL) {
			return NULL;
		}
	}
	return stack;
}

/*
 * stack_iter: loop over 'stack' nodes from bottom to top, running 'apply' on
 * each node
 */
void *
stack_iter_reverse(struct Stack *stack, void *(*apply)(void *))
{
	assert(stack != NULL);
	assert(apply != NULL);
	for (struct Node *node = stack->bottom; node != NULL; node = node->prev) {
		if (apply(node->data) == NULL) {
			return NULL;
		}
	}
	return stack;
}