टेक्स्ट एडिटर के लिए डेटा संरचना

Question

यह एक साक्षात्कार प्रश्न है। पाठ संपादक में पाठ को संग्रहीत करने के लिए आप किस डेटा संरचना का उपयोग करेंगे?

Answer 1

अच्छे पुराने ZX-स्पेक्ट्रम एक पर (या अधिक, मैं नहीं जानता कि) पाठ exditor बहुत ही सरल संरचना का इस्तेमाल किया।

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

बफर लेआउट:

Hello, World! 
     ^------Cursor here 

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 
|H|e|l|l|o|,| |W| <free> |o|r|l|d|!| 
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 
|    ^  ^  | 
begin   cur1  cur2 end 

है यही कारण है, कैसे कुछ कार्यों को संपादित किया गया था:

Type a char: buffer[cur1++] = character 

Backspace:  cur1-- 

Cursor left: buffer[--cur2] = buffer[--cur1] 

Cursor right: buffer[cur1++] = buffer[cur2++] 

बफर कार्रवाई में:

   Hello, W..............orld! 
Press right  ^   ^
      Hello, Wo..............rld! 
Press backspace  ^   ^
      Hello, W...............rld! 
Press 0   ^   ^
      Hello, W0..............rld! 
        ^   ^

Answer 2

भले ही यह वास्तव में आपके प्रश्न का उत्तर नहीं है आप इस दिलचस्प लग सकते हैं:

Most efficient data structure to add styles to text

मैं आशा करता हूं कि चर्चा :-)

Answer 3

Rope

आकर्षक स्थानों के लिए जाना जाएगा

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

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

Answer 4

मैं जानता हूँ कि यह बहुत एक जवाब के लिए देर हो चुकी है, लेकिन मुझे The Craft of Text Editing पुस्तक वास्तव में उपयोगी मिली। इसमें उनके पेशेवरों और विपक्ष के साथ कई बफर मॉडल का विवरण शामिल है। दुर्भाग्यवश, इसमें रस्सियों की डेटा संरचना का उल्लेख नहीं है।

Answer 5

जैसा कि @ वोवैनियम ने पहले से ही बुनियादी सिद्धांत का उल्लेख किया है कि अंतराल बफर का उपयोग कैसे किया जा सकता है, मैंने सी/सी ++ का एक संस्करण लागू किया है।

कोड:

#include <stdio.h> 
#define SZ 1000 

char leftArray[SZ], rightArray[SZ]; 
int leftCount, rightCount; 
int cursorPos; 

/* 
* Private APIs 
*/ 

void printArray(){ 

    for(register int i = 0; i < leftCount; i++){ 
     printf("%c", leftArray[i]); 
    } 

    for(register int i = rightCount - 1; i >= 0; i--){ 
     printf("%c", rightArray[i]); 
    } 
    printf("\n"); 
} 

void adjust(int pos){ 

    while(leftCount > pos){ 
     rightArray[rightCount++] = leftArray[--leftCount]; 
    } 

    while(leftCount < pos){ 
     leftArray[leftCount++] = rightArray[--rightCount]; 
    } 
} 


/* 
* Public APIs for Text Editor 
*/ 

void init(){ 

    cursorPos = leftCount = rightCount = 0; 
} 

void addWord(char word[], int len){ 

    adjust(cursorPos); 

    for(register int i = 0; i < len; i++){ 
     leftArray[leftCount++] = word[i]; 
    } 
    leftArray[leftCount] = 0; 
} 

void addBackSpace(){ 

    adjust(cursorPos); 
    leftCount--; 
} 

void moveCurson(int newPosition){ 

    cursorPos = newPosition; 
} 

void subString(int pos, int length, char result[]){ 

     adjust(cursorPos); 

    int k = 0; 
     int l = 0; 
    while(k + pos < leftCount && k < length){ 
     result[k] = leftArray[pos + k]; 
     k++; 
    } 

    length -= k; 
    while(l < length){ 
     result[k++] = rightArray[rightCount - 1 - l]; 
     l++; 
    } 
}