#
# Programme developpe par Guy Tremblay, Professeur au dept. d'informatique
# dans le cadre du cours INF7440.
# (Automne 2002, 2003, 2004)
#


resource MinPRAM()
  # Calcul du minimum des elements d'un tableau a la PRAM avec n/2 processeurs.
  # Premiere version: non optimale.

  procedure estPuissanceDeux( int n ) returns bool estPuissance 
  {
    int p = 1;
    estPuissance = true;
    while( p <= n ) {
      if (p == n) { return; }
      p = 2 * p;
    }
    estPuissance = false;
  }

  # Lecture et verification du nombre d'elements a generer et a traiter
  int n; getarg(1, n); 
  if (n <= 0 | ~estPuissanceDeux(n) ) {
    write("*** Erreur: n <= 0 | ~estPuissanceDeux(n)" );
    stop(1);
  }

  # Generation (aleatoire) des elements du tableau a.
  procedure generer( ref int a[*], int n ) 
  {
    seed(1.0);
    for [i = 1 to n] {
      a[i] = int(random(1, n));
    }
  }

  # Impression des elements d'un tableau.
  procedure imprimer( int a[*], int n ) 
  {
    for [i = 1 to n-1] {
        writes( a[i], ", " );
    }
    write( a[n] );
  }

  procedure lg( int n ) returns int leLog 
  {
    if (~estPuissanceDeux(n)) { return; }

    leLog = 0;
    int p = 1;
    while ( p < n ) {
      leLog += 1;
      p *= 2;
    }
  }

  procedure copier2( ref int T[*], int a[*], int i, int j )
  {
    T[i] = a[i];  T[j] = a[j];
  }

  procedure min2( int n1, int n2 ) returns int leMin
  {
    leMin = min( n1, n2 );
  }  

  procedure trouverMin( int X[*], int n ) returns int leMin
  {
    int T[n]; # Copie du tableau.

    co [i = 1 to n/2] 
      copier2(T, X, i, i+n/2);
    oc
    for [i = 1 to lg(n)] {
      int dist = 2**(i-1);
      co [j = 1 to (n/2)/dist]
        T[dist*2*j] = min2( T[dist*(2*j-1)], T[dist*2*j] );  
      oc
    }
    leMin = T[n];
  }

  #
  # Programme principal
  #

  # Generation aleatoire des elements
  int X[n]; # Tableau a fouiller.
  generer( X, n )

  # Calcul du minimum.
  int m = trouverMin( X, n );

  # Impression des resultats
  imprimer( X, n );
  write( m );
end