Instrucciones
Un búfer circular, búfer cíclico o búfer en anillo es una estructura de datos que usa un único búfer de tamaño fijo como si estuviera conectado de extremo a extremo.
Un búfer circular comienza vacío y con una longitud predefinida.
Por ejemplo, este es un búfer de 7 elementos:
[ ][ ][ ][ ][ ][ ][ ]
Supón que se escribe un 1 en el medio del búfer (la ubicación exacta de inicio no importa en un búfer circular):
[ ][ ][ ][1][ ][ ][ ]
Luego supón que se agregan dos elementos más, 2 y 3, que quedan después del 1:
[ ][ ][ ][1][2][3][ ]
Si después se eliminan dos elementos del búfer, se eliminan los valores más antiguos que hay dentro de él.
Los dos elementos eliminados, en este caso, son 1 y 2, y dejan el búfer con solo un 3:
[ ][ ][ ][ ][ ][3][ ]
Si el búfer tiene 7 elementos, entonces está completamente lleno:
[5][6][7][8][9][3][4]
Cuando el búfer está lleno se generará un error que le avisa al cliente que las escrituras posteriores están bloqueadas hasta que se libere un espacio.
Cuando el búfer está lleno, el cliente puede optar por sobrescribir los datos más antiguos con una escritura forzada.
En este caso, se agregan dos elementos más, A y B, que sobrescriben el 3 y el 4:
[5][6][7][8][9][A][B]
El 3 y el 4 han sido reemplazados por A y B, lo que hace que 5 sea ahora el dato más antiguo del búfer.
Por último, si se eliminan dos elementos, lo que se devolvería es 5 y 6, lo que da como resultado el búfer:
[ ][ ][7][8][9][A][B]
Como hay espacio disponible, si el cliente vuelve a usar la sobrescritura para guardar C y D, se usará el espacio donde antes se guardaron 5 y 6, y no la ubicación de 7 y 8.
El 7 sigue siendo el elemento más antiguo y el búfer vuelve a estar lleno.
[C][D][7][8][9][A][B]
Tareas
Define un tipo compuesto paramétrico CircularBuffer{T} que contenga elementos de tipo T, y escribe un constructor
CircularBuffer{T}(capacity::Integer) where {T} -> CircularBuffer{T}
que cree una instancia capaz de almacenar hasta capacity elementos.
Extiende las siguientes funciones de Base para que funcionen con CircularBuffer:
-
Base.push!(cb::CircularBuffer, item; overwrite::Bool=false): Inserta el elemento item
al final de cb y luego devuelve cb. Si cb ya está lleno, lanza un BoundsError
si overwrite es false (el valor predeterminado); de lo contrario, elimina el primer
elemento para hacer espacio para item si overwrite es true.
-
Base.popfirst!(cb::CircularBuffer): Elimina y devuelve el primer elemento de cb.
-
Base.empty!(cb::CircularBuffer): Elimina todos los elementos de cb y luego devuelve el
cb vacío.
Tareas adicionales
Este ejercicio es bastante grande y potencialmente complicado, y eso hace que la mentoría sea
más difícil y tome más tiempo. Para ayudar a tu mentor, no envíes código para los ejercicios
adicionales hasta que tu mentor haya revisado tu solución de la primera parte del ejercicio.
Extiende tu CircularBuffer para que pase las pruebas de CircularBuffer del
paquete DataStructures.jl. Estas
pruebas están incluidas pero deshabilitadas en las pruebas proporcionadas para este ejercicio
de Exercism; para habilitar estas pruebas, agrega la línea de nivel superior
enable_bonus_tests = true a tu archivo o cuaderno.
Para pasar estas pruebas, debes declarar CircularBuffer como un subtipo de
AbstractVector y definir dos funciones:
-
capacity(cb::CircularBuffer): Devuelve la capacidad de cb.
-
isfull(cb::CircularBuffer): Devuelve true si cb está lleno.
Luego debes asegurarte de que las siguientes funciones de Base funcionen correctamente con
CircularBuffer: append!, empty!, pop!, pushfirst, setindex!, collect,
eltype, first, getindex, isempty, iterate, last, length y size.
Pista: no necesitas extender todas estas funciones, ¡y no deberías hacerlo! Si defines
CircularBuffer como un subtipo de AbstractVector, las funciones genéricas que se
definieron para AbstractVector ahora aceptarán CircularBuffer como argumento. Consulta la
sección sobre interfaces
en el manual de Julia:
Gran parte de la potencia y la extensibilidad de Julia proviene de un conjunto de
interfaces informales. Al extender unos pocos métodos específicos para que funcionen con un
tipo personalizado, los objetos de ese tipo no solo reciben esas funcionalidades, sino que
también se pueden usar en otros métodos que se escriben para construir de forma genérica
sobre esos comportamientos.
Tendrás que revisar el código fuente del módulo
Base de Julia para ver las
definiciones de funciones y determinar cuáles extender. Para localizar el código relevante de
una llamada a función, puedes usar la macro
@which
para identificar el método específico al que se despacha una llamada a función. También te
muestra el archivo y el número de línea donde se define ese método (en un Jupyter Notebook a
través de IJulia, incluso te da un enlace al código relevante en GitHub).
Si estás trabajando en el REPL, quizás prefieras usar la macro @edit para abrir el archivo y la línea relevantes en tu editor de texto predeterminado.
