# include <stdio.h>
# include <stdlib.h>
# include <time.h>

# include "polyomino_condense.h"

/******************************************************************************/

void polyomino_condense ( int mp, int np, int p[], int *mq, int *nq, int **q )

/******************************************************************************/
/*
  Purpose:

    POLYOMINO_CONDENSE condenses a polyomino.

  Discussion:

    A polyomino is a shape formed by connecting unit squares edgewise.

    A polyomino can be represented by an MxN matrix, whose entries are
    1 for squares that are part of the polyomino, and 0 otherwise.

    This program is given an MxN matrix that is meant to represent a 
    polyomino.  It first replaces all nonzero entries by the value 1.
    It then "condenses" the matrix, if possible, by removing initial and
    final rows and columns that are entirely zero.

    While this procedure might save a slight amount of space, its purpose
    is to simplify the task of manipulating polyominos, embedding them in
    larger shapes, and detecting whether two polyominos describe the same
    shape.

    It is entirely possible, and usual, that the output quantities are
    simply copies of the input quantities.

  Licensing:

    This code is distributed under the GNU LGPL license.

  Modified:

    29 April 2018

  Author:

    John Burkardt

  Parameters:

    Input, int MP, NP, the number of rows and columns in the representation
    of the polyomino P.

    Input, int P[MP*NP], a matrix of 0's and 1's representing the 
    polyomino.  

    Output, int *MQ, *NQ, the number of rows and columns of the
    condensed polyomino.

    Output, int *Q[MQ*NQ], the representation of the condensed
    polyomino.
*/
{
  int i;
  int i_max;
  int i_min;
  int j;
  int j_max;
  int j_min;
/*
  Discard nonsense.
*/
  if ( mp <= 0 || np <= 0 )
  {
    *mq = 0;
    *nq = 0;
    *q = NULL;
    return;
  }
/*
  Seek first and last nonzero rows, columns.
*/
  i_min = -1;
  for ( i = 0; i < mp; i++ )
  {
    for ( j = 0; j < np; j++ )
    {
      if ( p[i+j*mp] != 0 )
      {
        i_min = i;
        break;
      }
    }
    if ( i_min != -1 ) 
    {
      break;
    }
  }
/*
  If I_MIN = -1, then we have a null matrix.
*/
  if ( i_min == -1 )
  {
    *mq = 0;
    *nq = 0;
    *q = NULL;
    return;
  }

  i_max = mp;
  for ( i = mp - 1; 0 <= i; i-- )
  {
    for ( j = 0; j < np; j++ )
    {
      if ( p[i+j*mp] != 0 )
      {
        i_max = i;
        break;
      }
    }
    if ( i_max != mp ) 
    {
      break;
    }
  }

  j_min = -1;
  for ( j = 0; j < np; j++ )
  {
    for ( i = 0; i < mp; i++ )
    {
      if ( p[i+j*mp] != 0 )
      {
        j_min = j;
        break;
      }
    }
    if ( j_min != -1 ) 
    {
      break;
    }
  }

  j_max = np;
  for ( j = np - 1; 0 <= j; j-- )
  {
    for ( i = 0; i < mp; i++ )
    {
      if ( p[i+j*mp] != 0 )
      {
        j_max = j;
        break;
      }
    }
    if ( j_max != np ) 
    {
      break;
    }
  }
/*
  Measure the nonzero block.
*/
  *mq = i_max + 1 - i_min;
  *nq = j_max + 1 - j_min;
  *q = ( int * ) malloc ( ( *mq ) * ( *nq ) * sizeof ( int ) );
/*
  Copy the nonzero block.
*/
  for ( j = 0; j < *nq; j++ )
  {
    for ( i = 0; i < *mq; i++ )
    {
      if ( p[(i+i_min)+(j+j_min)*mp] != 0 )
      {
        (*q)[i+j*(*mq)] = 1;
      }
      else
      {
        (*q)[i+j*(*mq)] = 0;
      }
    }
  }

  return;
}
/******************************************************************************/

void polyomino_print ( int m, int n, int p[], char *label )

/******************************************************************************/
/*
  Purpose:

    POLYOMINO_PRINT prints a polyomino.

  Licensing:

    This code is distributed under the GNU LGPL license.

  Modified:

    29 April 2018

  Author:

    John Burkardt

  Parameters:

    Input, int M, N, the number of rows and columns in the representation
    of the polyomino P.

    Input, int P[M*N], a matrix of 0's and 1's representing the 
    polyomino.  

    Input, char *LABEL, a title for the polyomino.
*/
{
  int i;
  int j;

  printf ( "\n" );
  printf ( "%s\n", label );
  printf ( "\n" );
  if ( m <= 0 || n <= 0 )
  {
    printf ( " [ NULL matrix ]" );
  }
  else
  {
    for ( i = 0; i < m; i++ )
    {
      for ( j = 0; j < n; j++ )
      {
        printf ( " %d", p[i+j*m] );
      }
      printf ( "\n" );
    }
  }
  return;
}
/******************************************************************************/

void timestamp ( )

/******************************************************************************/
/*
  Purpose:

    TIMESTAMP prints the current YMDHMS date as a time stamp.

  Example:

    17 June 2014 09:45:54 AM

  Licensing:

    This code is distributed under the GNU LGPL license. 

  Modified:

    17 June 2014

  Author:

    John Burkardt

  Parameters:

    None
*/
{
# define TIME_SIZE 40

  static char time_buffer[TIME_SIZE];
  const struct tm *tm;
  time_t now;

  now = time ( NULL );
  tm = localtime ( &now );

  strftime ( time_buffer, TIME_SIZE, "%d %B %Y %I:%M:%S %p", tm );

  printf ( "%s\n", time_buffer );

  return;
# undef TIME_SIZE
}