#
# Programme developpe par Guy Tremblay, Professeur au dept. d'informatique de l'UQAM,
# dans le cadre du cours INF5170 (2006, 2008).
#
# Tous droits reserves.
#


resource labo1()

  # Fonction pour determiner si n est une puissance de b.
  procedure estPuissance( int n, int b ) returns bool r
  {
    int p = 1;
    r = true;
    while( p <= n ) {
      if (p == n) { return; }
      p *= b;
    }
    r = false;
  }

  # Procedure pour generer aleatoirement un tableau d'entiers.
  procedure generer( ref int A[*], int n ) {
    for [i = 1 to n] {
      A[i] = int(random(1, n));
    }
  }

  # Procedure pour imprimer un tableau d'entiers.
  procedure imprimer( int A[*], int n ) {
    writes( "( " );
    for [i = 1 to n-1] { 
     writes( A[i], ", " ); 
    }
    write( A[n], ")" );
  }


  #
  # Fonctions pour calculer le nombre d'inversions.
  #
  procedure nbInversionsIt( ref int A[*], int i, int j ) returns int nb
  { 
    nb = 0;
    for [k = i to j-1] {
      nb += int(A[k] > A[k+1]);
    }
  }

  procedure nbInversions( ref int A[*], int i, int j ) returns int nb
  # PRECONDITION
  #   n est une puissance de 3
  { 
    if (i == j) {
      nb = 0;
    } else {
      int n = j - i + 1;
      int i2 = i + n / 3;
      int i3 = i + 2 * n / 3
      int nb1, nb2, nb3;
      co
         nb1 = nbInversions( A, i, i2-1 )
      // nb2 = nbInversions( A, i2, i3-1 )
      // nb3 = nbInversions( A, i3, j )
      oc
      nb = nb1 + nb2 + nb3 + int(A[i2-1] > A[i2]) + int(A[i3-1] > A[i3]);
    }
  }

  procedure nbInversionsSeuil( ref int A[*], int i, int j, int seuil ) returns int nb
  { 
    if ( (j-i+1) <= seuil) {
      nb = nbInversionsIt( A, i, j );
    } else {
      int n = j - i + 1;
      int i2 = i + n / 3;
      int i3 = i + 2 * n / 3
      int nb1, nb2, nb3;
      co
         nb1 = nbInversionsSeuil( A, i, i2-1, seuil );
      // nb2 = nbInversionsSeuil( A, i2, i3-1, seuil )
      // nb3 = nbInversionsSeuil( A, i3, j, seuil )
      oc
      nb = nb1 + nb2 + nb3 + int(A[i2-1] > A[i2]) + int(A[i3-1] > A[i3]);
    }
  }


  #
  # Programme principal.
  #
  
  # On verifie le nombre d'arguments du programme.
  if (numargs() < 2) {
    write( "Usage:" );
    write( "   a.out n seuil" );
    stop;
  }


  # On obtient et on verifie ces arguments.
  int n; getarg(1, n);
  if ( n <= 0 | ~estPuissance(n, 3) ) {
    write( "*** Erreur: n doit etre une puissance de 3 et doit etre positif" );
    stop;
  }
  int seuil; getarg(2, seuil);


  # On genere le tableau de nombres.
  int A[n];
  generer(A, n);     # Generation aleatoire des elements


  # On appelle les differentes fonctions.
  int t1 = age();
  int nbIt = nbInversionsIt( A, 1, n )
  t1 = age() - t1;

  int t2 = age();
  int nbRec = nbInversions  ( A, 1, n )
  t2 = age() - t2;

  int t3 = age();
  int nbRecSeuil = nbInversionsSeuil( A, 1, n, seuil );
  t3 = age() - t3;


  # On imprime les resultats
  #imprimer( A, n );
  write();

  write( nbIt );
  write( nbRec );
  write( nbRecSeuil );
  write();

  if ( nbIt == nbRec ) {
     write( "OK" );
  } else {
     write( "Pas OK" );
  }

  if ( nbIt == nbRecSeuil ) {
     write( "OK" );
  } else {
     write( "Pas OK" );
  }
  
  write();
  write( "Temps:" )
  write( "  Iteratif              = ", t1 );
  write( "  Recursif              = ", t2 );
  write( "  Recursif avec seuil   = ", t3 );
end