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

using namespace std;

# include "matrix_chain_dynamic.hpp"

int main ( );
void i4vec_transpose_print ( int n, int a[], string 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 ( );
  cout << "\n";
  cout << "matrix_chain_dynamic_test():\n";
  cout << "  C++ version\n";
  cout << "  Test matrix_chain_dynamic().\n";

  n = 4;
  dims = new int[n+1];
  dims[0] = 40;
  dims[1] = 20;
  dims[2] = 30;
  dims[3] = 10;
  dims[4] = 30;
  cost = matrix_chain_dynamic ( n, dims );
  cout << "\n";
  cout << "  n = " << n << "\n";
  i4vec_transpose_print ( n + 1, dims, "  dims():" );
  cout << "  minimal cost = " << cost << "\n";
  cout << "  Number of possible orderings = " << catalan_number ( n - 1 ) << "\n";
  delete [] dims;

  n = 4;
  dims = new int[n+1];
  dims[0] = 1;
  dims[1] = 2;
  dims[2] = 3;
  dims[3] = 4;
  dims[4] = 3;
  cost = matrix_chain_dynamic ( n, dims );
  cout << "\n";
  cout << "  n = " << n << "\n";
  i4vec_transpose_print ( n + 1, dims, "  dims():" );
  cout << "  minimal cost = " << cost << "\n";
  cout << "  Number of possible orderings = " << catalan_number ( n - 1 ) << "\n";
  delete [] dims;

  n = 2;
  dims = new int[n+1];
  dims[0] = 10;
  dims[1] = 20;
  dims[2] = 30;
  cost = matrix_chain_dynamic ( n, dims );
  cout << "\n";
  cout << "  n = " << n << "\n";
  i4vec_transpose_print ( n + 1, dims, "  dims():" );
  cout << "  minimal cost = " << cost << "\n";
  cout << "  Number of possible orderings = " << catalan_number ( n - 1 ) << "\n";
  delete [] dims;

  n = 3;
  dims = new int[n+1];
  dims[0] = 10;
  dims[1] = 30;
  dims[2] = 5;
  dims[3] = 60;
  cost = matrix_chain_dynamic ( n, dims );
  cout << "\n";
  cout << "  n = " << n << "\n";
  i4vec_transpose_print ( n + 1, dims, "  dims():" );
  cout << "  minimal cost = " << cost << "\n";
  cout << "  Number of possible orderings = " << catalan_number ( n - 1 ) << "\n";
  delete [] dims;

  n = 1;
  dims = new int[n+1];
  dims[0] = 10;
  dims[1] = 20;
  cost = matrix_chain_dynamic ( n, dims );
  cout << "\n";
  cout << "  n = " << n << "\n";
  i4vec_transpose_print ( n + 1, dims, "  dims():" );
  cout << "  minimal cost = " << cost << "\n";
  cout << "  Number of possible orderings = " << catalan_number ( n - 1 ) << "\n";
  delete [] dims;

  n = 0;
  dims = new int[n+1];
  dims[0] = 40;
  cost = matrix_chain_dynamic ( n, dims );
  cout << "\n";
  cout << "  n = " << n << "\n";
  i4vec_transpose_print ( n + 1, dims, "  dims():" );
  cout << "  minimal cost = " << cost << "\n";
  cout << "  Number of possible orderings = " << catalan_number ( n - 1 ) << "\n";
  delete [] dims;
//
//  Terminate.
//
  cout << "\n";
  cout << "matrix_chain_dynamic_test():\n";
  cout << "  Normal end of execution.\n";
  cout << "\n";
  timestamp ( );

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

void i4vec_transpose_print ( int n, int a[], string title )

//****************************************************************************80
//
//  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:
//
//    03 July 2004
//
//  Author:
//
//    John Burkardt
//
//  Input:
//
//    int N, the number of components of the vector.
//
//    int A[N], the vector to be printed.
//
//    string TITLE, a title.
//
{
  int i;
  int ihi;
  int ilo;
  int title_len;

  title_len = title.length ( );

  if ( 0 < title_len )
  {
    cout << "\n";
    cout << title << "\n";
  }

  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++ )
      {
        cout << setw(12) << a[i-1];
      }
      cout << "\n";
    }
  }
  else
  {
    cout << "  (empty vector)\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 MIT license. 
//
//  Modified:
//
//    19 March 2018
//
//  Author:
//
//    John Burkardt
//
{
# 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
}