push_swap/chunks.c at main · LuisPM24/push_swap · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
/* ************************************************************************** */
/*                                                                            */
/*                                                        :::      ::::::::   */
/*   chunks.c                                           :+:      :+:    :+:   */
/*                                                    +:+ +:+         +:+     */
/*   By: scamlett <scamlett@student.42malaga.com    +#+  +:+       +#+        */
/*                                                +#+#+#+#+#+   +#+           */
/*   Created: 2026/05/15 09:19:45 by lupalomi          #+#    #+#             */
/*   Updated: 2026/05/24 19:37:50 by scamlett         ###   ########.fr       */
/*                                                                            */
/* ************************************************************************** */

#include "push_swap.h"

// Determines the size of each chunk based on the total number of elements.
static int	get_chunk_range(int total)
{
	int	range;

	range = ft_sqrt(total) * 15 / 10;
	if (range < 2)
		range = 2;
	return (range);
}

// Finds the position of the best candidate to push to stack B
static int	find_best_friend(t_stack *stack, unsigned int pushed, int range)
{
	t_node	*aux;
	int		position;
	int		first;
	int		last;

	aux = stack->head;
	position = 0;
	first = -1;
	last = -1;
	while (aux)
	{
		if (aux->index <= pushed + range)
		{
			if (first == -1)
				first = position;
			last = position;
		}
		aux = aux->next;
		position++;
	}
	if (first == -1)
		return (-1);
	if (first <= (int)stack->size - (int)last)
		return (first);
	return (last);
}

// Moves the element at the given position to the head of the stack
static void	move_position_to_head(t_stack *stack, unsigned int position)
{
	if (position <= stack->size / 2)
	{
		while (position > 0)
		{
			ra(stack);
			position--;
		}
	}
	else
	{
		while (position < stack->size)
		{
			rra(stack);
			position++;
		}
	}
}

// Pushes elements from stack A to stack B in chunks
void	push_chunks_to_b(t_stack *stack_a, t_stack *stack_b)
{
	int	position;
	int	range;
	int	pushed;
	int	index;

	range = get_chunk_range(stack_a->total_nbr);
	pushed = 0;
	while (stack_a->size > 0)
	{
		position = find_best_friend(stack_a, pushed, range);
		if (position != -1)
			move_position_to_head(stack_a, position);
		index = stack_a->head->index;
		pb(stack_a, stack_b);
		if (stack_b->head && index <= pushed)
			rb(stack_b);
		pushed++;
	}
}

// Pushes elements back from stack B to stack A in sorted order
void	chunks(t_stack *stack_a, t_stack *stack_b)
{
	if (!stack_a || stack_a->size < 2)
		return ;
	assign_chunks_indexes(stack_a);
	push_chunks_to_b(stack_a, stack_b);
	push_chunks_to_a(stack_a, stack_b);
}