नोटपैड जैसे संपादकों के कार्यान्वयन में कौन सी डेटा संरचना/एस का उपयोग किया जाता है। यह डेटा संरचना एक्स्टेंसिबल होनी चाहिए, और संस्करण, हटाना, स्क्रॉलिंग, पाठ की श्रेणी का चयन आदि जैसी विभिन्न सुविधाओं का समर्थन करना चाहिए?नोटपैड जैसे संपादक को लागू करने के लिए उपयुक्त सर्वोत्तम डेटा संरचना क्या है?
चेक बाहर नोटपैड की ++ कार्यान्वयन, आप पर SourceForge
बाहर चेक Ropes स्रोत देख सकते हैं। स्ट्रिंग्स के तेज़ डालने/हटाने/संपादित करने को संभालता है। रेंज आमतौर पर रस्सी कार्यान्वयन में समर्थित होते हैं, और स्क्रॉलिंग को उलटा इंडेक्स के साथ रस्सी में किया जा सकता है।
सामान्य बात यह है कि वर्णों की सरणी या सरणी की तरह कुछ है। पिछले कुछ वर्षों में इस पर बहुत सी चीजें हुई हैं: आपको this google search पर एक नज़र डालें।
हमने एक पुरानी मशीन के लिए एक संपादक लिखा (ध्यान रखें कि यह थोड़ी देर पहले, लगभग 1 9 86 था, इसलिए यह स्मृति से है, और कला की स्थिति तब से कुछ हद तक उन्नत हो सकती है) जिसे हम प्राप्त करने में कामयाब रहे स्व-प्रबंधित पूल से निश्चित मेमोरी ब्लॉक का उपयोग करके प्रदर्शन के अनुसार, चिल्लाओ।
इसमें दो पूल थे, जिनमें प्रत्येक विशिष्ट आकार के ब्लॉक (एक पूल लाइन संरचनाओं के लिए था, दूसरा लाइन-सेगमेंट संरचनाओं के लिए था) था। यह मूल रूप से लिंक्ड सूचियों की एक लिंक सूची थी।
मेमोरी को 'malloc()' से कॉल के पूर्व-आवंटित (प्रत्येक क्षेत्र के लिए) था, और हमने 65,535 ब्लॉक (0,5,534 के माध्यम से 0, ब्लॉक संख्या 65,535 को शून्य ब्लॉक माना जाता था, एक अंत-सूची सूचक)।
यह 65, 535 लाइनों (गद्देदार संस्करण के लिए 384 के या 512 के) के लिए अनुमति देता है और फ़ाइल आकार के लगभग 1.6 जी (आवंटित अंतरिक्ष के 2 जी लेते हुए), जो तब बहुत बड़ा था। वह सैद्धांतिक फ़ाइल आकार सीमा थी - मुझे नहीं लगता कि हमने कभी वास्तविकता से संपर्क किया क्योंकि हमने कभी भी लाइन सेगमेंट संरचनाओं का पूरा सेट आवंटित नहीं किया था।
स्मृति के हर छोटे ब्लॉक के लिए malloc() पर कॉल करने के लिए हमें बहुत तेज गति नहीं मिली, विशेष रूप से हम निश्चित आकार ब्लॉक (अंतिम अनुकूलित संस्करण में कॉल को रेखांकित करने सहित) के लिए अपनी याददाश्त आवंटन दिनचर्या को अनुकूलित कर सकते हैं।
दो पूल में संरचनाओं प्रत्येक पंक्ति एक एकल बाइट) होने के साथ, इस प्रकार थे:
Line structure (6/8 bytes) Line-segment structure (32 bytes)
+--------+ +--------+
|NNNNNNNN| |nnnnnnnn|
|NNNNNNNN| |nnnnnnnn|
|PPPPPPPP| |pppppppp|
|PPPPPPPP| |pppppppp|
|bbbbbbbb| |LLLLLLLL|
|bbbbbbbb| |LLLLLLLL|
|........| |xxxxxxxx|
|........| :25 more :
+--------+ : x lines:
+--------+
जहां: खंड पूल लाइन के लिए x बिंदु के अलावा अन्य
N अगली पंक्ति के लिए एक ब्लॉक नंबर था (शून्य अर्थ यह फ़ाइल में आखिरी पंक्ति थी)।P पिछली लाइन के लिए ब्लॉक संख्या (शून्य अर्थ यह है कि यह फ़ाइल में पहली पंक्ति थी)।b उस पंक्ति में पहले पंक्ति खंड के लिए ब्लॉक संख्या थी (शून्य अर्थ यह है कि रेखा खाली थी)।. आरक्षित पैडिंग (8 बाइट्स तक संरचना को टक्कर देने के लिए) था।n अगले लाइन सेगमेंट के लिए ब्लॉक नंबर था (शून्य अर्थ यह लाइन में अंतिम खंड था)।p पिछले लाइन सेगमेंट के लिए ब्लॉक नंबर था (शून्य अर्थ यह लाइन में पहला खंड था)।L सेगमेंट के लाइन ब्लॉक के लिए ब्लॉक नंबर था।x उस रेखा खंड में 26 वर्ण थे।कारण लाइन संरचना गद्देदार था वास्तविक स्मृति स्थल (3 बिट्स द्वारा छोड़ा स्थानांतरण में ब्लॉक नंबर के रूपांतरण में तेजी लाने के लिए किया गया था कि विशेष रूप से वास्तुकला और अतिरिक्त स्मृति में 6 से गुणा करने के लिए इस्तेमाल किया की तुलना में बहुत तेजी से केवल 128K किया गया था , कुल भंडारण के मुकाबले कम से कम) हालांकि हमने उन लोगों के लिए धीमे संस्करण प्रदान किए जो स्मृति के बारे में अधिक देखभाल करते थे।
हमारे पास 100 से 16-बिट मानों की एक सरणी भी थी जिसमें लाइन सेगमेंट (और लाइन नंबर ताकि हम जल्दी से विशिष्ट लाइनों पर जा सकें) लगभग उस प्रतिशत पर (ताकि सरणी [7] मोटे तौर पर उस रेखा थी फाइल में 7%) और प्रत्येक पूल में मुफ्त सूची बनाए रखने के लिए दो नि: शुल्क पॉइंटर्स (यह एक बहुत ही सरल एक तरीका सूची थी जहां संरचना में N या n इंगित किया गया था कि अगला नि: शुल्क ब्लॉक और नि: शुल्क ब्लॉक आवंटित किए गए थे, और वापस रखे गए , इन सूचियों के सामने)।
प्रत्येक लाइन सेगमेंट में वर्णों की गिनती रखने की कोई आवश्यकता नहीं थी क्योंकि 0-बाइट फाइलों में मान्य नहीं थे। प्रत्येक पंक्ति खंड को अंत में 0-बाइट्स रखने की अनुमति थी जिसे पूरी तरह अनदेखा कर दिया गया था। लाइनों को संपीड़ित किया गया था (यानी, रेखा खंड संयुक्त थे) जब भी वे संशोधित किए गए थे। इसने ब्लॉक उपयोग को कम रखा (बिना कम और लंबे कचरे के संग्रह के) और खोज-और-प्रतिस्थापन संचालन को भी बढ़ा दिया।
इन संरचनाओं का उपयोग बहुत पाठ के चारों ओर तेज़ संपादन, सम्मिलन, हटाना, खोज और नेविगेशन की अनुमति है, जहां आपको एक साधारण पाठ संपादक में अपनी अधिकांश प्रदर्शन समस्याओं का सामना करने की संभावना है।
चयन का उपयोग (हम इसे लागू नहीं किया था, क्योंकि यह एक पाठ मोड संपादक कि vi की तरह आदेशों में इस तरह के रूप में इस्तेमाल किया 3d 6 अक्षर को हटाने के लिए 3 लाइनों या 6x नष्ट करने के लिए किया गया था) एक {line#/block, char-pos} टपल होने से लागू किया जा सकता पाठ में पदों को चिह्नित करने के लिए, और चयन श्रेणी के लिए उन दो tuples का उपयोग करें।
विकिपीडिया का कहना है कि कई संपादक का उपयोग करते हैं। यह मूल रूप से मध्य में एक अप्रयुक्त स्थान के साथ एक सरणी है। कर्सर अंतर से ठीक पहले बैठता है, इसलिए कर्सर पर हटाना और सम्मिलन ओ (1) है। इसे लागू करने के लिए बहुत आसान होना चाहिए।
नोटपैड ++ के स्रोत कोड को देखते हुए (जैसा कि क्रिस बैलेंस इस धागे here में सुझाया गया है) दिखाता है कि वे एक अंतर बफर का भी उपयोग करते हैं। आप उससे कुछ कार्यान्वयन विचार प्राप्त कर सकते हैं।
HexEdit के लेखक जेम्स ब्राउन द्वारा Piece Chains के बारे में एक उत्कृष्ट लेख है।
संक्षेप में: टुकड़ा श्रृंखला आपको पाठ में किए गए परिवर्तनों को रिकॉर्ड करने की अनुमति देती है। लोड होने के बाद, आपके पास एक टुकड़ा श्रृंखला है जो पूरे पाठ को फैलाती है। अब आप बीच में कहीं भी डालें।
एक नया बफर आवंटित करने के बजाय, पाठ को चारों ओर प्रतिलिपि बनाने के बजाय, आप दो नए टुकड़े बनाते हैं और मौजूदा को संशोधित करते हैं: मौजूदा में अब सम्मिलन बिंदु तक टेक्स्ट शामिल है (यानी।आप बस टुकड़े की लंबाई बदलते हैं), फिर आपके पास नए पाठ के साथ एक टुकड़ा है और उसके बाद सम्मिलन के बाद सभी पाठों के साथ एक नया टुकड़ा है। मूल पाठ अपरिवर्तित छोड़ दिया गया है।
पूर्ववत/फिर से करने के लिए, आपको याद है कि आपने कौन से टुकड़े जोड़े/हटाए/बदले।
टुकड़ा श्रृंखला का उपयोग करते समय सबसे जटिल क्षेत्र यह है कि दृश्यमान पाठ और मेमोरी संरचना में ऑफ़सेट के बीच 1: 1 मैपिंग नहीं है। आपको या तो श्रृंखला खोजनी है या आपको किसी प्रकार की बाइनरी पेड़ संरचना को बनाए रखना होगा।
Emacs विकिपीडिया के अनुसार इसका भी उपयोग करता है –