rbtree
changeset 5:56a08d00bb41
added rb_copy and rb_clear
moved the visualization test to test/vis/
| author | John Tsiombikas <nuclear@member.fsf.org> |
|---|---|
| date | Wed, 12 Oct 2011 05:25:34 +0300 |
| parents | c4f36d709ee9 |
| children | 028a21468abf b266386d19ce |
| files | Makefile.in src/rbtree.c src/rbtree.h test/Makefile test/test.c test/vis/Makefile test/vis/test.c |
| diffstat | 7 files changed, 460 insertions(+), 436 deletions(-) [+] |
line diff
1.1 --- a/Makefile.in Wed Oct 12 05:01:11 2011 +0300 1.2 +++ b/Makefile.in Wed Oct 12 05:25:34 2011 +0300 1.3 @@ -11,7 +11,7 @@ 1.4 ifeq ($(shell uname -s), Darwin) 1.5 lib_a = $(name).a 1.6 lib_so = $(name).dylib 1.7 - shared = -dynamiclib $(lib_so) 1.8 + shared = -dynamiclib 1.9 else 1.10 lib_a = lib$(name).a 1.11 devlink = lib$(name).so
2.1 --- a/src/rbtree.c Wed Oct 12 05:01:11 2011 +0300 2.2 +++ b/src/rbtree.c Wed Oct 12 05:25:34 2011 +0300 2.3 @@ -90,6 +90,27 @@ 2.4 rb->del_cls = cls; 2.5 } 2.6 2.7 + 2.8 +void rb_clear(struct rbtree *rb) 2.9 +{ 2.10 + del_tree(rb->root, rb->del, rb->del_cls); 2.11 + rb->root = 0; 2.12 +} 2.13 + 2.14 +int rb_copy(struct rbtree *dest, struct rbtree *src) 2.15 +{ 2.16 + struct rbnode *node; 2.17 + 2.18 + rb_clear(dest); 2.19 + rb_begin(src); 2.20 + while((node = rb_next(src))) { 2.21 + if(rb_insert(dest, node->key, node->data) == -1) { 2.22 + return -1; 2.23 + } 2.24 + } 2.25 + return 0; 2.26 +} 2.27 + 2.28 int rb_size(struct rbtree *rb) 2.29 { 2.30 return count_nodes(rb->root);
3.1 --- a/src/rbtree.h Wed Oct 12 05:01:11 2011 +0300 3.2 +++ b/src/rbtree.h Wed Oct 12 05:25:34 2011 +0300 3.3 @@ -37,6 +37,9 @@ 3.4 void rb_set_compare_func(struct rbtree *rb, rb_cmp_func_t func); 3.5 void rb_set_delete_func(struct rbtree *rb, rb_del_func_t func, void *cls); 3.6 3.7 +void rb_clear(struct rbtree *rb); 3.8 +int rb_copy(struct rbtree *dest, struct rbtree *src); 3.9 + 3.10 int rb_size(struct rbtree *rb); 3.11 3.12 int rb_insert(struct rbtree *rb, void *key, void *data);
4.1 --- a/test/Makefile Wed Oct 12 05:01:11 2011 +0300 4.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 4.3 @@ -1,32 +0,0 @@ 4.4 -obj = test.o 4.5 -bin = test 4.6 - 4.7 -font = linux-libertine.ttf 4.8 - 4.9 -CC = gcc 4.10 -CFLAGS = -pedantic -Wall -g -I../src -I/usr/local/include 4.11 -LDFLAGS = -L.. -L/usr/local/lib $(libgl) -lrbtree -ldrawtext 4.12 - 4.13 -ifeq ($(shell uname -s), Darwin) 4.14 - libgl = -framework OpenGL -framework GLUT 4.15 -else 4.16 - libgl = -lGL -lglut 4.17 -endif 4.18 - 4.19 -.PHONY: all 4.20 -all: $(bin) $(font) 4.21 - 4.22 -$(bin): $(obj) 4.23 - $(CC) -o $@ $(obj) $(LDFLAGS) 4.24 - 4.25 -$(font): 4.26 - wget http://downloads.sourceforge.net/project/linuxlibertine/linuxlibertine/5.1.3-2/LinLibertineTTF_5.1.3_2011_06_21.tgz 4.27 - mkdir -p linlibertine 4.28 - cd linlibertine; tar xzvf ../LinLibertineTTF_5.1.3_2011_06_21.tgz 4.29 - rm -f LinLibertineTTF_5.1.3_2011_06_21.tgz 4.30 - cp linlibertine/LinLibertine_R.ttf $@ 4.31 - 4.32 - 4.33 -.PHONY: clean 4.34 -clean: 4.35 - rm -f $(obj) $(bin)
5.1 --- a/test/test.c Wed Oct 12 05:01:11 2011 +0300 5.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 5.3 @@ -1,403 +0,0 @@ 5.4 -#include <stdio.h> 5.5 -#include <stdlib.h> 5.6 -#include <string.h> 5.7 -#include <ctype.h> 5.8 -#include <math.h> 5.9 -#include <assert.h> 5.10 -#include <alloca.h> 5.11 - 5.12 -#ifndef __APPLE__ 5.13 -#include <GL/glut.h> 5.14 -#else 5.15 -#include <GLUT/glut.h> 5.16 -#endif 5.17 -#include <rbtree.h> 5.18 -#include <drawtext.h> 5.19 - 5.20 -#define FONTSZ 18 5.21 - 5.22 -void init_gl(int argc, char **argv); 5.23 -float rbvis_width(struct rbnode *tree); 5.24 -void rbvis_draw(struct rbnode *tree, float x, float y); 5.25 - 5.26 -void draw_roundbox(float xsz, float ysz, float rad, int segm, const float *col, float border, const float *bcol); 5.27 -void draw_fillet(float rad, int segm); 5.28 - 5.29 -struct rbtree *tree; 5.30 -int num_nodes; 5.31 -struct dtx_font *font; 5.32 -char input_buffer[64]; 5.33 -int win_xsz, win_ysz; 5.34 - 5.35 -int main(int argc, char **argv) 5.36 -{ 5.37 - int i; 5.38 - 5.39 - if(argv[1]) { 5.40 - if(!isdigit(argv[1][0])) { 5.41 - fprintf(stderr, "pass a fucking number, not: %s\n", argv[1]); 5.42 - return 1; 5.43 - } 5.44 - num_nodes = atoi(argv[1]); 5.45 - } 5.46 - 5.47 - if(!(font = dtx_open_font("linux-libertine.ttf", FONTSZ))) { 5.48 - fprintf(stderr, "failed to open font\n"); 5.49 - return 1; 5.50 - } 5.51 - 5.52 - if(!(tree = rb_create(RB_KEY_INT))) { 5.53 - return 1; 5.54 - } 5.55 - 5.56 - for(i=0; i<num_nodes; i++) { 5.57 - rb_inserti(tree, i, 0); 5.58 - } 5.59 - 5.60 - init_gl(argc, argv); 5.61 - return 0; 5.62 -} 5.63 - 5.64 -#define NWIDTH 28.0 5.65 -#define NHEIGHT 24.0 5.66 -#define PADDING 0 5.67 -#define DY (NHEIGHT + NHEIGHT / 2.0) 5.68 - 5.69 -#define VIS(node) ((struct visinfo*)(node)->data) 5.70 - 5.71 -void disp(void); 5.72 -void reshape(int x, int y); 5.73 -void keyb(unsigned char key, int x, int y); 5.74 -void draw_rect(float x, float y, float width, float height, const char *text, int red); 5.75 -void draw_link(float x0, float y0, float x1, float y1, int red); 5.76 - 5.77 -void init_gl(int argc, char **argv) 5.78 -{ 5.79 - glutInitWindowSize(1280, 720); 5.80 - glutInit(&argc, argv); 5.81 - glutInitDisplayMode(GLUT_RGB | GLUT_DOUBLE | GLUT_MULTISAMPLE); 5.82 - 5.83 - glutCreateWindow("foo"); 5.84 - 5.85 - dtx_use_font(font, FONTSZ); 5.86 - 5.87 - glutDisplayFunc(disp); 5.88 - glutReshapeFunc(reshape); 5.89 - glutKeyboardFunc(keyb); 5.90 - 5.91 - glEnable(GL_DEPTH_TEST); 5.92 - glEnable(GL_MULTISAMPLE); 5.93 - 5.94 - glutMainLoop(); 5.95 -} 5.96 - 5.97 -void disp(void) 5.98 -{ 5.99 - struct rbnode *root = rb_root(tree); 5.100 - 5.101 - glClearColor(0.57, 0.64, 0.59, 1.0); 5.102 - glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT); 5.103 - 5.104 - glMatrixMode(GL_MODELVIEW); 5.105 - glLoadIdentity(); 5.106 - 5.107 - if(input_buffer[0]) { 5.108 - char *prompt = "select node: "; 5.109 - char *buf = alloca(strlen(prompt) + strlen(input_buffer)); 5.110 - 5.111 - glPushMatrix(); 5.112 - glTranslatef(10, 10, -0.9); 5.113 - glColor3f(0, 0, 0); 5.114 - sprintf(buf, "%s%s", prompt, input_buffer); 5.115 - dtx_string(buf); 5.116 - glPopMatrix(); 5.117 - } 5.118 - 5.119 - if(root) { 5.120 - rbvis_draw(root, rbvis_width(root->left) + NWIDTH, 550); 5.121 - } 5.122 - 5.123 - glutSwapBuffers(); 5.124 - assert(glGetError() == GL_NO_ERROR); 5.125 -} 5.126 - 5.127 - 5.128 -float rbvis_width(struct rbnode *tree) 5.129 -{ 5.130 - if(!tree) 5.131 - return NWIDTH; 5.132 - 5.133 - return NWIDTH + rbvis_width(tree->left) + rbvis_width(tree->right) + PADDING * 3.0; 5.134 -} 5.135 - 5.136 -void rbvis_draw(struct rbnode *tree, float x, float y) 5.137 -{ 5.138 - float leftx, rightx, nexty; 5.139 - static const float hxsz = NWIDTH / 2.0; 5.140 - static const float hysz = NHEIGHT / 2.0; 5.141 - char text[16]; 5.142 - 5.143 - if(!tree) 5.144 - return; 5.145 - 5.146 - leftx = x - (tree->left ? rbvis_width(tree->left->right) + NWIDTH : rbvis_width(tree->left) / 2.0); 5.147 - rightx = x + (tree->right ? rbvis_width(tree->right->left) + NWIDTH : rbvis_width(tree->right) / 2.0); 5.148 - 5.149 - nexty = y - DY; 5.150 - 5.151 - sprintf(text, "%d", rb_node_keyi(tree)); 5.152 - draw_rect(x - hxsz, y - hysz, NWIDTH, NHEIGHT, text, tree->red); 5.153 - 5.154 - rbvis_draw(tree->left, leftx, nexty); 5.155 - rbvis_draw(tree->right, rightx, nexty); 5.156 - 5.157 - if(tree->left) 5.158 - draw_link(x, y, leftx, nexty, tree->left->red); 5.159 - if(tree->right) 5.160 - draw_link(x, y, rightx, nexty, tree->right->red); 5.161 -} 5.162 - 5.163 -void draw_rect(float x, float y, float width, float height, const char *text, int red) 5.164 -{ 5.165 - float node_col[] = {0.63, 0.71, 0.82, 1.0}; 5.166 - float bord_col[] = {0, 0, 0, 1}; 5.167 - 5.168 - if(red) { 5.169 - bord_col[0] = 1.0; 5.170 - } 5.171 - 5.172 - glMatrixMode(GL_MODELVIEW); 5.173 - glPushMatrix(); 5.174 - glTranslatef(x + width / 2.0, y + height / 2.0, 0.0); 5.175 - 5.176 - draw_roundbox(width, height, 8, 6, node_col, 1.2, bord_col); 5.177 - 5.178 - glColor3f(0.15, 0.15, 0.15); 5.179 - glTranslatef(-dtx_string_width(text) / 2.0, -dtx_string_height(text) / 2.0, 0.1); 5.180 - dtx_string(text); 5.181 - glMatrixMode(GL_MODELVIEW); 5.182 - glPopMatrix(); 5.183 -} 5.184 - 5.185 -void draw_link(float x0, float y0, float x1, float y1, int red) 5.186 -{ 5.187 - glPushAttrib(GL_LINE_BIT); 5.188 - if(red) { 5.189 - glLineWidth(3); 5.190 - } else { 5.191 - glLineWidth(2); 5.192 - } 5.193 - 5.194 - glBegin(GL_LINES); 5.195 - if(red) { 5.196 - glColor3f(0.8, 0.36, 0.3); 5.197 - } else { 5.198 - glColor3f(0, 0, 0); 5.199 - } 5.200 - glVertex3f(x0, y0, -0.8); 5.201 - glVertex3f(x1, y1, -0.8); 5.202 - glEnd(); 5.203 - 5.204 - glPopAttrib(); 5.205 -} 5.206 - 5.207 -void draw_roundbox(float xsz, float ysz, float rad, int segm, const float *col, float border, const float *bcol) 5.208 -{ 5.209 - float hin_xsz, hin_ysz; 5.210 - 5.211 - if(border > 0.0f) { 5.212 - glPushMatrix(); 5.213 - glTranslatef(0, 0, -0.001); 5.214 - draw_roundbox(xsz + 2 * border, ysz + 2 * border, rad + border, segm, bcol, 0.0, bcol); 5.215 - glPopMatrix(); 5.216 - } 5.217 - 5.218 - /* half inner size */ 5.219 - hin_xsz = (xsz - 2.0 * rad) / 2.0; 5.220 - hin_ysz = (ysz - 2.0 * rad) / 2.0; 5.221 - 5.222 - glColor4fv(col); 5.223 - 5.224 - glBegin(GL_QUADS); 5.225 - /* center */ 5.226 - glVertex2f(-hin_xsz, -hin_ysz); 5.227 - glVertex2f(hin_xsz, -hin_ysz); 5.228 - glVertex2f(hin_xsz, hin_ysz); 5.229 - glVertex2f(-hin_xsz, hin_ysz); 5.230 - /* right */ 5.231 - glVertex2f(hin_xsz, -hin_ysz); 5.232 - glVertex2f(hin_xsz + rad, -hin_ysz); 5.233 - glVertex2f(hin_xsz + rad, hin_ysz); 5.234 - glVertex2f(hin_xsz, hin_ysz); 5.235 - /* top */ 5.236 - glVertex2f(-hin_xsz, hin_ysz); 5.237 - glVertex2f(hin_xsz, hin_ysz); 5.238 - glVertex2f(hin_xsz, hin_ysz + rad); 5.239 - glVertex2f(-hin_xsz, hin_ysz + rad); 5.240 - /* left */ 5.241 - glVertex2f(-hin_xsz - rad, -hin_ysz); 5.242 - glVertex2f(-hin_xsz, -hin_ysz); 5.243 - glVertex2f(-hin_xsz, hin_ysz); 5.244 - glVertex2f(-hin_xsz - rad, hin_ysz); 5.245 - /* bottom */ 5.246 - glVertex2f(-hin_xsz, -hin_ysz - rad); 5.247 - glVertex2f(hin_xsz, -hin_ysz - rad); 5.248 - glVertex2f(hin_xsz, -hin_ysz); 5.249 - glVertex2f(-hin_xsz, -hin_ysz); 5.250 - glEnd(); 5.251 - 5.252 - glMatrixMode(GL_MODELVIEW); 5.253 - 5.254 - glPushMatrix(); 5.255 - glTranslatef(hin_xsz, hin_ysz, 0); 5.256 - draw_fillet(rad, segm); 5.257 - glPopMatrix(); 5.258 - 5.259 - glPushMatrix(); 5.260 - glTranslatef(-hin_xsz, hin_ysz, 0); 5.261 - glRotatef(90, 0, 0, 1); 5.262 - draw_fillet(rad, segm); 5.263 - glPopMatrix(); 5.264 - 5.265 - glPushMatrix(); 5.266 - glTranslatef(-hin_xsz, -hin_ysz, 0); 5.267 - glRotatef(180, 0, 0, 1); 5.268 - draw_fillet(rad, segm); 5.269 - glPopMatrix(); 5.270 - 5.271 - glPushMatrix(); 5.272 - glTranslatef(hin_xsz, -hin_ysz, 0); 5.273 - glRotatef(270, 0, 0, 1); 5.274 - draw_fillet(rad, segm); 5.275 - glPopMatrix(); 5.276 -} 5.277 - 5.278 -void draw_fillet(float rad, int segm) 5.279 -{ 5.280 - int i; 5.281 - 5.282 - glBegin(GL_TRIANGLE_FAN); 5.283 - glVertex2f(0, 0); 5.284 - for(i=0; i<segm; i++) { 5.285 - float theta = 0.5 * M_PI * (float)i / (float)(segm - 1); 5.286 - float x = cos(theta) * rad; 5.287 - float y = sin(theta) * rad; 5.288 - glVertex2f(x, y); 5.289 - } 5.290 - glEnd(); 5.291 -} 5.292 - 5.293 - 5.294 -void reshape(int x, int y) 5.295 -{ 5.296 - win_xsz = x; 5.297 - win_ysz = y; 5.298 - 5.299 - glViewport(0, 0, x, y); 5.300 - 5.301 - glMatrixMode(GL_PROJECTION); 5.302 - glLoadIdentity(); 5.303 - glOrtho(0, x, 0, y, -1, 1); 5.304 -} 5.305 - 5.306 -void keyb(unsigned char key, int x, int y) 5.307 -{ 5.308 - static int wposx = -1, wposy; 5.309 - static char *inp_next; 5.310 - static char op; 5.311 - 5.312 - switch(key) { 5.313 - case 27: 5.314 - exit(0); 5.315 - 5.316 - case 'a': 5.317 - rb_inserti(tree, num_nodes++, 0); 5.318 - glutPostRedisplay(); 5.319 - break; 5.320 - 5.321 - case 'r': 5.322 - { 5.323 - int x; 5.324 - do { 5.325 - x = rand() % 1024; 5.326 - } while(rb_findi(tree, x)); 5.327 - 5.328 - rb_inserti(tree, x, 0); 5.329 - } 5.330 - glutPostRedisplay(); 5.331 - break; 5.332 - 5.333 - case 'd': 5.334 - case 'f': 5.335 - op = key; 5.336 - inp_next = input_buffer; 5.337 - *inp_next++ = ' '; 5.338 - *inp_next = 0; 5.339 - glutPostRedisplay(); 5.340 - break; 5.341 - 5.342 - case '0': 5.343 - case '1': 5.344 - case '2': 5.345 - case '3': 5.346 - case '4': 5.347 - case '5': 5.348 - case '6': 5.349 - case '7': 5.350 - case '8': 5.351 - case '9': 5.352 - if(inp_next) { 5.353 - *inp_next++ = key; 5.354 - *inp_next = 0; 5.355 - glutPostRedisplay(); 5.356 - } 5.357 - break; 5.358 - 5.359 - case '\b': 5.360 - if(inp_next > input_buffer) { 5.361 - *--inp_next = 0; 5.362 - glutPostRedisplay(); 5.363 - } 5.364 - break; 5.365 - 5.366 - case '\n': 5.367 - case '\r': 5.368 - if(inp_next) { 5.369 - int x; 5.370 - char *endp; 5.371 - 5.372 - *inp_next = 0; 5.373 - inp_next = 0; 5.374 - 5.375 - if((x = strtol(input_buffer, &endp, 10)), endp == input_buffer) { 5.376 - fprintf(stderr, "invalid input: %s\n", input_buffer); 5.377 - } else if(!rb_findi(tree, x)) { 5.378 - fprintf(stderr, "%d not found in the tree\n", x); 5.379 - } else { 5.380 - if(op == 'd') { 5.381 - printf("deleting: %d\n", x); 5.382 - rb_deletei(tree, x); 5.383 - } else { 5.384 - printf("%d found!\n", x); 5.385 - } 5.386 - } 5.387 - input_buffer[0] = 0; 5.388 - glutPostRedisplay(); 5.389 - } 5.390 - break; 5.391 - 5.392 - case 'p': 5.393 - { 5.394 - struct rbnode *node; 5.395 - 5.396 - rb_begin(tree); 5.397 - while((node = rb_next(tree))) { 5.398 - int key = rb_node_keyi(node); 5.399 - printf("%d ", key); 5.400 - } 5.401 - putchar('\n'); 5.402 - } 5.403 - break; 5.404 - } 5.405 -} 5.406 -
6.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 6.2 +++ b/test/vis/Makefile Wed Oct 12 05:25:34 2011 +0300 6.3 @@ -0,0 +1,32 @@ 6.4 +obj = test.o 6.5 +bin = test 6.6 + 6.7 +font = linux-libertine.ttf 6.8 + 6.9 +CC = gcc 6.10 +CFLAGS = -pedantic -Wall -g -I../src -I/usr/local/include 6.11 +LDFLAGS = -L.. -L/usr/local/lib $(libgl) -lrbtree -ldrawtext 6.12 + 6.13 +ifeq ($(shell uname -s), Darwin) 6.14 + libgl = -framework OpenGL -framework GLUT 6.15 +else 6.16 + libgl = -lGL -lglut 6.17 +endif 6.18 + 6.19 +.PHONY: all 6.20 +all: $(bin) $(font) 6.21 + 6.22 +$(bin): $(obj) 6.23 + $(CC) -o $@ $(obj) $(LDFLAGS) 6.24 + 6.25 +$(font): 6.26 + wget http://downloads.sourceforge.net/project/linuxlibertine/linuxlibertine/5.1.3-2/LinLibertineTTF_5.1.3_2011_06_21.tgz 6.27 + mkdir -p linlibertine 6.28 + cd linlibertine; tar xzvf ../LinLibertineTTF_5.1.3_2011_06_21.tgz 6.29 + rm -f LinLibertineTTF_5.1.3_2011_06_21.tgz 6.30 + cp linlibertine/LinLibertine_R.ttf $@ 6.31 + 6.32 + 6.33 +.PHONY: clean 6.34 +clean: 6.35 + rm -f $(obj) $(bin)
7.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 7.2 +++ b/test/vis/test.c Wed Oct 12 05:25:34 2011 +0300 7.3 @@ -0,0 +1,403 @@ 7.4 +#include <stdio.h> 7.5 +#include <stdlib.h> 7.6 +#include <string.h> 7.7 +#include <ctype.h> 7.8 +#include <math.h> 7.9 +#include <assert.h> 7.10 +#include <alloca.h> 7.11 + 7.12 +#ifndef __APPLE__ 7.13 +#include <GL/glut.h> 7.14 +#else 7.15 +#include <GLUT/glut.h> 7.16 +#endif 7.17 +#include <rbtree.h> 7.18 +#include <drawtext.h> 7.19 + 7.20 +#define FONTSZ 18 7.21 + 7.22 +void init_gl(int argc, char **argv); 7.23 +float rbvis_width(struct rbnode *tree); 7.24 +void rbvis_draw(struct rbnode *tree, float x, float y); 7.25 + 7.26 +void draw_roundbox(float xsz, float ysz, float rad, int segm, const float *col, float border, const float *bcol); 7.27 +void draw_fillet(float rad, int segm); 7.28 + 7.29 +struct rbtree *tree; 7.30 +int num_nodes; 7.31 +struct dtx_font *font; 7.32 +char input_buffer[64]; 7.33 +int win_xsz, win_ysz; 7.34 + 7.35 +int main(int argc, char **argv) 7.36 +{ 7.37 + int i; 7.38 + 7.39 + if(argv[1]) { 7.40 + if(!isdigit(argv[1][0])) { 7.41 + fprintf(stderr, "pass a fucking number, not: %s\n", argv[1]); 7.42 + return 1; 7.43 + } 7.44 + num_nodes = atoi(argv[1]); 7.45 + } 7.46 + 7.47 + if(!(font = dtx_open_font("linux-libertine.ttf", FONTSZ))) { 7.48 + fprintf(stderr, "failed to open font\n"); 7.49 + return 1; 7.50 + } 7.51 + 7.52 + if(!(tree = rb_create(RB_KEY_INT))) { 7.53 + return 1; 7.54 + } 7.55 + 7.56 + for(i=0; i<num_nodes; i++) { 7.57 + rb_inserti(tree, i, 0); 7.58 + } 7.59 + 7.60 + init_gl(argc, argv); 7.61 + return 0; 7.62 +} 7.63 + 7.64 +#define NWIDTH 28.0 7.65 +#define NHEIGHT 24.0 7.66 +#define PADDING 0 7.67 +#define DY (NHEIGHT + NHEIGHT / 2.0) 7.68 + 7.69 +#define VIS(node) ((struct visinfo*)(node)->data) 7.70 + 7.71 +void disp(void); 7.72 +void reshape(int x, int y); 7.73 +void keyb(unsigned char key, int x, int y); 7.74 +void draw_rect(float x, float y, float width, float height, const char *text, int red); 7.75 +void draw_link(float x0, float y0, float x1, float y1, int red); 7.76 + 7.77 +void init_gl(int argc, char **argv) 7.78 +{ 7.79 + glutInitWindowSize(1280, 720); 7.80 + glutInit(&argc, argv); 7.81 + glutInitDisplayMode(GLUT_RGB | GLUT_DOUBLE | GLUT_MULTISAMPLE); 7.82 + 7.83 + glutCreateWindow("foo"); 7.84 + 7.85 + dtx_use_font(font, FONTSZ); 7.86 + 7.87 + glutDisplayFunc(disp); 7.88 + glutReshapeFunc(reshape); 7.89 + glutKeyboardFunc(keyb); 7.90 + 7.91 + glEnable(GL_DEPTH_TEST); 7.92 + glEnable(GL_MULTISAMPLE); 7.93 + 7.94 + glutMainLoop(); 7.95 +} 7.96 + 7.97 +void disp(void) 7.98 +{ 7.99 + struct rbnode *root = rb_root(tree); 7.100 + 7.101 + glClearColor(0.57, 0.64, 0.59, 1.0); 7.102 + glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT); 7.103 + 7.104 + glMatrixMode(GL_MODELVIEW); 7.105 + glLoadIdentity(); 7.106 + 7.107 + if(input_buffer[0]) { 7.108 + char *prompt = "select node: "; 7.109 + char *buf = alloca(strlen(prompt) + strlen(input_buffer)); 7.110 + 7.111 + glPushMatrix(); 7.112 + glTranslatef(10, 10, -0.9); 7.113 + glColor3f(0, 0, 0); 7.114 + sprintf(buf, "%s%s", prompt, input_buffer); 7.115 + dtx_string(buf); 7.116 + glPopMatrix(); 7.117 + } 7.118 + 7.119 + if(root) { 7.120 + rbvis_draw(root, rbvis_width(root->left) + NWIDTH, 550); 7.121 + } 7.122 + 7.123 + glutSwapBuffers(); 7.124 + assert(glGetError() == GL_NO_ERROR); 7.125 +} 7.126 + 7.127 + 7.128 +float rbvis_width(struct rbnode *tree) 7.129 +{ 7.130 + if(!tree) 7.131 + return NWIDTH; 7.132 + 7.133 + return NWIDTH + rbvis_width(tree->left) + rbvis_width(tree->right) + PADDING * 3.0; 7.134 +} 7.135 + 7.136 +void rbvis_draw(struct rbnode *tree, float x, float y) 7.137 +{ 7.138 + float leftx, rightx, nexty; 7.139 + static const float hxsz = NWIDTH / 2.0; 7.140 + static const float hysz = NHEIGHT / 2.0; 7.141 + char text[16]; 7.142 + 7.143 + if(!tree) 7.144 + return; 7.145 + 7.146 + leftx = x - (tree->left ? rbvis_width(tree->left->right) + NWIDTH : rbvis_width(tree->left) / 2.0); 7.147 + rightx = x + (tree->right ? rbvis_width(tree->right->left) + NWIDTH : rbvis_width(tree->right) / 2.0); 7.148 + 7.149 + nexty = y - DY; 7.150 + 7.151 + sprintf(text, "%d", rb_node_keyi(tree)); 7.152 + draw_rect(x - hxsz, y - hysz, NWIDTH, NHEIGHT, text, tree->red); 7.153 + 7.154 + rbvis_draw(tree->left, leftx, nexty); 7.155 + rbvis_draw(tree->right, rightx, nexty); 7.156 + 7.157 + if(tree->left) 7.158 + draw_link(x, y, leftx, nexty, tree->left->red); 7.159 + if(tree->right) 7.160 + draw_link(x, y, rightx, nexty, tree->right->red); 7.161 +} 7.162 + 7.163 +void draw_rect(float x, float y, float width, float height, const char *text, int red) 7.164 +{ 7.165 + float node_col[] = {0.63, 0.71, 0.82, 1.0}; 7.166 + float bord_col[] = {0, 0, 0, 1}; 7.167 + 7.168 + if(red) { 7.169 + bord_col[0] = 1.0; 7.170 + } 7.171 + 7.172 + glMatrixMode(GL_MODELVIEW); 7.173 + glPushMatrix(); 7.174 + glTranslatef(x + width / 2.0, y + height / 2.0, 0.0); 7.175 + 7.176 + draw_roundbox(width, height, 8, 6, node_col, 1.2, bord_col); 7.177 + 7.178 + glColor3f(0.15, 0.15, 0.15); 7.179 + glTranslatef(-dtx_string_width(text) / 2.0, -dtx_string_height(text) / 2.0, 0.1); 7.180 + dtx_string(text); 7.181 + glMatrixMode(GL_MODELVIEW); 7.182 + glPopMatrix(); 7.183 +} 7.184 + 7.185 +void draw_link(float x0, float y0, float x1, float y1, int red) 7.186 +{ 7.187 + glPushAttrib(GL_LINE_BIT); 7.188 + if(red) { 7.189 + glLineWidth(3); 7.190 + } else { 7.191 + glLineWidth(2); 7.192 + } 7.193 + 7.194 + glBegin(GL_LINES); 7.195 + if(red) { 7.196 + glColor3f(0.8, 0.36, 0.3); 7.197 + } else { 7.198 + glColor3f(0, 0, 0); 7.199 + } 7.200 + glVertex3f(x0, y0, -0.8); 7.201 + glVertex3f(x1, y1, -0.8); 7.202 + glEnd(); 7.203 + 7.204 + glPopAttrib(); 7.205 +} 7.206 + 7.207 +void draw_roundbox(float xsz, float ysz, float rad, int segm, const float *col, float border, const float *bcol) 7.208 +{ 7.209 + float hin_xsz, hin_ysz; 7.210 + 7.211 + if(border > 0.0f) { 7.212 + glPushMatrix(); 7.213 + glTranslatef(0, 0, -0.001); 7.214 + draw_roundbox(xsz + 2 * border, ysz + 2 * border, rad + border, segm, bcol, 0.0, bcol); 7.215 + glPopMatrix(); 7.216 + } 7.217 + 7.218 + /* half inner size */ 7.219 + hin_xsz = (xsz - 2.0 * rad) / 2.0; 7.220 + hin_ysz = (ysz - 2.0 * rad) / 2.0; 7.221 + 7.222 + glColor4fv(col); 7.223 + 7.224 + glBegin(GL_QUADS); 7.225 + /* center */ 7.226 + glVertex2f(-hin_xsz, -hin_ysz); 7.227 + glVertex2f(hin_xsz, -hin_ysz); 7.228 + glVertex2f(hin_xsz, hin_ysz); 7.229 + glVertex2f(-hin_xsz, hin_ysz); 7.230 + /* right */ 7.231 + glVertex2f(hin_xsz, -hin_ysz); 7.232 + glVertex2f(hin_xsz + rad, -hin_ysz); 7.233 + glVertex2f(hin_xsz + rad, hin_ysz); 7.234 + glVertex2f(hin_xsz, hin_ysz); 7.235 + /* top */ 7.236 + glVertex2f(-hin_xsz, hin_ysz); 7.237 + glVertex2f(hin_xsz, hin_ysz); 7.238 + glVertex2f(hin_xsz, hin_ysz + rad); 7.239 + glVertex2f(-hin_xsz, hin_ysz + rad); 7.240 + /* left */ 7.241 + glVertex2f(-hin_xsz - rad, -hin_ysz); 7.242 + glVertex2f(-hin_xsz, -hin_ysz); 7.243 + glVertex2f(-hin_xsz, hin_ysz); 7.244 + glVertex2f(-hin_xsz - rad, hin_ysz); 7.245 + /* bottom */ 7.246 + glVertex2f(-hin_xsz, -hin_ysz - rad); 7.247 + glVertex2f(hin_xsz, -hin_ysz - rad); 7.248 + glVertex2f(hin_xsz, -hin_ysz); 7.249 + glVertex2f(-hin_xsz, -hin_ysz); 7.250 + glEnd(); 7.251 + 7.252 + glMatrixMode(GL_MODELVIEW); 7.253 + 7.254 + glPushMatrix(); 7.255 + glTranslatef(hin_xsz, hin_ysz, 0); 7.256 + draw_fillet(rad, segm); 7.257 + glPopMatrix(); 7.258 + 7.259 + glPushMatrix(); 7.260 + glTranslatef(-hin_xsz, hin_ysz, 0); 7.261 + glRotatef(90, 0, 0, 1); 7.262 + draw_fillet(rad, segm); 7.263 + glPopMatrix(); 7.264 + 7.265 + glPushMatrix(); 7.266 + glTranslatef(-hin_xsz, -hin_ysz, 0); 7.267 + glRotatef(180, 0, 0, 1); 7.268 + draw_fillet(rad, segm); 7.269 + glPopMatrix(); 7.270 + 7.271 + glPushMatrix(); 7.272 + glTranslatef(hin_xsz, -hin_ysz, 0); 7.273 + glRotatef(270, 0, 0, 1); 7.274 + draw_fillet(rad, segm); 7.275 + glPopMatrix(); 7.276 +} 7.277 + 7.278 +void draw_fillet(float rad, int segm) 7.279 +{ 7.280 + int i; 7.281 + 7.282 + glBegin(GL_TRIANGLE_FAN); 7.283 + glVertex2f(0, 0); 7.284 + for(i=0; i<segm; i++) { 7.285 + float theta = 0.5 * M_PI * (float)i / (float)(segm - 1); 7.286 + float x = cos(theta) * rad; 7.287 + float y = sin(theta) * rad; 7.288 + glVertex2f(x, y); 7.289 + } 7.290 + glEnd(); 7.291 +} 7.292 + 7.293 + 7.294 +void reshape(int x, int y) 7.295 +{ 7.296 + win_xsz = x; 7.297 + win_ysz = y; 7.298 + 7.299 + glViewport(0, 0, x, y); 7.300 + 7.301 + glMatrixMode(GL_PROJECTION); 7.302 + glLoadIdentity(); 7.303 + glOrtho(0, x, 0, y, -1, 1); 7.304 +} 7.305 + 7.306 +void keyb(unsigned char key, int x, int y) 7.307 +{ 7.308 + static int wposx = -1, wposy; 7.309 + static char *inp_next; 7.310 + static char op; 7.311 + 7.312 + switch(key) { 7.313 + case 27: 7.314 + exit(0); 7.315 + 7.316 + case 'a': 7.317 + rb_inserti(tree, num_nodes++, 0); 7.318 + glutPostRedisplay(); 7.319 + break; 7.320 + 7.321 + case 'r': 7.322 + { 7.323 + int x; 7.324 + do { 7.325 + x = rand() % 1024; 7.326 + } while(rb_findi(tree, x)); 7.327 + 7.328 + rb_inserti(tree, x, 0); 7.329 + } 7.330 + glutPostRedisplay(); 7.331 + break; 7.332 + 7.333 + case 'd': 7.334 + case 'f': 7.335 + op = key; 7.336 + inp_next = input_buffer; 7.337 + *inp_next++ = ' '; 7.338 + *inp_next = 0; 7.339 + glutPostRedisplay(); 7.340 + break; 7.341 + 7.342 + case '0': 7.343 + case '1': 7.344 + case '2': 7.345 + case '3': 7.346 + case '4': 7.347 + case '5': 7.348 + case '6': 7.349 + case '7': 7.350 + case '8': 7.351 + case '9': 7.352 + if(inp_next) { 7.353 + *inp_next++ = key; 7.354 + *inp_next = 0; 7.355 + glutPostRedisplay(); 7.356 + } 7.357 + break; 7.358 + 7.359 + case '\b': 7.360 + if(inp_next > input_buffer) { 7.361 + *--inp_next = 0; 7.362 + glutPostRedisplay(); 7.363 + } 7.364 + break; 7.365 + 7.366 + case '\n': 7.367 + case '\r': 7.368 + if(inp_next) { 7.369 + int x; 7.370 + char *endp; 7.371 + 7.372 + *inp_next = 0; 7.373 + inp_next = 0; 7.374 + 7.375 + if((x = strtol(input_buffer, &endp, 10)), endp == input_buffer) { 7.376 + fprintf(stderr, "invalid input: %s\n", input_buffer); 7.377 + } else if(!rb_findi(tree, x)) { 7.378 + fprintf(stderr, "%d not found in the tree\n", x); 7.379 + } else { 7.380 + if(op == 'd') { 7.381 + printf("deleting: %d\n", x); 7.382 + rb_deletei(tree, x); 7.383 + } else { 7.384 + printf("%d found!\n", x); 7.385 + } 7.386 + } 7.387 + input_buffer[0] = 0; 7.388 + glutPostRedisplay(); 7.389 + } 7.390 + break; 7.391 + 7.392 + case 'p': 7.393 + { 7.394 + struct rbnode *node; 7.395 + 7.396 + rb_begin(tree); 7.397 + while((node = rb_next(tree))) { 7.398 + int key = rb_node_keyi(node); 7.399 + printf("%d ", key); 7.400 + } 7.401 + putchar('\n'); 7.402 + } 7.403 + break; 7.404 + } 7.405 +} 7.406 +