diff options
| -rw-r--r-- | Makefile | 11 | ||||
| -rw-r--r-- | assignments/01/swap_doubly_linked_list_test.c | 281 | ||||
| -rw-r--r-- | assignments/01/swap_singly_linked_list_test.c (renamed from assignments/01/swap_linked_list_test.c) | 60 | ||||
| -rw-r--r-- | main.c | 2 |
4 files changed, 320 insertions, 34 deletions
@@ -13,8 +13,8 @@ doc : doc/ run : main ./main -main : main.o words_test.o words.o priority_queue_test.o stack_test.o swap_linked_list_test.o - $(CC) main.o words_test.o words.o priority_queue_test.o stack_test.o swap_linked_list_test.o -lcgreen -o main +main : main.o words_test.o words.o priority_queue_test.o stack_test.o swap_singly_linked_list_test.o swap_doubly_linked_list_test.o + $(CC) main.o words_test.o words.o priority_queue_test.o stack_test.o swap_singly_linked_list_test.o swap_doubly_linked_list_test.o -lcgreen -o main main.o : main.c $(CC) -c main.c @@ -31,8 +31,11 @@ priority_queue_test.o : assignments/01/priority_queue_test.c stack_test.o : assignments/01/stack_test.c $(CC) -c assignments/01/stack_test.c -swap_linked_list_test.o : assignments/01/swap_linked_list_test.c - $(CC) -c assignments/01/swap_linked_list_test.c +swap_singly_linked_list_test.o : assignments/01/swap_singly_linked_list_test.c + $(CC) -c assignments/01/swap_singly_linked_list_test.c + +swap_doubly_linked_list_test.o : assignments/01/swap_doubly_linked_list_test.c + $(CC) -c assignments/01/swap_doubly_linked_list_test.c clean: rm -f main *.o diff --git a/assignments/01/swap_doubly_linked_list_test.c b/assignments/01/swap_doubly_linked_list_test.c new file mode 100644 index 0000000..9e59981 --- /dev/null +++ b/assignments/01/swap_doubly_linked_list_test.c @@ -0,0 +1,281 @@ +#include <cgreen/cgreen.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 +*/ + +Describe(DoublyLinkedList); +BeforeEach(DoublyLinkedList){ } +AfterEach(DoublyLinkedList){ } + +struct node { + int data; + struct node *next; + struct node *prev; +}; + +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"); +} + +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 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(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) { + 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(DoublyLinkedList, 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(DoublyLinkedList, 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(DoublyLinkedList, 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(DoublyLinkedList, 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(DoublyLinkedList, 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(DoublyLinkedList, 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_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); + add_test_with_context(suite, DoublyLinkedList, when_swapping_y_head); + 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_tail); + add_test_with_context(suite, DoublyLinkedList, when_swapping_index_out_of_range); + add_test_with_context(suite, DoublyLinkedList, when_swapping_self); + + return suite; +} diff --git a/assignments/01/swap_linked_list_test.c b/assignments/01/swap_singly_linked_list_test.c index 7a5fdfb..aedd015 100644 --- a/assignments/01/swap_linked_list_test.c +++ b/assignments/01/swap_singly_linked_list_test.c @@ -6,9 +6,9 @@ only the links (and not the data) using a: * doubly-linked list */ -Describe(SwapLinkedList); -BeforeEach(SwapLinkedList){ } -AfterEach(SwapLinkedList){ } +Describe(SinglyLinkedList); +BeforeEach(SinglyLinkedList){ } +AfterEach(SinglyLinkedList){ } struct node { int data; @@ -92,13 +92,13 @@ void swap(Node **head, int x, int y) { xc->next = tmp; } -Ensure(SwapLinkedList, when_getting_head) { +Ensure(SinglyLinkedList, when_getting_head) { Node *head = initialize(100); assert_that(get(head, 0), is_equal_to(head)); free(head); } -Ensure(SwapLinkedList, when_getting_mid) { +Ensure(SinglyLinkedList, when_getting_mid) { Node *head = initialize(100); Node *mid = add(head, 200); @@ -110,7 +110,7 @@ Ensure(SwapLinkedList, when_getting_mid) { free(head); } -Ensure(SwapLinkedList, when_getting_tail) { +Ensure(SinglyLinkedList, when_getting_tail) { Node *head = initialize(100); add(head, 200); @@ -121,11 +121,11 @@ Ensure(SwapLinkedList, when_getting_tail) { free(head); } -Ensure(SwapLinkedList, when_getting_from_empty_list) { +Ensure(SinglyLinkedList, when_getting_from_empty_list) { assert_that(get(NULL, 2), is_equal_to(NULL)); } -Ensure(SwapLinkedList, when_getting_negative_index) { +Ensure(SinglyLinkedList, when_getting_negative_index) { Node *head = initialize(100); assert_that(get(head, -1), is_equal_to(NULL)); @@ -133,7 +133,7 @@ Ensure(SwapLinkedList, when_getting_negative_index) { free(head); } -Ensure(SwapLinkedList, when_getting_index_out_of_range) { +Ensure(SinglyLinkedList, when_getting_index_out_of_range) { Node *head = initialize(100); assert_that(get(head, 1), is_equal_to(NULL)); @@ -142,7 +142,7 @@ Ensure(SwapLinkedList, when_getting_index_out_of_range) { } -Ensure(SwapLinkedList, when_swapping_head) { +Ensure(SinglyLinkedList, when_swapping_head) { Node *head = initialize(100); add(head, 200); @@ -160,7 +160,7 @@ Ensure(SwapLinkedList, when_swapping_head) { free(head); } -Ensure(SwapLinkedList, when_swapping_y_head) { +Ensure(SinglyLinkedList, when_swapping_y_head) { Node *head = initialize(100); add(head, 200); @@ -178,7 +178,7 @@ Ensure(SwapLinkedList, when_swapping_y_head) { free(head); } -Ensure(SwapLinkedList, when_swapping_mid) { +Ensure(SinglyLinkedList, when_swapping_mid) { Node *head = initialize(100); add(head, 200); @@ -195,7 +195,7 @@ Ensure(SwapLinkedList, when_swapping_mid) { free(head); } -Ensure(SwapLinkedList, when_swapping_y_mid) { +Ensure(SinglyLinkedList, when_swapping_y_mid) { Node *head = initialize(100); add(head, 200); @@ -212,7 +212,7 @@ Ensure(SwapLinkedList, when_swapping_y_mid) { free(head); } -Ensure(SwapLinkedList, when_swapping_tail) { +Ensure(SinglyLinkedList, when_swapping_tail) { Node *head = initialize(100); add(head, 200); @@ -230,7 +230,7 @@ Ensure(SwapLinkedList, when_swapping_tail) { free(head); } -Ensure(SwapLinkedList, when_swapping_index_out_of_range) { +Ensure(SinglyLinkedList, when_swapping_index_out_of_range) { Node *head = initialize(100); add(head, 200); @@ -245,7 +245,7 @@ Ensure(SwapLinkedList, when_swapping_index_out_of_range) { free(head); } -Ensure(SwapLinkedList, when_swapping_self) { +Ensure(SinglyLinkedList, when_swapping_self) { Node *head = initialize(100); swap(&head, 0, 0); @@ -259,20 +259,20 @@ Ensure(SwapLinkedList, when_swapping_self) { TestSuite *swap_singly_linked_list_tests() { TestSuite *suite = create_test_suite(); - add_test_with_context(suite, SwapLinkedList, when_getting_head); - add_test_with_context(suite, SwapLinkedList, when_getting_mid); - add_test_with_context(suite, SwapLinkedList, when_getting_tail); - add_test_with_context(suite, SwapLinkedList, when_getting_from_empty_list); - add_test_with_context(suite, SwapLinkedList, when_getting_negative_index); - add_test_with_context(suite, SwapLinkedList, when_getting_index_out_of_range); - - add_test_with_context(suite, SwapLinkedList, when_swapping_head); - add_test_with_context(suite, SwapLinkedList, when_swapping_y_head); - add_test_with_context(suite, SwapLinkedList, when_swapping_mid); - add_test_with_context(suite, SwapLinkedList, when_swapping_y_mid); - add_test_with_context(suite, SwapLinkedList, when_swapping_tail); - add_test_with_context(suite, SwapLinkedList, when_swapping_index_out_of_range); - add_test_with_context(suite, SwapLinkedList, when_swapping_self); + 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; } @@ -4,6 +4,7 @@ TestSuite *words_tests(); TestSuite *priority_queue_tests(); TestSuite *stack_tests(); TestSuite *swap_singly_linked_list_tests(); +TestSuite *swap_doubly_linked_list_tests(); int main(int argc, char **argv) { TestSuite *suite = create_test_suite(); @@ -12,6 +13,7 @@ int main(int argc, char **argv) { add_suite(suite, priority_queue_tests()); add_suite(suite, stack_tests()); add_suite(suite, swap_singly_linked_list_tests()); + add_suite(suite, swap_doubly_linked_list_tests()); if (argc > 1) return run_single_test(suite, argv[1], create_text_reporter()); |