//the floodfill algorithms
void floodFill4(int x, int y, int newColor, int oldColor);
void floodFill8(int x, int y, int newColor, int oldColor);
void floodFill4Stack(int x, int y, int newColor, int oldColor);
void floodFill8Stack(int x, int y, int newColor, int oldColor);
void floodFillScanline(int x, int y, int newColor, int oldColor);
void floodFillScanlineStack(int x, int y, int newColor, int oldColor);
//the stack (NOTE: use better data structure like std::vector push_back and pop_back to avoid such limits)
#define stackSize 16777216
int stack[stackSize];
int stackPointer;
//the auxiliary functions
bool paint_drawLine(int x1, int y1, int x2, int y2, ColorRGB color);
void clearScreenBuffer(ColorRGB color);
//the graphics buffer
#define screenW 256
#define screenH 256
int screenBuffer[screenH][screenW]; // ycoordinate first because it works per scanline

int main(int argc, char *argv[])
{
screen(screenW, screenH, 0, "Flood Fill");
clearScreenBuffer(RGB_White);
int mouseX, mouseY;
int oldMouseX, oldMouseY;
bool LMB, RMB;
while(!done())
{
oldMouseX = mouseX;
oldMouseY = mouseY;
getMouseState(mouseX, mouseY, LMB, RMB);
//3 different mouse input actions
if(LMB) paint_drawLine(oldMouseX, oldMouseY, mouseX, mouseY, RGB_Black);
if(RMB)
{
int color = RGBtoINT(ColorRGB((mouseX % 3 + 1) * 64, (mouseY % 8) * 32, (mouseX + mouseY) % 256));
floodFillScanlineStack(mouseX, mouseY, color, screenBuffer[mouseY][mouseX]);
}
if(RMB && LMB) clearScreenBuffer(RGB_White);
//benchmark
readKeys();
if(inkeys[SDLK_SPACE])
{
float startTime = getTime();
for(int i = 1; i < 50; i++) floodFill4Stack(mouseX, mouseY, RGBtoINT(ColorRGB(i,255,i)), screenBuffer[mouseY][mouseX]);
float endTime = getTime();
float startTime2 = getTime();
for(int i = 1; i < 50; i++) floodFillScanlineStack(mouseX, mouseY, RGBtoINT(ColorRGB(i,255,i)), screenBuffer[mouseY][mouseX]);
float endTime2 = getTime();
drawBuffer(screenBuffer[0]);
print(endTime  startTime, 0, 0, 0, RGB_Black, 1, RGB_White);
print(endTime2  startTime2, 0, 0, 8, RGB_Black, 1, RGB_White);
redraw();
sleep();
}
//redraw the screen each frame
drawBuffer(screenBuffer[0]);
redraw();
}
return 0;
}

bool pop(int& x, int& y)
{
if(stackPointer > 0)
{
int p = stack[stackPointer];
x = p / h;
y = p % h;
stackPointer;
return 1;
}
else
{
return 0;
}
}
bool push(int x, int y)
{
if(stackPointer < stackSize  1)
{
stackPointer++;
stack[stackPointer] = h * x + y;
return 1;
}
else
{
return 0;
}
}
void emptyStack()
{
int x, y;
while(pop(x, y));
}

void clearScreenBuffer(ColorRGB color)
{
for(int y = 0; y < h; y++)
for(int x = 0; x < w; x++)
{
screenBuffer[y][x] = RGBtoINT(color);
}
}

//Recursive 4way floodfill, crashes if recursion stack is full
void floodFill4(int x, int y, int newColor, int oldColor)
{
if(x >= 0 && x < w && y >= 0 && y < h && screenBuffer[y][x][y] == oldColor && screenBuffer[x] != newColor)
{
screenBuffer[y][x] = newColor; //set color before starting recursion
floodFill4(x + 1, y , newColor, oldColor);
floodFill4(x  1, y , newColor, oldColor);
floodFill4(x , y + 1, newColor, oldColor);
floodFill4(x , y  1, newColor, oldColor);
}
}

//Recursive 8way floodfill, crashes if recursion stack is full
void floodFill8(int x, int y, int newColor, int oldColor)
{
if(x >= 0 && x < w && y >= 0 && y < h && screenBuffer[y][x][y] == oldColor && screenBuffer[x] != newColor)
{
screenBuffer[y][x] = newColor; //set color before starting recursion!
floodFill8(x + 1, y , newColor, oldColor);
floodFill8(x  1, y , newColor, oldColor);
floodFill8(x , y + 1, newColor, oldColor);
floodFill8(x , y  1, newColor, oldColor);
floodFill8(x + 1, y + 1, newColor, oldColor);
floodFill8(x  1, y  1, newColor, oldColor);
floodFill8(x  1, y + 1, newColor, oldColor);
floodFill8(x + 1, y  1, newColor, oldColor);
}
}

//4way floodfill using our own stack routines
void floodFill4Stack(int x, int y, int newColor, int oldColor)
{
if(newColor == oldColor) return; //avoid infinite loop
emptyStack();
static const int dx[4] = {0, 1, 0, 1}; // relative neighbor x coordinates
static const int dy[4] = {1, 0, 1, 0}; // relative neighbor y coordinates
if(!push(x, y)) return;
while(pop(x, y))
{
screenBuffer[y][x] = newColor;
for(int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if(nx > 0 && nx < w && ny > 0 && ny < h && screenBuffer[ny][nx] == oldColor) {
if(!push(nx, ny)) return;
}
}
}
}

//4way floodfill using our own stack routines
void floodFill4Stack(int x, int y, int newColor, int oldColor)
{
if(newColor == oldColor) return; //avoid infinite loop
emptyStack();
static const int dx[8] = {0, 1, 1, 1, 0, 1, 1, 1}; // relative neighbor x coordinates
static const int dy[8] = {1, 1, 0, 1, 1, 1, 0, 1}; // relative neighbor y coordinates
if(!push(x, y)) return;
while(pop(x, y))
{
screenBuffer[y][x] = newColor;
for(int i = 0; i < 8; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if(nx > 0 && nx < w && ny > 0 && ny < h && screenBuffer[ny][nx] == oldColor) {
if(!push(nx, ny)) return;
}
}
}
}

//stack friendly and fast floodfill algorithm
void floodFillScanline(int x, int y, int newColor, int oldColor)
{
if(oldColor == newColor) return;
if(screenBuffer[y][x] != oldColor) return;
int x1;
//draw current scanline from start position to the right
x1 = x;
while(x1 < w && screenBuffer[y][x1] == oldColor)
{
screenBuffer[y][x1] = newColor;
x1++;
}
//draw current scanline from start position to the left
x1 = x  1;
while(x1 >= 0 && screenBuffer[y][x1] == oldColor)
{
screenBuffer[y][x1] = newColor;
x1;
}
//test for new scanlines above
x1 = x;
while(x1 < w && screenBuffer[y][x1] == newColor)
{
if(y > 0 && screenBuffer[y  1][x1] == oldColor)
{
floodFillScanline(x1, y  1, newColor, oldColor);
}
x1++;
}
x1 = x  1;
while(x1 >= 0 && screenBuffer[y][x1] == newColor)
{
if(y > 0 && screenBuffer[y  1][x1] == oldColor)
{
floodFillScanline(x1, y  1, newColor, oldColor);
}
x1;
}
//test for new scanlines below
x1 = x;
while(x1 < w && screenBuffer[y][x1] == newColor)
{
if(y < h  1 && screenBuffer[y + 1][x1] == oldColor)
{
floodFillScanline(x1, y + 1, newColor, oldColor);
}
x1++;
}
x1 = x  1;
while(x1 >= 0 && screenBuffer[y][x1] == newColor)
{
if(y < h  1 && screenBuffer[y + 1][x1] == oldColor)
{
floodFillScanline(x1, y + 1, newColor, oldColor);
}
x1;
}
}

//The scanline floodfill algorithm using our own stack routines, faster
void floodFillScanlineStack(int x, int y, int newColor, int oldColor)
{
if(oldColor == newColor) return;
emptyStack();
int x1;
bool spanAbove, spanBelow;
if(!push(x, y)) return;
while(pop(x, y))
{
x1 = x;
while(x1 >= 0 && screenBuffer[y][x1] == oldColor) x1;
x1++;
spanAbove = spanBelow = 0;
while(x1 < w && screenBuffer[y][x1] == oldColor )
{
screenBuffer[y][x1] = newColor;
if(!spanAbove && y > 0 && screenBuffer[y  1][x1] == oldColor)
{
if(!push(x1, y  1)) return;
spanAbove = 1;
}
else if(spanAbove && y > 0 && screenBuffer[y  1][x1] != oldColor)
{
spanAbove = 0;
}
if(!spanBelow && y < h  1 && screenBuffer[y + 1][x1] == oldColor)
{
if(!push(x1, y + 1)) return;
spanBelow = 1;
}
else if(spanBelow && y < h  1 && screenBuffer[y + 1][x1] != oldColor)
{
spanBelow = 0;
}
x1++;
}
}
}
