code.kerkeslager.com Git - sandbox/blob - reverse.c

   1 // This code uses nested functions, which were introduced to C in the 1999
   2 // standard, so it won't compile on some older compilers. To compile with GCC,
   3 // use "gcc -std=c99 reverse.c".
   4
   5 #include <stdlib.h>
   6
   7 typedef struct List List;
   8
   9 struct List
  10 {
  11         void* head;
  12         List* tail;
  13 };
  14
  15 List* makeList(void* head, List* tail)
  16 {
  17         List* result = malloc(sizeof(result));
  18         result->head = head;
  19         result->tail = tail;
  20         return result;
  21 }
  22
  23 List* reverse(List* list)
  24 {
  25         List* internal(List* in, List* out)
  26         {
  27                 if(in == NULL)
  28                         return out;
  29
  30                 return internal(in->tail, makeList(in->head, out));
  31         }
  32
  33         return internal(list,NULL);
  34 }
  35
  36 // Tests.
  37 #include <assert.h>
  38 #include <stdio.h>
  39
  40 void test_reverseOnEmptyList()
  41 {
  42         List* fixture = NULL;
  43
  44         List* result = reverse(fixture);
  45
  46         assert(result == NULL);
  47 }
  48
  49 void test_reverseOnSingleElementList()
  50 {
  51         int one = 1;
  52         List* fixture = makeList(&one,NULL);
  53
  54         List* result = reverse(fixture);
  55
  56         assert(result->head == &one);
  57         assert(result->tail == NULL);
  58 }
  59
  60 void test_reverseOnMultiElementList()
  61 {
  62         int one = 1, two = 2, three = 3;
  63         List* fixture = makeList(&one, makeList(&two, makeList(&three, NULL)));
  64
  65         List* result = reverse(fixture);
  66
  67         assert(result->head == &three);
  68         assert(result->tail->head == &two);
  69         assert(result->tail->tail->head == &one);
  70         assert(result->tail->tail->tail == NULL);
  71 }
  72
  73 void test_doublyReversedListIsSameAsOriginal()
  74 {
  75         int listsAreEqual(List* left, List* right)
  76         {
  77                 if(left == NULL && right == NULL)
  78                         return 1;
  79
  80                 if(left == NULL || right == NULL || left->head != right->head)
  81                         return 0;
  82
  83                 return listsAreEqual(left->tail, right->tail);
  84         }
  85
  86         int one = 1, two = 2, three = 3;
  87         List* fixture = makeList(&one, makeList(&two, makeList(&three, NULL)));
  88
  89         List* result = reverse(reverse(fixture));
  90
  91         assert(listsAreEqual(fixture, result));
  92 }
  93
  94 int main(int argc, char** argv)
  95 {
  96         test_reverseOnEmptyList();
  97         test_reverseOnSingleElementList();
  98         test_reverseOnMultiElementList();
  99         test_doublyReversedListIsSameAsOriginal();
 100
 101         printf("All tests passed.\n");
 102         return 0;
 103 }