Splay Ropes

wiki

此實作使用函式式 splay 樹，以維持 ropes 的平衡；splay 樹的實作部分靈感來自 Chris Okasaki 優秀的純函式式資料類型書籍。

節點在此實作中使用元組，搭配 Lua 基礎函式庫的一點點補充實作

static int l_tuple(lua_State *L) {
   lua_pushcclosure(L, lua_pushupvalues, lua_gettop(L));
   return 1;
}

/* also add {"tuple", l_tuple} to luaL_reg base_funcs[] */

如果你不想重新編譯 Lua，你可以實作 tuple 函式，如下所示

local tuplemeta = {__call = table.unpack}
function tuple(...) return setmetatable(arg, tuplemeta) end

它會比較慢且使用更多記憶體，但這是純 Lua。

rope 函式庫實際上已經太大，無法放入 Wiki，因此我將其置於檔案區域，並搭配一個用來搜尋/取代的 Knuth Morris Pratt 函式，做為如何使用 ropes 的範例（儘管在 Lua 中逐字搜尋並不快。）

要載入函式庫，請使用 LTN-11 樣式：(local) rope = dofile"rope.lua"()

在此下載函式庫：檔案：wiki_insecure/users/rici/rope.lua 和在此：檔案：wiki_insecure/users/rici/ropesearch.lua

Ropes 特別適合於大型文字字串，其中會在局部點進行隨機變更；例如，這會使其理想地實作文字編輯器。函式式 splay 樹也有有趣的特性，就是你可以隨時維持對 rope 的參考，並在之後「返回」到該參考；因此，維持取消記錄變得非常簡單。單一局部變更不太可能建立超過幾個 splay 節點。

splay ropes 使用間隔映射實作：樹中的每個節點都包含左右指標、字串和字串結尾的相對位置（這可能是字串開頭的相對位置或節點加上所有後代的總大小；這三個公式在計算上是相等的。）這表示節點可以在多於一個 rope 中，甚至在同一個 rope 中多於一個位置——一個極端的範例由 rope.rep 的實作顯示，它使用密集節點共用，讓它可以建立大小遠大於 RAM 的 ropes：rope.rep("a", 1E40) 花費幾毫秒並使用約 10 kb，但它實際上是擁有 10^40 個字元的字串表示。在我看來，當你採用不可變物件和垃圾回收，而非嘗試在函式式垃圾回收環境中實作 C 資料類型時，你就是得到了這種類型的資料結構。

關於間隔映射的另一個有趣事實是，可以讓兩個映射保持同步索引，而不共用相同的拓樸。舉例來說，假設的文字編輯器可以在另一個間隔映射中保留文字樣式資訊，方法僅是在樣式執行間隔映射上執行相同的 insert、delete 和 replace 操作，即使樣式執行間隔映射正在整合連續的相同樣式。

Splay 樹會在這種應用程式中有用，原因在於它們不需要在任意刪除或插入作業之後重新平衡。另一方面，splay 樹會自動調整，這表示您可以在查詢後取得新的 splay 物件，而並非僅在變異之後取得，而 splay 樹的效能取決於您是否針對後續查詢使用新物件。基於這樣的理由，splay 樹通常被認為不適合用於函式式程式，尤其是依賴於持久性（或時間旅行，如果您偏好此說法）的程式。不過，我相信文字編輯器應用程式會證明這其實並非事實。