Qu’est-ce que l’équivalence de deux implémentations d’une file ?

Réponse courte

Deux implémentations d’une file sont fonctionnellement équivalentes si, pour toute suite permise d’opérations, elles respectent le même contrat et produisent les mêmes valeurs dans le même ordre. Leur représentation interne peut différer.

Comprendre

Comparer ce que le programme observe

Une file promet notamment d’ajouter en fin et de retirer la valeur la plus ancienne. Deux implémentations sont équivalentes du point de vue de cette interface si les mêmes appels valides renvoient les mêmes résultats et maintiennent le même ordre abstrait. L’une peut employer une liste, l’autre deux piles : le tableau interne n’a pas à se ressembler.

Tester une séquence complète

Ajoute 4, puis 9, puis retire : les deux réalisations doivent renvoyer 4 et conserver 9. Ajoute ensuite 2 et vide la file : elles doivent renvoyer 9 puis 2. Répéter seulement un retrait sur une file à un élément ne suffit pas à révéler une erreur d’ordre. Il faut aussi tester l’état vide puis un nouvel ajout.

Pièges de portée

Une égalité sur un seul exemple ne prouve pas l’équivalence pour toutes les suites d’opérations permises ; il faut raisonner sur le contrat, en plus des tests. Enfin, équivalence fonctionnelle ne signifie pas coût identique : retirer en tête d’une liste peut décaler des éléments, tandis qu’une implémentation à deux piles a un autre profil de coût.

Exemples

  • Sur les appels ajouter(4), ajouter(9), retirer(), les deux files doivent renvoyer 4 et garder seulement 9.
  • Après ajouter(A), ajouter(B), retirer(), ajouter(C), les retraits suivants doivent donner B puis C dans chaque implémentation.

Pièges fréquents

  • Comparer les tableaux internes au lieu des résultats observables rejette à tort deux structures qui rangent différemment les mêmes valeurs abstraites.
  • Tester seulement une insertion puis un retrait ne vérifie pas la conservation de l’ordre après plusieurs opérations alternées.

Et maintenant ?

Questions proches

← Toutes les questions-réponses