# include <limits.h>
# include <stdbool.h>
# include <stdlib.h>

# include "matrix_chain_dynamic.h"

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

int catalan_number ( int n )

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

    catalan_number() computes the N-th Catalan number.

  First values:

     C(0)     1
     C(1)     1
     C(2)     2
     C(3)     5
     C(4)    14
     C(5)    42
     C(6)   132
     C(7)   429
     C(8)  1430
     C(9)  4862
    C(10) 16796

  Licensing:

    This code is distributed under the MIT license. 

  Modified:

    23 April 2024

  Author:

    John Burkardt

  Input:

    int N, the index of the Catalan number.

  Output:

    int C: the value of the Catalan number.
*/
{
  int c;
  int i;

  if ( n < 0 )
  {
    return 0;
  }

  c = 1;
/*
  The extra parentheses ensure that the integer division is
  done AFTER the integer multiplication.
*/
  for ( i = 1; i <= n; i++ )
  {
    c = ( c * 2 * ( 2 * i - 1 ) ) / ( i + 1 );
  }

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

bool i4vec_is_nonpositive_any ( int n, int a[] )

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

    i4vec_is_nonpositive_any(): ( any ( A <= 0 ) ).

  Discussion:

    An I4VEC is a vector of I4's.

  Licensing:

    This code is distributed under the MIT license.

  Modified:

    01 January 2023

  Author:

    John Burkardt

  Input:

    int n: the number of entries.

    int a[n]: the vector to check.

  Output:

    bool i4vec_is_nonpositive_any: true if ANY entry is nonpositive.
*/
{
  int i;
  bool value;

  value = false;

  for ( i = 0; i < n; i++ )
  {
    if ( a[i] <= 0 )
    {
      value = true;
      break;
    }
  }

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

int matrix_chain_dynamic ( int n, int dims[] )

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

    matrix_chain_dynamic() finds the lowest cost to form a multiple matrix product.

  Discussion:

    This code represents a dynamic programming approach from 
    a Wikipedia article.

  Licensing:

    This code is distributed under the MIT license.

  Modified:

    31 December 2023

  Author:

    John Burkardt

  Reference:

    Thomas Cormen, Charles Leiserson, Ronald Rivest, Clifford Stein,
    Introduction to Algorithms,
    MIT Press, 2001,
    ISBN: 978-0-262-03293-3,
    LC: QA76.C662.

  Input:

    integer n: the number of matrices in the product.

    integer dims(n+1): matrix dimension information.  Matrix A(i)
    has dimensions dims(i) x dims(i+1).  All entries must be positive.

  Output:

    int matrix_chain_dynamic: the minimal cost, in terms of scalar
    multiplications, for the optimal ordering of the matrix multiplications.
*/
{
  int cost;
  int i;
  int j;
  int k;
  int l;
  int *m;
  int *s;

  cost = 0;
/*
  N is the number of matrices in the product.
*/
  if ( n < 2 )
  {
    return cost;
  }

  if ( i4vec_is_nonpositive_any ( n, dims ) )
  {
    return cost;
  }
/*
  m[i,j] = Minimum number of scalar multiplications (i.e., cost)
  needed to compute the matrix A[i]A[i+1]...A[j] = A[i..j]
  The cost is zero when multiplying one matrix.

  K is the index of the subsequence split that achieved minimal cost
*/
  m = ( int * ) malloc ( n * n * sizeof ( int ) );
  s = ( int * ) malloc ( n * n * sizeof ( int ) );

  for ( i = 0; i < n; i++ )
  {
    for ( j = 0; j < n; j++ )
    {
      if ( i == j )
      {
        m[i+j*n] = 0;
      }
      else
      {
        m[i+j*n] = INT_MAX;
      }
    }
  }

  for ( l = 2; l <= n; l++ )
  {
    for ( i = 1; i <= n + 1 - l; i++ )
    {
      j = i - 1 + l;
      for ( k = i; k <= j - 1; k++ )
      {
        cost = m[i-1+(k-1)*n] + m[k+(j-1)*n] + dims[i-1] * dims[k] * dims[j];
        if ( cost <= m[i-1+(j-1)*n] )
        {
          m[i-1+(j-1)*n] = cost;
          s[i-1+(j-1)*n] = k - 1;
        }
      }
    }
  }

  free ( m );
  free ( s );

  return cost;
}