duangsuse::Echo

写的太多不知从何说起... 时间还是不够啊我不是把时间给虵(shé 🐸)了... QAQ 就先说绝句、二进制和字符流 Parser 框架这些最令人 excited 的玩意 Parser 框架我还打算自己手写这些算法： TrieTree （只需要 Trie，因为只是字符流嘛，Radix 树还不如自己手动 maybe 匹配解析... 虽然那样好像没有优化了） RangeMap （到学校里想了会，发现还真不是那么简单的，滚动歌词什么的还真是可以简单点，但是 RangeMap 可以启用二分查找技术和区间碰撞检测，进而可以实现…

RangeMap 其实是相当有用的数据结构，前几天我亲自算过的，二分查找算法优化可以实现！

所谓一个 RangeMap，有插入、删除、查询三个基本操作，就是给你一对 Comparable（Range）、以及他们的映射 Value，进行插入后，查询 i1 <= x < i2，或者说 x in range 就能获得之前的 Value

比如：

val offsetLineMap = RangeMap()

val str = "abc\n123\n!@#"

var startLine = 0
for ((i, c) in str.withIndex) when (c) {
  '\n' -> { offsetLineMap[startLine..i] = str[startLine..i]; startLine = i+1; }
  else -> {}
}

然后我们就可以利用 RangeMap，在 O(log2 n) 的时间复杂度（而不是 O(n) 辣鸡线性复杂度下）完成 offset -> line 的索引

offsetLineMap[0] -> "abc"
offsetLineMap[1] -> "abc"
offsetLineMap[2] -> "abc"
offsetLineMap[3] -> "123"
offsetLineMap[5] -> "123"
offsetLineMap[6] -> "!@#"
offsetLineMap[9] -> IndexOutOfBounds

当我们有了 NestRangeMap 这种逆天的数据结构（和普通 BsearchRangeMap 比更类似 HashMap 和 MultiMap 比）后，还能快速实现类似 IDEA 的辅助功能，给可能有嵌套结构的 AST（抽象语法树，JB 也有一个类似的 PSI，程序结构接口）加上索引

这样，只要我们能拿到 TextField 的光标 offset，就能做类似
+ 拿到光标下的语法嵌套结构，能够知道语法路径在哪

这样的事情 🤪

这种功能很重要吗？的确很重要啊，如果你用线性查找这种省事但不讨好的算法，或者不考虑 Range 的碰撞，是绝对没有这种福利的

然而 NestedRangeMap 就可以实现这种操作，让人为之一振

val documentOffsetNesting = NestedRangeMap()

val document = KommonMarks.parseString
("""
# H1
_a_ __b__ *c*
## H2
[name](url:)
""".trim())

/* Add pairs to nested range by document marker offsets */
documentOffsetNesting[0] => HeaderNode(children = [TextNode("H1")], n = 1)
documentOffsetNesting[5] => [DocumentSection(name = "H1", n = 1), TextDisplayNode(mode = Italic, text = "a")]
documentOffsetNesting[19] => HeaderNode(children = [TextNode("H2")], n = 2)

看到 documentOffsetNesting[5] 的返回值了吗？它能够提示某个 Markdown 元素的路径，是在哪个标签里

对于 NestedRangeMap 来说，它会自动处理任何的区间碰撞（被分成五个大类型），将碰撞的部分替换成一个列表

val rm = NestedRangeMap()
rm[0...10] = "0 to 10"
rm[2..6] = "2 to 5" // "Full Overwrite" collision from index 2 to 6

rm[0] => "0 to 10"
rm[2] => ["0 to 10", "2 to 5"]

程序员在写 SourceManager 的时候，就只需要把某个语法结构的 startOffset 和 endOffset 记录一下就好了，NestedRangeMap 可以自动完成代码路径索引创建任务

25 viewsduangsuse ¯\_(ツ)_/¯ |学渣 | 我爱学习 | ∈ [E²PROM, 范畴论], edited 01:35