summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--src/01/05/README.md37
-rw-r--r--src/01/05/doubly_linked_list_test.c398
-rw-r--r--src/01/05/main.c26
3 files changed, 46 insertions, 415 deletions
diff --git a/src/01/05/README.md b/src/01/05/README.md
index 11b72e1..0aa0fd6 100644
--- a/src/01/05/README.md
+++ b/src/01/05/README.md
@@ -5,9 +5,44 @@ Student ID: 3431709
## Problem Statement
-Write a method, reverse(), that reverses the order of elements in a DLList.
+Write a method, `reverse()`, that reverses the order of elements in a DLList.
## Description of the Code
+
+To reverse the linked list I chose to iterate from the head of the
+linked list to the tail and swap the next and previous pointers while
+iterating.
+
+After iterating through the list, the previous tail becomes the new head of the list.
+
## Errors and Warnings
+
+```bash
+モ make run_test
+clang build/doubly_linked_list.o build/doubly_linked_list_test.o -lcgreen -o build/test
+cgreen-runner -c -v build/test
+Discovered DoublyLinkedList:when_reversing_a_short_list (CgreenSpec__DoublyLinkedList__when_reversing_a_short_list__)
+Discovered DoublyLinkedList:when_reversing_an_empty_list (CgreenSpec__DoublyLinkedList__when_reversing_an_empty_list__)
+Discovered 2 test(s)
+Opening [build/test] to run all 2 discovered tests ...
+Running "test" (2 tests)...
+ "DoublyLinkedList": 8 passes in 2ms.
+ Completed "test": 8 passes in 2ms.
+```
+
## Sample Input and Output
+
+```bash
+モ make run
+clang -c -o build/main.o main.c
+clang build/doubly_linked_list.o build/main.o -o build/program
+./build/program
+=== COMP-272 - Assignment 1 - Question 5 ===
+Before:
+ [ (nil<0>0) (0<0>1) (0<1>2) (1<2>3) (2<3>4) (3<4>5) (4<5>6) (5<6>7) (6<7>8) (7<8>9) (8<9>nil) ]
+ Reversing...
+ After:
+ [ (nil<9>8) (9<8>7) (8<7>6) (7<6>5) (6<5>4) (5<4>3) (4<3>2) (3<2>1) (2<1>0) (1<0>0) (0<0>nil) ]
+```
+
## Discussion
diff --git a/src/01/05/doubly_linked_list_test.c b/src/01/05/doubly_linked_list_test.c
index 3ef4c29..e674917 100644
--- a/src/01/05/doubly_linked_list_test.c
+++ b/src/01/05/doubly_linked_list_test.c
@@ -5,404 +5,6 @@ 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);
diff --git a/src/01/05/main.c b/src/01/05/main.c
index 10e18e3..ec56b42 100644
--- a/src/01/05/main.c
+++ b/src/01/05/main.c
@@ -8,27 +8,21 @@ int next(void) {
int main(int argc, char *argv[])
{
- printf("=== COMP-272 - Assignment 1 - Question 2b ===\n");
- Node *head = initialize(next());
- Node *new_head = NULL;
+ printf("=== COMP-272 - Assignment 1 - Question 5 ===\n");
- for (int i = 0; i < 9; ++i)
- add(head, next());
+ Node *head = initialize(0);
- printf("\t");
- inspect(head);
+ for (int i = 0; i < 10; i++)
+ add(head, i);
- new_head = get(head, 1);
- swap(head, new_head);
- head = new_head;
- printf("swap: 0,1\n\t");
+ printf("Before:\n\t");
inspect(head);
- for (int i = 2; i < 10; i+=2) {
- swap(get(head, i), get(head, i + 1));
- printf("swap: %d,%d\n\t", i, i + 1);
- inspect(head);
- }
+ printf("Reversing...\n");
+ head = reverse(head);
+
+ printf("After:\n\t");
+ inspect(head);
return 0;
}
generated by cgit v1.2.3 (git 2.39.1) at 2026-02-02 03:11:56 +0000