use std::cmp::Ordering;
use std::collections::{VecDeque};
#[derive(Eq, Debug, Clone)]
pub struct Interval<T: Eq + Clone> {
pub start: usize,
pub stop: usize,
pub val: T,
}
#[derive(Debug)]
pub struct Lapper<T: Eq + Clone> {
pub intervals: Vec<Interval<T>>,
max_len: usize,
cursor: usize,
cov: Option<usize>,
pub overlaps_merged: bool,
}
impl<T: Eq + Clone> Interval<T> {
#[inline]
pub fn intersect(&self, other: &Interval<T>) -> usize {
std::cmp::min(self.stop, other.stop).checked_sub(std::cmp::max(self.start, other.start)).unwrap_or(0)
}
#[inline]
pub fn overlap(&self, start: usize, stop: usize) -> bool {
self.start < stop && self.stop > start
}
}
impl<T: Eq + Clone> Ord for Interval<T> {
#[inline]
fn cmp(&self, other: &Interval<T>) -> Ordering {
if self.start < other.start {
Ordering::Less
} else if other.start < self.start {
Ordering::Greater
} else {
self.stop.cmp(&other.stop)
}
}
}
impl<T: Eq + Clone> PartialOrd for Interval<T> {
#[inline]
fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
Some(self.cmp(&other))
}
}
impl<T: Eq + Clone> PartialEq for Interval<T> {
#[inline]
fn eq(&self, other: &Interval<T>) -> bool {
self.start == other.start && self.stop == other.stop
}
}
impl<T: Eq + Clone> Lapper<T> {
pub fn new(mut intervals: Vec<Interval<T>>) -> Self {
intervals.sort();
let mut max_len = 0;
for interval in intervals.iter() {
let i_len = interval.stop.checked_sub(interval.start).unwrap_or(0);
if i_len > max_len {
max_len = i_len;
}
}
Lapper {
intervals,
max_len,
cursor: 0,
cov: None,
overlaps_merged: false,
}
}
#[inline]
pub fn len(&self) -> usize {
self.intervals.len()
}
#[inline]
pub fn is_empty(&self) -> bool {
self.intervals.is_empty()
}
#[inline]
pub fn cov(&self) -> usize {
match self.cov {
None => self.calculate_coverage(),
Some(cov) => cov
}
}
pub fn set_cov(&mut self) -> usize {
let cov = self.calculate_coverage();
self.cov = Some(cov);
cov
}
fn calculate_coverage(&self) -> usize {
let mut moving_interval = Interval{start: 0, stop: 0, val: 0};
let mut cov = 0;
for interval in self.intervals.iter() {
if moving_interval.overlap(interval.start, interval.stop) {
moving_interval.start = std::cmp::min(moving_interval.start, interval.start);
moving_interval.stop = std::cmp::max(moving_interval.stop, interval.stop);
} else {
cov += moving_interval.stop - moving_interval.start;
moving_interval.start = interval.start;
moving_interval.stop = interval.stop;
}
}
cov += moving_interval.stop - moving_interval.start;
cov
}
#[inline]
pub fn iter(&self) -> IterLapper<T> {
IterLapper {
inner: self,
pos: 0,
}
}
pub fn merge_overlaps(&mut self) {
let mut stack: VecDeque<&mut Interval<T>> = VecDeque::new();
let mut ivs = self.intervals.iter_mut();
if let Some(first) = ivs.next() {
stack.push_back(first);
for interval in ivs {
let mut top = stack.pop_back().unwrap();
if top.stop < interval.start {
stack.push_back(top);
stack.push_back(interval);
} else if top.stop < interval.stop {
top.stop = interval.stop;
stack.push_back(top);
} else {
stack.push_back(top);
}
}
self.overlaps_merged = true;
self.intervals = stack.into_iter().map(|x| Interval{start: x.start, stop: x.stop, val: x.val.clone()}).collect();
}
}
#[inline]
fn lower_bound(&self, start: usize) -> usize {
let mut result = 0;
let mut count = self.intervals.len();
let mut step: usize;
let mut pos: usize;
while count != 0 {
step = count / 2;
pos = result + step;
if self.intervals[pos].start < start {
result = pos + 1;
count -= step + 1;
} else {
count = step;
}
}
result
}
#[inline]
fn lower_bound_offset(&self, start: usize, intervals: &[Interval<T>]) -> usize {
let mut result = 0;
let mut count = intervals.len();
let mut step: usize;
let mut pos: usize;
while count != 0 {
step = count / 2;
pos = result + step;
if intervals[pos].start < start {
result = pos + 1;
count -= step + 1;
} else {
count = step;
}
}
result
}
#[inline]
pub fn union_and_intersect(&self, other: &Self) -> (usize, usize) {
let mut cursor: usize = 0;
if !self.overlaps_merged || !other.overlaps_merged {
let mut intersections: Vec<Interval<bool>> = vec![];
for self_iv in self.iter() {
for other_iv in other.seek(self_iv.start, self_iv.stop, &mut cursor) {
let start = std::cmp::max(self_iv.start, other_iv.start);
let stop = std::cmp::min(self_iv.stop, other_iv.stop);
intersections.push(Interval{start, stop, val: true});
}
}
let mut temp_lapper = Lapper::new(intersections);
temp_lapper.merge_overlaps();
temp_lapper.set_cov();
let union = self.cov() + other.cov() - temp_lapper.cov();
(union, temp_lapper.cov())
} else {
let mut intersect = 0;
for c1_iv in self.iter() {
for c2_iv in other.seek(c1_iv.start, c1_iv.stop, &mut cursor) {
let local_intersect = c1_iv.intersect(c2_iv);
intersect += local_intersect;
}
}
let union = self.cov() + other.cov() - intersect;
(union, intersect)
}
}
#[inline]
pub fn intersect(&self, other: &Self) -> usize {
self.union_and_intersect(other).1
}
#[inline]
pub fn union(&self, other: &Self) -> usize {
self.union_and_intersect(other).0
}
#[inline]
pub fn find(&self, start: usize, stop: usize) -> IterFind<T> {
IterFind {
inner: self,
off: self.lower_bound(start.checked_sub(self.max_len).unwrap_or(0)),
end: self.intervals.len(),
start,
stop,
}
}
#[inline]
pub fn seek<'a>(&'a self, start: usize, stop: usize, cursor: &mut usize) -> IterFind<'a, T> {
if *cursor == 0 || (*cursor < self.intervals.len() && self.intervals[*cursor].start > start)
{
*cursor = self.lower_bound(start.checked_sub(self.max_len).unwrap_or(0));
}
while *cursor + 1 < self.intervals.len()
&& self.intervals[*cursor + 1].start < start.checked_sub(self.max_len).unwrap_or(0)
{
*cursor += 1;
}
IterFind {
inner: self,
off: *cursor,
end: self.intervals.len(),
start,
stop,
}
}
}
pub struct IterFind<'a, T>
where
T: Eq + Clone + 'a,
{
inner: &'a Lapper<T>,
off: usize,
end: usize,
start: usize,
stop: usize,
}
impl<'a, T: Eq + Clone> Iterator for IterFind<'a, T> {
type Item = &'a Interval<T>;
#[inline]
fn next(&mut self) -> Option<Self::Item> {
while self.off < self.end {
let interval = &self.inner.intervals[self.off];
self.off += 1;
if interval.overlap(self.start, self.stop) {
return Some(interval);
} else if interval.start >= self.stop {
break;
}
}
None
}
}
pub struct IterLapper<'a, T>
where
T: Eq + Clone + 'a,
{
inner: &'a Lapper<T>,
pos: usize,
}
impl<'a, T: Eq + Clone> Iterator for IterLapper<'a, T> {
type Item = &'a Interval<T>;
fn next(&mut self) -> Option<Self::Item> {
if self.pos >= self.inner.intervals.len() {
None
} else {
self.pos += 1;
self.inner.intervals.get(self.pos - 1)
}
}
}
impl<T: Eq + Clone> IntoIterator for Lapper<T> {
type Item = Interval<T>;
type IntoIter = ::std::vec::IntoIter<Self::Item>;
fn into_iter(self) -> Self::IntoIter {
self.intervals.into_iter()
}
}
impl<'a, T: Eq + Clone> IntoIterator for &'a Lapper<T> {
type Item = &'a Interval<T>;
type IntoIter = std::slice::Iter<'a, Interval<T>>;
fn into_iter(self) -> std::slice::Iter<'a, Interval<T>> {
self.intervals.iter()
}
}
impl<'a, T: Eq + Clone> IntoIterator for &'a mut Lapper<T> {
type Item = &'a mut Interval<T>;
type IntoIter = std::slice::IterMut<'a, Interval<T>>;
fn into_iter(self) -> std::slice::IterMut<'a, Interval<T>> {
self.intervals.iter_mut()
}
}
#[cfg(test)]
mod tests {
use super::*;
type Iv = Interval<u32>;
fn setup_nonoverlapping() -> Lapper<u32> {
let data: Vec<Iv> = (0..100)
.step_by(20)
.map(|x| Iv {
start: x,
stop: x + 10,
val: 0,
})
.collect();
let lapper = Lapper::new(data);
lapper
}
fn setup_overlapping() -> Lapper<u32> {
let data: Vec<Iv> = (0..100)
.step_by(10)
.map(|x| Iv {
start: x,
stop: x + 15,
val: 0,
})
.collect();
let lapper = Lapper::new(data);
lapper
}
fn setup_badlapper() -> Lapper<u32> {
let data: Vec<Iv> = vec![
Iv{start: 70, stop: 120, val: 0},
Iv{start: 10, stop: 15, val: 0},
Iv{start: 10, stop: 15, val: 0},
Iv{start: 12, stop: 15, val: 0},
Iv{start: 14, stop: 16, val: 0},
Iv{start: 40, stop: 45, val: 0},
Iv{start: 50, stop: 55, val: 0},
Iv{start: 60, stop: 65, val: 0},
Iv{start: 68, stop: 71, val: 0},
Iv{start: 70, stop: 75, val: 0},
];
let lapper = Lapper::new(data);
lapper
}
fn setup_single() -> Lapper<u32> {
let data: Vec<Iv> = vec![Iv {
start: 10,
stop: 35,
val: 0,
}];
let lapper = Lapper::new(data);
lapper
}
#[test]
fn test_query_stop_interval_start() {
let lapper = setup_nonoverlapping();
let mut cursor = 0;
assert_eq!(None, lapper.find(15, 20).next());
assert_eq!(None, lapper.seek(15, 20, &mut cursor).next())
}
#[test]
fn test_query_start_interval_stop() {
let lapper = setup_nonoverlapping();
let mut cursor = 0;
assert_eq!(None, lapper.find(30, 35).next());
assert_eq!(None, lapper.seek(30, 35, &mut cursor).next())
}
#[test]
fn test_query_overlaps_interval_start() {
let lapper = setup_nonoverlapping();
let mut cursor = 0;
let expected = Iv {
start: 20,
stop: 30,
val: 0,
};
assert_eq!(Some(&expected), lapper.find(15, 25).next());
assert_eq!(Some(&expected), lapper.seek(15, 25, &mut cursor).next())
}
#[test]
fn test_query_overlaps_interval_stop() {
let lapper = setup_nonoverlapping();
let mut cursor = 0;
let expected = Iv {
start: 20,
stop: 30,
val: 0,
};
assert_eq!(Some(&expected), lapper.find(25, 35).next());
assert_eq!(Some(&expected), lapper.seek(25, 35, &mut cursor).next())
}
#[test]
fn test_interval_envelops_query() {
let lapper = setup_nonoverlapping();
let mut cursor = 0;
let expected = Iv {
start: 20,
stop: 30,
val: 0,
};
assert_eq!(Some(&expected), lapper.find(22, 27).next());
assert_eq!(Some(&expected), lapper.seek(22, 27, &mut cursor).next())
}
#[test]
fn test_query_envolops_interval() {
let lapper = setup_nonoverlapping();
let mut cursor = 0;
let expected = Iv {
start: 20,
stop: 30,
val: 0,
};
assert_eq!(Some(&expected), lapper.find(15, 35).next());
assert_eq!(Some(&expected), lapper.seek(15, 35, &mut cursor).next())
}
#[test]
fn test_overlapping_intervals() {
let lapper = setup_overlapping();
let mut cursor = 0;
let e1 = Iv {
start: 0,
stop: 15,
val: 0,
};
let e2 = Iv {
start: 10,
stop: 25,
val: 0,
};
assert_eq!(vec![&e1, &e2], lapper.find(8, 20).collect::<Vec<&Iv>>());
assert_eq!(
vec![&e1, &e2],
lapper.seek(8, 20, &mut cursor).collect::<Vec<&Iv>>()
);
}
#[test]
fn test_merge_overlaps() {
let mut lapper = setup_badlapper();
let expected: Vec<&Iv> = vec![
&Iv{start: 10, stop: 16, val: 0},
&Iv{start: 40, stop: 45, val: 0},
&Iv{start: 50, stop: 55, val: 0},
&Iv{start: 60, stop: 65, val: 0},
&Iv{start: 68, stop: 120, val: 0},
];
lapper.merge_overlaps();
assert_eq!(expected, lapper.iter().collect::<Vec<&Iv>>())
}
#[test]
fn test_lapper_cov() {
let mut lapper = setup_badlapper();
let before = lapper.cov();
lapper.merge_overlaps();
let after = lapper.cov();
assert_eq!(before, after);
let mut lapper = setup_nonoverlapping();
lapper.set_cov();
assert_eq!(lapper.cov(), 50);
}
#[test]
fn test_interval_intersects() {
let i1 = Iv{start: 70, stop: 120, val: 0};
let i2 = Iv{start: 10, stop: 15, val: 0};
let i3 = Iv{start: 10, stop: 15, val: 0};
let i4 = Iv{start: 12, stop: 15, val: 0};
let i5 = Iv{start: 14, stop: 16, val: 0};
let i6 = Iv{start: 40, stop: 50, val: 0};
let i7 = Iv{start: 50, stop: 55, val: 0};
let i_8 = Iv{start: 60, stop: 65, val: 0};
let i9 = Iv{start: 68, stop: 71, val: 0};
let i10 = Iv{start: 70, stop: 75, val: 0};
assert_eq!(i2.intersect(&i3), 5);
assert_eq!(i2.intersect(&i4), 3);
assert_eq!(i2.intersect(&i5), 1);
assert_eq!(i9.intersect(&i10), 1);
assert_eq!(i7.intersect(&i_8), 0);
assert_eq!(i6.intersect(&i7), 0);
assert_eq!(i1.intersect(&i10), 5);
}
#[test]
fn test_union_and_intersect() {
let data1: Vec<Iv> = vec![
Iv{start: 70, stop: 120, val: 0},
Iv{start: 10, stop: 15, val: 0},
Iv{start: 12, stop: 15, val: 0},
Iv{start: 14, stop: 16, val: 0},
Iv{start: 68, stop: 71, val: 0},
];
let data2: Vec<Iv> = vec![
Iv{start: 10, stop: 15, val: 0},
Iv{start: 40, stop: 45, val: 0},
Iv{start: 50, stop: 55, val: 0},
Iv{start: 60, stop: 65, val: 0},
Iv{start: 70, stop: 75, val: 0},
];
let (mut lapper1, mut lapper2) = (Lapper::new(data1), Lapper::new(data2)) ;
let (union, intersect) = lapper1.union_and_intersect(&lapper2);
assert_eq!(intersect, 10);
assert_eq!(union, 73);
let (union, intersect) = lapper2.union_and_intersect(&lapper1);
assert_eq!(intersect, 10);
assert_eq!(union, 73);
lapper1.merge_overlaps();
lapper1.set_cov();
lapper2.merge_overlaps();
lapper2.set_cov();
let (union, intersect) = lapper1.union_and_intersect(&lapper2);
assert_eq!(intersect, 10);
assert_eq!(union, 73);
let (union, intersect) = lapper2.union_and_intersect(&lapper1);
assert_eq!(intersect, 10);
assert_eq!(union, 73);
}
#[test]
fn test_seek_over_len() {
let lapper = setup_nonoverlapping();
let single = setup_single();
let mut cursor: usize = 0;
for interval in lapper.iter() {
for o_interval in single.seek(interval.start, interval.stop, &mut cursor) {
println!("{:#?}", o_interval);
}
}
}
#[test]
fn test_find_over_behind_first_match() {
let lapper = setup_badlapper();
let e1 = Iv {start: 50, stop: 55, val: 0};
let found = lapper.find(50, 55).next();
assert_eq!(found, Some(&e1));
}
}