Instruções
Um buffer circular, buffer cíclico ou buffer em anel é uma estrutura de dados que usa um único buffer de tamanho fixo como se estivesse conectado de ponta a ponta.
Um buffer circular começa vazio e com um comprimento predefinido.
Por exemplo, este é um buffer de 7 elementos:
[ ][ ][ ][ ][ ][ ][ ]
Suponha que um 1 seja escrito no meio do buffer (a posição inicial exata não importa em um buffer circular):
[ ][ ][ ][1][ ][ ][ ]
Depois, suponha que mais dois elementos sejam adicionados, 2 e 3, e que eles sejam anexados depois do 1:
[ ][ ][ ][1][2][3][ ]
Se dois elementos forem removidos do buffer, os valores mais antigos dentro dele são removidos.
Os dois elementos removidos, neste caso, são 1 e 2, deixando o buffer apenas com um 3:
[ ][ ][ ][ ][ ][3][ ]
Se o buffer tiver 7 elementos, então ele está completamente cheio:
[5][6][7][8][9][3][4]
Quando o buffer está cheio, um erro é gerado, avisando o cliente de que novas escritas ficam bloqueadas até que uma vaga fique livre.
Quando o buffer está cheio, o cliente pode optar por sobrescrever os dados mais antigos com uma escrita forçada.
Neste caso, mais dois elementos, A e B, são adicionados e sobrescrevem os valores 3 e 4:
[5][6][7][8][9][A][B]
Os valores 3 e 4 foram substituídos por A e B, fazendo com que o 5 seja agora o dado mais antigo do buffer.
Por fim, se dois elementos forem removidos, o que seria retornado são 5 e 6, resultando no buffer:
[ ][ ][7][8][9][A][B]
Como há espaço disponível, se o cliente usar a sobrescrita novamente para armazenar C e D, o espaço onde 5 e 6 estavam armazenados será usado, e não o local de 7 e 8.
O 7 ainda é o elemento mais antigo e o buffer está cheio novamente.
[C][D][7][8][9][A][B]
Tarefas
Defina um tipo composto paramétrico CircularBuffer{T} que armazena elementos do tipo T, e escreva um construtor
CircularBuffer{T}(capacity::Integer) where {T} -> CircularBuffer{T}
que cria uma instância que pode armazenar até capacity elementos.
Estenda as seguintes funções de Base para funcionar com os CircularBuffer:
-
Base.push!(cb::CircularBuffer, item; overwrite::Bool=false): Insira o elemento item no final de cb e retorne cb. Se cb já estiver cheio, lance um BoundsError se overwrite for false (o valor padrão); caso contrário, remova o primeiro elemento para abrir espaço para item se overwrite for true.
-
Base.popfirst!(cb::CircularBuffer): Remova e retorne o primeiro elemento de cb.
-
Base.empty!(cb::CircularBuffer): Remova todos os elementos de cb e retorne o cb vazio.
Tarefas bônus
Este exercício é bastante grande e potencialmente complicado, o que torna a mentoria mais desafiadora e demorada. Para ajudar seu mentor, não envie o código dos exercícios bônus até que seu mentor tenha revisado sua solução da primeira parte do exercício.
Estenda seu CircularBuffer para passar nos testes de CircularBuffer do pacote DataStructures.jl. Esses testes estão incluídos, mas desativados nos testes fornecidos para este exercício do Exercism; para ativá-los, adicione a linha de nível superior enable_bonus_tests = true ao seu arquivo ou notebook.
Para passar nesses testes, você precisa declarar CircularBuffer como um subtipo de AbstractVector e definir duas funções:
-
capacity(cb::CircularBuffer): Retorne a capacidade de cb.
-
isfull(cb::CircularBuffer): Retorne true se cb estiver cheio.
Depois, você deve garantir que as seguintes funções de Base funcionem corretamente com os CircularBuffer: append!, empty!, pop!, pushfirst, setindex!, collect, eltype, first, getindex, isempty, iterate, last, length e size.
Dica: você não precisa, e não deve, estender todas essas funções! Ao definir CircularBuffer como um subtipo de AbstractVector, funções genéricas definidas para AbstractVector agora aceitarão CircularBuffer como entrada. Veja a seção sobre interfaces no manual do Julia:
Muito do poder e da extensibilidade do Julia vem de uma coleção de interfaces informais. Ao estender alguns métodos específicos para funcionar com um tipo personalizado, objetos desse tipo não apenas recebem essas funcionalidades, mas também podem ser usados em outros métodos escritos para construir genericamente sobre esses comportamentos.
Você terá que examinar o código-fonte do módulo Base do Julia para ver as definições de funções e descobrir quais deve estender. Para localizar o código relevante de uma chamada de função, você pode usar a macro @which para identificar o método específico para o qual uma chamada de função é despachada. Ela também mostra o arquivo e o número da linha em que esse método está definido (em um Jupyter Notebook via IJulia, ela até fornece um link para o código relevante no GitHub).
Se você estiver trabalhando no REPL, talvez prefira usar a macro @edit para abrir o arquivo e a linha relevantes no seu editor de texto padrão.
