Splay Ropes

wiki

此实现使用函数式伸展树来保持绳索平衡；伸展树的实现部分受到 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，您可以按如下方式实现元组函数

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

它会更慢，并且会使用更多内存，但它是纯 Lua。

绳索库确实变得太大，无法容纳在 Wiki 上，因此我将其放在文件区域，以及一个小的 Knuth Morris Pratt 搜索/替换函数，作为如何使用绳索的示例（尽管在 Lua 中逐字符搜索并不快）。

要加载库，请使用 LTN-11 样式：(local) rope = dofile"rope.lua"()

在此处下载库：Files:wiki_insecure/users/rici/rope.lua 和此处：Files:wiki_insecure/users/rici/ropesearch.lua

绳索特别适用于大型文本字符串，其中在局部点进行随机更改；例如，这将使它们成为实现文本编辑器的理想选择。函数式伸展树还具有一个有趣的特性，即您可以随时保留对绳索的引用，然后稍后“返回”到它；因此，维护撤消历史记录是微不足道的。单个局部更改不太可能创建多个伸展节点。

扩展绳的实现使用区间映射：树中的每个节点包含一个左指针、一个右指针、一个字符串以及字符串末尾的相对位置（这也可以是字符串开头的相对位置或节点及其所有后代的总大小；这三种表述在计算上是等价的）。这意味着一个节点可以存在于多个绳中，甚至在同一个绳中的多个位置——一个极端的例子是 rope.rep 的实现，它使用密集的节点共享来创建比 RAM 大得多的绳：rope.rep("a", 1E40) 耗时几毫秒，占用约 10kb，但它实际上表示一个包含 10^40 个字符的字符串。在我看来，当你拥抱不可变对象和垃圾回收，而不是试图在函数式垃圾回收环境中实现 C 数据类型时，最终会得到这种数据结构。

关于区间映射的另一个有趣的事实是，可以将两个区间映射保持同步索引，而无需共享相同的拓扑结构。例如，假设的文本编辑器可以在另一个区间映射中保存文本样式信息，只需在 stylerun 区间映射上执行相同的 insert、delete 和 replace 操作，即使 stylerun 区间映射正在合并连续的相同样式。

扩展树在这种应用中很有用，因为它们不需要在任意删除或插入操作后重新平衡。另一方面，扩展树是自调整的，这意味着即使在查找后，而不是仅仅在变异后，你也会得到一个新的扩展对象，并且扩展树的性能取决于使用新对象进行后续查找。出于这些原因，扩展树通常被认为不适合函数式程序，特别是那些依赖持久性（或者如果你愿意，时间旅行）的程序；但是，我相信文本编辑器应用程序将证明这实际上并非如此。