Struct Lapper

Source

pub struct Lapper<I, T>where
    I: PrimInt + Ord + Clone + Send + Sync,
    T: Eq + Clone + Send + Sync,{
    pub intervals: Vec<Interval<I, T>>,
    pub overlaps_merged: bool,
    /* private fields */
}

Expand description

Primary interval collection and query index.

The public interval vector is the canonical storage and can be read or used to mutate payload values. Coordinate or structural changes must use Lapper::insert or Lapper::merge_overlaps so the private query index is rebuilt.

Fields§

§intervals: Vec<Interval<I, T>>

Intervals in ascending start order.

Directly changing coordinates or vector length leaves the private query index stale. Payload-only changes are safe.

§overlaps_merged: bool

Whether or not overlaps have been merged

Implementations§

Source §

impl<I, T> Lapper<I, T>
where I: PrimInt + Ord + Clone + Send + Sync + 'static, T: Eq + Clone + Send + Sync,

Source

pub fn new(intervals: Vec<Interval<I, T>>) -> Self

Create a new instance of Lapper by passing in a vector of Intervals. This vector will immediately be sorted by start order.

use rust_lapper::{Lapper, Interval};
let data = (0..20).step_by(5)
                  .map(|x| Interval{start: x, stop: x + 10, val: true})
                  .collect::<Vec<Interval<usize, bool>>>();
let lapper = Lapper::new(data);

Source

pub fn insert(&mut self, elem: Interval<I, T>)

Insert a new interval after the Lapper has been created. This is very inefficient and should be avoided if possible.

SIDE EFFECTS: This clears cov() and overlaps_merged meaning that those will have to be recomputed after a insert

use rust_lapper::{Lapper, Interval};
let data : Vec<Interval<usize, usize>>= vec!{
    Interval{start:0,  stop:5,  val:1},
    Interval{start:6,  stop:10, val:2},
};
let mut lapper = Lapper::new(data);
lapper.insert(Interval{start:0, stop:20, val:5});
assert_eq!(lapper.len(), 3);
assert_eq!(lapper.find(1,3).collect::<Vec<&Interval<usize,usize>>>(),
    vec![
        &Interval{start:0, stop:5, val:1},
        &Interval{start:0, stop:20, val:5},
    ]
);

Source

pub fn len(&self) -> usize

Get the number over intervals in Lapper

use rust_lapper::{Lapper, Interval};
let data = (0..20).step_by(5)
                  .map(|x| Interval{start: x, stop: x + 10, val: true})
                  .collect::<Vec<Interval<usize, bool>>>();
let lapper = Lapper::new(data);
assert_eq!(lapper.len(), 4);

Source

pub fn is_empty(&self) -> bool

Check if lapper is empty

use rust_lapper::{Lapper, Interval};
let data: Vec<Interval<usize, bool>> = vec![];
let lapper = Lapper::new(data);
assert_eq!(lapper.is_empty(), true);

Source

pub fn cov(&self) -> I

Get the number of positions covered by the intervals in Lapper. This provides immutable access if it has already been set, or on the fly calculation.

use rust_lapper::{Lapper, Interval};
let data = (0..20).step_by(5)
                  .map(|x| Interval{start: x, stop: x + 10, val: true})
                  .collect::<Vec<Interval<usize, bool>>>();
let lapper = Lapper::new(data);
assert_eq!(lapper.cov(), 25);

Source

pub fn set_cov(&mut self) -> I

Get the number of positions covered by the intervals in Lapper and store it. If you are going to be using the coverage, you should set it to avoid calculating it over and over.

Source

pub fn iter(&self) -> IterLapper<'_, I, T> ⓘ

Return an iterator over the intervals in Lapper

Source

pub fn merge_overlaps(&mut self)

Merge any intervals that overlap with each other within the Lapper. This is an easy way to speed up queries.

Source

pub fn lower_bound(start: I, intervals: &[Interval<I, T>]) -> usize

Determine the first index that we should start checking for overlaps for via a binary search. Assumes that the maximum interval length in intervals has been subtracted from start, otherwise the result is undefined

Source

pub fn bsearch_seq<K>(key: K, elems: &[K]) -> usize
where K: PartialEq + PartialOrd,

Source

pub fn bsearch_seq_ref<K>(key: &K, elems: &[K]) -> usize
where K: PartialEq + PartialOrd,

Source

pub fn union_and_intersect(&self, other: &Self) -> (I, I)

Return the number of positions in the union and intersection of two Lappers.

The union counts each position covered by either Lapper once. The intersection counts each position covered by both Lappers once, regardless of how many intervals cover it.

use rust_lapper::{Lapper, Interval};
type Iv = Interval<u32, u32>;
let data1: Vec<Iv> = vec![
    Iv{start: 70, stop: 120, val: 0}, // a long interval
    Iv{start: 10, stop: 15, val: 0}, // exact overlap
    Iv{start: 12, stop: 15, val: 0}, // inner overlap
    Iv{start: 14, stop: 16, val: 0}, // overlap end
    Iv{start: 68, stop: 71, val: 0}, // overlap start
];
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)) ;
// Should be the same either way it's calculated
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();

// Should be the same either way it's calculated
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);

Source

pub fn intersect(&self, other: &Self) -> I

Find the intersect of two lapper objects. Intersect: The number of positions where both lappers intersect. Note that a position only counts one time, multiple Intervals covering the same position don’t add up

Source

pub fn union(&self, other: &Self) -> I

Find the union of two lapper objects.

Source

pub fn depth(&self) -> IterDepth<'_, I, T> ⓘ

Return the contiguous intervals of coverage, val represents the number of intervals covering the returned interval.

§Examples

use rust_lapper::{Lapper, Interval};
let data = (0..20).step_by(5)
                  .map(|x| Interval{start: x, stop: x + 10, val: true})
                  .collect::<Vec<Interval<usize, bool>>>();
let lapper = Lapper::new(data);
assert_eq!(lapper.depth().collect::<Vec<Interval<usize, usize>>>(), vec![
            Interval { start: 0, stop: 5, val: 1 },
            Interval { start: 5, stop: 20, val: 2 },
            Interval { start: 20, stop: 25, val: 1 }]);

Source

pub fn count(&self, start: I, stop: I) -> usize

Count all intervals that overlap the half-open query [start, stop). This performs two binary searches in order to find all the excluded elements, and then deduces the intersection from there. See BITS for more details.

use rust_lapper::{Lapper, Interval};
let lapper = Lapper::new((0..100).step_by(5)
                                .map(|x| Interval{start: x, stop: x+2 , val: true})
                                .collect::<Vec<Interval<usize, bool>>>());
assert_eq!(lapper.count(5, 11), 2);

Source

pub fn find(&self, start: I, stop: I) -> IterFind<'_, I, T> ⓘ

Find all intervals that overlap the half-open query [start, stop).

use rust_lapper::{Lapper, Interval};
let lapper = Lapper::new((0..100).step_by(5)
                                .map(|x| Interval{start: x, stop: x+2 , val: true})
                                .collect::<Vec<Interval<usize, bool>>>());
assert_eq!(lapper.find(5, 11).count(), 2);

Source

pub fn seek<'a>( &'a self, start: I, stop: I, cursor: &mut usize, ) -> IterFind<'a, I, T> ⓘ

Find all intervals that overlap the half-open query [start, stop).

Use this method when query starts arrive in nondecreasing order. A caller-owned cursor narrows the first candidate block, after which seek() uses the same block traversal as Lapper::find. Keeping the cursor outside Lapper allows immutable queries and preserves Sync when T and I are Sync.

use rust_lapper::{Lapper, Interval};
let lapper = Lapper::new((0..100).step_by(5)
                                .map(|x| Interval{start: x, stop: x+2 , val: true})
                                .collect::<Vec<Interval<usize, bool>>>());
let mut cursor = 0;
for i in lapper.iter() {
   assert_eq!(lapper.seek(i.start, i.stop, &mut cursor).count(), 1);
}