{{{ #!comment -*- coding: utf-8 -*- }}} [[PageOutline]] = Représentation d'une Structure Booléenne Multi-niveaux (EBM) = == Les différentes classes == Pour pouvoir implanter en mémoire une {{{EBM}}} il est nécessaire de disposer de trois classes: * Une classe de base {{{Ebm}}} * Une classe {{{EbmExpr}}} pour représenter les expressions (dérivant d'{{{Ebm}}}). * Une classe {{{EbmVar}}} pour reprséenter les variables (dérivant d'{{{Ebm}}}). Les squelettes de ces classes sont fournis dans l'énoncé {{{Ebm.h}}}, {{{EbmExpr.h}}} et {{{EbmVar.h}}}. Il vous est demandé de les compléter. Une implantation de la classe {{{LogicValue}}} vous est fournie: * [attachment:LogicValue.h LogicValue.h] * [attachment:LogicValue.cpp LogicValue.cpp] === La classe {{{Ebm}}} === {{{ class Ebm { public: enum Type { Variable=1, Expression=2 }; enum OperatorType { Not=1, And, Or, Xor, UndefinedOperator }; public: static Ebm* parse ( std::string ); public: unsigned int litterals (); std::set support (); LogicValue eval (); void support ( std::ostream& ); void display ( std::ostream& ); }; }}} __Principales méthodes de la classe {{{Ebm}}}:__ * {{{litterals()}}} : retourne le nombre de littéraux de l'{{{EBM}}}. C'est à dire le nombre de fois que des variables apparaissent dans l'expression. * {{{support()}}} : retourne le support de l'{{{EBM}}} sous forme d'ensemble ({{{set<>}}}) Le support est l'ensemble des variables nécessaire pour calculer la valeur de l'expression. * {{{support(std::ostream&)}}} : Affiche le support dans un flux, voir l'exemple d'éxécution du programme de test fourni plus bas. * {{{display(std::ostream&)}}} : Affiche l'{{{EBM}}} sous sa forme humainement lisible, en notation ''préfixée''. * {{{eval()}}} : Calcule la valeur de l'expression booléenne. Le type de retour est un {{{LogicValue}}}, c'est à dire une variable pouvant prendre trois valeurs: {{{Zero}}}, {{{One}}} et {{{Undefined}}} (cf. {{{TME 2}}}). * {{{parse()}}} : Une fonction statique transformant une chaîne de caractères en une {{{EBM}}}. === La classe {{{EbmVar}}} === {{{ class EbmVar: public Ebm { public: // Operations sur les dictionnaires. static EbmVar* get ( unsigned int index ); static EbmVar* get ( std::string name ); public: inline std::string getName (); inline LogicValue getValue (); inline unsigned int getIndex (); inline void setValue ( LogicValue value ); private: EbmVar ( std::string name, LogicValue value=Low ); virtual ~EbmVar (); private: static unsigned int _maxIndex; static std::map _byIndex; public: static EbmVar* create ( std::string name, LogicValue value=LogicValue::Zero ); // Completer ici... private: std::string _name; // Variable name. LogicValue _value; // Logical value. unsigned int _index; // Unique index (for ROBDD) }; }}} __Attributs de la classe {{{EbmVar}}}:__ * {{{_name}}} : Le nom de la variable (par ex. {{{"a"}}}) * {{{_value}}} : La valeur actuellement affectée à la variable ({{{Zero}}}, {{{One}}} ou {{{Undefined}}}). * {{{_index}}} : Un index permettant d'identifier de façon unique la variable. Cet index trouvera son utilité dans le TME suivant, présentant les {{{ROBDD}}}. __Attributs ''statiques'' de la classe {{{EbmVar}}}:__ * {{{_maxIndex}}} : Le compteur utilisé pour générer des index uniques (mécanisme identique à celui utilisé pour les vecteurs lors du TME1). * {{{_byName}}} : Une table associative permettant de retrouver ''n'importe quelle'' variable sachant son nom. * {{{_byIndex}}} : Une table associative permettant de retrouver ''n'importe quelle'' variable sachant son index. __Principales méthodes de la classe {{{EbmVar}}}:__ * {{{getName()}}} : accesseur retournant le nom. * {{{getIndex()}}} : accesseur retournant l'index. * {{{getValue()}}} : accesseur retournant la valeur. * {{{setValue()}}} : modificateur de la valeur. * {{{get()}}} : deux surcharge différentes pour retrouver une variable par son nom ou par son index. * {{{create()}}} : crée ''ou'' retourne, si elle existe déjà un pointeur sur la variable demandée. === La classe {{{EbmExpr}}} === {{{ class EbmExpr : public Ebm { private: OperatorType _operator; // operateur de ce noeud std::list _operands; // pointeurs sur les operandes public: EbmExpr ( OperatorType, std::list& operands ); virtual ~EbmExpr (); static EbmExpr* Not ( Ebm* ); static EbmExpr* Or ( Ebm*, Ebm* ); static EbmExpr* Or ( Ebm*, Ebm*, Ebm* ); static EbmExpr* Or ( Ebm*, Ebm*, Ebm*, Ebm* ); static EbmExpr* Xor ( Ebm*, Ebm* ); static EbmExpr* Xor ( Ebm*, Ebm*, Ebm* ); static EbmExpr* Xor ( Ebm*, Ebm*, Ebm*, Ebm* ); static EbmExpr* And ( Ebm*, Ebm* ); static EbmExpr* And ( Ebm*, Ebm*, Ebm* ); static EbmExpr* And ( Ebm*, Ebm*, Ebm*, Ebm* ); public: inline OperatorType getOperator (); inline std::list& getOperands (); }; }}} __Attributs de la classe {{{EbmExpr}}}:__ * {{{_operator}}} : le type de l'opérateur (dans {{{CaoTypes.h}}}, parmis {{{Not}}}, {{{And}}}, {{{Or}}} ou {{{Xor}}}). * {{{_operands}}} : une liste de pointeurs vers les opérandes. __Principales méthodes de la classe {{{EbmVar}}}:__ * {{{getOperator()}}} : accesseur, retourne le type de l'opérateur. * {{{getOperands()}}} : accesseur, retourne une référence sur la liste des opérandes (pour éviter une copie inutile de la liste). * {{{Or()}}} : trois surcharges construisant une expression {{{Or}}} entre ses {{{N}}} opérandes. Le but de ces différentes fonctions est de cacher la construction de la liste des opérandes et l'allocation de l'{{{EbmExpr}}} résultante. Noter que cela implique une construction ''bottom-up'' de l'{{{EBM}}} complète. Voir l'exemple fourni. * {{{And()}}} et {{{Xor()}}} : idem. == Présentation des méthodes récursives == Les méthodes {{{litterals()}}}, {{{support()}}}, {{{display()}}} et {{{parse()}}} de la classe {{{Ebm}}} sont récursives. On définit le niveau de profondeur de l'arbre d'une {{{EBM}}} comme le nombre d'arcs {{{N}}} nécessaire pour atteindre la racine. Dans l'{{{EBM}}} {{{e4}}}, la racine {{{e4}}} à une profondeur nulle, {{{e1}}} une profondeur de 1 et {{{a}}} une profondeur de 2. '''Récursion''' Considérons l'exemple de la fonction {{{litterals()}}}. Dire qu'elle est récursive signifie que son calcul au niveau de profondeur {{{N}}} peut se décomposer en calculs ''de cette même fonction'' appliquée sur le niveau {{{N+1}}}. Par exemple, le calcul de {{{litterals()}}} de {{{e4}}} peut s'exprimer comme la somme des fonctions {{{litterals()}}} ''appliquée à ses opérandes'' ({{{e0}}}, {{{e1}}}, {{{e2}}} et {{{e3}}}) : '''Condition d'arrêt''' On comprend bien, que l'on ne va pas rappeler indéfiniment {{{litterals()}}}, à une profondeur donnée, il faudra bien d'arrêter. Le critère d'arrêt est simple: lorsque l'on atteind une {{{EbmVar}}}, le noeud n'a pas d'opérandes, et son nombre de littéraux vaut 1. En conclusion, la fonction récursive aura la structure générale suivante: {{{ LITTERALS(e) IF e IS_A variable: RETURN 1 ELSE sum = 0 FOR EACH operand OF e: sum += LITTERALS(operand) RETURN sum }}} [[Image(Ebm-1.png,align=center)]] La figure suivante représente l'ordre dans lequel les noeud de l'arbre de l'{{{EBM}}} sont parcourus lors d'une récursion. [[Image(Ebm-2.png,align=center)]] État de la pile d'appel des fonctions a un instant donné du parcours récursif. Le chemin actullement parcouru est {{{(e4,e1,a)}}} [[Image(Ebm-3.png,align=center)]] La pile d'appel des fonctions membres à un instant donné. ''Attention'' : il est très important de bien distinguer le code la fonction, qui est écrit une fois (dans {{{Ebm}}}) et l' ''objet'' auquel elle s'applique. Nous avons ainsi la même fonction membre {{{display()}}} mais sur trois objets différents : {{{e4}}}, {{{e1}}} et {{{a}}}. [[Image(Ebm-4.png,align=center)]] == Fonctionnement de la fonction {{{getType()}}} == Dans la présentation de la récursion, nous avons vu qu'il était nécessaire, pour choisir entre la récursion et l'arrêt, de savoir distinguer une variable ({{{EbmVar}}}) d'une expression ({{{EbmExpr}}}). Pour cela nous allons implanter la fonction {{{getType()}}}. La fonction {{{getType()}}} a les caractéristiques suivantes: * Elle est déclarée virtuelle pure dans la classe {{{Ebm}}}, c'est à dire qu'elle '''doit''' être sur-définie dans les classes dérivées '''et''' qu'elle n'a aucune implémentation au niveau de la classe {{{Ebm}}}. * Dans la classe {{{EbmVar}}} elle retourne '''Variable'''. * Dans la classe {{{EbmExpr}}} elle retourne '''Expression'''. De cette façon, lorsqu'elle est appelée dans les fonctions récursives définies dans {{{Ebm}}}, elle retournera la valeur associée au ''type dynamique'' de l'{{{Ebm}}} en cours de traitement. C'est à dire {{{EbmVar}}} ou {{{EbmExpr}}}. [[Image(Ebm-5.png,align=center)]] == Travail a Effectuer == === Question 1 === Implanter {{{EbmVar}}}: * Ajouter le dictionnaire manquant. * Ajouter la fonction de création statique. * Implanter les méthodes ''ordinaires''. * Les constructeurs & destructeurs ne sont pas vides: que doivent-il contenir? === Question 2 === Implanter {{{EbmExpr}}}: * Penser à une façon simple pour les opérateurs logiques d'appeler le constructeur générique. === Question 3 === Implanter {{{Ebm}}}: * Le squelette du fichier vous est fourni: [attachment:Ebm.cpp Ebm.cpp]. Il contient le code de la fonction {{{Ebm::parse()}}} * Implanter la déclaration (dans {{{Ebm}}}) et les deux sur-définitions de la fonction {{{getType()}}} (dans {{{EbmVar}}} & {{{EbmExpr}}}). * Implanter les fonctions {{{Ebm::litterals()}}}, {{{Ebm::support()}}}, {{{Ebm::eval()}}} et {{{Ebm::display()}}}. === Question 4 === Tester l'ensemble avec le programme suivant: [attachment:Main.cpp Main.cpp]. === Question 5 (facultative) === Il existe une autre façon d'implanter le mécanisme de récursivité ne nécessitant pas de fonction {{{getType()}}}, suggérez une approche alternative (utilisant plus intensivement l'héritage).