Struct Lapper 

pub struct Lapper<I, T> {
    pub intervals: Vec<Interval<I, T>>,
    pub overlaps_merged: bool,
    /* private fields */
}

Primary object of the library. The public intervals holds all the intervals and can be used for iterating / pulling values out of the tree.

Fields

intervals: Vec<Interval<I, T>>

List of intervals

overlaps_merged: bool

Whether or not overlaps have been merged

Implementations

impl<I: PrimInt, T> Lapper<I, T>

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 bed_utils::intervaltree::{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);

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 bed_utils::intervaltree::{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},
    ]
);

pub fn len(&self) -> usize

Get the number over intervals in Lapper

use bed_utils::intervaltree::{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);

pub fn is_empty(&self) -> bool

Check if lapper is empty

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

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 bed_utils::intervaltree::{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);

pub fn set_cov(&mut self) -> I

Get the number fo 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.

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

Return an iterator over the intervals in Lapper

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

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

where K: PartialEq + PartialOrd,

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

where K: PartialEq + PartialOrd,

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

Find the union and the intersect of two lapper objects. Union: The set of positions found in both lappers 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.

use bed_utils::intervaltree::{Lapper, Interval};
type Iv = Interval<u32, u32>;
let data1: Vec<Iv> = vec![
    Iv{start: 70, stop: 120, val: 0}, // max_len = 50
    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);

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

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

Find the union of two lapper objects.

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 bed_utils::intervaltree::{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 }]);

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

Count all intervals that overlap start .. stop. This performs two binary search in order to find all the excluded elements, and then deduces the intersection from there. See BITS for more details.

use bed_utils::intervaltree::{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);

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

Find all intervals that overlap start .. stop

use bed_utils::intervaltree::{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);

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

Find all intevals that overlap start .. stop. This method will work when queries to this lapper are in sorted (start) order. It uses a linear search from the last query instead of a binary search. A reference to a cursor must be passed in. This reference will be modified and should be reused in the next query. This allows seek to not need to make the lapper object mutable, and thus use the same lapper accross threads.

use bed_utils::intervaltree::{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);
}

impl<I: PrimInt, T: Clone> Lapper<I, T>

pub fn merge_overlaps(&mut self)

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

Trait Implementations

impl<I, T> Archive for Lapper<I, T>

where Vec<Interval<I, T>>: Archive, Vec<I>: Archive, I: Archive, Option<I>: Archive, bool: Archive,

type Archived = ArchivedLapper<I, T>

The archived representation of this type.

type Resolver = LapperResolver<I, T>

The resolver for this type. It must contain all the additional information from serializing needed to make the archived type from the normal type.

fn resolve(&self, resolver: Self::Resolver, out: Place<Self::Archived>)

Creates the archived version of this value at the given position and writes it to the given output.

const COPY_OPTIMIZATION: CopyOptimization<Self> = _

An optimization flag that allows the bytes of this type to be copied directly to a writer instead of calling serialize.

impl<I: Clone, T: Clone> Clone for Lapper<I, T>

fn clone(&self) -> Lapper<I, T>

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<I: Debug, T: Debug> Debug for Lapper<I, T>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<__D: Fallible + ?Sized, I, T> Deserialize<Lapper<I, T>, __D> for Archived<Lapper<I, T>>

where Vec<Interval<I, T>>: Archive, <Vec<Interval<I, T>> as Archive>::Archived: Deserialize<Vec<Interval<I, T>>, __D>, Vec<I>: Archive, <Vec<I> as Archive>::Archived: Deserialize<Vec<I>, __D>, I: Archive, <I as Archive>::Archived: Deserialize<I, __D>, Option<I>: Archive, <Option<I> as Archive>::Archived: Deserialize<Option<I>, __D>, bool: Archive, <bool as Archive>::Archived: Deserialize<bool, __D>,

fn deserialize( &self, deserializer: &mut __D, ) -> Result<Lapper<I, T>, <__D as Fallible>::Error>

Deserializes using the given deserializer

impl<'a, I, T> IntoIterator for &'a Lapper<I, T>

type Item = &'a Interval<I, T>

The type of the elements being iterated over.

type IntoIter = Iter<'a, Interval<I, T>>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Iter<'a, Interval<I, T>>

Creates an iterator from a value.

impl<'a, I, T> IntoIterator for &'a mut Lapper<I, T>

type Item = &'a mut Interval<I, T>

The type of the elements being iterated over.

type IntoIter = IterMut<'a, Interval<I, T>>

Which kind of iterator are we turning this into?

fn into_iter(self) -> IterMut<'a, Interval<I, T>>

Creates an iterator from a value.

impl<I, T> IntoIterator for Lapper<I, T>

type Item = Interval<I, T>

The type of the elements being iterated over.

type IntoIter = IntoIter<<Lapper<I, T> as IntoIterator>::Item>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<__S: Fallible + ?Sized, I, T> Serialize<__S> for Lapper<I, T>

where Vec<Interval<I, T>>: Serialize<__S>, Vec<I>: Serialize<__S>, I: Serialize<__S>, Option<I>: Serialize<__S>, bool: Serialize<__S>,

fn serialize( &self, serializer: &mut __S, ) -> Result<<Self as Archive>::Resolver, <__S as Fallible>::Error>

Writes the dependencies for the object and returns a resolver that can create the archived type.