Moon Collections

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

项目状态

当前模块版本：0.3.0
推荐工具链：MoonBit 0.10.3；本地验证也覆盖了 0.10.4
目标后端：wasm、wasm-gc、js、native、llvm
当前测试规模：95 个测试用例，包含空集合、重复插入、边界索引、淘汰顺序、堆耗尽、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)`

安装与使用

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

moon add Hhsqoo/moon-collections

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

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

示例：

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()}")

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

moon run src/examples

开发与验证

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。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/architecture.md     # 数据结构和不变量
docs/performance.md      # 基准方法与数据
pkg.generated.mbti        # moon info 生成的公共接口摘要

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

贡献

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

许可证与镜像

本项目采用 Apache License 2.0。

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