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 empieza 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 centro del búfer (la ubicación inicial exacta no importa en un búfer circular):
[ ][ ][ ][1][ ][ ][ ]
Después, supón que se añaden dos elementos más, 2 y 3, que quedan a continuación del 1:
[ ][ ][ ][1][2][3][ ]
Si luego se eliminan dos elementos del búfer, se eliminan los valores más antiguos que contiene.
Los dos elementos eliminados, en este caso, son el 1 y el 2, con lo que el búfer se queda solo con 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 producirá un error, que avisará al cliente de que las escrituras posteriores están bloqueadas hasta que se libere una posición.
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 añaden 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, con lo que el 5 pasa a ser ahora el dato más antiguo del búfer.
Por último, si se eliminan dos elementos, lo que se devolvería es el 5 y el 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 el 5 y el 6, no la ubicación del 7 y el 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.
Amplía 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 devuelve cb. Si cb ya está lleno, lanza un BoundsError si
overwrite es false (el valor predeterminado); en caso contrario, elimina el primer
elemento para hacer sitio a 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 devuelve cb
vacío.
Tareas adicionales
Este ejercicio es bastante extenso y potencialmente complicado, lo que hace que sea más
difícil y requiera más tiempo hacer de mentor. Para echarle una mano 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.
Amplía tu CircularBuffer para superar las pruebas de CircularBuffer del
paquete DataStructures.jl. Estas
pruebas están incluidas pero desactivadas en las pruebas proporcionadas para este ejercicio
de Exercism; para activarlas, añade la línea de nivel superior enable_bonus_tests = true a
tu archivo o cuaderno.
Para superar estas pruebas tienes que declarar CircularBuffer como subtipo de
AbstractVector y definir dos funciones:
-
capacity(cb::CircularBuffer): Devuelve la capacidad de cb.
-
isfull(cb::CircularBuffer): Devuelve true si cb está lleno.
Después, tienes que 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.
Sugerencia: no necesitas ampliar todas estas funciones, ¡y no deberías hacerlo! Al definir
CircularBuffer como subtipo de AbstractVector, las funciones genéricas que se definieron
para AbstractVector aceptarán ahora CircularBuffer como entrada. Consulta la sección
sobre las interfaces
en el manual de Julia:
Gran parte de la potencia y la extensibilidad de Julia provienen de un conjunto de
interfaces informales. Al ampliar unos cuantos métodos concretos 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 escritos para construirse 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 averiguar cuáles ampliar. Para localizar el código relevante de
una llamada a una función, puedes usar la macro
@which
para identificar el método concreto al que se despacha una llamada a función. También te
muestra el archivo y el número de línea en los que se define ese método (en un cuaderno de
Jupyter a través de IJulia, incluso te da un enlace al código correspondiente en GitHub).
Si trabajas en el REPL, quizá prefieras usar la macro @edit para abrir el archivo y la línea correspondientes en tu editor de texto predeterminado.
