Série 9 – Piles immutables

Le but de cette série est d'explorer le thème de la mutabilité à travers une mise en œuvre immutable d'une collection que vous connaissez déjà, les piles. Pour mémoire, une pile est une collection très similaire à une liste, si ce n'est que l'ajout et la suppression d'éléments se fait toujours à la même extrémité.

L'interface ci-dessous, basée sur celle de l'examen intermédiaire et proche de la classe Stack du paquetage java.util, modélise une pile mutable générique très simple :

// Attention : pile mutable !
public interface Stack<E> {
    public boolean isEmpty();
    public int size();
    public void push(E newElem);
    public E pop();
}

Le fait que cette interface modélise les piles mutables transparaît dans le type de retour de la méthode push, qui est ici void. Etant donné que push ne retourne rien, le seul moyen pour qu'elle ajoute effectivement l'élément reçu à la pile est qu'elle le fasse par modification de cette dernière !

De manière générale, les collections immutables diffèrent des collections mutables en ce que les opérations qui ajoutent ou suppriment des éléments retournent toutes une nouvelle collection. C'est obligatoire, puisque par définition les collections immutables ne peuvent être modifiées !

L'interface des piles mutables présentée plus haut ne saurait donc convenir aux piles immutables. Pour ces dernières, l'interface suivante est appropriée :

public interface Stack<E> {
    public boolean isEmpty();
    public int size();
    public Stack<E> push(E newElem);
    public Stack<E> pop();
    public E top();
}

En comparant ces deux interfaces, on constate que la différence principale est que les méthodes push et pop retournent, dans la version immutable, une nouvelle pile. Dès lors, la méthode pop des piles mutables a dû être scindée en deux : pop (version immutable) retourne une nouvelle pile égale à celle à laquelle on l'applique mais amputée de son sommet, tandis que top retourne l'élément au sommet.

Les piles ressemblant beaucoup aux listes, on utilise généralement les mêmes techniques de mise en œuvre pour les deux. Pour cet exercice, nous vous demandons d'utiliser la technique du chaînage simple. En d'autres termes, la classe modélisant les piles contient une référence vers le nœud du sommet, et chaque nœud contient une référence vers son successeur, éventuellement inexistant.

Nous vous fournissons une archive zip contenant l'interface ci-dessus et un squelette de mise en œuvre des piles immutables. A vous de le compléter ! Notez que comme ces piles sont immutables, il n'y a aucun problème pour que différentes piles partagent des nœuds entre-elles. Ainsi, si on exécute le morceau de programme ci-dessous :

Stack<Integer> s1 = LinkedStack.<Integer>emptyStack().push(0);
Stack<Integer> s2 = s1.push(1);
Stack<Integer> s3 = s2.push(2);
Stack<Integer> s4 = s2.push(3);

on devrait obtenir en mémoire la situation illustrée par la figure ci-dessous :

Le fichier DAG.java de l'archive fournie contient le code d'une variante du corrigé de l'exercice sur les graphes orientés acycliques de l'examen intermédiaire. Cette variante diffère de celle que vous avez déjà vue en ce que la méthode isReachable n'est plus récursive mais itérative. Pour se souvenir des nœuds du graphe à visiter (et pas ceux déjà visités !), elle utilise une pile.

Dans la version que nous vous fournissons, cette pile est une instance de la classe java.util.Stack, qui est mutable. Le but de cette dernière partie est de récrire la méthode isReachable pour qu'elle utilise une de vos piles immutable à la place.

Ce faisant, vous constaterez que, pour cette exemple, une pile immutable est moins agréable à utiliser que sa cousine mutable. N'en tirez toutefois pas de conclusions hâtives, il existe bien d'autres situations dans lesquelles les piles—et plus généralement les collections—immutables sont idéales !