rbtree: 53afe96233f2 test/test.c

rbtree

view test/test.c @ 3:53afe96233f2

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

line source

1 #include <stdio.h>

2 #include <stdlib.h>

3 #include <string.h>

4 #include <ctype.h>

5 #include <math.h>

6 #include <assert.h>

7 #include <alloca.h>

9 #ifndef __APPLE__

10 #include <GL/glut.h>

11 #else

12 #include <GLUT/glut.h>

13 #endif

14 #include <rbtree.h>

15 #include <drawtext.h>

17 #define FONTSZ 18

19 void init_gl(int argc, char **argv);

20 float rbvis_width(struct rbnode *tree);

21 void rbvis_draw(struct rbnode *tree, float x, float y);

23 void draw_roundbox(float xsz, float ysz, float rad, int segm, const float *col, float border, const float *bcol);

24 void draw_fillet(float rad, int segm);

26 struct rbtree *tree;

27 int num_nodes;

28 struct dtx_font *font;

29 char input_buffer[64];

30 int win_xsz, win_ysz;

32 int main(int argc, char **argv)

33 {

34 int i;

36 if(argv[1]) {

37 if(!isdigit(argv[1][0])) {

38 fprintf(stderr, "pass a fucking number, not: %s\n", argv[1]);

39 return 1;

40 }

41 num_nodes = atoi(argv[1]);

42 }

44 if(!(font = dtx_open_font("linux-libertine.ttf", FONTSZ))) {

45 fprintf(stderr, "failed to open font\n");

46 return 1;

47 }

49 if(!(tree = rb_create(RB_KEY_INT))) {

50 return 1;

51 }

53 for(i=0; i<num_nodes; i++) {

54 rb_inserti(tree, i, 0);

55 }

57 init_gl(argc, argv);

58 return 0;

59 }

61 #define NWIDTH 28.0

62 #define NHEIGHT 24.0

63 #define PADDING 0

64 #define DY (NHEIGHT + NHEIGHT / 2.0)

66 #define VIS(node) ((struct visinfo*)(node)->data)

68 void disp(void);

69 void reshape(int x, int y);

70 void keyb(unsigned char key, int x, int y);

71 void draw_rect(float x, float y, float width, float height, const char *text, int red);

72 void draw_link(float x0, float y0, float x1, float y1, int red);

74 void init_gl(int argc, char **argv)

75 {

76 glutInitWindowSize(1280, 720);

77 glutInit(&argc, argv);

78 glutInitDisplayMode(GLUT_RGB | GLUT_DOUBLE | GLUT_MULTISAMPLE);

80 glutCreateWindow("foo");

82 dtx_use_font(font, FONTSZ);

84 glutDisplayFunc(disp);

85 glutReshapeFunc(reshape);

86 glutKeyboardFunc(keyb);

88 glEnable(GL_DEPTH_TEST);

89 glEnable(GL_MULTISAMPLE);

91 glutMainLoop();

92 }

94 void disp(void)

95 {

96 struct rbnode *root = rb_root(tree);

98 glClearColor(0.57, 0.64, 0.59, 1.0);

99 glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);

100

101 glMatrixMode(GL_MODELVIEW);

102 glLoadIdentity();

103

104 if(input_buffer[0]) {

105 char *prompt = "select node: ";

106 char *buf = alloca(strlen(prompt) + strlen(input_buffer));

107

108 glPushMatrix();

109 glTranslatef(10, 10, -0.9);

110 glColor3f(0, 0, 0);

111 sprintf(buf, "%s%s", prompt, input_buffer);

112 dtx_string(buf);

113 glPopMatrix();

114 }

115

116 if(root) {

117 rbvis_draw(root, rbvis_width(root->left) + NWIDTH, 550);

118 }

119

120 glutSwapBuffers();

121 assert(glGetError() == GL_NO_ERROR);

122 }

123

124

125 float rbvis_width(struct rbnode *tree)

126 {

127 if(!tree)

128 return NWIDTH;

129

130 return NWIDTH + rbvis_width(tree->left) + rbvis_width(tree->right) + PADDING * 3.0;

131 }

132

133 void rbvis_draw(struct rbnode *tree, float x, float y)

134 {

135 float leftx, rightx, nexty;

136 static const float hxsz = NWIDTH / 2.0;

137 static const float hysz = NHEIGHT / 2.0;

138 char text[16];

139

140 if(!tree)

141 return;

142

143 leftx = x - (tree->left ? rbvis_width(tree->left->right) + NWIDTH : rbvis_width(tree->left) / 2.0);

144 rightx = x + (tree->right ? rbvis_width(tree->right->left) + NWIDTH : rbvis_width(tree->right) / 2.0);

145

146 nexty = y - DY;

147

148 sprintf(text, "%d", rb_node_keyi(tree));

149 draw_rect(x - hxsz, y - hysz, NWIDTH, NHEIGHT, text, tree->red);

150

151 rbvis_draw(tree->left, leftx, nexty);

152 rbvis_draw(tree->right, rightx, nexty);

153

154 if(tree->left)

155 draw_link(x, y, leftx, nexty, tree->left->red);

156 if(tree->right)

157 draw_link(x, y, rightx, nexty, tree->right->red);

158 }

159

160 void draw_rect(float x, float y, float width, float height, const char *text, int red)

161 {

162 float node_col[] = {0.63, 0.71, 0.82, 1.0};

163 float bord_col[] = {0, 0, 0, 1};

164

165 if(red) {

166 bord_col[0] = 1.0;

167 }

168

169 glMatrixMode(GL_MODELVIEW);

170 glPushMatrix();

171 glTranslatef(x + width / 2.0, y + height / 2.0, 0.0);

172

173 draw_roundbox(width, height, 8, 6, node_col, 1.2, bord_col);

174

175 glColor3f(0.15, 0.15, 0.15);

176 glTranslatef(-dtx_string_width(text) / 2.0, -dtx_string_height(text) / 2.0, 0.1);

177 dtx_string(text);

178 glMatrixMode(GL_MODELVIEW);

179 glPopMatrix();

180 }

181

182 void draw_link(float x0, float y0, float x1, float y1, int red)

183 {

184 glPushAttrib(GL_LINE_BIT);

185 if(red) {

186 glLineWidth(3);

187 } else {

188 glLineWidth(2);

189 }

190

191 glBegin(GL_LINES);

192 if(red) {

193 glColor3f(0.8, 0.36, 0.3);

194 } else {

195 glColor3f(0, 0, 0);

196 }

197 glVertex3f(x0, y0, -0.8);

198 glVertex3f(x1, y1, -0.8);

199 glEnd();

200

201 glPopAttrib();

202 }

203

204 void draw_roundbox(float xsz, float ysz, float rad, int segm, const float *col, float border, const float *bcol)

205 {

206 float hin_xsz, hin_ysz;

207

208 if(border > 0.0f) {

209 glPushMatrix();

210 glTranslatef(0, 0, -0.001);

211 draw_roundbox(xsz + 2 * border, ysz + 2 * border, rad + border, segm, bcol, 0.0, bcol);

212 glPopMatrix();

213 }

214

215 /* half inner size */

216 hin_xsz = (xsz - 2.0 * rad) / 2.0;

217 hin_ysz = (ysz - 2.0 * rad) / 2.0;

218

219 glColor4fv(col);

220

221 glBegin(GL_QUADS);

222 /* center */

223 glVertex2f(-hin_xsz, -hin_ysz);

224 glVertex2f(hin_xsz, -hin_ysz);

225 glVertex2f(hin_xsz, hin_ysz);

226 glVertex2f(-hin_xsz, hin_ysz);

227 /* right */

228 glVertex2f(hin_xsz, -hin_ysz);

229 glVertex2f(hin_xsz + rad, -hin_ysz);

230 glVertex2f(hin_xsz + rad, hin_ysz);

231 glVertex2f(hin_xsz, hin_ysz);

232 /* top */

233 glVertex2f(-hin_xsz, hin_ysz);

234 glVertex2f(hin_xsz, hin_ysz);

235 glVertex2f(hin_xsz, hin_ysz + rad);

236 glVertex2f(-hin_xsz, hin_ysz + rad);

237 /* left */

238 glVertex2f(-hin_xsz - rad, -hin_ysz);

239 glVertex2f(-hin_xsz, -hin_ysz);

240 glVertex2f(-hin_xsz, hin_ysz);

241 glVertex2f(-hin_xsz - rad, hin_ysz);

242 /* bottom */

243 glVertex2f(-hin_xsz, -hin_ysz - rad);

244 glVertex2f(hin_xsz, -hin_ysz - rad);

245 glVertex2f(hin_xsz, -hin_ysz);

246 glVertex2f(-hin_xsz, -hin_ysz);

247 glEnd();

248

249 glMatrixMode(GL_MODELVIEW);

250

251 glPushMatrix();

252 glTranslatef(hin_xsz, hin_ysz, 0);

253 draw_fillet(rad, segm);

254 glPopMatrix();

255

256 glPushMatrix();

257 glTranslatef(-hin_xsz, hin_ysz, 0);

258 glRotatef(90, 0, 0, 1);

259 draw_fillet(rad, segm);

260 glPopMatrix();

261

262 glPushMatrix();

263 glTranslatef(-hin_xsz, -hin_ysz, 0);

264 glRotatef(180, 0, 0, 1);

265 draw_fillet(rad, segm);

266 glPopMatrix();

267

268 glPushMatrix();

269 glTranslatef(hin_xsz, -hin_ysz, 0);

270 glRotatef(270, 0, 0, 1);

271 draw_fillet(rad, segm);

272 glPopMatrix();

273 }

274

275 void draw_fillet(float rad, int segm)

276 {

277 int i;

278

279 glBegin(GL_TRIANGLE_FAN);

280 glVertex2f(0, 0);

281 for(i=0; i<segm; i++) {

282 float theta = 0.5 * M_PI * (float)i / (float)(segm - 1);

283 float x = cos(theta) * rad;

284 float y = sin(theta) * rad;

285 glVertex2f(x, y);

286 }

287 glEnd();

288 }

289

290

291 void reshape(int x, int y)

292 {

293 win_xsz = x;

294 win_ysz = y;

295

296 glViewport(0, 0, x, y);

297

298 glMatrixMode(GL_PROJECTION);

299 glLoadIdentity();

300 glOrtho(0, x, 0, y, -1, 1);

301 }

302

303 void keyb(unsigned char key, int x, int y)

304 {

305 static int wposx = -1, wposy;

306 static char *inp_next;

307 static char op;

308

309 switch(key) {

310 case 27:

311 exit(0);

312

313 case 'a':

314 rb_inserti(tree, num_nodes++, 0);

315 glutPostRedisplay();

316 break;

317

318 case 'r':

319 {

320 int x;

321 do {

322 x = rand() % 1024;

323 } while(rb_findi(tree, x));

324

325 rb_inserti(tree, x, 0);

326 }

327 glutPostRedisplay();

328 break;

329

330 case 'd':

331 case 'f':

332 op = key;

333 inp_next = input_buffer;

334 *inp_next++ = ' ';

335 *inp_next = 0;

336 glutPostRedisplay();

337 break;

338

339 case '0':

340 case '1':

341 case '2':

342 case '3':

343 case '4':

344 case '5':

345 case '6':

346 case '7':

347 case '8':

348 case '9':

349 if(inp_next) {

350 *inp_next++ = key;

351 *inp_next = 0;

352 glutPostRedisplay();

353 }

354 break;

355

356 case '\b':

357 if(inp_next > input_buffer) {

358 *--inp_next = 0;

359 glutPostRedisplay();

360 }

361 break;

362

363 case '\n':

364 case '\r':

365 if(inp_next) {

366 int x;

367 char *endp;

368

369 *inp_next = 0;

370 inp_next = 0;

371

372 if((x = strtol(input_buffer, &endp, 10)), endp == input_buffer) {

373 fprintf(stderr, "invalid input: %s\n", input_buffer);

374 } else if(!rb_findi(tree, x)) {

375 fprintf(stderr, "%d not found in the tree\n", x);

376 } else {

377 if(op == 'd') {

378 printf("deleting: %d\n", x);

379 rb_deletei(tree, x);

380 } else {

381 printf("%d found!\n", x);

382 }

383 }

384 input_buffer[0] = 0;

385 glutPostRedisplay();

386 }

387 break;

388

389 case 'p':

390 {

391 struct rbnode *node;

392

393 rb_begin(tree);

394 while((node = rb_next(tree))) {

395 int key = rb_node_keyi(node);

396 printf("%d ", key);

397 }

398 putchar('\n');

399 }

400 break;

401 }

402 }

403