Examen intermédiaire : corrigé

Itérateur de liste

Cet exercice consistait simplement à reprendre l'itérateur de liste écrit pour l'exercice 2 de la série 5 et de l'adapter pour qu'il fasse le parcours à l'envers — en suivant les liens pred plutôt que les liens succ — et qu'il soit défini sous forme de classe imbriquée anonyme.

Pour savoir si l'appel à la méthode remove est valide, on peut soit utiliser la variable booléenne canRemove comme dans la série 5, soit une référence vers le dernier nœud retourné par next comme dans la série 7. C'est cette dernière solution qui a été retenue ci-dessous. 

public Iterator<E> reverseIterator() {
    return new Iterator<E>() {
        private Node<E> prev = head.pred, last = null;

        @Override
        public boolean hasNext() {
            return prev != head;
        }

        @Override
        public E next() {
            if (! hasNext())
                throw new NoSuchElementException();
            last = prev;
            prev = prev.pred;
            return last.value;
        }

        @Override
        public void remove() {
            if (last == null)
                throw new IllegalStateException();
            removeNode(last);
            last = null;
        }
    };
}

Grands nombres

Partie 1 – constructeur

Le constructeur de BigInteger doit premièrement vérifier la validité de la liste de chiffres reçue — selon les indications de l'énoncé — puis la copier afin de garantir l'immuabilité de la classe.

La vérification se fait par parcours de la liste des chiffres reçue, tandis que la copie se fait au moyen du constructeur de copie de l'une des listes mettant en œuvre l'interface List, p.ex. ArrayList. 

public BigInteger(List<Integer> digits) {
    boolean endsWithZero = false;
    for (int d: digits) {
        if (! (0 <= d && d <= 9))
            throw new IllegalArgumentException();
        endsWithZero = (d == 0);
    }
    if (endsWithZero)
        throw new IllegalArgumentException();

    this.digits = new ArrayList<>(digits);
}

Partie 2 – méthode toString

Deux petites difficultés existent pour la méthode toString : d'une part les chiffres sont stockés dans l'ordre inverse de l'ordre dans lequel ils doivent apparaître dans la représentation textuelle, et d'autre part l'entier 0 constitue un cas particulier.

Pour gérer le problème de l'ordre, le plus simple consiste à construire la chaîne en commençant par le chiffre de poids faible (en tête de liste), puis à renverser la chaîne obtenue au moyen de la méthode reverse de la classe StringBuilder.

Quant au cas de l'entier 0, le plus simple est de le gérer séparément. 

public String toString() {
    if (digits.isEmpty())
        return "0";
    else {
        StringBuilder b = new StringBuilder();
        for (int d: digits)
            b.append(d);
        return b.reverse().toString();
    }
}

Partie 3 – méthode add

L'addition de deux grands nombres se fait selon la technique standard consistant à additioner les chiffres les uns après les autres, par poids croissant, en prenant en compte une éventuelle retenue (carry en anglais et dans le code ci-dessous).

La retenue peut être représentée par un entier — qui ne vaut que 0 ou 1 — ou un booléen. C'est cette deuxième solution qui a été choisie ci-dessous. 

public BigInteger add(BigInteger that) {
    boolean carry = false;
    List<Integer> sum = new LinkedList<>();
    Iterator<Integer> thisIt = this.digits.iterator();
    Iterator<Integer> thatIt = that.digits.iterator();
    while (thisIt.hasNext() || thatIt.hasNext()) {
        int thisD = thisIt.hasNext() ? thisIt.next() : 0;
        int thatD = thatIt.hasNext() ? thatIt.next() : 0;
        int res = thisD + thatD + (carry ? 1 : 0);
        sum.add(res % 10);
        carry = res >= 10;
    }
    if (carry)
        sum.add(1);
    return new BigInteger(sum);
}

Multi-ensemble

Partie 1 – méthode count

La méthode count consulte la table associative des nombres d'occurrence et retourne 0 si aucune entrée n'existe dans cette table, ou le nombre associé à l'élément sinon. Pour vérifier la présence de l'élément dans la table, on peut soit utiliser la méthode containsKey, soit utiliser le fait que la méthode get retourne null lorsqu'un élément n'est pas présent. C'est ce que nous avons choisi de faire ici. 

public int count(E elem) {
    Integer c = counts.get(elem);
    return c != null ? c : 0;
}

Partie 2 – méthode add

La méthode add obtient le nombre d'occurrence actuel pour l'élément à ajouter (au moyen de la méthode count afin de lui laisser traiter le cas où l'élément n'est pas encore dans l'ensemble), ajoute 1 et stocke le résultat dans la table. Bien entendu, une fois cela fait, elle incrémente la taille. 

public void add(E newElem) {
    int cnt = count(newElem);
    counts.put(newElem, cnt + 1);
    size += 1;
}

Partie 3 – méthode remove

La méthode remove ne fait rien si l'élément n'apparaît pas dans le multi-ensemble. Dans le cas contraire, elle distingue deux cas :

  1. si l'élément n'apparaît qu'une fois, alors il doit être supprimé de la table,
  2. sinon, son nombre d'occurrence doit être diminué de une unité.

Dans les deux cas, elle décrémente la taille. 

public void remove(E elem) {
    if (! counts.containsKey(elem))
        return;

    int cnt = counts.get(elem);
    if (cnt == 1)
        counts.remove(elem);
    else
        counts.put(elem, cnt - 1);
    size -= 1;
}

Partie 4 – méthode iterator

L'itérateur sur les multi-ensembles est presque identique à celui sur les ensembles, si ce n'est que chaque élément doit être retourné un nombre de fois qui dépend de son nombre d'occurrence.

Le parcours des éléments eux-même peut se faire en parcourant l'ensemble des clefs de la table des nombres d'occurrences, retournée par la méthode keySet. Ensuite, chaque élément doit être retourné autant de fois que son nombre d'occurrences le précise, ce dernier pouvant être obtenu par consultation de la table.

A noter qu'il est aussi possible, et même légèrement plus efficace, d'utiliser l'itérateur sur les entrées de la table (retourné par entrySet). Le formulaire de l'examen ne donnait que les méthodes keySet et get, raison pour laquelle la solution basée sur ces méthodes est donnée ici. 

public Iterator<E> iterator() {
    return new Iterator<E>() {
        private Iterator<E> it = counts.keySet().iterator();
        private E currElem = null;
        private int currRemaining = 0;

        public boolean hasNext() {
            return it.hasNext() || currRemaining > 0;
        }

        public E next() {
            if (!hasNext())
                throw new NoSuchElementException();
            if (currRemaining == 0) {
                currElem = it.next();
                currRemaining = counts.get(currElem);
            }
            --currRemaining;
            return currElem;
        }

        public void remove() {
            throw new UnsupportedOperationException();
        }
    };
}

A noter que la méthode hasNext n'est correcte que car il est garanti que la table ne contient aucune entrée dont le nombre d'occurrence est nul !