rbtree: 6621337b6378 test/test.c

rbtree

view test/test.c @ 0:6621337b6378

red-black tree lib

author	John Tsiombikas <nuclear@mutantstargoat.com>
date	Sun, 09 Oct 2011 07:48:14 +0300
parents
children	7205a7d8d3d6

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 to delete: ";

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

308 switch(key) {

309 case 27:

310 exit(0);

311

312 case 'f':

313 case 'F':

314 if(wposx >= 0) {

315 glutPositionWindow(wposx, wposy);

316 wposx = -1;

317 } else {

318 wposx = glutGet(GLUT_WINDOW_X);

319 wposy = glutGet(GLUT_WINDOW_Y);

320 glutFullScreen();

321 }

322 break;

323

324 case 'a':

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

326 glutPostRedisplay();

327 break;

328

329 case 'r':

330 {

331 int x;

332 do {

333 x = rand() % 1024;

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

335

336 rb_inserti(tree, x, 0);

337 }

338 glutPostRedisplay();

339 break;

340

341 case 'd':

342 inp_next = input_buffer;

343 *inp_next++ = ' ';

344 *inp_next = 0;

345 glutPostRedisplay();

346 break;

347

348 case '0':

349 case '1':

350 case '2':

351 case '3':

352 case '4':

353 case '5':

354 case '6':

355 case '7':

356 case '8':

357 case '9':

358 if(inp_next) {

359 *inp_next++ = key;

360 *inp_next = 0;

361 glutPostRedisplay();

362 }

363 break;

364

365 case '\b':

366 if(inp_next > input_buffer) {

367 *--inp_next = 0;

368 glutPostRedisplay();

369 }

370 break;

371

372 case '\n':

373 case '\r':

374 if(inp_next) {

375 int x;

376 char *endp;

377

378 *inp_next = 0;

379 inp_next = 0;

380

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

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

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

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

385 } else {

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

387 rb_deletei(tree, x);

388 }

389 input_buffer[0] = 0;

390 glutPostRedisplay();

391 }

392 break;

393 }

394 }

395