fork download 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. enum node_type {type_nil, type_node};
  4. struct int_list {
  5.   enum node_type type;
  6.   union {
  7.     struct {int value; struct int_list *next;} node;
  8.     struct {} nil;
  9.   } as;
  10. };
  11. #define hd(list) ((list).as.node.value)
  12. #define tl(list) ((list).as.node.next)
  13. #define is_nil(list) ((list).type == type_nil)
  14. #define is_node(list) ((list).type == type_node)
  15. struct int_list int_list_nil() {
  16.   return (struct int_list){type_nil, 0, 0};
  17. }
  18. struct int_list int_list_cons(int value, struct int_list next) {
  19.   struct int_list list = {type_node, value, malloc(sizeof (struct int_list))};
  20.   *tl(list) = next;
  21.   return list;
  22. }
  23. void int_list_free(struct int_list list) {
  24.   if (is_node(list)) int_list_free(*tl(list)), free(tl(list));
  25. }
  26. void int_list_each(void (f)(int), struct int_list list) {
  27.   if (is_node(list)) f(hd(list)), int_list_each(f, *tl(list));
  28. }
  29. struct int_list int_list_rev_aux(struct int_list acc, struct int_list list) {
  30.   return is_nil(list)
  31.     ? acc
  32.     : int_list_rev_aux(int_list_cons(hd(list), acc), *tl(list));
  33. }
  34. struct int_list int_list_rev(struct int_list list) {
  35.   return int_list_rev_aux(int_list_nil(), list);
  36. }
  37. struct int_list int_list_append(struct int_list a, struct int_list b) {
  38.   if (is_node(a)) 
  39.     return int_list_cons(hd(a), int_list_append(*tl(a), b));
  40.   else if (is_node(b))
  41.     return int_list_cons(hd(b), int_list_append(a, *tl(b)));
  42.   else
  43.     return int_list_nil();
  44. }
  45. struct pair_of_int_lists {
  46.   struct int_list first, second;
  47. };
  48. struct pair_of_int_lists int_list_partition_aux(void *context, int (predicate)(void *, int), struct pair_of_int_lists acc, struct int_list list) {
  49. #define _(a, b) ((struct pair_of_int_lists){(a), (b)})
  50.   if (is_nil(list))
  51.     return acc;
  52.   else if (predicate(context, hd(list)))
  53.     return int_list_partition_aux(context, predicate, _(int_list_cons(hd(list), acc.first), acc.second), *tl(list));
  54.   else
  55.     return int_list_partition_aux(context, predicate, _(acc.first, int_list_cons(hd(list), acc.second)), *tl(list));
  56. #undef _
  57. }
  58. struct pair_of_int_lists int_list_partition(void *context, int (predicate)(void *, int), struct int_list list) {
  59.   struct pair_of_int_lists acc = {int_list_nil(), int_list_nil()};
  60.   struct int_list reversed = int_list_rev(list);
  61.   acc = int_list_partition_aux(context, predicate, acc, reversed);
  62.   int_list_free(reversed);
  63.   return acc;
  64. }
  65. int less_than_context(void *context, int value) {
  66.   return value < *(int *)context;
  67. }
  68. struct int_list int_list_qsort(struct int_list list) {
  69.   int pivot;
  70.   struct int_list sorted, tail, smaller, rest, a, b;
  71.   struct pair_of_int_lists pair;
  72.   if (is_nil(list))
  73.     return int_list_nil();
  74.   else {
  75.     pivot = hd(list), tail = *tl(list);
  76.     pair = int_list_partition(&pivot, less_than_context, tail);
  77.     smaller = pair.first, rest = pair.second;
  78.     sorted = int_list_append(a = int_list_qsort(smaller), b = int_list_cons(pivot, int_list_qsort(rest)));
  79.     int_list_free(smaller), int_list_free(rest), int_list_free(a), int_list_free(b);
  80.     return sorted;
  81.   }
  82. }
  83. #define list_cons(x, xs) _Generic((xs), struct int_list : int_list_cons, default : int_list_cons)((x), (xs))
  84. #define list_free(list) _Generic((list), struct int_list : int_list_free, default : int_list_free)(list)
  85. #define list_each(f, list) _Generic((list), struct int_list : int_list_each, default : int_list_each)((f), (list))
  86. #define list_qsort(list) _Generic((list), struct int_list : int_list_qsort, default : int_list_qsort)(list)
  87. void print_int(int x) {printf("%d", x);}
  88. int main() {
  89.   struct int_list list = list_cons(4, list_cons(8, list_cons(8, list_cons(3, int_list_nil()))));
  90.   struct int_list sorted = list_qsort(list);
  91.   list_each(print_int, list);puts("");
  92.   list_each(print_int, sorted);puts("");
  93.   list_free(list), list = int_list_nil();
  94.   list_free(sorted), sorted = int_list_nil();
  95.   return 0;
  96. }
  97.  
Success #stdin #stdout 0s 5504KB
comments (?)
stdin 
Standard input is empty
stdout 
4883
3488
https://ideone.com/Rp476I
language:
C (gcc 8.3)
created:
205 days ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!