ScAIList

这是按照此处描述的AIList算法的Rust实现。最大的不同之处在于，这个实现动态地确定组件的最大数量，而不是限制在10个。人们可以称之为缩放增强区间列表。它将输入元素长度的log2作为组件的最大数量，并将其分解成该数量。

这似乎非常快。在所有简单情况下，与rust-lapper一样快，当事情变得复杂时，速度更快。随着interval_bakeoff项目的进展，将添加基准测试。

文档

Crates.io

lib.rs:

本模块提供了一个AIList的实现，但对于子列表的数量具有动态缩放。

功能

• 始终快速。输入区间的分解方式降低了超级包含的影响。
• 并行友好。查询在一个不可变结构上进行，即使是对于查找
• 消费者/适配器范式，返回一个迭代器。

细节

请参阅论文。

大多数与此crate的交互将通过ScAIList struct The main methods is [find。

此重叠函数假设了一个基于0的基因组坐标系统。因此，对于查询和区间，[start, stop)不包括停止位置。

ScAIList由四个主要部分组成。一个主要区间列表，它保存所有分解后的区间。一个组件索引列表，它保存每个子列表分解后的起始索引。一个组件长度列表，它保存每个组件的长度，最后是一个max_ends列表，它保存每个区间相对于子列表的相对最大结束位置。

分解步骤是通过遍历区间列表并递归（带有限制）提取与它重叠的特定距离内的给定数量其他区间的区间来实现的。在此实现中的独特发展是使限制动态化。

示例

   use scailist::{Interval, ScAIList};
   use std::cmp;
   type Iv = Interval<u32>;

   // create some fake data
   let data: Vec<Iv> = (0..20).step_by(5).map(|x| Iv{start: x, end: x + 2, val: 0}).collect();
   println!("{:#?}", data);

   // make lapper structure
   let laps = ScAIList::new(data, None);
   assert_eq!(laps.find(6, 11).next(), Some(&Iv{start: 5, end: 7, val: 0}));
   
   let mut sim: u32= 0;
   // Calculate the overlap between the query and the found intervals, sum total overlap
   for i in (0..10).step_by(3) {
       sim += laps
           .find(i, i + 2)
           .map(|iv| cmp::min(i + 2, iv.end) - cmp::max(i, iv.start))
           .sum::<u32>();
   }
   assert_eq!(sim, 4);