Guava : Classer les éléments d’une collection

Pour certains algorithmes, nous avons besoin de classer des éléments selon une de leur propriété.

Nous allons voir dans un premier temps comment classer une liste d'objets de manière classique, puis nous verrons comment le faire plus simplement à l'aide des bibliothèques common-collections d'Apache et guava de Google.

Cas pratique

Nous prenons comme exemple la liste de livres d'une bibliothèque.

Nous souhaitons avoir le classement des ouvrages selon leur auteur de la manière suivante :

 - Auteur : Jules Vernes
    - Cinq semaines en ballon, 1863
    - Voyage au centre de la Terre, 1864
    - De la Terre à la Lune, 1865
 - Auteur : Rudyard Kipling
    - Le livre de la jungle, 1894
    - Le second livre de la jungle, 1895

Classer des objets

En Java, ce classement s'effectuerait de la manière suivante :

Nous avons la collection de type Map<clé, Collection<valeur>> qui permet de stocker pour chaque clé plusieurs valeurs.

Ainsi dans notre exemple, nous avons pour la clé auteur un ou plusieurs livres.

// Livres classés par auteur
Map<String, Collection<Livre>> livresParAuteurs =
    new HashMap<String, Collection<Livre>>();

Boucle de classement

La valorisation de ce tableau peut s'effectuer via le traitement suivant qui consiste à parcourir la liste des livres et pour chaque livre d'ajouter ce livre à la liste de ceux de l'auteur.

// Parcourt les livres
for (Livre livre : livres)
{
    // Auteur du livre
    String auteur = livre.getAuteur();

    // Liste des livres de l'auteur
    Collection<Livre> livresParAuteur = livresParAuteurs.get(auteur);

    // Créer la liste si elle n'existe pas
    if (livresParAuteur == null)
    {
        livresParAuteur = new ArrayList<Livre>();
        livresParAuteurs.put(auteur,
                             livresParAuteur);
    }

    // Ajoute le livre à la liste des livres de l'auteur
    livresParAuteur.add(livre);
}

Nous remarquons qu'une partie de ce code est redondant, il s'agit de créer la liste de livres dans le cas où elle n'existe pas déjà pour l'auteur.

Nous pouvons améliorer cela à l'aide du type Multimap.

Guava : MultiMap

L'interface Multimap<clé, valeur> correspond à la collection Map<clé, Collection<valeur>>.

Elle permet de gérer la création d'une nouvelle liste d'éléments pour tout nouvel ajout dans le tableau.

Il existe une implémentation de Multimap pour les bibliothèques common-collections d'Apache et guava de Google. Nous choisissons ici la bibliothèque guava de Google car elle supporte par défaut les types génériques.

Différence entre Multimap et Map

Cependant, il ne s'agit pas exactement de la collection Map<clé, Collection<valeur>>.
En effet, comme expliqué sur le wiki de Guava, Multimap ne se comporte pas exactement comme la collection Map, notamment au niveau de la gestion de la liste d'éléments dans le cas où aucune valeur n'est présente pour une clé.
Par exemple, Multimap retournera toujours une liste vide et jamais nulle dans le cas où aucun élément n'a été ajouté pour une clé du tableau.

Ceci est détaillé dans la documentation : Multimap is not a map

Multimap : Implémentations possibles

Les implémentations de Multimap<clé, valeur> correspondent à une implémentation possible Map<clé,Collection<valeur>>.

Les plus communes sont :

  • ArrayListMultimap<clé, valeur> => HashMap<clé, ArrayList<valeur>>
  • HashMultimap<clé, valeur> => HashMap<clé, HashSet<valeur>>
  • TreeMultimap<clé, valeur> => TreeMap<clé, TreeSet<valeur>>

Elles sont détaillées sur le wiki de Guava : Implémentations

Instanciation de Multimap

L'instanciation s'effectue via l'interface de la classe d'implémentation de la collection, ici ArrayListMultimap :

// Livres classés par auteur
final Multimap<String, Livre> livresParAuteurs = 
    ArrayListMultimap.create();

Ainsi le code précédent se simplifie car le code de création de la liste n'est plus utile :

for (final Livre livre : livres)
{
    // Auteur du livre
    final String auteur = livre.getAuteur();

    // Livres par auteur
    livresParAuteurs.put(auteur,
                         livre);
}

Cependant, hormis pour la récupération de l'auteur à partir de l'objet Livre, ce code n'a pas réellement de valeur ajoutée.

Nous pouvons de nouveau améliorer ce code pour ne plus avoir à parcourir nous-même, ni à gérer l'ajout des éléments dans le tableau.

Utilisation de Function

L'interface Function de guava correspond à une transformation d'un objet vers un autre objet.

Ainsi cette interface a deux types génériques, le type de l'objet initial et le type de l'objet qui sera en résultat de la fonction.

Function<initial, final>

L'interface impose l'implémentation de la méthode apply qui prend en paramètre l'objet à transformer et qui retourne le résultat de cette transformation.

public interface Function<F, T> {
    T apply(@Nullable F input);
}

Function

Dans notre exemple, nous allons utiliser cette interface Function pour définir une classe qui sera chargée de retourner l'auteur à partir de l'objet Livre :

Function<Livre, String> getAuteurFromLivreFunction = 
    new Function<Livre, String>() {
        public String apply(final Livre livre)
        {
            return livre.getAuteur();
        }
};

Multimaps.index

De plus, guava dispose de la méthode index via la classe Multimaps.

Cette méthode prend en paramètre la collection à traiter ainsi que la fonction qui va fournir la clé correspondant à chaque objet de la collection. Ceci permettra de définir pour une même clé tous les éléments associés de la collection.

Dans notre exemple, nous avons ainsi l'appel suivant :

final Multimap<String, Livre> livresParAuteurs =
    Multimaps.index(livres,
                    getAuteurFromLivreFunction);

Ceci permet de ne se focaliser que sur la gestion de la clé associée à chaque élément et non sur la façon dont le tableau est alimenté.

Conclusion

L'utilisation de la bibliothèque Guava de Google permet de simplifier l'écriture d'algorithmes basés sur des collections en Java.

Il est intéressant de lire la documentation de cette bibliothèque et de s'en inspirer pour améliorer nos pratiques et sur notre façon d'implémenter nos solutions.

L'interface Function tout comme Predicate permettent d'externaliser une partie du code spécifique et de les utiliser ainsi avec les méthodes de traitement génériques déjà implémentés dans Guava. Connaître ces méthodes permet de gagner du temps, réduit les risques d'erreurs et simplifie le code à écrire.

Références

Guava de Google

Site

Documentation

Dépendance Maven

<dependency>
    <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
    <version>13.0.1</version>
</dependency>

2 commentaires

  1. Pour info, l’équivalent de l’interface Function<Initial,Final> de Guava est l’interface Transformer d’Apache, même si comme tu l’as dit, la première a l’avantage de gérer la généricité.

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *

Captcha *

Ce site utilise Akismet pour réduire les indésirables. En savoir plus sur comment les données de vos commentaires sont utilisées.