2 个版本
使用旧的 Rust 2015
| 0.1.1 | 2017 年 4 月 14 日 |
|---|---|
| 0.1.0 | 2017 年 4 月 14 日 |
#1923 在 数据结构
105KB
3K SLoC
集合
0.1 Rube Goldberg 发布
此库为 Rust 实现持久化数据结构，具有高效的，联合操作的复杂性在实际情况中可以小于线性。
确定性平衡搜索树
这是通过使用确定性平衡树实现的，其中树的分裂点由集合中元素的 Weight 决定。
如果 T 实现 Weight，则意味着 T 或 T 的部分可以被 Hashed，然后使用该哈希值来确定权重，本质上是通过计算哈希中的前导零的数量来实现的。权重决定了要分割的层数。
写时复制，以及结构共享
克隆集合是一个常量时间操作。这是通过 Stash 抽象实现的，它通过一个 Location 间接引用来维护一个节点集合。
可插拔元数据
每个集合都可以携带不同类型的元数据，元数据定义为操作 &T -> Meta<T>，以及结合两个 Meta<T> 的二进制操作。因此，要实现一个集合，你会使用 Max<T>，如果你还想要常量时间的等价性检查，你会添加 CheckSum<T>
集合类型
集合包含 3 个预定义的操作集，组成一个集合、一个向量和一个映射。
要定义一个集合，你使用 collection! 宏
collection!(Set<T> {
max: Max<T>,
checksum: CheckSum<u64>,
} where T: Ord + Hash);
collection!(Vector<T> {
cardinality: Cardinality<usize>,
checksum: CheckSum<u64>,
} where T: Hash);
collection!(Map<T> {
key: Key<T::Key>,
keysum: KeySum<u64>,
valsum: ValSum<u64>,
} where T: Keyed,
T::Key: Hash,
T::Value: Hash);
许可证
GPLv3
依赖项
~365–590KB