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

typedef struct cell {
  int value;
  struct cell *next;
} cell_t;

typedef struct intlist {
  cell_t *head;
  cell_t *last;
} intlist_t;

intlist_t create_list() {
  intlist_t result = { NULL, NULL };
  return result;
}

void free_list(intlist_t *list) {
  cell_t *prev = list->head;
  if (prev != NULL) {
    cell_t *current = prev->next;
    while (current != NULL) {
      free(prev);
      prev = current;
      current = current->next;
    }
    free(prev);
  }
}

void assert_list_empty(const intlist_t *list) {
  assert(list->head == NULL);
  assert(list->last == NULL);
}

void assert_list_contains(const intlist_t *list, size_t size, const int expected_values[]) {
  if (size == 0) {
    assert_list_empty(list);
  } else {
    cell_t *current = list->head;
    for (size_t i = 0; i < size - 1; i++) {
      assert(current->value == expected_values[i]);
      current = current->next;
      assert(current != NULL);
    }
    assert(current->value == expected_values[size - 1]);
    assert(current->next == NULL);
    assert(list->last == current);
  }
}

void test_create_list() {
  intlist_t list = create_list();
  assert_list_empty(&list);
  free_list(&list);
}

void list_add_first(intlist_t *list, int value) {
  cell_t *new_head = (cell_t *) malloc(sizeof(cell_t));
  new_head->value = value;
  new_head->next = list->head;
  list->head = new_head;
  if (list->last == NULL)
    list->last = new_head;
}

void test_add_first() {
  intlist_t list = create_list();

  list_add_first(&list, 56);
  const int expected1[] = { 56 };
  assert_list_contains(&list, 1, expected1);

  list_add_first(&list, 123);
  list_add_first(&list, 5);
  const int expected2[] = { 5, 123, 56 };
  assert_list_contains(&list, 3, expected2);

  free_list(&list);
}

void list_remove_first(intlist_t *list) {
  cell_t *old_head = list->head;
  assert(old_head != NULL);
  list->head = old_head->next;
  if (list->last == old_head)
    list->last = NULL;
  free(old_head);
}

void test_remove_first() {
  intlist_t list = create_list();

  list_add_first(&list, 56);
  list_add_first(&list, 123);
  list_add_first(&list, 5);

  list_remove_first(&list);
  const int expected1[] = { 123, 56 };
  assert_list_contains(&list, 2, expected1);

  list_remove_first(&list);
  const int expected2[] = { 56 };
  assert_list_contains(&list, 1, expected2);

  list_remove_first(&list);
  assert_list_empty(&list);

  free_list(&list);
}

cell_t *list_find(const intlist_t *list, int lookup) {
  for (cell_t *current = list->head; current != NULL; current = current->next) {
    if (current->value == lookup) {
      return current;
    }
  }
  return NULL;
}

void test_list_find() {
  intlist_t list = create_list();

  assert(list_find(&list, 5) == NULL);

  list_add_first(&list, 56);
  list_add_first(&list, 123);
  list_add_first(&list, 5);

  assert(list_find(&list, 56)->value == 56);
  assert(list_find(&list, 123)->value == 123);
  assert(list_find(&list, 5)->value == 5);
  assert(list_find(&list, 4321) == NULL);

  free_list(&list);
}

void list_add_after(intlist_t *list, cell_t *where, int value) {
  if (where == NULL) {
    list_add_first(list, value);
  } else {
    cell_t *cell = (cell_t *) malloc(sizeof(cell_t));
    cell->value = value;
    cell->next = where->next;
    where->next = cell;
    if (list->last == where) {
      list->last = cell;
    }
  }
}

void test_list_add_after() {
  intlist_t list = create_list();

  list_add_after(&list, NULL, 56);
  const int expected1[] = { 56 };
  assert_list_contains(&list, 1, expected1);

  list_add_after(&list, NULL, 123);
  const int expected2[] = { 123, 56 };
  assert_list_contains(&list, 2, expected2);

  list_add_after(&list, list.head, 5);
  const int expected3[] = { 123, 5, 56 };
  assert_list_contains(&list, 3, expected3);

  list_add_after(&list, list.last, 4321);
  const int expected4[] = { 123, 5, 56, 4321 };
  assert_list_contains(&list, 4, expected4);

  free_list(&list);
}

void list_remove_after(intlist_t *list, cell_t *where) {
  if (where == NULL) {
    list_remove_first(list);
  } else {
    cell_t *cell = where->next;
    assert(cell != NULL);
    where->next = cell->next;
    if (list->last == cell) {
      list->last = where;
    }
    free(cell);
  }
}

void test_remove_after() {
  intlist_t list = create_list();

  list_add_first(&list, 56);
  list_add_first(&list, 123);
  list_add_first(&list, 5);
  list_add_first(&list, 4321);

  list_remove_after(&list, NULL);
  const int expected1[] = { 5, 123, 56 };
  assert_list_contains(&list, 3, expected1);

  list_remove_after(&list, list.head);
  const int expected2[] = { 5, 56 };
  assert_list_contains(&list, 2, expected2);

  list_remove_after(&list, list.head);
  const int expected3[] = { 5 };
  assert_list_contains(&list, 1, expected3);

  list_remove_after(&list, NULL);
  assert_list_empty(&list);

  free_list(&list);
}

void list_add_last(intlist_t *list, int value) {
  list_add_after(list, list->last, value);
}

void show_list(const intlist_t *list) {
  printf("[");
  for (cell_t *current = list->head; current != NULL; current = current->next) {
    if (current != list->head) {
      printf(", ");
    }
    printf("%d", current->value);
  }
  printf("]\n");
}

void test_all() {
  test_create_list();
  test_add_first();
  test_remove_first();
  test_list_find();
  test_list_add_after();
  test_remove_after();
}

int main() {
  test_all();

  intlist_t list = create_list();
  list_add_last(&list, 56);
  list_add_last(&list, 65);
  list_add_last(&list, 42);
  list_add_last(&list, 24);
  show_list(&list);
  free_list(&list);

  return 0;
}