Pale Machine - Files Persistantes
Jean-Christophe Filliâtre

Introduction

Le but de cet exercice est de réaliser une structure de file persistante, c'est-à-dire une file qui n'est pas modifiée par les opérations d'ajout ou de retrait d'éléments. (À l'instar des listes persistantes déjà vues, ces opérations renverront de nouvelles files.) Une file persistante peut être très simplement réalisée à l'aide d'une paire de listes : l'une pour y ajouter (en tête) les éléments entrant, l'autre pour y prélever (en tête) les éléments sortant. Dans le cas particulier où la liste de sortie vient à s'épuiser, il suffit alors de la remplacer par la liste d'entrée renversée, et de vider la liste d'entrée.

Comme application des files persistantes, nous allons considérer le problème du rendu de la monnaie à la caisse d'un magasin. Les clients se présentant à la caisse forment naturellement une file. En fonction de l'état de sa caisse et de la monnaie qu'il doit rendre, le caissier peut se retrouver dans la situation inconfortable où il n'est pas en mesure de rendre la monnaie. Nous allons simuler le comportement d'un caissier qui cherche à tout prix à éviter cette situation. En conséquence, il se permet parfois de renvoyer le client qui se présente à lui refaire toute la queue au lieu de lui rendre la monnaie, pour ne pas mettre sa caisse en péril. Par une exploration brutale, nous allons chercher à déterminer, étant donnée une file d'attente initiale, s'il existe une stratégie pour le caissier qui lui permet de rendre la monnaie à chaque client.

L'exercice commence par la construction de classes pour représenter les sommes échangées (Question 1) et les clients (Question 2). Viennent ensuite les classes représentant les files persistantes (Question 3). Enfin nous combinerons ces différents éléments pour déterminer l'existence d'une stratgégie (Question 4).

1. Porte-monnaies

Pour simplifier les choses, on ne considère que des sommes échangées à l'aide de billets de 10 et de 5 euros et de pièces de 1 euro. Une somme d'argent échangée est donc simplement un triplet d'entiers représentant un nombre de billets de 10 euros, un nombre de billets de 5 euros et un nombre de pièces de 1 euro. Un tel triplet est appelé porte-monnaie par la suite, et représentera aussi bien la somme versée par le client que le contenu de la caisse.

Question 1

Dans un fichier Purse.java, définir une classe Purse représentant un porte-monnaie et munie du constructeur naturel.

Définir les méthodes dynamiques suivantes pour la classe Purse :

Si besoin, on pourra utiliser la méthode Math.min calculant le minimum de deux entiers.

2. Clients

Un client est simplement représenté par la somme qu'il s'apprête à verser à la caisse (ici sous la forme d'un porte-monnaie de la classe Purse) et par le montant de la monnaie que le caissier doit lui rendre (ici sous la forme d'un entier).

Question 2. La classe Client

Dans un fichier Client.java, définir une classe Client représentant un client et munie du constructeur naturel.

3. Files d'attente

Une file d'attente va être codée par une file persistante dont les éléments sont de la classe Client. Comme expliqué dans l'introduction, une telle file persistante est représentée par une paire de liste. On commence donc par définir des listes de Client.

Question 3.1

Dans un fichier ClientList.java, définir une classe ClientList représentant des listes dont les éléments sont de la classe Client et munie du constructeur naturel.

Définir une méthode dynamique ClientList reverse() qui renverse une liste de manière persistante, c'est-à-dire en renvoyant une nouvelle liste dont les éléments apparaissent dans l'ordre inverse de ceux de this.

Question 3.2

Dans un fichier ClientQueue.java, définir une classe ClientQueue représentant une file sous la forme de deux listes (c'est-à-dire de deux variables de la classe ClientList). L'une représente l'entrée de la file et on y ajoute les nouveaux clients en tête de liste ; l'autre représente la sortie de la file et on y retire les clients en tête de liste. Lorsque la liste de sortie vient à s'épuiser, on la remplace par la liste d'entrée renversée et on vide la liste d'entrée. Attention : on construit ici des listes persistantes et il ne faut donc pas modifier ces listes en place mais toujours construire de nouvelles paires de listes.

Définir les constructeurs suivants pour la classe ClientQueue :

Définir les méthodes dynamiques suivantes pour la classe ClientQueue :

4. Existence d'une stratégie

Étant donnée une caisse initiale et une file de clients, on souhaite déterminer s'il existe une stratégie pour le caissier permettant de rendre la monnaie à tout le monde. On rappelle que le caissier procède de cette façon :
si la file est vide, il termine avec succès
sinon, il considère le premier client
- s'il ne peut lui rendre la monnaie, c'est un échec
- sinon, il a le choix entre 
  - lui rendre la monnaie (et le client est supprimé de la file)
  - le renvoyer au tout début de la file d'attente

Dans un fichier Cashier.java, définir une méthode statique boolean solution(Purse cashier, ClientQueue q, int m) qui détermine l'existence d'une stratégie gagnante. L'argument m spécifie le nombre maximum de fois où le caissier peut renvoyer un client au début de la file (ainsi on ne se préoccupe pas du problème d'une éventuelle non-terminaison).

On pourra tester avec le main suivant

    public static void main(String args[]) {
	ClientQueue q = new ClientQueue();
	q = q.put(new Client(new Purse(1,0,0), 9));
	q = q.put(new Client(new Purse(0,1,0), 1));
	Purse cashier = new Purse(0,0,9);
	System.out.println(solution(cashier, q));
    }
qui doit donner la réponse true (il existe ici une solution consistant à ne pas rendre la monnaie au premier client).

5. Amélioration

Cette représentation des files persistantes est relativement efficace mais peut être encore améliorée. En effet, il arrive que l'on inverse plusieurs fois la même liste. Ainsi, plusieurs opérations get ou remove successives sur la même file q peuvent amener à inverser plusieurs fois la même liste (dans le cas où la liste de sortie de q est vide). Pour y remédier, on peut enregistrer le retournement de la liste la première fois qu'il est effectué, en modifiant les champs de q. On ne modifie cependant pas le contenu de la file q et elle reste donc persistante.

Modifier les fonctions get et remove de la classe ClientQueue pour qu'elles effectuent cette amélioration.