/***********************************************************
data VList T where
  | Empty :: VList T
  | Node {value::T, next::VList T} :: VList T
(for int type only)
***********************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

/*#define DEBUG*/

#ifdef DEBUG
int mallocCounter = 0;
int freeCounter = 0;
#endif

enum TAG_VList {
  EMPTY,
  NODE
};
union VList {
  enum TAG_VList tag;
  struct {
    enum TAG_VList tag;
  } Empty;
  struct {
    enum TAG_VList tag;
    int value;
    union VList *next;
  } Node;
};

void *dmalloc(size_t size) {
  if (size >= 0) {
    void *ptr = malloc(size);
#ifdef DEBUG
    if (ptr) {
      mallocCounter++;
      fprintf(stderr, "[DEBUG] MALLOC: %p\n", ptr);
    }
#endif
    return ptr;
  } else {
    return NULL;
  }
}

void dfree(void * ptr) {
  if (ptr) {
    free(ptr);
#ifdef DEBUG
    freeCounter++;
    fprintf(stderr, "[DEBUG]   FREE: %p\n", ptr);
#endif
  }
}

void VList_dispose(union VList **pList) {
  if (pList && *pList) {
    if ((*pList)->tag == NODE) {
      VList_dispose(&((*pList)->Node.next));
    }
    dfree(*pList);
    *pList = NULL;
  }
}

union VList *VList_Empty() {
  union VList *result = (union VList*)dmalloc(sizeof(union VList));
  if (result) {
    result->Empty.tag = EMPTY;
  }
  return result;
}

union VList *VList_Node(int value, union VList *next) {
  union VList *result = (union VList*)dmalloc(sizeof(union VList));
  if (result) {
    result->Node.tag   = NODE;
    result->Node.value = value;
    result->Node.next  = next;
  }
  return result;
}

int VList_match_Empty(union VList *list) {
  return list && list->tag == EMPTY;
}

int VList_match_Node(union VList *list, int *pValue, union VList **pNext) {
  if (list && list->tag == NODE) {
    if (pValue) {
      *pValue = list->Node.value;
    }
    if (pNext) {
      *pNext  = list->Node.next;
    }
    return 1;
  }
  return 0;
}

union VList *VList_clone(union VList *list) {
  int value;
  union VList *next;
  if (VList_match_Empty(list)) {
    return VList_Empty();
  } else if (VList_match_Node(list, &value, &next)) {
    return VList_Node(value, VList_clone(next));
  } else {
    return 0;
  }
}

union VList *VList_map(union VList *list, int (*fn)(int)) {
  int value;
  union VList *next;
  if (VList_match_Empty(list)) {
    return VList_Empty();
  } else if (VList_match_Node(list, &value, &next)) {
    return VList_Node(fn ? fn(value) : value, VList_map(next, fn)); 
  } else {
    return NULL;
  }
}

union VList *VList_filter(union VList *list, int (*fn)(int)) {
  int value;
  union VList *next;
  if (VList_match_Empty(list)) {
    return VList_Empty();
  } else if (VList_match_Node(list, &value, &next)) {
    return (fn && fn(value)) ?
      VList_Node(value, VList_filter(next, fn)) :
      VList_filter(next, fn);
  } else {
    return NULL;
  }
}

int VList_fold(union VList *list, int start, int (*fn)(int, int)) {
  int value;
  union VList *next;
  if (VList_match_Empty(list)) {
    return start;
  } else if (VList_match_Node(list, &value, &next)) {
    return fn ? fn(value, VList_fold(next, start, fn)) : start;
  } else {
    return start;
  }
}

union VList *VList_appendValue(union VList *list, int newValue) {
  int value;
  union VList *next;
  if (VList_match_Empty(list)) {
    return VList_Node(newValue, VList_Empty());
  } else if (VList_match_Node(list, &value, &next)) {
    return VList_Node(value, VList_appendValue(next, newValue));
  } else {
    return NULL;
  }
}

union VList *VList_appendValues(union VList *list, union VList *newValues) {
  int value;
  union VList *next;
  if (VList_match_Empty(list)) {
    return VList_clone(newValues);
  } else if (VList_match_Node(list, &value, &next)) {
    return VList_Node(value, VList_appendValues(next, newValues));
  } else {
    return NULL;
  }
}

union VList *VList_reverse(union VList *list) {
  int value;
  union VList *next;
  if (VList_match_Empty(list)) {
    return VList_Empty();
  } else if (VList_match_Node(list, &value, &next)) {
    return VList_appendValue(VList_reverse(next), value);
  } else {
    return NULL;
  }
}

int VList_count(union VList *list) {
  int value;
  union VList *next;
  if (VList_match_Empty(list)) {
    return 0;
  } else if (VList_match_Node(list, &value, &next)) {
    return 1 + VList_count(next);
  } else {
    return 0;
  }
}

void *closure = NULL;

int lt(int x) {
  int y = closure ? *((int*)closure) : 0;
  return x < y;
}

int ge(int x) {
  int y = closure ? *((int*)closure) : 0;
  return x >= y;
}

union VList *VList_sort(union VList *list) {
  int value;
  union VList *next;
  if (VList_match_Empty(list)) {
    return VList_Empty();
  } else if (VList_match_Node(list, &value, &next)) {
    void *oldClosure = closure;
    closure = &value;
    union VList *leftFilter = VList_filter(next, lt);
    union VList *leftSide = VList_sort(leftFilter);
    VList_dispose(&leftFilter);
    union VList *rightFilter = VList_filter(next, ge);
    union VList *rightSide = VList_sort(rightFilter);
    VList_dispose(&rightFilter);
    closure = oldClosure;
    union VList *temp = VList_appendValue(leftSide, value);
    VList_dispose(&leftSide);
    union VList *result = VList_appendValues(temp, rightSide);
    VList_dispose(&rightSide);
    VList_dispose(&temp);
    return result;
  } else {
    return NULL;
  }
}

union VList *randomNumbers(int count, int min, int max) {
  if (count >= 1) {
    int number = min + rand() % (max - min + 1);
    return VList_Node(number, randomNumbers(count - 1, min, max));
  } else {
    return VList_Empty();
  }
}

void printNumbers(union VList *numbers) {
  int flagFirst = 1;
  union VList *current = numbers;
  while (current) {
    int value;
    union VList *next;
    if (VList_match_Node(current, &value, &next)) {
      if (flagFirst) {
        flagFirst = 0;
      } else {
        putchar(',');
        putchar(' ');
      }
      printf("%d", value);
      current = next;
    } else {
      current = NULL;
    }
  }
  putchar('\n');
}

int main(int argc, char *argv[]) {
  srand((unsigned)time(NULL));
  union VList *numbers = randomNumbers(12, 1, 6);
  printf("Before sort: ");
  printNumbers(numbers);
  union VList *sortedNumbers = VList_sort(numbers);
  printf("After sort:  ");
  printNumbers(sortedNumbers);
  VList_dispose(&sortedNumbers);
  VList_dispose(&numbers);
#ifdef DEBUG
  fprintf(stderr, "[DEBUG] MALLOC: %d, FREE: %d\n", mallocCounter, freeCounter);
#endif
  return 0;
}