/***********************************************************
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) {
#ifdef DEBUG
if (ptr) {
mallocCounter++;
fprintf(stderr
, "[DEBUG] MALLOC: %p\n", ptr
); }
#endif
return ptr;
} else {
return NULL;
}
}
void dfree(void * ptr) {
if (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 {
}
current = next;
} else {
current = NULL;
}
}
}
int main(int argc, char *argv[]) {
union VList *numbers = randomNumbers(12, 1, 6);
printNumbers(numbers);
union VList *sortedNumbers = VList_sort(numbers);
printNumbers(sortedNumbers);
VList_dispose(&sortedNumbers);
VList_dispose(&numbers);
#ifdef DEBUG
fprintf(stderr
, "[DEBUG] MALLOC: %d, FREE: %d\n", mallocCounter
, freeCounter
); #endif
return 0;
}