Série 11 – Piles immuables : corrigé

Le code du corrigé est disponible sous la forme d'une archive Zip. Les solutions aux différents exercices sont brièvement discutées ci-dessous.

La classe LinkedStack étant une liste (simplement) chaînée, la première chose à faire est de définir une classe pour les nœuds. Comme d'habitude, on fait pour cela une classe Node privée et imbriquée statiquement dans la classe de la pile elle-même. Etant donné que la pile est immuable, ses nœuds le sont aussi, donc le champ next est final! La classe Node ressemble donc à ceci (sans sa classe englobante) :

private static class Node<E> {
    public final E value;
    public final Node<E> next;

    public Node(E value, Node<E> next) {
        this.value = value;
        this.next = next;
    }
}

La classe LinkedStack elle-même ne possède qu'un champ, nommé topNode, qui désigne le nœud du sommet de la pile. Etant donné que la pile est immuable, ce champ est également final! Il doit donc être initialisé dans le constructeur, qui doit dès lors être privé étant donné qu'il reçoit un nœud en argument et que le type Node ne doit pas être visible en dehors de la classe LinkedStack. Pour palier à l'absence de constructeur, la méthode statique emptyStack est fournie. Comme son nom l'indique, elle retourne une pile vide.

public final class LinkedStack<E> implements Stack<E> {
    private final Node<E> topNode;

    public static <E> Stack<E> emptyStack() {
        return new LinkedStack<>(null);
    }

    private LinkedStack(Node<E> topNode) {
        this.topNode = topNode;
    }

    // ... autres méthodes
}

Une fois la classe LinkedStack définie ainsi, les méthodes isEmpty, size et top sont triviales à écrire :

@Override
public boolean isEmpty() {
    return topNode == null;
}

@Override
public int size() {
    int size = 0;
    for (Node<E> n = topNode; n != null; n = n.next)
        ++size;
    return size;
}

@Override
public E top() {
    if (topNode == null)
        throw new EmptyStackException();
    return topNode.value;
}

Les deux dernières méthodes, push et pop, sont peut-être les plus difficiles à écrire pour qui a l'habitude des collections modifiables. Il faut donc toujours bien se souvenir que, dans les collections immuables comme celle-ci, les méthodes de « modification » retournent une nouvelle collection !

Ainsi, push retourne une nouvelle pile en tous points semblable à la pile à laquelle on l'applique si ce n'est qu'elle a un élément de plus, l'argument de push, au sommet. Pour construire cette nouvelle pile, il serait possible de copier la totalité de l'ancienne, mais étant donné que les piles sont immuables, cela n'est pas nécessaire, il est possible de partager des nœuds entre l'ancienne et la nouvelle pile. La méthode push se contente donc de créer un nouveau nœud contenant son argument et le lie avec le sommet de la pile originale.

@Override
public Stack<E> push(E newElem) {
    return new LinkedStack<E>(new Node<E>(newElem, topNode));
}

Quant à pop, elle fonctionne selon un principe similaire : plutôt que de modifier de manière destructive la pile à laquelle on l'applique, elle retourne simplement une pile dont le sommet est le second nœud de la pile à laquelle on l'applique. Bien entendu, si cette dernière est vide, l'exception EmptyStackException est levée.

@Override
public Stack<E> pop() {
    if (topNode == null)
        throw new EmptyStackException();
    return new LinkedStack<E>(topNode.next);
}

Pour ajouter la possibilité de rejouer des actions annulées (redo), l'idée principale est de gérer une seconde pile, appelée redoStack dans le code. Le type de cette pile est identique à celui de la pile d'annulation (undoStack) à savoir Stack<Stack<Double>>.

Lors de l'annulation d'une opération (undo), la pile de la calculatrice (stack) que l'on s'apprête à remplacer par le sommet de la pile undoStack est placée sur la pile redoStack. Elle en est ensuite extraite si l'utilisateur choisit de rejouer la dernière action annulée.

Temporellement, on peut dire que la pile undoStack représente le passé, dans le sens où elle stocke toutes les piles passées triées de manière à ce que la plus récente soit au sommet. La pile de la calculatrice, stack, représente le présent. Et redoStack représente quant à elle le futur, dans le sens où elle stocke toutes les piles futures (uniquement lorsqu'il est possible de rejouer des annulations, bien entendu !) triées de manière à ce que la plus ancienne soit au sommet. Les boutons undo et redo permettent de « voyager dans le temps » dans deux directions :

• lors de l'annulation d'une opération, on voyage vers le passé et pour ne pas oublier le présent, on le stocke dans la pile du futur,
• lors de l'annulation d'une annulation (redo), on voyage vers le futur et pour ne pas oublier le présent, on le stocke dans la pile du passé.

Bien entendu, toutes les actions normales (p.ex. l'entrée d'un nombre ou la sélection d'une opération arithmétique) font également voyager vers le futur.