4. TP de C++ n°4 Le pattern Strategy

4.1. Motivation du pattern Strategy

Dans de nombreuses situations il faut choisir un algorithme au sein d'une famille afin de traiter au mieux la situation courante. Prenons, par exemple, un problème classique de recherche opérationnelle : la recherche de plus courts chemins. Selon la structure du graphe, nous avons le choix entre les algorithmes de Bellman, de Dijkstra ou de Ford (pour ne citer que les plus courants). Si nous désirons pouvoir appliquer chacun de ces algorithmes sur un objet de type Graphe, cela impose (à première vue) les caractéristiques suivantes :

Une première solution consiste à créer des sous classes de Graphe possédant chacune l'algorithme approprié, par exemple, la méthode PlusCourtsChemins de la classe GrapheAcycliqueCoutsPositifs sera de type Bellmann alors que la méthode PlusCourtsChemins de la classe GrapheGénéral sera de type Ford. Cette solution n'est toutefois pas pleinement satisfaisante car elle impose de savoir à quel type de graphe l'on est confronté à la création de l'objet, ce qui est loin d'être toujours le cas. Donnons un autre exemple peut être encore plus frappant. Supposons que vous disposiez de plusieurs algorithmes permettant d'effectuer un tri sur un tableau. Si le tableau est de petite taille, vous pouvez utiliser un tri simple genre TriInsertionSimple alors qu'un tableau de grande taille nécessitera un algorithme plus compliqué genre QuickSort. Si vous utilisez un formalisme par dérivation, vous fixez l'algorithme de tri lors de la création de l'objet, ce qui sera mal adapté si la taille de votre tableau change beaucoup au cours du temps.

L'idée du Pattern Strategy consiste à déplacer l'algorithme dans un objet. Nous associons une classe de base virtuelle à la catégorie d'algorithmes de la famille et une classe concrete à chaque algorithme. La classe de base virtuelle est chargée de représenter l'interface commune à tous les algorithmes de la famille, chaque classe concrète reprennant cette interface. La classe tableau agrège alors (le plus souvent par pointeur), un objet de la classe AlgorithmeTRI. La figure suivante illustre l'utilisation de Strategy dans ce cas.

 

Séparer l'algorithme de tri de son contexte (le tableau) permet de modifier chacun indépendament de l'autre du moment que les interfaces ne varient pas. On obtient ainsi une plus grande souplesse ! En outre, il est facile de rajouter un nouvel algorithme de tri sans modifier pour autant la classe Tableau ou sa hiérarchie. En outre, cela permet de cacher à la classe Tableau l'implémentation des algorithmes de tri.

La classe Tableau, c'est à dire celle qui utilise Strategy porte le nom de Contexte. En effet, elle modélise bien le contexte dans lequel on doit choisir un algorithme.

On peut remarquer qu'une variante du pattern Strategy est utilisée régulièrement par la STL qui délègue à des objets foncteurs les opérations de comparaison sur les différents éléments recensés dans un conteneur.

Les trois reproches suivants sont souvents adressés au pattern Strategy

  1. Certes, la structure conditionnelle de choix est ici remplacée par un appel à la méthode appliquerTri qui délègue cette opération à la méthode Trier de l'objet agrégé. Vous remarquerez toutefois, qu'il sera néanmoins nécessaire d'effectuer un choix pour associer le bon objet AlgorithmeTRI à l'objet Tableau. En outre, cela suppose que le programmeur qui utilise le pattern doit savoir qu'il lui est possible de choisir entre divers algorithmes. Pire encore, il doit connaître les différences entre ses algorithmes pour choisir le bon.
  2. La communication entre la classe Contexte et les classes Stratégies peut s'avérer assez complexe.
    En effet, si les algorithmes de tri étaient implémentés en dur dans la classe Tableau, alors ils pourraient accéder directement à ses attributs dans un souci d'effacité. Ici, à moins d'utiliser des friend, ceci ne sera pas possible. En outre, tous les algorithmes d'une même famille doivent fournir la même interface afin que le pattern fonctionne.
    Hors, lorsque l'on utilise différentes stratégies, il arrive fréquemment que les algorithmes les plus puissants aient besoin d'informations supplémentaires. Le seul moyen permettant d'obtenir une interface cohérente consistera à passer aux autres algorithmes des informations dont ils n'ont pas besoin, ce qui engendre un surcoût notoire au moment de l'appel sans parler de la nécessité de construire parfois des objets inutiles.
    Une autre technique consiste à passer à la méthode de Stratégie une référence sur l'objet contexte. Auquel cas, c'est la Stratégie qui se débrouille pour aller récupérer dans le Contexte les données dont elle a besoin. Si elle paraît plus efficace, cette technique n'en est pas moins très dangereuse car elle introduit une dépendance de la Stratégie sur la structures des données du Contexte.
  3. Finalement, utiliser Strategy fait croître de manière significative le nombre d'objets. Aux objets Contextes s'ajoute les objets Stratégies. Afin de réduire le nombre d'objets Stratégies présents, il faut s'arranger pour que ces derniers soient partageables entres les divers contextes qui les utilisent.

4.2. Les stratégies fixées à la compilation

Si l'on fixe la stratégie à la compilation, il est possible d'utiliser un objet permanent dans le contexte, le type de celui-ci étant passé en template à la classe Contexte. Ce schéma est utilisé à outrance par la STL et permet de gagner en efficacité lors de l'exécution au détriment de la souplesse d'utilisation.

4.3. Application au problème du parc de véhicules

Chaque véhicule peut désormais tomber en panne. Il dispose alors d'une variable d'instance spécifiant son état à choisir entre Fonctionnel, Panne Légère ou Panne sévère. Incluons désormais dans notre simulation de parc un générateur aléatoire de panne. Lorsque les véhicules tombent en panne, il faudra choisir parmi les deux stratégies de dépannage suivantes :

Nous disposerons donc de deux objets stratégies respectivement associés à chaque type de réparation.

Le travail demandé consiste à gérer ces deux stratégies sur un parc complet de véhicules. Comment pouvez vous gérer de façon homogène l'état fonctionnel ?

4.4 Solution

Le problème avec ce TP tient au fait qu'il est possible de l'implémenter de plein de façons différentes. Nous présentons ici une version qui tient pas mal debout mais est loin d'être unique. Elle repose sur les deux fichiers :

Bien entendu, ce code ne servirait à rien sans l'introduction dans la classe Véhicule (voir dans Vehicule.hxx) d'un attribut nommé depannage_ et référençant l'une de ces variables globales, lequel est utilisé par les méthodes Véhicule::mettreEnPanne et Véhicule::depanner