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


resource RangListeSequentielle()
  import Barriere;

  ##############################################################
  # Types pour listes chainees.
  ##############################################################
  type PtNoeud = ptr Noeud;
  type Noeud = rec(
                    int valeur; 
                    PtNoeud suivant;
                    PtNoeud suivantSaut;
                    int rang;
                  );

  

  ##############################################################
  # Lecture de la taille de la liste a generer.
  ##############################################################
  procedure estPuissanceDeux( int n ) returns bool estPuissance 
  {
    int p = 1;
    estPuissance = true;
    while( p <= n ) {
      if (p == n) { return; }
      p = 2 * p;
    }
    estPuissance = false;
  }

  procedure lg( int n ) returns int leLog 
  {
    if (~estPuissanceDeux(n)) { return; }
    leLog = 0;
    int p = 1;
    while ( p < n ) {
      leLog += 1;
      p *= 2;
    }
  }


  int n; getarg(1, n);
  if (n <= 0 | ~estPuissanceDeux(n) ) {
    write("*** Erreur: n <= 0 & ~estPuissanceDeux(n)" );
    stop(1);
  }

  
  ##############################################################
  # Procedures auxiliaires de traitement des noeuds.
  ##############################################################
  procedure imprimerNoeud( Noeud n ) 
  {
    writes( "(", n.valeur, ", ", n.rang, ") " );
  }

  procedure imprimer( PtNoeud tete )
  {
    if (tete != null) {
      imprimerNoeud( tete^ );
      imprimer( tete^.suivant );
    } else {
      write();
    }
  }

  procedure imprimerTableau( PtNoeud noeuds[*], int n ) 
  {
    for [i = 1 to n-1] {
      imprimerNoeud( noeuds[i]^ );
    }
    imprimerNoeud( noeuds[n]^ );
  }

  procedure permuter( ref PtNoeud noeuds[*], int n )
  {
    for [i = 1 to n/2] {
      int r1 = int(random(n))+1;
      int r2 = int(random(n))+1;
      noeuds[r1] :=: noeuds[r2];
    }
  }
 
  procedure generer( ref PtNoeud noeuds[*], int n ) returns PtNoeud tete
  {
    for [i = 1 to n] {
      noeuds[i] = new(Noeud);
      noeuds[i]^.valeur = 10*i;
      noeuds[i]^.rang = 0;
      if ( i == 1 ) {
        noeuds[i]^.suivant = null;
      } else {      
        noeuds[i]^.suivant = noeuds[i-1];
      }
    }
    tete = noeuds[n];
    permuter( noeuds, n );
  }


  ##############################################################
  # Procedures pour calcul du rang par sauts de pointeurs.
  ##############################################################

  procedure initNoeud( PtNoeud pt )
  {     
    # Initialisation des rangs: initialement tous a 1, 
    # sauf le dernier de la liste.
    if (pt^.suivant == null) {
      pt^.rang = 0; 
    } else {
      pt^.rang = 1; 
    }
    pt^.suivantSaut = pt^.suivant;
  }

  cap Barriere barriere = create Barriere(n);

  procedure sauterPointeur( PtNoeud pt )
  {
    if (pt^.suivantSaut != null) {
      # On commence par lire les donnees.
      int rangSuiv = pt^.suivantSaut^.rang;
      PtNoeud suivSuiv = pt^.suivantSaut^.suivantSaut;

      # On attend que les lectures soient completees.
      barriere.attendre();
  
      # On effectue les mises a jour.
      pt^.rang += rangSuiv;
      pt^.suivantSaut = suivSuiv;
    } else {
      barriere.attendre();
    }
  }

  procedure determinerRang( PtNoeud noeuds[*], int n )
  {
   # On initialise les rangs.
   co [i = 1 to n]
      initNoeud(noeuds[i]);
   oc
    
   # On effectue les sauts de pointeurs.
   for [i = 1 to lg(n)] {
     co [i = 1 to n]
       sauterPointeur(noeuds[i])
     oc
   }
  }

 
  ##############################################################
  # Programme principal.
  ##############################################################

  # Tableau contenant les divers noeuds generes, chaines
  # dans un ordre aleatoire.

  PtNoeud noeuds[n];
  PtNoeud tete = generer( noeuds, n );
 
  write( "Avant: " ); imprimer( tete ); write();

  determinerRang( noeuds, n );

  write( "Apres: " ); imprimer( tete ); write();
end