Moon Collections

面向 MoonBit 生态的高性能扩展数据结构与算法库，提供有序映射、有序集合、位图、缓存、堆、图算法、并查集和 AVL 有序容器。项目使用纯 MoonBit 实现，不依赖 C/Wasm 外部绑定。

项目状态

• 当前模块版本：0.4.0
• 验证工具链：MoonBit 0.10.7+bc794d341（CI 与本地统一）
• CI 验证后端：wasm、wasm-gc、js、native；LLVM 是实验性后端，不包含在 --target all 中
• 当前测试规模：105 个测试用例，覆盖集合、图遍历、连通性、空集合、重复插入、边界索引、淘汰顺序、堆耗尽、AVL 删除和双端队列扩容等场景
• 开源协议：Apache-2.0

包含模块

包	作用	典型复杂度
src/indexmap	保持插入顺序的哈希映射	查询/更新平均 O(1)；shift_remove 为 O(n)；swap_remove 平均 O(1)
src/indexset	保持插入顺序的集合	插入/查询平均 O(1)
src/bitset	基于 Array[Int] 的动态位图	单点操作 O(1)；集合运算按机器字长度批量处理
src/lru_cache	双向链表 + 哈希表的 LRU 缓存	get/set/remove 平均 O(1)
src/priority_queue	支持自定义比较器的二叉堆	peek 为 O(1)；push/pop 为 O(log n)
src/sorted_map	AVL 树有序映射	查询/插入/删除为 O(log n)
src/sorted_set	基于 SortedMap[T, Unit] 的 AVL 有序集合	查询/插入/删除为 O(log n)
src/deque	基于循环缓冲区的双端队列	两端插入/删除均摊 O(1)
src/graph	确定性邻接表图与图算法	遍历 O(V+E)；拓扑排序 O(V+E)
src/disjoint_set	路径压缩并查集	合并/查询近似 O(α(n))

安装与使用

发布到 Mooncakes 后，在你的 MoonBit 模块中执行：

moon add Hhsqoo/moon-collections

在目标包的 moon.pkg 中导入需要的包：

import {
  "Hhsqoo/moon-collections/src/indexmap" @indexmap,
  "Hhsqoo/moon-collections/src/bitset" @bitset,
  "Hhsqoo/moon-collections/src/graph" @graph,
  "Hhsqoo/moon-collections/src/disjoint_set" @disjoint_set,
}

示例：

let map : @indexmap.IndexMap[String, Int] = @indexmap.IndexMap::new()
let _ = map.set("moon", 1)
let _ = map.set("bit", 2)
println("keys: \{map.keys().to_array()}")

let bits = @bitset.BitSet::new()
bits.set(31)
bits.set(32)
println("set bits: \{bits.iter().to_array()}")

let dependencies : @graph.Graph[String] = @graph.Graph::new(true)
let _ = dependencies.add_edge("parse", "typecheck")
let _ = dependencies.add_edge("typecheck", "codegen")
println("build order: \{dependencies.topological_sort()}")

let connectivity = @disjoint_set.DisjointSet::new(4)
let _ = connectivity.union(0, 1)
println("connected: \{connectivity.connected(0, 1)}")

完整可运行示例位于 src/examples：

moon run src/examples

图算法和并查集的 API、复杂度与应用场景见 docs/graph-and-connectivity.md。

开发与验证

moon update
moon fmt
moon check --fmt --deny-warn
moon check --target all --deny-warn
moon build --target all
moon test --target all --deny-warn
moon info
git diff --exit-code

moon fmt --deny-warn 和 moon info --deny-warn 不是当前 CLI 的有效参数：格式检查使用 moon fmt --check 或 moon check --fmt --deny-warn；接口检查使用 moon info 后检查生成的 pkg.generated.mbti 是否产生 diff。项目使用 0.10.7 的 pkgtype(kind: "executable") 清单语法和 Default::default() API；CI 与本地执行同一版本验证。

Windows 原生目标需要 C 编译器。CI 使用 MSYS2 UCRT64 + MinGW GCC；本地可以将 C:\msys64\ucrt64\bin 加入 PATH 后执行 --target native 或 --target all。

可复现基准

基准入口是 src/benchmarks，固定执行 100,000 次映射写入/查询，以及每 3 个位置设置一次位图再遍历：

moon run src/benchmarks --target native

在 Windows 11、MSYS2 UCRT64、MoonBit 0.10.4 本地运行 5 次的中位数如下。该数据用于复现实验方法，不是跨机器性能承诺：

工作负载	中位耗时	校验和
IndexMap 100,000 次写入 + 查询	28 ms	1409965408
BitSet 100,000 次设置 + 遍历	28 ms	1666683333

如需比较不同机器或后端，请保留工具链版本、目标后端和工作负载，并重复运行至少 5 次。

项目结构

moon.mod                 # 模块元数据和版本
src/indexmap             # 有序哈希映射
src/indexset             # 有序集合
src/bitset               # 动态位图
src/lru_cache            # LRU 缓存
src/priority_queue       # 二叉堆优先队列
src/sorted_map            # AVL 有序映射
src/sorted_set            # AVL 有序集合
src/deque                 # 循环缓冲双端队列
src/examples              # 可直接运行的示例
src/benchmarks            # 可复现 native 基准入口
docs/graph-and-connectivity.md # 图算法与并查集使用说明
docs/architecture.md     # 数据结构和不变量
docs/performance.md      # 基准方法与数据
pkg.generated.mbti        # moon info 生成的公共接口摘要

公共接口文件由 moon info 生成并纳入版本控制，修改公共 API 时请同时检查接口 diff。测试文件采用 *_test.mbt，文档中的代码示例应保持可复制运行。

贡献

请先阅读 CONTRIBUTING.md。新功能应同时提供边界测试、README/API 示例和必要的复杂度说明；提交前至少运行格式、全目标检查、测试和接口漂移检查。

许可证与镜像

本项目采用 Apache License 2.0。默认开发分支为 main；master 仅为历史镜像分支。

• GitHub：https://github.com/Hhsqoo/moon-collections
• Gitlink：https://gitlink.org.cn/Hsoop/moon-collections