/* FILE: multMatrix.cpp   last change: 19-Mar-2001   author: Romeo Rizzi
 * This program reads a sequence s_0, s-1, .... n_n  of n+1 integers
 * representing the dimensionalities of a sequence of n matrices
 * A_1, ..., A_n to be multiplied,
 * The sequence s is put into a static array,
 * whose dimension is at most MAX_N_MATRICES+1.
 * An optimal parentesization is computed based on a dynamic programming approach.
 */


const long int  MAX_N_MATRICES = 1000;


#include <fstream.h>
#include <iostream.h>
#include <limits.h>
#include <strstream>
#include <string>
#include <sys/times.h>
#include <unistd.h>

const int time_fact = (int) sysconf(_SC_CLK_TCK);
      // _SC_CLK_TCK gives the number of tics per second


template <class genType>
string toString(genType n)
{
  strstream ss;
  ss << n;
  return ss.str();
}


int Ricorsiva(int *, int, int, string&);

int Ricorsiva(int *s, int from, int to, string& descr_ottimo) {
  // finds an optimal parenthesization for the product of the subchain
  // A_from * A_{from+1} * ... * A_to

  if (to == from) {
    descr_ottimo = string();
    descr_ottimo += "A";
    descr_ottimo += toString(from);
    return 0;
  }

  int min = INT_MAX;

  string tmp_descr1;
  string tmp_descr2;

  for(int i = from; i < to; i++) {
    int tmp = s[from-1]*s[i]*s[to] +
              Ricorsiva (s, from, i, tmp_descr1) +
	      Ricorsiva (s, i+1, to, tmp_descr2);
    if(tmp < min) {
      min = tmp;
      descr_ottimo = string();
      descr_ottimo += "(";
      descr_ottimo += tmp_descr1;
      descr_ottimo += ")(";
      descr_ottimo += tmp_descr2;
      descr_ottimo += ")";
    }
  }

  return min;
}


int RicMemoized(int *, int, int, int** cost, int** track);

int RicMemoized(int *s, int from, int to, int** cost, int** track) {
  // finds an optimal parenthesization for the product of the subchain
  // A_from * A_{from+1} * ... * A_to

  if(cost[from][to] < INT_MAX) return cost[from][to];

  for(int i = from; i < to; i++) {
    int tmp = s[from-1]*s[i]*s[to] + RicMemoized (s, from, i, cost, track);
    if(tmp < cost[from][to]) {
      tmp += RicMemoized (s, i+1, to, cost, track);
      if(tmp < cost[from][to]) {
        cost[from][to] = tmp;
        track[from][to] = i+1;
      }
    }
  }

  return cost[from][to];
}



// inizializzazione delle tabelle

void Initialize(int** & cost, int** & track, int n) {
  track = new int*[n+1];
  cost = new int*[n+1];
  for(int i=0; i <= n; i++) {
    track[i] = new int[n+1];
    cost[i] = new int[n+1];
    cost[i][i] = 0; // il costo di ottenere le matrici gia' date in input e' nullo
    for(int j = i+1; j <= n; j++)
      cost[i][j] = INT_MAX;   // INT_MAX rappresenta un costo infinito

  }
}


// rilascio della memoria per tabelle

void Release(int** & cost, int** & track, int n) {
  for(int i=0; i <= n; i++) {
    delete [] track[i];
    delete [] cost[i];

  }
  delete [] track;
  delete [] cost;
}


// manipolazione dinamica della tabella dei costi

void optMatrix(const int * s, int n, int** cost, int** track) {
  for(int j = 1; j < n; j++ )
    for(int i = 1; i <= n - j; i++ )
      for(int k = i+1; k <= i+j; k++ ) {
        long temp = cost[i][k-1] + cost[k][i+j] + s[i-1] * s[k-1] * s[i+j];
        if( temp < cost[ i ][ i+j ] ) {
          cost[i][i+j] = temp;
          track[i][i+j] = k;
        }
      }
}




// ricostruzione di una parentesizzazione ottima

void readTrack(int i, int j, int** track) {
  if (i == j)
    cout << "(A" << i << ")";
  else {
    cout << "(";
    readTrack (i, track[i][j]-1, track);
    readTrack(track[i][j], j, track);
    cout << ")";
  }
}


main(int argc, char** argv) {
  if (argc != 2) {
     cerr << "syntax:" << endl
          << " > multMatrix <file>" << endl
          << "where, <file> = input file containing a sequence of integers" << endl;
     exit(1);
  }

  ifstream  in;
  in.open(argv[1]);
  if (!in.good()) {
     cerr << "err: file " << argv[1] << " does not exist" << endl;
     exit(1);
  }

  int s[MAX_N_MATRICES+1];
  int n = 0;  // n is the number of matrices;
  while (!in.eof()) {
     if (n > MAX_N_MATRICES) {
        cerr << "err: file " << argv[1] << " contains more than "
             << MAX_N_MATRICES+1 << " integers." << endl;
        exit(1);
     }
     in >> s[n++];
  }
  in.close(); n -= 2;  // n is the number of matrices;

  struct tms ttmmss;
  int startingTime;

  int **cost, **track;

  // BEGIN: Parte ora la programmazione dinamica:
     times(&ttmmss); startingTime = (int) ttmmss.tms_utime;

  Initialize(cost, track, n);
  optMatrix(s, n, cost, track);

     times(&ttmmss);
     double tot_cpu = (ttmmss.tms_utime - startingTime) / (double)time_fact;

  // La programmazione dinamica ha trovato il costo dell'ottimo

  cout << "Costo ottimo: " << cost[1][n] << endl
       << "Tempo di CPU impiegato: " << tot_cpu << endl;
  cout << "Soluzione di costo ottimo: " << endl;
  readTrack(1, n, track);
  Release(cost, track, n);
     times(&ttmmss);
     tot_cpu = (ttmmss.tms_utime - startingTime) / (double)time_fact;
     cout << endl << "Tempo totale di CPU impiegato dalla Programmazione Dinamica: "
          << tot_cpu << endl << endl;

  // END: la programmazione dinamica ha concluso.

  if (n <= 13) {
  // BEGIN: Parte ora, se n <= 13, la soluzione ricorsiva:
     times(&ttmmss); startingTime = (int) ttmmss.tms_utime;

    string soluzione;
    cout << "Costo ottimo: " << Ricorsiva (s, 1, n, soluzione) << endl;
    cout << "Soluzione di costo ottimo: " << endl << soluzione << endl;
       times(&ttmmss);
       tot_cpu = (ttmmss.tms_utime - startingTime) / (double)time_fact;
       cout << endl << "Tempo totale di CPU impiegato dalla soluzione ricorsiva: "
            << tot_cpu << endl << endl;

  // END: la procedura ricorsiva ha concluso.
  }

  // BEGIN: Parte ora la soluzione ricorsiva con memoizzazione:
     times(&ttmmss); startingTime = (int) ttmmss.tms_utime;

  Initialize(cost, track, n);
  cout << "Costo ottimo: " << RicMemoized (s, 1, n, cost, track) << endl;
  cout << "Soluzione di costo ottimo: " << endl;
  readTrack(1, n, track);
  Release(cost, track, n);
     times(&ttmmss);
     tot_cpu = (ttmmss.tms_utime - startingTime) / (double)time_fact;
     cout << endl
          << "Tempo totale di CPU impiegato dalla soluzione ricorsiva con memoizzazione: "
          << tot_cpu << endl << endl;
  // END: la procedura ricorsiva con memoizzazione ha concluso.
}