#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);
}