/* pnmdissect.c - dissect a portable anymap
**
** Copyright (C) 1998 by Jef Poskanzer.
**
** Permission to use, copy, modify, and distribute this software and its
** documentation for any purpose and without fee is hereby granted, provided
** that the above copyright notice appear in all copies and that both that
** copyright notice and this permission notice appear in supporting
** documentation.  This software is provided "as is" without express or
** implied warranty.
*/

#include "pnm.h"


/* Forwards. */
static void pushflood( int col, int row );
static int popflood( int* colP, int* rowP );


static int rows, cols;

int
main( int argc, char* argv[] )
    {
    FILE* ifp;
    xel** xels;
    xel background;
    xelval maxval;
    int argn, format;
    int minsize, adjacency;
    int row, col, minrow, maxrow, mincol, maxcol, row2, col2, i, j;
    char** markers;
    char* infilename;
    char infileext[500];
    char* dot;
    int outfilecount;
    char outfilename[500];
    FILE* outfile;
    char* usage = "[-adjacency n] [-minsize n] [pnmfile]";

    pnm_init( &argc, argv );

    argn = 1;
    adjacency = 2;
    minsize = 5;

    while ( argn < argc && argv[argn][0] == '-' && argv[argn][1] != '\0' )
	{
	if ( pm_keymatch( argv[argn], "-adjacency", 2 ) )
	    {
	    ++argn;
	    if ( argn == argc || sscanf( argv[argn], "%d", &adjacency ) != 1 )
		pm_usage( usage );
	    if ( minsize < 1 )
		pm_usage( usage );
	    }
	else if ( pm_keymatch( argv[argn], "-minsize", 2 ) )
	    {
	    ++argn;
	    if ( argn == argc || sscanf( argv[argn], "%d", &minsize ) != 1 )
		pm_usage( usage );
	    if ( minsize < 1 )
		pm_usage( usage );
	    }
	else
	    pm_usage( usage );
	++argn;
	}

    if ( argn != argc )
	{
	infilename = argv[argn];
	ifp = pm_openr( infilename );
	++argn;
	}
    else
	{
	infilename = "stdin";
	ifp = stdin;
	}

    if ( argn != argc )
	pm_usage( usage );

    xels = pnm_readpnm( ifp, &cols, &rows, &maxval, &format );
    pm_closer( ifp );

    background = pnm_backgroundxel( xels, cols, rows, maxval, format );

    /* Allocate the markers array. */
    markers = (char**) pm_allocarray( cols, rows, sizeof(char) );

    /* Clear it out - every pixel marked as an 'o'bject. */
    for ( row = 0; row < rows; ++row )
        for ( col = 0; col < cols; ++col )
	    markers[row][col] = 'o';

    /* Flood-fill, marking background pixels as 'b'. */
    pm_message( "dissecting..." );
    pushflood( 0, 0 );
    pushflood( cols - 1, 0 );
    pushflood( 0, rows - 1 );
    pushflood( cols - 1, rows - 1 );
    while ( popflood( &col, &row ) )
	if ( markers[row][col] == 'o' &&
	     PNM_EQUAL( xels[row][col], background ) )
	    {
	    markers[row][col] = 'b';
	    pushflood( col, row - 1 );
	    pushflood( col - 1, row );
	    pushflood( col + 1, row );
	    pushflood( col, row + 1 );
	    }

    /* Scan for pixels marked 'o'.  Do another flood-fill on the 'o's,
    ** turning them to 'b's and remembering the max and min row and col.
    ** Each resulting region is written out as a separate image.
    */
    outfilecount = 0;
    dot = strchr( infilename, '.' );
    if ( dot != (char*) 0 )
	{
	(void) strcpy( infileext, dot + 1 );
	*dot = '\0';
	}
    else
	infileext[0] = '\0';
    for ( row = 0; row < rows; ++row )
        for ( col = 0; col < cols; ++col )
	    if ( markers[row][col] == 'o' )
		{
		minrow = maxrow = row;
		mincol = maxcol = col;
		pushflood( col, row );
		while ( popflood( &col2, &row2 ) )
		    {
		    if ( markers[row2][col2] == 'o' )
			{
			markers[row2][col2] = 'b';
			minrow = min( minrow, row2 );
			maxrow = max( maxrow, row2 );
			mincol = min( mincol, col2 );
			maxcol = max( maxcol, col2 );
			for ( i = -adjacency ; i <= adjacency; ++i )
			    for ( j = -adjacency ; j <= adjacency; ++j )
				if ( i != 0 || j != 0 )
				    pushflood( col2 + i, row2 + j );
			}
		    }
		/* Check if the region is large enough. */
		if ( maxcol - mincol + 1 >= minsize ||
		     maxrow - minrow + 1 >= minsize )
		    {
		    ++outfilecount;
		    if ( infileext[0] != '\0' )
			(void) sprintf(
			    outfilename, "%s_%03d.%s", infilename, outfilecount,
			    infileext );
		    else
			(void) sprintf(
			    outfilename, "%s_%03d", infilename, outfilecount );
		    pm_message(
			"writing out (%d-%d,%d-%d) as %s",
			minrow, maxrow, mincol, maxcol, outfilename );
		    outfile = pm_openw( outfilename );
		    pnm_writepnminit(
			outfile, maxcol - mincol + 1, maxrow - minrow + 1,
			maxval, format, 0 );
		    for ( row2 = minrow; row2 <= maxrow; ++row2 )
			pnm_writepnmrow(
			    outfile, &(xels[row2][mincol]),
			    maxcol - mincol + 1, maxval, format, 0 );
		    pm_closew( outfile );
		    }
		}

    /* All done. */
    exit( 0 );
    }


static short* fcols;
static short* frows;
static int fstacksize = 0, fstackp = 0;

static void
pushflood( int col, int row )
    {
    if ( col < 0 || col >= cols || row < 0 || row >= rows )
	return;
    if ( fstackp >= fstacksize )
	{
	if ( fstacksize == 0 )
	    {
	    fstacksize = 10000;
	    fcols = (short*) malloc( fstacksize * sizeof(short) );
	    frows = (short*) malloc( fstacksize * sizeof(short) );
	    if ( fcols == (short*) 0 || frows == (short*) 0 )
		pm_error( "out of memory" );
	    }
	else
	    {
	    fstacksize *= 4;
	    fcols = (short*) realloc(
		(char*) fcols, fstacksize * sizeof(short) );
	    frows = (short*) realloc(
		(char*) frows, fstacksize * sizeof(short) );
	    if ( fcols == (short*) 0 || frows == (short*) 0 )
		pm_error( "out of memory" );
	    }
	}
    fcols[fstackp] = col;
    frows[fstackp] = row;
    ++fstackp;
    }


static int
popflood( int* colP, int* rowP )
    {
    if ( fstackp <= 0 )
	return 0;
    --fstackp;
    *colP = fcols[fstackp];
    *rowP = frows[fstackp];
    return 1;
    }