# HG changeset patch # User Dennis C. M. # Date 1688057316 -3600 # Node ID f945bcc3571fa037db511a4ba717fb5518eebf76 # Parent dae463bbf5ca433ed37f3a499964789fcc814331 refactor diff -r dae463bbf5ca -r f945bcc3571f src/algorithms.c --- a/src/algorithms.c Wed Jun 28 20:10:55 2023 +0100 +++ b/src/algorithms.c Thu Jun 29 17:48:36 2023 +0100 @@ -1,29 +1,60 @@ #include "algorithms.h" +/* Bubble sort */ + void *bubble_sort(void *arguments) { struct AlgoArgs *args = (struct AlgoArgs *)arguments; - printf("Size: %i\n", args->arr_size); - printf("Comparisons: %i\n", args->comparisons); - (args->comparisons)++; - printf("Comparisons: %i\n", args->comparisons); - /* - for (int i = 0; i < args->arr_size - 1; i++) { - //(*args->comparisons)++; + for (int step = 0; step < args->arr_size - 1; step++) { + int swapped = false; + + for (int i = 0; i < args->arr_size - step - 1; i++) { + args->comparisons++; + args->arr[i].current = true; + args->arr[i + 1].current = true; - for (int j = 0; j < args->arr_size - i - 1; j++) { - //(*args->comparisons)++; - - if (args->arr[j].value > args->arr[j + 1].value) { - //swap_elements(j, j + 1, args->arr); + if (args->arr[i].value > args->arr[i + 1].value) { + swap_elements(i, i + 1, args->arr); + swapped = true; } - - - //usleep((*args->delay)); - //bool test = false; - //delay_flow(args->delay, &test); + + control_flow(args->delay, args->sequentially, &args->pause); + args->arr[i].current = false; + args->arr[i + 1].current = false; + } + + if (swapped == 0) { + break; } } - */ } + + +/* Selection sort */ + +void *selection_sort(void *arguments) { + struct AlgoArgs *args = (struct AlgoArgs *)arguments; + + for (int step = 0; step < args->arr_size - 1; step++) { + int min_idx = step; + + for (int i = step + 1; i < args->arr_size; i++) { + args->comparisons++; + args->arr[i].current = true; + + if (args->arr[i].value < args->arr[min_idx].value) { + min_idx = i; + } + + control_flow(args->delay, args->sequentially, &args->pause); + } + + swap_elements(min_idx, step, args->arr); + } +} + + +/* Quick sort */ + + diff -r dae463bbf5ca -r f945bcc3571f src/algorithms.h --- a/src/algorithms.h Wed Jun 28 20:10:55 2023 +0100 +++ b/src/algorithms.h Thu Jun 29 17:48:36 2023 +0100 @@ -4,15 +4,8 @@ #include "utils.h" -struct AlgoArgs { - struct Element *arr; - int arr_size; - int *comparisons; - useconds_t *delay; - bool pause; -}; - void *bubble_sort(void *arguments); +void *selection_sort(void *arguments); #endif // ALGORITHMS_H diff -r dae463bbf5ca -r f945bcc3571f src/main.c --- a/src/main.c Wed Jun 28 20:10:55 2023 +0100 +++ b/src/main.c Thu Jun 29 17:48:36 2023 +0100 @@ -1,26 +1,22 @@ #include "algorithms.h" -#include -#include -#include -#include FT_FREETYPE_H int window_width = 1920; int window_height = 1080; int vpadding = 150; -int rect_width = 5; +int rect_width = 30; int space = 1; -struct Algo algos[1]; +struct Algo algos[2]; int selected_algo = 0; +int algos_size; struct AlgoArgs algo_args; +struct ThreadState thread_state; FT_Library ft_library; FT_Face ft_face; -pthread_t thread_id; - void render_text(int x, int y, char* text) { for (const char *c = text; *c; c++) { @@ -49,11 +45,14 @@ FT_Bitmap* glyph_bitmap = &slot->bitmap; // Flip the bitmap vertically - unsigned char* flipped_bitmap = (unsigned char*)malloc(glyph_bitmap->width * glyph_bitmap->rows); + unsigned char* flipped_bitmap = (unsigned char*)malloc( + glyph_bitmap->width * glyph_bitmap->rows); for (int row = 0; row < glyph_bitmap->rows; row++) { unsigned char* src_row = glyph_bitmap->buffer + (row * glyph_bitmap->width); - unsigned char* dest_row = flipped_bitmap + ((glyph_bitmap->rows - row - 1) * glyph_bitmap->width); + unsigned char* dest_row = flipped_bitmap + ((glyph_bitmap->rows - row - 1) * + glyph_bitmap->width); + memcpy(dest_row, src_row, glyph_bitmap->width); } @@ -63,7 +62,8 @@ int adjusted_y = y + (slot->bitmap_top - glyph_bitmap->rows); glRasterPos2f(x, adjusted_y); - glDrawPixels(glyph_bitmap->width, glyph_bitmap->rows, GL_LUMINANCE, GL_UNSIGNED_BYTE, glyph_bitmap->buffer); + glDrawPixels(glyph_bitmap->width, glyph_bitmap->rows, GL_LUMINANCE, + GL_UNSIGNED_BYTE, glyph_bitmap->buffer); x += slot->advance.x / 64; } @@ -76,7 +76,7 @@ glBegin(GL_QUADS); int x = 0; - for (int i = 0; i < algo_args.arr_size; i++) { + for (int i = 0; i < algo_args.arr_size - 1; i++) { if (algo_args.arr[i].current) { glColor3f(1.0, 1.0, 1.0); @@ -97,8 +97,6 @@ glVertex2f(x + rect_width, vpadding); x += rect_width + space; - - algo_args.arr[i].current = false; } glEnd(); @@ -120,6 +118,17 @@ sprintf(text, "Comparisons: %i", algo_args.comparisons); render_text(500, window_height - 80, text); + // Top: Column 3 + if (algo_args.pause && !algo_args.sequentially) { + sprintf(text, "PAUSED"); + render_text(window_width - 400, window_height - 50, text); + } + + if (algo_args.sequentially) { + sprintf(text, "SEQUENTIAL MODE"); + render_text(window_width - 400, window_height - 80, text); + } + // Bottom: Column 1 render_text(20, vpadding - 50, "Press a or s to select an algorithm."); render_text(20, vpadding - 80, "Press u or d to modify speed."); @@ -128,6 +137,7 @@ // Bottom: Column 2 render_text(800, vpadding - 50, "Press enter to run the algorithm."); render_text(800, vpadding - 80, "Press p to pause the algorithm."); + render_text(800, vpadding - 110, "Press q to enable or disable sequential mode."); glutSwapBuffers(); } @@ -142,39 +152,42 @@ // s: Next algorithm if (key == 115) { - + algorithm_selector(algos, algos_size, 1, &selected_algo); } // a: Previous algorithm if (key == 97) { - + algorithm_selector(algos, algos_size, -1, &selected_algo); } // r: Reset state if (key == 114) { - randomize_array(algo_args.arr, algo_args.arr_size); + reset_state(&algo_args, &thread_state); } // u: Increase speed if (key == 117) { - algo_args.delay += 10; + change_speed(&algo_args, 10); } // d: reduce speed if (key == 100) { - if (algo_args.delay > 10) { - algo_args.delay -= 10; - } + change_speed(&algo_args, -10); } // enter: Run program if (key == 13) { - pthread_create(&thread_id, NULL, algos[selected_algo].function, (void *)&algo_args); + run(&algo_args, algos, selected_algo, &thread_state); } // p: Pause program if (key == 112) { + algo_args.pause = true; + } + // q: Enable sequential mode + if (key == 113) { + algo_args.sequentially = !algo_args.sequentially; } } @@ -236,14 +249,20 @@ int main(int argc, char** argv) { + algo_args.arr_size = window_width / (rect_width + space); + algo_args.arr = malloc(algo_args.arr_size * sizeof(struct Element)); algo_args.comparisons = 0; + algo_args.pause = false; + algo_args.sequentially = false; algo_args.delay = 100; strcpy(algos[0].name, "Bubble sort"); algos[0].function = bubble_sort; + + strcpy(algos[1].name, "Selection sort"); + algos[1].function = selection_sort; - algo_args.arr_size = window_width / (rect_width + space); - algo_args.arr = malloc(algo_args.arr_size * sizeof(struct Element)); + algos_size = sizeof(algos) / sizeof(algos[0]); create_array(algo_args.arr, algo_args.arr_size, window_height, vpadding); randomize_array(algo_args.arr, algo_args.arr_size); diff -r dae463bbf5ca -r f945bcc3571f src/utils.c --- a/src/utils.c Wed Jun 28 20:10:55 2023 +0100 +++ b/src/utils.c Thu Jun 29 17:48:36 2023 +0100 @@ -30,32 +30,63 @@ } -bool array_sorted(struct Element *arr, int arr_size) { - for (int i = 0; i < arr_size - 1; i++) { - if (arr[i].value > arr[i + 1].value) { - return false; - } +void algorithm_selector(struct Algo *algos, int size, int direction, int *selected_algo) { + int selection = *selected_algo + direction; + + if (selection >= 0 && selection <= size - 1) { + *selected_algo = selection; } - - return true; } -void algorithm_selector(struct Algo *algos, int direction, int *selected_algorithm) { - int selection = *selected_algorithm + direction; - int lower = 0; - int upper = (int)((sizeof(algos) / sizeof(algos[0])) - 1); +void change_speed(struct AlgoArgs *algo_args, int change) { + int new_delay = algo_args->delay + change; - if (selection >= lower && selection <= upper) { - *selected_algorithm = selection; + if (new_delay) { + algo_args->delay = new_delay; } } -void delay_flow(useconds_t *delay, bool *pause) { +void control_flow(useconds_t delay, bool sequentially, bool *pause) { + if (sequentially) { + *pause = true; + } + while (*pause) { // Wait to resume } - - usleep(*delay); + + usleep(delay); } + + +void reset_state(struct AlgoArgs *algo_args, struct ThreadState *thread_state) { + if (thread_state->running) { + pthread_cancel(thread_state->thread); + } + + randomize_array(algo_args->arr, algo_args->arr_size); + + algo_args->comparisons = 0; + algo_args->pause = false; + algo_args->sequentially = false; + + for (int i = 0; i < algo_args->arr_size - 1; i++) { + algo_args->arr[i].current = false; + } +} + + +void run(struct AlgoArgs *algo_args, struct Algo *algos, int selected_algo, + struct ThreadState *thread_state) { + + if (algo_args->pause) { + algo_args->pause = false; + } else { + thread_state->running = true; + pthread_create(&(thread_state->thread), NULL, algos[selected_algo].function, + (void *)algo_args); + } +} + diff -r dae463bbf5ca -r f945bcc3571f src/utils.h --- a/src/utils.h Wed Jun 28 20:10:55 2023 +0100 +++ b/src/utils.h Thu Jun 29 17:48:36 2023 +0100 @@ -6,6 +6,11 @@ #include #include #include +#include +#include +#include +#include +#include FT_FREETYPE_H struct Element { @@ -18,12 +23,31 @@ void *(*function)(void *); }; +struct AlgoArgs { + struct Element *arr; + int arr_size; + int comparisons; + bool pause; + bool sequentially; + useconds_t delay; +}; + + +struct ThreadState { + bool running; + pthread_t thread; +}; + void create_array(struct Element *arr, int arr_size, int window_height, int vpadding); void swap_elements(int x, int y, struct Element *arr); void randomize_array(struct Element *arr, int arr_size); bool array_sorted(struct Element *arr, int arr_size); -void algorithm_selector(struct Algo *algos, int direction, int *selected_algorithm); -void delay_flow(useconds_t *delay, bool *pause); +void algorithm_selector(struct Algo *algos, int algos_size, int direction, int *selected_algo); +void change_speed(struct AlgoArgs *algo_args, int change); +void control_flow(useconds_t delay, bool sequentially, bool *pause); +void reset_state(struct AlgoArgs *algo_args, struct ThreadState *thread_state); +void run(struct AlgoArgs *algo_args, struct Algo *algos, int selected_algo, + struct ThreadState *thread_state); -#endif // UTILS_H +#endif // UTILS_H