Newer
Older
# Implantion d'une Queue (Liste FIFO) en <r style="color:red">SCALA</r>
Le but du projet, comme il peut sembler évident avec le titre, était d'implémenter une Queue en Scala.
Il s'agit d'une queue fonctionnant avec deux listes internes, qu'on appelle <b>in</b> et <b>out</b>, qui permettent de renverser la liste en fonction des besoins.
### Utilisation
Pour utiliser la Queue définie ici, vous pouvez charger les sources dans votre REPL Scala ainsi :
scala> load "ScalaQueue.scala"
Ou bien charger les classes compilées (avec l'instruction scalac) dans votre projet, via une instruction <b>import</b>.
La création de cette dernière peut se faire via la célèbre instruction <b>new</b> en spécifiant au maximum une List comme argument. Il est aussi possible de simplement appeler le constructeur sans le mot clé new (comme ceci : Queue()) en y spécifiant aussi au maximum une List.
### Détails de l'implantation
Comme brièvement expliqué dans l'introduction, la queue est implémentée grâce à deux listes de l'api de base de Scala (l'objet List),
que l'on réaffecte (ou plutôt recrée, nous sommes dans une optique fonctionnelle) selon l'opération à effectuer :
- Si on ajoute des éléments à la queue, c'est la liste <b>in</b> qui est sollicitée.
- Si on récupère des éléments de la queue, c'est la liste <b>out</b> qui est sollicitée.
En effet, le choix d'implémentation fait ici permet d'obtenir une recherche d'élément en temps constant dit <b>amorti</b> : en fonction de l'élément voulu, on inverse la liste et la place dans <b>out</b>, permettant de trouver plus rapidement des éléments du fond de la liste (Le bénéfice se sentira dès la seconde opération successive, l'inversion de la liste étant déjà de complexité linéaire).
Méthodes classiques de Queue implantées :
- enqueue (permet d'ajouter un élément dans la file)
- dequeue (permet de retirer la tête de file et la récupérer)
- headOption (permet de visualiser la tête de file si elle existe). Cette dernière utilise l'objet Option de Scala afin de ne pas être bloqué sur les listes vides durant les chaînages d'opérations.
- isEmpty (permet de savoir si la liste est vide)
Méthodes supplémentaires implantées :
<em>Il est important de noter que la plupart des implémentations décrites ici utilisent les déjà présentes et optimisées méthodes équivalentes de l'objet List.</em>
- length (permet d'obtenir la longueur de la liste)
- rearOption (contrepatie de headOption, permet de visualiser la queue de la file si elle existe)
- toList (permet de transformer la Queue en List)
- map (permet d'appliquer une fonction de transformation sur chaque élément de la Queue)
- foldLeft (permet d'appliquer une fonction d'agrégation sur la Queue)
Ce projet étant universitaire, il me semble intéressant de terminer avec ce qu'a pu éventuellement m'apporter sa réalisation.
En premier lieu, j'aimerai faire part du regret que j'ai éprouvé quant au fait que le projet soit aussi guidé. Je pense que l'expérience aurait été bien plus formatrice (sans compter gratifiante) avec un sujet plus libre, ou tout du moins, moins "mis sur les rails". Toutefois, la structure étudiée étant intéressante dans sa construction et dans l'objectif qu'elle permet d'atteindre, la programmation de cette Queue fut tout de même enrichissante.
Pas de difficulté notable rencontrée, à part peut-être un soucis de peaufinage quant à "l'expérience utilisateur" de cette Queue ; je souhaitais pouvoir cantonner la construction de la Queue à un modèle bien précis et ai requis l'aide du professeur, manquant personnellement de connaissances dans ce langage.