From e5f55cfd9dec028d537e6b95c0545ec017ee51a5 Mon Sep 17 00:00:00 2001 From: mo khan Date: Mon, 29 Jun 2020 12:53:12 -0600 Subject: Split files to directories for each section of the assignment --- src/01/01a/priority_queue_test.c | 150 ++++++++ src/01/01b/min_stack_test.c | 171 +++++++++ src/01/02a/swap_singly_linked_list_test.c | 278 ++++++++++++++ src/01/02b/swap_doubly_linked_list_test.c | 588 ++++++++++++++++++++++++++++++ src/01/06/stack_test.c | 168 +++++++++ src/01/min_stack_test.c | 171 --------- src/01/priority_queue_test.c | 150 -------- src/01/stack_test.c | 168 --------- src/01/swap_doubly_linked_list_test.c | 588 ------------------------------ src/01/swap_singly_linked_list_test.c | 278 -------------- 10 files changed, 1355 insertions(+), 1355 deletions(-) create mode 100644 src/01/01a/priority_queue_test.c create mode 100644 src/01/01b/min_stack_test.c create mode 100644 src/01/02a/swap_singly_linked_list_test.c create mode 100644 src/01/02b/swap_doubly_linked_list_test.c create mode 100644 src/01/06/stack_test.c delete mode 100644 src/01/min_stack_test.c delete mode 100644 src/01/priority_queue_test.c delete mode 100644 src/01/stack_test.c delete mode 100644 src/01/swap_doubly_linked_list_test.c delete mode 100644 src/01/swap_singly_linked_list_test.c (limited to 'src') diff --git a/src/01/01a/priority_queue_test.c b/src/01/01a/priority_queue_test.c new file mode 100644 index 0000000..f754c33 --- /dev/null +++ b/src/01/01a/priority_queue_test.c @@ -0,0 +1,150 @@ +#include +#include + +/* +Implement the methods of the priority queue interface using a singly-linked list. + +* `add(x)` +* `deleteMin()` +* `size()` + +Analyze the running time of the `add(x)` and `deletMin()` operations based on this implementation. +*/ +struct node { + int priority; + int data; + struct node *next; +}; + +typedef struct node Node; + +typedef struct { + Node *head; + int size; +} PriorityQueue; + + +// https://en.wikipedia.org/wiki/Priority_queue +static PriorityQueue *initialize() { + PriorityQueue *queue = malloc(sizeof(PriorityQueue)); + queue->size = 0; + queue->head = NULL; + return queue; +} + +static Node *create_node(int priority, int data) { + Node *node = malloc(sizeof(Node)); + node->priority = priority; + node->data = data; + node->next = NULL; + return node; +} + +// This function is constant time O(1) +static int size(PriorityQueue *queue) { + return queue->size; +} + +// This function is linear time O(n) +static void add(PriorityQueue *queue, Node *node) { + queue->size++; + + if (queue->head == NULL) { + queue->head = node; + return; + } + + Node *tmp = queue->head; + Node *prev = NULL; + + while(tmp != NULL) { + if (tmp->data > node->data) { + node->next = tmp; + if (tmp == queue->head) + queue->head = node; + else if (prev != NULL) + prev->next = node; + break; + } + prev = tmp; + tmp = tmp->next; + } +} + +// This function is constant time O(1) +static Node *delete_min(PriorityQueue *queue) { + Node *tmp = queue->head; + queue->head = tmp->next; + return tmp; +} + +static void inspect(PriorityQueue *queue) { + Node *tmp = queue->head; + + while(tmp) { + printf("%d\n", tmp->data); + tmp = tmp->next; + } +} + +static void destroy(PriorityQueue *queue) { + Node *current = queue->head; + Node *tmp; + + while(current) { + tmp = current, current = current->next; + + if (tmp) free(tmp); + } + free(queue); +} + +Describe(PriorityQueue); +BeforeEach(PriorityQueue){ } +AfterEach(PriorityQueue){ } + +Ensure(PriorityQueue, returns_size) { + PriorityQueue *queue = initialize(); + + assert_that(size(queue), is_equal_to(0)); + + destroy(queue); +} + +Ensure(PriorityQueue, adds_a_node) { + PriorityQueue *queue = initialize(); + Node *node = create_node(1, 0); + + add(queue, node); + + assert_that(size(queue), is_equal_to(1)); + + destroy(queue); +} + +Ensure(PriorityQueue, removes_the_node_with_the_lowest_priority){ + PriorityQueue *queue = initialize(); + Node *min = create_node(1, 100); + Node *mid = create_node(2, 200); + Node *max = create_node(3, 300); + + add(queue, max); + add(queue, min); + add(queue, mid); + + assert_that(size(queue), is_equal_to(3)); + assert_that(delete_min(queue), is_equal_to(min)); + assert_that(queue->head, is_equal_to(mid)); + + destroy(queue); +}; + +TestSuite *priority_queue_tests() { + TestSuite *suite = create_test_suite(); + + add_test_with_context(suite, PriorityQueue, returns_size); + add_test_with_context(suite, PriorityQueue, adds_a_node); + add_test_with_context(suite, PriorityQueue, removes_the_node_with_the_lowest_priority); + + return suite; +} diff --git a/src/01/01b/min_stack_test.c b/src/01/01b/min_stack_test.c new file mode 100644 index 0000000..383ae62 --- /dev/null +++ b/src/01/01b/min_stack_test.c @@ -0,0 +1,171 @@ +#include + +/* + Design and implement a `MinStack` data structure that can store + comparable elements and supports the stack operations: + + * `push(x)` + * `pop()` + * `size()` + * `min()` + All operations should run in constant time. + */ + +Describe(MinStack); +BeforeEach(MinStack){ } +AfterEach(MinStack){ } + +struct node { + int data; + struct node *next; +}; + +typedef struct node Node; + +typedef struct { + Node *head; +} Stack; + +static Stack *initialize() { + Stack *self = malloc(sizeof(Stack)); + self->head = NULL; + return self; +} + +static 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; + node->data = data; + return node; +} + +static int compare(int x, int y) { + return x == y ? 0 : (x > y) ? 1 : -1; +} + +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; + } +} + +static void push(Stack *self, int data) { + if (self->head) + insert(&self->head, data); + else + self->head = new(data); +} + +static int min(Stack *self) { + if (self && self->head) + return self->head->data; + + return (int)NULL; +} + +static int pop(Stack *self) { + if (!self->head) + return (int)NULL; + + Node *current = self->head; + int data = current->data; + self->head = current->next; + current->next = NULL; + free(current); + return data; +} + +Ensure(MinStack, when_empty) { + Stack *stack = initialize(); + + assert_that(size(stack), is_equal_to(0)); + assert_that(min(stack), is_equal_to(NULL)); + assert_that(pop(stack), is_equal_to(NULL)); + + free(stack); +} + +Ensure(MinStack, when_pushing_a_single_integer) { + Stack *stack = initialize(); + + push(stack, 1); + + assert_that(size(stack), is_equal_to(1)); + assert_that(min(stack), is_equal_to(1)); + assert_that(pop(stack), is_equal_to(1)); + assert_that(size(stack), is_equal_to(0)); + + free(stack); +} + +Ensure(MinStack, when_pushing_multiple_integers_out_of_order) { + Stack *stack = initialize(); + + push(stack, 2); + push(stack, 3); + push(stack, 1); + + assert_that(size(stack), is_equal_to(3)); + assert_that(min(stack), is_equal_to(1)); + + assert_that(pop(stack), is_equal_to(1)); + assert_that(size(stack), is_equal_to(2)); + + assert_that(pop(stack), is_equal_to(2)); + assert_that(size(stack), is_equal_to(1)); + + assert_that(pop(stack), is_equal_to(3)); + assert_that(size(stack), is_equal_to(0)); + + assert_that(pop(stack), is_equal_to(NULL)); + assert_that(size(stack), is_equal_to(0)); + + free(stack); +} + +Ensure(MinStack, when_pushing_duplicate_values_on_to_the_stack) { + Stack *stack = initialize(); + + push(stack, 2); + push(stack, 1); + push(stack, 2); + + assert_that(size(stack), is_equal_to(3)); + assert_that(min(stack), is_equal_to(1)); + + assert_that(pop(stack), is_equal_to(1)); + assert_that(pop(stack), is_equal_to(2)); + assert_that(pop(stack), is_equal_to(2)); + assert_that(pop(stack), is_equal_to(NULL)); + + free(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_pushing_a_single_integer); + add_test_with_context(suite, MinStack, when_pushing_multiple_integers_out_of_order); + return suite; +} diff --git a/src/01/02a/swap_singly_linked_list_test.c b/src/01/02a/swap_singly_linked_list_test.c new file mode 100644 index 0000000..aedd015 --- /dev/null +++ b/src/01/02a/swap_singly_linked_list_test.c @@ -0,0 +1,278 @@ +#include +/* +Swap two adjacent elements in a list by adjusting +only the links (and not the data) using a: +* singly-linked list +* doubly-linked list +*/ + +Describe(SinglyLinkedList); +BeforeEach(SinglyLinkedList){ } +AfterEach(SinglyLinkedList){ } + +struct node { + int data; + struct node *next; +}; + +typedef struct node Node; + +static void inspect(Node *node) { + if (!node) return; + + printf("*******\n"); + while (node) { + printf("\t%d\n", node->data); + node = node->next; + } + printf("*******\n"); +} + +Node *initialize(int data) { + Node *node = malloc(sizeof(Node)); + node->data = data; + node->next = NULL; + return node; +} + +Node *add(Node *head, int data) { + Node *tail; + Node *tmp = head; + + while(tmp) { + if (!tmp->next) + break; + tmp = tmp->next; + } + tail = tmp; + tail->next = initialize(data); + return tail->next; +} + +Node *get(Node *from, int index) { + if (!from || index < 0) return NULL; + + while(index > 0 && from){ + from = from->next; + index--; + } + return from; +} + +static int size(Node *head) { + int i = 0; + for (Node *tmp = head; tmp && tmp != NULL; tmp = tmp->next) i++; + return i; +} + +void swap(Node **head, int x, int y) { + int count = size(*head); + + if (x == y) return; + if (x >= count) return; + if (y >= count) return; + + Node *xp = get(*head, x - 1); + Node *yp = get(*head, y - 1); + Node *xc = get(*head, x); + Node *yc = get(*head, y); + + if (x == 0) + *head = yc; + else + xp->next = yc; + + if (y == 0) + *head = xc; + else + yp->next = xc; + + Node *tmp = yc->next; + yc->next = xc->next; + xc->next = tmp; +} + +Ensure(SinglyLinkedList, when_getting_head) { + Node *head = initialize(100); + assert_that(get(head, 0), is_equal_to(head)); + free(head); +} + +Ensure(SinglyLinkedList, when_getting_mid) { + Node *head = initialize(100); + + Node *mid = add(head, 200); + add(head, 300); + + assert_that(get(head, 1), is_equal_to(mid)); + assert_that(get(head, 1)->data, is_equal_to(200)); + + free(head); +} + +Ensure(SinglyLinkedList, when_getting_tail) { + Node *head = initialize(100); + + add(head, 200); + Node *tail = add(head, 300); + + assert_that(get(head, 2), is_equal_to(tail)); + + free(head); +} + +Ensure(SinglyLinkedList, when_getting_from_empty_list) { + assert_that(get(NULL, 2), is_equal_to(NULL)); +} + +Ensure(SinglyLinkedList, when_getting_negative_index) { + Node *head = initialize(100); + + assert_that(get(head, -1), is_equal_to(NULL)); + + free(head); +} + +Ensure(SinglyLinkedList, when_getting_index_out_of_range) { + Node *head = initialize(100); + + assert_that(get(head, 1), is_equal_to(NULL)); + + free(head); +} + + +Ensure(SinglyLinkedList, when_swapping_head) { + Node *head = initialize(100); + + add(head, 200); + add(head, 300); + + swap(&head, 0, 1); + + assert_that(get(head, 0), is_non_null); + assert_that(get(head, 0)->data, is_equal_to(200)); + assert_that(get(head, 1), is_non_null); + assert_that(get(head, 1)->data, is_equal_to(100)); + assert_that(get(head, 2), is_non_null); + assert_that(get(head, 2)->data, is_equal_to(300)); + + free(head); +} + +Ensure(SinglyLinkedList, when_swapping_y_head) { + Node *head = initialize(100); + + add(head, 200); + add(head, 300); + + swap(&head, 1, 0); + + assert_that(get(head, 0), is_non_null); + assert_that(get(head, 0)->data, is_equal_to(200)); + assert_that(get(head, 1), is_non_null); + assert_that(get(head, 1)->data, is_equal_to(100)); + assert_that(get(head, 2), is_non_null); + assert_that(get(head, 2)->data, is_equal_to(300)); + + free(head); +} + +Ensure(SinglyLinkedList, when_swapping_mid) { + Node *head = initialize(100); + + add(head, 200); + add(head, 300); + add(head, 400); + + swap(&head, 1, 2); + + assert_that(get(head, 0)->data, is_equal_to(100)); + assert_that(get(head, 1)->data, is_equal_to(300)); + assert_that(get(head, 2)->data, is_equal_to(200)); + assert_that(get(head, 3)->data, is_equal_to(400)); + + free(head); +} + +Ensure(SinglyLinkedList, when_swapping_y_mid) { + Node *head = initialize(100); + + add(head, 200); + add(head, 300); + add(head, 400); + + swap(&head, 2, 1); + + assert_that(get(head, 0)->data, is_equal_to(100)); + assert_that(get(head, 1)->data, is_equal_to(300)); + assert_that(get(head, 2)->data, is_equal_to(200)); + assert_that(get(head, 3)->data, is_equal_to(400)); + + free(head); +} + +Ensure(SinglyLinkedList, when_swapping_tail) { + Node *head = initialize(100); + + add(head, 200); + add(head, 300); + + swap(&head, 1, 2); + + assert_that(get(head, 0), is_non_null); + assert_that(get(head, 0)->data, is_equal_to(100)); + assert_that(get(head, 1), is_non_null); + assert_that(get(head, 1)->data, is_equal_to(300)); + assert_that(get(head, 2), is_non_null); + assert_that(get(head, 2)->data, is_equal_to(200)); + + free(head); +} + +Ensure(SinglyLinkedList, when_swapping_index_out_of_range) { + Node *head = initialize(100); + + add(head, 200); + add(head, 300); + + swap(&head, 1, 3); + + assert_that(get(head, 0)->data, is_equal_to(100)); + assert_that(get(head, 1)->data, is_equal_to(200)); + assert_that(get(head, 2)->data, is_equal_to(300)); + + free(head); +} + +Ensure(SinglyLinkedList, when_swapping_self) { + Node *head = initialize(100); + + swap(&head, 0, 0); + + assert_that(get(head, 0), is_non_null); + assert_that(get(head, 0)->data, is_equal_to(100)); + + free(head); +} + +TestSuite *swap_singly_linked_list_tests() { + TestSuite *suite = create_test_suite(); + + add_test_with_context(suite, SinglyLinkedList, when_getting_head); + add_test_with_context(suite, SinglyLinkedList, when_getting_mid); + add_test_with_context(suite, SinglyLinkedList, when_getting_tail); + add_test_with_context(suite, SinglyLinkedList, when_getting_from_empty_list); + add_test_with_context(suite, SinglyLinkedList, when_getting_negative_index); + add_test_with_context(suite, SinglyLinkedList, when_getting_index_out_of_range); + + add_test_with_context(suite, SinglyLinkedList, when_swapping_head); + add_test_with_context(suite, SinglyLinkedList, when_swapping_y_head); + add_test_with_context(suite, SinglyLinkedList, when_swapping_mid); + add_test_with_context(suite, SinglyLinkedList, when_swapping_y_mid); + add_test_with_context(suite, SinglyLinkedList, when_swapping_tail); + add_test_with_context(suite, SinglyLinkedList, when_swapping_index_out_of_range); + add_test_with_context(suite, SinglyLinkedList, when_swapping_self); + + return suite; +} diff --git a/src/01/02b/swap_doubly_linked_list_test.c b/src/01/02b/swap_doubly_linked_list_test.c new file mode 100644 index 0000000..0520f67 --- /dev/null +++ b/src/01/02b/swap_doubly_linked_list_test.c @@ -0,0 +1,588 @@ +#include +/* +Swap two adjacent elements in a list by adjusting +only the links (and not the data) using a: +* singly-linked list +* doubly-linked list +* +* +* Write a method, `reverse()`, that reverses the order of elements in a `DLList` +*/ + +Describe(DoublyLinkedList); +BeforeEach(DoublyLinkedList){ } +AfterEach(DoublyLinkedList){ } + +struct node { + int data; + struct node *next; + struct node *prev; +}; + +typedef struct node Node; + +static void print(Node *node) { + if (node->prev && node->next) + printf("%d <- %d -> %d\n", node->prev->data, node->data, node->next->data); + else if (node->next) + printf("nil <- %d -> %d\n", node->data, node->next->data); + else + printf("%d <- %d -> nil\n", node->prev->data, node->data); +} + +static void inspect(Node *node) { + if (!node) return; + + printf("*******\n"); + while (node) { + print(node); + node = node->next; + } + printf("*******\n"); +} + +static Node *initialize(int data) { + Node *node = malloc(sizeof(Node)); + node->data = data; + node->next = NULL; + node->prev = NULL; + return node; +} + +static Node *add(Node *head, int data) { + Node *tail; + Node *tmp = head; + + while(tmp) { + if (!tmp->next) + break; + tmp = tmp->next; + } + tail = tmp; + tail->next = initialize(data); + tail->next->prev = tail; + return tail->next; +} + +static Node *get(Node *from, int index) { + if (!from || index < 0) return NULL; + + while(index > 0 && from){ + from = from->next; + index--; + } + return from; +} + +static int size(Node *head) { + int i = 0; + for (Node *tmp = head; tmp && tmp != NULL; tmp = tmp->next) i++; + return i; +} + +static void assign_next(Node *self, Node *other) { + if (self) + self->next = other; + + if (other) + other->prev = self; +} + +static void assign_prev(Node *self, Node *other) { + if (self) + self->prev = other; + + if (other) + other->next = self; +} + +static void swap(Node *x, Node *y) { + if (x == y) return; + if (!x || !y) return; + if (x->prev == y && y->next == x) return swap(y, x); + + Node *xp = x->prev, *xn = x->next, *yp = y->prev, *yn = y->next; + + // if adjacent + if (x->next == y && y->prev == x) { + assign_next(x, yn); + assign_prev(x, y); + assign_prev(y, xp); + } else { + assign_prev(x, yp); + assign_next(x, yn); + assign_prev(y, xp); + assign_next(y, xn); + } +} + +static Node *reverse(Node *head) { + Node *tmp = NULL; + Node *current = head; + + while (current != NULL) { + tmp = current->prev; + current->prev = current->next; + current->next = tmp; + current = current->prev; + } + return tmp ? tmp->prev : head; +} + +Ensure(DoublyLinkedList, when_getting_head) { + Node *head = initialize(100); + assert_that(get(head, 0), is_equal_to(head)); + free(head); +} + +Ensure(DoublyLinkedList, when_getting_mid) { + Node *head = initialize(100); + + Node *mid = add(head, 200); + add(head, 300); + + assert_that(get(head, 1), is_equal_to(mid)); + assert_that(get(head, 1)->data, is_equal_to(200)); + + free(head); +} + +Ensure(DoublyLinkedList, when_getting_tail) { + Node *head = initialize(100); + + add(head, 200); + Node *tail = add(head, 300); + + assert_that(get(head, 2), is_equal_to(tail)); + + free(head); +} + +Ensure(DoublyLinkedList, when_getting_from_empty_list) { + assert_that(get(NULL, 2), is_equal_to(NULL)); +} + +Ensure(DoublyLinkedList, when_getting_negative_index) { + Node *head = initialize(100); + + assert_that(get(head, -1), is_equal_to(NULL)); + + free(head); +} + +Ensure(DoublyLinkedList, when_getting_index_out_of_range) { + Node *head = initialize(100); + + assert_that(get(head, 1), is_equal_to(NULL)); + + free(head); +} + +Ensure(DoublyLinkedList, when_swapping_head_with_non_adjacent_node) { + Node *head = initialize(100); + Node *mid1 = add(head, 200); + Node *mid2 = add(head, 300); + Node *tail = add(head, 400); + + swap(head, mid2); + + assert_that(head->prev, is_equal_to(mid1)); + assert_that(head->data, is_equal_to(100)); + assert_that(head->next, is_equal_to(tail)); + + assert_that(mid1->prev, is_equal_to(mid2)); + assert_that(mid1->data, is_equal_to(200)); + assert_that(mid1->next, is_equal_to(head)); + + assert_that(mid2->prev, is_equal_to(NULL)); + assert_that(mid2->data, is_equal_to(300)); + assert_that(mid2->next, is_equal_to(mid1)); + + assert_that(tail->prev, is_equal_to(head)); + assert_that(tail->data, is_equal_to(400)); + assert_that(tail->next, is_equal_to(NULL)); + + free(head); +} + +Ensure(DoublyLinkedList, when_swapping_head_with_non_adjacent_node_inverted) { + Node *head = initialize(100); + Node *mid1 = add(head, 200); + Node *mid2 = add(head, 300); + Node *tail = add(head, 400); + + swap(mid2, head); + + assert_that(head->prev, is_equal_to(mid1)); + assert_that(head->data, is_equal_to(100)); + assert_that(head->next, is_equal_to(tail)); + + assert_that(mid1->prev, is_equal_to(mid2)); + assert_that(mid1->data, is_equal_to(200)); + assert_that(mid1->next, is_equal_to(head)); + + assert_that(mid2->prev, is_equal_to(NULL)); + assert_that(mid2->data, is_equal_to(300)); + assert_that(mid2->next, is_equal_to(mid1)); + + assert_that(tail->prev, is_equal_to(head)); + assert_that(tail->data, is_equal_to(400)); + assert_that(tail->next, is_equal_to(NULL)); + + free(head); +} + +Ensure(DoublyLinkedList, when_swapping_head_adjacent) { + Node *head = initialize(100); + Node *mid = add(head, 200); + Node *tail = add(head, 300); + + swap(head, mid); + + assert_that(head->prev, is_equal_to(mid)); + assert_that(head->data, is_equal_to(100)); + assert_that(head->next, is_equal_to(tail)); + + assert_that(mid->prev, is_equal_to(NULL)); + assert_that(mid->data, is_equal_to(200)); + assert_that(mid->next, is_equal_to(head)); + + assert_that(tail->prev, is_equal_to(head)); + assert_that(tail->data, is_equal_to(300)); + assert_that(tail->next, is_equal_to(NULL)); + + free(head); +} + +Ensure(DoublyLinkedList, when_swapping_head_adjacent_inverted) { + Node *head = initialize(100); + Node *mid = add(head, 200); + Node *tail = add(head, 300); + + swap(mid, head); + + assert_that(head->prev, is_equal_to(mid)); + assert_that(head->data, is_equal_to(100)); + assert_that(head->next, is_equal_to(tail)); + + assert_that(mid->prev, is_equal_to(NULL)); + assert_that(mid->data, is_equal_to(200)); + assert_that(mid->next, is_equal_to(head)); + + assert_that(tail->prev, is_equal_to(head)); + assert_that(tail->data, is_equal_to(300)); + assert_that(tail->next, is_equal_to(NULL)); + + free(head); +} + +Ensure(DoublyLinkedList, when_swapping_mid) { + Node *head = initialize(100); + Node *mid1 = add(head, 200); + Node *mid2 = add(head, 300); + Node *mid3 = add(head, 400); + Node *tail = add(head, 500); + + swap(mid1, mid3); + + assert_that(head->prev, is_equal_to(NULL)); + assert_that(head->data, is_equal_to(100)); + assert_that(head->next, is_equal_to(mid3)); + + assert_that(mid1->prev, is_equal_to(mid2)); + assert_that(mid1->data, is_equal_to(200)); + assert_that(mid1->next, is_equal_to(tail)); + + assert_that(mid2->prev, is_equal_to(mid3)); + assert_that(mid2->data, is_equal_to(300)); + assert_that(mid2->next, is_equal_to(mid1)); + + assert_that(mid3->prev, is_equal_to(head)); + assert_that(mid3->data, is_equal_to(400)); + assert_that(mid3->next, is_equal_to(mid2)); + + assert_that(tail->prev, is_equal_to(mid1)); + assert_that(tail->data, is_equal_to(500)); + assert_that(tail->next, is_equal_to(NULL)); + + free(head); +} + +Ensure(DoublyLinkedList, when_swapping_y_mid) { + Node *head = initialize(100); + Node *mid1 = add(head, 200); + Node *mid2 = add(head, 300); + Node *mid3 = add(head, 400); + Node *tail = add(head, 500); + + swap(mid3, mid1); + + assert_that(head->prev, is_equal_to(NULL)); + assert_that(head->data, is_equal_to(100)); + assert_that(head->next, is_equal_to(mid3)); + + assert_that(mid1->prev, is_equal_to(mid2)); + assert_that(mid1->data, is_equal_to(200)); + assert_that(mid1->next, is_equal_to(tail)); + + assert_that(mid2->prev, is_equal_to(mid3)); + assert_that(mid2->data, is_equal_to(300)); + assert_that(mid2->next, is_equal_to(mid1)); + + assert_that(mid3->prev, is_equal_to(head)); + assert_that(mid3->data, is_equal_to(400)); + assert_that(mid3->next, is_equal_to(mid2)); + + assert_that(tail->prev, is_equal_to(mid1)); + assert_that(tail->data, is_equal_to(500)); + assert_that(tail->next, is_equal_to(NULL)); + + free(head); +} + +Ensure(DoublyLinkedList, when_swapping_mid_adjacent) { + Node *head = initialize(100); + Node *mid1 = add(head, 200); + Node *mid2 = add(head, 300); + Node *tail = add(head, 400); + + swap(mid1, mid2); + + assert_that(head->prev, is_equal_to(NULL)); + assert_that(head->data, is_equal_to(100)); + assert_that(head->next, is_equal_to(mid2)); + + assert_that(mid1->prev, is_equal_to(mid2)); + assert_that(mid1->data, is_equal_to(200)); + assert_that(mid1->next, is_equal_to(tail)); + + assert_that(mid2->prev, is_equal_to(head)); + assert_that(mid2->data, is_equal_to(300)); + assert_that(mid2->next, is_equal_to(mid1)); + + assert_that(tail->prev, is_equal_to(mid1)); + assert_that(tail->data, is_equal_to(400)); + assert_that(tail->next, is_equal_to(NULL)); + + free(head); +} + +Ensure(DoublyLinkedList, when_swapping_mid_adjacent_y) { + Node *head = initialize(100); + Node *mid1 = add(head, 200); + Node *mid2 = add(head, 300); + Node *tail = add(head, 400); + + swap(mid2, mid1); + + assert_that(head->prev, is_equal_to(NULL)); + assert_that(head->data, is_equal_to(100)); + assert_that(head->next, is_equal_to(mid2)); + + assert_that(mid1->prev, is_equal_to(mid2)); + assert_that(mid1->data, is_equal_to(200)); + assert_that(mid1->next, is_equal_to(tail)); + + assert_that(mid2->prev, is_equal_to(head)); + assert_that(mid2->data, is_equal_to(300)); + assert_that(mid2->next, is_equal_to(mid1)); + + assert_that(tail->prev, is_equal_to(mid1)); + assert_that(tail->data, is_equal_to(400)); + assert_that(tail->next, is_equal_to(NULL)); + + free(head); +} + +Ensure(DoublyLinkedList, when_swapping_tail_adjacent) { + Node *head = initialize(100); + Node *mid = add(head, 200); + Node *tail = add(head, 300); + + swap(mid, tail); + + assert_that(head->prev, is_equal_to(NULL)); + assert_that(head->data, is_equal_to(100)); + assert_that(head->next, is_equal_to(tail)); + + assert_that(mid->prev, is_equal_to(tail)); + assert_that(mid->data, is_equal_to(200)); + assert_that(mid->next, is_equal_to(NULL)); + + assert_that(tail->prev, is_equal_to(head)); + assert_that(tail->data, is_equal_to(300)); + assert_that(tail->next, is_equal_to(mid)); + + free(head); +} + +Ensure(DoublyLinkedList, when_swapping_tail_adjacent_inverted) { + Node *head = initialize(100); + Node *mid = add(head, 200); + Node *tail = add(head, 300); + + swap(tail, mid); + + assert_that(head->prev, is_equal_to(NULL)); + assert_that(head->data, is_equal_to(100)); + assert_that(head->next, is_equal_to(tail)); + + assert_that(mid->prev, is_equal_to(tail)); + assert_that(mid->data, is_equal_to(200)); + assert_that(mid->next, is_equal_to(NULL)); + + assert_that(tail->prev, is_equal_to(head)); + assert_that(tail->data, is_equal_to(300)); + assert_that(tail->next, is_equal_to(mid)); + + free(head); +} + +Ensure(DoublyLinkedList, when_swapping_tail_with_non_adjacent_node) { + Node *head = initialize(100); + Node *mid1 = add(head, 200); + Node *mid2 = add(head, 300); + Node *tail = add(head, 400); + + swap(mid1, tail); + + assert_that(head->prev, is_equal_to(NULL)); + assert_that(head->data, is_equal_to(100)); + assert_that(head->next, is_equal_to(tail)); + + assert_that(mid1->prev, is_equal_to(mid2)); + assert_that(mid1->data, is_equal_to(200)); + assert_that(mid1->next, is_equal_to(NULL)); + + assert_that(mid2->prev, is_equal_to(tail)); + assert_that(mid2->data, is_equal_to(300)); + assert_that(mid2->next, is_equal_to(mid1)); + + assert_that(tail->prev, is_equal_to(head)); + assert_that(tail->data, is_equal_to(400)); + assert_that(tail->next, is_equal_to(mid2)); + + free(head); +} + +Ensure(DoublyLinkedList, when_swapping_tail_with_non_adjacent_node_inverted) { + Node *head = initialize(100); + Node *mid1 = add(head, 200); + Node *mid2 = add(head, 300); + Node *tail = add(head, 400); + + swap(tail, mid1); + + assert_that(head->prev, is_equal_to(NULL)); + assert_that(head->data, is_equal_to(100)); + assert_that(head->next, is_equal_to(tail)); + + assert_that(mid1->prev, is_equal_to(mid2)); + assert_that(mid1->data, is_equal_to(200)); + assert_that(mid1->next, is_equal_to(NULL)); + + assert_that(mid2->prev, is_equal_to(tail)); + assert_that(mid2->data, is_equal_to(300)); + assert_that(mid2->next, is_equal_to(mid1)); + + assert_that(tail->prev, is_equal_to(head)); + assert_that(tail->data, is_equal_to(400)); + assert_that(tail->next, is_equal_to(mid2)); + + free(head); +} + +Ensure(DoublyLinkedList, when_swapping_with_NULL) { + Node *head = initialize(100); + Node *mid = add(head, 200); + Node *tail = add(head, 300); + + swap(mid, NULL); + + assert_that(head->prev, is_equal_to(NULL)); + assert_that(head->data, is_equal_to(100)); + assert_that(head->next, is_equal_to(mid)); + + assert_that(mid->prev, is_equal_to(head)); + assert_that(mid->data, is_equal_to(200)); + assert_that(mid->next, is_equal_to(tail)); + + assert_that(tail->prev, is_equal_to(mid)); + assert_that(tail->data, is_equal_to(300)); + assert_that(tail->next, is_equal_to(NULL)); + + free(head); +} + +Ensure(DoublyLinkedList, when_swapping_self) { + Node *head = initialize(100); + Node *mid = add(head, 200); + Node *tail = add(head, 300); + + swap(mid, mid); + + assert_that(head->prev, is_equal_to(NULL)); + assert_that(head->data, is_equal_to(100)); + + free(head); +} + +Ensure(DoublyLinkedList, when_reversing_a_short_list) { + Node *head = initialize(100); + Node *mid = add(head, 200); + Node *tail = add(head, 300); + + Node *new_head = reverse(head); + + assert_that(new_head->prev, is_equal_to(NULL)); + assert_that(new_head, is_equal_to(tail)); + assert_that(new_head->next, is_equal_to(mid)); + + assert_that(mid->prev, is_equal_to(tail)); + assert_that(mid->next, is_equal_to(head)); + + assert_that(head->prev, is_equal_to(mid)); + assert_that(head->next, is_equal_to(NULL)); + + free(head); +} + +Ensure(DoublyLinkedList, when_reversing_an_empty_list) { + Node *head = initialize(100); + Node *result = reverse(head); + + assert_that(result, is_equal_to(head)); + + free(head); +} + +TestSuite *swap_doubly_linked_list_tests() { + TestSuite *suite = create_test_suite(); + + add_test_with_context(suite, DoublyLinkedList, when_getting_head); + add_test_with_context(suite, DoublyLinkedList, when_getting_mid); + add_test_with_context(suite, DoublyLinkedList, when_getting_tail); + add_test_with_context(suite, DoublyLinkedList, when_getting_from_empty_list); + add_test_with_context(suite, DoublyLinkedList, when_getting_negative_index); + add_test_with_context(suite, DoublyLinkedList, when_getting_index_out_of_range); + + add_test_with_context(suite, DoublyLinkedList, when_swapping_head_adjacent); + add_test_with_context(suite, DoublyLinkedList, when_swapping_head_adjacent_inverted); + add_test_with_context(suite, DoublyLinkedList, when_swapping_head_with_non_adjacent_node); + add_test_with_context(suite, DoublyLinkedList, when_swapping_head_with_non_adjacent_node_inverted); + add_test_with_context(suite, DoublyLinkedList, when_swapping_mid); + add_test_with_context(suite, DoublyLinkedList, when_swapping_y_mid); + add_test_with_context(suite, DoublyLinkedList, when_swapping_mid_adjacent); + add_test_with_context(suite, DoublyLinkedList, when_swapping_mid_adjacent_y); + add_test_with_context(suite, DoublyLinkedList, when_swapping_tail_adjacent); + add_test_with_context(suite, DoublyLinkedList, when_swapping_tail_adjacent_inverted); + add_test_with_context(suite, DoublyLinkedList, when_swapping_tail_with_non_adjacent_node); + add_test_with_context(suite, DoublyLinkedList, when_swapping_tail_with_non_adjacent_node_inverted); + add_test_with_context(suite, DoublyLinkedList, when_swapping_with_NULL); + add_test_with_context(suite, DoublyLinkedList, when_swapping_self); + + add_test_with_context(suite, DoublyLinkedList, when_reversing_a_short_list); + add_test_with_context(suite, DoublyLinkedList, when_reversing_an_empty_list); + + return suite; +} diff --git a/src/01/06/stack_test.c b/src/01/06/stack_test.c new file mode 100644 index 0000000..b34c191 --- /dev/null +++ b/src/01/06/stack_test.c @@ -0,0 +1,168 @@ +#include + +/* +Implement the stack methods using two queues + +* `push(x)` +* `pop()` + +Analyze the running time of the `push(x)` and `pop()` operations based on this implementation. +*/ + +struct node { + int data; + struct node *next; +}; + +typedef struct node Node; + +typedef struct { + Node *head; + int size; +} Queue; + +typedef struct { + Queue *q1; +} Stack; + +static Queue *newQueue(){ + Queue *queue = malloc(sizeof(Queue)); + queue->size = 0; + queue->head = NULL; + return queue; +} + +static Stack *initialize() { + Stack *stack = malloc(sizeof(Stack)); + stack->q1 = newQueue(); + return stack; +} + +Node *newNode(int data) { + Node *node = malloc(sizeof(Node)); + node->data = data; + node->next = NULL; + return node; +} + +void enqueue(Queue *q, int data) { + Node *node = newNode(data); + q->size++; + + if (q->head == NULL) { + q->head = node; + } else { + Node *tail = q->head; + + while (tail->next != NULL) + tail = tail->next; + tail->next = node; + } +} + +int dequeue(Queue *q) { + if (q->head == NULL) return -1; + + Node *node = q->head; + int data = node->data; + + q->head = node->next; + free(node); + return data; +} + +// The running time is linear time. +static void push(Stack *stack, int data) { + enqueue(stack->q1, data); +} + +// The running time is linear time. +static int pop(Stack *stack) { + int count = stack->q1->size - 1; + Queue *tmp = newQueue(); + + for (int i = 0; i < count; i++) + enqueue(tmp, dequeue(stack->q1)); + + int data = dequeue(stack->q1); + free(stack->q1); + stack->q1 = tmp; + return data; +} + +int size(Stack *stack) { + return stack->q1->size; +} + +static void destroy(Stack *stack) { + int count = size(stack); + + for (int i = 0; i < count; i++) + pop(stack); + + free(stack->q1); + free(stack); +} + +static void inspect(Queue *q) { + Node *tmp = q->head; + + if (q->size == 0) { + printf("[]\n"); + return; + } + + printf("["); + for (int i = 0; i < q->size; i++) { + printf("%d,", tmp->data); + tmp = tmp->next; + } + printf("\b]\n"); +} + +Describe(Stack); +BeforeEach(Stack){ } +AfterEach(Stack){ } + +Ensure(Stack, push_onto_stack) { + Stack *stack = initialize(); + + push(stack, 1); + assert_that(size(stack), is_equal_to(1)); + + push(stack, 2); + assert_that(size(stack), is_equal_to(2)); + + destroy(stack); +} + +Ensure(Stack, pop_single_item) { + Stack *stack = initialize(); + + push(stack, 1); + + assert_that(pop(stack), is_equal_to(1)); + destroy(stack); +} + +Ensure(Stack, pop_successive_items) { + Stack *stack = initialize(); + + push(stack, 1); + push(stack, 2); + + assert_that(pop(stack), is_equal_to(2)); + assert_that(pop(stack), is_equal_to(1)); + + destroy(stack); +} + +TestSuite *stack_tests() { + TestSuite *suite = create_test_suite(); + + add_test_with_context(suite, Stack, push_onto_stack); + add_test_with_context(suite, Stack, pop_single_item); + add_test_with_context(suite, Stack, pop_successive_items); + + return suite; +} diff --git a/src/01/min_stack_test.c b/src/01/min_stack_test.c deleted file mode 100644 index 383ae62..0000000 --- a/src/01/min_stack_test.c +++ /dev/null @@ -1,171 +0,0 @@ -#include - -/* - Design and implement a `MinStack` data structure that can store - comparable elements and supports the stack operations: - - * `push(x)` - * `pop()` - * `size()` - * `min()` - All operations should run in constant time. - */ - -Describe(MinStack); -BeforeEach(MinStack){ } -AfterEach(MinStack){ } - -struct node { - int data; - struct node *next; -}; - -typedef struct node Node; - -typedef struct { - Node *head; -} Stack; - -static Stack *initialize() { - Stack *self = malloc(sizeof(Stack)); - self->head = NULL; - return self; -} - -static 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; - node->data = data; - return node; -} - -static int compare(int x, int y) { - return x == y ? 0 : (x > y) ? 1 : -1; -} - -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; - } -} - -static void push(Stack *self, int data) { - if (self->head) - insert(&self->head, data); - else - self->head = new(data); -} - -static int min(Stack *self) { - if (self && self->head) - return self->head->data; - - return (int)NULL; -} - -static int pop(Stack *self) { - if (!self->head) - return (int)NULL; - - Node *current = self->head; - int data = current->data; - self->head = current->next; - current->next = NULL; - free(current); - return data; -} - -Ensure(MinStack, when_empty) { - Stack *stack = initialize(); - - assert_that(size(stack), is_equal_to(0)); - assert_that(min(stack), is_equal_to(NULL)); - assert_that(pop(stack), is_equal_to(NULL)); - - free(stack); -} - -Ensure(MinStack, when_pushing_a_single_integer) { - Stack *stack = initialize(); - - push(stack, 1); - - assert_that(size(stack), is_equal_to(1)); - assert_that(min(stack), is_equal_to(1)); - assert_that(pop(stack), is_equal_to(1)); - assert_that(size(stack), is_equal_to(0)); - - free(stack); -} - -Ensure(MinStack, when_pushing_multiple_integers_out_of_order) { - Stack *stack = initialize(); - - push(stack, 2); - push(stack, 3); - push(stack, 1); - - assert_that(size(stack), is_equal_to(3)); - assert_that(min(stack), is_equal_to(1)); - - assert_that(pop(stack), is_equal_to(1)); - assert_that(size(stack), is_equal_to(2)); - - assert_that(pop(stack), is_equal_to(2)); - assert_that(size(stack), is_equal_to(1)); - - assert_that(pop(stack), is_equal_to(3)); - assert_that(size(stack), is_equal_to(0)); - - assert_that(pop(stack), is_equal_to(NULL)); - assert_that(size(stack), is_equal_to(0)); - - free(stack); -} - -Ensure(MinStack, when_pushing_duplicate_values_on_to_the_stack) { - Stack *stack = initialize(); - - push(stack, 2); - push(stack, 1); - push(stack, 2); - - assert_that(size(stack), is_equal_to(3)); - assert_that(min(stack), is_equal_to(1)); - - assert_that(pop(stack), is_equal_to(1)); - assert_that(pop(stack), is_equal_to(2)); - assert_that(pop(stack), is_equal_to(2)); - assert_that(pop(stack), is_equal_to(NULL)); - - free(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_pushing_a_single_integer); - add_test_with_context(suite, MinStack, when_pushing_multiple_integers_out_of_order); - return suite; -} diff --git a/src/01/priority_queue_test.c b/src/01/priority_queue_test.c deleted file mode 100644 index f754c33..0000000 --- a/src/01/priority_queue_test.c +++ /dev/null @@ -1,150 +0,0 @@ -#include -#include - -/* -Implement the methods of the priority queue interface using a singly-linked list. - -* `add(x)` -* `deleteMin()` -* `size()` - -Analyze the running time of the `add(x)` and `deletMin()` operations based on this implementation. -*/ -struct node { - int priority; - int data; - struct node *next; -}; - -typedef struct node Node; - -typedef struct { - Node *head; - int size; -} PriorityQueue; - - -// https://en.wikipedia.org/wiki/Priority_queue -static PriorityQueue *initialize() { - PriorityQueue *queue = malloc(sizeof(PriorityQueue)); - queue->size = 0; - queue->head = NULL; - return queue; -} - -static Node *create_node(int priority, int data) { - Node *node = malloc(sizeof(Node)); - node->priority = priority; - node->data = data; - node->next = NULL; - return node; -} - -// This function is constant time O(1) -static int size(PriorityQueue *queue) { - return queue->size; -} - -// This function is linear time O(n) -static void add(PriorityQueue *queue, Node *node) { - queue->size++; - - if (queue->head == NULL) { - queue->head = node; - return; - } - - Node *tmp = queue->head; - Node *prev = NULL; - - while(tmp != NULL) { - if (tmp->data > node->data) { - node->next = tmp; - if (tmp == queue->head) - queue->head = node; - else if (prev != NULL) - prev->next = node; - break; - } - prev = tmp; - tmp = tmp->next; - } -} - -// This function is constant time O(1) -static Node *delete_min(PriorityQueue *queue) { - Node *tmp = queue->head; - queue->head = tmp->next; - return tmp; -} - -static void inspect(PriorityQueue *queue) { - Node *tmp = queue->head; - - while(tmp) { - printf("%d\n", tmp->data); - tmp = tmp->next; - } -} - -static void destroy(PriorityQueue *queue) { - Node *current = queue->head; - Node *tmp; - - while(current) { - tmp = current, current = current->next; - - if (tmp) free(tmp); - } - free(queue); -} - -Describe(PriorityQueue); -BeforeEach(PriorityQueue){ } -AfterEach(PriorityQueue){ } - -Ensure(PriorityQueue, returns_size) { - PriorityQueue *queue = initialize(); - - assert_that(size(queue), is_equal_to(0)); - - destroy(queue); -} - -Ensure(PriorityQueue, adds_a_node) { - PriorityQueue *queue = initialize(); - Node *node = create_node(1, 0); - - add(queue, node); - - assert_that(size(queue), is_equal_to(1)); - - destroy(queue); -} - -Ensure(PriorityQueue, removes_the_node_with_the_lowest_priority){ - PriorityQueue *queue = initialize(); - Node *min = create_node(1, 100); - Node *mid = create_node(2, 200); - Node *max = create_node(3, 300); - - add(queue, max); - add(queue, min); - add(queue, mid); - - assert_that(size(queue), is_equal_to(3)); - assert_that(delete_min(queue), is_equal_to(min)); - assert_that(queue->head, is_equal_to(mid)); - - destroy(queue); -}; - -TestSuite *priority_queue_tests() { - TestSuite *suite = create_test_suite(); - - add_test_with_context(suite, PriorityQueue, returns_size); - add_test_with_context(suite, PriorityQueue, adds_a_node); - add_test_with_context(suite, PriorityQueue, removes_the_node_with_the_lowest_priority); - - return suite; -} diff --git a/src/01/stack_test.c b/src/01/stack_test.c deleted file mode 100644 index b34c191..0000000 --- a/src/01/stack_test.c +++ /dev/null @@ -1,168 +0,0 @@ -#include - -/* -Implement the stack methods using two queues - -* `push(x)` -* `pop()` - -Analyze the running time of the `push(x)` and `pop()` operations based on this implementation. -*/ - -struct node { - int data; - struct node *next; -}; - -typedef struct node Node; - -typedef struct { - Node *head; - int size; -} Queue; - -typedef struct { - Queue *q1; -} Stack; - -static Queue *newQueue(){ - Queue *queue = malloc(sizeof(Queue)); - queue->size = 0; - queue->head = NULL; - return queue; -} - -static Stack *initialize() { - Stack *stack = malloc(sizeof(Stack)); - stack->q1 = newQueue(); - return stack; -} - -Node *newNode(int data) { - Node *node = malloc(sizeof(Node)); - node->data = data; - node->next = NULL; - return node; -} - -void enqueue(Queue *q, int data) { - Node *node = newNode(data); - q->size++; - - if (q->head == NULL) { - q->head = node; - } else { - Node *tail = q->head; - - while (tail->next != NULL) - tail = tail->next; - tail->next = node; - } -} - -int dequeue(Queue *q) { - if (q->head == NULL) return -1; - - Node *node = q->head; - int data = node->data; - - q->head = node->next; - free(node); - return data; -} - -// The running time is linear time. -static void push(Stack *stack, int data) { - enqueue(stack->q1, data); -} - -// The running time is linear time. -static int pop(Stack *stack) { - int count = stack->q1->size - 1; - Queue *tmp = newQueue(); - - for (int i = 0; i < count; i++) - enqueue(tmp, dequeue(stack->q1)); - - int data = dequeue(stack->q1); - free(stack->q1); - stack->q1 = tmp; - return data; -} - -int size(Stack *stack) { - return stack->q1->size; -} - -static void destroy(Stack *stack) { - int count = size(stack); - - for (int i = 0; i < count; i++) - pop(stack); - - free(stack->q1); - free(stack); -} - -static void inspect(Queue *q) { - Node *tmp = q->head; - - if (q->size == 0) { - printf("[]\n"); - return; - } - - printf("["); - for (int i = 0; i < q->size; i++) { - printf("%d,", tmp->data); - tmp = tmp->next; - } - printf("\b]\n"); -} - -Describe(Stack); -BeforeEach(Stack){ } -AfterEach(Stack){ } - -Ensure(Stack, push_onto_stack) { - Stack *stack = initialize(); - - push(stack, 1); - assert_that(size(stack), is_equal_to(1)); - - push(stack, 2); - assert_that(size(stack), is_equal_to(2)); - - destroy(stack); -} - -Ensure(Stack, pop_single_item) { - Stack *stack = initialize(); - - push(stack, 1); - - assert_that(pop(stack), is_equal_to(1)); - destroy(stack); -} - -Ensure(Stack, pop_successive_items) { - Stack *stack = initialize(); - - push(stack, 1); - push(stack, 2); - - assert_that(pop(stack), is_equal_to(2)); - assert_that(pop(stack), is_equal_to(1)); - - destroy(stack); -} - -TestSuite *stack_tests() { - TestSuite *suite = create_test_suite(); - - add_test_with_context(suite, Stack, push_onto_stack); - add_test_with_context(suite, Stack, pop_single_item); - add_test_with_context(suite, Stack, pop_successive_items); - - return suite; -} diff --git a/src/01/swap_doubly_linked_list_test.c b/src/01/swap_doubly_linked_list_test.c deleted file mode 100644 index 0520f67..0000000 --- a/src/01/swap_doubly_linked_list_test.c +++ /dev/null @@ -1,588 +0,0 @@ -#include -/* -Swap two adjacent elements in a list by adjusting -only the links (and not the data) using a: -* singly-linked list -* doubly-linked list -* -* -* Write a method, `reverse()`, that reverses the order of elements in a `DLList` -*/ - -Describe(DoublyLinkedList); -BeforeEach(DoublyLinkedList){ } -AfterEach(DoublyLinkedList){ } - -struct node { - int data; - struct node *next; - struct node *prev; -}; - -typedef struct node Node; - -static void print(Node *node) { - if (node->prev && node->next) - printf("%d <- %d -> %d\n", node->prev->data, node->data, node->next->data); - else if (node->next) - printf("nil <- %d -> %d\n", node->data, node->next->data); - else - printf("%d <- %d -> nil\n", node->prev->data, node->data); -} - -static void inspect(Node *node) { - if (!node) return; - - printf("*******\n"); - while (node) { - print(node); - node = node->next; - } - printf("*******\n"); -} - -static Node *initialize(int data) { - Node *node = malloc(sizeof(Node)); - node->data = data; - node->next = NULL; - node->prev = NULL; - return node; -} - -static Node *add(Node *head, int data) { - Node *tail; - Node *tmp = head; - - while(tmp) { - if (!tmp->next) - break; - tmp = tmp->next; - } - tail = tmp; - tail->next = initialize(data); - tail->next->prev = tail; - return tail->next; -} - -static Node *get(Node *from, int index) { - if (!from || index < 0) return NULL; - - while(index > 0 && from){ - from = from->next; - index--; - } - return from; -} - -static int size(Node *head) { - int i = 0; - for (Node *tmp = head; tmp && tmp != NULL; tmp = tmp->next) i++; - return i; -} - -static void assign_next(Node *self, Node *other) { - if (self) - self->next = other; - - if (other) - other->prev = self; -} - -static void assign_prev(Node *self, Node *other) { - if (self) - self->prev = other; - - if (other) - other->next = self; -} - -static void swap(Node *x, Node *y) { - if (x == y) return; - if (!x || !y) return; - if (x->prev == y && y->next == x) return swap(y, x); - - Node *xp = x->prev, *xn = x->next, *yp = y->prev, *yn = y->next; - - // if adjacent - if (x->next == y && y->prev == x) { - assign_next(x, yn); - assign_prev(x, y); - assign_prev(y, xp); - } else { - assign_prev(x, yp); - assign_next(x, yn); - assign_prev(y, xp); - assign_next(y, xn); - } -} - -static Node *reverse(Node *head) { - Node *tmp = NULL; - Node *current = head; - - while (current != NULL) { - tmp = current->prev; - current->prev = current->next; - current->next = tmp; - current = current->prev; - } - return tmp ? tmp->prev : head; -} - -Ensure(DoublyLinkedList, when_getting_head) { - Node *head = initialize(100); - assert_that(get(head, 0), is_equal_to(head)); - free(head); -} - -Ensure(DoublyLinkedList, when_getting_mid) { - Node *head = initialize(100); - - Node *mid = add(head, 200); - add(head, 300); - - assert_that(get(head, 1), is_equal_to(mid)); - assert_that(get(head, 1)->data, is_equal_to(200)); - - free(head); -} - -Ensure(DoublyLinkedList, when_getting_tail) { - Node *head = initialize(100); - - add(head, 200); - Node *tail = add(head, 300); - - assert_that(get(head, 2), is_equal_to(tail)); - - free(head); -} - -Ensure(DoublyLinkedList, when_getting_from_empty_list) { - assert_that(get(NULL, 2), is_equal_to(NULL)); -} - -Ensure(DoublyLinkedList, when_getting_negative_index) { - Node *head = initialize(100); - - assert_that(get(head, -1), is_equal_to(NULL)); - - free(head); -} - -Ensure(DoublyLinkedList, when_getting_index_out_of_range) { - Node *head = initialize(100); - - assert_that(get(head, 1), is_equal_to(NULL)); - - free(head); -} - -Ensure(DoublyLinkedList, when_swapping_head_with_non_adjacent_node) { - Node *head = initialize(100); - Node *mid1 = add(head, 200); - Node *mid2 = add(head, 300); - Node *tail = add(head, 400); - - swap(head, mid2); - - assert_that(head->prev, is_equal_to(mid1)); - assert_that(head->data, is_equal_to(100)); - assert_that(head->next, is_equal_to(tail)); - - assert_that(mid1->prev, is_equal_to(mid2)); - assert_that(mid1->data, is_equal_to(200)); - assert_that(mid1->next, is_equal_to(head)); - - assert_that(mid2->prev, is_equal_to(NULL)); - assert_that(mid2->data, is_equal_to(300)); - assert_that(mid2->next, is_equal_to(mid1)); - - assert_that(tail->prev, is_equal_to(head)); - assert_that(tail->data, is_equal_to(400)); - assert_that(tail->next, is_equal_to(NULL)); - - free(head); -} - -Ensure(DoublyLinkedList, when_swapping_head_with_non_adjacent_node_inverted) { - Node *head = initialize(100); - Node *mid1 = add(head, 200); - Node *mid2 = add(head, 300); - Node *tail = add(head, 400); - - swap(mid2, head); - - assert_that(head->prev, is_equal_to(mid1)); - assert_that(head->data, is_equal_to(100)); - assert_that(head->next, is_equal_to(tail)); - - assert_that(mid1->prev, is_equal_to(mid2)); - assert_that(mid1->data, is_equal_to(200)); - assert_that(mid1->next, is_equal_to(head)); - - assert_that(mid2->prev, is_equal_to(NULL)); - assert_that(mid2->data, is_equal_to(300)); - assert_that(mid2->next, is_equal_to(mid1)); - - assert_that(tail->prev, is_equal_to(head)); - assert_that(tail->data, is_equal_to(400)); - assert_that(tail->next, is_equal_to(NULL)); - - free(head); -} - -Ensure(DoublyLinkedList, when_swapping_head_adjacent) { - Node *head = initialize(100); - Node *mid = add(head, 200); - Node *tail = add(head, 300); - - swap(head, mid); - - assert_that(head->prev, is_equal_to(mid)); - assert_that(head->data, is_equal_to(100)); - assert_that(head->next, is_equal_to(tail)); - - assert_that(mid->prev, is_equal_to(NULL)); - assert_that(mid->data, is_equal_to(200)); - assert_that(mid->next, is_equal_to(head)); - - assert_that(tail->prev, is_equal_to(head)); - assert_that(tail->data, is_equal_to(300)); - assert_that(tail->next, is_equal_to(NULL)); - - free(head); -} - -Ensure(DoublyLinkedList, when_swapping_head_adjacent_inverted) { - Node *head = initialize(100); - Node *mid = add(head, 200); - Node *tail = add(head, 300); - - swap(mid, head); - - assert_that(head->prev, is_equal_to(mid)); - assert_that(head->data, is_equal_to(100)); - assert_that(head->next, is_equal_to(tail)); - - assert_that(mid->prev, is_equal_to(NULL)); - assert_that(mid->data, is_equal_to(200)); - assert_that(mid->next, is_equal_to(head)); - - assert_that(tail->prev, is_equal_to(head)); - assert_that(tail->data, is_equal_to(300)); - assert_that(tail->next, is_equal_to(NULL)); - - free(head); -} - -Ensure(DoublyLinkedList, when_swapping_mid) { - Node *head = initialize(100); - Node *mid1 = add(head, 200); - Node *mid2 = add(head, 300); - Node *mid3 = add(head, 400); - Node *tail = add(head, 500); - - swap(mid1, mid3); - - assert_that(head->prev, is_equal_to(NULL)); - assert_that(head->data, is_equal_to(100)); - assert_that(head->next, is_equal_to(mid3)); - - assert_that(mid1->prev, is_equal_to(mid2)); - assert_that(mid1->data, is_equal_to(200)); - assert_that(mid1->next, is_equal_to(tail)); - - assert_that(mid2->prev, is_equal_to(mid3)); - assert_that(mid2->data, is_equal_to(300)); - assert_that(mid2->next, is_equal_to(mid1)); - - assert_that(mid3->prev, is_equal_to(head)); - assert_that(mid3->data, is_equal_to(400)); - assert_that(mid3->next, is_equal_to(mid2)); - - assert_that(tail->prev, is_equal_to(mid1)); - assert_that(tail->data, is_equal_to(500)); - assert_that(tail->next, is_equal_to(NULL)); - - free(head); -} - -Ensure(DoublyLinkedList, when_swapping_y_mid) { - Node *head = initialize(100); - Node *mid1 = add(head, 200); - Node *mid2 = add(head, 300); - Node *mid3 = add(head, 400); - Node *tail = add(head, 500); - - swap(mid3, mid1); - - assert_that(head->prev, is_equal_to(NULL)); - assert_that(head->data, is_equal_to(100)); - assert_that(head->next, is_equal_to(mid3)); - - assert_that(mid1->prev, is_equal_to(mid2)); - assert_that(mid1->data, is_equal_to(200)); - assert_that(mid1->next, is_equal_to(tail)); - - assert_that(mid2->prev, is_equal_to(mid3)); - assert_that(mid2->data, is_equal_to(300)); - assert_that(mid2->next, is_equal_to(mid1)); - - assert_that(mid3->prev, is_equal_to(head)); - assert_that(mid3->data, is_equal_to(400)); - assert_that(mid3->next, is_equal_to(mid2)); - - assert_that(tail->prev, is_equal_to(mid1)); - assert_that(tail->data, is_equal_to(500)); - assert_that(tail->next, is_equal_to(NULL)); - - free(head); -} - -Ensure(DoublyLinkedList, when_swapping_mid_adjacent) { - Node *head = initialize(100); - Node *mid1 = add(head, 200); - Node *mid2 = add(head, 300); - Node *tail = add(head, 400); - - swap(mid1, mid2); - - assert_that(head->prev, is_equal_to(NULL)); - assert_that(head->data, is_equal_to(100)); - assert_that(head->next, is_equal_to(mid2)); - - assert_that(mid1->prev, is_equal_to(mid2)); - assert_that(mid1->data, is_equal_to(200)); - assert_that(mid1->next, is_equal_to(tail)); - - assert_that(mid2->prev, is_equal_to(head)); - assert_that(mid2->data, is_equal_to(300)); - assert_that(mid2->next, is_equal_to(mid1)); - - assert_that(tail->prev, is_equal_to(mid1)); - assert_that(tail->data, is_equal_to(400)); - assert_that(tail->next, is_equal_to(NULL)); - - free(head); -} - -Ensure(DoublyLinkedList, when_swapping_mid_adjacent_y) { - Node *head = initialize(100); - Node *mid1 = add(head, 200); - Node *mid2 = add(head, 300); - Node *tail = add(head, 400); - - swap(mid2, mid1); - - assert_that(head->prev, is_equal_to(NULL)); - assert_that(head->data, is_equal_to(100)); - assert_that(head->next, is_equal_to(mid2)); - - assert_that(mid1->prev, is_equal_to(mid2)); - assert_that(mid1->data, is_equal_to(200)); - assert_that(mid1->next, is_equal_to(tail)); - - assert_that(mid2->prev, is_equal_to(head)); - assert_that(mid2->data, is_equal_to(300)); - assert_that(mid2->next, is_equal_to(mid1)); - - assert_that(tail->prev, is_equal_to(mid1)); - assert_that(tail->data, is_equal_to(400)); - assert_that(tail->next, is_equal_to(NULL)); - - free(head); -} - -Ensure(DoublyLinkedList, when_swapping_tail_adjacent) { - Node *head = initialize(100); - Node *mid = add(head, 200); - Node *tail = add(head, 300); - - swap(mid, tail); - - assert_that(head->prev, is_equal_to(NULL)); - assert_that(head->data, is_equal_to(100)); - assert_that(head->next, is_equal_to(tail)); - - assert_that(mid->prev, is_equal_to(tail)); - assert_that(mid->data, is_equal_to(200)); - assert_that(mid->next, is_equal_to(NULL)); - - assert_that(tail->prev, is_equal_to(head)); - assert_that(tail->data, is_equal_to(300)); - assert_that(tail->next, is_equal_to(mid)); - - free(head); -} - -Ensure(DoublyLinkedList, when_swapping_tail_adjacent_inverted) { - Node *head = initialize(100); - Node *mid = add(head, 200); - Node *tail = add(head, 300); - - swap(tail, mid); - - assert_that(head->prev, is_equal_to(NULL)); - assert_that(head->data, is_equal_to(100)); - assert_that(head->next, is_equal_to(tail)); - - assert_that(mid->prev, is_equal_to(tail)); - assert_that(mid->data, is_equal_to(200)); - assert_that(mid->next, is_equal_to(NULL)); - - assert_that(tail->prev, is_equal_to(head)); - assert_that(tail->data, is_equal_to(300)); - assert_that(tail->next, is_equal_to(mid)); - - free(head); -} - -Ensure(DoublyLinkedList, when_swapping_tail_with_non_adjacent_node) { - Node *head = initialize(100); - Node *mid1 = add(head, 200); - Node *mid2 = add(head, 300); - Node *tail = add(head, 400); - - swap(mid1, tail); - - assert_that(head->prev, is_equal_to(NULL)); - assert_that(head->data, is_equal_to(100)); - assert_that(head->next, is_equal_to(tail)); - - assert_that(mid1->prev, is_equal_to(mid2)); - assert_that(mid1->data, is_equal_to(200)); - assert_that(mid1->next, is_equal_to(NULL)); - - assert_that(mid2->prev, is_equal_to(tail)); - assert_that(mid2->data, is_equal_to(300)); - assert_that(mid2->next, is_equal_to(mid1)); - - assert_that(tail->prev, is_equal_to(head)); - assert_that(tail->data, is_equal_to(400)); - assert_that(tail->next, is_equal_to(mid2)); - - free(head); -} - -Ensure(DoublyLinkedList, when_swapping_tail_with_non_adjacent_node_inverted) { - Node *head = initialize(100); - Node *mid1 = add(head, 200); - Node *mid2 = add(head, 300); - Node *tail = add(head, 400); - - swap(tail, mid1); - - assert_that(head->prev, is_equal_to(NULL)); - assert_that(head->data, is_equal_to(100)); - assert_that(head->next, is_equal_to(tail)); - - assert_that(mid1->prev, is_equal_to(mid2)); - assert_that(mid1->data, is_equal_to(200)); - assert_that(mid1->next, is_equal_to(NULL)); - - assert_that(mid2->prev, is_equal_to(tail)); - assert_that(mid2->data, is_equal_to(300)); - assert_that(mid2->next, is_equal_to(mid1)); - - assert_that(tail->prev, is_equal_to(head)); - assert_that(tail->data, is_equal_to(400)); - assert_that(tail->next, is_equal_to(mid2)); - - free(head); -} - -Ensure(DoublyLinkedList, when_swapping_with_NULL) { - Node *head = initialize(100); - Node *mid = add(head, 200); - Node *tail = add(head, 300); - - swap(mid, NULL); - - assert_that(head->prev, is_equal_to(NULL)); - assert_that(head->data, is_equal_to(100)); - assert_that(head->next, is_equal_to(mid)); - - assert_that(mid->prev, is_equal_to(head)); - assert_that(mid->data, is_equal_to(200)); - assert_that(mid->next, is_equal_to(tail)); - - assert_that(tail->prev, is_equal_to(mid)); - assert_that(tail->data, is_equal_to(300)); - assert_that(tail->next, is_equal_to(NULL)); - - free(head); -} - -Ensure(DoublyLinkedList, when_swapping_self) { - Node *head = initialize(100); - Node *mid = add(head, 200); - Node *tail = add(head, 300); - - swap(mid, mid); - - assert_that(head->prev, is_equal_to(NULL)); - assert_that(head->data, is_equal_to(100)); - - free(head); -} - -Ensure(DoublyLinkedList, when_reversing_a_short_list) { - Node *head = initialize(100); - Node *mid = add(head, 200); - Node *tail = add(head, 300); - - Node *new_head = reverse(head); - - assert_that(new_head->prev, is_equal_to(NULL)); - assert_that(new_head, is_equal_to(tail)); - assert_that(new_head->next, is_equal_to(mid)); - - assert_that(mid->prev, is_equal_to(tail)); - assert_that(mid->next, is_equal_to(head)); - - assert_that(head->prev, is_equal_to(mid)); - assert_that(head->next, is_equal_to(NULL)); - - free(head); -} - -Ensure(DoublyLinkedList, when_reversing_an_empty_list) { - Node *head = initialize(100); - Node *result = reverse(head); - - assert_that(result, is_equal_to(head)); - - free(head); -} - -TestSuite *swap_doubly_linked_list_tests() { - TestSuite *suite = create_test_suite(); - - add_test_with_context(suite, DoublyLinkedList, when_getting_head); - add_test_with_context(suite, DoublyLinkedList, when_getting_mid); - add_test_with_context(suite, DoublyLinkedList, when_getting_tail); - add_test_with_context(suite, DoublyLinkedList, when_getting_from_empty_list); - add_test_with_context(suite, DoublyLinkedList, when_getting_negative_index); - add_test_with_context(suite, DoublyLinkedList, when_getting_index_out_of_range); - - add_test_with_context(suite, DoublyLinkedList, when_swapping_head_adjacent); - add_test_with_context(suite, DoublyLinkedList, when_swapping_head_adjacent_inverted); - add_test_with_context(suite, DoublyLinkedList, when_swapping_head_with_non_adjacent_node); - add_test_with_context(suite, DoublyLinkedList, when_swapping_head_with_non_adjacent_node_inverted); - add_test_with_context(suite, DoublyLinkedList, when_swapping_mid); - add_test_with_context(suite, DoublyLinkedList, when_swapping_y_mid); - add_test_with_context(suite, DoublyLinkedList, when_swapping_mid_adjacent); - add_test_with_context(suite, DoublyLinkedList, when_swapping_mid_adjacent_y); - add_test_with_context(suite, DoublyLinkedList, when_swapping_tail_adjacent); - add_test_with_context(suite, DoublyLinkedList, when_swapping_tail_adjacent_inverted); - add_test_with_context(suite, DoublyLinkedList, when_swapping_tail_with_non_adjacent_node); - add_test_with_context(suite, DoublyLinkedList, when_swapping_tail_with_non_adjacent_node_inverted); - add_test_with_context(suite, DoublyLinkedList, when_swapping_with_NULL); - add_test_with_context(suite, DoublyLinkedList, when_swapping_self); - - add_test_with_context(suite, DoublyLinkedList, when_reversing_a_short_list); - add_test_with_context(suite, DoublyLinkedList, when_reversing_an_empty_list); - - return suite; -} diff --git a/src/01/swap_singly_linked_list_test.c b/src/01/swap_singly_linked_list_test.c deleted file mode 100644 index aedd015..0000000 --- a/src/01/swap_singly_linked_list_test.c +++ /dev/null @@ -1,278 +0,0 @@ -#include -/* -Swap two adjacent elements in a list by adjusting -only the links (and not the data) using a: -* singly-linked list -* doubly-linked list -*/ - -Describe(SinglyLinkedList); -BeforeEach(SinglyLinkedList){ } -AfterEach(SinglyLinkedList){ } - -struct node { - int data; - struct node *next; -}; - -typedef struct node Node; - -static void inspect(Node *node) { - if (!node) return; - - printf("*******\n"); - while (node) { - printf("\t%d\n", node->data); - node = node->next; - } - printf("*******\n"); -} - -Node *initialize(int data) { - Node *node = malloc(sizeof(Node)); - node->data = data; - node->next = NULL; - return node; -} - -Node *add(Node *head, int data) { - Node *tail; - Node *tmp = head; - - while(tmp) { - if (!tmp->next) - break; - tmp = tmp->next; - } - tail = tmp; - tail->next = initialize(data); - return tail->next; -} - -Node *get(Node *from, int index) { - if (!from || index < 0) return NULL; - - while(index > 0 && from){ - from = from->next; - index--; - } - return from; -} - -static int size(Node *head) { - int i = 0; - for (Node *tmp = head; tmp && tmp != NULL; tmp = tmp->next) i++; - return i; -} - -void swap(Node **head, int x, int y) { - int count = size(*head); - - if (x == y) return; - if (x >= count) return; - if (y >= count) return; - - Node *xp = get(*head, x - 1); - Node *yp = get(*head, y - 1); - Node *xc = get(*head, x); - Node *yc = get(*head, y); - - if (x == 0) - *head = yc; - else - xp->next = yc; - - if (y == 0) - *head = xc; - else - yp->next = xc; - - Node *tmp = yc->next; - yc->next = xc->next; - xc->next = tmp; -} - -Ensure(SinglyLinkedList, when_getting_head) { - Node *head = initialize(100); - assert_that(get(head, 0), is_equal_to(head)); - free(head); -} - -Ensure(SinglyLinkedList, when_getting_mid) { - Node *head = initialize(100); - - Node *mid = add(head, 200); - add(head, 300); - - assert_that(get(head, 1), is_equal_to(mid)); - assert_that(get(head, 1)->data, is_equal_to(200)); - - free(head); -} - -Ensure(SinglyLinkedList, when_getting_tail) { - Node *head = initialize(100); - - add(head, 200); - Node *tail = add(head, 300); - - assert_that(get(head, 2), is_equal_to(tail)); - - free(head); -} - -Ensure(SinglyLinkedList, when_getting_from_empty_list) { - assert_that(get(NULL, 2), is_equal_to(NULL)); -} - -Ensure(SinglyLinkedList, when_getting_negative_index) { - Node *head = initialize(100); - - assert_that(get(head, -1), is_equal_to(NULL)); - - free(head); -} - -Ensure(SinglyLinkedList, when_getting_index_out_of_range) { - Node *head = initialize(100); - - assert_that(get(head, 1), is_equal_to(NULL)); - - free(head); -} - - -Ensure(SinglyLinkedList, when_swapping_head) { - Node *head = initialize(100); - - add(head, 200); - add(head, 300); - - swap(&head, 0, 1); - - assert_that(get(head, 0), is_non_null); - assert_that(get(head, 0)->data, is_equal_to(200)); - assert_that(get(head, 1), is_non_null); - assert_that(get(head, 1)->data, is_equal_to(100)); - assert_that(get(head, 2), is_non_null); - assert_that(get(head, 2)->data, is_equal_to(300)); - - free(head); -} - -Ensure(SinglyLinkedList, when_swapping_y_head) { - Node *head = initialize(100); - - add(head, 200); - add(head, 300); - - swap(&head, 1, 0); - - assert_that(get(head, 0), is_non_null); - assert_that(get(head, 0)->data, is_equal_to(200)); - assert_that(get(head, 1), is_non_null); - assert_that(get(head, 1)->data, is_equal_to(100)); - assert_that(get(head, 2), is_non_null); - assert_that(get(head, 2)->data, is_equal_to(300)); - - free(head); -} - -Ensure(SinglyLinkedList, when_swapping_mid) { - Node *head = initialize(100); - - add(head, 200); - add(head, 300); - add(head, 400); - - swap(&head, 1, 2); - - assert_that(get(head, 0)->data, is_equal_to(100)); - assert_that(get(head, 1)->data, is_equal_to(300)); - assert_that(get(head, 2)->data, is_equal_to(200)); - assert_that(get(head, 3)->data, is_equal_to(400)); - - free(head); -} - -Ensure(SinglyLinkedList, when_swapping_y_mid) { - Node *head = initialize(100); - - add(head, 200); - add(head, 300); - add(head, 400); - - swap(&head, 2, 1); - - assert_that(get(head, 0)->data, is_equal_to(100)); - assert_that(get(head, 1)->data, is_equal_to(300)); - assert_that(get(head, 2)->data, is_equal_to(200)); - assert_that(get(head, 3)->data, is_equal_to(400)); - - free(head); -} - -Ensure(SinglyLinkedList, when_swapping_tail) { - Node *head = initialize(100); - - add(head, 200); - add(head, 300); - - swap(&head, 1, 2); - - assert_that(get(head, 0), is_non_null); - assert_that(get(head, 0)->data, is_equal_to(100)); - assert_that(get(head, 1), is_non_null); - assert_that(get(head, 1)->data, is_equal_to(300)); - assert_that(get(head, 2), is_non_null); - assert_that(get(head, 2)->data, is_equal_to(200)); - - free(head); -} - -Ensure(SinglyLinkedList, when_swapping_index_out_of_range) { - Node *head = initialize(100); - - add(head, 200); - add(head, 300); - - swap(&head, 1, 3); - - assert_that(get(head, 0)->data, is_equal_to(100)); - assert_that(get(head, 1)->data, is_equal_to(200)); - assert_that(get(head, 2)->data, is_equal_to(300)); - - free(head); -} - -Ensure(SinglyLinkedList, when_swapping_self) { - Node *head = initialize(100); - - swap(&head, 0, 0); - - assert_that(get(head, 0), is_non_null); - assert_that(get(head, 0)->data, is_equal_to(100)); - - free(head); -} - -TestSuite *swap_singly_linked_list_tests() { - TestSuite *suite = create_test_suite(); - - add_test_with_context(suite, SinglyLinkedList, when_getting_head); - add_test_with_context(suite, SinglyLinkedList, when_getting_mid); - add_test_with_context(suite, SinglyLinkedList, when_getting_tail); - add_test_with_context(suite, SinglyLinkedList, when_getting_from_empty_list); - add_test_with_context(suite, SinglyLinkedList, when_getting_negative_index); - add_test_with_context(suite, SinglyLinkedList, when_getting_index_out_of_range); - - add_test_with_context(suite, SinglyLinkedList, when_swapping_head); - add_test_with_context(suite, SinglyLinkedList, when_swapping_y_head); - add_test_with_context(suite, SinglyLinkedList, when_swapping_mid); - add_test_with_context(suite, SinglyLinkedList, when_swapping_y_mid); - add_test_with_context(suite, SinglyLinkedList, when_swapping_tail); - add_test_with_context(suite, SinglyLinkedList, when_swapping_index_out_of_range); - add_test_with_context(suite, SinglyLinkedList, when_swapping_self); - - return suite; -} -- cgit v1.2.3