Crate rust_lapper

(Docs from nim-lapper, by Brent Pendersen) This module provides a simple data-structure for fast interval searches. It does not use an interval tree, instead, it operates on the assumtion that most intervals are of similar length; or, more exactly, that the longest interval in the set is not long compred to the average distance between intervals. On any dataset where that is not the case, this method will not perform well. For cases where this holds true (as it often does with genomic data), we can sort by start and use binary search on the starts, accounting for the length of the longest interval. The advantage of this approach is simplicity of implementation and speed. In realistic tests queries returning the overlapping intervals are 1000 times faster than brute force and queries that merely check for the overlaps are > 5000 times faster.

The main methods are find and seek where the latter uses a cursor and is very fast for cases when the queries are sorted. This is another innovation in this library that allows an additional ~50% speed improvement when consecutive queries are known to be in sort order.

The overlap function for this assumes a zero based genomic coordinate system. So [start, stop) is not inclusive of the stop position for neither the queries, nor the Intervals.

Examples

   use rust_lapper::{Interval, Lapper};
   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, stop: x + 2, val: 0}).collect();
   println!("{:#?}", data);

   // make lapper structure
   let laps = Lapper::new(data);

   assert_eq!(laps.find(6, 11).next(), Some(&Iv{start: 5, stop: 7, val: 0}));

   let mut sim: i32 = 0;
   let mut cursor = 0;
   // Calculate the overlap between the query and the found intervals, sum total overlap
   for i in (0..10).step_by(3) {
       sim += laps
           .seek(i, i + 2, &mut cursor)
           .map(|iv| cmp::min(i + 2, iv.stop) - cmp::max(i, iv.start))
           .sum::<i32>();
   }
   assert_eq!(sim, 3);

Structs

Interval
IterFind	Find Iterator
IterLapper	Lapper Iterator
Lapper	Primary object of the library. The public intervals holds all the intervals and can be used for iterating / pulling values out of the tree.