rbtree

annotate test/test.c @ 3:53afe96233f2

find changesets by author, revision, files, or words in the commit message
changed the tail-recursive find and find_min to loops
author John Tsiombikas <nuclear@mutantstargoat.com>
date Sun, 09 Oct 2011 08:30:54 +0300
parents 7205a7d8d3d6
children
rev   line source
nuclear@0 1 #include <stdio.h>
nuclear@0 2 #include <stdlib.h>
nuclear@0 3 #include <string.h>
nuclear@0 4 #include <ctype.h>
nuclear@0 5 #include <math.h>
nuclear@0 6 #include <assert.h>
nuclear@0 7 #include <alloca.h>
nuclear@0 8
nuclear@0 9 #ifndef __APPLE__
nuclear@0 10 #include <GL/glut.h>
nuclear@0 11 #else
nuclear@0 12 #include <GLUT/glut.h>
nuclear@0 13 #endif
nuclear@0 14 #include <rbtree.h>
nuclear@0 15 #include <drawtext.h>
nuclear@0 16
nuclear@0 17 #define FONTSZ 18
nuclear@0 18
nuclear@0 19 void init_gl(int argc, char **argv);
nuclear@0 20 float rbvis_width(struct rbnode *tree);
nuclear@0 21 void rbvis_draw(struct rbnode *tree, float x, float y);
nuclear@0 22
nuclear@0 23 void draw_roundbox(float xsz, float ysz, float rad, int segm, const float *col, float border, const float *bcol);
nuclear@0 24 void draw_fillet(float rad, int segm);
nuclear@0 25
nuclear@0 26 struct rbtree *tree;
nuclear@0 27 int num_nodes;
nuclear@0 28 struct dtx_font *font;
nuclear@0 29 char input_buffer[64];
nuclear@0 30 int win_xsz, win_ysz;
nuclear@0 31
nuclear@0 32 int main(int argc, char **argv)
nuclear@0 33 {
nuclear@0 34 int i;
nuclear@0 35
nuclear@0 36 if(argv[1]) {
nuclear@0 37 if(!isdigit(argv[1][0])) {
nuclear@0 38 fprintf(stderr, "pass a fucking number, not: %s\n", argv[1]);
nuclear@0 39 return 1;
nuclear@0 40 }
nuclear@0 41 num_nodes = atoi(argv[1]);
nuclear@0 42 }
nuclear@0 43
nuclear@0 44 if(!(font = dtx_open_font("linux-libertine.ttf", FONTSZ))) {
nuclear@0 45 fprintf(stderr, "failed to open font\n");
nuclear@0 46 return 1;
nuclear@0 47 }
nuclear@0 48
nuclear@0 49 if(!(tree = rb_create(RB_KEY_INT))) {
nuclear@0 50 return 1;
nuclear@0 51 }
nuclear@0 52
nuclear@0 53 for(i=0; i<num_nodes; i++) {
nuclear@0 54 rb_inserti(tree, i, 0);
nuclear@0 55 }
nuclear@0 56
nuclear@0 57 init_gl(argc, argv);
nuclear@0 58 return 0;
nuclear@0 59 }
nuclear@0 60
nuclear@0 61 #define NWIDTH 28.0
nuclear@0 62 #define NHEIGHT 24.0
nuclear@0 63 #define PADDING 0
nuclear@0 64 #define DY (NHEIGHT + NHEIGHT / 2.0)
nuclear@0 65
nuclear@0 66 #define VIS(node) ((struct visinfo*)(node)->data)
nuclear@0 67
nuclear@0 68 void disp(void);
nuclear@0 69 void reshape(int x, int y);
nuclear@0 70 void keyb(unsigned char key, int x, int y);
nuclear@0 71 void draw_rect(float x, float y, float width, float height, const char *text, int red);
nuclear@0 72 void draw_link(float x0, float y0, float x1, float y1, int red);
nuclear@0 73
nuclear@0 74 void init_gl(int argc, char **argv)
nuclear@0 75 {
nuclear@0 76 glutInitWindowSize(1280, 720);
nuclear@0 77 glutInit(&argc, argv);
nuclear@0 78 glutInitDisplayMode(GLUT_RGB | GLUT_DOUBLE | GLUT_MULTISAMPLE);
nuclear@0 79
nuclear@0 80 glutCreateWindow("foo");
nuclear@0 81
nuclear@0 82 dtx_use_font(font, FONTSZ);
nuclear@0 83
nuclear@0 84 glutDisplayFunc(disp);
nuclear@0 85 glutReshapeFunc(reshape);
nuclear@0 86 glutKeyboardFunc(keyb);
nuclear@0 87
nuclear@0 88 glEnable(GL_DEPTH_TEST);
nuclear@0 89 glEnable(GL_MULTISAMPLE);
nuclear@0 90
nuclear@0 91 glutMainLoop();
nuclear@0 92 }
nuclear@0 93
nuclear@0 94 void disp(void)
nuclear@0 95 {
nuclear@0 96 struct rbnode *root = rb_root(tree);
nuclear@0 97
nuclear@0 98 glClearColor(0.57, 0.64, 0.59, 1.0);
nuclear@0 99 glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);
nuclear@0 100
nuclear@0 101 glMatrixMode(GL_MODELVIEW);
nuclear@0 102 glLoadIdentity();
nuclear@0 103
nuclear@0 104 if(input_buffer[0]) {
nuclear@3 105 char *prompt = "select node: ";
nuclear@0 106 char *buf = alloca(strlen(prompt) + strlen(input_buffer));
nuclear@0 107
nuclear@0 108 glPushMatrix();
nuclear@0 109 glTranslatef(10, 10, -0.9);
nuclear@0 110 glColor3f(0, 0, 0);
nuclear@0 111 sprintf(buf, "%s%s", prompt, input_buffer);
nuclear@0 112 dtx_string(buf);
nuclear@0 113 glPopMatrix();
nuclear@0 114 }
nuclear@0 115
nuclear@0 116 if(root) {
nuclear@0 117 rbvis_draw(root, rbvis_width(root->left) + NWIDTH, 550);
nuclear@0 118 }
nuclear@0 119
nuclear@0 120 glutSwapBuffers();
nuclear@0 121 assert(glGetError() == GL_NO_ERROR);
nuclear@0 122 }
nuclear@0 123
nuclear@0 124
nuclear@0 125 float rbvis_width(struct rbnode *tree)
nuclear@0 126 {
nuclear@0 127 if(!tree)
nuclear@0 128 return NWIDTH;
nuclear@0 129
nuclear@0 130 return NWIDTH + rbvis_width(tree->left) + rbvis_width(tree->right) + PADDING * 3.0;
nuclear@0 131 }
nuclear@0 132
nuclear@0 133 void rbvis_draw(struct rbnode *tree, float x, float y)
nuclear@0 134 {
nuclear@0 135 float leftx, rightx, nexty;
nuclear@0 136 static const float hxsz = NWIDTH / 2.0;
nuclear@0 137 static const float hysz = NHEIGHT / 2.0;
nuclear@0 138 char text[16];
nuclear@0 139
nuclear@0 140 if(!tree)
nuclear@0 141 return;
nuclear@0 142
nuclear@0 143 leftx = x - (tree->left ? rbvis_width(tree->left->right) + NWIDTH : rbvis_width(tree->left) / 2.0);
nuclear@0 144 rightx = x + (tree->right ? rbvis_width(tree->right->left) + NWIDTH : rbvis_width(tree->right) / 2.0);
nuclear@0 145
nuclear@0 146 nexty = y - DY;
nuclear@0 147
nuclear@0 148 sprintf(text, "%d", rb_node_keyi(tree));
nuclear@0 149 draw_rect(x - hxsz, y - hysz, NWIDTH, NHEIGHT, text, tree->red);
nuclear@0 150
nuclear@0 151 rbvis_draw(tree->left, leftx, nexty);
nuclear@0 152 rbvis_draw(tree->right, rightx, nexty);
nuclear@0 153
nuclear@0 154 if(tree->left)
nuclear@0 155 draw_link(x, y, leftx, nexty, tree->left->red);
nuclear@0 156 if(tree->right)
nuclear@0 157 draw_link(x, y, rightx, nexty, tree->right->red);
nuclear@0 158 }
nuclear@0 159
nuclear@0 160 void draw_rect(float x, float y, float width, float height, const char *text, int red)
nuclear@0 161 {
nuclear@0 162 float node_col[] = {0.63, 0.71, 0.82, 1.0};
nuclear@0 163 float bord_col[] = {0, 0, 0, 1};
nuclear@0 164
nuclear@0 165 if(red) {
nuclear@0 166 bord_col[0] = 1.0;
nuclear@0 167 }
nuclear@0 168
nuclear@0 169 glMatrixMode(GL_MODELVIEW);
nuclear@0 170 glPushMatrix();
nuclear@0 171 glTranslatef(x + width / 2.0, y + height / 2.0, 0.0);
nuclear@0 172
nuclear@0 173 draw_roundbox(width, height, 8, 6, node_col, 1.2, bord_col);
nuclear@0 174
nuclear@0 175 glColor3f(0.15, 0.15, 0.15);
nuclear@0 176 glTranslatef(-dtx_string_width(text) / 2.0, -dtx_string_height(text) / 2.0, 0.1);
nuclear@0 177 dtx_string(text);
nuclear@0 178 glMatrixMode(GL_MODELVIEW);
nuclear@0 179 glPopMatrix();
nuclear@0 180 }
nuclear@0 181
nuclear@0 182 void draw_link(float x0, float y0, float x1, float y1, int red)
nuclear@0 183 {
nuclear@0 184 glPushAttrib(GL_LINE_BIT);
nuclear@0 185 if(red) {
nuclear@0 186 glLineWidth(3);
nuclear@0 187 } else {
nuclear@0 188 glLineWidth(2);
nuclear@0 189 }
nuclear@0 190
nuclear@0 191 glBegin(GL_LINES);
nuclear@0 192 if(red) {
nuclear@0 193 glColor3f(0.8, 0.36, 0.3);
nuclear@0 194 } else {
nuclear@0 195 glColor3f(0, 0, 0);
nuclear@0 196 }
nuclear@0 197 glVertex3f(x0, y0, -0.8);
nuclear@0 198 glVertex3f(x1, y1, -0.8);
nuclear@0 199 glEnd();
nuclear@0 200
nuclear@0 201 glPopAttrib();
nuclear@0 202 }
nuclear@0 203
nuclear@0 204 void draw_roundbox(float xsz, float ysz, float rad, int segm, const float *col, float border, const float *bcol)
nuclear@0 205 {
nuclear@0 206 float hin_xsz, hin_ysz;
nuclear@0 207
nuclear@0 208 if(border > 0.0f) {
nuclear@0 209 glPushMatrix();
nuclear@0 210 glTranslatef(0, 0, -0.001);
nuclear@0 211 draw_roundbox(xsz + 2 * border, ysz + 2 * border, rad + border, segm, bcol, 0.0, bcol);
nuclear@0 212 glPopMatrix();
nuclear@0 213 }
nuclear@0 214
nuclear@0 215 /* half inner size */
nuclear@0 216 hin_xsz = (xsz - 2.0 * rad) / 2.0;
nuclear@0 217 hin_ysz = (ysz - 2.0 * rad) / 2.0;
nuclear@0 218
nuclear@0 219 glColor4fv(col);
nuclear@0 220
nuclear@0 221 glBegin(GL_QUADS);
nuclear@0 222 /* center */
nuclear@0 223 glVertex2f(-hin_xsz, -hin_ysz);
nuclear@0 224 glVertex2f(hin_xsz, -hin_ysz);
nuclear@0 225 glVertex2f(hin_xsz, hin_ysz);
nuclear@0 226 glVertex2f(-hin_xsz, hin_ysz);
nuclear@0 227 /* right */
nuclear@0 228 glVertex2f(hin_xsz, -hin_ysz);
nuclear@0 229 glVertex2f(hin_xsz + rad, -hin_ysz);
nuclear@0 230 glVertex2f(hin_xsz + rad, hin_ysz);
nuclear@0 231 glVertex2f(hin_xsz, hin_ysz);
nuclear@0 232 /* top */
nuclear@0 233 glVertex2f(-hin_xsz, hin_ysz);
nuclear@0 234 glVertex2f(hin_xsz, hin_ysz);
nuclear@0 235 glVertex2f(hin_xsz, hin_ysz + rad);
nuclear@0 236 glVertex2f(-hin_xsz, hin_ysz + rad);
nuclear@0 237 /* left */
nuclear@0 238 glVertex2f(-hin_xsz - rad, -hin_ysz);
nuclear@0 239 glVertex2f(-hin_xsz, -hin_ysz);
nuclear@0 240 glVertex2f(-hin_xsz, hin_ysz);
nuclear@0 241 glVertex2f(-hin_xsz - rad, hin_ysz);
nuclear@0 242 /* bottom */
nuclear@0 243 glVertex2f(-hin_xsz, -hin_ysz - rad);
nuclear@0 244 glVertex2f(hin_xsz, -hin_ysz - rad);
nuclear@0 245 glVertex2f(hin_xsz, -hin_ysz);
nuclear@0 246 glVertex2f(-hin_xsz, -hin_ysz);
nuclear@0 247 glEnd();
nuclear@0 248
nuclear@0 249 glMatrixMode(GL_MODELVIEW);
nuclear@0 250
nuclear@0 251 glPushMatrix();
nuclear@0 252 glTranslatef(hin_xsz, hin_ysz, 0);
nuclear@0 253 draw_fillet(rad, segm);
nuclear@0 254 glPopMatrix();
nuclear@0 255
nuclear@0 256 glPushMatrix();
nuclear@0 257 glTranslatef(-hin_xsz, hin_ysz, 0);
nuclear@0 258 glRotatef(90, 0, 0, 1);
nuclear@0 259 draw_fillet(rad, segm);
nuclear@0 260 glPopMatrix();
nuclear@0 261
nuclear@0 262 glPushMatrix();
nuclear@0 263 glTranslatef(-hin_xsz, -hin_ysz, 0);
nuclear@0 264 glRotatef(180, 0, 0, 1);
nuclear@0 265 draw_fillet(rad, segm);
nuclear@0 266 glPopMatrix();
nuclear@0 267
nuclear@0 268 glPushMatrix();
nuclear@0 269 glTranslatef(hin_xsz, -hin_ysz, 0);
nuclear@0 270 glRotatef(270, 0, 0, 1);
nuclear@0 271 draw_fillet(rad, segm);
nuclear@0 272 glPopMatrix();
nuclear@0 273 }
nuclear@0 274
nuclear@0 275 void draw_fillet(float rad, int segm)
nuclear@0 276 {
nuclear@0 277 int i;
nuclear@0 278
nuclear@0 279 glBegin(GL_TRIANGLE_FAN);
nuclear@0 280 glVertex2f(0, 0);
nuclear@0 281 for(i=0; i<segm; i++) {
nuclear@0 282 float theta = 0.5 * M_PI * (float)i / (float)(segm - 1);
nuclear@0 283 float x = cos(theta) * rad;
nuclear@0 284 float y = sin(theta) * rad;
nuclear@0 285 glVertex2f(x, y);
nuclear@0 286 }
nuclear@0 287 glEnd();
nuclear@0 288 }
nuclear@0 289
nuclear@0 290
nuclear@0 291 void reshape(int x, int y)
nuclear@0 292 {
nuclear@0 293 win_xsz = x;
nuclear@0 294 win_ysz = y;
nuclear@0 295
nuclear@0 296 glViewport(0, 0, x, y);
nuclear@0 297
nuclear@0 298 glMatrixMode(GL_PROJECTION);
nuclear@0 299 glLoadIdentity();
nuclear@0 300 glOrtho(0, x, 0, y, -1, 1);
nuclear@0 301 }
nuclear@0 302
nuclear@0 303 void keyb(unsigned char key, int x, int y)
nuclear@0 304 {
nuclear@0 305 static int wposx = -1, wposy;
nuclear@0 306 static char *inp_next;
nuclear@3 307 static char op;
nuclear@0 308
nuclear@0 309 switch(key) {
nuclear@0 310 case 27:
nuclear@0 311 exit(0);
nuclear@0 312
nuclear@0 313 case 'a':
nuclear@0 314 rb_inserti(tree, num_nodes++, 0);
nuclear@0 315 glutPostRedisplay();
nuclear@0 316 break;
nuclear@0 317
nuclear@0 318 case 'r':
nuclear@0 319 {
nuclear@0 320 int x;
nuclear@0 321 do {
nuclear@0 322 x = rand() % 1024;
nuclear@0 323 } while(rb_findi(tree, x));
nuclear@0 324
nuclear@0 325 rb_inserti(tree, x, 0);
nuclear@0 326 }
nuclear@0 327 glutPostRedisplay();
nuclear@0 328 break;
nuclear@0 329
nuclear@0 330 case 'd':
nuclear@3 331 case 'f':
nuclear@3 332 op = key;
nuclear@0 333 inp_next = input_buffer;
nuclear@0 334 *inp_next++ = ' ';
nuclear@0 335 *inp_next = 0;
nuclear@0 336 glutPostRedisplay();
nuclear@0 337 break;
nuclear@0 338
nuclear@0 339 case '0':
nuclear@0 340 case '1':
nuclear@0 341 case '2':
nuclear@0 342 case '3':
nuclear@0 343 case '4':
nuclear@0 344 case '5':
nuclear@0 345 case '6':
nuclear@0 346 case '7':
nuclear@0 347 case '8':
nuclear@0 348 case '9':
nuclear@0 349 if(inp_next) {
nuclear@0 350 *inp_next++ = key;
nuclear@0 351 *inp_next = 0;
nuclear@0 352 glutPostRedisplay();
nuclear@0 353 }
nuclear@0 354 break;
nuclear@0 355
nuclear@0 356 case '\b':
nuclear@0 357 if(inp_next > input_buffer) {
nuclear@0 358 *--inp_next = 0;
nuclear@0 359 glutPostRedisplay();
nuclear@0 360 }
nuclear@0 361 break;
nuclear@0 362
nuclear@0 363 case '\n':
nuclear@0 364 case '\r':
nuclear@0 365 if(inp_next) {
nuclear@0 366 int x;
nuclear@0 367 char *endp;
nuclear@0 368
nuclear@0 369 *inp_next = 0;
nuclear@0 370 inp_next = 0;
nuclear@0 371
nuclear@0 372 if((x = strtol(input_buffer, &endp, 10)), endp == input_buffer) {
nuclear@0 373 fprintf(stderr, "invalid input: %s\n", input_buffer);
nuclear@0 374 } else if(!rb_findi(tree, x)) {
nuclear@0 375 fprintf(stderr, "%d not found in the tree\n", x);
nuclear@0 376 } else {
nuclear@3 377 if(op == 'd') {
nuclear@3 378 printf("deleting: %d\n", x);
nuclear@3 379 rb_deletei(tree, x);
nuclear@3 380 } else {
nuclear@3 381 printf("%d found!\n", x);
nuclear@3 382 }
nuclear@0 383 }
nuclear@0 384 input_buffer[0] = 0;
nuclear@0 385 glutPostRedisplay();
nuclear@0 386 }
nuclear@0 387 break;
nuclear@2 388
nuclear@2 389 case 'p':
nuclear@2 390 {
nuclear@2 391 struct rbnode *node;
nuclear@2 392
nuclear@2 393 rb_begin(tree);
nuclear@2 394 while((node = rb_next(tree))) {
nuclear@2 395 int key = rb_node_keyi(node);
nuclear@2 396 printf("%d ", key);
nuclear@2 397 }
nuclear@2 398 putchar('\n');
nuclear@2 399 }
nuclear@2 400 break;
nuclear@0 401 }
nuclear@0 402 }
nuclear@0 403