Examen intermédiaire
corrigé

Dates empaquetées

Partie 1

La méthode isLeapYear est une simple traduction en Java de l'énoncé, dans laquelle l'opérateur de calcul du reste de la division (%) est utilisé pour déterminer si l'année est ou n'est pas un multiple de 4, 100 ou 400.

public static boolean isLeapYear(int y) {
  if (! (0 < y && y <= 3000))
    throw new IllegalArgumentException();

  return (y % 4 == 0 && y % 100 != 0) || (y % 400 == 0);
}

Partie 2

La manière la plus simple d'écrire daysInMonth est probablement d'utiliser un énoncé switch pour distinguer les trois cas : mois à 31 jours, mois à 30 jours, et février.

public static int daysInMonth(int y, int m) {
  if (! (0 < y && y <= 3000))
    throw new IllegalArgumentException();

  switch (m) {
  case 1: case 3: case 5: case 7: case 8: case 10: case 12:
    return 31;
  case 4: case 6: case 9: case 11:
    return 30;
  case 2:
    return isLeapYear(y) ? 29 : 28;
  default:
    throw new IllegalArgumentException();
  }
}

Partie 3

Étant donné l'existence des attributs YEAR_START, MONTH_START et DAY_START, la méthode pack est simple à écrire : il suffit de décaler chaque composante afin que son bit de poids faible se trouve à la bonne position, puis d'utiliser un « ou » bit à bit pour combiner les composantes ainsi décalées.

public static int pack(int y, int m, int d) {
  if (! (0 < y && y <= 3000))
    throw new IllegalArgumentException();
  if (! (0 < m && m <= 12))
    throw new IllegalArgumentException();
  if (! (0 < d && d <= daysInMonth(y, m)))
    throw new IllegalArgumentException();
  return ((y << YEAR_START)
	  | (m << MONTH_START)
	  | (d << DAY_START));
}

A noter que comme DAY_START vaut 0, il n'est pas strictement nécessaire d'effectuer le dernier décalage, mais le code est plus clair et plus robuste ainsi.

Partie 4

L'extraction du mois implique de faire deux choses :

décaler la date empaquetée pour que le bit de poids faible du mois se trouve à l'index 0,
masquer la date ainsi décalée afin de ne garder que les bits correspondant au mois, en mettant à 0 ceux de l'année.

L'ordre de ces deux opérations peut bien entendu être échangé, pour peu que le masque soit ajusté en fonction.

Le calcul du masque se fait en combinant un décalage est une soustraction, comme expliqué dans le cours.

public static int month(int pkDate) {
  int mMask = (1 << MONTH_SIZE) - 1;
  return (pkDate >> MONTH_START) & mMask;
}

Partie 5

La seule petite difficulté que présente toString est le fait que le mois et le jour doivent toujours être écrits avec deux chiffres, en plaçant un 0 en tête au besoin. Cela n'est nécessaire que si la valeur est inférieure à 10, et le test s'effectue très naturellement au moyen de l'opérateur ternaire (?:):

public static String toString(int pkDate) {
  int m = month(pkDate);
  int d = day(pkDate);
  return (String.valueOf(year(pkDate))
	  + (m < 10 ? "-0" : "-") + m
	  + (d < 10 ? "-0" : "-") + d);
}

Il est également possible d'utiliser la méthode format de String pour obtenir le même résultat de manière encore plus simple :

public static String toString(int pkDate) {
  return String.format("%d-%02d-%02d",
		       year(pkDate),
		       month(pkDate),
		       day(pkDate));
}

Partie 6

Non, car la méthode toString de PackedDate n'est pas une redéfinition de la méthode toString de Object, pour deux raisons : d'une part elle est statique, et d'autre part elle prend un argument alors que la méthode de Object n'en prend aucun.

Dates

Partie 1

Pour mettre en œuvre la classe Date au moyen de PackedDate, l'idée est bien entendu de n'y stocker qu'un seul attribut, la date empaquetée. Cet attribut est final car la classe est immuable.

Le constructeur privé ne fait rien d'autre qu'initialiser cet attribut avec la valeur qu'on lui passe en argument.

La méthode of appelle ce constructeur avec la version empaquetée de la date dont les composantes lui sont passées en argument, qu'elle obtient au moyen de la méthode pack de PackedDate.

public final class Date {
  private final int pkDate;

  public static Date of(int year, int month, int day) {
    return new Date(PackedDate.pack(year, month, day));
  }

  private Date(int pkDate) {
    this.pkDate = pkDate;
  }

  // … à compléter
}

Partie 2

Oui, car il s'agit d'une classe immuable, et il faut donc que ses instances soient comparées de manière structurelle : deux dates qui représentent le même jour doivent être considérées comme égales même s'il s'agit d'objets Java différents.

La méthode equals doit donc vérifier si la date empaquetée de this est identique à celle de son argument, après avoir vérifié que ce dernier est lui aussi une instance de Date.

La méthode hashCode se contente de retourner la date empaquetée, qui constitue une excellente valeur de hachage car elle garantit que deux dates différentes ont une valeur de hachage différente.

@Override
public boolean equals(Object thatO) {
  return (thatO instanceof Date)
    && (pkDate == ((Date)thatO).pkDate);
}

@Override
public int hashCode() {
  return pkDate;
}

Partie 3

La classe Date doit implémenter l'interface Comparable instanciée comme d'habitude avec le type de la classe elle-même, ici Date. Pour mémoire, cette utilisation surprenante de la généricité permet de garantir que le type de l'argument de compareTo est le même que celui du récepteur (this).

La méthode compareTo peut être mise en œuvre très facilement si on se rend compte que la technique d'empaquetage utilisée permet de comparer les versions empaquetées des dates comme s'il s'agissait d'entiers. On peut dès lors simplement appliquer la méthode compare de Integer aux deux dates empaquetées.

public final class Date implements Comparable<Date> {
  // … comme avant

  @Override
  public int compareTo(Date that) {
    return Integer.compare(this.pkDate, that.pkDate);
  }
}

Ensemble d'énumération

Partie 1

La méthode noneOf est triviale à définir, car un ensemble vide est représenté par l'entier 0, qu'il suffit de passer au constructeur en même temps que le tableau values reçu en argument.

static <E extends Enum<E>> EnumSet<E> noneOf(E[] values) {
  return new EnumSet<E>(values, 0);
}

Partie 2

Pour mettre en œuvre range, il faut calculer une valeur de type long dont les seuls bits à 1 sont ceux correspondant aux éléments compris entre from et to, inclus.

Si l'on nomme fromI l'index du bit correspondant à la valeur from et toI l'index du bit correspondant à la valeur to, on peut observer que :

le nombre de bits à 1 est : toI - fromI + 1,
le premier d'entre eux est à l'index fromI,
ces bits sont contigus.

En combinant ces observations, on conclut que la valeur représentant l'ensemble se calcule en :

générant une première valeur (mask ci-dessous) dont le bon nombre de bits de poids faible sont à 1,
décalant cette valeur à gauche de fromI positions.

En traduisant cela en Java, on obtient la méthode range ci-dessous. Attention à ne pas oublier d'utiliser la constante 1L (de type long) plutôt que 1 (de type int) dans le calcul du masque, faute de quoi le résultat obtenu est incorrect !

static <E extends Enum<E>> EnumSet<E> range(E[] values,
					    E from,
					    E to) {
  int fromI = from.ordinal(), toI = to.ordinal();
  if (! (fromI <= toI))
    throw new IllegalArgumentException();

  long mask = (1L << (toI - fromI + 1)) - 1;
  return new EnumSet<>(values, mask << fromI);
}

Partie 3

La méthode isEmpty est triviale puisque, comme nous l'avons dit, l'ensemble vide est représenté par l'entier 0.

La méthode size doit simplement retourner le nombre de bits valant 1 dans l'entier représentant l'ensemble, ce qui se fait facilement au moyen de la méthode bitCount de Long.

public boolean isEmpty() {
  return set == 0;
}

public int size() {
  return Long.bitCount(set);
}

Partie 4

La méthode contains doit vérifier si le bit correspondant à l'élément vaut 1, ce qui se fait aisément au moyen d'un masque et d'un « et » bit à bit.

La méthode containsAll est presque encore plus simple puisqu'il n'y a pas besoin de construire un masque, celui-ci n'est autre que l'entier représentant le second ensemble !

public boolean contains(E e) {
  return (set & 1L << e.ordinal()) != 0;
}

public boolean containsAll(EnumSet<E> that) {
  return (this.set & that.set) == that.set;
}

Partie 5

La méthode add met à 1 le bit correspondant à l'élément, ce qui se fait encore une fois au moyen d'un masque, puis d'un « ou » bit à bit. Pour déterminer si l'ensemble a changé en raison de l'ajout, il suffit de comparer l'ancien entier représentant l'ensemble avec le nouveau.

La méthode addAll met à 1 tous les bits correspondants aux éléments du second ensemble, ce qui se fait au moyen d'un simple « ou » bit à bit.

public boolean add(E e) {
  long oldSet = set;
  set |= 1L << e.ordinal();
  return set != oldSet;
}

public boolean addAll(EnumSet<E> that) {
  long oldSet = set;
  set |= that.set;
  return set != oldSet;
}

Partie 6

La méthode toString se réalise très facilement au moyen d'un « joigneur » de chaînes de type StringJoiner dont le contenu est calculé en :

itérant sur toutes les valeurs du type énuméré, qui sont disponibles dans l'attribut values,
regardant, pour chacune d'elle, si elle appartient à l'ensemble,
si oui, ajoutant sa représentation textuelle au joigneur de chaînes.

@Override
public String toString() {
  StringJoiner j = new StringJoiner(",", "{", "}");
  for (E e: values) {
    if (contains(e))
      j.add(e.toString());
  }
  return j.toString();
}

Dictionnaire pour mots croisés

La manière la plus simple de représenter le dictionnaire pour mots croisés est d'utiliser une table associative dont les clefs sont les longueurs de mots, et les valeurs sont les ensembles de mots de cette longueur. En d'autres termes, on représente le dictionnaire au moyen d'une valeur de type :

Map<Integer, Set<String>>

Cette décision prise, il reste à choisir la mise en œuvre des tables associatives et ensembles à utiliser, et ici un choix s'impose rapidement : il faut utiliser TreeMap et TreeSet, car elles trient leurs clefs/éléments, ce qui est exactement ce que l'on désire.

Une fois ce choix effectué, le code s'écrit facilement.

public final class CrosswordDict {
  private final Map<Integer, Set<String>> dict =
    new TreeMap<>();

  public void add(String word) {
    if (word.isEmpty())
      throw new IllegalArgumentException();

    Set<String> s = dict.get(word.length());
    if (s == null) {
      s = new TreeSet<>();
      dict.put(word.length(), s);
    }
    s.add(word);
  }

  public void addAll(Collection<String> words) {
    for (String word: words)
      add(word);
  }

  public void print() {
    for (Map.Entry<Integer, Set<String>> e: dict.entrySet()) {
      System.out.println("Mots de "+ e.getKey() +" lettres :");
      for (String s: e.getValue())
	System.out.println("  " + s);
    }
  }
}

On notera qu'au moyen des méthodes des collections acceptant des lambdas, la classe CrosswordDict peut être écrite de manière plus claire et plus concise :

public final class CrosswordDictL {
  private final Map<Integer, Set<String>> dict =
    new TreeMap<>();

  public void add(String word) {
    if (word.isEmpty())
      throw new IllegalArgumentException();

    dict
      .computeIfAbsent(word.length(), k -> new TreeSet<>())
      .add(word);
  }

  public void addAll(Collection<String> words) {
    words.forEach(w -> add(w));
  }

  public void print() {
    dict.forEach((l, s) -> {
	System.out.println("Mots de "+ l +" lettres :");
	s.forEach(w -> System.out.println("  " + w));
      });
  }
}

Examen intermédiaire corrigé

Dates empaquetées

Partie 1

Partie 2

Partie 3

Partie 4

Partie 5

Partie 6

Dates

Partie 1

Partie 2

Partie 3

Ensemble d'énumération

Partie 1

Partie 2

Partie 3

Partie 4

Partie 5

Partie 6

Dictionnaire pour mots croisés

Examen intermédiaire
corrigé