Mercurial > public > algo-animator

changeset 30:f945bcc3571f

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
refactor
author Dennis C. M. <dennis@denniscm.com>
date Thu, 29 Jun 2023 17:48:36 +0100
parents dae463bbf5ca
children 61104b22a25d
files src/algorithms.c src/algorithms.h src/main.c src/utils.c src/utils.h
diffstat 5 files changed, 167 insertions(+), 69 deletions(-) [+]
line wrap: on
line diff
--- 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 */
+
+
--- 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
--- 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 <GL/glut.h>
-#include <pthread.h>
-#include <ft2build.h>
-#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);
--- 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);
+	}
+}
+
--- 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 <time.h>
 #include <stdbool.h>
 #include <unistd.h>
+#include <GL/glut.h>
+#include <pthread.h>
+#include <ft2build.h>
+#include <signal.h>
+#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