#include <stdlib.h>
#include <string.h>

/*
** Définition des notions d'image et de pixel ; tout ceci peut être remplacé
** en fonction de la plate-forme cible (que je ne connais pas), la seule
** contrainte est de disposer de fonctions "GetPixel" et "SetPixel"
** quelconques sur une image.
*/

typedef struct
{
	unsigned char	r;
	unsigned char	g;
	unsigned char	b;
} Color;

typedef struct
{
	unsigned int	width;
	unsigned int	height;
	Color*			pixels;
} Image;

void	imageGet (Image* image, unsigned int x, unsigned y, Color** color)
{
	*color = &image->pixels[x + image->width * y];
}

void	imageSet (Image* image, unsigned int x, unsigned y, Color* color)
{
	Color*	pixel = &image->pixels[x + image->width * y];

	pixel->r = color->r;
	pixel->g = color->g;
	pixel->b = color->b;
}

/*
** Définition d'une pile de coordonnées et des opérations habituelles dessus,
** pour remplacer la récursivité.
*/

typedef struct
{
	unsigned int	x;
	unsigned int	y;
} Location;

typedef struct
{
	unsigned int	capacity;
	unsigned int	count;
	Location*		items;
} Stack;

void	stackCreate (Stack* stack)
{
	stack->capacity = 0;
	stack->count = 0;
	stack->items = NULL;
}

void	stackDelete (Stack* stack)
{
	if (stack->items)
		free (stack->items);
}

int	stackPop (Stack* stack, unsigned int* x, unsigned int* y)
{
	Location*	top;

	if (stack->count < 1)
		return 0;

	top = &stack->items[--stack->count];
	*x = top->x;
	*y = top->y;

	return 1;
}

int	stackPush (Stack* stack, unsigned int x, unsigned int y)
{
	unsigned int	capacity;
	Location*		items;
	Location*		top;

	if (stack->count >= stack->capacity)
	{
		capacity = stack->capacity * 2 + 1;
		items = realloc (stack->items, capacity * sizeof (*stack->items));

		if (!items)
			return 0;

		stack->capacity = capacity;
		stack->items = items;
	}

	top = &stack->items[stack->count++];
	top->x = x;
	top->y = y;

	return 1;
}

/*
** Le remplissage en lui-même.
** image:	image source (à adapter à la plate-forme, cf. plus haut)
** x:		coordonnée X de départ du remplissage
** y:		coordonnée Y de départ du remplissage
** color:	couleur de remplissage (à adapter également)
*/

void floodFill (Image* image, unsigned int x, unsigned int y, Color* color)
{
	Color*	pixel;
	Stack	stack;

	stackCreate (&stack);
	stackPush (&stack, x, y);

	while (stack.count > 0)
	{
		stackPop (&stack, &x, &y);
		imageGet (image, x, y, &pixel); // à remplacer par GetPixel

		if (color->r != pixel->r || color->g != pixel->g || color->b != pixel->b)
		{
			if (x > 0)
				stackPush (&stack, x - 1, y);

			if (x + 1 < image->width)
				stackPush (&stack, x + 1, y);

			if (y > 0)
				stackPush (&stack, x, y - 1);

			if (y + 1 < image->height)
				stackPush (&stack, x, y + 1);

			imageSet (image, x, y, color); // à remplacer par SetPixel
		}
	}

	stackDelete (&stack);
}