/* Splits a PGM image of N fragments into N separate images. */
/* Improved version of PZSPlit: does not generate images with holes. */
/* Last edited on 2015-01-20 16:48:26 by stolfilocal */

#include <stdio.h>

#include <argparser.h>

#include <pz_image.h>
#include <pz_types.h>
 

TYPE

  Options = struct ??? {
    char *inFile;       /* Input image name, without the ".pgm" extension */
    char *outPrefix;    /* Output image name prefix, without the ".pgm" extension */
    unsigned startNum;      /* First fragment number */
    unsigned sep; /* Intensity value that separates bg from fg. */
  } ???;

  IntPoint == i2_t;

  Pixels == ARRAY OF IntPoint;
  

int main(int argc, char **argv 
  )
  VAR image : REF pz_image_t;
  {

    { /* with */
      ??? o = pz_get_options(int argc, char **argv);
      /* do */
      image = pz_image_read_pgm(o.inFile);
      SplitPuzzle(o.outPrefix, o.startNum, image^, o.sep);
      fprintf(stderr, " ok !! \n");
     };
  } /* Main */


void SplitPuzzle(
    char *outPrefix, 
    unsigned startNum, 
    pz_image_t *M, 
    unsigned sep 
  )
  /* 
    Gets a PGM image "M" of a puzzle, identifies the pieces, and
    writes each piece to a separate file "outPrefix-0001.pgm",
    "outPrefix-0002.pgm", etc.
    
    The "background" of the input image is defined to be a 8-connected
    set of pixels with value less than or equal to "sep" that contains
    the upper left corner of the image.
    
    A "piece" is a 4-connected component of the complement of the
    background. The "border" of a piece consists of all pixels that
    are 4-adjacent to one of the piece's pixels.
    
    In the output files, the inside and border pixels are copied from
    the original image, while the surrounding background pixels are
    set to 0. */
    
  CONST 
    MinImagePixels == 100; /* Ignore pieces with this perimeter or less */
  VAR 
    nextImageNum: unsigned = startNum;
  {

    { /* with */ 
      ??? MY = (M.ne);
      ??? MX = (M[0].ne);
      ??? pix = NEW(REF Pixels, MX*MY)^;
      ??? mark = NEW(ARRAY *OF ARRAY OF BOOLEAN, MY, MX)^;
      /* do */ 


      void EnqueuePixel(
    unsigned y,
    unsigned x 
  ) 
        /*
          If pixel "M[y,x]" is unmarked, appends it to the queue, and marks it. */
        { 
          if (( NOT mark[y,x] )){ 
            pix[f] = IntPoint{x, y};
            mark[y,x] = TRUE;
            f++;
          }
        } /* EnqueuePixel */ 
        

      void EnqueueFirstBackgroundPixel( 
  )
        /*
          Locates a bacground pixel near corner "M[0,0]",
          and inserts it into the queue. */
        {
          for (k = 0; k <= min(MY,MX)-1 ; k++){
            for (y = 0; y <= k ; y++){

              { /* with */
                ??? x = k - y;
                /* do */
                if (( M[y,x] <= sep )){ 
                  EnqueuePixel(y,x); return ;
                };
              };
            };
          };
          affirm(FALSE ); /* Could not find a background pixel. */
        } /* EnqueueFirstBackgroundPixel */
      

      void PropagateBackground( 
  )
        /*
          Repeatedly extracts from the queue a pixel with coordinates "(x,y)" that 
          is assumed to be part of the background. Finds all unmarked
          pixels that are 8-connected to it and have intensity "sep" or less,
          inserts them into the queue, and marks them. */
        {
          while (  s < f ){ 

            { /* with */ 
              ??? xp = pix[s][0];
              ??? yp = pix[s][1];
              /* do */ 
              affirm(mark[yp,xp] );
              affirm(M[yp,xp] <= sep );
              for (dx = -1; dx <= +1 ; dx++){ 
                for (dy = -1; dy <= +1 ; dy++){
                  if (( dx != 0 ) || ( dy != 0 )){ 

                    { /* with */
                      ??? x = xp+dx, y = yp+dy;
                      /* do */
                      if (( (x >= 0) ) ANDAND ( (x < MX) ) ANDAND ( (y >= 0) ) ANDAND ( (y < MY) )){
                        if (( M[y,x] <= sep )){ EnqueuePixel(y,x) ;};
                      };
                    };
                  };
                };
              };
            };
            s++;;
          };
        } /* PropagateBackground */  


      void PropagateForeground( 
  )
        /*
          Repeatedly extracts from the queue a pixel with coordinates "(x,y)" that 
          is assumed to be part of the foreground. Finds all unmarked pixels that are
          4-connected to it and have value greater than "sep", and inserts them into
          the queue, marking them. */
        {
          while (  s < f ){ 

            { /* with */ 
              ??? x = pix[s][0];
              ??? y = pix[s][1];
              /* do */ 
              affirm(mark[y,x] );
              if (( y > 0 )){ EnqueuePixel(y-1,x) ;};                                        
              if (( x > 0 )){ EnqueuePixel(y,x-1) ;};      
              if (( y < MY-1 )){ EnqueuePixel(y+1,x) ;};   
              if (( x < MX-1 )){ EnqueuePixel(y,x+1) ;};;
            };
            s++;;
          };
        } /* PropagateForeground */  
      
      {
        /* First pass: clear all pixel marks. */
        for (y = 0; y <= MY-1 ; y++){ 
          for (x = 0; x <= MX-1 ; x++){  
            mark[y,x] = FALSE;
          };
        };
        
        /* Second pass: find all background pixels and set them to 0. */
        f = 0; s = 0;
        EnqueueFirstBackgroundPixel();
        PropagateBackground();
        
        /* Third pass: find all pieces and extract them as separate images. */
        for (y = 0; y <= MY-1 ; y++){ 
          for (x = 0; x <= MX-1 ; x++){  
            if (( NOT mark[y,x] )){
              f = 0; s = 0;
              EnqueuePixel(y,x);
              PropagateForeground();
              if (( f > MinImagePixels )){

                { /* with */ 
                  ??? newImage = ExtractFragmentImage(M, SUBARRAY(pix, 0, f));
                  /* do */
                  WriteFragmentImage(outPrefix, nextImageNum, newImage^);
                };
                nextImageNum++;
              };
            } ;
          };
        };
      };
    }   
  } /* SplitPuzzle */
  

void WriteFragmentImage( 
    char *fname,
    unsigned imageNum, 
    pz_image_t *P 
  )
  { 
  /*
    Writes an image with the puzzle piece stored in "P". */

     { /* with */
       ??? name = fname & "-" & Fmt.Pad(Fmt.Int(imageNum), 4, '0');
       /* do */ 
       fprintf(stderr, name);
       fprintf(stderr, "\n");
       pz_image_write_pgm(name, P);
     }  
  } /* WriteFragmentImage */ 


pz_image_t *ExtractFragmentImage(
    pz_image_t *M, 
    Pixels *pix 
  )
  /*
    Creates an image containing the given pixels from "M", plus all
    their 4-connected neighbors. */

  VAR minX, maxX, minY, maxY : unsigned;


  void FindMinMax( 
  ) 
    {
      affirm((pix.ne) >= 1 );
      minX = pix[0][0];
      maxX = pix[0][0];
      minY = pix[0][1];
      maxY = pix[0][1];

      for (i = 1; i < (pix.ne ) ; i++){

        { /* with */
          ??? x = pix[i][0], y = pix[i][1];
          /* do */
          if (( minX > x  )){ minX = x ;};
          if (( minY > y  )){ minY = y ;};
          if (( maxX < x  )){ maxX = x ;};
          if (( maxY < y  )){ maxY = y ;};;
        };
      }
    } /* FindMinMax */

  { 
    FindMinMax();

    { /* with */
      ??? MY = (M.ne);
      ??? MX = (M[0].ne);
      ??? PY = (maxY - minY + 1) + 2;
      ??? PX = (maxX - minX + 1) + 2;
      ??? rP = pz_image_new(PY, PX);
      ??? P = rP^;
      /* do */ 
      /* Clear whole image: */
      for (y = 0; y <= PY-1 ; y++){ 
        for (x = 0; x <= PX-1 ; x++){ 
          P[y,x] = 0;
        };
      };
      
      /* Copy pixels and their 4-connected neighbors: */
      for (i = 0; i < (pix.ne ) ; i++){ 

        { /* with */ 
          ??? xM = pix[i][0];
          ??? yM = pix[i][1];
          ??? xP = xM - minX + 1;
          ??? yP = yM - minY + 1;
          /* do */ 
          P[yP, xP] = M[yM,xM];
          if (( yM > 0 )){ P[yP-1,xP] = M[yM-1,xM] ;};
          if (( xM > 0 )){ P[yP,xP-1] = M[yM,xM-1] ;};
          if (( yM < MY-1 )){ P[yP+1,xP] = M[yM+1,xM] ;};
          if (( xM < MX-1 )){ P[yP,xP+1] = M[yM,xM+1] ;};
        };
      };
      return rP;
    }
  } /* ExtractFragmentImage */
 

Options  pz_get_options(int argc, char **argv 
  )
  VAR o: Options;
  {
    argparser_t *pp = argparser_new(stderr, argc, argv);
    argparser_set_help(pp, PROG_NAME " version " PROG_VERS ", usage:\n" PROG_HELP);
    argparser_set_info(pp, PROG_INFO);
    argparser_process_help_info_options(pp);
    

    { /* with */
      /* do */

      TRY
        argparser_get_keyword(pp, "-inFile");
        o.inFile = argparser_get_next(pp);
   
        if (( argparser_keyword_present(pp, "-outPrefix") )){
          o.outPrefix = argparser_get_next(pp)
        }else{
          o.outPrefix = o.inFile;
        };
        
        if (( argparser_keyword_present(pp, "-startNum") )){
          o.startNum = argparser_get_next_int(pp, 0, (unsigned.ne - 1))
        }else{
          o.startNum = 0;
        };
        
        argparser_get_keyword(pp, "-sep");
        o.sep = argparser_get_next_int(pp, 0, 254);
   
        argparser_finish(pp);                                       
      EXCEPT                                                            
      | ParseParams.Error ==>                                              
          fprintf(stderr, "Usage: pz_split_ext \\\n");
          fprintf(stderr, "  -inFile <name> \\\n");
          fprintf(stderr, "  [ -outPrefix <name> ] [ -startNum <num> ] \\\n");
          fprintf(stderr, "  -sep <num> \n");
        Process.Exit(1);;
      };;
    };
    return o
    
  } /* GetOptions */
  
{ 

/*
  Copyright © 2001 Universidade Estadual de Campinas (UNICAMP).
  Authors: Helena C. G. Leitão and Jorge Stolfi.
  
  This file can be freely distributed, used, and modified, provided
  that this copyright and authorship notice is preserved, and that any
  modified versions are clearly marked as such.
  
  This software has NO WARRANTY of correctness or applicability for
  any purpose. Neither the authors nor their employers chall be held
  responsible for any losses or damages that may result from its use.
*/