文本編輯器中的行管理

Question

我一直在使用文本編輯器一段時間。我從頭開始進行自定義編輯控制，現在我已經掌握了基本知識。我面臨的問題是關於生產線管理。因爲，我的程序依賴於將輸入文本分成行（文本逐行打印），所以行管理非常重要。我正在使用std :: vector來存儲行位置。我正在使用Piece Table進行文本處理，但爲了簡單起見，假設我有一組字符。每次用戶按下回車鍵時，我會在行向量中添加/插入一個元素。問題是每次用戶插入角色時，整個結構都會受到干擾。例如：

  0 1 2 3 4 5 6 7 8 9 10 
text = ['h','e','l','l','o','\n','W','o','r','l','d'] 
state of line vector : 
line[0] = 0 
line[1] = 6 

比方說用戶的文本[2]之後插入一個字符（「X」）：

  0 1 2 3 4 5 6 7 8 9 10 11 
text = ['h','e','l','x','l','o','\n','W','o','r','l','d'] 
state of line vector : 
line[0] = 0 
line[1] = 6 

由於插入的，我需要更新每個的值元素在當前行之後的行向量中。刪除也一樣。如果程序中有1000行，並且用戶編輯了第一行，那麼更新所有999個元素（第一行除外）的效率會非常低。

我在想什麼是保持每條線彼此獨立。但是，如果將現有的線路劃分爲兩條線路，這會導致複雜化。所以我想知道什麼是解決問題的好方法？

編輯： 只是爲了澄清，我使用的是一個名爲Piece Table的數據結構。我沒有使用字符數組。以下是一個表格數據結構： http://www.cs.unm.edu/~crowley/papers/sds.pdf

Answer 1

許多編輯器所使用的經典的數據結構是「Gap Buffer」。這基本上有一個活動周圍的工作空間，活動發生的地方，以便本地操作快速發生。然後，當光標移動時，假設發生改變，間隙將隨之移動。

就行計算而言，現代系統足夠快，您幾乎可以簡單地掃描緩衝區並查找行。好的是，你不需要在大多數操作上這樣做，所以你不要一直這麼做。此外，緩衝區中的物理線（即以EOL標記結尾的字符集合）和柔和線（ala文字包裝等）之間存在差異。考慮一個現代的文字處理器，其中的段落通常是單一的「行」，但換行到頁邊距。當然，你可以處理這種方式。最後，對於鍵盤上的大多數操作，可以簡單地使用相對位置（例如，如果插入一條新線，則可以直接將新線條標記添加到線陣列，因爲您已經知道了點在緩衝區內）。但是，當你這樣做的時候，比如說一個大型的多行代碼粘貼操作，它可能會更快地將所有內容填充並重新計算整個緩衝區（作爲替代方案，您總是可以將粘貼分隔成行，然後插入一行一個在幕後，就像一條正常的線）。

對於巨大的緩衝區或緩慢的計算機，您可能需要考慮不必擔心如此多的全局狀態（確切地說，緩衝區中有多少行，您可能在哪一行等等）一點，並開始這種重新計算的背景。最有可能的是暫停會很小（但如果你打字的話會很煩人），並且一旦人類停下來思考自己的想法，就會馬上趕上。顯然，這可能會使設計複雜化，並且您可能會暫時使用現代硬件上的蠻力。

Answer 2

向量將正常工作。

考慮讓該行動態分配，並讓該向量存儲一個指向該行的指針。將一堆指針移動到行比移動行自己便宜得多。

您也可能要考慮某種Gap Buffer techniques.

Answer 3

如果我理解這個問題，你沿着這些線路跟蹤的線位置的一個輔助數據結構：

line offset length 
    0  0  65 
    1  65  30 
    2  95  50 
    3  145  1 
    4  146  13 
... 

如果用d第n行的長度發生變化，那麼你有用d來更新所有剩餘行的偏移量。當線路很多時，這很慢。

您可以跟蹤地標。而不是從序列開始的偏移量，您將它們與某個地標相關聯。

假設您爲每100行創建一個里程碑。由於第一個地標位於文件的開頭，因此前100行的跟蹤方式相同。但是接下來的一百行只是有偏移量，而地標具有從第100行文件開始處的絕對偏移量。

所以當你改變一條線的長度時，你只需要更新其餘的偏移量該地標中的線條加上其餘地標的偏移量。這仍然是O（n），但有一個相當大的除數，它會使它更快。

但是我們可以做得更好。假設我們把它們放在樹中，樹的葉子是你的線，而根代表整個文件，而不是僅僅維護一個地標列表。要查找給定線的偏移量，請將所有祖先的偏移量加在一起。如果一條線改變了，你只需更新一個節點及其祖先。這給了O（log n），代價是一些簿記。空間開銷並不比你已經使用的雙向鏈表更差。