Commit 838b1b7

@@ -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;
+}

@@ -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());

@@ -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