/* ************************************************************************** */
/*                                                                            */
/*                                                        :::      ::::::::   */
/*   sort.c                                             :+:      :+:    :+:   */
/*                                                    +:+ +:+         +:+     */
/*   By: cacharle <marvin@42.fr>                    +#+  +:+       +#+        */
/*                                                +#+#+#+#+#+   +#+           */
/*   Created: 2020/01/19 09:12:02 by cacharle          #+#    #+#             */
/*   Updated: 2021/09/11 13:41:33 by charles          ###   ########.fr       */
/*                                                                            */
/* ************************************************************************** */

#include "push_swap.h"

static int	frame_length(t_stack *st, int frame_index)
{
	return (stack_length(st) - frame_index);
}

static int	stack_cmp(t_stack *stack, int x, int y)
{
	if (stack->tag == STACK_A)
		return (x < y);
	else
		return (x > y);
}

/*
** stack is in reverse order compared to expected_orders
*/

int has_order(t_stack *stack, int *expected_orders, int expected_orders_len)
{
	int i;
	int j;
	int count = 0;

	i = -1;
	while (++i < expected_orders_len)
	{
		count = 0;
		j = -1;
		while (++j < stack_length(stack))
		{
			if (stack_cmp(stack, stack->elements[j], stack->elements[expected_orders_len - 1 - i]))
				count++;
		}
		if (count != expected_orders[i])
			return (false);
	}
	return (true);
}

static void	push_swap_sort3(t_stack *main)
{
	/* 1 2 0 rra */
	if (has_order(main, (int[]){1, 2, 0}, 3))
		stack_reverse_rotate_print(main);

	/* 2 0 1 ra */
	else if (has_order(main, (int[]){2, 0, 1}, 3))
		stack_rotate_print(main);

	/* 2 1 0 ra sa */
	else if (has_order(main, (int[]){2, 1, 0}, 3))
	{
		stack_rotate_print(main);
		stack_swap_print(main);
	}

	/* 1 0 2 sa */
	else if (has_order(main, (int[]){1, 0, 2}, 3))
		stack_swap_print(main);

	/* 0 2 1 sa ra */
	else if (has_order(main, (int[]){0, 2, 1}, 3))
	{
		stack_swap_print(main);
		stack_rotate_print(main);
	}
}



/*
** main       : stack to sort
** tmp        : temporary stack used to store pivot > values
** main_frame : main current sorting frame index
**              (ignore values beyond a certain index,
**               which bellong to previous recursions)
**
** store pivot value
** hide it at the bottom of the stack
** iterate over the current frame
** if < pivot, push it to tmp stack
** else, hide it with the pivot
** put all hidden elements on the top of the stack
** these form the new frame
**
** we have splitted the elements of the frame in upper and lower partition
** each of those will be sorted in the next recursion
*/

static void	push_swap_qsort_partition(t_stack *main, t_stack *tmp,
										int main_frame)
{
	int	pivot;
	int	hidden_count;
	int	frame_len;

	pivot = stack_peek(main);
	stack_rotate_print(main);
	hidden_count = 1;
	frame_len = frame_length(main, main_frame) - 1;
	while (frame_len > 0)
	{
		if (stack_cmp(main, stack_peek(main) , pivot))
			stack_push_to_print(main, tmp);
		else
		{
			stack_rotate_print(main);
			hidden_count++;
		}
		frame_len--;
	}
	if (stack_peek(main) == pivot)
		return ;
	while (hidden_count-- > 0)
		stack_reverse_rotate_print(main);
}

static bool stack_frame_sorted(t_stack *stack, int frame_len)
{
	int i;

	i = 0;
	while (i < frame_len - 1)
	{
		if (stack_cmp(stack, stack->elements[stack->top - 1 - i], stack->elements[stack->top - i]))
			return false;
		i++;
	}
	return true;
}

/*
** main       : final stack where all sorted values will be stored
** tmp        : temporary stack use to during partitionning
** main_frame : main stack sorting frame
** tmp_frame  : tmp stack sorting frame
**
** base condition : the current main frame contain 0 or 1 element
** sort current partition and get new main frame
** according to the new frame:
**     sort the new partition
**     sort the tmp stack
** push all elements of tmp on main
*/

static void	push_swap_qsort_rec(t_stack *main, t_stack *tmp,
								int main_frame, int tmp_frame)
{
	int	tmp_frame_len;

	/* printf("f: %d\n", main_frame); */
	if (frame_length(main, main_frame) < 2)
		return ;
	if (stack_frame_sorted(main, frame_length(main, main_frame)))
		return ;
	if (stack_length(main) == 4)
	{
		stack_push_to_print(main, tmp);
		push_swap_sort3(main);
		stack_push_to_print(tmp, main);

	}

	/* 3 2 4 1 sa */
	/* 2 3 4 1 sort3 */
	/* 2 1 3 4 sa */
	/* 1 2 3 4 */

	if (stack_length(main) == 3)
		return push_swap_sort3(main);
	if (frame_length(main, main_frame) == 2)
	{
		if (stack_cmp(main, main->elements[main->top - 1], main->elements[main->top]))
			stack_swap_print(main);
		return ;
	}
	push_swap_qsort_partition(main, tmp, main_frame);
	push_swap_qsort_rec(tmp, main, tmp_frame, stack_length(main));
	stack_push_to_print(main, tmp);
	push_swap_qsort_rec(main, tmp, main_frame, stack_length(tmp));
	stack_push_to_print(tmp, main);
	tmp_frame_len = frame_length(tmp, tmp_frame);
	while (tmp_frame_len-- > 0)
		stack_push_to_print(tmp, main);
}

/*
** wrapper for push_swap_qsort_rec
*/

void	push_swap_qsort(t_stack *a, t_stack *b)
{
	push_swap_qsort_rec(a, b, 0, 0);
}