/* cc cell.c -pedantic -pedantic-errors -ansi -Wall -Werror -O2 -o cell */

#include<stdlib.h>
#include<stdio.h>

typedef struct cell *cell;

struct cell {
	cell cell[3];
};

#define car ->cell[0]
#define cdr ->cell[1]
#define mem ->cell[2]

static cell
new_cell(cell data)
{
	cell cell = malloc(sizeof(struct cell));

	if(!cell) {
		fprintf(stderr, "out of memory\n");
		exit(1);
	}

	cell car = 0;
	cell cdr = 0;
	cell mem = data;

	return cell;
}

static void
join(cell a, cell b)
{
	a cdr = b;
	b car = a;
}

static cell
cons(cell a, cell b)
{
	cell acar;
	cell bcar;

	if(!a)
		return b;
	if(!b)
		return a;

	acar = a car;
	bcar = b car;

	join(acar, b);
	join(bcar, a);

	return a;
}

static cell
tree_as_list(cell root)
{
	cell a, b;

	if(!root)
		return 0;

	a = tree_as_list(root car);
	b = tree_as_list(root cdr);

	a = cons(a, cons(root car = root cdr = root, b));

	return a;
}

static void
tree_insert(cell * tree, cell data)
{
	cell root = *tree;

	if(root)
		tree_insert(&(root->cell[data > root mem]), data);
	else
		*tree = new_cell(data);
}

static void
dump_cell(cell cell)
{
	if(cell)
		fprintf(stdout, "%ld ", (long int)cell mem);
}

static void
list_walk(cell list, void (*call) (cell))
{
	cell cell = list;

	while(cell) {
		call(cell);
		if((cell = cell cdr) == list)
			break;
	}
}

int
main(void)
{
	cell tree = 0;

	tree_insert(&tree, (cell) 4);
	tree_insert(&tree, (cell) 2);
	tree_insert(&tree, (cell) 1);
	tree_insert(&tree, (cell) 3);
	tree_insert(&tree, (cell) 5);

	list_walk(tree_as_list(tree), &dump_cell);

	fprintf(stdout, "\n");

	exit(0);
}