commit 6ce6150900d7cd6a89b7bb6b595d7eccbad2f128
parent a8528d84a5c66bbc139ca637b9384878999d2e59
Author: klewer-martin <martin.cachari@gmail.com>
Date: Tue, 29 Mar 2022 01:03:06 -0300
Almost a rewrite of the entire main, next step is to separate into threads ?
Diffstat:
| M | Makefile | | | 4 | ++-- |
| M | drw.c | | | 42 | ++++++++++++++++++++++++++++++++++++++++++ |
| M | drw.h | | | 6 | ++++++ |
| M | sav.c | | | 243 | +++++++++++++++++++------------------------------------------------------------ |
| A | sdl_extra.c | | | 74 | ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | sdl_extra.h | | | 27 | +++++++++++++++++++++++++++ |
| M | sort.c | | | 86 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++---------------- |
| M | sort.h | | | 2 | +- |
8 files changed, 278 insertions(+), 206 deletions(-)
diff --git a/Makefile b/Makefile
@@ -1,7 +1,7 @@
CC := cc
CLIBS := `sdl2-config --libs --cflags`
-CFLAGS := -lSDL2_image -lm -Wall -pedantic -ansi -std=c99
-SRCS := sav.c util.c sort.c
+CFLAGS := -lSDL2_image -lm -Wall -pedantic -ansi -std=c99 -g
+SRCS := sav.c util.c sort.c drw.c sdl_extra.c
OBJS := $(SRCS:.c=.o)
TARGET := sav
diff --git a/drw.c b/drw.c
@@ -1 +1,43 @@
#include "drw.h"
+
+#define X_BORDER 40
+#define Y_BORDER 40
+#define RECT_WIDTH 5
+
+void drw_element(SDL_Renderer *rend, int x, int y, int h) {
+ SDL_Rect rect;
+
+ rect.x = x + X_BORDER; /* top left + x */
+ rect.y = y - Y_BORDER; /* top left + y, (y < 0) */
+ rect.w = RECT_WIDTH; /* fixed width */
+ rect.h = -h;
+
+ SDL_RenderDrawRect(rend, &rect);
+ SDL_SetRenderDrawColor(rend, 255, 0, 0, 0); /* RGBA */
+ SDL_RenderFillRect(rend, &rect);
+
+ SDL_SetRenderDrawColor(rend, 0, 0, 0, 0);
+ SDL_RenderDrawLine(rend, x + X_BORDER, y - Y_BORDER, x + X_BORDER, y - Y_BORDER - h);
+}
+
+void drw_element_color(SDL_Renderer *rend, int x, int y, int h, unsigned int col) {
+ SDL_Rect rect;
+ unsigned char r, g, b, a;
+
+ rect.x = x + X_BORDER; /* bottom left + x */
+ rect.y = y - Y_BORDER; /* bottom */
+ rect.w = RECT_WIDTH; /* fixed width */
+ rect.h = -h;
+
+ r = (char)(col >> 24) & 0xFF;
+ g = (char)(col >> 16) & 0xFF;
+ b = (char)(col >> 8) & 0xFF;
+ a = (char)(col) & 0xFF;
+
+ SDL_RenderDrawRect(rend, &rect);
+ SDL_SetRenderDrawColor(rend, r, g, b, a);
+ SDL_RenderFillRect(rend, &rect);
+
+ SDL_SetRenderDrawColor(rend, 0, 0, 0, 0);
+ SDL_RenderDrawLine(rend, x + X_BORDER, y - Y_BORDER, x + X_BORDER, y - Y_BORDER - h);
+}
diff --git a/drw.h b/drw.h
@@ -1,5 +1,11 @@
#ifndef __DRAW_H__
#define __DRAW_H__
+#include <SDL2/SDL.h>
+#include <SDL2/SDL_video.h>
+#include <SDL2/SDL_image.h>
+
+void drw_element(SDL_Renderer *rend, int x, int y, int h);
+void drw_element_color(SDL_Renderer *rend, int x, int y, int h, unsigned int col);
#endif // __DRAW_H__
diff --git a/sav.c b/sav.c
@@ -6,225 +6,96 @@
#include <SDL2/SDL_video.h>
#include <SDL2/SDL_image.h>
+#include <unistd.h>
+#include <pthread.h>
+
#include "drw.h"
#include "util.h"
-#include "sort.h"
-
-#define WINDOW_TITLE "Sorting Algorithms Visualized"
-#define WINDOW_WIDTH 0
-#define WINDOW_HEIGHT 0
+/* #include "sort.h" */
+#include "sdl_extra.h"
#define SEL_COLOR 0x00FF0000 // RGBA
#define CMP_COLOR 0x00FFFF00
-#define ANIM_SPEED 50
-#define SPEED_STEP 10
-
-#define ARR_LEN 100
+#define ARR_LEN 120
#define ARR_MAX 500
-#define X_BORDER 25
-#define Y_BORDER 25
#define RECT_WIDTH 5
-#define SPEED_MIN 5000
-#define SPEED_MAX 0
-
-SDL_Window *window;
-SDL_Renderer *renderer;
-
-int x, w, h, arr[ARR_LEN], speed;
-size_t sel, cmp, arr_max, x_border, y_border, g_w, g_h;
-int min_w, min_h;
-
-bool run = true;
-
-void setup(void) {
- SDL_Init(SDL_INIT_VIDEO);
-
- // Create an application window with the following settings:
- window = SDL_CreateWindow(
- WINDOW_TITLE, // window title
- SDL_WINDOWPOS_UNDEFINED, // initial x position
- SDL_WINDOWPOS_UNDEFINED, // initial y position
- WINDOW_WIDTH, // width, in pixels
- WINDOW_HEIGHT, // height, in pixels
- SDL_WINDOW_OPENGL // window flags
- );
-
- renderer = SDL_CreateRenderer(window, -1, SDL_RENDERER_ACCELERATED);
-
- if (!window) end("SDL: window cannot be created");
-
- SDL_SetRenderDrawColor(renderer, 32, 32, 32, 0);
- SDL_RenderClear(renderer);
- SDL_RenderPresent(renderer);
-}
-
-void cleanup(void) {
- SDL_DestroyRenderer(renderer);
- SDL_DestroyWindow(window);
- SDL_Quit();
-}
-
-void drw_element(size_t height) {
- SDL_Rect rect;
-
- rect.x = X_BORDER + x; /* bottom left + x */
- rect.y = h - Y_BORDER + 1; /* bottom */
- rect.w = RECT_WIDTH; /* fixed width */
- rect.h = -height;
-
- SDL_RenderDrawRect(renderer, &rect);
- SDL_SetRenderDrawColor(renderer, 255, 0, 0, 0); /* RGBA */
- SDL_RenderFillRect(renderer, &rect);
-
- SDL_SetRenderDrawColor(renderer, 0, 0, 0, 0);
- SDL_RenderDrawLine(renderer,
- x + X_BORDER,
- h - Y_BORDER,
- x + X_BORDER,
- h - Y_BORDER - height);
-
- x += RECT_WIDTH;
-}
+int arr[ARR_LEN];
+SDL_Renderer *rend;
+SDL_Window *win;
+size_t sel, cmp;
+status_t st;
-void drw_element_color(size_t height, unsigned int color) {
- SDL_Rect rect;
- unsigned char r, g, b, a;
+void update_array_graph(SDL_Renderer *rend, SDL_Window *win);
+void insertion_sort(int *arr, size_t len);
- rect.x = X_BORDER + x; /* bottom left + x */
- rect.y = h - Y_BORDER + 1; /* bottom */
- rect.w = RECT_WIDTH; /* fixed width */
- rect.h = -height;
+void update_array_graph(SDL_Renderer *rend, SDL_Window *win) {
+ int x, w, h;
- r = (char)(color >> 24) & 0xFF;
- g = (char)(color >> 16) & 0xFF;
- b = (char)(color >> 8) & 0xFF;
- a = (char)(color) & 0xFF;
+ SDL_GetWindowSize(win, &w, &h);
- SDL_RenderDrawRect(renderer, &rect);
- SDL_SetRenderDrawColor(renderer, r, g, b, a);
- SDL_RenderFillRect(renderer, &rect);
+ SDL_SetRenderDrawColor(rend, 29, 28, 28, 0);
+ SDL_RenderClear(rend);
- SDL_SetRenderDrawColor(renderer, 0, 0, 0, 0);
- SDL_RenderDrawLine(renderer,
- x + X_BORDER,
- h - Y_BORDER,
- x + X_BORDER,
- h - Y_BORDER - height);
-
- x += RECT_WIDTH;
-}
-
-void update_window_size(void) {
- SDL_GetWindowSize(window, &w, &h);
-
- g_w = (ARR_LEN * RECT_WIDTH);
- g_h = (ARR_MAX);
-
- x_border = X_BORDER;
- y_border = Y_BORDER;
-
- min_w = (g_w + (2 * x_border));
- min_h = (g_h + (2 * y_border));
-
- SDL_SetWindowMinimumSize(window, min_w, min_h);
- SDL_SetWindowMaximumSize(window, min_w, min_h);
-}
-
-void update_graph(void) {
- SDL_SetRenderDrawColor(renderer, 28, 28, 28, 0);
- SDL_RenderClear(renderer);
-
- SDL_GetWindowSize(window, &w, &h);
-
- /* reset 'x' in order to start drawing from the left */
size_t i;
- for(i = x = 0; i < ARR_LEN; i++) {
- if(i == sel) drw_element_color(arr[i], SEL_COLOR);
- else if(i == cmp) drw_element_color(arr[i], CMP_COLOR);
- else drw_element(arr[i]);
+ for(i = x = 0; i < ARR_LEN; i++, x += RECT_WIDTH) {
+ if(i == sel) drw_element_color(rend, x, h, arr[i], SEL_COLOR);
+ else if(i == cmp) drw_element_color(rend, x, h, arr[i], CMP_COLOR);
+ else drw_element(rend, x, h, arr[i]);
}
- SDL_RenderPresent(renderer);
+ SDL_RenderPresent(rend);
}
-void check_events(void) {
- SDL_Event event;
- while (SDL_PollEvent(&event)) {
- switch(event.type) {
- case SDL_QUIT: run = false; break;
- case SDL_KEYDOWN:
- switch(event.key.keysym.scancode) {
- case SDL_SCANCODE_EQUALS:
- if(speed > SPEED_MAX) speed -= SPEED_STEP;
- break;
- case SDL_SCANCODE_MINUS:
- if(speed < SPEED_MIN) speed += SPEED_STEP;
- break;
- default: break;
- }
- default: break;
+void insertion_sort(int *arr, size_t len) {
+ int key;
+ size_t i, j;
+
+ for(i = 1, st = RUN; i < len; i++) {
+ key = arr[i];
+ j = i - 1;
+ while((j >= 0) && (arr[j] > key)) {
+ arr[j + 1] = arr[j];
+ j = j - 1;
+ sel = i;
+ cmp = j;
+ update_array_graph(rend, win);
+ check_events(&st);
+ if(st == STOP) break;
}
+ arr[j + 1] = key;
+ sel = i;
+ cmp = j;
+ update_array_graph(rend, win);
+ check_events(&st);
+ if(st == STOP) break;
}
}
int main (void) {
- setup();
- size_t i, j;
- int key;
-
- speed = ANIM_SPEED;
+ size_t i, len;
- bool sorted = false;
+ len = ARR_LEN;
+ sel = cmp = 0;
- arr_max = ARR_MAX;
-
- update_window_size();
+ setup(&win, &rend);
/* create a random array */
srand((unsigned int)time(NULL));
- for(i = 0; i < ARR_LEN; i++)
- while(!(arr[i] = rand() % arr_max))
- arr[i] = (rand() % arr_max);
+ for(i = 0; i < len; i++)
+ while(!(arr[i] = rand() % ARR_MAX))
+ arr[i] = (rand() % ARR_MAX);
/* main loop */
- while(run) {
- check_events();
- /* sort the array while updating the graph */
- if(sorted == false) {
- for(i = 1; i < ARR_LEN; i++) {
- key = arr[i];
- j = i - 1;
- while((j >= 0) && (arr[j] > key)) {
- arr[j + 1] = arr[j];
- j = j - 1;
- sel = i;
- cmp = j;
- update_graph();
- SDL_Delay(speed);
- check_events();
- if(run == false) goto end_main_while;
- }
- arr[j + 1] = key;
- sel = i;
- cmp = j;
- check_events();
- if(run == false) goto end_main_while;
- update_graph();
- SDL_Delay(speed);
- }
- sel = cmp = i;
- update_graph();
- SDL_Delay(speed);
- sorted = true;
- }
- update_graph();
- SDL_Delay(speed);
+ st = RUN;
+ while(st != STOP) {
+ check_events(&st);
+ update_array_graph(rend, win);
+ insertion_sort(arr, len);
}
-end_main_while:
- cleanup();
+ cleanup(win, rend);
return 0;
}
diff --git a/sdl_extra.c b/sdl_extra.c
@@ -0,0 +1,74 @@
+#include "sdl_extra.h"
+#include "util.h"
+
+#define WINDOW_TITLE "SAV - Sorting Algorithms Visualized"
+
+#define ARR_LEN 120
+#define ARR_MAX 500
+
+#define X_BORDER 40
+#define Y_BORDER 40
+#define RECT_WIDTH 5
+#define TOP_BORDER 50
+
+void check_events(status_t *status) {
+ SDL_Event event;
+ while (SDL_PollEvent(&event)) {
+ switch(event.type) {
+ case SDL_QUIT: *status = STOP; break;
+ /* case SDL_KEYDOWN: */
+ /* switch(event.key.keysym.scancode) { */
+ /* case SDL_SCANCODE_EQUALS: */
+ /* if(speed > SPEED_MAX) speed -= SPEED_STEP; */
+ /* break; */
+ /* case SDL_SCANCODE_MINUS: */
+ /* if(speed < SPEED_MIN) speed += SPEED_STEP; */
+ /* break; */
+ /* case SDL_SCANCODE_P: */
+ /* if(status == PAUSE) *status = RUN; */
+ /* else *status = PAUSE; */
+ /* break; */
+ /* default: break; */
+ /* } */
+ default: break;
+ }
+ }
+}
+
+void setup(SDL_Window **win, SDL_Renderer **rend) {
+ int min_w, min_h;
+
+ SDL_Init(SDL_INIT_VIDEO);
+
+ *win = SDL_CreateWindow(
+ WINDOW_TITLE,
+ SDL_WINDOWPOS_UNDEFINED,
+ SDL_WINDOWPOS_UNDEFINED,
+ 0,
+ 0,
+ SDL_WINDOW_OPENGL
+ );
+
+ *rend = SDL_CreateRenderer(*win, -1, SDL_RENDERER_ACCELERATED | SDL_RENDERER_PRESENTVSYNC);
+
+ if (*win == NULL) end("SDL: window cannot be created");
+ else if (*rend == NULL) end("SDL: renderer cannot be created");
+
+ SDL_SetRenderDrawColor(*rend, 32, 32, 32, 0);
+ SDL_RenderClear(*rend);
+ SDL_RenderPresent(*rend);
+
+ /* compute the window minimum size */
+ min_w = ((ARR_LEN * RECT_WIDTH) + (2 * X_BORDER));
+ min_h = ((ARR_MAX) + (2 * Y_BORDER) + TOP_BORDER);
+
+ SDL_SetWindowMinimumSize(*win, min_w, min_h);
+ SDL_SetWindowMaximumSize(*win, min_w, min_h);
+}
+
+void cleanup(SDL_Window *win, SDL_Renderer *rend) {
+ SDL_DestroyRenderer(rend);
+ SDL_DestroyWindow(win);
+ SDL_Quit();
+}
+
diff --git a/sdl_extra.h b/sdl_extra.h
@@ -0,0 +1,27 @@
+#ifndef __SDL_EXTRA_H__
+#define __SDL_EXTRA_H__
+
+#include <stdbool.h>
+#include <SDL2/SDL.h>
+#include <SDL2/SDL_video.h>
+#include <SDL2/SDL_image.h>
+
+/* typedef struct { */
+/* status_t status; */
+/* int speed; */
+/* size_t sel, cmp, swap; */
+/* void (*sort)(int *arr, size_t len); */
+/* } Sav; */
+
+typedef enum {
+ RUN,
+ PAUSE,
+ STOP
+} status_t;
+
+void check_events(status_t *status);
+void setup(SDL_Window **win, SDL_Renderer **rend);
+void cleanup(SDL_Window *win, SDL_Renderer *rend);
+
+#endif
+
diff --git a/sort.c b/sort.c
@@ -1,8 +1,15 @@
#include <stdio.h>
+#include <stdbool.h>
#include "sort.h"
#include "util.h"
+typedef enum {
+ RUN,
+ PAUSE,
+ STOP
+} status_t;
+
int bubble_sort(int *arr, size_t len) {
if(arr == NULL) return 1;
@@ -31,25 +38,70 @@ int bubble_sort(int *arr, size_t len) {
return 1;
}
-int insertion_sort(int *arr, size_t len) {
- static size_t i = 1;
- int j;
+/* int insertion_sort(int *arr, size_t len) { */
+/* static size_t i = 1; */
+/* int j; */
- int key;
+/* int key; */
- if(i < len) {
- key = arr[i];
- j = i - 1;
+/* if(i < len) { */
+/* key = arr[i]; */
+/* j = i - 1; */
- while((j >= 0) && (arr[j] > key)) {
- arr[j + 1] = arr[j];
- j = j - 1;
- }
+/* while((j >= 0) && (arr[j] > key)) { */
+/* arr[j + 1] = arr[j]; */
+/* j = j - 1; */
+/* } */
- arr[j + 1] = key;
- i++;
- return 1;
- }
+/* arr[j + 1] = key; */
+/* i++; */
+/* return 1; */
+/* } */
+
+/* return 0; */
+/* } */
+
+/* void insertion_sort(int *arr, size_t len) { */
+ /* int key; */
+ /* size_t i, j; */
+
+ /* extern status_t status; */
+ /* extern size_t sel, cmp; */
+ /* bool sorted = false; */
+ /* extern bool update; */
+
+ /* /1* if((sorted == false) && (status == RUN)) { *1/ */
+ /* while((status == RUN) && (sorted != true)) { */
+ /* if(status != PAUSE) { */
+ /* for(i = 1; i < len; i++) { */
+ /* key = arr[i]; */
+ /* j = i - 1; */
+ /* while((j >= 0) && (arr[j] > key)) { */
+ /* arr[j + 1] = arr[j]; */
+ /* j = j - 1; */
+ /* sel = i; */
+ /* cmp = j; */
+ /* /1* update_array_graph(rend, win); *1/ */
+ /* /1* SDL_Delay(speed); *1/ */
+ /* /1* if(status == PAUSED) goto end_sort; *1/ */
+ /* } */
+ /* arr[j + 1] = key; */
+ /* sel = i; */
+ /* cmp = j; */
+ /* /1* if(status == PAUSED) goto end_sort; *1/ */
+ /* /1* update_array_graph(rend, win); *1/ */
+ /* /1* SDL_Delay(speed); *1/ */
+ /* } */
+ /* sel = cmp = i; */
+ /* update = true; */
+ /* /1* goto end_sort; *1/ */
+ /* /1* update_array_graph(rend, win); *1/ */
+ /* /1* SDL_Delay(speed); *1/ */
+ /* /1* sorted = true; *1/ */
+ /* } */
+ /* } */
+ /* update_array_graph(rend, win); */
+ /* SDL_Delay(speed); */
+ /* return 0; */
+/* } */
- return 0;
-}
diff --git a/sort.h b/sort.h
@@ -2,6 +2,6 @@
#define __SORT_H__
int bubble_sort(int *arr, size_t len);
-int insertion_sort(int *arr, size_t len);
+void insertion_sort(int *arr, size_t len);
#endif // __SORT_H__
