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 ligado de ponta a ponta.
Um buffer circular começa vazio e com um determinado comprimento predefinido.
Por exemplo, este é um buffer de 7 elementos:
[ ][ ][ ][ ][ ][ ][ ]
Imagina que se escreve um 1 no meio do buffer (a localização inicial exata não importa num buffer circular):
[ ][ ][ ][1][ ][ ][ ]
Imagina agora que são acrescentados mais dois elementos, o 2 e o 3, que ficam depois do 1:
[ ][ ][ ][1][2][3][ ]
Se depois forem removidos dois elementos do buffer, são removidos os valores mais antigos que estão dentro dele.
Os dois elementos removidos, neste caso, são o 1 e o 2, ficando o buffer apenas com o 3:
[ ][ ][ ][ ][ ][3][ ]
Se o buffer tiver 7 elementos, fica completamente cheio:
[5][6][7][8][9][3][4]
Quando o buffer está cheio, é gerado um erro que avisa o cliente de que novas escritas ficam bloqueadas até que fique uma fenda livre.
Quando o buffer está cheio, o cliente pode optar por sobrescrever os dados mais antigos com uma escrita forçada.
Neste caso, são acrescentados mais dois elementos, o A e o B, que sobrescrevem o 3 e o 4:
[5][6][7][8][9][A][B]
O 3 e o 4 foram substituídos por A e B, o que faz do 5 o dado mais antigo do buffer.
Por fim, se forem removidos dois elementos, o que seria devolvido é o 5 e o 6, dando origem ao buffer:
[ ][ ][7][8][9][A][B]
Como há espaço disponível, se o cliente voltar a usar a sobrescrita para guardar C e D, será usado o espaço onde o 5 e o 6 estavam guardados anteriormente, e não a posição do 7 e do 8.
O 7 continua a ser o elemento mais antigo e o buffer volta a estar cheio.
[C][D][7][8][9][A][B]
Tarefas
Define um tipo compósito paramétrico CircularBuffer{T} que contém elementos do tipo T, e escreve um construtor
CircularBuffer{T}(capacity::Integer) where {T} -> CircularBuffer{T}
que cria uma instância capaz de armazenar até capacity elementos.
Estende as seguintes funções de Base para funcionarem com CircularBuffers:
-
Base.push!(cb::CircularBuffer, item; overwrite::Bool=false): Insere o elemento item no fim de cb e devolve cb. Se cb já estiver cheio, lança um BoundsError se overwrite for false (o valor predefinido); caso contrário, remove o primeiro elemento para abrir espaço para item se overwrite for true.
-
Base.popfirst!(cb::CircularBuffer): Remove e devolve o primeiro elemento de cb.
-
Base.empty!(cb::CircularBuffer): Remove todos os elementos de cb e devolve o cb vazio.
Tarefas bónus
Este exercício é bastante grande e potencialmente complicado, o que torna o acompanhamento mais desafiante e moroso. Para ajudar o teu mentor, não submetas código para os exercícios bónus enquanto o teu mentor não tiver revisto a tua solução da primeira parte do exercício.
Estende o teu CircularBuffer para passar nos testes de CircularBuffer do pacote DataStructures.jl. Estes testes estão incluídos, mas desativados, nos testes fornecidos para este exercício do Exercism; para os ativares, adiciona a linha de nível superior enable_bonus_tests = true ao teu ficheiro ou notebook.
Para passares nestes testes, tens de declarar CircularBuffer como um subtipo de AbstractVector e definir duas funções:
-
capacity(cb::CircularBuffer): Devolve a capacidade de cb.
-
isfull(cb::CircularBuffer): Devolve true se cb estiver cheio.
Depois, tens de garantir que as seguintes funções de Base funcionam corretamente com CircularBuffers: append!, empty!, pop!, pushfirst, setindex!, collect, eltype, first, getindex, isempty, iterate, last, length, e size.
Dica: não precisas de estender todas estas funções, nem deves! Ao definires CircularBuffer como um subtipo de AbstractVector, as funções genéricas que foram definidas para AbstractVector passam agora a aceitar CircularBuffer como valor de entrada. Vê a secção sobre interfaces no manual da Julia:
Grande parte do poder e da extensibilidade da Julia vem de um conjunto de interfaces
informais. Ao estender alguns métodos específicos para funcionarem com um tipo
personalizado, os objetos desse tipo não só recebem essas funcionalidades, como também
podem ser usados noutros métodos escritos para construir genericamente sobre esses
comportamentos.
Vais ter de procurar no código-fonte do módulo Base da Julia para veres as definições das funções e perceberes quais deves estender. Para localizares o código relevante para uma chamada de função, podes usar a macro @which para identificares o método específico para o qual essa chamada é despachada. Também te mostra o ficheiro e o número da linha onde esse método está definido (num Jupyter Notebook através do IJulia, chega a dar-te um link para o código relevante no GitHub).
Se estiveres a trabalhar no REPL, podes preferir usar a macro @edit para abrires o ficheiro e a linha relevantes no teu editor de texto predefinido.
