# HG changeset patch
# User John Tsiombikas <nuclear@mutantstargoat.com>
# Date 1318135694 -10800
# Node ID 6621337b6378a71b3a9feeef3a1159bd85261d9c

red-black tree lib

diff -r 000000000000 -r 6621337b6378 .hgignore
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/.hgignore	Sun Oct 09 07:48:14 2011 +0300
@@ -0,0 +1,6 @@
+\.o$
+\.d$
+\.swp$
+^Makefile$
+rbtree\.a$
+rbtree\.so
diff -r 000000000000 -r 6621337b6378 Makefile.in
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/Makefile.in	Sun Oct 09 07:48:14 2011 +0300
@@ -0,0 +1,58 @@
+src = $(wildcard src/*.c)
+obj = $(src:.c=.o)
+dep = $(obj:.o=.d)
+
+name = rbtree
+
+AR = ar
+CC = gcc
+CFLAGS = -pedantic -Wall $(dbg) $(opt) -fPIC
+
+ifeq ($(shell uname -s), Darwin)
+	lib_a = $(name).a
+	lib_so = $(name).dylib
+	shared = -dynamiclib $(lib_so)
+else
+	lib_a = lib$(name).a
+	devlink = lib$(name).so
+	soname = $(devlink).0
+	lib_so = $(soname).0
+	shared = -shared -Wl,-soname=$(soname)
+endif
+
+.PHONY: all
+all: $(lib_so) $(lib_a)
+
+$(lib_a): $(obj)
+	$(AR) rcs $(lib_a) $(obj)
+
+$(lib_so): $(obj)
+	$(CC) -o $@ $(shared) $(obj) $(LDFLAGS)
+
+-include $(dep)
+
+%.d: %.c
+	@$(CPP) $(CFLAGS) $< -MM -MT $(@:.d=.o) >$@
+
+.PHONY: clean
+clean:
+	rm -f $(obj) $(lib_a) $(lib_so)
+
+.PHONY: install
+install:
+	mkdir -p $(PREFIX)/include $(PREFIX)/lib
+	cp src/rbtree.h $(PREFIX)/include/rbtree.h
+	cp $(lib_a) $(PREFIX)/lib/$(lib_a)
+	cp $(lib_so) $(PREFIX)/lib/$(lib_so)
+	[ -n "$(soname)" ] \
+		&& rm -f $(PREFIX)/lib/$(soname) $(PREFIX)/lib/$(devlink) \
+		&& ln -s $(PREFIX)/lib/$(lib_so) $(PREFIX)/lib/$(soname) \
+		&& ln -s $(PREFIX)/lib/$(soname) $(PREFIX)/lib/$(devlink) \
+		|| true
+
+.PHONY: uninstall
+	rm -f $(PREFIX)/include/rbtree.h
+	rm -f $(PREFIX)/lib/$(lib_a)
+	rm -f $(PREFIX)/lib/$(lib_so)
+	rm -f $(PREFIX)/lib/$(soname)
+	rm -f $(PREFIX)/lib/$(devlink)
diff -r 000000000000 -r 6621337b6378 configure
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/configure	Sun Oct 09 07:48:14 2011 +0300
@@ -0,0 +1,36 @@
+#!/bin/sh
+
+prefix=/usr/local
+opt=false
+dbg=true
+
+while [ $# != 0 ]; do
+	case $1 in
+	--prefix=*)
+		prefix=`echo $1 | sed 's/^--prefix=//'`
+		;;
+	--enable-opt)
+		opt=true
+		;;
+	--disable-opt)
+		opt=false
+		;;
+	--enable-dbg)
+		dbg=true
+		;;
+	--disable-dbg)
+		dbg=false
+		;;
+	esac
+	shift
+done
+
+echo 'Configuring librbtree...'
+
+echo "# do not modify this file manually, it's generated by configure" >Makefile
+echo "PREFIX = $prefix" >>Makefile
+$opt && echo '-O3' | xargs echo 'opt =' >>Makefile
+$dbg && echo '-g' | xargs echo 'dbg =' >>Makefile
+cat Makefile.in >>Makefile
+
+echo 'Done. Run make (or gmake) to compile.'
diff -r 000000000000 -r 6621337b6378 src/rbtree.c
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/rbtree.c	Sun Oct 09 07:48:14 2011 +0300
@@ -0,0 +1,456 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include "rbtree.h"
+
+#define INT2PTR(x)	((void*)(x))
+#define PTR2INT(x)	((int)(x))
+
+struct rbtree {
+	struct rbnode *root;
+
+	rb_alloc_func_t alloc;
+	rb_free_func_t free;
+
+	rb_cmp_func_t cmp;
+	rb_del_func_t del;
+	void *del_cls;
+
+	struct rbnode *rstack, *iter;
+};
+
+static int cmpaddr(void *ap, void *bp);
+static int cmpint(void *ap, void *bp);
+
+static int count_nodes(struct rbnode *node);
+static void del_tree(struct rbnode *node, void (*delfunc)(struct rbnode*, void*), void *cls);
+static struct rbnode *insert(struct rbtree *rb, struct rbnode *tree, void *key, void *data);
+static struct rbnode *delete(struct rbtree *rb, struct rbnode *tree, void *key);
+static struct rbnode *find(struct rbtree *rb, struct rbnode *node, void *key);
+static void traverse(struct rbnode *node, void (*func)(struct rbnode*, void*), void *cls);
+
+struct rbtree *rb_create(rb_cmp_func_t cmp_func)
+{
+	struct rbtree *rb;
+
+	if(!(rb = malloc(sizeof *rb))) {
+		return 0;
+	}
+	if(rb_init(rb, cmp_func) == -1) {
+		free(rb);
+		return 0;
+	}
+	return rb;
+}
+
+void rb_free(struct rbtree *rb)
+{
+	rb_destroy(rb);
+	free(rb);
+}
+
+
+int rb_init(struct rbtree *rb, rb_cmp_func_t cmp_func)
+{
+	memset(rb, 0, sizeof *rb);
+
+	if(cmp_func == RB_KEY_INT) {
+		rb->cmp = cmpint;
+	} else if(cmp_func == RB_KEY_STRING) {
+		rb->cmp = (rb_cmp_func_t)strcmp;
+	} else {
+		rb->cmp = cmpaddr;
+	}
+
+	rb->alloc = malloc;
+	rb->free = free;
+	return 0;
+}
+
+void rb_destroy(struct rbtree *rb)
+{
+	del_tree(rb->root, rb->del, rb->del_cls);
+}
+
+void rb_set_allocator(struct rbtree *rb, rb_alloc_func_t alloc, rb_free_func_t free)
+{
+	rb->alloc = alloc;
+	rb->free = free;
+}
+
+
+void rb_set_compare_func(struct rbtree *rb, rb_cmp_func_t func)
+{
+	rb->cmp = func;
+}
+
+void rb_set_delete_func(struct rbtree *rb, rb_del_func_t func, void *cls)
+{
+	rb->del = func;
+	rb->del_cls = cls;
+}
+
+int rb_size(struct rbtree *rb)
+{
+	return count_nodes(rb->root);
+}
+
+int rb_insert(struct rbtree *rb, void *key, void *data)
+{
+	rb->root = insert(rb, rb->root, key, data);
+	rb->root->red = 0;
+	return 0;
+}
+
+int rb_inserti(struct rbtree *rb, int key, void *data)
+{
+	rb->root = insert(rb, rb->root, INT2PTR(key), data);
+	rb->root->red = 0;
+	return 0;
+}
+
+
+int rb_delete(struct rbtree *rb, void *key)
+{
+	rb->root = delete(rb, rb->root, key);
+	rb->root->red = 0;
+	return 0;
+}
+
+int rb_deletei(struct rbtree *rb, int key)
+{
+	rb->root = delete(rb, rb->root, INT2PTR(key));
+	rb->root->red = 0;
+	return 0;
+}
+
+
+void *rb_find(struct rbtree *rb, void *key)
+{
+	return find(rb, rb->root, key);
+}
+
+void *rb_findi(struct rbtree *rb, int key)
+{
+	return find(rb, rb->root, INT2PTR(key));
+}
+
+
+void rb_foreach(struct rbtree *rb, void (*func)(struct rbnode*, void*), void *cls)
+{
+	traverse(rb->root, func, cls);
+}
+
+
+struct rbnode *rb_root(struct rbtree *rb)
+{
+	return rb->root;
+}
+
+void rb_begin(struct rbtree *rb)
+{
+	rb->rstack = 0;
+	rb->iter = rb->root;
+}
+
+#define push(sp, x)		((x)->next = (sp), (sp) = (x))
+#define pop(sp)			((sp) = (sp)->next)
+#define top(sp)			(sp)
+
+struct rbnode *rb_next(struct rbtree *rb)
+{
+	struct rbnode *res = 0;
+
+	while(rb->rstack || rb->iter) {
+		if(rb->iter) {
+			push(rb->rstack, rb->iter);
+			rb->iter = rb->iter->left;
+		} else {
+			rb->iter = top(rb->rstack);
+			pop(rb->rstack);
+			res = rb->iter;
+			rb->iter = rb->iter->right;
+			break;
+		}
+	}
+	return res;
+}
+
+void *rb_node_key(struct rbnode *node)
+{
+	return node ? node->key : 0;
+}
+
+int rb_node_keyi(struct rbnode *node)
+{
+	return node ? PTR2INT(node->key) : 0;
+}
+
+void *rb_node_data(struct rbnode *node)
+{
+	return node ? node->data : 0;
+}
+
+static int cmpaddr(void *ap, void *bp)
+{
+	return ap < bp ? -1 : (ap > bp ? 1 : 0);
+}
+
+static int cmpint(void *ap, void *bp)
+{
+	return PTR2INT(ap) - PTR2INT(bp);
+}
+
+
+/* ---- left-leaning 2-3 red-black implementation ---- */
+
+/* helper prototypes */
+static int is_red(struct rbnode *tree);
+static void color_flip(struct rbnode *tree);
+static struct rbnode *rot_left(struct rbnode *a);
+static struct rbnode *rot_right(struct rbnode *a);
+static struct rbnode *find_min(struct rbnode *tree);
+static struct rbnode *del_min(struct rbtree *rb, struct rbnode *tree);
+/*static struct rbnode *move_red_right(struct rbnode *tree);*/
+static struct rbnode *move_red_left(struct rbnode *tree);
+static struct rbnode *fix_up(struct rbnode *tree);
+
+static int count_nodes(struct rbnode *node)
+{
+	if(!node)
+		return 0;
+
+	return 1 + count_nodes(node->left) + count_nodes(node->right);
+}
+
+static void del_tree(struct rbnode *node, rb_del_func_t delfunc, void *cls)
+{
+	if(!node)
+		return;
+
+	del_tree(node->left, delfunc, cls);
+	del_tree(node->right, delfunc, cls);
+
+	delfunc(node, cls);
+	free(node);
+}
+
+static struct rbnode *insert(struct rbtree *rb, struct rbnode *tree, void *key, void *data)
+{
+	int cmp;
+
+	if(!tree) {
+		struct rbnode *node = rb->alloc(sizeof *node);
+		node->red = 1;
+		node->key = key;
+		node->data = data;
+		node->left = node->right = 0;
+		return node;
+	}
+
+	cmp = rb->cmp(key, tree->key);
+
+	if(cmp < 0) {
+		tree->left = insert(rb, tree->left, key, data);
+	} else if(cmp > 0) {
+		tree->right = insert(rb, tree->right, key, data);
+	} else {
+		tree->data = data;
+	}
+
+	/* fix right-leaning reds */
+	if(is_red(tree->right)) {
+		tree = rot_left(tree);
+	}
+	/* fix two reds in a row */
+	if(is_red(tree->left) && is_red(tree->left->left)) {
+		tree = rot_right(tree);
+	}
+
+	/* if 4-node, split it by color inversion */
+	if(is_red(tree->left) && is_red(tree->right)) {
+		color_flip(tree);
+	}
+
+	return tree;
+}
+
+static struct rbnode *delete(struct rbtree *rb, struct rbnode *tree, void *key)
+{
+	int cmp;
+
+	if(!tree) {
+		return 0;
+	}
+
+	cmp = rb->cmp(key, tree->key);
+
+	if(cmp < 0) {
+		if(!is_red(tree->left) && !is_red(tree->left->left)) {
+			tree = move_red_left(tree);
+		}
+		tree->left = delete(rb, tree->left, key);
+	} else {
+		/* need reds on the right */
+		if(is_red(tree->left)) {
+			tree = rot_right(tree);
+		}
+
+		/* found it at the bottom (XXX what certifies left is null?) */
+		if(cmp == 0 && !tree->right) {
+			if(rb->del) {
+				rb->del(tree, rb->del_cls);
+			}
+			rb->free(tree);
+			return 0;
+		}
+
+		if(!is_red(tree->right) && !is_red(tree->right->left)) {
+			tree = move_red_left(tree);
+		}
+
+		if(key == tree->key) {
+			struct rbnode *rmin = find_min(tree->right);
+			tree->key = rmin->key;
+			tree->data = rmin->data;
+			tree->right = del_min(rb, tree->right);
+		} else {
+			tree->right = delete(rb, tree->right, key);
+		}
+	}
+
+	return fix_up(tree);
+}
+
+static struct rbnode *find(struct rbtree *rb, struct rbnode *node, void *key)
+{
+	int cmp;
+
+	if(!node)
+		return 0;
+
+	if((cmp = rb->cmp(key, node->key)) == 0) {
+		return node;
+	}
+	return find(rb, cmp < 0 ? node->left : node->right, key);
+}
+
+static void traverse(struct rbnode *node, void (*func)(struct rbnode*, void*), void *cls)
+{
+	if(!node)
+		return;
+
+	traverse(node->left, func, cls);
+	func(node, cls);
+	traverse(node->right, func, cls);
+}
+
+/* helpers */
+
+static int is_red(struct rbnode *tree)
+{
+	return tree && tree->red;
+}
+
+static void color_flip(struct rbnode *tree)
+{
+	tree->red = !tree->red;
+	tree->left->red = !tree->left->red;
+	tree->right->red = !tree->right->red;
+}
+
+static struct rbnode *rot_left(struct rbnode *a)
+{
+	struct rbnode *b = a->right;
+	a->right = b->left;
+	b->left = a;
+	b->red = a->red;
+	a->red = 1;
+	return b;
+}
+
+static struct rbnode *rot_right(struct rbnode *a)
+{
+	struct rbnode *b = a->left;
+	a->left = b->right;
+	b->right = a;
+	b->red = a->red;
+	a->red = 1;
+	return b;
+}
+
+static struct rbnode *find_min(struct rbnode *tree)
+{
+	if(!tree || !tree->left) {
+		return tree;
+	}
+	return find_min(tree->left);
+}
+
+static struct rbnode *del_min(struct rbtree *rb, struct rbnode *tree)
+{
+	if(!tree->left) {
+		if(rb->del) {
+			rb->del(tree->left, rb->del_cls);
+		}
+		rb->free(tree->left);
+		return 0;
+	}
+
+	/* make sure we've got red (3/4-nodes) at the left side so we can delete at the bottom */
+	if(!is_red(tree->left) && !is_red(tree->left->left)) {
+		tree = move_red_left(tree);
+	}
+	tree->left = del_min(rb, tree->left);
+
+	/* fix right-reds, red-reds, and split 4-nodes on the way up */
+	return fix_up(tree);
+}
+
+#if 0
+/* push a red link on this node to the right */
+static struct rbnode *move_red_right(struct rbnode *tree)
+{
+	/* flipping it makes both children go red, so we have a red to the right */
+	color_flip(tree);
+
+	/* if after the flip we've got a red-red situation to the left, fix it */
+	if(is_red(tree->left->left)) {
+		tree = rot_right(tree);
+		color_flip(tree);
+	}
+	return tree;
+}
+#endif
+
+/* push a red link on this node to the left */
+static struct rbnode *move_red_left(struct rbnode *tree)
+{
+	/* flipping it makes both children go red, so we have a red to the left */
+	color_flip(tree);
+
+	/* if after the flip we've got a red-red on the right-left, fix it */
+	if(is_red(tree->right->left)) {
+		tree->right = rot_right(tree->right);
+		tree = rot_left(tree);
+		color_flip(tree);
+	}
+	return tree;
+}
+
+static struct rbnode *fix_up(struct rbnode *tree)
+{
+	/* fix right-leaning */
+	if(is_red(tree->right)) {
+		tree = rot_left(tree);
+	}
+	/* change invalid red-red pairs into a proper 4-node */
+	if(is_red(tree->left) && is_red(tree->left->left)) {
+		tree = rot_right(tree);
+	}
+	/* split 4-nodes */
+	if(is_red(tree->left) && is_red(tree->right)) {
+		color_flip(tree);
+	}
+	return tree;
+}
diff -r 000000000000 -r 6621337b6378 src/rbtree.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/rbtree.h	Sun Oct 09 07:48:14 2011 +0300
@@ -0,0 +1,68 @@
+#ifndef RBTREE_H_
+#define RBTREE_H_
+
+struct rbtree;
+
+
+struct rbnode {
+	void *key, *data;
+	int red;
+	struct rbnode *left, *right;
+	struct rbnode *next;	/* for iterator stack */
+};
+
+
+typedef void *(*rb_alloc_func_t)(size_t);
+typedef void (*rb_free_func_t)(void*);
+
+typedef int (*rb_cmp_func_t)(void*, void*);
+typedef void (*rb_del_func_t)(struct rbnode*, void*);
+
+#define RB_KEY_ADDR		(rb_cmp_func_t)(0)
+#define RB_KEY_INT		(rb_cmp_func_t)(1)
+#define RB_KEY_STRING	(rb_cmp_func_t)(3)
+
+typedef struct rbnode* rbiter_t;
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+struct rbtree *rb_create(rb_cmp_func_t cmp_func);
+void rb_free(struct rbtree *rb);
+
+int rb_init(struct rbtree *rb, rb_cmp_func_t cmp_func);
+void rb_destroy(struct rbtree *rb);
+
+void rb_set_allocator(struct rbtree *rb, rb_alloc_func_t alloc, rb_free_func_t free);
+void rb_set_compare_func(struct rbtree *rb, rb_cmp_func_t func);
+void rb_set_delete_func(struct rbtree *rb, rb_del_func_t func, void *cls);
+
+int rb_size(struct rbtree *rb);
+
+int rb_insert(struct rbtree *rb, void *key, void *data);
+int rb_inserti(struct rbtree *rb, int key, void *data);
+
+int rb_delete(struct rbtree *rb, void *key);
+int rb_deletei(struct rbtree *rb, int key);
+
+void *rb_find(struct rbtree *rb, void *key);
+void *rb_findi(struct rbtree *rb, int key);
+
+void rb_foreach(struct rbtree *rb, void (*func)(struct rbnode*, void*), void *cls);
+
+struct rbnode *rb_root(struct rbtree *rb);
+
+void rb_begin(struct rbtree *rb);
+struct rbnode *rb_node_next(struct rbtree *rb);
+
+void *rb_node_key(struct rbnode *node);
+int rb_node_keyi(struct rbnode *node);
+void *rb_node_data(struct rbnode *node);
+
+#ifdef __cplusplus
+}
+#endif
+
+
+#endif	/* RBTREE_H_ */
diff -r 000000000000 -r 6621337b6378 test/Makefile
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/test/Makefile	Sun Oct 09 07:48:14 2011 +0300
@@ -0,0 +1,32 @@
+obj = test.o
+bin = test
+
+font = linux-libertine.ttf
+
+CC = gcc
+CFLAGS = -pedantic -Wall -g -I../src -I/usr/local/include
+LDFLAGS = -L.. -L/usr/local/lib $(libgl) -lrbtree -ldrawtext
+
+ifeq ($(shell uname -s), Darwin)
+	libgl = -framework OpenGL -framework GLUT
+else
+	libgl = -lGL -lglut
+endif
+
+.PHONY: all
+all: $(bin) $(font)
+
+$(bin): $(obj)
+	$(CC) -o $@ $(obj) $(LDFLAGS)
+
+$(font):
+	wget http://downloads.sourceforge.net/project/linuxlibertine/linuxlibertine/5.1.3-2/LinLibertineTTF_5.1.3_2011_06_21.tgz
+	mkdir -p linlibertine
+	cd linlibertine; tar xzvf ../LinLibertineTTF_5.1.3_2011_06_21.tgz
+	rm -f LinLibertineTTF_5.1.3_2011_06_21.tgz
+	cp linlibertine/LinLibertine_R.ttf $@
+
+
+.PHONY: clean
+clean:
+	rm -f $(obj) $(bin)
diff -r 000000000000 -r 6621337b6378 test/test.c
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/test/test.c	Sun Oct 09 07:48:14 2011 +0300
@@ -0,0 +1,395 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <ctype.h>
+#include <math.h>
+#include <assert.h>
+#include <alloca.h>
+
+#ifndef __APPLE__
+#include <GL/glut.h>
+#else
+#include <GLUT/glut.h>
+#endif
+#include <rbtree.h>
+#include <drawtext.h>
+
+#define FONTSZ	18
+
+void init_gl(int argc, char **argv);
+float rbvis_width(struct rbnode *tree);
+void rbvis_draw(struct rbnode *tree, float x, float y);
+
+void draw_roundbox(float xsz, float ysz, float rad, int segm, const float *col, float border, const float *bcol);
+void draw_fillet(float rad, int segm);
+
+struct rbtree *tree;
+int num_nodes;
+struct dtx_font *font;
+char input_buffer[64];
+int win_xsz, win_ysz;
+
+int main(int argc, char **argv)
+{
+	int i;
+
+	if(argv[1]) {
+		if(!isdigit(argv[1][0])) {
+			fprintf(stderr, "pass a fucking number, not: %s\n", argv[1]);
+			return 1;
+		}
+		num_nodes = atoi(argv[1]);
+	}
+
+	if(!(font = dtx_open_font("linux-libertine.ttf", FONTSZ))) {
+		fprintf(stderr, "failed to open font\n");
+		return 1;
+	}
+
+	if(!(tree = rb_create(RB_KEY_INT))) {
+		return 1;
+	}
+
+	for(i=0; i<num_nodes; i++) {
+		rb_inserti(tree, i, 0);
+	}
+
+	init_gl(argc, argv);
+	return 0;
+}
+
+#define NWIDTH	28.0
+#define NHEIGHT 24.0
+#define PADDING	0
+#define DY	(NHEIGHT + NHEIGHT / 2.0)
+
+#define VIS(node)	((struct visinfo*)(node)->data)
+
+void disp(void);
+void reshape(int x, int y);
+void keyb(unsigned char key, int x, int y);
+void draw_rect(float x, float y, float width, float height, const char *text, int red);
+void draw_link(float x0, float y0, float x1, float y1, int red);
+
+void init_gl(int argc, char **argv)
+{
+	glutInitWindowSize(1280, 720);
+	glutInit(&argc, argv);
+	glutInitDisplayMode(GLUT_RGB | GLUT_DOUBLE | GLUT_MULTISAMPLE);
+
+	glutCreateWindow("foo");
+
+	dtx_use_font(font, FONTSZ);
+
+	glutDisplayFunc(disp);
+	glutReshapeFunc(reshape);
+	glutKeyboardFunc(keyb);
+
+	glEnable(GL_DEPTH_TEST);
+	glEnable(GL_MULTISAMPLE);
+
+	glutMainLoop();
+}
+
+void disp(void)
+{
+	struct rbnode *root = rb_root(tree);
+
+	glClearColor(0.57, 0.64, 0.59, 1.0);
+	glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);
+
+	glMatrixMode(GL_MODELVIEW);
+	glLoadIdentity();
+
+	if(input_buffer[0]) {
+		char *prompt = "select node to delete: ";
+		char *buf = alloca(strlen(prompt) + strlen(input_buffer));
+
+		glPushMatrix();
+		glTranslatef(10, 10, -0.9);
+		glColor3f(0, 0, 0);
+		sprintf(buf, "%s%s", prompt, input_buffer);
+		dtx_string(buf);
+		glPopMatrix();
+	}
+
+	if(root) {
+		rbvis_draw(root, rbvis_width(root->left) + NWIDTH, 550);
+	}
+
+	glutSwapBuffers();
+	assert(glGetError() == GL_NO_ERROR);
+}
+
+
+float rbvis_width(struct rbnode *tree)
+{
+	if(!tree)
+		return NWIDTH;
+
+	return NWIDTH + rbvis_width(tree->left) + rbvis_width(tree->right) + PADDING * 3.0;
+}
+
+void rbvis_draw(struct rbnode *tree, float x, float y)
+{
+	float leftx, rightx, nexty;
+	static const float hxsz = NWIDTH / 2.0;
+	static const float hysz = NHEIGHT / 2.0;
+	char text[16];
+
+	if(!tree)
+		return;
+
+	leftx = x - (tree->left ? rbvis_width(tree->left->right) + NWIDTH : rbvis_width(tree->left) / 2.0);
+	rightx = x + (tree->right ? rbvis_width(tree->right->left) + NWIDTH : rbvis_width(tree->right) / 2.0);
+
+	nexty = y - DY;
+
+	sprintf(text, "%d", rb_node_keyi(tree));
+	draw_rect(x - hxsz, y - hysz, NWIDTH, NHEIGHT, text, tree->red);
+
+	rbvis_draw(tree->left, leftx, nexty);
+	rbvis_draw(tree->right, rightx, nexty);
+
+	if(tree->left)
+		draw_link(x, y, leftx, nexty, tree->left->red);
+	if(tree->right)
+		draw_link(x, y, rightx, nexty, tree->right->red);
+}
+
+void draw_rect(float x, float y, float width, float height, const char *text, int red)
+{
+	float node_col[] = {0.63, 0.71, 0.82, 1.0};
+	float bord_col[] = {0, 0, 0, 1};
+
+	if(red) {
+		bord_col[0] = 1.0;
+	}
+
+	glMatrixMode(GL_MODELVIEW);
+	glPushMatrix();
+	glTranslatef(x + width / 2.0, y + height / 2.0, 0.0);
+
+	draw_roundbox(width, height, 8, 6, node_col, 1.2, bord_col);
+
+	glColor3f(0.15, 0.15, 0.15);
+	glTranslatef(-dtx_string_width(text) / 2.0, -dtx_string_height(text) / 2.0, 0.1);
+	dtx_string(text);
+	glMatrixMode(GL_MODELVIEW);
+	glPopMatrix();
+}
+
+void draw_link(float x0, float y0, float x1, float y1, int red)
+{
+	glPushAttrib(GL_LINE_BIT);
+	if(red) {
+		glLineWidth(3);
+	} else {
+		glLineWidth(2);
+	}
+
+	glBegin(GL_LINES);
+	if(red) {
+		glColor3f(0.8, 0.36, 0.3);
+	} else {
+		glColor3f(0, 0, 0);
+	}
+	glVertex3f(x0, y0, -0.8);
+	glVertex3f(x1, y1, -0.8);
+	glEnd();
+
+	glPopAttrib();
+}
+
+void draw_roundbox(float xsz, float ysz, float rad, int segm, const float *col, float border, const float *bcol)
+{
+	float hin_xsz, hin_ysz;
+
+	if(border > 0.0f) {
+		glPushMatrix();
+		glTranslatef(0, 0, -0.001);
+		draw_roundbox(xsz + 2 * border, ysz + 2 * border, rad + border, segm, bcol, 0.0, bcol);
+		glPopMatrix();
+	}
+
+	/* half inner size */
+	hin_xsz = (xsz - 2.0 * rad) / 2.0;
+	hin_ysz = (ysz - 2.0 * rad) / 2.0;
+
+	glColor4fv(col);
+
+	glBegin(GL_QUADS);
+	/* center */
+	glVertex2f(-hin_xsz, -hin_ysz);
+	glVertex2f(hin_xsz, -hin_ysz);
+	glVertex2f(hin_xsz, hin_ysz);
+	glVertex2f(-hin_xsz, hin_ysz);
+	/* right */
+	glVertex2f(hin_xsz, -hin_ysz);
+	glVertex2f(hin_xsz + rad, -hin_ysz);
+	glVertex2f(hin_xsz + rad, hin_ysz);
+	glVertex2f(hin_xsz, hin_ysz);
+	/* top */
+	glVertex2f(-hin_xsz, hin_ysz);
+	glVertex2f(hin_xsz, hin_ysz);
+	glVertex2f(hin_xsz, hin_ysz + rad);
+	glVertex2f(-hin_xsz, hin_ysz + rad);
+	/* left */
+	glVertex2f(-hin_xsz - rad, -hin_ysz);
+	glVertex2f(-hin_xsz, -hin_ysz);
+	glVertex2f(-hin_xsz, hin_ysz);
+	glVertex2f(-hin_xsz - rad, hin_ysz);
+	/* bottom */
+	glVertex2f(-hin_xsz, -hin_ysz - rad);
+	glVertex2f(hin_xsz, -hin_ysz - rad);
+	glVertex2f(hin_xsz, -hin_ysz);
+	glVertex2f(-hin_xsz, -hin_ysz);
+	glEnd();
+
+	glMatrixMode(GL_MODELVIEW);
+
+	glPushMatrix();
+	glTranslatef(hin_xsz, hin_ysz, 0);
+	draw_fillet(rad, segm);
+	glPopMatrix();
+
+	glPushMatrix();
+	glTranslatef(-hin_xsz, hin_ysz, 0);
+	glRotatef(90, 0, 0, 1);
+	draw_fillet(rad, segm);
+	glPopMatrix();
+
+	glPushMatrix();
+	glTranslatef(-hin_xsz, -hin_ysz, 0);
+	glRotatef(180, 0, 0, 1);
+	draw_fillet(rad, segm);
+	glPopMatrix();
+
+	glPushMatrix();
+	glTranslatef(hin_xsz, -hin_ysz, 0);
+	glRotatef(270, 0, 0, 1);
+	draw_fillet(rad, segm);
+	glPopMatrix();
+}
+
+void draw_fillet(float rad, int segm)
+{
+	int i;
+
+	glBegin(GL_TRIANGLE_FAN);
+	glVertex2f(0, 0);
+	for(i=0; i<segm; i++) {
+		float theta = 0.5 * M_PI * (float)i / (float)(segm - 1);
+		float x = cos(theta) * rad;
+		float y = sin(theta) * rad;
+		glVertex2f(x, y);
+	}
+	glEnd();
+}
+
+
+void reshape(int x, int y)
+{
+	win_xsz = x;
+	win_ysz = y;
+
+	glViewport(0, 0, x, y);
+
+	glMatrixMode(GL_PROJECTION);
+	glLoadIdentity();
+	glOrtho(0, x, 0, y, -1, 1);
+}
+
+void keyb(unsigned char key, int x, int y)
+{
+	static int wposx = -1, wposy;
+	static char *inp_next;
+
+	switch(key) {
+	case 27:
+		exit(0);
+
+	case 'f':
+	case 'F':
+		if(wposx >= 0) {
+			glutPositionWindow(wposx, wposy);
+			wposx = -1;
+		} else {
+			wposx = glutGet(GLUT_WINDOW_X);
+			wposy = glutGet(GLUT_WINDOW_Y);
+			glutFullScreen();
+		}
+		break;
+
+	case 'a':
+		rb_inserti(tree, num_nodes++, 0);
+		glutPostRedisplay();
+		break;
+
+	case 'r':
+		{
+			int x;
+			do {
+				x = rand() % 1024;
+			} while(rb_findi(tree, x));
+
+			rb_inserti(tree, x, 0);
+		}
+		glutPostRedisplay();
+		break;
+
+	case 'd':
+		inp_next = input_buffer;
+		*inp_next++ = ' ';
+		*inp_next = 0;
+		glutPostRedisplay();
+		break;
+
+	case '0':
+	case '1':
+	case '2':
+	case '3':
+	case '4':
+	case '5':
+	case '6':
+	case '7':
+	case '8':
+	case '9':
+		if(inp_next) {
+			*inp_next++ = key;
+			*inp_next = 0;
+			glutPostRedisplay();
+		}
+		break;
+
+	case '\b':
+		if(inp_next > input_buffer) {
+			*--inp_next = 0;
+			glutPostRedisplay();
+		}
+		break;
+
+	case '\n':
+	case '\r':
+		if(inp_next) {
+			int x;
+			char *endp;
+
+			*inp_next = 0;
+			inp_next = 0;
+
+			if((x = strtol(input_buffer, &endp, 10)), endp == input_buffer) {
+				fprintf(stderr, "invalid input: %s\n", input_buffer);
+			} else if(!rb_findi(tree, x)) {
+				fprintf(stderr, "%d not found in the tree\n", x);
+			} else {
+				printf("deleting: %d\n", x);
+				rb_deletei(tree, x);
+			}
+			input_buffer[0] = 0;
+			glutPostRedisplay();
+		}
+		break;
+	}
+}
+