Mercurial > public > algo-animator

comparison src/main.c @ 29:dae463bbf5ca

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
implementing multi-thread and refactoring
author Dennis C. M. <dennis@denniscm.com>
date Wed, 28 Jun 2023 20:10:55 +0100
parents 30b6812fefdd
children f945bcc3571f
comparison
equal deleted inserted replaced
28:99592fae8ea1 29:dae463bbf5ca
1 #include <stdio.h> 1 #include "algorithms.h"
2 #include <stdlib.h>
3 #include <GL/glut.h> 2 #include <GL/glut.h>
4 #include <math.h> 3 #include <pthread.h>
5 #include <time.h>
6 #include <stdbool.h>
7 #include <ft2build.h> 4 #include <ft2build.h>
8 #include FT_FREETYPE_H 5 #include FT_FREETYPE_H
9 6
10 7
11 #define WINDOW_WIDTH 1920 8 int window_width = 1920;
12 #define WINDOW_HEIGHT 1080 9 int window_height = 1080;
13 #define VPADDING 150 10 int vpadding = 150;
14 #define RECT_WIDTH 5 11 int rect_width = 5;
15 #define SPACE 1 12 int space = 1;
16 13
17 14 struct Algo algos[1];
18 /* Helper functions */
19
20 struct Element {
21 float value;
22 bool current;
23 };
24
25 struct Element *arr;
26 int arr_size;
27
28 void create_array() {
29 arr_size = WINDOW_WIDTH / (RECT_WIDTH + SPACE);
30 arr = malloc(arr_size * sizeof(struct Element));
31
32 float rect_increase = (WINDOW_HEIGHT - VPADDING * 2) / (float)(arr_size - 1);
33
34 for (int i = 1; i <= arr_size; i++) {
35 arr[i - 1].value = i * rect_increase;
36 arr[i - 1].current = false;
37 }
38 }
39
40
41 void swap_elements(int x, int y) {
42 struct Element temp = arr[x];
43 arr[x] = arr[y];
44 arr[y] = temp;
45 }
46
47
48 void randomize_array() {
49 srand(time(NULL));
50
51 // Fisher-Yates shuffle
52 for (int i = arr_size - 1; i > 0; i--) {
53 int j = rand() % (i + 1);
54
55 // Swap
56 swap_elements(i, j);
57 }
58 }
59
60
61 bool array_sorted() {
62 for (int i = 0; i < arr_size - 1; i++) {
63 if (arr[i].value > arr[i + 1].value) {
64 return false;
65 }
66 }
67
68 return true;
69 }
70
71
72 struct Algo {
73 char name[50];
74 void (*function)();
75 };
76
77 struct Algo algos[2];
78 int selected_algo = 0; 15 int selected_algo = 0;
79 16
80 void algo_selector(int direction) { 17 struct AlgoArgs algo_args;
81 int selection = selected_algo + direction;
82 int lower = 0;
83 int upper = (sizeof(algos) / sizeof(algos[0])) - 1;
84
85 if (selection >= lower && selection <= upper) {
86 selected_algo = selection;
87 }
88 }
89
90
91 /* Algorithms */
92
93 // Just some variables to store the state of the running algorithm
94 struct AlgoState {
95 int a;
96 int b;
97 int c;
98 };
99
100 struct AlgoState as;
101
102 void reset_state() {
103 as.a = 0;
104 as.b = 0;
105 as.c = 0;
106 }
107
108
109 void bubble_sort() {
110
111 /*
112 * a: Index of the current selection
113 * b: Index boundary of the sorted array
114 */
115
116 if (as.a < arr_size - 1 - as.b) {
117 arr[as.a].current = true;
118
119 if (arr[as.a].value > arr[as.a + 1].value) {
120 swap_elements(as.a + 1, as.a);
121 }
122
123 as.a++;
124 } else {
125 as.b++;
126 as.a = 0;
127 }
128 }
129
130
131 void selection_sort() {
132
133 /*
134 * a: Index of current selection
135 * b: Index of boundary of sorted array
136 * c: Index of the minimum element
137 */
138
139
140 if (as.a < arr_size) {
141 arr[as.a].current = true;
142
143 if (arr[as.a].value < arr[as.c].value) {
144
145 // Save new minimum
146 as.c = as.a;
147 }
148
149 as.a++;
150 } else {
151 swap_elements(as.b, as.c);
152
153 as.b++;
154 as.a = as.b;
155 as.c = as.a;
156 }
157 }
158
159
160 void quick_sort() {
161
162 }
163
164
165 void insertion_sort() {
166
167 }
168
169
170 void merge_sort() {
171
172 }
173
174
175 /* Render functions */
176 18
177 FT_Library ft_library; 19 FT_Library ft_library;
178 FT_Face ft_face; 20 FT_Face ft_face;
21
22 pthread_t thread_id;
23
179 24
180 void render_text(int x, int y, char* text) { 25 void render_text(int x, int y, char* text) {
181 for (const char *c = text; *c; c++) { 26 for (const char *c = text; *c; c++) {
182 27
183 // Get glyph index from character code 28 // Get glyph index from character code
223 x += slot->advance.x / 64; 68 x += slot->advance.x / 64;
224 } 69 }
225 } 70 }
226 71
227 72
228 int speed = 50;
229 int iter_counter = 0;
230
231 void display() { 73 void display() {
232 glClear(GL_COLOR_BUFFER_BIT); 74 glClear(GL_COLOR_BUFFER_BIT);
233 75
234 glBegin(GL_QUADS); 76 glBegin(GL_QUADS);
235 77
236 int x = 0; 78 int x = 0;
237 for (int i = 0; i < arr_size; i++) { 79 for (int i = 0; i < algo_args.arr_size; i++) {
238 80
239 if (arr[i].current) { 81 if (algo_args.arr[i].current) {
240 glColor3f(1.0, 1.0, 1.0); 82 glColor3f(1.0, 1.0, 1.0);
241 } else { 83 } else {
242 glColor3f(1.0, 0.7569, 0.0); 84 glColor3f(1.0, 0.7569, 0.0);
243 } 85 }
244 86
245 // Bottom left 87 // Bottom left
246 glVertex2f(x, VPADDING); 88 glVertex2f(x, vpadding);
247 89
248 // Top left 90 // Top left
249 glVertex2f(x, VPADDING + arr[i].value); 91 glVertex2f(x, vpadding + algo_args.arr[i].value);
250 92
251 // Top right 93 // Top right
252 glVertex2f(x + RECT_WIDTH, VPADDING + arr[i].value); 94 glVertex2f(x + rect_width, vpadding + algo_args.arr[i].value);
253 95
254 // Bottom right 96 // Bottom right
255 glVertex2f(x + RECT_WIDTH, VPADDING); 97 glVertex2f(x + rect_width, vpadding);
256 98
257 x += RECT_WIDTH + SPACE; 99 x += rect_width + space;
258 100
259 arr[i].current = false; 101 algo_args.arr[i].current = false;
260 } 102 }
261 103
262 glEnd(); 104 glEnd();
263 105
264 // Render text 106 // Render text
265 char text[256]; 107 char text[256];
266 108
267 // Top: Column 1 109 // Top: Column 1
268 sprintf(text, "Algorithm: %s", algos[selected_algo].name); 110 sprintf(text, "Algorithm: %s", algos[selected_algo].name);
269 render_text(20, WINDOW_HEIGHT - 50, text); 111 render_text(20, window_height - 50, text);
270 112
271 sprintf(text, "Speed: %i", speed); 113 sprintf(text, "Delay: %u microseconds", algo_args.delay);
272 render_text(20, WINDOW_HEIGHT - 80, text); 114 render_text(20, window_height - 80, text);
273 115
274 // Top: Column 2 116 // Top: Column 2
275 sprintf(text, "Number of elements: %i", arr_size); 117 sprintf(text, "Number of elements: %i", algo_args.arr_size);
276 render_text(500, WINDOW_HEIGHT - 50, text); 118 render_text(500, window_height - 50, text);
277 119
278 sprintf(text, "Iterations: %i", iter_counter); 120 sprintf(text, "Comparisons: %i", algo_args.comparisons);
279 render_text(500, WINDOW_HEIGHT - 80, text); 121 render_text(500, window_height - 80, text);
280
281 122
282 // Bottom: Column 1 123 // Bottom: Column 1
283 render_text(20, VPADDING - 50, "Press a or s to select an algorithm."); 124 render_text(20, vpadding - 50, "Press a or s to select an algorithm.");
284 render_text(20, VPADDING - 80, "Press u or d to modify speed."); 125 render_text(20, vpadding - 80, "Press u or d to modify speed.");
285 render_text(20, VPADDING - 110, "Press r to randomize the array."); 126 render_text(20, vpadding - 110, "Press r to randomize the array.");
286 127
287 // Bottom: Column 2 128 // Bottom: Column 2
288 render_text(800, VPADDING - 50, "Press enter to run the algorithm."); 129 render_text(800, vpadding - 50, "Press enter to run the algorithm.");
289 render_text(800, VPADDING - 80, "Press p to pause the algorithm."); 130 render_text(800, vpadding - 80, "Press p to pause the algorithm.");
290 131
291 glutSwapBuffers(); 132 glutSwapBuffers();
292 } 133 }
293 134
294 135
295 /* Refresh function */
296
297
298 bool run;
299 int refresh_counter = 0;
300
301 void idle() { 136 void idle() {
302 if (run) { 137 glutPostRedisplay();
303 algos[selected_algo].function(); 138 }
304 refresh_counter++; 139
305 iter_counter++;
306
307 if (refresh_counter == speed) {
308 glutPostRedisplay();
309 refresh_counter = 0;
310 }
311
312 } else {
313 glutPostRedisplay();
314 }
315
316 if (array_sorted()) {
317 run = false;
318 }
319 }
320
321
322 /* User input handler */
323 140
324 void keyboard(unsigned char key, int x, int y) { 141 void keyboard(unsigned char key, int x, int y) {
325 142
326 // s: Next algorithm 143 // s: Next algorithm
327 if (key == 115) { 144 if (key == 115) {
328 algo_selector(1); 145
329 } 146 }
330 147
331 // a: Previous algorithm 148 // a: Previous algorithm
332 if (key == 97) { 149 if (key == 97) {
333 algo_selector(-1); 150
334 } 151 }
335 152
336 // r: Reset state 153 // r: Reset state
337 if (key == 114) { 154 if (key == 114) {
338 randomize_array(); 155 randomize_array(algo_args.arr, algo_args.arr_size);
339
340 // Reset state
341 iter_counter = 0;
342 refresh_counter = 0;
343 run = false;
344
345 // Reset algo steps
346 reset_state();
347 } 156 }
348 157
349 // u: Increase speed 158 // u: Increase speed
350 if (key == 117) { 159 if (key == 117) {
351 speed++; 160 algo_args.delay += 10;
352 } 161 }
353 162
354 // d: reduce speed 163 // d: reduce speed
355 if (key == 100) { 164 if (key == 100) {
356 if (speed > 1) { 165 if (algo_args.delay > 10) {
357 speed--; 166 algo_args.delay -= 10;
358 } 167 }
359 } 168 }
360 169
361 // enter: Run program 170 // enter: Run program
362 if (key == 13) { 171 if (key == 13) {
363 run = true; 172 pthread_create(&thread_id, NULL, algos[selected_algo].function, (void *)&algo_args);
364 } 173 }
365 174
366 // p: Pause program 175 // p: Pause program
367 if (key == 112) { 176 if (key == 112) {
368 run = false; 177
369 } 178 }
370 } 179 }
371 180
372
373 /* Set up functions */
374 181
375 void setup_gl() { 182 void setup_gl() {
376 183
377 // Set background dark 184 // Set background dark
378 glClearColor(0.0, 0.0, 0.0, 1.0); 185 glClearColor(0.0, 0.0, 0.0, 1.0);
383 190
384 // Matrix projection and reset with identity 191 // Matrix projection and reset with identity
385 glMatrixMode(GL_PROJECTION); 192 glMatrixMode(GL_PROJECTION);
386 glLoadIdentity(); 193 glLoadIdentity();
387 194
388 /* 195 /*
389 * Creates projection matrix 196 * Creates projection matrix
390 * x increases from left to right (0 to WINDOW_WIDTH) 197 * x increases from left to right (0 to WINDOW_WIDTH)
391 * y increases from bottom to top (0 to WINDOW_HEIGHT) 198 * y increases from bottom to top (0 to WINDOW_HEIGHT)
392 */ 199 */
393 200
394 gluOrtho2D(0, WINDOW_WIDTH, 0, WINDOW_HEIGHT); 201 gluOrtho2D(0, window_width, 0, window_height);
395 202
396 /* 203 /*
397 * This fucking line... I spent a day rendering weird symbols 204 * This fucking line... I spent a day rendering weird symbols
398 * because the padding that adds FreeType to each row of the bitmap 205 * because the padding that adds FreeType to each row of the bitmap
399 * does not match the padding expected by GL. 206 * does not match the padding expected by GL.
400 */ 207 */
401 208
427 } 234 }
428 } 235 }
429 236
430 237
431 int main(int argc, char** argv) { 238 int main(int argc, char** argv) {
239 algo_args.comparisons = 0;
240 algo_args.delay = 100;
241
432 strcpy(algos[0].name, "Bubble sort"); 242 strcpy(algos[0].name, "Bubble sort");
433 algos[0].function = &bubble_sort; 243 algos[0].function = bubble_sort;
434 244
435 strcpy(algos[1].name, "Selection sort"); 245 algo_args.arr_size = window_width / (rect_width + space);
436 algos[1].function = &selection_sort; 246 algo_args.arr = malloc(algo_args.arr_size * sizeof(struct Element));
437 247
438 create_array(); 248 create_array(algo_args.arr, algo_args.arr_size, window_height, vpadding);
249 randomize_array(algo_args.arr, algo_args.arr_size);
439 250
440 glutInit(&argc, argv); 251 glutInit(&argc, argv);
441 glutInitDisplayMode(GLUT_DOUBLE | GLUT_RGB); 252 glutInitDisplayMode(GLUT_DOUBLE | GLUT_RGB);
442 glutInitWindowSize(WINDOW_WIDTH, WINDOW_HEIGHT); 253 glutInitWindowSize(window_width, window_height);
443 glutCreateWindow("Algorithm animator"); 254 glutCreateWindow("Algorithm animator");
444 255
445 setup_gl(); 256 setup_gl();
446 setup_freetype(); 257 setup_freetype();
447 258
448 glutDisplayFunc(display); 259 glutDisplayFunc(display);
449 glutKeyboardFunc(keyboard); 260 glutKeyboardFunc(keyboard);
450 glutIdleFunc(idle); 261 glutIdleFunc(idle);
451 glutMainLoop(); 262 glutMainLoop();
452 263
453 free(arr); 264 free(algo_args.arr);
454 265
455 FT_Done_Face(ft_face); 266 FT_Done_Face(ft_face);
456 FT_Done_FreeType(ft_library); 267 FT_Done_FreeType(ft_library);
457 268
458 return 0; 269 return 0;