Istruzioni
Un buffer circolare, detto anche buffer ciclico o buffer ad anello, è una struttura dati che usa un unico buffer di dimensione fissa come se fosse collegato da un'estremità all'altra.
Un buffer circolare all'inizio è vuoto e ha una lunghezza predefinita.
Ad esempio, questo è un buffer di 7 elementi:
[ ][ ][ ][ ][ ][ ][ ]
Supponi che venga scritto il valore 1 al centro del buffer (la posizione iniziale esatta non ha importanza in un buffer circolare):
[ ][ ][ ][1][ ][ ][ ]
Poi supponi che vengano aggiunti altri due elementi, 2 e 3, che vengono accodati dopo il valore 1:
[ ][ ][ ][1][2][3][ ]
Se poi vengono rimossi due elementi dal buffer, vengono rimossi i valori più vecchi presenti nel buffer.
I due elementi rimossi, in questo caso, sono 1 e 2, lasciando nel buffer solo il valore 3:
[ ][ ][ ][ ][ ][3][ ]
Se il buffer ha 7 elementi, allora è completamente pieno:
[5][6][7][8][9][3][4]
Quando il buffer è pieno, viene generato un errore che avvisa il client che ulteriori scritture sono bloccate finché non si libera uno slot.
Quando il buffer è pieno, il client può scegliere di sovrascrivere i dati più vecchi con una scrittura forzata.
In questo caso, vengono aggiunti altri due elementi, A e B, che sovrascrivono i valori 3 e 4:
[5][6][7][8][9][A][B]
3 e 4 sono stati sostituiti da A e B, rendendo ora 5 il dato più vecchio nel buffer.
Infine, se vengono rimossi due elementi, quelli restituiti sarebbero 5 e 6, ottenendo il buffer:
[ ][ ][7][8][9][A][B]
Poiché c'è spazio disponibile, se il client usa di nuovo la sovrascrittura per memorizzare C e D, verrà usato lo spazio in cui erano stati memorizzati 5 e 6, non la posizione di 7 e 8.
7 è ancora l'elemento più vecchio e il buffer è di nuovo pieno.
[C][D][7][8][9][A][B]
Attività
Definisci un tipo composito parametrico CircularBuffer{T} che contiene elementi di tipo T, e
scrivi un costruttore
CircularBuffer{T}(capacity::Integer) where {T} -> CircularBuffer{T}
che crea un'istanza in grado di memorizzare fino a capacity elementi.
Estendi le seguenti funzioni di Base in modo che funzionino con i CircularBuffer:
-
Base.push!(cb::CircularBuffer, item; overwrite::Bool=false): Inserisci l'elemento item in fondo a cb, poi restituisci cb. Se cb è già pieno, lancia un BoundsError se overwrite è false (il valore predefinito); altrimenti, se overwrite è true, rimuovi il primo elemento per fare spazio a item.
-
Base.popfirst!(cb::CircularBuffer): Rimuovi e restituisci il primo elemento di cb.
-
Base.empty!(cb::CircularBuffer): Rimuovi tutti gli elementi da cb, poi restituisci cb vuoto.
Attività bonus
Questo esercizio è piuttosto grande e potenzialmente complicato, e questo lo rende più impegnativo e richiede più tempo per il mentoring. Per dare una mano al tuo mentore, ti chiediamo di non inviare il codice per le attività bonus finché il tuo mentore non ha esaminato la tua soluzione per la prima parte dell'esercizio.
Estendi CircularBuffer in modo che superi i test per CircularBuffer del pacchetto DataStructures.jl. Questi test sono inclusi ma disabilitati nei test forniti per questo esercizio di Exercism; per abilitarli, aggiungi la riga di primo livello enable_bonus_tests = true al file o al notebook.
Per superare questi test devi dichiarare CircularBuffer come sottotipo di AbstractVector e definire due funzioni:
-
capacity(cb::CircularBuffer): Restituisci la capacità di cb.
-
isfull(cb::CircularBuffer): Restituisci true se cb è pieno.
Poi devi assicurarti che le seguenti funzioni di Base funzionino correttamente con i CircularBuffer: append!, empty!, pop!, pushfirst, setindex!, collect, eltype, first, getindex, isempty, iterate, last, length e size.
Suggerimento: non è necessario estendere tutte queste funzioni, e anzi non dovresti farlo! Definendo CircularBuffer come sottotipo di AbstractVector, le funzioni generiche definite per AbstractVector ora accetteranno CircularBuffer come input. Vedi la sezione sulle interfacce nel manuale di Julia:
Gran parte della potenza e dell'estensibilità di Julia deriva da una raccolta di
interfacce informali. Estendendo alcuni metodi specifici perché funzionino con un tipo
personalizzato, gli oggetti di quel tipo non solo ricevono quelle funzionalità, ma possono
anche essere usati in altri metodi scritti per basarsi genericamente su quei comportamenti.
Dovrai esaminare il codice sorgente del modulo Base di Julia per vedere le definizioni delle funzioni e capire quali estendere. Per individuare il codice rilevante per una chiamata di funzione, puoi usare la macro @which per identificare il metodo specifico a cui viene indirizzata una chiamata di funzione. Ti mostra anche il file e il numero di riga in cui quel metodo è definito (in un Jupyter Notebook tramite IJulia, ti dà persino un link al codice rilevante su GitHub).
Se stai lavorando nella REPL, potresti preferire usare la macro @edit per aprire il file e la riga rilevanti nel tuo editor di testo predefinito.
