package adarsha;
[Update:[Tue Jan 02 IST 2018]]

// {{{ To do (Tue Jan 14 IST 2014))
/*
1)  The  program  expects  3  calibration  symbols  at  the  very
beginning,  and makes  mistakes  if it  encounters  a noise  blob
instead. A blob should be ignored if its boundary is not as large
as that of a symbol.  

2) Also the program enters an  infinite loop if the top left hand
pixel (or  the left/top margin)  has black blobs. This  should be
corrected. How?

3)  GIMP's  default thresholding  is  not  good. Move  the  lower
threshold all  the up to (but  a bit shy of)  where the histogram
starts  rising. Need  to do  this automatically  inside the  java
program.

 */
// }}}
// {{{ Imports
 import java.awt.*;
 import java.awt.image.*;
 import javax.swing.*;
 import javax.imageio.*;
 import java.io.*;
 import java.util.*;
     // }}}

public class Boundary
    implements Callback {
    private BufferedImage img,fin;
    int w,h, cenI, cenJ;
    int left, right, top, bottom;
    //Dict dict;
    private int BACKGROUND = -1;
    FloodFill ff;

    Vector<Axar> box;

    
    public Boundary(JProgressBar pbar) {
        box = new Vector<Axar>();
        pb = pbar;
        try {
            tw = new PrintWriter(new FileOutputStream("time.log"));
            pw = new PrintWriter(new FileOutputStream("ocr.log"));
        }
        catch(Exception ex) {
            ex.printStackTrace();
        }
    }

    public void work(Pixel p, int id) {
        out.setRGB(p.j,p.i,FloodFill.RED);
    }

    public BufferedImage getImage() {
        if(state == ERROR) finG.drawRect(left,top,right-left+1,bottom-top+1);
        return fin;
    }

    // {{{ Thresholding stuff (unused)

    public void doThresh2() {
        int threshold = findThresh();

        for(int i=0;i<h;i++)
            for(int j=0;j<w;j++)
                if((img.getRGB(j,i) & 0xff) > threshold) 
                    img.setRGB(j,i,WHITE);
                else
                    img.setRGB(j,i,BLACK);

        darao();

    }
        
    private int currentThresh;
    private static final int 
        WHITE = 0xffffffff,
        BLACK = 0xff000000;



    private int findThresh() {
        int temp=0;
    
        int freq[] = new int[256];

        for(int i=0;i<h;i++)
            for(int j=0;j<w;j++) {
                int pixVal = img.getRGB(j,i) & 0xff;
                freq[pixVal]++;
            }

        int lowerLim = -1, 
            upperLim = -1;

        for(int i=0;i<256;i++) {
            temp += freq[i];
            if(temp>5000) {
                lowerLim = i;
                break;
            }
        }
        return lowerLim;

        /*
        for(int i=255;i>=0;i--) {
            temp += freq[i];
            if(temp>50) {
                upperLim = i;
                break;
            }
        }

        int startReg = -1,
            endReg = -1;
        int threshstate = 0;
        search: 
        for(int i=lowerLim;i<upperLim;i++) {
            switch(threshstate) {
            case 0: 
                if(freq[i]<20) {
                    startReg = i;
                    state = 1;
                }
                break;
            case 1:
                if(freq[i]>=20) {
                    endReg = i;
                    break search;
                }
                break;
            }
        }

        return (startReg+endReg)/2;
*/
    }       

    private void doThresh() {
        int temp=0;
        int min=300, max=-1;
    
        for(int i=0;i<h;i++) {
            for(int j=0;j<w;j++) {
                int pixVal = img.getRGB(j,i) & 0xff;
                if(min > pixVal) min = pixVal;
                if(max < pixVal) max = pixVal;
            }
            
            int threshold = (max-min> 60? (min+max)/2 : min-1);
            for(int j=0;j<w;j++) {
                if((img.getRGB(j,i) & 0xff) > threshold) 
                    img.setRGB(j,i,WHITE);
                else
                    img.setRGB(j,i,BLACK);
            }                
        }
    }

    // }}}


    private boolean isFG(int i, int j) {
        if(i<0 || i>=h || j<0 || j>=w) return false;
        dbg("col at ("+i+", "+j+") is "+(img.getRGB(j,i) & 0xffffff));
        return (img.getRGB(j,i)&0xffffff)!=(BACKGROUND&0xffffff);
    }

    Graphics imgG, outG, finG;

    int state;
    final int IMG=1, OUT = 2, FINAL = 3, ERROR= 4;

    public void prepare(String fname) throws Exception {
        img = ImageIO.read(new File(fname));

        tw.println("#-------["+fname+"]---");
        pw.println("#-------["+fname+"]---");
        System.out.println("\n---"+fname+"---");
        state = 0;
        w = img.getWidth();
        h = img.getHeight();
        pb.setMinimum(0);
        pb.setMaximum(h);
        dbg("w = "+w+", h = "+h);
        //doThresh();
        out=new BufferedImage(w,h,BufferedImage.TYPE_INT_ARGB);
        fin=new BufferedImage(w,h,BufferedImage.TYPE_INT_ARGB);
        imgG =  img.getGraphics();
        outG =  out.getGraphics();
        finG =  fin.getGraphics();

        box.clear();
        procCount = 0;
        calib = true;
        calibSucCount = 0;
        calibCount = 0;
        critSizeLarge = critSizeSmall = 10;
        pageI = pageJ = 0;
        darao();
    }

    
    boolean drama;

    BufferedImage out;

    private void dbg(String msg) {
        if(drama) System.err.println(msg);
    }

    int procCount = 0;
    int pageI, pageJ;

    long timeStart;
    JProgressBar pb;

    // Need the following wrapper to add a rectangle to 
    //the page image for debugging.
    public boolean wrapProcess() throws Exception {
        try {
            return process();
        }
        catch(Exception ex) {
            state = ERROR;
            throw ex;
        }
    }

    private boolean process() {
        procCount++;
        pb.setValue(pageI);
        pb.setString(""+procCount);

        timeStart = System.currentTimeMillis();

        // {{{ Find the boundary (return false  if no black pixel)

        BACKGROUND = img.getRGB(0,0) & 0xffffff;
        dcount = 0;
        boolean found = false;
        int i,j=0;

        state = IMG;

        darao();

        // {{{ Find a back pixel (return false if no black pixel)
        // {{{ Comment : Continuing the last search
        /*
          The search starts from where the last search ended. That pixel location is saved 
          as (pageI, pageJ). Note the slight complication about starting value of the 
          inner loop. 
         */
        // }}}
        
        //System.err.print("[b["+pageI+","+pageJ+"]]");
        dbg("Searching for a black pixel..."+BACKGROUND);
        search: for(i=pageI;i<h;i++) {
            int jStart = (i==pageI? pageJ : 0);
            for(j=jStart;j<w;j++) {
                if(isFG(i,j)) {
                    found = true;
                    pageI= i;
                    pageJ = j;
                    break search;
                }
            }
        }
        //System.err.print("{"+procCount+"}");
        //System.err.print("[a["+i+","+j+"]]");

        if(!found) {
            dbg("No black pixel found!");
            return false;
        }
        // }}}

        int cI, cJ, sI, sJ, d=0;

        sI = i;
        sJ = j;
        d = 4;

        Pixel p = new Pixel(sI,sJ);
        Pixel sp = new Pixel(sI,sJ);
        Pixel np=null;

        int count = 0;

        dbg("Bdry pixel found at "+p+": dir = " + d);
        out.setRGB(p.j,p.i,FloodFill.RED);
        //img.setRGB(p.j,p.i,FloodFill.RED);
        float sumI = p.i;
        float sumJ = p.j;


        left = right = p.j;
        top = bottom = p.i;
        count++;

        darao();

        do {
            // {{{ Follow boundary until we return to start

            found = false;
            d = (d+4)%8;
            for(int t=0;t<8;t++) {
                d = (d+1)%8;
                //dbg("Searching in direction "+d);
                np = p.nbr(d);
                //dbg("New pixel at "+np);
                if(isFG(np.i, np.j)) {
                    found = true;
                    break;
                }
            }

            if(!found) {
                img.setRGB(sJ,sI,WHITE);
                out.setRGB(sJ,sI,WHITE);
                timeStamp("notfound -1");
                return true;
            }

            dbg("Found = "+found+"Color at ["+np.i+", "+np.j+"] is "+isFG(np.i,np.j));
            p = np;
            dbg("Bdry pixel found at "+p+": dir = " + d);
            dbg("Color at ["+p.i+", "+p.j+"] is "+isFG(p.i,p.j));
            out.setRGB(p.j,p.i,FloodFill.RED);
            //img.setRGB(p.j,p.i,FloodFill.RED);

            sumI += p.i;
            sumJ += p.j;

            if(p.j < left) left = p.j;
            if(p.j > right) right = p.j;

            if(p.i < top) top = p.i;
            if(p.i > bottom) bottom = p.i;

            count++;

            // }}}
        } while(!(p.equals(sp)));
        state = OUT;

        darao();

        // }}}

        // {{{ Return if too few pixels in boundary
        if(count<50) {
            imgG.setColor(Color.WHITE);
            outG.setColor(Color.WHITE);
            //finG.setColor(Color.RED);
            imgG.fillRect(left,top,right-left+1,bottom-top+1);
            outG.fillRect(left,top,right-left+1,bottom-top+1);
            //finG.drawRect(left,top,right-left+1,bottom-top+1);
            dbg("Small speck ignored.");
            darao();
            //System.err.print("s");
            timeStamp("small "+count);
            return true;
        }
        // }}}

        // {{{ Find the region inside the boundary, "space" if impossible

        cenI = (int)(sumI/count);
        cenJ = (int)(sumJ/count);

        ff = new FloodFill(out, this);
        try {
            ff.fill(new Pixel(cenI,cenJ),0,left,right,top,bottom,false);
        }
        catch(Exception ex) {
            outG.setColor(Color.WHITE);
            outG.fillRect(left,top,right-left+1,bottom-top+1);
            imgG.setColor(Color.WHITE);
            imgG.fillRect(left,top,right-left+1,bottom-top+1);
            output(false,"space");
            timeStamp("space -1");
            return true;
        }

        // }}}

        // {{{ Add the shell to this region
        FloodFill ff0 = new FloodFill(img, this);
        try {
            ff0.fill(sp,0,left,right,top,bottom,true);
        }
        catch(Exception ex) {}

        // }}}

        // {{{ Locate the connected components

        state = FINAL;
        NewCallback cb2 = new NewCallback(fin);
        FloodFill ff2 =  new FloodFill(img,cb2);
        int which = 0;
        boolean bw[] = new boolean[50];
        int size[] = new int[50];

        dbg("top = "+top+", bottom = "+bottom+", left = "+
            left+",right = "+right);
        for(i=top;i<=bottom;i++) {
            for(j=left;j<=right;j++) {
                if(out.getRGB(j,i)==FloodFill.RED && fin.getRGB(j,i)==0) {
                    // {{{ (i,j) within bdry, not yet handled, handle it.

                    dbg("Entered "+which);
                    bw[which] = isFG(i,j);//Determine colour

                    try {
                        size[which] = ff2.fill(new
                                               Pixel(i,j),which,left,right,top,bottom,bw[which]);
                        dbg(""+size[which]);
                    }
                    catch(Exception ex) {
                        // {{{ Comment : Why this should not happen

                        /*
                          FloodFill throws an exception if a filled region tries to spill beyond 
                          the specified boundary: [l,r]x[t,b]. Here we are supposed to remain within 
                          the shell, and the boundary is that of the shell.
                        */

                        // }}}
                        dbg("eta haoya uchit nay!");
                        System.err.println(ex);
                        output(false,"??");
                        // Clean the strange occurence and bail out.
                        clean(top,bottom,left,right);
                        timeStamp("strange -1");
                        return true;
                    }

                    which++;

                    // {{{ Too many components? Just trash and return true! 
                    if(which > 30) {
                        System.out.print("*");
                        clean(top,bottom,left,right);
                        return true;
                    }
                    // }}}
                    darao();

                    // }}}
                }
            }
        }

        int nComp = which;


        dbg("No. of componenents = "+nComp);

        darao();

        // }}}
                                                  
        // {{{ Make the bipartite graph
        boolean mat[][] = new boolean[nComp][nComp];

        for(i=1;i<h;i++) {
            for(j=1;j<w;j++) {

                int thisCol = cb2.khata[i][j];
                int leftCol = cb2.khata[i][j-1];

                if(thisCol==0 || thisCol > nComp) continue;
                if(leftCol > nComp) continue;
                if(leftCol>0 && leftCol!=thisCol) {
                    mat[thisCol-1][leftCol-1] =
                        mat[leftCol-1][thisCol-1] = true;
                }
                
                int topCol = cb2.khata[i-1][j];
                if(topCol > nComp) continue;
                if(topCol>0 && topCol!=thisCol) {
                    mat[thisCol-1][topCol-1] = mat[topCol-1][thisCol-1] = true;
                }
                
            }
        }
        // }}}

        /*
        // {{{ Dump the bipartite graph

          for(i=0;i<nComp;i++) {
          for(j=0;j<nComp;j++)
          System.err.print(mat[i][j]+" ");
          dbg("\n");
          }

        for(i=0;i<nComp;i++)
            for(j=0;j<i;j++)
                if(mat[i][j]) dbg(i+"("+bw[i]+
                                  ","+size[i]+") ~ "+j+
                                  "("+bw[j]+","+size[j]+")");

          // }}} 
        */

        // {{{ Detect small components
        // {{{ Comment: When should we ignore a component? 
        //Ans: 1) If it is black and smaller than critSizeLarge
        //     2) If it is white, connected with shell, and
        //        smaller that critSizeLarge
        //     3) If it is white, not connected with shell
        //        and smaller than critSizeSmall.
        // }}}
        boolean isSmall[] = new boolean[nComp];
        for(i=0;i<nComp;i++) {
                isSmall[i] = (size[i]< (bw[i] || mat[0][i]?
                                        critSizeLarge : critSizeSmall));
        }
        // }}}


        // {{{ Find nLoop and nWhite
        int nLoop = 0, nWhite = 0;

        for(j=0;j<nComp;j++) {
            if(isSmall[j]) continue;
            if(!bw[j]) nWhite++;
            if(mat[0][j]) nLoop++;
        }
        // }}}

        // {{{ Find key 

        boolean isCont = (nWhite > nLoop);

        int k=0;
        int part[] = new int[nLoop];

        dbg("nLoop = "+nLoop+", nComp = "+nComp);
        dbg("top = "+top+", bottom = "+bottom);
        dbg("left = "+left+", right = "+right);

        for(j=0;j<nComp;j++) {
            if(isSmall[j]) continue;
            if(!mat[0][j]) continue;
            //This j coresponds to a loop (white region touching shell)
            for(i=0;i<nComp;i++) 
                if(!isSmall[i] && mat[i][j]) part[k]++;
            k++;
        }
        
        Arrays.sort(part);
        
        /*
        int frq[] = new int[7];

        
        for(i=0;i<nLoop;i++) {
            if(part[i]==0) System.err.println("\n\n\tError!\n");
            frq[part[i]-1]++;
        }
        */

        String key = "";

        for(i=nLoop-1;i>=0;i--)
            key+=(part[i]-1);//Need to subtract 1 to avoid counting
                             //the shell.

        String prefix = (isCont? "+" : "");

        // }}}
              

        if(calib) {
            // {{{ Calibrate, and return true
            
            calibCount++;
            System.err.print("Calibrating attempt "+calibCount);
            //calibrate
            if(isCont && key.equals("33")) {
                System.err.println(" success.");
                calibSucCount++;
                if(calibSucCount==1) minSize = Integer.MAX_VALUE;
                for(i=0;i<nComp;i++) {
                    dbg("size["+i+"] = "+size[i]); 
                    if(!isSmall[i] && minSize>size[i])
                        minSize=size[i];
                }
                    dbg("minSize = "+minSize);
            }
            else {
                System.err.println(" failure ["+key+"]"+isCont);
                System.err.println("top = "+top+", bottom = "+bottom);
                System.err.println("left = "+left+", right = "+right);
            }

            if(calibCount==3) {
                calib=false;
                if(calibSucCount>0) {
                    critSizeLarge = (int)(0.7 * minSize);
                    critSizeSmall = (int)(0.4 * minSize);
                }

                System.err.println("Calibration over.");
                System.err.println("Critical sizes: large = "+
                                   critSizeLarge+", small = "+critSizeSmall);
            }
            clean(top,bottom,left,right);
            timeStamp("calib -1");
            drama = false;
            return true;

            // }}}

        }

        output(isCont,key);

        clean(top,bottom,left,right);

        darao();
        timeStamp("letter -1");
        return true;
    }

    PrintWriter pw, tw;

    private void timeStamp(String msg) {
        long now = System.currentTimeMillis();
        tw.println(procCount+" "+msg+" "+(now-timeStart));
        tw.flush();
    } 

    private void clean(int top,int bottom,int left,int right) {
        for(int i=top;i<=bottom;i++) {
            for(int j=left;j<=right;j++) {
                if(out.getRGB(j,i)==FloodFill.RED) {
                    out.setRGB(j,i,0);
                    img.setRGB(j,i,BACKGROUND);
                }
            }
        }
    }

    int dcount, critSizeSmall, critSizeLarge, minSize, calibCount;
    boolean calib;
    int calibSucCount;

    private void darao() {
        //System.err.print("["+dcount+"]");
        //dcount++;
    }

    int nOutput=0;
    private void output(boolean ic, String let) {
        //dest.setText(dest.getText()+" "+let);
        //System.out.println(cenI+" "+cenJ+" "+prefix+let+"
        //    "+dict.lookUp(let));
        box.add(new Axar(nOutput,top,bottom, left, right, cenI, cenJ,ic,let));
        nOutput++;
    }
            

    int[] group;

    // {{{ Union and find methods
    private void mergeGroups(int gp1, int gp2) {
        if(gp1 < gp2) 
            group[gp2] = gp1;
        else 
            group[gp1] = gp2;
    }

    private int groupOf(int elt) {
        while(group[elt]!=elt) elt = group[elt];
        return elt;
    }
    // }}}

    public void dumpBox() {
        int nAxar = box.size();
        group = new int[nAxar];

        // {{{ Find the transitive closure
        for(int i=0;i<nAxar;i++) 
            group[i] = i;


        for(int i=0;i<nAxar;i++) {
            for(int j=0;j<i;j++) {
                if(box.elementAt(i).
                   sharesLineWith(box.elementAt(j))) {
                    int gpOfI = groupOf(i);
                    int gpOfJ = groupOf(j);
                    mergeGroups(gpOfI, gpOfJ);

                    dbg("----- "+i+" -> "+j);
                    for(int k=0;k<nAxar;k++)
                        dbg(k+": "+group[k]+", ");

                }
            }
        }
        // }}}

        // {{{ Assign the lines to the axars

        for(int i=0;i<nAxar;i++) {
            int temp = i;
            while(group[temp]!=temp) temp = group[temp];
            group[i] = temp;
        }

        for(int i=0;i<nAxar;i++) 
            box.elementAt(i).setLine(group[i]);

        // }}}

        // {{{ Write the final output

        try {
            boolean couldCont = false;           
            Collections.sort(box);
            for(Axar a : box) {
                pw.println(a);
                if(!a.isValid()) {
                    //System.out.print("*");
                    continue;
                }
                if(couldCont && !a.getIsCont()) System.out.print("a");
                System.out.print(a.show());
                couldCont = a.canCont();
            }
            pw.flush();
            pw.close();
        }
        catch(Exception ex) {
            ex.printStackTrace();
        }

        // }}}
    }

    public static void main(String args[]) throws Exception {

        JProgressBar pbar = new JProgressBar();
        pbar.setIndeterminate(false);
        pbar.setStringPainted(true);
        pbar.setBorderPainted(true);
        Boundary bdry = new Boundary(pbar);

        JFrame f = new JFrame("আশ্চর্য লিপি");
        JTabbedPane tabs = new JTabbedPane();
        f.add(tabs);
        f.add(BorderLayout.SOUTH,pbar);
        f.pack();
        f.setSize(500,500);
        f.setVisible(true);
        int i=0;
        try {
            for(i=0;i<args.length;i++) {
                System.err.println("Opening "+args[i]);
                bdry.prepare(args[i]);
                while(bdry.wrapProcess());
                tabs.addTab(args[i],new JScrollPane(new ImageHolder(bdry.getImage())));
                bdry.dumpBox();
                System.err.println("Finished "+args[i]);
            }
        }
        catch(Exception ex) {
            tabs.addTab("[x]"+args[i],new JScrollPane(new ImageHolder(bdry.getImage())));
            System.err.println("Undone at "+bdry.procCount+" of "+args[i]);
            ex.printStackTrace();
        }
    }
}