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


resource ParallelPrefix()
  # Type pour des operateurs binaires.
  optype OpBinaire = (int, int) returns int;
 

  # Les deux operateurs binaires utilises par l'algorithme
  # dans le calcul des prefixes/postfixes paralleles.

  procedure plus2( int x, int y ) returns int r
  { r = x + y; }

  procedure max2( int x, int y ) returns int r
  { r = max(x, y); }


  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 ) 
  {
   a[1] = -3;
   a[2] =  5;
   a[3] =  2;
   a[4] = -1;
   a[5] = -4;
   a[6] =  8;
   a[7] = 10;
   a[8] = -2;
  }

  n = 8;

  # 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 copier( int x, ref int r )
  { r = x; }

  procedure combinerPrefixes( ref int prefixes[*], int k, int dist, cap OpBinaire op0 )
  {
    co [i = k-dist+1 to k]
      prefixes[i] = op0( prefixes[k-dist], prefixes[i] );
    oc
  }

  procedure calculerPrefixes( int x[*], ref int prefixes[*], int n, cap OpBinaire op0 )
  {

    co [i = 1 to n]
      copier( x[i], prefixes[i] );
    oc
    for [i = 1 to lg(n)] {
      int dist = 2**(i-1);
      co [j = 1 to (n/2)/dist]
        combinerPrefixes(prefixes, dist*(2*j), dist, op0)
      oc
    }
  }

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

  procedure trouverMax2( int n1, int n2 ) returns int leMax
  {
    leMax = max( n1, n2 );
  }  

  procedure trouverMax( int X[*], int n ) returns int leMax
  {
    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)] {
      co [j = 1 to n/(2**i)]
        T[j] = trouverMax2( T[2*j-1], T[2*j] );  
      oc
    }
    leMax = T[1];
  }

  procedure inverser( int x[*], var int y[*], int n )
  {
    co [i = 1 to n]
      copier( x[i], y[n-i+1] );
    oc
  }

  procedure calculerPostfixes( int x[*], ref int postfs[*], int n, cap OpBinaire op0 )
  {
    int prefs[n];

    # Pour un operateur binaire commutatif, les postfixes paralleles peuvent
    # etre obtenus en inversant les prefixes paralleles pour la sequence inverse.
    inverser( x, x, n );
    calculerPrefixes( x, prefs, n, op0 );
    inverser( prefs, postfs, n );
  }

  procedure maxPrefixeDroite( int s, int m, int x ) returns int r
  { r = m - s + x;  }

  procedure trouverMaxSomme( int x[*], int n ) returns int s
  {
    int sommes[n];
    int maxs[n];
    int b[n];

    # On calcule les prefixes paralleles des sommes des elements.
    calculerPrefixes ( x,        sommes,  n, plus2 );

    # On calcule les postfixes paralleles des maximum des sommes.
    calculerPostfixes( sommes, maxs, n, max2  );


    # On determine, pour chaque position, le maximum pouvant etre
    # obtenu a partir de cette position.
    co [i = 1 to n]
      b[i] = maxPrefixeDroite( sommes[i], maxs[i], x[i] );
    oc
    s = trouverMax( b, n );
  }


  #
  # Programme principal
  #

  # Generation aleatoire des elements
  int x[n];           # Tableau des valeuurs.
  generer( x, n );
  
  writes( "x      = " ); imprimer( x, n );
  int s = trouverMaxSomme( x, n );

  # Impression des resultats
  write( s );
end