/*
sort_stack Copyright (C) 2026 yctct

This program is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation, either version 3 of the License, or
(at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program.  If not, see <https://www.gnu.org/licenses/>.
*/


#include "../include/push_swap.h"

int	greatest_smallest_value(int element, t_list *stack)
{
	int	saved;

	saved = (ft_lstmin(stack))->value;
	while (stack)
	{
		if (stack->value <= element && stack->value > saved)
			saved = stack->value;
		stack = stack->next;
	}
	return (saved);
}

int	find_position_stack(int element, t_list *stack)
{
	int	position;

	position = ft_lstmax(stack)->index;
	while (stack)
	{
		if (element >= stack->value
			&& stack->value >= greatest_smallest_value(element, stack))
		{
			position = stack->index;
			return (position);
		}
		stack = stack->next;
	}
	return (position);
}

int	find_cheapest_element(t_list *src, t_list *dst)
{
	int	index;
	int	cost;
	int	node_cost;

	cost = 0;
	index = src->index;
	while (src)
	{
		node_cost = src->index;
		node_cost += find_position_stack(src->value, dst);
		if (!cost)
			cost = node_cost;
		else if (cost && (node_cost < cost))
		{
			cost = node_cost;
			index = src->index;
		}
		src = src->next;
	}
	return (index);
}

void	push_and_sort(t_list **src, t_list **dst)
{
	int		position_a;
	int		position_b;
	t_list	*cheapst_element;

	while (*src)
	{
		position_a = find_cheapest_element(*src, *dst);
		cheapst_element = *src;
		while (cheapst_element->index < position_a)
			cheapst_element = cheapst_element->next;
		position_b = find_position_stack(cheapst_element->value, *dst);
		rotate_stacks(position_a, position_b, src, dst);
		pb(src, dst);
	}
}

void	sort(t_list **src)
{
	t_list	*dst;

	dst = NULL;
	pb(src, &dst);
	pb(src, &dst);
	push_and_sort(src, &dst);
	while (dst)
		pa(&dst, src);
	if ((ft_lstmin(*src))->index < (ft_lstsize(*src) / 2))
	{
		while ((*src)->value != ft_lstmin(*src)->value)
			ra(src);
	}
	else
	{
		while ((*src)->value != ft_lstmin(*src)->value)
			rra(src);
	}
}