#ifndef inc_gfx_flood_fill
#define inc_gfx_flood_fill

#include <gfx/canvas.h>
#include <smart_array.h>

    namespace gfx
    {
        struct floodfill_stack_t
        {
            floodfill_stack_t()
            {
                stack.allocate(2);
                stack_pointer = 0;
                max_stack = 0;
            }
            bool push(int x, int y);
            bool pop(int &x, int &y);
            void clear()
            {
                stack_pointer = 0;
            }
            int stack_pointer;
            int max_stack;
            smart_array<point> stack;
        };

        void floodfill(gfx::canvas &g, floodfill_stack_t &stack, const point &pt, const argb &new_color, const argb &old_color);
    }

#endif

#include "flood_fill.h"

using namespace gfx;

bool floodfill_stack_t::push(int x, int y)
{
    if (stack_pointer == stack.get_length() - 1) {
        stack.reallocate(stack.get_length() * 2);
    }

    stack[stack_pointer] = point(x, y);
    stack_pointer++;

    if (stack_pointer > max_stack) {
        max_stack = stack_pointer;
    }

    return 1;
}

bool floodfill_stack_t::pop(int &x, int &y)
{
    if (stack_pointer > 0) {
        x = stack[stack_pointer - 1].x;
        y = stack[stack_pointer - 1].y;
        stack_pointer--;
        return 1;
    } else {
        return 0;
    }
}

void gfx::floodfill(gfx::canvas &g, floodfill_stack_t &stack, const point &pt, const argb &new_color, const argb &old_color)
{
    if (old_color == new_color) {
        return;
    }

    int x = pt.x;
    int y = pt.y;

    stack.clear();

    if (!stack.push(x, y)) {
        return;
    }

    while (stack.pop(x, y)) {
        int y1 = y;
        while (y1 >= 0) {
            argb c = g.read(x, y1);
            if (c != old_color) {
                break;
            }
            y1--;
        }
        y1++;

        bool spanLeft = false;
        bool spanRight = false;

        while (y1 < g.height()) {
            argb c = g.read(x, y1);
            if (c != old_color) {
                break;
            }

            g.pixel(x, y1, new_color);

            if (!spanLeft && x > 0 && g.read(x - 1, y1) == old_color) {
                    if (!stack.push(x - 1, y1)) {
                        return;
                    }
                    spanLeft = true;
            } else if (spanLeft && x > 0 && g.read(x - 1, y1) != old_color) {
                    spanLeft = false;
            }

            if (!spanRight && x < g.width() - 1 && g.read(x + 1, y1) == old_color) {
                    if (!stack.push(x + 1, y1)) {
                        return;
                    }
                    spanRight = true;
                } else if (spanRight && x < g.width() - 1 && g.read(x + 1, y1) != old_color) {
                    spanRight = false;
            }
            y1++;
        }
    }
}