Convert min stack to near constant time algorithm

3 files changed, 128 insertions, 41 deletions

diff --git a/src/01/06/min_stack.c b/src/01/06/min_stack.c
index 6f8511b..816b46d 100644
--- a/src/01/06/min_stack.c
+++ b/src/01/06/min_stack.c
@@ -2,20 +2,6 @@
 #include <stdlib.h>
 #include "min_stack.h"
 
-Stack *initialize(void) {
-  Stack *self = malloc(sizeof(Stack));
-  self->head = NULL;
-  return self;
-}
-
-int size(Stack *self) {
-  Node *current = self->head;
-  int i;
-  for (i = 0; current != NULL; i++)
-    current = current->next;
-  return i;
-}
-
 static Node *new(int data) {
   Node *node = malloc(sizeof(Node));
   node->next = NULL;
@@ -23,38 +9,50 @@ static Node *new(int data) {
   return node;
 }
 
-static int compare(int x, int y) {
-  return x == y ? 0 : (x > y) ? 1 : -1;
+Stack *initialize(void) {
+  Stack *self = malloc(sizeof(Stack));
+  self->head = NULL;
+  self->min = NULL;
+  self->size = 0;
+  return self;
 }
 
-static void insert(Node **self, int data) {
-  int comparison = compare(data, (*self)->data);
-  Node *node = new(data);
-
-  switch(comparison) {
-    case 1:
-      if ((*self)->next)
-        insert(&((*self)->next), data);
-      else
-        (*self)->next = node;
-      break;
-    default:
-      node->next = *self;
-      *self = node;
-      break;
-  }
+int size(Stack *self) {
+  return self->size;
 }
 
 void push(Stack *self, int data) {
-  if (self->head)
-    insert(&self->head, data);
-  else
-    self->head = new(data);
+  if (self->min) {
+    if (data < self->min->data) {
+      Node *tmp = new(data);
+      tmp->next = self->min;
+      self->min = tmp;
+    }
+  } else {
+    self->min = new(data);
+  }
+
+  Node *node = new(data);
+  node->next = self->head;
+  self->head = node;
+  self->size++;
 }
 
 int min(Stack *self) {
-  if (self && self->head)
-    return self->head->data;
+  if(self->min)
+    return self->min->data;
+
+  if (self->head) {
+    int min = self->head->data;
+    Node *tmp = self->head->next;
+
+    while(tmp) {
+      if (tmp->data < min)
+        min = tmp->data;
+      tmp = tmp->next;
+    }
+    return min;
+  }
 
   return (int)NULL;
 }
@@ -65,7 +63,12 @@ int pop(Stack *self) {
 
   Node *current = self->head;
   int data = current->data;
+  if (data == self->min->data) {
+    self->min = self->min->next;
+  }
+
   self->head = current->next;
+  self->size--;
   current->next = NULL;
   free(current);
   return data;
diff --git a/src/01/06/min_stack.h b/src/01/06/min_stack.h
index 442a63b..416a93a 100644
--- a/src/01/06/min_stack.h
+++ b/src/01/06/min_stack.h
@@ -7,6 +7,8 @@ typedef struct node Node;
 
 typedef struct {
   Node *head;
+  Node *min;
+  int size;
 } Stack;
 
 Stack *initialize(void);
diff --git a/src/01/06/min_stack_test.c b/src/01/06/min_stack_test.c
index b892d5f..c796dca 100644
--- a/src/01/06/min_stack_test.c
+++ b/src/01/06/min_stack_test.c
@@ -15,6 +15,74 @@ Ensure(MinStack, when_empty) {
   free(stack);
 }
 
+Ensure(MinStack, when_empty_it_has_a_size_of_zero) {
+  Stack *stack = initialize();
+
+  assert_that(size(stack), is_equal_to(0));
+
+  free(stack);
+}
+
+Ensure(MinStack, when_empty_it_has_a_min_of_null) {
+  Stack *stack = initialize();
+
+  assert_that(min(stack), is_equal_to(NULL));
+
+  free(stack);
+}
+
+Ensure(MinStack, when_a_single_item_is_on_the_stack_it_has_a_size_of_one) {
+  Stack *stack = initialize();
+
+  push(stack, 1);
+
+  assert_that(size(stack), is_equal_to(1));
+
+  free(stack);
+}
+
+Ensure(MinStack, when_a_single_item_is_on_the_stack_it_is_the_min) {
+  Stack *stack = initialize();
+
+  push(stack, -100);
+
+  assert_that(min(stack), is_equal_to(-100));
+
+  free(stack);
+}
+
+Ensure(MinStack, when_a_single_item_is_on_the_stack_when_it_is_popped_off_it_returns_the_item) {
+  Stack *stack = initialize();
+
+  push(stack, 200);
+
+  assert_that(pop(stack), is_equal_to(200));
+
+  free(stack);
+}
+
+Ensure(MinStack, when_a_single_item_is_on_the_stack_when_it_is_popped_off_it_returns_a_size_of_zero) {
+  Stack *stack = initialize();
+
+  push(stack, 200);
+  pop(stack);
+
+  assert_that(size(stack), is_equal_to(0));
+
+  free(stack);
+}
+
+Ensure(MinStack, when_a_single_item_is_on_the_stack_when_it_is_popped_off_it_returns_a_min_of_null) {
+  Stack *stack = initialize();
+
+  push(stack, 200);
+  pop(stack);
+
+  assert_that(min(stack), is_equal_to(NULL));
+
+  free(stack);
+}
+
 Ensure(MinStack, when_pushing_a_single_integer) {
   Stack *stack = initialize();
 
@@ -33,18 +101,23 @@ Ensure(MinStack, when_pushing_multiple_integers_out_of_order) {
 
   push(stack, 2);
   push(stack, 3);
+  push(stack, 4);
   push(stack, 1);
 
-  assert_that(size(stack), is_equal_to(3));
+  assert_that(size(stack), is_equal_to(4));
   assert_that(min(stack), is_equal_to(1));
 
   assert_that(pop(stack), is_equal_to(1));
+  assert_that(size(stack), is_equal_to(3));
+  assert_that(min(stack), is_equal_to(2));
+
+  assert_that(pop(stack), is_equal_to(4));
   assert_that(size(stack), is_equal_to(2));
   assert_that(min(stack), is_equal_to(2));
 
   assert_that(pop(stack), is_equal_to(3));
   assert_that(size(stack), is_equal_to(1));
-  assert_that(min(stack), is_equal_to(3));
+  assert_that(min(stack), is_equal_to(2));
 
   assert_that(pop(stack), is_equal_to(2));
   assert_that(size(stack), is_equal_to(0));
@@ -83,7 +156,16 @@ Ensure(MinStack, when_pushing_duplicate_values_on_to_the_stack) {
 TestSuite *min_stack_tests() {
   TestSuite *suite = create_test_suite();
 
-  add_test_with_context(suite, MinStack, when_empty);
+  add_test_with_context(suite, MinStack, when_empty_it_has_a_size_of_zero);
+  add_test_with_context(suite, MinStack, when_empty_it_has_a_min_of_null);
+
+  add_test_with_context(suite, MinStack, when_a_single_item_is_on_the_stack_it_has_a_size_of_one);
+  add_test_with_context(suite, MinStack, when_a_single_item_is_on_the_stack_it_is_the_min);
+
+  add_test_with_context(suite, MinStack, when_a_single_item_is_on_the_stack_when_it_is_popped_off_it_returns_the_item);
+  add_test_with_context(suite, MinStack, when_a_single_item_is_on_the_stack_when_it_is_popped_off_it_returns_a_size_of_zero);
+  add_test_with_context(suite, MinStack, when_a_single_item_is_on_the_stack_when_it_is_popped_off_it_returns_a_min_of_null);
+
   add_test_with_context(suite, MinStack, when_pushing_a_single_integer);
   add_test_with_context(suite, MinStack, when_pushing_multiple_integers_out_of_order);
   return suite;