आधुनिक पाठ संपादक न केवल बीप करने में सक्षम हैं और कार्यक्रम को छोड़ने के लिए नहीं। यह पता चला है कि उनके अंदर एक बहुत ही जटिल चयापचय उबलता है। जानना चाहते हैं कि निर्देशांक जल्दी से पुनर्गणना करने के लिए क्या किया जा रहा है, कैसे शैलियों, तह और सॉफ्टवेप्स पाठ से जुड़े हुए हैं और यह सब कैसे अपडेट किया जाता है, कार्यात्मक डेटा संरचना और प्राथमिकता कतार का इसके साथ क्या करना है, साथ ही उपयोगकर्ता को कैसे धोखा देना है - बिल्ली का स्वागत!



यह लेख जोकर 2017 के साथ एलेक्सी कुद्रीवत्सेव की रिपोर्ट पर आधारित है। एलेक्सी 10 साल से जेटब्रेन में इंटेलीज आईडीईए लिख रहे हैं। कट के तहत आपको रिपोर्ट का वीडियो और टेक्स्ट ट्रांसक्रिप्ट मिलेगा।

पाठ संपादकों के अंदर डेटा संरचनाएं

संपादक कैसे काम करता है, इसे समझने के लिए, आइए इसे लिखें।



यही है, हमारा सबसे सरल संपादक तैयार है।

संपादक के अंदर, पाठ को वर्णों के एक सरणी में संग्रहीत करना सबसे आसान है, या, जावा वर्ग स्ट्रिंगरफ़र में (स्मृति संगठन के संदर्भ में) समान (क्या है)। ऑफसेट द्वारा कुछ वर्ण प्राप्त करने के लिए, हम StringBuffer.charAt (i) विधि कहते हैं। और इसमें उस चरित्र को सम्मिलित करने के लिए जिसे हमने कीबोर्ड पर टाइप किया था, हम StringBuffer.insert () विधि को कहते हैं, जो वर्ण को बीच में कहीं भी सम्मिलित करता है।

इस संपादक की सभी सादगी और मूर्खता के बावजूद, जो सबसे दिलचस्प है, वह सबसे अच्छा विचार है जिसे आप खोज सकते हैं। यह सरल और लगभग हमेशा तेज दोनों है।

दुर्भाग्य से, इस संपादक के साथ एक स्केल समस्या उत्पन्न होती है। कल्पना करें कि हमने इसमें बहुत सारे पाठ मुद्रित किए हैं और बीच में एक और पत्र डालने जा रहे हैं। निम्नलिखित होगा। हमें तत्काल इस पत्र के लिए कुछ जगह खाली करने की जरूरत है ताकि अन्य सभी अक्षर एक चरित्र को आगे बढ़ा सकें। ऐसा करने के लिए, हम इस पत्र को एक स्थिति से स्थानांतरित करते हैं, फिर अगला और इसी तरह, पाठ के अंत तक।

यहाँ है कि यह स्मृति में कैसा दिखेगा:



इन सभी मेगाबाइट को शिफ्ट करना बहुत अच्छा नहीं है: यह धीमा है। बेशक, एक आधुनिक कंप्यूटर के लिए, यह एक trifling मामला है - आगे और पीछे जाने के लिए किसी प्रकार का दयनीय मेगाबाइट। लेकिन बहुत सक्रिय पाठ परिवर्तन के लिए, यह ध्यान देने योग्य हो सकता है।

बीच में एक चरित्र डालने की इस समस्या को हल करने के लिए, बहुत समय पहले "गैप बफर" नामक एक वर्कअराउंड के साथ आया था।

गैप बफर

गैप गैप है। बफर है, जैसा कि आप कल्पना कर सकते हैं, एक बफर। गैप बफर डेटा संरचना एक ऐसा खाली बफर है जिसे हम अपने पाठ के बीच में रखते हैं, बस मामले में। यदि हमें कुछ प्रिंट करने की आवश्यकता है, तो हम तेजी से टाइपिंग के लिए इस छोटे पाठ बफर का उपयोग करते हैं।



डेटा संरचना थोड़ी बदल गई है - सरणी जगह में बनी हुई है, लेकिन दो संकेत दिखाई दिए हैं: बफर की शुरुआत में और इसके अंत में। कुछ ऑफसेट पर संपादक से एक चरित्र लेने के लिए, हमें यह समझने की आवश्यकता है कि क्या यह बफर से पहले या बाद में है और ऑफसेट को थोड़ा सही करता है। और एक चरित्र को सम्मिलित करने के लिए, हमें सबसे पहले गैप बफर को इस स्थान पर ले जाना होगा और इन पात्रों को भरना होगा। और, ज़ाहिर है, अगर हम अपने बफर से आगे निकल गए, तो किसी तरह इसे फिर से बनाएं। तस्वीर में यह कैसा दिख रहा है।



जैसा कि आप देख सकते हैं, हम पहली बार एक छोटे से गैप-बफर (नीली आयत) पर लंबे समय तक संपादन स्थान पर चलते हैं (बस इसके बाएँ और दाएँ किनारों से पात्रों को स्वैप करते हुए)। फिर हम इस बफ़र का उपयोग करते हैं, वहां वर्ण टाइप करते हैं।

जैसा कि आप देख सकते हैं, वर्णों की मेगाबाइट्स की कोई गति नहीं है, लगातार समय के लिए इंसर्ट बहुत तेज है, और ऐसा लगता है कि हर कोई खुश है। सब कुछ ठीक लग रहा है, लेकिन अगर हमारा प्रोसेसर बहुत धीमा है, तो ध्यान देने योग्य समय गैप-बफर और टेक्स्ट को आगे-पीछे करने में बर्बाद हो जाता है। यह विशेष रूप से बहुत छोटे मेगाहर्ट्ज़ के समय पर ध्यान देने योग्य था।

टुकड़ा मेज

बस उस समय, Microsoft नामक एक निगम ने एक पाठ संपादक वर्ड लिखा था। उन्होंने "टुकड़ा तालिका", अर्थात् "टुकड़ा तालिका" नामक संपादन को गति देने के लिए एक और विचार लागू करने का निर्णय लिया। और उन्होंने संपादक के पाठ को उसी सरलतम वर्णों में सहेजने का प्रस्ताव दिया, जो परिवर्तित नहीं होगा, और इसके सभी बदलावों को इन बहुत ही संपादित टुकड़ों से अलग तालिका में डाल दिया है।



इस प्रकार, यदि हमें ऑफसेट द्वारा कुछ वर्ण खोजने की आवश्यकता है, तो हमें इस टुकड़े को खोजने की आवश्यकता है जिसे हमने संपादित किया है और इस चरित्र को इसमें से निकाला है, और यदि यह नहीं है, तो मूल पाठ पर जाएं। एक प्रतीक सम्मिलित करना आसान हो जाता है, हमें बस इस नए टुकड़े को तालिका में बनाना और जोड़ना होगा। यहाँ यह है कि यह तस्वीर में कैसा दिखता है:



यहां हम ऑफसेट 5 पर स्थान को हटाना चाहते थे। ऐसा करने के लिए, हम टुकड़ा तालिका में दो नए टुकड़े जोड़ते हैं: एक पहले टुकड़े ("बमर") को इंगित करता है, और दूसरा संपादन ("भेड़") के बाद टुकड़े को इंगित करता है। यह पता चला है कि उनसे अंतर गायब हो जाता है, इन दो टुकड़ों को एक साथ चिपका दिया जाता है, और हमें पहले से ही एक स्थान के बिना एक नया पाठ मिलता है: "ओब्लोमोव्त्सी"। फिर हम नए पाठ ("ओब्लोमोविज़्म से पीड़ित") को अंत तक जोड़ते हैं। एक अतिरिक्त बफ़र का उपयोग करें और टुकड़ा तालिका में एक नया टुकड़ा जोड़ें जो इस नए पाठ में जोड़े गए बिंदुओं को इंगित करता है।

जैसा कि आप देख सकते हैं, आगे और पीछे कोई आंदोलन नहीं है, सभी पाठ जगह में बने हुए हैं। बुरी खबर यह है कि प्रतीक को प्राप्त करना कठिन हो रहा है, क्योंकि इन सभी टुकड़ों के माध्यम से छांटना बहुत कठिन है।

संक्षेप में देना।

टुकड़ा तालिका के बारे में क्या अच्छा है:

• जल्दी से एम्बेड;
• पूर्ववत करना आसान;
• संलग्न-केवल।

क्या बुरा है:

• किसी दस्तावेज़ तक पहुंचना बहुत मुश्किल है;
• इसे लागू करना बहुत मुश्किल है।

आइए देखें कि हम आम तौर पर किसका उपयोग करते हैं।

NetBeans, Eclipse और Emacs गैप बफर का उपयोग करते हैं - अच्छी तरह से किया! Vi परेशान नहीं करता है और सिर्फ लाइनों की एक सूची का उपयोग करता है। Word टुकड़ा तालिका का उपयोग करता है (उन्होंने हाल ही में अपने प्राचीन प्रकारों को निर्धारित किया है और वहां आप कुछ समझ भी सकते हैं)।

परमाणु अधिक रोचक है। कुछ समय पहले तक, उन्होंने परेशान नहीं किया था और लाइनों की एक जावास्क्रिप्ट सूची का उपयोग किया था। और फिर उन्होंने सी ++ में सब कुछ फिर से लिखने का फैसला किया और एक जटिल संरचना को ढेर कर दिया, जो कि टुकड़ा तालिका के समान प्रतीत होता है। लेकिन इन टुकड़ों को सूची में संग्रहीत नहीं किया जाता है, लेकिन पेड़ में, और तथाकथित छीले पेड़ में - यह एक ऐसा पेड़ है जो इसमें डाले जाने पर स्वयं को समायोजित करता है, ताकि हाल के आवेषण तेजी से हो। उन्होंने बहुत जटिल काम किया।

Intellij IDEA क्या उपयोग करता है?
नहीं, गैप-बफर नहीं। नहीं, आप भी गलत हैं, एक टुकड़ा तालिका नहीं है।
हां, बिल्कुल सही, अपनी बाइक।

तथ्य यह है कि पाठ को संग्रहीत करने के लिए IDE की आवश्यकताएं एक नियमित पाठ संपादक की तुलना में थोड़ी अलग हैं। IDE को प्रतिस्पर्धात्मकता जैसी विभिन्न मुश्किल चीजों के लिए समर्थन की आवश्यकता होती है, अर्थात संपादक से पाठ के समानांतर पहुँच। उदाहरण के लिए, ताकि कई अलग-अलग बेक किए गए सामान इसे पढ़ सकें और कुछ कर सकें। (निरीक्षण कोड का एक छोटा सा टुकड़ा है जो प्रोग्राम को एक या दूसरे तरीके से पार्स करता है - उदाहरण के लिए, NullPointerException को फेंकने वाले स्थानों की तलाश में)। IDE को संपादन योग्य पाठ संस्करण समर्थन भी चाहिए। जब आप किसी दस्तावेज़ के साथ काम कर रहे होते हैं तो कई संस्करण एक साथ स्मृति में होते हैं ताकि ये लंबी प्रक्रिया पुराने संस्करण का विश्लेषण करती रहे।

समस्याओं

प्रतिस्पर्धात्मकता / संस्करण

समानता बनाए रखने के लिए, टेक्स्ट ऑपरेशंस को आमतौर पर "सिंक्रोनाइज़", या रीड-/ राइट-लॉक में लपेटा जाता है। दुर्भाग्य से, यह बहुत अच्छा नहीं है। एक अन्य दृष्टिकोण है इम्यूटेबल टेक्स्ट, यानी एक अपरिवर्तनीय टेक्स्ट रिपॉजिटरी।



यहां एक संपादक एक सहायक डेटा संरचना के रूप में एक अपरिवर्तनीय दस्तावेज़ के साथ कैसा दिखता है।

डेटा संरचना कैसे काम करती है?

वर्णों की एक सरणी के बजाय, हमारे पास एक नई वस्तु होगी प्रकार ImmutableText, जो पाठ को एक पेड़ के रूप में संग्रहीत करता है, जहां चादरों में छोटे पदार्थ जमा होते हैं। कुछ ऑफसेट पर पहुंचते समय, वह इस पेड़ में बहुत नीचे की शीट तक पहुंचने की कोशिश करता है, और उसे पहले से ही उस प्रतीक से पूछा जाएगा जिसे हम संदर्भित कर रहे थे। और जब आप पाठ सम्मिलित करते हैं, तो वह एक नया पेड़ बनाता है और उसे पुरानी जगह पर बचाता है।



उदाहरण के लिए, हमारे पास "कैलोरी-मुक्त" पाठ के साथ एक दस्तावेज है। यह वृक्षों के रूप में कार्यान्वित किया जाता है, जिसमें दो प्रकार के पदार्थ "दानव" और "उच्च-कैलोरी" होते हैं। जब हम बीच में "सुंदर" लाइन डालना चाहते हैं, तो हमारे दस्तावेज़ का एक नया संस्करण बनाया जाता है। और ठीक है, एक नई जड़ बनाई गई है, जिसमें तीन शीट पहले से ही संलग्न हैं: "दानव", "पर्याप्त" और "उच्च-कैलोरी"। इसके अलावा, इनमें से दो नई शीट हमारे दस्तावेज़ के पहले संस्करण को संदर्भित कर सकती हैं। और जिस शीट में हमने "सुंदर" लाइन डाली थी, उसके लिए एक नया वर्ट आवंटित किया गया है। यहाँ पहला संस्करण और दूसरा संस्करण एक ही समय में उपलब्ध हैं और वे सभी अपरिवर्तनीय, अपरिवर्तनीय हैं। सब कुछ अच्छा लग रहा है।

कौन क्या मुश्किल संरचनाओं का उपयोग करता है?



उदाहरण के लिए, गनोम में, उनके कुछ मानक विजेट रस्सी नामक संरचना का उपयोग करते हैं। शी-एडिटर, रफ लेविन के नए शानदार संपादक, परसेंट रोप का उपयोग करते हैं। और Intellij IDEA इस इम्मुटेबल ट्री का उपयोग करता है। इन सभी नामों के पीछे, वास्तव में, कमोबेश एक ही डेटा संरचना होती है जिसमें पाठ का वृक्ष जैसा प्रतिनिधित्व होता है। सिवाय इसके कि GtkTextBuffer Mutable Rope का उपयोग करता है, यानी कि उत्परिवर्तित कोने के साथ एक पेड़, और Intellij IDEA और Xi-Editor - Immutable।

आधुनिक आईडीई में एक चरित्र भंडार का विकास करते समय विचार करने वाली अगली बात को मल्टीकाट कहा जाता है। यह सुविधा आपको कई स्थानों पर एक साथ कई गाड़ियों का उपयोग करने की अनुमति देती है।



हम कुछ प्रिंट कर सकते हैं और एक ही समय में दस्तावेज़ के कई स्थानों पर हम जो हम वहां मुद्रित करते हैं उसे सम्मिलित करते हैं। यदि हम देखते हैं कि हमारी डेटा संरचनाएं, जिनकी हमने जांच की, मल्टीकार्ट्स पर प्रतिक्रिया करते हैं, तो हम कुछ दिलचस्प देखेंगे।



यदि हम अपने पहले ही प्रधान संपादक में एक चरित्र सम्मिलित करते हैं, तो स्वाभाविक रूप से वर्णों का एक गुच्छा आगे और पीछे स्थानांतरित करने के लिए एक रैखिक मात्रा में समय लगेगा। इसे O (N) लिखा जाता है। गैप बफर पर आधारित संपादक के लिए, बदले में, निरंतर समय की आवश्यकता होती है, जिसके लिए उसे गढ़ा गया था।

एक अपरिवर्तनीय पेड़ के लिए, समय आकार पर लघुगणक पर निर्भर करता है, क्योंकि आपको पहले पेड़ के ऊपर से उसके पत्ते पर जाना चाहिए - यह लघुगणक है, और फिर नए पेड़ के लिए नए कोने बनाने के लिए मार्ग पर सभी कोने के लिए - यह फिर से लघुगणक है। टुकड़ा तालिका भी एक निरंतर की आवश्यकता है।
लेकिन सब कुछ थोड़ा बदल जाता है अगर हम एक चरित्र को मल्टी-कैरिएज के साथ एक संपादक में डालने के समय को मापने की कोशिश करते हैं, अर्थात, कई स्थानों पर एक साथ सम्मिलित करना। पहली नज़र में, समय सी के एक कारक द्वारा आनुपातिक रूप से वृद्धि करने के लिए लगता है - उन स्थानों की संख्या जहां प्रतीक डाला जाता है। गैप बफर के अपवाद के साथ वास्तव में यही होता है। उनके मामले में, C के बजाय समय, अप्रत्याशित रूप से कुछ समझ से बाहर C * L समय बढ़ाता है, जहां L, कैरिज के बीच की औसत दूरी है। ऐसा क्यों हो रहा है?

कल्पना कीजिए कि हमें अपने दस्तावेज़ में दो स्थानों पर ", पर" लाइन डालने की आवश्यकता है।



इस समय संपादक में ऐसा ही होता है।

• संपादक में अंतर-बफर बनाएं (चित्र में थोड़ा नीला आयत);
• हम दो गाड़ियां शुरू करते हैं (काली बोल्ड वर्टिकल लाइन्स);
• हम छापने की कोशिश कर रहे हैं;
• हमारे गैप बफर में एक अल्पविराम डालें;
• अब आपको इसे दूसरी गाड़ी के स्थान पर डालना चाहिए;
• ऐसा करने के लिए, हमें अपने गैप बफर को अगली गाड़ी की स्थिति में ले जाना होगा;
• दूसरे स्थान पर एक अल्पविराम छापें;
• अब आपको पहली गाड़ी की स्थिति में अगले चरित्र को सम्मिलित करने की आवश्यकता है;
• और हमें अपने गैप बफर को पीछे धकेलना होगा;
• पत्र "एन" डालें;
• और हम अपने लंबे समय तक पीड़ित बफर को दूसरी गाड़ी के स्थान पर ले जाते हैं;
• हम वहां अपना "एन" डालते हैं;
• अगला वर्ण सम्मिलित करने के लिए बफ़र को वापस ले जाएँ।

महसूस करें कि सब कुछ कहां चल रहा है?

हां, यह पता चलता है कि बफर के इन कई आंदोलनों के कारण, हमारा कुल समय बढ़ता है। ईमानदारी से, यह नहीं है कि यह प्रत्यक्ष रूप से भयावह हो गया है क्योंकि यह बढ़ गया है - आधुनिक कंप्यूटर के लिए आगे और पीछे मेगाबाइट, गीगाबाइट को स्थानांतरित करने के लिए कोई समस्या नहीं है, लेकिन यह दिलचस्प है कि यह डेटा संरचना बहुस्तरीय के मामले में मौलिक रूप से अलग तरह से काम करती है।

बहुत सारी लाइनें? LineSet!

एक नियमित पाठ संपादक में अन्य क्या समस्याएं हैं? सबसे कठिन समस्या स्क्रॉल है, अर्थात, संपादक को अगली पंक्ति में ले जाते समय रीडायरेक्ट करना।



जब संपादक स्क्रॉल करता है, तो हमें यह समझने की जरूरत है कि किस प्रतीक से, हमें अपनी छोटी खिड़की में पाठ को शुरू करने के लिए किस प्रतीक से चाहिए। ऐसा करने के लिए, हमें यह समझने की आवश्यकता है कि कौन सी रेखा किस ऑफसेट से मेल खाती है।



इसके लिए एक स्पष्ट इंटरफ़ेस है, जब हमें लाइन नंबर द्वारा पाठ में इसके ऑफसेट को समझने की आवश्यकता होती है। और इसके विपरीत, पाठ में ऑफसेट द्वारा यह समझने के लिए कि यह किस पंक्ति में है। इसे जल्दी कैसे किया जा सकता है?

उदाहरण के लिए, इस तरह:

इन पंक्तियों को एक पेड़ में व्यवस्थित करें और इस पेड़ के प्रत्येक शीर्ष को रेखा की शुरुआत को बदलकर और रेखा के अंत को शिफ्ट करके चिह्नित करें। और फिर, ऑफसेट द्वारा यह समझने के लिए कि यह किस लाइन में स्थित है, आपको बस इस पेड़ में एक लघुगणकीय खोज चलाने और इसे खोजने की आवश्यकता है।



एक और तरीका और भी आसान है।

तालिका में पंक्तियों की शुरुआत और रेखाओं के अंत की भरपाई करें। और फिर, लाइन नंबर द्वारा शुरुआत और अंत के ऑफसेट को खोजने के लिए, आपको सूचकांक तक पहुंचने की आवश्यकता होगी।



दिलचस्प है, वास्तविक दुनिया में, दोनों तरीकों का उपयोग किया जाता है।



उदाहरण के लिए, एक्लिप्स एक लकड़ी की संरचना का उपयोग करता है, जैसा कि आप देख सकते हैं, पढ़ने और अद्यतन करने के लिए एक लघुगणक समय में काम करता है। और IDEA एक टेबल संरचना का उपयोग करता है, जिसके लिए पढ़ना एक तेजी से स्थिर है, यह एक तालिका में एक इंडेक्स रिवर्सल है, लेकिन पुनर्निर्माण बल्कि धीमी है, क्योंकि आपको पंक्ति की लंबाई बदलते समय पूरे टेबल को पुनर्निर्माण करने की आवश्यकता होती है।

अभी भी बहुत सारी लाइनें? Foldings!

पाठ संपादकों के बीच ठोकर खाने के अलावा और क्या बुरा है? उदाहरण के लिए, तह। ये पाठ के टुकड़े हैं जिन्हें आप "ढह" सकते हैं और इसके बजाय कुछ और दिखा सकते हैं।



चित्र में हरे रंग की पृष्ठभूमि पर ये डॉट्स हमारे पीछे बहुत सारे प्रतीकों को छिपाते हैं, लेकिन अगर हम उन्हें देखने में रुचि नहीं रखते हैं (उदाहरण के लिए, उदाहरण के लिए, सबसे लंबे बोरिंग जावा डॉक्स या आयात सूची), हम उन्हें छिपाते हैं, उन्हें संक्षिप्त करते हैं। अंडाकार।

और यहां फिर से आपको यह समझने की आवश्यकता है कि यह कब समाप्त होता है और कब जिस क्षेत्र को हमें दिखाने की आवश्यकता होती है, और यह सब जल्दी से कैसे अपडेट किया जाए? यह कैसे आयोजित किया जाता है, मैं थोड़ी देर बाद बताऊंगा।

बहुत लंबी लाइनें? मुलायम लपेटो!

इसके अलावा, आधुनिक संपादक सॉफ्ट रैप के बिना नहीं रह सकते। चित्र दिखाता है कि डेवलपर ने न्यूनतम होने के बाद जावास्क्रिप्ट फ़ाइल को खोला और तुरंत इसे पछतावा हुआ। यह विशाल जावास्क्रिप्ट लाइन, जब हम इसे संपादक में दिखाने का प्रयास करते हैं, किसी भी स्क्रीन में फिट नहीं होगा। इसलिए, सॉफ्ट रैप इसे जबरन कई लाइनों में फाड़ देता है और स्क्रीन में बंद कर देता है।
यह कैसे आयोजित किया जाता है - बाद में।

बहुत कम सौंदर्य

और अंत में, मैं टेक्स्ट एडिटर्स के लिए भी सुंदरता लाना चाहता हूं। उदाहरण के लिए, कुछ शब्दों को उजागर करें। ऊपर की तस्वीर में, कीवर्ड बोल्ड ब्लू, इटैलिक द्वारा कुछ स्थिर तरीकों, कुछ एनोटेशन - को भी एक अलग रंग में हाइलाइट किया गया है।

तो आप अभी भी फोल्डिंग, सॉफ्ट-रैप्स और हाइलाइट्स को कैसे स्टोर और प्रोसेस करते हैं?
यह पता चला है कि यह सब, सिद्धांत रूप में, एक और एक ही कार्य है।

बहुत कम सौंदर्य? रेंज हाइलाइटर्स!

इन सभी विशेषताओं का समर्थन करने के लिए, हम सभी को करने की आवश्यकता है, पाठ में दिए गए ऑफसेट पर कुछ पाठ विशेषताओं को चिपकाने के लिए है, उदाहरण के लिए, रंग, फ़ॉन्ट या तह के लिए पाठ। इसके अलावा, इन पाठ विशेषताओं को इस स्थान पर हर समय अपडेट किया जाना चाहिए ताकि वे सभी प्रकार के सम्मिलन और विलोपन से बचे रहें।

यह आमतौर पर कैसे लागू किया जाता है? स्वाभाविक रूप से, एक पेड़ के रूप में।

समस्या: बहुत अधिक सौंदर्य? अंतराल का पेड़!

उदाहरण के लिए, यहां हमारे पास कई पीले हाइलाइट हैं जिन्हें हम पाठ में रखना चाहते हैं। हम इन हाइलाइट्स के अंतराल को एक खोज ट्री, तथाकथित अंतराल ट्री में जोड़ते हैं। यह वही खोज पेड़ है, लेकिन थोड़ा पेचीदा है क्योंकि हमें संख्याओं के बजाय अंतरालों को संग्रहीत करने की आवश्यकता है।

और चूंकि दोनों स्वस्थ और छोटे अंतराल हैं, उन्हें कैसे सॉर्ट करना है, एक-दूसरे के साथ उनकी तुलना करें और उन्हें एक पेड़ में डाल दें यह एक गैर-तुच्छ कार्य है। हालांकि कंप्यूटर विज्ञान में बहुत व्यापक रूप से जाना जाता है। फिर किसी तरह अपने अवकाश को देखें कि यह कैसे काम करता है। इसलिए, हम अपने सभी अंतराल एक पेड़ में डालते हैं, और फिर बीच में कहीं पाठ में प्रत्येक परिवर्तन इस पेड़ में एक लघुगणकीय परिवर्तन की ओर जाता है। उदाहरण के लिए, किसी चरित्र को सम्मिलित करने से उस चरित्र के दाईं ओर सभी अंतराल को अपडेट करने में परिणाम होना चाहिए। ऐसा करने के लिए, हम इस प्रतीक के लिए सभी प्रमुख कोने पाते हैं और संकेत देते हैं कि उनके सभी शीर्षों को एक प्रतीक को दाईं ओर ले जाना चाहिए।

अभी भी सौंदर्य चाहते हैं? Ligatures!

अभी भी एक ऐसी भयानक चीज है - लाइगर्स, जिसका मैं भी समर्थन करना चाहूंगा। ये अलग-अलग सुंदरियाँ हैं, जैसे संकेत "! =" एक बड़े ग्लिफ़ के रूप में तैयार किया गया है "बराबर नहीं" और इसी तरह। सौभाग्य से, यहाँ हम इन ligatures का समर्थन करने के लिए एक स्विंग तंत्र पर भरोसा कर रहे हैं। और, हमारे अनुभव में, वह स्पष्ट रूप से सबसे सरल तरीके से काम करता है। फॉन्ट के अंदर, इन सभी जोड़े के पात्रों की एक सूची संग्रहीत की जाती है, जो जब एक साथ जुड़ते हैं, तो कुछ प्रकार के मुश्किल संयुक्ताक्षर बनाते हैं। फिर, जब रेखा खींचती है, तो स्विंग केवल इन सभी जोड़ियों पर निर्भर करता है, आवश्यक लोगों को ढूंढता है और तदनुसार उन्हें आकर्षित करता है। यदि आपके पास फ़ॉन्ट में बहुत सारे लिगचर हैं, तो, जाहिर है, इसे प्रदर्शित करना आनुपातिक रूप से धीमा होगा।

ब्रेक लगाना

— , , — , , .



Intellij IDEA , - , , , :

• , completion popup', completion', , , - «Enter».
• , - , Perforce, - .
• , - , , - .
• , , , .
• injected-, , , - .
• auto popup handler, , , .
• info , , . selection remove, selection , . selection , .
• typed handler, , .
• .
• undo, virtual space' write action.
• , .

!

, , . , . , listener , , - . editor view. - listener'.

, , - DocumentListener?

Editor.documentChanged() :

• error stripe;
• gutter size, ;
• editor component size, ;
• ;
• soft wrap, ;
• repaint().

repaint() — Swing, . , Repaint Swing.

- , repaint , :



paint-, , .

, , ?



, , . Intellij IDEA .



, - - , , , . ! , , , - — ! , - . . «Zero latency typing».

— .

? , — , Google Docs - - .

:

• ;
• .

, , .

- . , , . . — , «intention preservation». , - , , , . — . , - , .

Operation transformation

, , «operation transformation». . , - : , . Operation transformation . , , , - . , . , - . , , .

, , , . «TP2 puzzle».



- , , . , Operation transformation , , , («»). («»). , . , Operation transformation, - .

, Google Docs, Google Wave - Etherpad. Operation transformation .

Conflict-free replicated data type

: « , OT!» , , . , , , , 100% . «CRDT» (Conflict-free replicated data type).



, , . , , , . , . - ( ), () ( ).



?

हां। , G-counter', , . , . «+1» , «+1» , , — «2». , , . G-counter, , . G-counter, . , , . . — . , CRDT. , .

Conflict-free replicated inserts

, , , . , , .

, , - - , , , , . , , , , . , , , , 2 «», , «» «» «».

Conflict-free replicated deletes

. , , , - . , , . , , , .
, .

Conflict-free replicated edits

, , CRDT - , , Xi-Editor, Fuchsia. , , .

Zipper

, «Zipper». , , . , , . , ( «» , , « »). , - . , - , . Zipper.

, . .



Zipper , (« »). Zipper' . — . (), , . , Zipper, - , . , , , ( ). , ( ). , . , .

, .

? -, , , , . , , . -, , . . आपका धन्यवाद

→
→

संदर्भ

Zipper data structure
CRDT in Xi Editor



, Visual Studio Code editor Piece Table .
, - .

जावा 11 सहित और भी अधिक शक्तिशाली रिपोर्ट चाहते हैं? फिर हम जोकर 2018 पर आपका इंतजार कर रहे हैं। इस वर्ष के वक्ता: जोश लॉन्ग, जॉन मैक्लीन, मार्कस हिर्थ, रॉबर्ट शोल्टे और अन्य समान रूप से शांत वक्ता। सम्मेलन से पहले 17 दिन शेष हैं। साइट पर टिकट ।