#nested #list #overlapping #interval #containment

无std nested_containment_list

一种用于高效存储和查询嵌套区间的数据结构

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

Download history 49/week @ 2024-04-20 17/week @ 2024-04-27 56/week @ 2024-05-04 28/week @ 2024-05-11 76/week @ 2024-05-18 67/week @ 2024-05-25 67/week @ 2024-06-01 67/week @ 2024-06-08 55/week @ 2024-06-15 120/week @ 2024-06-22 59/week @ 2024-06-29 56/week @ 2024-07-06 87/week @ 2024-07-13 79/week @ 2024-07-20 116/week @ 2024-07-27 56/week @ 2024-08-03

每月下载348
2个crate中使用(通过word_filter

MIT/Apache

165KB
3K SLoC

nested_containment_list

GitHub Workflow Status codecov.io crates.io docs.rs MSRV License

嵌套包含列表的实现。

嵌套包含列表是一种用于高效存储和查询区间的数据结构。它基于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-2.0 许可证定义,您有意提交的任何贡献,均将按上述方式双许可,不附加任何额外条款或条件。

依赖

~0–270KB