Série 4 – Diagrammes tige et feuille : corrigé

Introduction

Le code du corrigé est fourni sous la forme d'une archive Zip, et des explications concernant les principales difficultés des exercices sont données ci-dessous.

Exercice 1 : Diagramme unidirectionnel

La méthode print est composée de deux étapes distinctes :

  1. la création de la table associant la liste des feuilles aux tiges,
  2. l'affichage du diagramme correspondant à cette table.

La première étape peut être confiée à une méthode séparée, nommée stems ci-dessous, d'une part pour des raisons de clareté, et d'autre part pour permettre sa réutilisation pour l'exercice 2.

La méthode stems parcourt les données, et pour chacune d'entre elles calcule la tige (stem) et la feuille (leaf). Cela fait, elle regarde si la tige est déjà présente dans la table, et si tel est le cas, ajoute la feuille à sa liste. Sinon, elle ajoute à la table une nouvelle association entre la tige et une liste composée uniquement de la feuille. Une fois la totalité des données insérées dans la table, les listes des feuilles sont triées : 

Map<Integer, List<Integer>> stems(Collection<Integer> is){
  Map<Integer, List<Integer>> stems = new HashMap<>();
  for (int i: is) {
    int stem = i / 10, leaf = i % 10;
    if (stems.containsKey(stem))
      stems.get(stem).add(leaf);
    else
      stems.put(stem,
                new ArrayList<>(Arrays.asList(leaf)));
  }
  for (List<Integer> leaves: stems.values())
    Collections.sort(leaves);
  return stems;
}

En plus de la méthode stems, on peut écrire deux autres méthodes auxiliaires réutilisables pour l'exercice 2. La première permet d'obtenir la chaîne correspondant aux feuilles d'une tige donnée, éventuellement renversée (ce qui est utile pour l'exercice 2) : 

String leavesString(Map<Integer, List<Integer>> stems,
                    int stem,
                    boolean reversed) {
  StringBuilder b = new StringBuilder();
  List<Integer> leaves =
    stems.getOrDefault(stem, Collections.emptyList());
  for (Integer i: leaves)
    b.append(i);
  return (reversed ? b.reverse() : b).toString();
}

La seconde permet d'obtenir la chaîne de formattage à passer à la méthode format pour aligner les tiges, étant donné la valeur de la plus grande tige. Cette chaîne de formattage est composée du caractère %, suivi de la largeur maximale des tiges, suivi du caractère d. La largeur maximale s'obtient simplement en arrondissant vers le haut le logarithme en base 10 de la plus grande tige : 

String formatForMaxStem(int maxStem) {
  return "%" + (int)Math.ceil(Math.log10(maxStem)) + "d";
}

Ces méthodes écrites, la méthode print est simple à réaliser. Il faut toutefois penser à énumérer toutes les tiges entre la plus petite et la plus grande (au lieu d'itérer sur les clefs de la table stems) afin d'éviter les trous dans le diagramme : 

void print(Collection<Integer> data) {
  Map<Integer, List<Integer>> stems = stems(data);

  int minStem = Collections.min(stems.keySet());
  int maxStem = Collections.max(stems.keySet());
  String stemFmt = formatForMaxStem(maxStem);

  for (int stem = minStem; stem <= maxStem; ++stem) {
    System.out.println(String.format(stemFmt, stem) + '|'
                       + leavesString(stems, stem,false));
  }
}

Utilisation de computeIfAbsent

Comme sa documentation l'explique, la méthode computeIfAbsent regarde si la table contient déjà la clef qu'on lui passe, et si tel est le cas, la retourne. Sinon, elle utilise la fonction qu'on lui passe, appliquée à la clef, pour obtenir une nouvelle valeur, insère l'association (clef, valeur) dans la table, puis retourne la valeur.

Ce comportement est exactement celui que nous avons exprimé plus haut au moyen d'un énoncé if et des méthodes containsKey, get et put. Dès lors, on peut simplifier le corps de la boucle de la méthode stems au moyen de computeIfAbsent ainsi : 

Map<Integer, List<Integer>> stems(Collection<Integer> is){
  Map<Integer, List<Integer>> stems = new HashMap<>();
  for (int i: is) {
    stems
      .computeIfAbsent(i / 10, k -> new ArrayList<>())
      .add(i % 10);
  }
  for (List<Integer> leaves: stems.values())
    Collections.sort(leaves);
  return stems;
}

Notez qu'il est de plus possible de simplifier le tri des feuilles, au moyen de la méthode forEach déjà examinée, en récrivant la boucle de tri ainsi : 

stems.values().forEach(Collections::sort);

Comme cet exemple l'illustre, les lambdas (et les références de méthodes dans ce cas précis) permettent souvent de rendre le code très concis.

Exercice 2 : Diagramme bidirectionnel

Le dessin d'un diagramme bidirectionnel n'est pas beaucoup plus compliqué que celui d'un diagramme unidirectionnel une fois les méthodes auxiliaires ci-dessus écrites. 

void print(Collection<Integer> left,
           Collection<Integer> right) {
  Map<Integer, List<Integer>> lStems = stems(left);
  Map<Integer, List<Integer>> rStems = stems(right);

  int lWidth = 0;
  for (List<Integer> l: lStems.values())
    lWidth = Math.max(lWidth, l.size());
  String lFmt = "%" + lWidth + "s";

  int minStem =
    Math.min(Collections.min(lStems.keySet()),
             Collections.min(rStems.keySet()));
  int maxStem =
    Math.max(Collections.max(lStems.keySet()),
             Collections.max(rStems.keySet()));
  String stemFmt = formatForMaxStem(maxStem);

  for (int stem = minStem; stem <= maxStem; ++stem) {
    String lLeaves = leavesString(lStems, stem, true);
    String rLeaves = leavesString(rStems, stem, false);
    System.out.println(String.format(lFmt, lLeaves)
                       + '|' + String.format(stemFmt,stem)
                       + '|' + rLeaves);
  }
}