#include <sdl/sdl.h>
#include <assert.h>

typedef struct
{
    int x, y;
} Pos;

typedef struct node
{
    Pos p;
    struct node *p_nxt;
} Node;

Uint32 getpixel( SDL_Surface *surface, int x, int y )
{
    int bpp = surface->format->BytesPerPixel;
    /* Here p is the address to the pixel we want to retrieve */
    Uint8 *p = ( Uint8 * )surface->pixels + y * surface->pitch + x * bpp;

    switch ( bpp ) {
        case 1:
            return *p;

        case 2:
            return *( Uint16 * )p;

        case 3:
            if ( SDL_BYTEORDER == SDL_BIG_ENDIAN )
                return p[0] << 16 | p[1] << 8 | p[2];
            else
                return p[0] | p[1] << 8 | p[2] << 16;

        case 4:
            return *( Uint32 * )p;

        default:
            return 0;
    }
}

void putpixel( SDL_Surface *surface, int x, int y, Uint32 pixel )
{
    int bpp = surface->format->BytesPerPixel;
    /* Here p is the address to the pixel we want to set */
    Uint8 *p = ( Uint8 * )surface->pixels + y * surface->pitch + x * bpp;

    switch ( bpp ) {
        case 1:
            *p = pixel;
            break;

        case 2:
            *( Uint16 * )p = pixel;
            break;

        case 3:
            if ( SDL_BYTEORDER == SDL_BIG_ENDIAN ) {
                p[0] = ( pixel >> 16 ) & 0xff;
                p[1] = ( pixel >> 8 ) & 0xff;
                p[2] = pixel & 0xff;
            }
            else {
                p[0] = pixel & 0xff;
                p[1] = ( pixel >> 8 ) & 0xff;
                p[2] = ( pixel >> 16 ) & 0xff;
            }
            break;

        case 4:
            *( Uint32 * )p = pixel;
            break;

        default:
            break;           /* shouldn't happen, but avoids warnings */
    }
}

void push( Node **this, Pos p )
{
    Node *p_new = malloc( sizeof * p_new );
    if( p_new == NULL )
    {
        fprintf( stderr, "Not enough memory." );
        exit( EXIT_FAILURE );
    }
    p_new->p = p;
    p_new->p_nxt = *this;
    *this = p_new;
}


Pos pop( Node **this )
{
    Pos p = { -1, -1};
    if( *this != NULL )
    {
        Node *p_tmp = ( *this )->p_nxt;
        p = ( *this )->p;
        free( *this ), *this = NULL;
        *this = p_tmp;
    }
    return p;
}


#define N_DIR   4
static void fill( SDL_Surface *s, Sint16 x, Sint16 y, Uint32 dstclr )
{
    static Pos dir[N_DIR] = {{ -1, 0}, {0, 1}, {1, 0}, {0, -1}};
    Uint32 srcclr = getpixel( s, x, y );
    Node *stack = NULL;
    Pos p;
    p.x = x;
    p.y = y;

    push( &stack, p );
    while( stack != NULL )
    {
        int i;
        p = pop( &stack );
        putpixel( s, p.x, p.y, dstclr );

        for( i = 0; i < N_DIR; i++ )
        {
            Pos nxtp;
            nxtp.x = p.x + dir[i].x;
            nxtp.y = p.y + dir[i].y;
            if( nxtp.x >= 0 && nxtp.x < s->w
                    && nxtp.y > 0 && nxtp.y < s->h
                    && getpixel( s, nxtp.x, nxtp.y ) == srcclr )
                push( &stack, nxtp );
        }
    }

}


int main ( int argc, char *argv[] )
{
    SDL_Surface *screen;
    SDL_Surface *gfx;
    SDL_Rect rect;

    if ( SDL_Init( SDL_INIT_VIDEO ) < 0 )
    {
        printf( "Unable to init SDL: %s\n", SDL_GetError() );
        return EXIT_FAILURE;
    }

    screen = SDL_SetVideoMode( 640, 480, 16,
                               SDL_SWSURFACE );
    if ( !screen )
    {
        printf( "Unable to set video mode: %s\n", SDL_GetError() );
        return EXIT_FAILURE;
    }

    gfx = SDL_LoadBMP( "test.bmp" );
    assert( gfx != NULL );
    rect.x = screen->w / 2 - gfx->w / 2;
    rect.y = screen->h / 2 - gfx->h / 2;

    SDL_BlitSurface( gfx, NULL, screen, NULL );
    SDL_Flip( screen );

    fill( screen, screen->w / 2, screen->h / 2,
          SDL_MapRGB( screen->format, 0, 255, 0 ) );

    SDL_Flip( screen );

    while( !SDL_QuitRequested() )
        ;

    SDL_Quit();


    return 0;
}