1. 首頁
  2. 問答
  3. 文本編輯器的純功能數據結構

文本編輯器的純功能數據結構

2012-09-10 34 views
38

什麼是文本編輯器的純功能數據結構？我希望能夠將單個字符插入到文本中，並以可接受的效率從文本中刪除單個字符，並且希望能夠保留舊版本，以便輕鬆地撤消更改。文本編輯器的純功能數據結構

我應該只使用一個字符串列表並重用不會從版本更改爲版本的行嗎？

來源

2012-09-10 fredoverflow

+14

你可以看看拉鍊.. – Satvik

+3

你可以通過你使用（除非你在一個控制檯應用程序基於規劃），這可能會處理GUI框架的約束所有的文本編輯直接從你的錫。 – AndrewC

+1

查找列表拉鍊。 –

回答

10

A Vector[Vector[Char]]可能是一個很好的選擇。這是一個IndexedSeq所以有不俗的更新/預付/更新性能，不像你提到的List。如果你看看Performance Characteristics，這是唯一不變的集合，它提供了有效的恆定時間更新。

來源

2012-09-10 19:34:54

+2

我試過了，它效果很棒！ – fredoverflow

1

涌現在頭腦的可能性是：

  1. 「文本」類型的數值索引。它將文本保存在一個鏈接的緩衝區列表中（內部表示爲UTF16），因此理論上它的計算複雜度通常是鏈表（例如索引爲O（n）），實際上它比傳統鏈接快得多列出你可能會忘記n的影響，除非你將整個維基百科存儲在緩衝區中。嘗試對一百萬個字符文本進行一些實驗，看看我是否正確（我沒有實際完成的事情，順便說一句）。

  2. 文本拉鍊：將光標後面的文本存儲在一個文本元素中，並且將文本之前的光標放在另一個文本中。將光標傳輸文本從一側移動到另一側。

來源

2012-09-10 22:22:27

53

我不知道這個建議對於「好」的複雜定義是否「好」，但它很容易和有趣。我經常設置一個練習來編寫Haskell中的文本編輯器的核心，並鏈接到我提供的渲染代碼。數據模型如下。

首先，我定義一個光標在x -elements列表中，光標處可用的信息有一些類型m。 （該x會變成是Char或String）

type Cursor x m = (Bwd x, m, [x])

這Bwd的事情僅僅是落後的 「snoc-名單」。我想保持強大的空間直覺，所以我在我的代碼中轉而解決問題，而不是在我的腦海中。這個想法是，最接近光標的東西是最容易訪問的。這就是拉鍊的精神。

data Bwd x = B0 | Bwd x :< x deriving (Show, Eq)

我提供了一個免費的單式充當光標可讀標誌...

data Here = Here deriving Show

...，因此我可以說，它是什麼，是在一個String

某處 
type StringCursor = Cursor Char Here

現在，來表示多行的緩衝，我們需要String S上方並與光標線的下方，並且在中間StringCursor，對於線我們」目前正在編輯。

type TextCursor = Cursor String StringCursor

這TextCursor類型是我用來表示編輯緩衝區的狀態。這是一個雙層拉鍊。我向學生提供代碼，以在啓用ANSI-escape的shell窗口中的文本上渲染視口，確保視口包含光標。他們所要做的就是實現更新TextCursor以響應擊鍵的代碼。

handleKey :: Key -> TextCursor -> Maybe (Damage, TextCursor)

其中handleKey應該返回Nothing如果按鍵是沒有意義的，但在其他方面提供Just更新TextCursor和「損壞報告」的

data Damage 
    = NoChange  -- use this if nothing at all happened 
    | PointChanged -- use this if you moved the cursor but kept the text 
    | LineChanged -- use this if you changed text only on the current line 
    | LotsChanged -- use this if you changed text off the current line 
    deriving (Show, Eq, Ord)

後者是一個（如果你想知道請返回Nothing和返回Just (NoChange, ...)之間的區別是什麼，請考慮是否還希望編輯器發出嘟嘟聲。）損壞報告告訴渲染器需要做多少工作才能使顯示的圖像保持最新狀態。

Key類型只是給可能的擊鍵提供可讀的數據表示，從原始ANSI轉義序列中抽象出來。這並不顯眼。

我通過提供這些作品套件的學生提供大約走了一大線索，來與這個數據模型：

deactivate :: Cursor x Here -> (Int, [x]) 
deactivate c = outward 0 c where 
    outward i (B0, Here, xs)  = (i, xs) 
    outward i (xz :< x, Here, xs) = outward (i + 1) (xz, Here, x : xs)

的deactivate功能是用來轉移焦點了Cursor，給你是一個普通的列表，但是告訴你在哪裏光標是。相應activate函數試圖將光標在給定位置的列表：

activate :: (Int, [x]) -> Cursor x Here 
activate (i, xs) = inward i (B0, Here, xs) where 
    inward _ [email protected](_, Here, [])  = c -- we can go no further 
    inward 0 c     = c -- we should go no further 
    inward i (xz, Here, x : xs) = inward (i - 1) (xz :< x, Here, xs) -- and on!

我提供的學生handleKey

handleKey :: Key -> TextCursor -> Maybe (Damage, TextCursor) 
handleKey (CharKey c) (sz, 
         (cz, Here, cs), 
         ss) 
    = Just (LineChanged, (sz, 
         (cz, Here, c : cs), 
         ss)) 
handleKey _ _ = Nothing

故意不正確和不完整的定義，只是處理普通字符的按鍵，但使文字向後退出。很容易看到字符c出現對的Here。我邀請他們修復bug併爲箭頭鍵，退格鍵，刪除，返回等添加功能。

它可能不是最有效的表示，但它是純粹的功能，並使代碼具體地符合我們對正在編輯的文本的空間直覺。

來源

2012-09-11 00:27:49 pigworker

+0

根據http://www.reddit.com/r/haskell/comments/11pwh6，代碼目前可以通過'darcs克隆http：// personal.cis.strath.ac.uk/conor.mcbride/CS410'獲取。 /。 – nobody

2

Clojure的社區作爲插入數據的矢量的持久性數據晶格結構，可以有效地級聯/切片/等看RRB Trees（寬鬆基數平衡）

它允許級聯，插入-AT-索引和在O（log N）時間拆分操作。

我想象一個專門用於角色數據的RRB樹將非常適合於大型「可編輯」文本數據結構。

來源

2012-09-12 02:54:48 mikera

4

我建議使用zippers結合Data.Sequence.Seq這是基於finger trees。所以，你可以代表當前狀態 

data Cursor = Cursor { upLines :: Seq Line 
        , curLine :: CurLine 
        , downLines :: Seq Line }

這給你O（1）複雜移動光標向上/向下一行，並自splitAt和(><)（工會）有兩個O（日誌（min（n1，n2）））複雜性，您將獲得O（log（L））複雜度用於跳過L行向上/向下。

對於CurLine，您可以使用類似的拉鍊結構在遊標之前，之前和之後保留一個字符序列。

Line可能是一些節省空間的東西，如ByteString。

來源

2012-09-13 09:55:55

相關問題

 相關問題