#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <raylib.h>


#define BASE_ALLOC_SIZE 64
 
/*
 *  Recording
 */

struct replay
{
	int* swaps;
	int  swap_len;
	int  swap_capacity;
	
	int *array;
	int n;

	int position;
};

// global data

struct {
	float lag; 
	float elapsed;
	int playing;
} state;


void init_replay(struct replay *r, int elements, int array[elements])
{
	r->swaps         = malloc(BASE_ALLOC_SIZE * sizeof(int));
	r->swap_len      = 0;
	r->swap_capacity = BASE_ALLOC_SIZE;

	r->array = malloc(elements * sizeof(int));
	r->n     = elements;
	memcpy(r->array, array, elements * sizeof(int));

	r->position = 0;
}

void swap_values(int *a, int *b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

void record_swap(struct replay *r, int i, int j)
{
	if (r->swap_capacity == r->swap_len)
	{
		r->swap_capacity *= 2;
		r->swaps = realloc(r->swaps, r->swap_capacity * sizeof(int));	
	}
	r->swaps[r->swap_len]      = i;
	r->swaps[r->swap_len + 1]  = j;
	r->swap_len               += 2;
}

void in_sort_swap(int *array, int i, int j, struct replay *r)
{
	if (i == j)
	{
		return;
	}
	record_swap(r, i, j);
	swap_values(array + i, array + j);
}



/*
 *   replaying
 */

int swap_at_position(struct replay *r)
{
	int i = r->swaps[r->position];
	int j = r->swaps[r->position + 1];
	swap_values(r->array + i, r->array + j);	
}

int step_forward(struct replay *r)
{
	if (r->position == r->swap_len)
	{
		return 0;
	}
	swap_at_position(r);
	r->position += 2;
	return 1;
}

int step_backward(struct replay *r)
{
	if (r->position == 0)
	{
		return 0;
	}
	r->position -= 2;
	swap_at_position(r);
	return 1;
}


/*
 * sorting etc.
 */

void array_shuffle(int n, int array[n])
{
	for(int i = 0; i < n-1; i += 1)
	{
		int j = i + rand() / (RAND_MAX / (n - i) + 1);
		swap_values(array + i, array + j);
	}
}

void randomize_array(int n, int array[n])
{
	for(int i = 0; i < n; i += 1)
	{
		array[i] = i + 1;
	}
	array_shuffle(n, array);	
}


void r_coctail_sort(int n, int array[n], struct replay *rpl)
{  
	int l = 0;
	int r = n - 1;
 
	while (1)
	{
		int should_quit = 1;
 
		for (int i = l; i < r; i += 1)
		{
			if (array[i] > array[i + 1])
			{
				in_sort_swap(array, i, i + 1, rpl);
				should_quit = 0;
			}
		}
		if (should_quit)
		{
			break;
		}
 
		should_quit = 1;
		r -= 1;
       
		for (int i = r - 1; i >= l; i -= 1)
		{
			if (array[i] > array[i + 1])
			{
				in_sort_swap(array, i, i + 1, rpl);
				should_quit = 0;
			}
		}
		if (should_quit)
		{
			break;
		}
		l += 1;
	}
}

struct replay coctail_sort(int n, int array[n])
{
	struct replay ret;
	init_replay(&ret, n, array);
	r_coctail_sort(n, array, &ret);
	return ret;	
}

int r_partition(int *array, int l, int r, struct replay *rpl)
{
	int pivot = array[r];
	int i = l;

	for (int j = l; j < r; j += 1)
	{
		if (array[j] <= pivot)
		{
			in_sort_swap(array, i, j, rpl);
			i += 1;
		}
	}
	in_sort_swap(array, i, r, rpl);
	return i;
}

void r_quicksort(int *array, int l, int r, struct replay *rpl)
{
	if (l > r)
	{
		return;
	}
	int s = r_partition(array, l, r, rpl);
	r_quicksort(array, l, s - 1, rpl);
	r_quicksort(array, s + 1, r, rpl);
}

struct replay quicksort(int n, int array[n])
{
	struct replay ret;
	init_replay(&ret, n, array);
	r_quicksort(array, 0, n - 1, &ret);
	return ret;
}


/*
 *   drawing
 */
	

int was_last_swapped(struct replay rpl, int i)
{	
	return (rpl.position > 1) &&
		(i == rpl.swaps[rpl.position - 1] || i == rpl.swaps[rpl.position - 2]);
}

int will_be_swapped(struct replay rpl, int i)
{
	return (rpl.position < rpl.swap_len) &&
		(i == rpl.swaps[rpl.position] || i == rpl.swaps[rpl.position + 1]);
}


void draw_replay(Rectangle rect, struct replay rpl)
{
	const float skip = 3.0f;
	
	float bar_width  = (rect.width - ((rpl.n - 1) * skip)) / rpl.n;
	float px_per_unit  = rect.height / rpl.n;
	
	for (int i = 0; i < rpl.n; i += 1)
	{
		float h = rpl.array[i] * px_per_unit;
		Rectangle rec = {
			.x = rect.x + i * (bar_width + skip),
			.y = rect.y + rect.height - h,
			.width = bar_width,
			.height = h
		};

		Color color = BEIGE;
		if ( (state.elapsed > state.lag / 2 && was_last_swapped(rpl, i)) ||
		     (state.elapsed < state.lag / 2 && will_be_swapped(rpl, i)))
		{
			color = BROWN;
		}
		
		DrawRectangleRec(rec, color);
		DrawRectangleLinesEx(rec, 1, DARKBROWN);
	}	
	
}



int main()
{
	state.lag = 0.5f;
	state.elapsed = 0.0f;
	state.playing = 1;
	
	srand(time(0));
	int screen_width = 800;
	int screen_height = 450;
	int array_size = 32;
	
	Rectangle replay_rec = {
		.x = 10.0f,
		.y = 10.0f,
		.width = screen_width - 20.f,
		.height = screen_height - 20.f,		
	};
	
	int *a = malloc(array_size * sizeof(*a));
	randomize_array(array_size, a);	
	//struct replay rpl = coctail_sort(array_size, a);
	struct replay rpl = quicksort(array_size, a);
	
	InitWindow(screen_width, screen_height, "Sort visualization");
	SetTargetFPS(60);
	
	while (!WindowShouldClose())
	{
		
		/*
		 *  Input handling:
		 *  pause/play:   P
		 *  restart:      R
		 *  speed:        UP, DOWN
		 */

		if (IsKeyPressed(KEY_P))
		{
			state.playing = !state.playing;
		}

		if (IsKeyPressed(KEY_R))
		{
			while(step_backward(&rpl));
		}

		if (IsKeyPressed(KEY_UP))
		{
			if (state.lag > 0.1)
			{
				state.lag -= 0.1;
			}
		}

		if (IsKeyPressed(KEY_DOWN))
		{
			if (state.lag < 1)
			{
				state.lag += 0.1;
			}
		}

		
		/* update */
		if (state.playing) {
			state.elapsed -= GetFrameTime();
			if (state.elapsed <= 0)
			{
				if (!step_forward(&rpl))
				{
					state.playing = 0;
				}
				state.elapsed += state.lag;
			}
		}

		/* draw  */
		BeginDrawing();
		ClearBackground(RAYWHITE);

		draw_replay(replay_rec, rpl);
				
		EndDrawing();	
	}

	CloseWindow();
	
	return 0;
}