From c9575a555c0557be93e6b461c19cf5592e389d26 Mon Sep 17 00:00:00 2001 From: mo khan Date: Sat, 4 Jul 2020 16:52:13 -0600 Subject: split singly_linked_list into separate files --- src/01/02a/Makefile | 37 ++++ src/01/02a/main.c | 6 + src/01/02a/singly_linked_list.c | 78 +++++++++ src/01/02a/singly_linked_list.h | 11 ++ src/01/02a/singly_linked_list_test.c | 197 +++++++++++++++++++++ src/01/02a/swap_singly_linked_list_test.c | 278 ------------------------------ 6 files changed, 329 insertions(+), 278 deletions(-) create mode 100644 src/01/02a/Makefile create mode 100644 src/01/02a/main.c create mode 100644 src/01/02a/singly_linked_list.c create mode 100644 src/01/02a/singly_linked_list.h create mode 100644 src/01/02a/singly_linked_list_test.c delete mode 100644 src/01/02a/swap_singly_linked_list_test.c (limited to 'src/01') diff --git a/src/01/02a/Makefile b/src/01/02a/Makefile new file mode 100644 index 0000000..82cdb5d --- /dev/null +++ b/src/01/02a/Makefile @@ -0,0 +1,37 @@ +#!/usr/bin/make -f +SHELL=/bin/sh + +CC=clang +TEST_LIBS = -lcgreen + +BUILDDIR := build +OBJS := $(addprefix $(BUILDDIR)/,singly_linked_list.o) +TEST_OBJS := $(addprefix $(BUILDDIR)/,singly_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/02a/main.c b/src/01/02a/main.c new file mode 100644 index 0000000..d2dd2af --- /dev/null +++ b/src/01/02a/main.c @@ -0,0 +1,6 @@ +#include + +int main(int argc, char *argv[]) +{ + return 0; +} diff --git a/src/01/02a/singly_linked_list.c b/src/01/02a/singly_linked_list.c new file mode 100644 index 0000000..c4f3bb0 --- /dev/null +++ b/src/01/02a/singly_linked_list.c @@ -0,0 +1,78 @@ +#include "singly_linked_list.h" +#include +#include + +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; +} diff --git a/src/01/02a/singly_linked_list.h b/src/01/02a/singly_linked_list.h new file mode 100644 index 0000000..e240ce4 --- /dev/null +++ b/src/01/02a/singly_linked_list.h @@ -0,0 +1,11 @@ +struct node { + int data; + struct node *next; +}; + +typedef struct node Node; + +Node *initialize(int data); +Node *get(Node *from, int index); +Node *add(Node *head, int data); +void swap(Node **head, int x, int y); diff --git a/src/01/02a/singly_linked_list_test.c b/src/01/02a/singly_linked_list_test.c new file mode 100644 index 0000000..63cbd6a --- /dev/null +++ b/src/01/02a/singly_linked_list_test.c @@ -0,0 +1,197 @@ +#include "singly_linked_list.h" +#include + +Describe(SinglyLinkedList); +BeforeEach(SinglyLinkedList){ } +AfterEach(SinglyLinkedList){ } + +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; +} + +int main(int argc, char **argv) { + TestSuite *suite = create_test_suite(); + add_suite(suite, swap_singly_linked_list_tests()); + return run_test_suite(suite, create_text_reporter()); +} diff --git a/src/01/02a/swap_singly_linked_list_test.c b/src/01/02a/swap_singly_linked_list_test.c deleted file mode 100644 index aedd015..0000000 --- a/src/01/02a/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