Les adaptateurs

Définitions

Comme leur nom l’indique, les adaptateurs adaptent l’interface et/ou le comportement des curseurs `a des opérations plus complexes sans surcoˆut `a l’exécution. Ce sont des clients du ou des curseurs sous-jacents, c’est-`a-dire qu’ils les réutilisent, et qu’ils implémentent les fonctionnalités supplémentaires requises par une variante de l’algorithme de base. On définit l’arité d’un adaptateur comme le nombre de curseurs qu’il contient. Un adaptateur unaire encapsule un curseur, un adaptateur binaire, deux curseurs, etc. La figure 5.1 représente les interactions entre l’algorithme, le curseur adaptant et le(s) curseur(s) adapté(s). Ces adaptateurs appartiennent aussi au concept de curseur permettant  complémentarité et intersection un polymorphisme statique et toutes les opérations additionnelles sont effectuées `a la volée. Leur écriture impose principalement au programmeur de se poser trois questions : quelles sont les opérations `a effectuer lors des appels des méthodes first_transition, next_transition et forward ? Ceci a pour effet de segmenter et modulariser agréablement l’implémentation d’un algorithme. Les sections suivantes présentent un ensemble de cas o`u l’implémentation par adaptation du comportement de base est particulièrement puissante et efficace cependant le principe laisse libre cours `a l’imagination du développeur et ouvre la porte `a d’innombrables types de curseur. 

Les opérations ensemblistes

Les opérations ensemblistes sur les automates définies `a la section 2.2.6 page 30 sont mises en œuvre grˆace `a des adaptateurs de curseur monodirectionnel unaires (le complémentaire dans Σ∗ ) ou binaires (intersection, union, différence, différence symétrique, concaténation). La figure 5.2 décrit les interactions de l’adaptateur unaire du complémentaire not_cursor et de l’adaptateur binaire d’intersection intersection_cursor avec les autres composants. Nous allons nous intéresser `a l’intersection pour illustrer la démarche de création d’un tel curseur. Soient A(Σ, Q, i, F, ∆) et A′ (Σ, Q′ , i′ , F′ , ∆′ ) deux automates dont on veut calculer l’intersection B(Σ, Q′′, i′′, F′′ , ∆′′) définie par : B = (Σ, Q × Q ′ ,(i, i′ ), F × F ′ , ∆′′) B est un automate dont les états sont des couples pris dans l’ensemble du produit cartésien  Q × Q′ et dont l’ensemble des transitions ∆′′ est défini par la fonction de transition : δ ′′ 1 ((q, q′ ), σ) = (δ1(q, σ), δ′ 1 (q ′ , σ)).

Les états terminaux sont les couples dont les états sont tous deux terminaux dans les automates de départ. Soit x un curseur d’intersection évoluant sur l’automate B et encapsulant deux curseurs monodirectionnels c1 et c2 respectivement sur A et A′ . D’après les définitions précédentes, x doit avoir le comportement suivant : – L’état pointé par x est constitué d’une paire d’états des automates sous-jacents : q ′′ = (q, q′ ). State src() const { return make_pair(c1.src(), c2.src()); } – q ′′ est final si q et q ′ sont finaux : bool src_final() const { return c1.src_final() && c2.src_final(); } – forward implémente la fonction de transition δ ′′ 1 . Une transition étiquetée par a sortant de l’état q ′′ est définie si et seulement si il en existe une étiquetée par la mˆeme lettre sortant des états q et q ′ . Autrement dit, x peut avancer sur une transition si c1 et c2 le peuvent : bool forward(int a) { return c1.forward(a) && c2.forward(a); } – Une transition sortant de q ′′ étiquetée par a est définie dans B si elle est définie pour q et q ′ : bool exists(int a) const { return c1.exists(a) && c2.exists(a); } – L’état q ′′ est un état puits si au moins un des deux états q et q ′ est un état puits : bool sink() const { return c1.sink() || c2.sink(); } 

Les transitions par défaut

Les mécanismes de transitions et d’états par défaut décrits `a la section 2.2.5 s’implémentent très simplement avec des adaptateurs. Par exemple, un curseur x adaptant un curseur y sur un automate possédant un état par défaut s aura pour méthode forward : bool forward(int a) { if (! y.forward(a)) y = s; return true; } Cette fonction utilise la propriété affirmant qu’un état est assignable `a un curseur : l’instruction y = s positionne le curseur encapsulé sur l’état puits s en cas d’échec, rendant l’automate sous-jacent virtuellement complet. C’est la seule différence de comportement avec le curseur standard. En ce qui concerne l’automate avec transitions par défaut, il faut, lors de l’échec d’une avancée sur une transition non définie, que le curseur essaie de suivre la transition étiquetée par la lettre default, cette lettre étant fixée par l’utilisateur `a la construction de l’adaptateur :