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

using namespace std;

# include "polyomino_embed.hpp"

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

int i4mat_sum ( int m, int n, int a[] )

//****************************************************************************80
//
//  Purpose:
//
//    I4MAT_SUM returns the sum of the entries of an I4MAT.
//
//  Discussion:
//
//    An I4MAT is an MxN array of I4's, stored by (I,J) -> [I+J*M].
//
//  Licensing:
//
//    This code is distributed under the GNU LGPL license.
//
//  Modified:
//
//    01 May 2018
//
//  Author:
//
//    John Burkardt
//
//  Parameters:
//
//    Input, int M, the number of rows in A.
//
//    Input, int N, the number of columns in A.
//
//    Input, int A[M*N], the M by N matrix.
//
//    Output, int I4MAT_SUM, the sum of the entries.
//
{
  int i;
  int j;
  int value;

  value = 0;

  for ( j = 0; j < n; j++ )
  {
    for ( i = 0; i < m; i++ )
    {
      value = value + a[i+j*m];
    }
  }
  return value;
}
//****************************************************************************80

int *polyomino_embed_list ( int mr, int nr, int r[], int mp, int np, int p[], 
  int number )

//****************************************************************************80
//
//  Purpose:
//
//    POLYOMINO_EMBED_LIST lists the polyomino embeddings in a region.
//
//  Discusion:
//
//    A region R is a subset of an MRxNR grid of squares.
//
//    A polyomino P is a subset of an MPxNP grid of squares.
//
//    Both objects are represented by binary matrices, with the property that
//    there are no initial or final zero rows or columns.
//
//    For this computation, we regard P as a "fixed" polyomino; in other words,
//    no reflections or rotations will be allowed.
//
//    An "embedding" of P into R is an offset (MI,NJ) such that 
//      P(I,J) = R(I+MI,J+NJ) 
//      for 1 <= I <= MP, 1 <= J <= NP, and 
//      for 0 <= MI <= MR-MP, 0 <= MJ <= NR-NP.
//    We can detect an embedding simply by taking what amounts to a kind of
//    dot product of P with a corresponding subregion of R.
//
//  Licensing:
//
//    This code is distributed under the GNU LGPL license.
//
//  Modified:
//
//    02 May 2018
//
//  Author:
//
//    John Burkardt
//
//  Parameters:
//
//    Input, int MR, NR, the number of rows and columns in the representation
//    of the region R.
//
//    Input, int R(MR,NR), a matrix of 0's and 1's representing the 
//    region.
//
//    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.
//
//    Input, int NUMBER, the number of embeddings.
//
//    Output, int POLYOMINO_EMBED_LIST[NUMBER*2], for each embedding, the I 
//    and J offsets applied to the polyomino P.
//
{
  int i;
  int j;
  int k;
  int *list;
  int mi;
  int nj;
  int pr;
  int srp;

  list = new int [ number * 2 ];
//
//  Count the 1's in P.
//
  pr = i4mat_sum ( mp, np, p );
//
//  For each possible (I,J) coordinate of the upper left corner of a subset of R,
//  see if it matches P.
//
  k = 0;
  for ( mi = 0; mi <= mr - mp; mi++ )
  {
    for ( nj = 0; nj <= nr - np; nj++ )
    {
      srp = 0;
      for ( j = 0; j < np; j++ )
      {
        for ( i = 0; i < mp; i++ )
        {
          srp = srp + p[i+j*mp] * r[i+mi+(j+nj)*mr];
        }
      }
      if ( srp == pr )
      {
        list[k+0*number] = mi;
        list[k+1*number] = nj;
        k = k + 1;
      }
    }
  }

  return list;
}
//****************************************************************************80

int polyomino_embed_number ( int mr, int nr, int r[], int mp, int np, int p[] )

//****************************************************************************80
//
//  Purpose:
//
//    POLYOMINO_EMBED_NUMBER counts the number of polyomino embeddings in a region.
//
//  Discusion:
//
//    A region R is a subset of an MRxNR grid of squares.
//
//    A polyomino P is a subset of an MPxNP grid of squares.
//
//    Both objects are represented by binary matrices, with the property that
//    there are no initial or final zero rows or columns.
//
//    For this computation, we regard P as a "fixed" polyomino; in other words,
//    no reflections or rotations will be allowed.
//
//    An "embedding" of P into R is an offset (MI,NJ) such that 
//      P(I,J) = R(I+MI,J+NJ) 
//      for 1 <= I <= MP, 1 <= J <= NP, and 
//      for 0 <= MI <= MR-MP, 0 <= MJ <= NR-NP.
//    We can detect an embedding simply by taking what amounts to a kind of
//    dot product of P with a corresponding subregion of R.
//
//  Licensing:
//
//    This code is distributed under the GNU LGPL license.
//
//  Modified:
//
//    02 May 2018
//
//  Author:
//
//    John Burkardt
//
//  Parameters:
//
//    Input, int MR, NR, the number of rows and columns in the representation
//    of the region R.
//
//    Input, int R[MR*NR], a matrix of 0's and 1's representing the 
//    region.
//
//    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 POLYOMINO_EMBED_NUMBER, the number of distinct embeddings of 
//    P into R.
//
{
  int i;
  int j;
  int mi;
  int nj;
  int number;
  int pr;
  int srp;

  number = 0;
//
//  Count the 1's in P.
//
  pr = i4mat_sum ( mp, np, p );
//
//  For each possible (I,J) coordinate of the upper left corner of a subset of R,
//  see if it matches P.
//
  for ( mi = 0; mi <= mr - mp; mi++ )
  {
    for ( nj = 0; nj <= nr - np; nj++ )
    {
      srp = 0;
      for ( j = 0; j < np; j++ )
      {
        for ( i = 0; i < mp; i++ )
        {
          srp = srp + p[i+j*mp] * r[i+mi+(j+nj)*mr];
        }
      }
      if ( srp == pr )
      {
        number = number + 1;
      }     
    }
  }

  return number;
}
//****************************************************************************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:
//
//    08 July 2009
//
//  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
}