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 或 https://open-source.org.cn/licenses/MIT)

任选其一。

贡献

除非您明确声明，否则根据 Apache-2.0 许可证定义，您有意提交的任何贡献，均将按上述方式双许可，不附加任何额外条款或条件。