Examen intermédiaire : corrigé

Il y a trois points auxquels il faut penser lors de l'écriture du constructeur :

1. la classe Polynomial est immuable, donc la table des coefficients reçue doit être copiée, puis idéalement rendue non modifiable (même si ce n'est pas strictement nécessaire),
2. les coefficients nuls éventuellement présents dans la table donnée en argument ne doivent pas être stockés,
3. la présence d'un degré négatif doit être détectée et produire la levée de l'exception IllegalArgumentException.

Ces trois points peuvent être gérés dans le cadre d'une boucle qui parcourt la table des coefficients, vérifie que le degré de chacun est positif ou nul, et copie les coefficients non nuls dans la nouvelle table.

C'est cette approche qui est suivie dans le code ci-dessous, dans lequel on prend de plus soin de choisir TreeMap comme mise en œuvre de la table des coefficients, ce qui simplifie l'écriture de la méthode toString plus tard.

public Polynomial(Map<Integer, Integer> coefs) {
    Map<Integer, Integer> nonZeroCoefs = new TreeMap<>();
    for (Map.Entry<Integer, Integer> e: coefs.entrySet()) {
        if (e.getKey() < 0)
            throw new IllegalArgumentException();
        if (e.getValue() != 0)
            nonZeroCoefs.put(e.getKey(), e.getValue());
    }
    this.coefs = Collections.unmodifiableMap(nonZeroCoefs);
}

La méthode add doit construire une table de coefficients pour la somme des polyômes en combinant les coefficients de la table du récepteur avec ceux de la table du polynôme passé en argument, puis l'utiliser pour créer un nouveau polynôme qu'elle retourne.

Cela peut se faire de différentes manières, la technique utilisée ci-dessous consistant à :

1. dans un premier temps, copier la totalité des coefficients de l'argument dans la table résultat, au moyen du constructeur de copie,
2. ensuite, parcourir les coefficients du polynôme récepteur, et les combiner avec ceux déjà présents dans la table ; une manière simple de faire cette combinaison est d'utiliser la méthode getOrDefault pour obtenir soit le coefficient déjà présent dans la table, soit 0.

public Polynomial add(Polynomial that) {
    Map<Integer, Integer> summedCoefs =
        new HashMap<>(that.coefs);
    for (Map.Entry<Integer, Integer> e: coefs.entrySet()) {
        int c = summedCoefs.getOrDefault(e.getKey(), 0);
        summedCoefs.put(e.getKey(), c + e.getValue());
    }
    return new Polynomial(summedCoefs);
}

La méthode valueAt peut s'écrire simplement en parcourant les paires (degré \(d\), coefficient \(c\)) de la table, de les utiliser pour calculer le terme \(c\cdot x^d\) puis de faire la somme de ces termes.

public double valueAt(double x) {
    double r = 0;
    for (Map.Entry<Integer, Integer> e: coefs.entrySet())
        r += e.getValue() * Math.pow(x, e.getKey());
    return r;
}

Comme la table des coefficients n'inclut pas les coefficients nuls, on a la garantie que deux polynômes sont égaux si et seulement si leurs tables de coefficients sont égales. Cela se vérifie facilement au moyen de la méthode equals appliquée à ces tables, les collections Java étant comparées de manière structurelle.

@Override
public boolean equals(Object thatO) {
    return (thatO instanceof Polynomial)
        && coefs.equals(((Polynomial)thatO).coefs);
}

Pour la même raison, la méthode hashCode peut se contenter de retourner la valeur de hachage de la table des coefficients.

@Override
public int hashCode() {
    return coefs.hashCode();
}

Bien entendu, il n'est pas faux d'utiliser la méthode Objects.hash, mais cela est légèrement plus coûteux.

Non, il ne serait pas judicieux que la classe Polynomial implémente l'interface Comparable, car il n'existe pas de notion d'ordre naturelle pour les polynômes en mathématiques.

La méthode toString serait relativement simple à écrire s'il n'était pas demandé qu'elle produise des chaînes minimales sans facteurs, exposants ou signes + superflus. Dans ce cas simple, il suffirait de parcourir les entrées de la table des coefficients en produisant pour chacun d'eux une chaîne composée de :

• le coefficient, toujours précédé de son signe (+ ou -),
• la chaîne x représentant l'indéterminée,
• la chaîne ^ représentant l'exponentiation,
• l'exposant.

En ajoutant ces chaînes successives à un bâtisseur de chaîne, on obtiendrait soit la chaîne désirée, soit la chaîne vide pour le cas du polynôme 0. Dans ce dernier cas, il suffirait de retourner la chaine 0.

Notez qu'on fait ci-dessus l'hypothèse que les termes sont parcourus par degré croissant, ce qui est le cas si on a pris soin de les stocker dans une table de type TreeMap. Sinon, il faut au préalable placer les degrés (donc les clefs) de la table dans une liste puis la trier, ce qui complique et ralentit les choses.

La chaîne produite par la méthode décrite ci-dessus n'est malheureusement pas minimale, contrairement à ce que demande l'énoncé. Pour qu'elle le soit, il faut en supprimer (ou plutôt ne pas y ajouter) toutes les parties superflues, qui sont :

• le signe + en tout début de la chaîne,
• tout coefficient de degré supérieur à zéro et égal à ±1, pour lequel le signe suffit,
• la partie ^1 pour le coefficient de degré 1,
• la partie x^0 pour le coefficient de degré 0.

En combinant l'idée de la méthode simple avec les tests permettant de ne pas inclure ces parties superflues, on obtient la méthode toString ci-dessous :

@Override
public String toString() {
    StringBuilder b = new StringBuilder();
    for (Map.Entry<Integer, Integer> e: coefs.entrySet()) {
        int d = e.getKey(), c = e.getValue();

        if (d == 0)
            b.append(c);
        else {
            if (c < 0 || b.length() > 0)
                b.append(c < 0 ? "-" : "+");

            int cAbs = Math.abs(c);
            if (cAbs != 1)
                b.append(cAbs);
            b.append("x");
            if (d > 1)
                b.append("^").append(d);
        }
    }
    return b.length() == 0 ? "0" : b.toString();
}

La définition de l'interface fonctionnelle représentant un comparateur partiel ne pose pas de difficulté, il suffit de penser à en faire une interface générique (comme Comparator, pour la simple raison que le type exact des objets à comparer peut varier) et de donner le bon type à sa méthode abstraite. On obtient :

public interface PartialComparator<T> {
    boolean lessOrEqual(T x, T y);
}

Sachant qu'un comparateur retourne une valeur négative ou nulle si le premier objet qu'on lui passe est inférieur ou égal au second, la définition de la méthode ofTotal est simple :

static <T> PartialComparator<T> ofTotal(Comparator<T> c) {
    return (x, y) -> c.compare(x, y) <= 0;
}

Finalement, la méthode comparable est une simple traduction en Java du texte de l'énoncé, qui dit que deux objets sont comparables si l'un des deux est inférieur ou égal à l'autre :

default boolean comparable(T x, T y) {
    return lessOrEqual(x, y) || lessOrEqual(y, x);
}