# include <cmath>
# include <cstdlib>
# include <cstring>
# include <fstream>
# include <iomanip>
# include <iostream>

using namespace std;

# include "components.hpp"

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

int components_1d ( int n, int a[], int c[] )

//****************************************************************************80
//
//  Purpose:
//
//    components_1d() assigns contiguous nonzero pixels to a common component.
//
//  Discussion:
//
//    This calculation is trivial compared to the 2D problem, and is included
//    primarily for comparison.
//
//    On input, the A array contains values of 0 or 1.
//
//    The 0 pixels are to be ignored.  The 1 pixels are to be grouped
//    into connected components.
//
//    The pixel A(I) is "connected" to the pixels A(I-1) and A(I+1).
//
//    On output, COMPONENT_NUM reports the number of components of nonzero
//    data, and the array C contains the component assignment for
//    each nonzero pixel, and is 0 for zero pixels.
//
//  Picture:
//
//    Input A:
//
//      0 0 1 2 4 0 0 4 0 0 0 8 9 9 1 2 3 0 0 5 0 1 6 0 0 0 4 0
//
//    Output:
//
//      COMPONENT_NUM = 6
//
//      C:
//
//      0 0 1 1 1 0 0 2 0 0 0 3 3 3 3 3 3 0 0 4 0 5 5 0 0 0 6 0
//
//  Licensing:
//
//    This code is distributed under the MIT license.
//
//  Modified:
//
//    01 March 2011
//
//  Author:
//
//    John Burkardt
//
//  Parameters:
//
//    Input, int N, the order of the vector.
//
//    Input, int A(N), the pixel array.
//
//    Output, int C[N], the component array.
//
//    Output, int components_1d, the number of components
//    of nonzero data.
//
{
  int component_num;
  int j;
  int west;
//
//  Initialization.
//
  for ( j = 0; j < n; j++ )
  {
    c[j] = 0;
  }
  component_num = 0;
//
//  "Read" the array one pixel at a time.  If a (nonzero) pixel has a west
//  neighbor with a label, the current pixel inherits it.  Otherwise, we have
//  begun a new component.
//
  west = 0;

  for ( j = 0; j < n; j++ )
  {
    if ( a[j] != 0 )
    {
      if ( west == 0 )
      {
        component_num = component_num + 1;
      }
      c[j] = component_num;
    }
    west = c[j];
  }

  return component_num;
}
//****************************************************************************80

int components_2d ( int m, int n, int A[], int C[] )

//****************************************************************************80
//
//  Purpose:
//
//    components_2d() assigns contiguous nonzero pixels to a common component.
//
//  Discussion:
//
//    This code replaces a previous version which was defective,
//    -09 March 2025.
//
//    On input, the A array contains values of 0 or 1.
//
//    The 0 pixels are to be ignored.  The 1 pixels are to be grouped
//    into connected components.
//
//    The pixel A(I,J) is "connected" to the pixels A(I-1,J), A(I+1,J),
//    A(I,J-1) and A(I,J+1), so most pixels have 4 neighbors.
//
//    (Another choice would be to assume that a pixel was connected
//    to the other 8 pixels in the 3x3 block containing it.)
//
//    On output, COMPONENT_NUM reports the number of components of nonzero
//    data, and the array C contains the component assignment for
//    each nonzero pixel, and is 0 for zero pixels.
//
//  Picture:
//
//    Input A:
//
//      0  2  0  0 17  0  3
//      0  0  3  0  1  0  4
//      1  0  4  8  8  0  7
//      3  0  6 45  0  0  0
//      3 17  0  5  9  2  5
//
//    Output:
//
//      COMPONENT_NUM = 4
//
//      C:
//
//      0  1  0  0  2  0  3
//      0  0  2  0  2  0  3
//      4  0  2  2  2  0  3
//      4  0  2  2  0  0  0
//      4  4  0  2  2  2  2
//
//  Licensing:
//
//    This code is distributed under the MIT license.
//
//  Modified:
//
//    09 March 2025
//
//  Author:
//
//    John Burkardt
//
//  Input:
//
//    int m, n: the order of the array.
//
//    int A[m*n]: the pixel array.
//
//  Output:
//
//    int C[n*m]: the component array.
//
//    int components_2d: the number of components of nonzero data.
//
{
  int component_num;
  int i;
  int i2;
  int *i_list;
  int j;
  int j2;
  int *j_list;
  int list_num;
//
//  Initialization.
//
  for ( j = 0; j < n; j++ )
  {
    for ( i = 0; i < m; i++ )
    {
      C[i+j*m] = 0;
    }
  }
  component_num = 0;
  list_num = 0;
  i_list = new int[m*n];
  j_list = new int[m*n];
//
//  Find each cell that is nonzero, and has not joined a component yet.
//
  for ( i2 = 0; i2 < m; i2++ )
  {
    for ( j2 = 0; j2 < n; j2++ )
    {
      if ( A[i2+j2*m] != 0 && C[i2+j2*m] == 0 )
      {
        i_list[list_num] = i2;
        j_list[list_num] = j2;
        list_num = list_num + 1;
        component_num = component_num + 1;
//
//  One by one, pop neighbors off the stack.
//
        while ( 0 < list_num )
        {
          list_num = list_num - 1;
          i = i_list[list_num];
          j = j_list[list_num];

          C[i+j*m] = component_num;

          if ( 0 <= i-1 && A[i-1+j*m] != 0 && C[i-1+j*m] == 0 )
          {
            i_list[list_num] = i - 1;
            j_list[list_num] = j;
            list_num = list_num + 1;
          }
          if ( i+1 <= m-1 && A[i+1+j*m] != 0 && C[i+1+j*m] == 0 )
          {
            i_list[list_num] = i + 1;
            j_list[list_num] = j;
            list_num = list_num + 1;
          }
          if ( 0 <= j - 1 && A[i+(j-1)*m] != 0 && C[i+(j-1)*m] == 0 )
          {
            i_list[list_num] = i;
            j_list[list_num] = j - 1;
            list_num = list_num + 1;
          }
          if ( j+1 <= n-1 && A[i+(j+1)*m] != 0 && C[i+(j+1)*m] == 0 )
          {
            i_list[list_num] = i;
            j_list[list_num] = j + 1;
            list_num = list_num + 1;
          }

        }

      }

    }
  }

  delete [] i_list;
  delete [] j_list;

  return component_num;
}
//****************************************************************************80

int components_3d ( int l, int m, int n, int A[], int C[] )

//****************************************************************************80
//
//  Purpose:
//
//    components_3d() assigns contiguous nonzero pixels to a common component.
//
//  Discussion:
//
//    On input, the A array contains values of 0 or 1.
//
//    The 0 pixels are to be ignored.  The 1 pixels are to be grouped
//    into connected components.
//
//    The pixel A(I,J,K) is "connected" to the pixels:
//
//      A(I-1,J,  K  ),  A(I+1,J,  K  ),
//      A(I,  J-1,K  ),  A(I,  J+1,K  ),
//      A(I,  J,  K-1),  A(I,  J,  K+1),
//
//    so most pixels have 6 neighbors.
//
//    On output, COMPONENT_NUM reports the number of components of nonzero
//    data, and the array C contains the component assignment for
//    each nonzero pixel, and is 0 for zero pixels.
//
//  Licensing:
//
//    This code is distributed under the MIT license.
//
//  Modified:
//
//    13 March 2025
//
//  Author:
//
//    John Burkardt
//
//  Input:
//
//    int L, M, N, the order of the array.
//
//    int A[L*M*N], the pixel array.
//
//  Output:
//
//    int C[L*M*N], the component array.
//
//    int components_3d, the number of components of nonzero data.
//
{
  int component_num;
  int i;
  int i2;
  int *i_list;
  int j;
  int j2;
  int *j_list;
  int k;
  int k2;
  int *k_list;
  int list_num;
//
//  Initialization.
//
  for ( i = 0; i < l; i++ )
  {
    for ( j = 0; j < m; j++ )
    {
      for ( k = 0; k < n; k++ )
      {
        C[i+j*l+k*l*m] = 0;
      }
    }
  }
  component_num = 0;
  list_num = 0;
  i_list = new int[l*m*n];
  j_list = new int[l*m*n];
  k_list = new int[l*m*n];
//
//  Find each cell that is nonzero, and has not joined a component yet.
//
  for ( i2 = 0; i2 < l; i2++ )
  {
    for ( j2 = 0; j2 < m; j2++ )
    {
      for ( k2 = 0; k2 < n; k2++ )
      {
        if ( A[i2+j2*l+k2*l*m] != 0 && C[i2+j2*l+k2*l*m] == 0 )
        {
          i_list[list_num] = i2;
          j_list[list_num] = j2;
          k_list[list_num] = k2;
          list_num = list_num + 1;
          component_num = component_num + 1;
//
//  One by one, pop neighbors off the stack.
//
          while ( 0 < list_num )
          {
            list_num = list_num - 1;
            i = i_list[list_num];
            j = j_list[list_num];
            k = k_list[list_num];

            C[i+j*l+k*l*m] = component_num;

            if ( 0 <= i-1 && A[i-1+j*l+k*l*m] != 0 && C[i-1+j*l+k*l*m] == 0 )
            {
              i_list[list_num] = i - 1;
              j_list[list_num] = j;
              k_list[list_num] = k;
              list_num = list_num + 1;
            }
            if ( i+1 <= l-1 && A[i+1+j*l+k*l*m] != 0 && C[i+1+j*l+k*l*m] == 0 )
            {
              i_list[list_num] = i + 1;
              j_list[list_num] = j;
              k_list[list_num] = k;
              list_num = list_num + 1;
            }
            if ( 0 <= j - 1 && A[i+(j-1)*l+k*l*m] != 0 && C[i+(j-1)*l+k*l*m] == 0 )
            {
              i_list[list_num] = i;
              j_list[list_num] = j - 1;
              k_list[list_num] = k;
              list_num = list_num + 1;
            }
            if ( j+1 <= m-1 && A[i+(j+1)*l+k*l*m] != 0 && C[i+(j+1)*l+k*l*m] == 0 )
            {
              i_list[list_num] = i;
              j_list[list_num] = j + 1;
              k_list[list_num] = k;
              list_num = list_num + 1;
            }

            if ( 0 <= k - 1 && A[i+j*l+(k-1)*l*m] != 0 && C[i+j*l+(k-1)*l*m] == 0 )
            {
              i_list[list_num] = i;
              j_list[list_num] = j;
              k_list[list_num] = k - 1;
              list_num = list_num + 1;
            }
            if ( k+1 <= n-1 && A[i+j*l+(k+1)*l*m] != 0 && C[i+j*l+(k+1)*l*m] == 0 )
            {
              i_list[list_num] = i;
              j_list[list_num] = j;
              k_list[list_num] = k + 1;
              list_num = list_num + 1;
            }
          }
        }
      }
    }
  }

  delete [] i_list;
  delete [] j_list;
  delete [] k_list;

  return component_num;
}