42_old_fillit/search_map.c

/* ************************************************************************** */
/*                                                                            */
/*                                                        :::      ::::::::   */
/*   search_map.c                                       :+:      :+:    :+:   */
/*                                                    +:+ +:+         +:+     */
/*   By: hulamy <hulamy@student.42.fr>              +#+  +:+       +#+        */
/*                                                +#+#+#+#+#+   +#+           */
/*   Created: 2019/04/27 20:47:22 by hulamy            #+#    #+#             */
/*   Updated: 2019/05/17 15:55:04 by hulamy           ###   ########.fr       */
/*                                                                            */
/* ************************************************************************** */

#include "fillit.h"

/*
** function that look if a tretri fit in a place
*/

unsigned int	fit_in_place(unsigned int *map, t_fillist *list, int size)
{
	unsigned int	tmp;
	unsigned int	mask;
	int				i;
	int				n;
	int				r;

	n = list->int_number;
	r = list->pos_in_int;
	unsigned int	tetri;
	i = list->height;
	tetri = list->tetribit << 16 >> list->width;
	tmp = 0;
	mask = ~0u << (32 - list->width);
	while (i--)
	{
		if (tmp & tetri)
			return (0);
		if (r >= 32 && ++n)
			r -= 32;
		tmp = (mask & (map[n] << r)) | (mask & (map[n + 1] >> (32 - r)));
		tetri <<= list->width;
		r += size;
	}
	return (!(tmp & tetri));
}

/*
** function that add or remove a tetri on the map
*/

void	add_remove(unsigned int *map, t_fillist *list, int size)
{
	unsigned int	mask;
	unsigned short	tetri;
	int				i;
	int				j;

	tetri = list->tetribit;
	mask = ~0u << (32 - list->width);
	i = (list->height - 1) * list->width;
	j = (list->height - 1) * size + list->position;
	// change les bits du tetri sur la map a la position donnee
	while (j >= list->position)
	{
		map[(j - 1) / 32] ^= (mask & tetri << (16 + i)) >> (j - 1);
		map[(j - 1) / 32 + 1] ^= (mask & tetri << (16 + i)) << (32 - j) << 1;
		j -= size;
		i -= list->width;
	}
}

/*
** function that look for the first place in the map for a tetri
*/

int		find_place(unsigned int *tab, t_fillist *list, int size)
{
	t_fillist	tmp;


	tmp = *list;
	while (list->position < list->limit)
	{
		if (list->pos_in_int >= 32 && ++list->int_number)
			list->pos_in_int -= 32;
		if (list->posx > size - list->width && (list->posx = -1))
		{
			list->position += list->width - 2;
			list->pos_in_int += list->width - 2;
		}
		else if (fit_in_place(tab, list, size))
		{
			list->pos_in_int++;
			list->position++;
			list->posx++;
			return (1);
		}
		list->position++;
		list->posx++;
		list->pos_in_int++;
	}
	list = &tmp;
	return (0);
}

/*
** function that recursively try to fill the map with the tetris
*/

int		fill_map(unsigned int *map, t_fillist *list, int size, t_fillist *link)	// DEBUG link sert uniquement pour afficher le debug
{
	if (!list)
		return (1);
	list->position = 0;
	list->int_number = 0;
	list->pos_in_int = 0;
	list->posx = 0;
	while (find_place(map, list, size))
	{
		add_remove(map, list, size);
		if (fill_map(map, list->next, size, link))
			return (1);
		add_remove(map, list, size);
	}
	return (0);
}

/*
** function that init the map to the right size fill with int equal to zeros
*/

unsigned int	*init_map(int i)
{
	unsigned int	*new;
	int				size;

	size = (i * i) / 32 + 1;
	new = (unsigned int *)malloc(sizeof(*new) * size);
	while (size)
		new[size--] = 0;
	return (new);
}

/*
** function that init the list with the new values for each map size
*/

void	init_list(t_fillist *list, int size)
{
	t_fillist		*tmp;

	tmp = list;
	while (tmp)
	{
		list->posx = 0;
		list->int_number = 0;
		list->pos_in_int = 0;
		list->test = 0;	// DEBUG pour que print_final_map puisse imprimer correctement au fur et a mesure
		tmp->limit = (size - tmp->height + 1) * size;
		tmp = tmp->next;
	}
}

/*
** function that send to "fill_map" a map of a certain size and increment its size untill it's solved
*/

void	search_map(t_fillist *list)
{
	t_fillist		*tmp;
	unsigned int	*map;
	int				size;
	int				num;

	size = 2;
	num = 1;
	tmp = list;
	while ((tmp = tmp->next))		// trouve le nombre de tetri en parcourant la liste chainee
		num++;
	while (size * size < num * 4)	// trouve la taille minimale de la map
		size++;

	//////////////////////////////////////// TEST
	unsigned int	print;
	tmp = list;
	while (tmp)
	{
		// imression pour tests
		print = tmp->tetribit;
		print <<= 16;
		print_map(&print, tmp->width, tmp->height, tmp->letter);		// test, imprime le tetri
		ft_putchar('\n');
		tmp = tmp->next;
	}
	//////////////////////////////////////// TEST

	map = init_map(size);
	init_list(list, size);
	while (!fill_map(map, list, size, list))
	{
		map = init_map(size++);
		init_list(list, size);
	}
	print_final_map(list, size);		// DEBUG
	print_map(map, size, size, '#');	// DEBUG
}