[[PageOutline]]


= Représentation d'une Structure Booléenne Multi-niveaux (EBM) =

Les fichiers nécessaires à la réalisation de ce TME sont disponibles
directement sur le réseau enseignement, dans le répertoire:
{{{~jpc/M1-CAO/TME/3.public}}}


== 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 les fichiers {{{Ebm.h}}},
{{{EbmExpr.h}}} et {{{EbmVar.h}}}


=== La classe {{{Ebm}}} ===

{{{
class Ebm {
  public:
            unsigned int       litterals ();
            std::set<EbmVar*>  support   ();
            void               support   ( std::ostream& );
            void               display   ( std::ostream& );
            ValueType          eval      ();
    static  Ebm*               parse     ( std::string expression );
};
}}}

__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
   {{{ValueType}}}, c'est à dire une variable pouvant prendre trois valeurs:
   {{{Low}}}, {{{High}}} et {{{Unknown}}} (cf. {{{CaoTypes.h}}}).
 * {{{parse()}}} : Une fonction statique transformant une chaîne de caractères en une
   {{{EBM}}}.


=== La classe {{{EbmVar}}} ===

{{{
class EbmVar: public Ebm {
  private:
    static unsigned int                    _maxIndex;
    static std::map<std::string ,EbmVar*>  _byName;   // All variables storage.
    static std::map<unsigned int,EbmVar*>  _byIndex;
  private :    
             std::string   _name;       // Variable name.
             ValueType     _value;      // Logical value.
             unsigned int  _index;      // Unique index (for ROBDD)
  public:
                           EbmVar   ( std::string name, ValueType value=Low );
    virtual               ~EbmVar   ();
  public:
    inline   std::string   getName  ();
    inline   ValueType     getValue ();
    inline   unsigned int  getIndex ();
    inline   void          setValue ( ValueType value );
  // Operations sur le dictionnaire
    static   EbmVar*       get      ( unsigned int index );
    static   EbmVar*       get      ( std::string name );
};
}}}


__Attributs de la classe {{{EbmVar}}}:__
 * {{{_name}}}  : Le nom de la variable (par ex. {{{"a"}}})
 * {{{_value}}} : La valeur actuellement affectée à la variable
   ({{{Low}}}, {{{High}}} ou {{{Unknown}}}).
 * {{{_index}}} : Un index permettant d'identifier de façon unique la
   variable. Cet index trouvera sont 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.


=== La classe {{{EbmExpr}}} ===

{{{
class EbmExpr : public Ebm {
  private:
             OperatorType     _operator;  // operateur de ce noeud
             std::list<Ebm*>  _operands;  // pointeurs sur les operandes 
  public:
                              EbmExpr     ( OperatorType, std::list<Ebm*>& 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<Ebm*>& 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)]]

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)]]

É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)]]

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)]]


== 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)]]


== Les ''templates'' {{{map<>}}} et {{{set<>}}} ==