# include <cstdlib>
# include <cstring>
# include <ctime>
# include <iomanip>
# include <iostream>

using namespace std;

# include "polyomino_condense.hpp"

//****************************************************************************80

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

//****************************************************************************80
//
//  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 = new int [ mq * nq ];
//
//  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;
}
//****************************************************************************80

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

//****************************************************************************80
//
//  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.  The matrix should be "tight", that is, there should be a
//    1 in row 1, and in column 1, and in row M, and in column N.
//
//    Input, string LABEL, a title for the polyomino.
//
{
  int i;
  int j;

  cout << "\n";
  cout << label << "\n";
  cout << "\n";
  if ( m <= 0 || n <= 0 )
  {
    cout << "  [ Null matrix ]\n";
  }
  else
  {
    for ( i = 0; i < m; i++ )
    {
      for ( j = 0; j < n; j++ )
      {
        cout << " " << p[i+j*m];
      }
      cout << "\n";
    }
  }
  return;
}
//****************************************************************************80

void timestamp ( )

//****************************************************************************80
//
//  Purpose:
//
//    TIMESTAMP prints the current YMDHMS date as a time stamp.
//
//  Example:
//
//    31 May 2001 09:45:54 AM
//
//  Licensing:
//
//    This code is distributed under the GNU LGPL license. 
//
//  Modified:
//
//    19 March 2018
//
//  Author:
//
//    John Burkardt
//
//  Parameters:
//
//    None
//
{
# define TIME_SIZE 40

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

  now = std::time ( NULL );
  tm_ptr = std::localtime ( &now );

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

  std::cout << time_buffer << "\n";

  return;
# undef TIME_SIZE
}