UP | HOME

Files à priorité - La couche haute : l'opération de fusion

Table of Contents

1 Vers la structure monoïdale des files à priorité

Le but du TP est d'enrichir les files à priorité en ajoutant une couche supérieure, définissant l'opération de fusion de deux files.

Muni de cette opération de fusion, l'ensemble des files à priorité devient un monoïde, structure mathématique caractérisée par :

  • une opération binaire associative,
  • un élément neutre pour cette opération, ici la file vide.

Point intéressant : il est possible de paralléliser les calculs d'une somme de n termes dans un monoïde, ce que nous exploiterons.

Pour implémenter l'interface enrichie, nous allons recourir à deux techniques de factorisation :

  • l'héritage multiple,
  • l'agrégation avec délégation.

Ces deux techniques s'appliquent à des architectures en couche, comme celle des files enrichies. La couche haute contient la structure de monoïde et est implémentée en utilisant la couche basse, contenant les opérations de manipulation de la file, l'ajout et le retrait d'éléments. Les deux techniques donnent une factorisation optimale : on écrit une et une seule fois les implémentations des couches hautes et basses, puis on les combine librement, par héritage ou agrégation.

Dans la suite, nous utilisons uniquement des types immutables. Deux implémentations des listes immutables sont fournies :

  • bibliotheque.Liste et bibliotheque.Listes : une implémentation minimale avec une méthode de filtrage ("pattern matching"), qui incite à utiliser la récursion, des opérations utiles pour insérer un élément dans une liste supposée triée, et pour retirer l'élément minimal d'une liste,
  • bibliotheque.obsolete.Liste : une implémentation plus classique.

Certaines des questions ci-dessous relatives aux files simples ont pu être résolues dans le premier TP. Reprendre les consignes, les spécifications et les indications qui y sont données. Les diagrammes fournis donnent des indications concernant l'architecture. Ils représentent des types, classes ou interfaces, et la relation de sous-typage entre eux. Par défaut, un type est une interface. Il est précisé s'il s'agit d'une classe ou d'une classe abstraite. Les propriétés d'un type (attributs ou méthodes) sont préfixés par une indication de visibilité ou d'abstraction :

  • + : public,
  • # : protected,
  • - : private,
  • @ : abstract (non défini, nécessairement dans une classe abstraite),
  • $ : default (défini, nécessairement dans une interface).

En plus de la relation de sous-typage, la relation d'usage "instance de" est représentée lorsqu'elle est significative. Enfin, quelques conventions simplificatrices sont utilisées : il se peut que certains types ne soient pas représentés et les propriétés indiquées dans un type y sont soit déclarées (et définies ou non), soit héritées. Certaines peuvent être omises.

2 Travail à faire

2.1 Files simples à priorité

Définir une interface pour les files à priorité contenant les opérations suivantes.

  • Fabriques
    • Fabrique de file vide
  • Accesseurs
    • Conversion en la liste sous-jacente
    • Test de vacuité
    • Taille de la file
  • Services de premier niveau (future couche basse)
    • Ajout d'un élément appartenant à un ensemble ordonné
    • Retrait du plus petit élément

Implémenter cette interface par deux classes.

  • La première utilise une liste d'éléments pour stocker les éléments de la file.
  • La seconde utilise une liste triée d'éléments.

Il est possible de factoriser le code dans une classe abstraite. Celle-ci contiendra deux méthodes abstraites permettant d'insérer un élément dans la liste et de retirer un élément dans la liste. Il est nécessaire aussi d'y ajouter une fabrique abstraite permettant de construire une file à partir d'une liste : tout appel du constructeur est remplacé par l'appel de cette fabrique.

A l'issue de cette première partie, on obtient ce schéma.

	    -------------------
	    | File à priorité |
	    | + accesseurs    |
	    | + fabrique      |
	    | + services 1    |
	    ------------------
		   ∧
		   |
       ---------------------------
       |    Implem partielle     |
       |   (classe abstraite)    |
       | - état : une liste      |
       | #@ insertion liste      |
       | #@ retrait liste        |
       | #@ fabrique liste->file |
       | + accesseurs            |
       | + fabrique              |
       | + services 1            |
       ---------------------------
		   ∧
		   |
	 ----------------------
	 |                    |
---------------------  ---------------------
|  Implem 1 (classe)|  |  Implem 2 (classe)|
| - état : liste    |  | - état : liste    |
|   non triée       |  |   triée           |
| # insertion liste |  | # insertion liste |
| # retrait liste   |  | # retrait liste   |
| # fabrique        |  | # fabrique        |
|    liste->file    |  |    liste->file    |
 --------------------  --------------------

2.2 Files enrichies à priorité

Étendre l'interface précédente en ajoutant les méthodes propres à un monoïde, zero et somme. Celles-ci sont déclarées dans l'interface hierarchie.MonoideAdditif, exprimant la propriété d'être un monoïde additif, qu'il faudra aussi étendre. La méthode zero renvoie l'élément neutre, la file vide, alors que la méthode somme calcule la fusion de deux files, autrement dit la réunion des deux files en préservant les priorités.

Ces deux méthodes représentent les services de second niveau, correspondant à la couche haute et s'implémentant en utilisant les services de premier niveau correspondant à la couche basse.

Lorsqu'on étend une interface, il est habituel de remplacer les occurrences covariantes de l'interface parente par l'interface l'étendant, afin d'éviter des pertes d'information : c'est une spécialisation. Pratiquement, en Java, seul le type de retour peut être spécialisé.

Voici un extrait de code expliquant cette spécialisation.

interface F1<T> {
  F1<T> ajout(T x);
}
interface F2<T> extends F1<T> {
  @Override
  F2<T> ajout(T x);

Une difficulté cependant peut survenir si l'occurrence du type à spécialiser apparaît comme argument d'un type générique.

interface F1<T> {
  Couple<T, F1<T>> retrait();
}
// Erreur à la compilation : "The return type is incompatible."
interface F2<T> {
  Couple<T, F2<T>> retrait();
}

Nous verrons dans l'étude de la variance pourquoi en Java un type générique a cette limitation. Il existe cependant une astuce permettant d'obtenir la covariance, en utilisant le joker ?.

interface F1<T> {
  Couple<T, ? extends F1<T>> retrait();
}
interface F2<T> extends F1<T> {
  @Override
  Couple<T, ? extends F2<T>> retrait();
}

Le type Couple<T, ? extends S> correspond à la réunion de tous les types Couple<T, U>, pour U sous-type de S.

2.3 Implémentation de la couche haute

Etendre l'interface enrichie par une nouvelle interface qui non seulement redéclare les méthodes zero et somme mais les redéfinit. Il est nécessaire de les qualifier par default. L'implémentation de somme doit être récursive et utiliser les méthodes d'ajout et de retrait.

Réaliser une seconde extension. La nouvelle implémentation ne doit pas être récursive mais itérative (avec des boucles).

2.4 Implémentation par héritage multiple

Implémenter l'interface enrichie en utilisant l'héritage multiple. Pour chaque classe d'implémentation de la file simple et pour chaque interface d'implémentation de la couche haute, créer une nouvelle classe d'implémentation de la file enrichie par héritage de la classe implémentant la couche basse et de l'interface contenant les implémentations de la couche haute. Y redéfinir toutes les méthodes dont le type a été spécialisé, soit la fabrique de files à partir d'une liste, la fabrique d'une file vide, et les méthodes d'ajout et de retrait.

Voici le schéma décrivant une telle solution par héritage.

 ------------------                 -----------------------------
 | File à priorité|                 |      File Enrichie        | 
 | + accesseurs   |                 | + accesseurs              |
 | + fabrique     | <-------------  | + fabrique spécialisée    |
 | + services 1   |                 | + services 1 spécialisés  |
 |                |                 | + services 2 (monoïde)    |
 ------------------                 -----------------------------
	∧                                        ∧
	|                                        |  
-------------------                 ----------------------------    
|   Implem basse  |                 |      Implem haute        |                                                
|   (classe)      |                 |      (interface)         |
| - état : liste  |                 | +$ services 2 (monoïde)  |
| + accesseurs    |                 |    implémentés           |
| + fabrique      |                 |                          |
| # fabrique      |                 |                          |
|   liste -> file |                 |                          |
| # services liste|                 |                          |
| + services 1    |                 |                          |
-------------------                 ----------------------------    
	∧                                        ∧
	|                                        |
	------------------------------------------
			   |
	       ---------------------------
	       |    Implem (classe)      |
	       |+ fabrique spécialisée   |
	       |# fabrique liste-> file  |
	       |  spécialisée            |
	       |+ services 1 spécialisés |
	       ---------------------------

2.5 Implémentation par agrégation et délégation

Pour chaque interface implémentant la couche haute (récursivement et itérativement respectivement), définir une classe d'implémentation

  • agrégeant une file simple,
  • déléguant à cette file simple la réalisation des services de la couche basse,
  • héritant de l'interface les services de la couche haute.

Il est possible de factoriser le code dans une classe abstraite réalisant la délégation. Cette classe implémente la couche basse de l'interface enrichie des files à priorité. Elle contient :

  • une file simple à priorité,
  • une fabrique abstraite agrégeant une file simple dans une file enrichie,
  • les méthodes de la couche basse implémentées par délégation en utilisant la file agrégée puis par agrégation du résultat à une nouvelle file enrichie, en utilisant la fabrique abstraite.

Voici le schéma décrivant une telle solution par agrégation et délégation.

------------------                 -----------------------------
| File à priorité|                 |      File Enrichie        | 
| + accesseurs   |                 | + accesseurs              |
| + fabrique     | <-------------  | + fabrique spécialisée    |
| + services 1   |                 | + services 1 spécialisés  |
|                |                 | + services 2 (monoïde)    |
------------------                 -----------------------------
	∧                           ∧                        ∧
	|                           |                        |  
	|                   -------------------    ---------------------------     
	|                  |     Délégation   |    |     Implem haute        |                                                
	|   instance       |(classe abstraite)|    |     (interface)         |
	-------------------| - état : file    |    | +$ services 2 (monoïde) |
			   | #@ fabrique      |    |    implémentés          |
			   |    agrégeant     |    |                         |
			   | + accesseurs     |    |                         |
			   | + fabrique       |    |                         |
			   | + services 1     |    |                         |
			   -------------------     ---------------------------     
				    ∧                          ∧
				    |                          |
				    ----------------------------
						 |
				     ---------------------------
				     |    Implem (classe)      |
				     | # fabrique agrégeant    |
				     ---------------------------

2.6 Calculs génériques dans les monoïdes

Définir une fonction spécifiée ainsi :

  • fonction générique applicable à tout type T ayant la propriété d'être un monoïde,
  • deux paramètres : une liste d'éléments de type java.util.List<T> et un élément du type T,
  • résultat : la somme des éléments de la liste.

On utilisera un parallel stream et la méthode reduce. Tester en utilisant des files à priorité. Vous devriez observer une utilisation de tous les cœurs de votre machine.

Remarque. Pour utiliser les files obtenues par agrégation, il est nécessaire d'injecter une file simple lors de la construction : c'est un exemple d'injection de dépendances.

3 Consignes et livrables

  • Utiliser une et une seule branche git pour tous vos développements. Choisir un nom suffisamment long et original pour éviter tout conflit. Seul le contenu de votre branche sera considéré.
  • Définir un fichier README dans le répertoire 2020 du dépôt. Celui-ci doit contenir au moins les informations suivantes :
    • le nom de la branche utilisée,
    • la composition du groupe,
    • les conventions de nommage
  • Définir les interfaces et les classes d'implémentation dans le paquet file.session2, à placer dans le répertoire 2020/java/src/file/session2.

Author: Hervé Grall
Version history: v1: 2019-10-11.
Comments or questions: Send a mail.
The webpage content is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.