Utasítások
A körkörös puffer, a ciklikus puffer vagy a gyűrűpuffer egy olyan adatszerkezet, amely egyetlen, rögzített méretű puffert használ, mintha a végei össze lennének kötve.
A körkörös puffer kezdetben üres, és valamilyen előre meghatározott hosszúságú.
Például ez egy 7 elemű puffer:
[ ][ ][ ][ ][ ][ ][ ]
Tegyük fel, hogy egy 1-est írunk a puffer közepére (a pontos kezdőhely nem számít egy körkörös pufferben):
[ ][ ][ ][1][ ][ ][ ]
Ezután tegyük fel, hogy további két elem kerül hozzá, a 2 és a 3, amelyek az 1 után fűződnek be:
[ ][ ][ ][1][2][3][ ]
Ha ezután két elemet eltávolítunk a pufferből, a pufferben lévő legrégebbi értékek törlődnek.
Ebben az esetben a két eltávolított elem az 1 és a 2, így a pufferben csak a 3 marad:
[ ][ ][ ][ ][ ][3][ ]
Ha a puffer 7 elemet tartalmaz, akkor teljesen tele van:
[5][6][7][8][9][3][4]
Amikor a puffer megtelt, hiba keletkezik, ami jelzi a kliensnek, hogy a további írások blokkolva vannak, amíg egy hely fel nem szabadul.
Amikor a puffer tele van, a kliens úgy dönthet, hogy egy kényszerített írással felülírja a legrégebbi adatokat.
Ebben az esetben további két elem, az A és a B kerül hozzáadásra, és felülírják a 3-at és a 4-et:
[5][6][7][8][9][A][B]
A 3-at és a 4-et felváltotta az A és a B, így most az 5 a legrégebbi adat a pufferben.
Végül, ha két elemet eltávolítunk, akkor az 5-öt és a 6-ot kapnánk vissza, így a puffer:
[ ][ ][7][8][9][A][B]
Mivel van szabad hely, ha a kliens ismét a felülírást használja a C és a D tárolására, akkor azt a helyet fogja használni, ahol korábban az 5 és a 6 volt, nem pedig a 7 és a 8 helyét.
A 7 még mindig a legrégebbi elem, és a puffer ismét tele van.
[C][D][7][8][9][A][B]
Feladatok
Definiálj egy CircularBuffer{T} parametrikus összetett típust, amely T típusú elemeket tárol, és írj egy konstruktort
CircularBuffer{T}(capacity::Integer) where {T} -> CircularBuffer{T}
amely létrehoz egy olyan példányt, amely legfeljebb capacity elemet tud tárolni.
Terjeszd ki a Base alábbi függvényeit, hogy CircularBuffer-okkal is működjenek:
-
Base.push!(cb::CircularBuffer, item; overwrite::Bool=false): Szúrd be az item elemet a cb végére, majd add vissza a cb-t. Ha a cb már tele van, akkor dobj egy BoundsError-t, ha az overwrite értéke false (az alapértelmezett érték); egyébként távolítsd el az első elemet, hogy helyet csinálj az item számára, ha az overwrite értéke true.
-
Base.popfirst!(cb::CircularBuffer): Távolítsd el és add vissza a cb első elemét.
-
Base.empty!(cb::CircularBuffer): Távolítsd el az összes elemet a cb-ből, majd add vissza az üres cb-t.
Bónuszfeladatok
Ez a feladat meglehetősen nagy, és lehet, hogy bonyolult is, ami miatt nagyobb kihívást jelent, és több időt vesz igénybe a mentorálás. Hogy segíts a mentorodnak, addig ne küldj be kódot a bónuszfeladatokhoz, amíg a mentorod át nem nézte a megoldásodat a feladat első részéhez.
Egészítsd ki a CircularBuffer-odat, hogy átmenjen a DataStructures.jl csomag CircularBuffer típusára írt teszteken. Ezek a tesztek benne vannak, de le vannak tiltva az ehhez az Exercism-feladathoz mellékelt tesztekben; a tesztek engedélyezéséhez add hozzá a fájlodhoz vagy a notebookodhoz a legfelső szintű enable_bonus_tests = true sort.
Ahhoz, hogy átmenj ezeken a teszteken, a CircularBuffer-t az AbstractVector altípusaként kell deklarálnod, és definiálnod kell két függvényt:
-
capacity(cb::CircularBuffer): Add vissza a cb kapacitását.
-
isfull(cb::CircularBuffer): Add vissza true-t, ha a cb tele van.
Ezután biztosítanod kell, hogy a Base alábbi függvényei helyesen működjenek CircularBuffer-okkal: append!, empty!, pop!, pushfirst, setindex!, collect, eltype, first, getindex, isempty, iterate, last, length és size.
Tipp: nem kell, és nem is szabad, hogy ezek mindegyikét kiterjeszd! Ha a CircularBuffer-t az AbstractVector altípusaként definiálod, az AbstractVector számára definiált generikus függvények mostantól elfogadják bemenetként a CircularBuffer-t. Nézd meg az interfészekről szóló részt a Julia kézikönyvben:
A Julia sok ereje és bővíthetősége informális interfészek gyűjteményéből fakad. Ha néhány konkrét metódust kiterjesztesz egy saját típusra, az adott típus objektumai nemcsak megkapják ezeket a funkciókat, hanem olyan más metódusokban is használhatók lesznek, amelyek ezekre a viselkedésekre építve lettek generikusan megírva.
Át kell böngészned a Julia Base moduljának forráskódját, hogy megnézd a függvénydefiníciókat, és kitaláld, melyeket kell kiterjesztened. Ha meg akarod találni egy függvényhíváshoz tartozó kódot, használhatod a @which makrót, hogy azonosítsd azt a konkrét metódust, amelyhez a függvényhívás irányítódik. Ez megmutatja azt is, hogy melyik fájlban és hányadik sorban van definiálva az a metódus (Jupyter Notebookban, IJulia segítségével, még egy linket is ad a GitHubon található vonatkozó kódhoz).
Ha a REPL-ben dolgozol, talán inkább a @edit makrót használnád, hogy megnyisd a vonatkozó fájlt és sort az alapértelmezett szövegszerkesztődben.
