Anleitung
Ein Ringpuffer, auch zyklischer Puffer genannt, ist eine Datenstruktur, die einen einzigen Puffer fester Größe verwendet, als wären seine Enden miteinander verbunden.
Ein Ringpuffer ist zu Beginn leer und hat eine vorgegebene Länge.
Ein Puffer mit 7 Elementen sieht zum Beispiel so aus:
[ ][ ][ ][ ][ ][ ][ ]
Nimm an, dass eine 1 in die Mitte des Puffers geschrieben wird (die genaue Startposition spielt bei einem Ringpuffer keine Rolle):
[ ][ ][ ][1][ ][ ][ ]
Nimm dann an, dass zwei weitere Elemente hinzugefügt werden, 2 und 3, die nach der 1 angehängt werden:
[ ][ ][ ][1][2][3][ ]
Wenn anschließend zwei Elemente aus dem Puffer entfernt werden, werden die ältesten Werte im Puffer entfernt.
Die beiden entfernten Elemente sind in diesem Fall 1 und 2, sodass nur eine 3 im Puffer bleibt:
[ ][ ][ ][ ][ ][3][ ]
Wenn der Puffer 7 Elemente enthält, ist er voll:
[5][6][7][8][9][3][4]
Wenn der Puffer voll ist, wird ein Fehler ausgelöst, der den Client darüber informiert, dass weitere Schreibvorgänge blockiert sind, bis ein Platz frei wird.
Wenn der Puffer voll ist, kann der Client die ältesten Daten durch einen erzwungenen Schreibvorgang überschreiben.
In diesem Fall werden zwei weitere Elemente hinzugefügt, A und B, und sie überschreiben die 3 und 4:
[5][6][7][8][9][A][B]
3 und 4 wurden durch A und B ersetzt, wodurch 5 jetzt die ältesten Daten im Puffer sind.
Wenn schließlich zwei Elemente entfernt werden, werden 5 und 6 zurückgegeben, was den folgenden Puffer ergibt:
[ ][ ][7][8][9][A][B]
Da Platz verfügbar ist, wird, wenn der Client erneut das Überschreiben nutzt, um C und D zu speichern, der Platz verwendet, an dem zuvor 5 und 6 gespeichert waren, und nicht die Position von 7 und 8.
7 ist immer noch das älteste Element, und der Puffer ist wieder voll.
[C][D][7][8][9][A][B]
Aufgaben
Definiere einen parametrischen zusammengesetzten Typ CircularBuffer{T}, der Elemente vom Typ T aufnimmt, und schreibe einen Konstruktor
CircularBuffer{T}(capacity::Integer) where {T} -> CircularBuffer{T}
der eine Instanz erzeugt, die bis zu capacity Elemente speichern kann.
Erweitere die folgenden Funktionen aus Base, damit sie mit CircularBuffer funktionieren:
-
Base.push!(cb::CircularBuffer, item; overwrite::Bool=false): Füge das Element item am Ende von cb ein und gib dann cb zurück. Wenn cb bereits voll ist, löse einen BoundsError aus, falls overwrite false ist (der Standardwert); andernfalls entferne das erste Element, um Platz für item zu schaffen, falls overwrite true ist.
-
Base.popfirst!(cb::CircularBuffer): Entferne das erste Element von cb und gib es zurück.
-
Base.empty!(cb::CircularBuffer): Entferne alle Elemente aus cb und gib dann das leere cb zurück.
Bonusaufgaben
Diese Übung ist ziemlich groß und möglicherweise kompliziert, und das macht das Mentoring anspruchsvoller und zeitaufwändiger. Damit du deinem Mentor die Arbeit erleichterst, reiche bitte keinen Code für die Bonusübungen ein, bevor dein Mentor deine Lösung für den ersten Teil der Übung überprüft hat.
Erweitere deinen CircularBuffer, damit er die Tests für CircularBuffer aus dem DataStructures.jl-Paket besteht. Diese Tests sind in den bereitgestellten Tests für diese Exercism-Übung enthalten, aber deaktiviert; um diese Tests zu aktivieren, füge die Zeile enable_bonus_tests = true auf oberster Ebene in deine Datei oder dein Notebook ein.
Um diese Tests zu bestehen, musst du CircularBuffer als Untertyp von AbstractVector deklarieren und zwei Funktionen definieren:
-
capacity(cb::CircularBuffer): Gib die Kapazität von cb zurück.
-
isfull(cb::CircularBuffer): Gib true zurück, wenn cb voll ist.
Danach musst du sicherstellen, dass die folgenden Funktionen aus Base korrekt mit CircularBuffer funktionieren: append!, empty!, pop!, pushfirst, setindex!, collect, eltype, first, getindex, isempty, iterate, last, length und size.
Hinweis: Du musst nicht alle diese Funktionen erweitern, und du solltest es auch nicht! Wenn du CircularBuffer als Untertyp von AbstractVector definierst, akzeptieren generische Funktionen, die für AbstractVector definiert wurden, nun CircularBuffer als Eingabe. Sieh dir den Abschnitt über Schnittstellen im Julia-Handbuch an:
Ein Großteil der Leistungsfähigkeit und Erweiterbarkeit von Julia kommt von einer Sammlung informeller Schnittstellen. Indem man ein paar bestimmte Methoden so erweitert, dass sie für einen eigenen Typ funktionieren, erhalten Objekte dieses Typs nicht nur diese Funktionalitäten, sondern können auch in anderen Methoden verwendet werden, die darauf ausgelegt sind, generisch auf diesen Verhaltensweisen aufzubauen.
Du musst den Quellcode von Julias Base-Modul durchsehen, um Funktionsdefinitionen zu sehen und herauszufinden, welche du erweitern musst. Um den relevanten Code für einen Funktionsaufruf zu finden, kannst du das Makro @which verwenden, um die spezifische Methode zu ermitteln, an die ein Funktionsaufruf weitergeleitet wird. Es zeigt dir außerdem die Datei und die Zeilennummer an, in der diese Methode definiert ist (in einem Jupyter-Notebook über IJulia gibt es dir sogar einen Link zum relevanten Code auf GitHub).
Wenn du am REPL arbeitest, verwendest du vielleicht lieber das Makro @edit, um die relevante Datei und Zeile in deinem Standard-Texteditor zu öffnen.
