Instructions
Un tampon circulaire, aussi appelé tampon cyclique ou tampon en anneau, est une structure de données qui utilise un unique tampon de taille fixe comme s'il était relié de bout en bout.
Au départ, un tampon circulaire est vide et possède une longueur prédéfinie.
Par exemple, voici un tampon de 7 éléments :
[ ][ ][ ][ ][ ][ ][ ]
Supposons qu'un 1 soit écrit au milieu du tampon (l'emplacement de départ exact n'a pas d'importance dans un tampon circulaire) :
[ ][ ][ ][1][ ][ ][ ]
Supposons ensuite que deux éléments supplémentaires, 2 et 3, soient ajoutés à la suite du 1 :
[ ][ ][ ][1][2][3][ ]
Si on retire ensuite deux éléments du tampon, ce sont les valeurs les plus anciennes qu'il contient qui sont retirées.
Les deux éléments retirés, ici, sont 1 et 2, ce qui ne laisse dans le tampon qu'un 3 :
[ ][ ][ ][ ][ ][3][ ]
Si le tampon contient 7 éléments, il est alors complètement plein :
[5][6][7][8][9][3][4]
Quand le tampon est plein, une erreur est levée pour avertir le client que les écritures suivantes sont bloquées jusqu'à ce qu'un emplacement se libère.
Quand le tampon est plein, le client peut choisir d'écraser les données les plus anciennes au moyen d'une écriture forcée.
Dans ce cas, deux éléments supplémentaires, A et B, sont ajoutés et écrasent le 3 et le 4 :
[5][6][7][8][9][A][B]
3 et 4 ont été remplacés par A et B, ce qui fait désormais de 5 la donnée la plus ancienne du tampon.
Enfin, si on retire deux éléments, ce sont 5 et 6 qui sont renvoyés, ce qui donne le tampon suivant :
[ ][ ][7][8][9][A][B]
Comme de la place est disponible, si le client utilise à nouveau l'écrasement pour stocker C et D, c'est l'emplacement où 5 et 6 étaient stockés auparavant qui sera utilisé, et non celui de 7 et 8.
7 reste l'élément le plus ancien et le tampon est de nouveau plein.
[C][D][7][8][9][A][B]
Tâches
Définis un type composite paramétrique CircularBuffer{T} qui contient des éléments de type T, et écris un constructeur
CircularBuffer{T}(capacity::Integer) where {T} -> CircularBuffer{T}
qui crée une instance pouvant stocker jusqu'à capacity éléments.
Étends les fonctions suivantes de Base pour qu'elles fonctionnent avec les CircularBuffer :
-
Base.push!(cb::CircularBuffer, item; overwrite::Bool=false) : insère l'élément item à la fin de cb, puis renvoie cb. Si cb est déjà plein, lève une BoundsError si overwrite vaut false (la valeur par défaut) ; sinon, retire le premier élément pour faire de la place à item si overwrite vaut true.
-
Base.popfirst!(cb::CircularBuffer) : retire et renvoie le premier élément de cb.
-
Base.empty!(cb::CircularBuffer) : retire tous les éléments de cb, puis renvoie cb vide.
Tâches bonus
Cet exercice est assez volumineux et potentiellement compliqué, ce qui rend le mentorat plus difficile et plus long. Pour aider ton mentor, ne soumets pas de code pour les exercices bonus tant que ton mentor n'a pas relu ta solution de la première partie de l'exercice.
Étends ton CircularBuffer pour passer les tests de CircularBuffer du paquet DataStructures.jl. Ces tests sont inclus mais désactivés dans les tests fournis pour cet exercice Exercism ; pour les activer, ajoute la ligne de niveau supérieur enable_bonus_tests = true à ton fichier ou à ton notebook.
Pour passer ces tests, tu dois déclarer CircularBuffer comme sous-type de AbstractVector et définir deux fonctions :
-
capacity(cb::CircularBuffer) : renvoie la capacité de cb.
-
isfull(cb::CircularBuffer) : renvoie true si cb est plein.
Tu dois ensuite t'assurer que les fonctions suivantes de Base fonctionnent correctement avec les CircularBuffer : append!, empty!, pop!, pushfirst, setindex!, collect, eltype, first, getindex, isempty, iterate, last, length et size.
Indice : tu n'as pas besoin d'étendre toutes ces fonctions, et tu ne devrais d'ailleurs pas le faire ! Si tu définis CircularBuffer comme sous-type de AbstractVector, les fonctions génériques définies pour AbstractVector accepteront désormais un CircularBuffer en entrée. Va voir la section sur les interfaces du manuel de Julia :
Une grande partie de la puissance et de l'extensibilité de Julia vient d'un ensemble d'interfaces informelles. En étendant quelques méthodes spécifiques pour qu'elles fonctionnent avec un type personnalisé, les objets de ce type bénéficient non seulement de ces fonctionnalités, mais peuvent aussi être utilisés dans d'autres méthodes écrites pour s'appuyer de manière générique sur ces comportements.
Tu devras parcourir le code source du module Base de Julia pour voir les définitions de fonctions et déterminer lesquelles étendre. Pour trouver le code correspondant à un appel de fonction, tu peux utiliser la macro @which qui identifie la méthode précise vers laquelle un appel de fonction est envoyé. Elle t'indique aussi le fichier et le numéro de ligne où cette méthode est définie (dans un Notebook Jupyter via IJulia, elle te donne même un lien vers le code correspondant sur GitHub).
Si tu travailles dans le REPL, tu préféreras peut-être utiliser la macro @edit pour ouvrir le fichier et la ligne correspondants dans ton éditeur de texte par défaut.
