nested_intervals

此包处理可能重叠和嵌套的区间集合，即范围列表。

实现基于 Alekseyenko 等人 2007 年提出的嵌套包含列表，该实现提供与区间树相同的大 O 复杂度（O(n * log(n)) 构建，O(n + m) 查询）。查询数据结构的构建是懒加载的，并且只在依赖它的方法第一次被调用时发生。

每个区间都有一个附加的 u32 ids 向量，这使得可以将结果链接回其他数据结构。

完整的文档在 docs.rs。源代码在 GitHub

示例

代码示例

  fn test_example() {
        let intervals = vec![0..20, 15..30, 50..100];
        let mut interval_set = IntervalSet::new(&intervals);
        assert_eq!(interval_set.ids, vec![vec![0], vec![1], vec![2]]); // automatic ids, use new_with_ids otherwise
        let hits = interval_set.query_overlapping(10..16);
        assert_eq!(hits.intervals, [0..20, 15..30]);
        let merged = hits.merge_hull();
        assert_eq!(merged.intervals, [0..30]);
        assert_eq!(merged.ids, vec![vec![0,1]]);
    }

功能

• 检查与查询范围的重叠 -> has_overlap

• 查询与查询范围的重叠 -> query_overlapping

• 查询与查询集合的重叠 -> filter_to_overlapping_multiple

• 查询与查询集合的非重叠 -> filter_to_non_overlapping

• 检查内部重叠 -> any_overlapping

• 检查内部嵌套 -> any_nested

• 删除重复的区间（起始和结束！）-> remove_duplicates

• 删除重复的区间并抱怨非重复的重叠 -> [remove_duplictes ](https://docs.rs/nested_intervals/struct.IntervalSet.html#method.remove_duplictes & any_overlapping)

• 移除空区间 -> remove_empty

• 通过连接它们来合并内部重叠 -> merge_hull

• 通过删除它们来合并内部重叠 -> merge_drop

• 将内部重叠分割成非重叠的子集（例如，[10..100, 20..30] 变成 [10..20, 20..30, 30..100]）-> merge_split

• 反转一个区间集（给定外部边界）-> invert

• 找到最接近起始点的区间 -> find_closest_start

• 找到左侧最接近点的区间 -> find_closest_start_left

• 找到右侧最接近点的区间 -> find_closest_start_right

• 计算区间覆盖的单位 -> covered_units

• 找到区间的平均大小 -> mean_interval_size

• 构建 n 个区间集的并集 -> union

• 减去两个区间集 -> filter_to_non_overlapping

• 仅保留与 n 个其他集重叠的集 -> filter_to_overlapping_k_others

• 移除与超过 n 个其他集重叠的集 -> filter_to_non_overlapping_k_others

尚不支持

我们目前不能

• 找到最接近终点的区间

• 找到左侧最接近点的区间 // 将会非常昂贵 O(n/2)

• 找到右侧最接近点的区间 // 将会非常昂贵 O(n/2)

• 交集两个区间集（即两个集合中的覆盖单位）

• 交集多个区间集（即多个集合中的覆盖单位，可能应用 'k' 阈值）

• 通过交集来合并内部重叠？这对于嵌套集来说是什么意思？

更新日志

• 0.6.0 - 修复了 has_overlap 的一个错误，当数据集中有起始点相同的区间时，会产生假阴性。