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

# include "matrix_chain_dynamic.h"

int main ( );
void i4vec_transpose_print ( int n, int a[], char *title );
void timestamp ( );

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

int main ( )

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

    matrix_chain_dynamic_test() tests matrix_chain_dynamic().

  Licensing:

    This code is distributed under the MIT license.

  Modified:

    23 April 2024

  Author:

    John Burkardt
*/
{
  int cost;
  int *dims;
  int n;

  timestamp ( );
  printf ( "\n" );
  printf ( "matrix_chain_dynamic_test():\n" );
  printf ( "  C version\n" );
  printf ( "  Test matrix_chain_dynamic().\n" );

  n = 4;
  dims = ( int * ) malloc ( ( n + 1 ) * sizeof ( int ) );
  dims[0] = 40;
  dims[1] = 20;
  dims[2] = 30;
  dims[3] = 10;
  dims[4] = 30;
  cost = matrix_chain_dynamic ( n, dims );
  printf ( "\n" );
  printf ( "  n = %d\n", n );
  i4vec_transpose_print ( n + 1, dims, "  dims():" );
  printf ( "  minimum cost = %d\n", cost );
  printf ( "  Number of orderings = %d\n", catalan_number ( n - 1 ) );
  free ( dims );

  n = 4;
  dims = ( int * ) malloc ( ( n + 1 ) * sizeof ( int ) );
  dims[0] = 1;
  dims[1] = 2;
  dims[2] = 3;
  dims[3] = 4;
  dims[4] = 3;
  cost = matrix_chain_dynamic ( n, dims );
  printf ( "\n" );
  printf ( "  n = %d\n", n );
  i4vec_transpose_print ( n + 1, dims, "  dims():" );
  printf ( "  minimum cost = %d\n", cost );
  printf ( "  Number of orderings = %d\n", catalan_number ( n - 1 ) );
  free ( dims );

  n = 2;
  dims = ( int * ) malloc ( ( n + 1 ) * sizeof ( int ) );
  dims[0] = 10;
  dims[1] = 20;
  dims[2] = 30;
  cost = matrix_chain_dynamic ( n, dims );
  printf ( "\n" );
  printf ( "  n = %d\n", n );
  i4vec_transpose_print ( n + 1, dims, "  dims():" );
  printf ( "  minimum cost = %d\n", cost );
  printf ( "  Number of orderings = %d\n", catalan_number ( n - 1 ) );
  free ( dims );

  n = 3;
  dims = ( int * ) malloc ( ( n + 1 ) * sizeof ( int ) );
  dims[0] = 10;
  dims[1] = 30;
  dims[2] = 5;
  dims[3] = 60;
  cost = matrix_chain_dynamic ( n, dims );
  printf ( "\n" );
  printf ( "  n = %d\n", n );
  i4vec_transpose_print ( n + 1, dims, "  dims():" );
  printf ( "  minimum cost = %d\n", cost );
  printf ( "  Number of orderings = %d\n", catalan_number ( n - 1 ) );
  free ( dims );

  n = 1;
  dims = ( int * ) malloc ( ( n + 1 ) * sizeof ( int ) );
  dims[0] = 10;
  dims[1] = 20;
  cost = matrix_chain_dynamic ( n, dims );
  printf ( "\n" );
  printf ( "  n = %d\n", n );
  i4vec_transpose_print ( n + 1, dims, "  dims():" );
  printf ( "  minimum cost = %d\n", cost );
  printf ( "  Number of orderings = %d\n", catalan_number ( n - 1 ) );
  free ( dims );

  n = 0;
  dims = ( int * ) malloc ( ( n + 1 ) * sizeof ( int ) );
  dims[0] = 40;
  cost = matrix_chain_dynamic ( n, dims );
  printf ( "\n" );
  printf ( "  n = %d\n", n );
  i4vec_transpose_print ( n + 1, dims, "  dims():" );
  printf ( "  minimum cost = %d\n", cost );
  printf ( "  Number of orderings = %d\n", catalan_number ( n - 1 ) );
  free ( dims );
/*
  Terminate.
*/
  printf ( "\n" );
  printf ( "matrix_chain_dynamic_test():\n" );
  printf ( "  Normal end of execution.\n" );
  printf ( "\n" );
  timestamp ( );

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

void i4vec_transpose_print ( int n, int a[], char *title )

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

    i4vec_transpose_print() prints an I4VEC "transposed".

  Discussion:

    An I4VEC is a vector of I4's.

  Example:

    A = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 }
    TITLE = "My vector:  "

    My vector:      1    2    3    4    5
                    6    7    8    9   10
                   11

  Licensing:

    This code is distributed under the MIT license.

  Modified:

    02 June 2015

  Author:

    John Burkardt

  Input:

    int N, the number of components of the vector.

    int A[N], the vector to be printed.

    char *TITLE, a title.
*/
{
  int i;
  int ihi;
  int ilo;
  int title_len;

  title_len = strlen ( title );
  if ( 0 < title_len )
  {
    printf ( "\n" );
    printf ( "%s\n", title );
  }

  if ( 0 < n )
  {
    for ( ilo = 1; ilo <= n; ilo = ilo + 5 )
    {
      ihi = ilo + 5 - 1;
      if ( n < ihi )
      {
        ihi = n;
      }
      for ( i = ilo; i <= ihi; i++ )
      {
        printf ( "%12d", a[i-1] );
      }
      printf ( "\n" );
    }
  }
  else
  {
    printf ( "  (empty vector)\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 MIT license. 

  Modified:

    01 May 2021

  Author:

    John Burkardt
*/
{
# 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
}