sstadick / rust-lapper

Rust implementation of a fast, easy, interval tree library nim-lapper
https://docs.rs/rust-lapper
MIT License
55 stars 7 forks source link

Add overlap merge function and allow for incoming vector to use it #1

Closed sstadick closed 5 years ago

sstadick commented 5 years ago
type Iv = Interval<u32>;
fn merge_overlaps(ivs: Vec<Iv>) -> Vec<Iv> {
    let mut stack: VecDeque<&mut Iv> = VecDeque::new();
    let mut ivs: Vec<Iv> = Lapper::new(ivs).into_iter().collect();
    let mut ivs = ivs.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.pop_back();
                stack.push_back(top);
            } else { // they were equal
                stack.push_back(top);
            }
        }
        stack.into_iter().map(|x| Iv{start: x.start, stop: x.stop, val: x.val}).collect()
    } else {
        vec![]
    }
}