निर्देश
सर्कुलर बफर, साइक्लिक बफर या रिंग बफर एक ऐसा डेटा स्ट्रक्चर है जो एक ही निश्चित आकार के बफर का उपयोग इस तरह करता है मानो उसका अंतिम सिरा पहले सिरे से जुड़ा हो।
सर्कुलर बफर शुरू में खाली होता है और उसकी लंबाई पहले से तय होती है।
उदाहरण के लिए, यह 7 एलिमेंट वाला बफर है:
[ ][ ][ ][ ][ ][ ][ ]
मान लीजिए कि बफर के बीच में एक 1 लिखा जाता है (सर्कुलर बफर में शुरुआत की ठीक जगह से कोई अंतर नहीं पड़ता):
[ ][ ][ ][1][ ][ ][ ]
अब मान लीजिए कि दो और एलिमेंट, 2 और 3, जोड़े जाते हैं, जो 1 के बाद जुड़ जाते हैं:
[ ][ ][ ][1][2][3][ ]
अगर अब बफर से दो एलिमेंट हटाए जाएँ, तो बफर की सबसे पुरानी वैल्यू हट जाती हैं।
इस स्थिति में हटाए गए दो एलिमेंट 1 और 2 हैं, और बफर में सिर्फ 3 बचता है:
[ ][ ][ ][ ][ ][3][ ]
जब बफर में 7 एलिमेंट हो जाते हैं, तो वह पूरी तरह भर जाता है:
[5][6][7][8][9][3][4]
जब बफर भर जाता है, तो एक एरर मिलती है, जो क्लाइंट को बताती है कि जब तक कोई स्लॉट खाली न हो जाए, तब तक और कुछ लिखा नहीं जा सकता।
जब बफर भर जाता है, तो क्लाइंट चाहे तो जबरन लिखकर सबसे पुराना डेटा ओवरराइट कर सकता है।
इस स्थिति में दो और एलिमेंट, A और B, जोड़े जाते हैं और वे 3 और 4 को ओवरराइट कर देते हैं:
[5][6][7][8][9][A][B]
3 और 4 की जगह A और B आ गए हैं, जिससे अब बफर में 5 सबसे पुराना डेटा है।
अंत में, अगर दो एलिमेंट हटाए जाएँ, तो 5 और 6 लौटाए जाएँगे, और बफर ऐसा हो जाएगा:
[ ][ ][7][8][9][A][B]
चूँकि जगह खाली है, अगर क्लाइंट फिर से ओवरराइट करके C और D संग्रहीत करता है, तो 7 और 8 की जगह नहीं, बल्कि वही जगह इस्तेमाल होगी जहाँ पहले 5 और 6 रखे गए थे।
7 अब भी सबसे पुराना एलिमेंट है और बफर एक बार फिर भर जाता है।
[C][D][7][8][9][A][B]
कार्य
एक पैरामीट्रिक कंपोजिट टाइप CircularBuffer{T} बनाइए जो T टाइप के एलिमेंट रखता है, और एक ऐसा कंस्ट्रक्टर लिखिए
CircularBuffer{T}(capacity::Integer) where {T} -> CircularBuffer{T}
जो एक इंस्टेंस बनाता है जिसमें अधिकतम capacity एलिमेंट संग्रहीत किए जा सकते हैं।
CircularBuffer पर काम कराने के लिए Base के इन फंक्शनों को बढ़ाइए:
-
Base.push!(cb::CircularBuffer, item; overwrite::Bool=false): एलिमेंट item को cb के अंत में जोड़िए, फिर cb लौटाइए। अगर cb पहले से भरा हुआ है, तो overwrite के false (डिफ़ॉल्ट वैल्यू) होने पर BoundsError फेंकिए; वरना overwrite के true होने पर item के लिए जगह बनाने के लिए पहला एलिमेंट हटा दीजिए।
-
Base.popfirst!(cb::CircularBuffer): cb का पहला एलिमेंट हटाइए और लौटाइए।
-
Base.empty!(cb::CircularBuffer): cb से सारे एलिमेंट हटाइए, फिर खाली cb लौटाइए।
बोनस कार्य
यह अभ्यास काफी बड़ा है और जटिल भी हो सकता है, जिसकी वजह से मेंटर के लिए इसे संभालना और भी मुश्किल और समय लेने वाला हो जाता है। अपने मेंटर की मदद कीजिए: जब तक वे अभ्यास के पहले हिस्से के लिए आपके हल की जाँच न कर लें, तब तक बोनस अभ्यासों का कोड जमा न कीजिए।
अपने CircularBuffer को इतना बढ़ाइए कि वह DataStructures.jl पैकेज में मौजूद CircularBuffer के टेस्ट पास कर ले। इस Exercism अभ्यास के लिए दिए गए टेस्ट में ये टेस्ट शामिल तो हैं, पर बंद रखे गए हैं। इन्हें चालू करने के लिए, अपनी फाइल या नोटबुक में टॉप-लेवल पर enable_bonus_tests = true लाइन जोड़िए।
इन टेस्ट को पास करने के लिए आपको CircularBuffer को AbstractVector का सबटाइप घोषित करना होगा और दो फंक्शन बनाने होंगे:
-
capacity(cb::CircularBuffer): cb की क्षमता लौटाइए।
-
isfull(cb::CircularBuffer): अगर cb भरा हुआ है तो true लौटाइए।
इसके बाद आपको यह सुनिश्चित करना होगा कि Base के ये फंक्शन CircularBuffer के साथ ठीक से काम करें: append!, empty!, pop!, pushfirst, setindex!, collect, eltype, first, getindex, isempty, iterate, last, length, और size.
संकेत: आपको इन सभी फंक्शनों को बढ़ाने की ज़रूरत नहीं है, और बढ़ाना चाहिए भी नहीं! CircularBuffer को AbstractVector का सबटाइप घोषित करने से, AbstractVector के लिए बने जेनेरिक फंक्शन अब CircularBuffer को भी इनपुट के तौर पर स्वीकार करेंगे। Julia मैनुअल में इंटरफ़ेस वाला हिस्सा देखिए:
Julia की बहुत सारी शक्ति और विस्तार की क्षमता अनौपचारिक इंटरफ़ेसों के एक समूह से आती है। किसी कस्टम टाइप के लिए कुछ खास मेथड बढ़ाने भर से, उस टाइप के ऑब्जेक्ट को न सिर्फ ये सुविधाएँ मिल जाती हैं, बल्कि उन्हें ऐसे दूसरे मेथड में भी इस्तेमाल किया जा सकता है जो इन व्यवहारों पर आम तौर पर आगे बने होते हैं।
कौन से फंक्शन बढ़ाने हैं, यह समझने के लिए आपको Julia के Base मॉड्यूल का सोर्स कोड देखना होगा। किसी फंक्शन कॉल से जुड़ा सही कोड ढूँढने के लिए, आप @which मैक्रो का इस्तेमाल कर सकते हैं, जो बताता है कि वह कॉल किस खास मेथड पर भेजी जाती है। यह आपको वह फाइल और लाइन नंबर भी दिखाता है जहाँ वह मेथड परिभाषित है (IJulia के ज़रिए Jupyter Notebook में, यह GitHub पर मौजूद उस कोड का लिंक तक दे देता है)।
अगर आप REPL पर काम कर रहे हैं, तो हो सकता है आप @edit मैक्रो से सही फाइल और लाइन अपने डिफ़ॉल्ट टेक्स्ट एडिटर में खोलना पसंद करें।
