import java.awt.*;
import java.awt.image.*;
import java.util.*;


public class FloodFill {

    ArrayDeque<Pixel> q;
    Callback cb;

    protected BufferedImage pic;
    private BufferedImage rough;
    int markColor;
    int w,h;

    public FloodFill(BufferedImage bimg, Callback c) {
        cb = c;
        pic = bimg;
        w = pic.getWidth();
        h = pic.getHeight();

        rough = new BufferedImage(w,h,BufferedImage.TYPE_INT_RGB);
        Graphics temp = rough.getGraphics();
        temp.setColor(Color.WHITE);
        temp.fillRect(0,0,w,h);
        q = new ArrayDeque<Pixel>();
    }

    public void draw(Graphics g, int x, int y) {
        g.drawImage(rough,x,y,null);
    }

    private boolean outside(Pixel p) {
        return (p.j<left || p.j>right || p.i<top || p.i>bottom);
    }

    public BufferedImage getRough() {
        return rough;
    }

    private int top, bottom, left, right;

    // {{{ Comment : How fill works
/*
We start with a pixel s, and start spreading from it using
breadth first search within the rectangle [l,r]x[t,b]. The
neighbourhood system is determined by useN8. The "rough" image 
keeps track of the pixels already considered, so that pixels
do not get added more than once to the queue. For each pixel in
the region we invoke the work method of the CallBack
interface. The parameter id is passed to it unchanged. This
parameter is not used in the fill alogorithm. It is a way to pass
info from the caller to the work method. 
*/
// }}}
    public int fill(Pixel s, int id, boolean useN8) throws Exception {
        locCount = 1;
        int dk = (useN8? 1 : 2); //The direction counter increment

        markColor = RED;
        q.addFirst(s);
        rough.setRGB(s.j,s.i,markColor);

        while(!q.isEmpty()) {
            Pixel p = q.removeLast();
            //System.err.println("Current pixel = "+p);
            // {{{ Find children, and add to Q
            for(int k=0;k<8;k+=dk) {
                Pixel n = p.nbr(k);
                //System.err.print("\tConidering neighbour "+n+": ");
                if(isFriend(p,n)) {
                    //System.err.println("friend.");
                    tryToMark(n);
                }
                else {
                    //System.err.println("not a friend.");
                }
            }
            // }}}
            cb.work(p,id);
        }
        return locCount;
    }
    
    private int locCount;

    public boolean isFriend(Pixel a, Pixel b) {
        if(b.i<0 || b.i>=h || b.j<0 || b.j>=w) return false;
        //System.err.println("colour @"+a+" is "+pic.getRGB(a.j,a.i));
        //System.err.println("colour @"+b+" is "+pic.getRGB(b.j,b.i));
        return (pic.getRGB(b.j,b.i)==pic.getRGB(a.j,a.i));
    }
 
    public static final int 
        RED =  (0xff<<24) | (0xff<<16),
        BLUE = (0xff<<24) | 0xff;

    private void tryToMark(Pixel n) {
        int col = rough.getRGB(n.j,n.i);
        if(col!=markColor) {
            q.addFirst(n);
            rough.setRGB(n.j,n.i,markColor);
            locCount++;
        }
    }
}