From fd62033e4c79cf2753ba3518af709c7a4102f3bc Mon Sep 17 00:00:00 2001 From: mo khan Date: Sat, 4 Jul 2020 17:56:01 -0600 Subject: Split doubly linked list into separate files --- src/01/02b/Makefile | 37 ++ src/01/02b/doubly_linked_list.c | 112 ++++++ src/01/02b/doubly_linked_list.h | 13 + src/01/02b/doubly_linked_list_test.c | 480 ++++++++++++++++++++++++ src/01/02b/main.c | 15 + src/01/02b/swap_doubly_linked_list_test.c | 588 ------------------------------ 6 files changed, 657 insertions(+), 588 deletions(-) create mode 100644 src/01/02b/Makefile create mode 100644 src/01/02b/doubly_linked_list.c create mode 100644 src/01/02b/doubly_linked_list.h create mode 100644 src/01/02b/doubly_linked_list_test.c create mode 100644 src/01/02b/main.c delete mode 100644 src/01/02b/swap_doubly_linked_list_test.c (limited to 'src/01') diff --git a/src/01/02b/Makefile b/src/01/02b/Makefile new file mode 100644 index 0000000..fd91d8e --- /dev/null +++ b/src/01/02b/Makefile @@ -0,0 +1,37 @@ +#!/usr/bin/make -f +SHELL=/bin/sh + +CC=clang +TEST_LIBS = -lcgreen + +BUILDDIR := build +OBJS := $(addprefix $(BUILDDIR)/,doubly_linked_list.o) +TEST_OBJS := $(addprefix $(BUILDDIR)/,doubly_linked_list_test.o) + +$(BUILDDIR)/%.o : %.c + $(COMPILE.c) $(OUTPUT_OPTION) $< + +.PHONY: all +all: $(OBJS) $(BUILDDIR)/main.o + $(CC) $(OBJS) $(BUILDDIR)/main.o -o $(BUILDDIR)/program + +.PHONY: test +test: $(OBJS) $(TEST_OBJS) + $(CC) $(OBJS) $(TEST_OBJS) $(TEST_LIBS) -o $(BUILDDIR)/test + +$(OBJS): | $(BUILDDIR) + +$(TEST_OBJS): | $(BUILDDIR) + +$(BUILDDIR): + mkdir $(BUILDDIR) + +.PHONY: clean +clean: + rm -fr build + +run : all + ./build/program + +run_test : test + cgreen-runner -c -v $(BUILDDIR)/test diff --git a/src/01/02b/doubly_linked_list.c b/src/01/02b/doubly_linked_list.c new file mode 100644 index 0000000..88e49ee --- /dev/null +++ b/src/01/02b/doubly_linked_list.c @@ -0,0 +1,112 @@ +#include "doubly_linked_list.h" +#include +#include + +Node *initialize(int data) { + Node *node = malloc(sizeof(Node)); + node->data = data; + node->next = NULL; + node->prev = 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); + tail->next->prev = tail; + 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; +} + +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; +} + +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); + } +} + +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; +} + +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"); +} + diff --git a/src/01/02b/doubly_linked_list.h b/src/01/02b/doubly_linked_list.h new file mode 100644 index 0000000..63470c4 --- /dev/null +++ b/src/01/02b/doubly_linked_list.h @@ -0,0 +1,13 @@ +struct node { + int data; + struct node *next; + struct node *prev; +}; + +typedef struct node Node; + +Node *initialize(int data); +Node *add(Node *head, int data); +Node *get(Node *from, int index); +void swap(Node *x, Node *y); +Node *reverse(Node *head); diff --git a/src/01/02b/doubly_linked_list_test.c b/src/01/02b/doubly_linked_list_test.c new file mode 100644 index 0000000..ffc89cc --- /dev/null +++ b/src/01/02b/doubly_linked_list_test.c @@ -0,0 +1,480 @@ +#include +#include "doubly_linked_list.h" + +/* +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){ } + +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; +} + +int main(int argc, char **argv) { + TestSuite *suite = create_test_suite(); + add_suite(suite, swap_doubly_linked_list_tests()); + return run_test_suite(suite, create_text_reporter()); +} diff --git a/src/01/02b/main.c b/src/01/02b/main.c new file mode 100644 index 0000000..8249019 --- /dev/null +++ b/src/01/02b/main.c @@ -0,0 +1,15 @@ +#include "doubly_linked_list.h" +#include +#include + +int next(void) { + return rand() % 100; +} + +int main(int argc, char *argv[]) +{ + printf("=== COMP-272 - Assignment 1 - Question 2b ===\n"); + Node *head = initialize(next()); + + return 0; +} diff --git a/src/01/02b/swap_doubly_linked_list_test.c b/src/01/02b/swap_doubly_linked_list_test.c deleted file mode 100644 index 0520f67..0000000 --- a/src/01/02b/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; -} -- cgit v1.2.3