Οδηγίες
Ένας κυκλικός buffer, ένας επανακυκλούμενος buffer ή ένας buffer δακτυλίου είναι μια δομή δεδομένων που χρησιμοποιεί έναν μόνο buffer σταθερού μεγέθους, σαν να ήταν συνδεδεμένος από άκρη σε άκρη.
Ένας κυκλικός buffer ξεκινάει κενός και με κάποιο προκαθορισμένο μήκος.
Για παράδειγμα, αυτός είναι ένας buffer 7 στοιχείων:
[ ][ ][ ][ ][ ][ ][ ]
Ας υποθέσουμε ότι ένα 1 γράφεται στη μέση του buffer (η ακριβής αρχική θέση δεν έχει σημασία σε έναν κυκλικό buffer):
[ ][ ][ ][1][ ][ ][ ]
Έπειτα, ας υποθέσουμε ότι προστίθενται άλλα δύο στοιχεία, το 2 και το 3, τα οποία προσαρτώνται μετά το 1:
[ ][ ][ ][1][2][3][ ]
Αν στη συνέχεια αφαιρεθούν δύο στοιχεία από τον buffer, αφαιρούνται οι παλαιότερες τιμές που υπάρχουν μέσα του.
Τα δύο στοιχεία που αφαιρούνται, στην περίπτωση αυτή, είναι το 1 και το 2, αφήνοντας τον buffer με ένα μόνο 3:
[ ][ ][ ][ ][ ][3][ ]
Αν ο buffer έχει 7 στοιχεία, τότε είναι τελείως γεμάτος:
[5][6][7][8][9][3][4]
Όταν ο buffer γεμίσει, πετάγεται ένα σφάλμα, ειδοποιώντας τον client ότι περαιτέρω εγγραφές μπλοκάρονται μέχρι να ελευθερωθεί μια θέση.
Όταν ο buffer είναι γεμάτος, ο client μπορεί να επιλέξει να αντικαταστήσει τα παλαιότερα δεδομένα με μια εξαναγκασμένη εγγραφή.
Στην περίπτωση αυτή, προστίθενται άλλα δύο στοιχεία, το A και το B, τα οποία αντικαθιστούν το 3 και το 4:
[5][6][7][8][9][A][B]
Τα 3 και 4 έχουν αντικατασταθεί από τα A και B, κάνοντας το 5 τα παλαιότερα δεδομένα μέσα στον buffer.
Τέλος, αν αφαιρεθούν δύο στοιχεία, αυτό που θα επιστραφεί είναι τα 5 και 6, δίνοντας τον buffer:
[ ][ ][7][8][9][A][B]
Επειδή υπάρχει διαθέσιμος χώρος, αν ο client χρησιμοποιήσει ξανά την αντικατάσταση για να αποθηκεύσει το C και το D, τότε θα χρησιμοποιηθεί ο χώρος όπου ήταν αποθηκευμένα προηγουμένως το 5 και το 6, και όχι η θέση του 7 και του 8.
Το 7 εξακολουθεί να είναι το παλαιότερο στοιχείο και ο buffer είναι για άλλη μια φορά γεμάτος.
[C][D][7][8][9][A][B]
Εργασίες
Όρισε έναν παραμετρικό σύνθετο τύπο CircularBuffer{T} που περιέχει στοιχεία τύπου T, και
γράψε έναν κατασκευαστή
CircularBuffer{T}(capacity::Integer) where {T} -> CircularBuffer{T}
που δημιουργεί ένα στιγμιότυπο που μπορεί να αποθηκεύσει μέχρι capacity στοιχεία.
Επέκτεινε τις παρακάτω συναρτήσεις από το Base ώστε να λειτουργούν με CircularBuffer:
-
Base.push!(cb::CircularBuffer, item; overwrite::Bool=false): Εισάγει το στοιχείο item
στο τέλος του cb και μετά επιστρέφει το cb. Αν το cb είναι ήδη γεμάτο, τότε πέτα ένα
BoundsError αν το overwrite είναι false (η προεπιλεγμένη τιμή)· διαφορετικά αφαίρεσε
το πρώτο στοιχείο για να κάνεις χώρο για το item αν το overwrite είναι true.
-
Base.popfirst!(cb::CircularBuffer): Αφαίρεσε και επέστρεψε το πρώτο στοιχείο του cb.
-
Base.empty!(cb::CircularBuffer): Αφαίρεσε όλα τα στοιχεία από το cb και μετά επέστρεψε
το κενό cb.
Εργασίες μπόνους
Αυτή η άσκηση είναι αρκετά μεγάλη και δυνητικά περίπλοκη, κάτι που την κάνει πιο απαιτητική
και χρονοβόρα για τον μέντορα. Για να βοηθήσεις τον μέντορά σου, σε παρακαλώ μην υποβάλεις
κώδικα για τις εργασίες μπόνους μέχρι ο μέντοράς σου να ελέγξει τη λύση σου για το πρώτο
μέρος της άσκησης.
Επέκτεινε το CircularBuffer σου ώστε να περνάει τα τεστ για το CircularBuffer από το
πακέτο DataStructures.jl. Αυτά τα
τεστ περιλαμβάνονται αλλά είναι απενεργοποιημένα στα τεστ που παρέχονται για αυτή την άσκηση
του Exercism· για να ενεργοποιήσεις αυτά τα τεστ, πρόσθεσε τη γραμμή
enable_bonus_tests = true στο ανώτερο επίπεδο του αρχείου ή του notebook σου.
Για να περάσεις αυτά τα τεστ πρέπει να δηλώσεις το CircularBuffer ως υποτύπο του
AbstractVector και να ορίσεις δύο συναρτήσεις:
-
capacity(cb::CircularBuffer): Επέστρεψε τη χωρητικότητα του cb.
-
isfull(cb::CircularBuffer): Επέστρεψε true αν το cb είναι γεμάτο.
Έπειτα πρέπει να διασφαλίσεις ότι οι παρακάτω συναρτήσεις από το Base λειτουργούν σωστά με
τα CircularBuffer: append!, empty!, pop!, pushfirst, setindex!, collect,
eltype, first, getindex, isempty, iterate, last, length και size.
Υπόδειξη: Δεν χρειάζεται, και δεν πρέπει, να επεκτείνεις όλες αυτές τις συναρτήσεις!
Ορίζοντας το CircularBuffer ως υποτύπο του AbstractVector, οι γενικές συναρτήσεις που
έχουν οριστεί για το AbstractVector θα δέχονται πλέον το CircularBuffer ως είσοδο. Δες
την ενότητα για τις
διεπαφές στο
εγχειρίδιο της Julia:
Μεγάλο μέρος της δύναμης και της επεκτασιμότητας της Julia προέρχεται από μια συλλογή
άτυπων διεπαφών. Επεκτείνοντας μερικές συγκεκριμένες μεθόδους ώστε να δουλεύουν για έναν
προσαρμοσμένο τύπο, τα αντικείμενα αυτού του τύπου όχι μόνο αποκτούν αυτές τις λειτουργίες,
αλλά μπορούν επίσης να χρησιμοποιηθούν σε άλλες μεθόδους που είναι γραμμένες ώστε να χτίζουν
γενικά πάνω σε αυτές τις συμπεριφορές.
Θα χρειαστεί να ψάξεις στον πηγαίο κώδικα του module
Base της Julia για να δεις τους
ορισμούς των συναρτήσεων και να καταλάβεις ποιες να επεκτείνεις. Για να εντοπίσεις τον
σχετικό κώδικα για μια κλήση συνάρτησης, μπορείς να χρησιμοποιήσεις τη μακροεντολή
@which
για να προσδιορίσεις τη συγκεκριμένη μέθοδο στην οποία καταλήγει μια κλήση συνάρτησης. Σου
δείχνει επίσης το αρχείο και τον αριθμό γραμμής όπου ορίζεται αυτή η μέθοδος (σε ένα Jupyter
Notebook μέσω IJulia, σου δίνει μάλιστα έναν σύνδεσμο προς τον σχετικό κώδικα στο GitHub).
Αν δουλεύεις στο REPL, ίσως προτιμήσεις να χρησιμοποιήσεις τη μακροεντολή @edit για να ανοίξεις το σχετικό αρχείο και τη γραμμή στον προεπιλεγμένο επεξεργαστή κειμένου σου.
