import java.util.ArrayList;
//==========================================================
// Circuits
//==========================================================
public class Circuit {
public static void main(String[] args) {
Circuit c = new Circuit();
Noeud n1 = c.creeMultiplication(c.creeConstante(2),
c.creeEntree());
c.sortie = n1;
System.out.println("Ceci doit afficher 2 : " + c.calcule(1));
System.out.println("Ceci doit afficher 12 : " + c.calcule(6));
Noeud n2 = c.creeMultiplication(n1,
c.creeAddition(c.creeConstante(1),
n1));
c.sortie = n2;
System.out.println("Ceci doit afficher 6 : " + c.calcule(1));
System.out.println("Ceci doit afficher 156 : " + c.calcule(6));
System.out.println("Ceci doit afficher 2 : " + c.nbNoeudsMult());
System.out.println("Ceci doit afficher 10 : " + c.nbOpEffectuees());
Circuit p20 = expRapide(20);
System.out.println("Ceci doit afficher 7 : " + p20.nbNoeudsMult());
System.out.println("Ceci doit afficher 1048576 : " + p20.calcule(2));
System.out.println("Ceci doit afficher 51 : " + p20.nbOpEffectuees());
Circuit p20m = expRapideMemoisee(20);
System.out.println("Ceci doit afficher 7 : " + p20m.nbNoeudsMult());
System.out.println("Ceci doit afficher 1048576 : " + p20m.calcule(2));
System.out.println("Ceci doit afficher 7 : " + p20m.nbOpEffectuees());
System.out.print("Ceci doit afficher ((2 * x) * (1 + (2 * x))) : ");
c.affiche();
}
// Partie I : Mise en jambes
private int entree; // Valeur de la variable dont dépend le calcul
private Noeud sortie; // Le dernier nœud, calculant le résultat
private ArrayList<Noeud> noeuds; // L'ensemble des nœuds
// Le constructeur n'initialise pas l'entrée : la méthode calcule
// s'en chargera avant chaque calcul. La sortie n'est pas initialisée
// non plus pour éviter un problème de circularité.
private Circuit() {
this.noeuds = new ArrayList<Noeud>();
}
// Ajout d'un nœud à la liste
private void ajouteNoeud(Noeud n) {
noeuds.add(n);
}
// Création de nœuds avec ajout direct
public Noeud creeConstante(int n) {
Noeud c = new Constante(n);
this.ajouteNoeud(c);
return c;
}
public Noeud creeEntree() {
Noeud e = new Entree(this);
this.ajouteNoeud(e);
return e;
}
public Noeud creeAddition(Noeud n1, Noeud n2) {
Noeud a = new Addition(n1, n2);
this.ajouteNoeud(a);
return a;
}
public Noeud creeMultiplication(Noeud n1, Noeud n2) {
Noeud m = new Multiplication(n1, n2);
this.ajouteNoeud(m);
return m;
}
public Noeud creeSoustraction(Noeud n1, Noeud n2) {
Noeud m = new Soustraction(n1, n2);
this.ajouteNoeud(m);
return m;
}
public Noeud creeMultiplicationMemoisee(Noeud n1, Noeud n2) {
Noeud m = new MultiplicationMemoisee(n1, n2);
this.ajouteNoeud(m);
return m;
}
// Donne la valeur de l'entrée, dont auront besoin certains nœuds
public int litEntree() {
return this.entree;
}
// Initialise la variable d'entrée et calcule le résultat.
public int calcule(int e) {
this.entree = e;
return this.sortie.valeur();
}
// Partie III : Affichage
public void affiche() {
// Pour l'affichage on part de la sortie, qui va transmettre à ses
// sources jusqu'à arriver aux constantes et aux entrées.
// this.sortie.affiche();
System.out.println(this.sortie);
}
// Partie IV : Des outils de diagnostic
// Pour l'une et l'autre, on fait une boucle sur l'ensemble des nœuds, et on
// utilise une méthode définie (ou héritée, ou redéfinie) dans chaque nœud.
public int nbNoeudsMult() {
int nb=0;
for (Noeud n : this.noeuds) {
if (n.estMult()) { nb++; }
}
return nb;
}
public int nbOpEffectuees() {
int nb=0;
for (Noeud n : this.noeuds) {
nb += n.nbOpEffectuees();
}
return nb;
}
public static Noeud expRapide(Circuit c, int n) {
if (n == 0) {
// x^0 = 1
return (c.creeConstante(1));
} else if (n % 2 == 0) {
// Si n pair, x^n = (x^{n/2})^2
Noeud e = expRapide(c, n/2);
return (c.creeMultiplication(e, e));
} else {
// Si n impair, x^n = x*((x^{n/2})^2)
Noeud e = expRapide(c, n/2);
return (c.creeMultiplication(c.creeEntree(),
c.creeMultiplication(e, e)));
}
}
public static Circuit expRapide(int n) {
// On crée d'abord un circuit vide...
Circuit c = new Circuit();
// puis on y ajoute des nœuds, et on connecte le dernier à la sortie.
c.sortie = expRapide(c, n);
return c;
}
// Partie V : Mémoïsation
// Les nœuds de multiplication directement renvoyés par la méthode ont
// besoin d'être mémoïsés, car excepté le dernier ils sont systématiquement
// utilisés deux fois. Le nœud {Multiplication(e,e)} du cas impair en
// revanche n'est utilisé qu'une seule fois (si le reste est correctement
// mémoïsé).
public static Noeud expRapideMemoisee(Circuit c, int n) {
if (n == 0) {
// x^0 = 1
return (c.creeConstante(1));
} else if (n % 2 == 0) {
// Si n pair, x^n = (x^{n/2})^2
Noeud e = expRapideMemoisee(c, n/2);
return (c.creeMultiplicationMemoisee(e, e));
} else {
// Si n impair, x^n = x*((x^{n/2})^2)
Noeud e = expRapideMemoisee(c, n/2);
return (c.creeMultiplicationMemoisee(c.creeEntree(),
c.creeMultiplication(e, e)));
}
}
public static Circuit expRapideMemoisee(int n) {
Circuit c = new Circuit();
c.sortie = expRapideMemoisee(c, n);
return c;
}
// Pour réinitialiser, on fait une boucle sur les nœuds et on délègue à
// chaque nœud la tâche de se réinitialiser si besoin.
public void reInit() {
for (Noeud n : noeuds) { n.reInit(); }
}
}
//==========================================================
// Nœuds
//==========================================================
abstract class Noeud {
abstract public int valeur();
// Partie III
// On ne saurait quoi afficher pour un nœud abstrait, d'où la méthode
// abstraite (qu'il faut quand même déclarer pour pouvoir l'appeler ensuite
// sur un nœud de type inconnu).
// C'est mieux qu'une méthode vide
// public void affiche() {}
// car cela force la redéfinition dans toutes les sous-classes concrètes.
// abstract public void affiche();
// Partie IV
// Par défaut, un nœud n'est pas une multiplication. Tous les nœuds
// vont hériter de cette définition qui renvoie {false}, le nœud de
// multiplication la redéfinira de manière à ce qu'elle renvoie {true},
// et la multiplication mémoïsée héritera de cette redéfinition.
public boolean estMult() { return false; };
// L'attribut comptant le nombre d'utilisations d'un mot est privé, mais
// on fournit d'une part la possibilité d'obtenir sa valeur, et d'autre part
// des moyens *limités* de la mettre à jour.
// Dire à ceux qui écrivent sans mettre aucune restriction une méthode
// public void setNbOp(int n) { this.nbOp = n; }
// qu'ils tuent l'encapsulation.
private int nbOp;
public int nbOpEffectuees() { return this.nbOp; }
public void incrNbOp() { this.nbOp++; }
// Partie V
// Par défaut, un nœud n'a rien à réinitialiser. Seuls les nœuds avec
// mémoïsation ont réellement besoin de redéfinir cette méthode.
public void reInit() {}
}
// Partie II : Une hiérarchie de nœuds
abstract class NoeudBinaire extends Noeud {
private Noeud source1, source2;
public NoeudBinaire(Noeud s1, Noeud s2) {
this.source1 = s1;
this.source2 = s2;
}
// Les attributs {source*} étant privés, il faut fournir des méthodes pour
// les récupérer. Cependant ici, personne n'a vraiment besoin d'obtenir la
// source elle-même. On obtient une meilleure encapsulation en ne
// fournissant qu'une méthode accédant à la chose utile : la valeur
// calculée par {source*}.
public int valeurSource1() {
return this.source1.valeur();
}
public int valeurSource2() {
return this.source2.valeur();
}
// Variante possible : on peut faire comme pour {affiche}, et définir une
// fonction {valeur} qui combine les valeurs des deux sources avec un
// opérateur défini par le nœud concret. Dans ce cas pas besoin de définir
// {valeurSource*}.
// public int valeur() {
// this.incrNbOp(); // Partie IV : on compte une opération
// return this.combine(this.source1.valeur(), this.source2.valeur());
// }
// abstract public int combine(int v1, int v2);
// Partie III
// Une méthode abstraite dont on attend que chaque définition concrète
// affiche l'opérateur unaire correspondant au nœud concret.
// abstract public void afficheOp();
// public void affiche() {
// // On place des parenthèses systématiquement. Certaines seront inutiles.
// System.out.print("(");
// this.source1.affiche();
// afficheOp();
// this.source2.affiche();
// System.out.print(")");
// }
abstract public String opString();
public String toString() {
return "(" + this.source1 + this.opString() + this.source2 + ")";
}
}
class Constante extends Noeud {
private int cst;
public Constante(int c) { this.cst = c; }
public int valeur() { return this.cst; }
// Partie III
// public void affiche() {
// System.out.print(this.cst);
// }
public String toString() {
return String.valueOf(this.cst);
}
}
class Entree extends Noeud {
private Circuit circuit;
public Entree(Circuit c) {
this.circuit = c;
}
public int valeur() {
return this.circuit.litEntree();
}
// Partie III
// public void affiche() {
// System.out.print("x");
// }
public String toString() {
return "x";
}
}
class Addition extends NoeudBinaire {
public Addition(Noeud e1, Noeud e2) { super(e1, e2); }
public int valeur() {
this.incrNbOp(); // Partie IV : on compte une opération
return (this.valeurSource1() + this.valeurSource2());
}
// Variante
// public int combine(int v1, int v2) { return v1 + v2; }
// Partie III
// public void afficheOp() {
// System.out.print(" + ");
// }
public String opString() {
return " + ";
}
}
class Multiplication extends NoeudBinaire {
public Multiplication(Noeud e1, Noeud e2) { super(e1, e2); }
public int valeur() {
this.incrNbOp(); // Partie IV : on compte une opération
return (this.valeurSource1() * this.valeurSource2());
}
// Variante
// public int combine(int v1, int v2) { return v1 * v2; }
// Partie III
// public void afficheOp() {
// System.out.print(" * ");
// }
public String opString() {
return " * ";
}
// Partie IV
// Redéfinition de cette méthode dont la définition standard renvoie
// {false}.
public boolean estMult() { return true; }
}
// Rien de spécial ici, c'est juste pour montrer qu'il y a peu de choses à
// écrire une fois qu'on hérite de {NoeudBinaire}.
class Soustraction extends NoeudBinaire {
public Soustraction(Noeud e1, Noeud e2) { super(e1, e2); }
public int valeur() {
this.incrNbOp(); // Partie IV
return (this.valeurSource1() - this.valeurSource2());
}
// Variante
// public int combine(int v1, int v2) { return v1 - v2; }
// Partie III
// public void afficheOp() {
// System.out.print(" - ");
// }
public String opString() {
return " - ";
}
}
// Partie V : Mémoïsation
class MultiplicationMemoisee extends Multiplication {
// Par défaut, un nœud n'est pas déjà évalué, et {mem} n'est pas défini.
// Invariant des objets de cette classe : si {dejaEvalue} vaut {true},
// alors {mem} contient une valeur.
private boolean dejaEvalue=false;
private int mem;
public MultiplicationMemoisee(Noeud e1, Noeud e2) { super(e1, e2); }
// Redéfinition de {valeur()}
public int valeur() {
if (!this.dejaEvalue) {
// Si pas déjà évalué, on appelle la méthode {valeur()} de la
// classe mère {Multiplication} pour définir l'attribut {mem}.
this.mem = super.valeur();
this.dejaEvalue = true;
}
// Dans tous les cas, à ce stade {mem} est défini, on renvoie sa
// valeur.
return this.mem;
}
// Pour la réinitialisation, pas besoin d'effacer explicitement {mem}, il
// suffit de placer le booléen à {false} pour s'assurer que la méthode
// {valeur()} ne peut plus aller voir l'ancienne valeur de {mem} (ni aucune
// autre méthode, l'attribut {mem} étant évidemment privé).
public void reInit() {
this.dejaEvalue=false;
}
}