// from krayon

void Fill::drawFlood(KisLayer *lay, QRect & layerRect, int x, int y)
{
    // make sure desired pixel is in bounds - can operate on 
    // selection as well as entire image, so layerRect is not
    // always same as imageExtents (later)
    if(!layerRect.contains(x, y)) 
        return;

    // pixel is not same color as source pixel color, return
    if((lay->pixel(0, x, y) != sRed)
    || (lay->pixel(1, x, y) != sGreen) 
    || (lay->pixel(2, x, y) != sBlue))
    {
        return;
    }

    // pixel is already the desired (new) color, return
    if((lay->pixel(0, x, y) == nRed)
    && (lay->pixel(1, x, y) == nGreen) 
    && (lay->pixel(2, x, y) == nBlue))
    {
        return;
    }

    // pixel is same as original color, set it to new color
    lay->setPixel(0, x, y, nRed);
    lay->setPixel(1, x, y, nGreen);
    lay->setPixel(2, x, y, nBlue);
    
    if(layerRect.contains(x, y-1)) 
        drawFlood(lay, layerRect, x, y-1);
    if(layerRect.contains(x, y+1))         
        drawFlood(lay, layerRect, x, y+1);
    if(layerRect.contains(x-1, y))         
        drawFlood(lay, layerRect, x-1, y);
    if(layerRect.contains(x+1, y))         
        drawFlood(lay, layerRect, x+1, y);
}

// from gpaint

#define STACKSIZE 10000

/* algorithm based on SeedFill.c from GraphicsGems 1 */

static void flood_fill(struct fillinfo *info, int x, int y)
{
   struct fillpixelinfo stack[STACKSIZE];
   struct fillpixelinfo * sp = stack;
   
   int l, x1, x2, dy;
   
#define PUSH(py, pxl, pxr, pdy) \
{  struct fillpixelinfo *p = sp;\
   if (((py) + (pdy) >= 0) && ((py) + (pdy) < info->height))\
   {\
      p->y = (py);\
      p->xl = (pxl);\
      p->xr = (pxr);\
      p->dy = (pdy);\
      sp++; \
   }\
}
   
   
#define POP(py, pxl, pxr, pdy) \
{\
   sp--;\
   (py) = sp->y + sp->dy;\
   (pxl) = sp->xl;\
   (pxr) = sp->xr;\
   (pdy) = sp->dy;\
}

      
   if ((x >= 0) && (x < info->width) && (y >= 0) && (y < info->height))
   {
      if ((info->or == info->r) && (info->og == info->g) && (info->ob == info->b))
         return;
      
      PUSH(y, x, x, 1);
      PUSH(y + 1, x, x, -1);
      	 
      while (sp > stack)	
      {
         POP(y, x1, x2, dy);
	 for (x = x1; (x >= 0) && is_old_pixel_value(info, x, y); x--)
	    set_new_pixel_value(info, x, y);
	 if (x >= x1) goto skip;
	 l = x + 1;
	 if (l < x1)
	    PUSH(y, l, x1 - 1, -dy);
	 x = x1 + 1;
	 do
	 {
	    for (; (x < info->width) && is_old_pixel_value(info, x, y); x++)
	       set_new_pixel_value(info, x, y);
	    
	    PUSH(y, l, x - 1, dy);
	    if (x > x2 + 1)
	       PUSH(y, x2 + 1, x - 1, -dy);
skip:
            for (x++; x <= x2 && !is_old_pixel_value(info, x, y); x++) 
	       ;
	    
	    l = x;
	 } while (x <= x2);
	 	       
	
      }
   }

#undef POP
#undef PUSH