6个版本
0.3.1 | 2022年3月26日 |
---|---|
0.3.0 | 2021年3月8日 |
0.2.1 | 2021年2月12日 |
0.1.1 | 2021年1月24日 |
在数据结构中排名第1123
每月下载348次
在2个crate中使用(通过word_filter)
165KB
3K SLoC
nested_containment_list
嵌套包含列表的实现。
嵌套包含列表是一种用于高效存储和查询区间的数据结构。它基于Alexander V. Alekseyenko和Christopher J. Lee在他们的2007年Bioinformatics出版物中提出的一种嵌套包含列表数据结构。此实现允许使用泛型界限存储和查询泛型类型。
用法
嵌套包含列表可以存储实现RangeBounds
特质的类型。例如,以下是一个存储Range
的简单嵌套包含列表的构建方式:
use nested_containment_list::NestedContainmentList;
let nclist = NestedContainmentList::new();
nclist.insert(1..5);
nclist.insert(2..4);
nclist.insert(6..7);
nclist.insert(5..9);
存储在嵌套包含列表中的数据通常通过一个嵌套的Iterator
结构来访问,该结构是通过使用.overlapping()
方法查询获得的。
let query = 3..6;
let mut overlapping = nclist.overlapping(&query);
// 1..5 overlaps with 3..6, so it is the first element.
let first_element = overlapping.next().unwrap();
assert_eq!(first_element.value, &(1..5));
// 2..4 is contained inside 1..5 and overlaps with 3..6, so it is accessed through the first
// element's sublist.
assert_eq!(first_element.sublist().next().unwrap().value, &(2..4));
// 5..9 overlaps with 3..6, so it is the second element.
let second_element = overlapping.next().unwrap();
assert_eq!(second_element.value, &(5..9));
// Even though 6..7 is contained inside 5..9, it does not overlap with 3..6, and therefore is not
// contained in the second element's sublist.
assert!(second_element.sublist().next().is_none())
性能
构建
构建NestedContainmentList
的时间复杂度为O(n log(n))。使用NestedContainmentList::insert()
插入的时间复杂度为O(log n)。同样,使用NestedContainmentList::remove()
删除的时间复杂度也为O(log n)。
查询
使用 NestedContainmentList::overlapping()
查询重叠区间的时间复杂度为 O(n + log(N)),其中 N 是 Nested Containment List 中存储的区间数量,而 n 是与查询重叠的区间数量。
最低支持的 Rust 版本
此 crate 可确保在稳定版 rustc 1.31.0
及以上版本编译。在 no_std
环境中使用需要稳定版 rustc 1.36.0
及以上版本,因为使用了 alloc
。
许可证
本项目可根据您的选择采用以下任一许可证:
- Apache License,版本 2.0 (LICENSE-APACHE 或 https://apache.ac.cn/licenses/LICENSE-2.0)
- MIT 许可证 (LICENSE-MIT 或 http://opensource.org/licenses/MIT)
任选其一。
贡献
除非您明确声明,否则根据 Apache-2.0 许可证定义,您有意提交的任何贡献,均将按上述方式双许可,不附加任何额外条款或条件。
依赖
~0–270KB