Cirru 项目里有个需求, 需要在服务端的整个 Cirru 的语法树比较容易被 Diff, 这个结构最好是 HashMap, 但是, Cirru 的语义又是需要有顺序的, 原来使用 Vector 存储. 所以现在我就需要又是一个 HashMap, 又要有顺序. 于是我想到了用 key 的字符串来表示顺序.
比如 "a"
"b"
两个字符串可以作为 HashMap 的 key, 但是同时两个有序, 如果我要在中间插入新的, 我可以选择 "aa"
满足字典顺序在两者之间. 而且还可以继续插值.
然后我选择了 +-/
0~9
A~Z
a~z
的序列作为我的字典, 从 0
对应到 64
总共 65 个字符, 这样选择一方面方便阅读, 另一方面 (0 + 64) / 2
一直是 2 的次方, 方便取整找到中间位置的字符.
最终得到这样的 API:
(bisection-key.core/bisect "a" "c") ; "b"
(bisection-key.core/bisect "a" "b") ; "aT"
; make sure "a < b"
bisection-key.core/min-id ; "+"
bisection-key.core/mid-id ; "T"
bisection-key.core/max-id ; "z"
这样任意两个合法的不相等的字符串中间都可以生成字典顺序处于两者之间的字符串了.