TD 5 : Types à champs nommés
Réseaux de Pétri
A quoi ça sert ?
Les réseaux de Petri sont un formalisme mathématique qui permet de spécifier des programme où plusieurs tâches s'exécutent en parallèle, ces tâches devant parfois accéder à des resources chacunes à leur tour. On s'en sert pour spécifier des protocoles de communication... mais l'idée ici est simplement de jouer avec ce formalisme, sur des cas scolaires, à titre d'exercice de programmation.
Définition
Un réseau de Pétri est un ensemble d'éléments reliés entre eux. Ces éléments sont de deux natures. Premièrement, le réseau contient des pools de jetons (tokens). Il s'agit de simple boîtes dans lesquelles on peut ajouter ou enlever des jetons. Deuxièmement, le réseau contient des transitions. Les transitions mettent les pools en relation via des connexions. Plus précisément, une transition a vocation à prendre des jetons dans certains pools (les pools input) et à ajouter des jetons dans d'autres (les pools output). Pour chaque pool input d'une transition, le nombre de jetons à prendre, pour cette transition, est fixé lors de la conception du réseau. De même, pour les pools output, le nombre de jetons déposés par la transition est fixé lors de la conception du réseau. Une transition est activable si, pour tous ses pools input, il y a plus de jetons que le nombre à prendre par la transition. Activer une transition activable revient à prélever le nombre de jetons requis dans chaque pool input (il y en a assez donc, puisque la transition est activable), et à ajouter dans chaque pool output le nombre de jetons défini pour cette transition.
Le déroulement de la vie d'un réseau de Petri est alors le suivant.
Exemple des feux rouges
Un feu rouge peut se modéliser par un réseau de Pétri. Les transitions sont les changements de couleur, et les pools permettent de procéder à ces changements dans le bon ordre (rouge ne suit jamais vert par exemple. La figure suivante montre cette modélisation.
Là où l'intérêt des réseaux de Pétri se fait mieux sentir, c'est dans le cas où l'on doit gérer deux feux sur un carrefour... ils ne doivent pas passer au vert en même temps. Il faut attendre que l'un soit rouge pour autoriser le passage au vert de l'autre. Il suffit pour celà de créer deux exemplaires du réseau précédents (un exemplaire par feu), et d'exprimer la contrainte d'exclusivité par un nouveau pool.
Nous allons travailler sur cet exemple-là pour ce TD.
Implémentation
Nous allons faire en sorte que le code suivant exécute une simulation des deux feux. 
public static void main(String[] args) {
  Petri feux = new Petri();

  PetriBuild(feux,7,6);

  int rouge_1          = PetriAddPool(feux,"1 rouge",       1);
  int rouge_2          = PetriAddPool(feux,"2 rouge",       1);
  int orange_1         = PetriAddPool(feux,"1 orange",      0);
  int orange_2         = PetriAddPool(feux,"2 orange",      0);
  int vert_1           = PetriAddPool(feux,"1 vert",        0);
  int vert_2           = PetriAddPool(feux,"2 vert",        0);
  int tout_rouge       = PetriAddPool(feux,"Tout est rouge",1);

  int passe_au_vert_1  = PetriAddTransition(feux,"1 passe au vert",   2,1);
  int passe_au_vert_2  = PetriAddTransition(feux,"2 passe au vert",   2,1);
  int passe_a_orange_1 = PetriAddTransition(feux,"1 passe a l'orange",1,1);
  int passe_a_orange_2 = PetriAddTransition(feux,"2 passe a l'orange",1,1);
  int passe_au_rouge_1 = PetriAddTransition(feux,"1 passe au rouge",  1,2);
  int passe_au_rouge_2 = PetriAddTransition(feux,"2 passe au rouge",  1,2);

  PetriSetInput (feux,passe_au_vert_1,rouge_1   , 1);
  PetriSetInput (feux,passe_au_vert_1,tout_rouge, 1);
  PetriSetOutput(feux,passe_au_vert_1,vert_1,     1);

  PetriSetInput (feux,passe_a_orange_1,vert_1,    1);
  PetriSetOutput(feux,passe_a_orange_1,orange_1,  1);

  PetriSetInput (feux,passe_au_rouge_1,orange_1,  1);
  PetriSetOutput(feux,passe_au_rouge_1,rouge_1,   1);
  PetriSetOutput(feux,passe_au_rouge_1,tout_rouge,1);

  PetriSetInput (feux,passe_au_vert_2,rouge_2   , 1);
  PetriSetInput (feux,passe_au_vert_2,tout_rouge, 1);
  PetriSetOutput(feux,passe_au_vert_2,vert_2,     1);

  PetriSetInput (feux,passe_a_orange_2,vert_2,    1);
  PetriSetOutput(feux,passe_a_orange_2,orange_2,  1);

  PetriSetInput (feux,passe_au_rouge_2,orange_2,  1);
  PetriSetOutput(feux,passe_au_rouge_2,rouge_2,   1);
  PetriSetOutput(feux,passe_au_rouge_2,tout_rouge,1);

  for(int steps = 0; steps < 100 && PetriStep(feux); ++steps);
}
Définition des types
Le type Pool
Le type à champ nommé Pool définit un chaîne de caractères (le nom du pool), et le nombre de jetons contenus dans le pool. Définissez-ce type dans un fichier Pool.java 
import java.lang.*;

class Pool {
  public String name;
  public int    nb_tokens;
}
Le type Transition
Le type Transition doit représenter une transition. On lui donnera un nom, et on stockera les références sur les pools input et output dans deux tableaux séparés. La taille de ces tableaux sera allouée au départ, mais on y entrera les pools un à un, ce qui oblige à conserver l'indice du premier slot libre. Enfin, pour chacun des pools, il faut stocker le nombre de jetons considérés par la transition. Cela conduit au type suivant, que vous définirez dans un fichier Transition.java, et que l'on illustre sur la figure ci-après. 
import java.lang.*;

class Transition {
  public String  name;
  public int[]   input_token;
  public int[]   output_token;
  public Pool[]  inputs;
  public Pool[]  outputs;
  public int     next_free_input_slot;
  public int     next_free_output_slot;
  public boolean activable;
}
Le type Petri
Le type Petri stocke les transitions et les pools, avec une gestion des tableaux identique à Transition. Définissez-le dans Petri.java. 
import java.lang.*;

class Petri {
  public Transition[] transitions;
  public Pool[]       pools;
  public int          next_free_pool_slot;
  public int          next_free_transition_slot;
}
Programmation
Recopiez, ce code dans un fichier Feux.java, et écrivez le code des fonctions. L'ordre de définition des fonctions n'a aucune importance, on en a doc profité pour les ranger dans l'ordre suivant lequel vous devez les écrire.