rust_lapper/
lib.rs

1//! This module provides a simple data-structure for fast interval searches.
2//! ## Features
3//! - Extremely fast on most genomic datasets. (3-4x faster than other methods)
4//! - Extremely fast on in order queries. (10x faster than other methods)
5//! - Extremely fast intersections count method based on the
6//!   [BITS](https://arxiv.org/pdf/1208.3407.pdf) algorithm
7//! - Parallel friendly. Queries are on an immutable structure, even for seek
8//! - Consumer / Adapter paradigm, Iterators are returned and serve as the main API for interacting
9//!   with the lapper
10//!
11//! ## Details:
12//!
13//! ```text
14//!       0  1  2  3  4  5  6  7  8  9  10 11
15//! (0,10]X  X  X  X  X  X  X  X  X  X
16//! (2,5]       X  X  X
17//! (3,8]          X  X  X  X  X
18//! (3,8]          X  X  X  X  X
19//! (3,8]          X  X  X  X  X
20//! (3,8]          X  X  X  X  X
21//! (5,9]                X  X  X  X
22//! (8,11]                        X  X  X
23//!
24//! Query: (8, 11]
25//! Answer: ((0,10], (5,9], (8,11])
26//! ```
27//!
28//! Most interaction with this crate will be through the [`Lapper`](struct.Lapper.html) struct
29//! The main methods are [`find`](struct.Lapper.html#method.find),
30//! [`seek`](struct.Lapper.html#method.seek), and [`count`](struct.Lapper.html#method.count)
31//! where both `seek` and `count` are special cases allowing for very fast queries in certain scenarios.
32//!
33//! The overlap function for this assumes a zero based genomic coordinate system. So [start, stop)
34//! is not inclusive of the stop position for neither the queries, nor the Intervals.
35//!
36//! Lapper does not use an interval tree, instead, it operates on the assumtion that most intervals are
37//! of similar length; or, more exactly, that the longest interval in the set is not long compred to
38//! the average distance between intervals.
39//!
40//! For cases where this holds true (as it often does with genomic data), we can sort by start and
41//! use binary search on the starts, accounting for the length of the longest interval. The advantage
42//! of this approach is simplicity of implementation and speed. In realistic tests queries returning
43//! the overlapping intervals are 1000 times faster than brute force and queries that merely check
44//! for the overlaps are > 5000 times faster.
45//!
46//! When this is not the case, if possible in your scenario, use merge_overlaps first, and then use
47//! `find` or `seek`. The `count` method will be fast in all scenarios.
48//!
49//! # Examples
50//!
51//! ```rust
52//!    use rust_lapper::{Interval, Lapper};
53//!    use std::cmp;
54//!    type Iv = Interval<usize, u32>;
55//!
56//!    // create some fake data
57//!    let data: Vec<Iv> = (0..20).step_by(5).map(|x| Iv{start: x, stop: x + 2, val: 0}).collect();
58//!    println!("{:#?}", data);
59//!
60//!    // make lapper structure
61//!    let laps = Lapper::new(data);
62//!
63//!    assert_eq!(laps.find(6, 11).next(), Some(&Iv{start: 5, stop: 7, val: 0}));
64//!
65//!    // Demonstration of seek function. By passing in the &mut cursor, seek can have thread local
66//!    // cursors going
67//!    let mut sim: usize = 0;
68//!    let mut cursor = 0;
69//!    // Calculate the overlap between the query and the found intervals, sum total overlap
70//!    for i in (0..10).step_by(3) {
71//!        sim += laps
72//!            .seek(i, i + 2, &mut cursor)
73//!            .map(|iv| cmp::min(i + 2, iv.stop) - cmp::max(i, iv.start))
74//!            .sum::<usize>();
75//!    }
76//!    assert_eq!(sim, 4);
77//! ```
78use num_traits::{
79    identities::{one, zero},
80    PrimInt, Unsigned,
81};
82use std::cmp::Ordering::{self};
83use std::collections::VecDeque;
84
85#[cfg(feature = "with_serde")]
86use serde::{Deserialize, Serialize};
87
88/// Represent a range from [start, stop)
89/// Inclusive start, exclusive of stop
90#[cfg_attr(feature = "with_serde", derive(Serialize, Deserialize))]
91#[derive(Eq, Debug, Clone)]
92pub struct Interval<I, T>
93where
94    I: PrimInt + Unsigned + Ord + Clone + Send + Sync,
95    T: Eq + Clone + Send + Sync,
96{
97    pub start: I,
98    pub stop: I,
99    pub val: T,
100}
101
102/// Primary object of the library. The public intervals holds all the intervals and can be used for
103/// iterating / pulling values out of the tree.
104#[cfg_attr(feature = "with_serde", derive(Serialize, Deserialize))]
105#[derive(Debug, Clone)]
106pub struct Lapper<I, T>
107where
108    I: PrimInt + Unsigned + Ord + Clone + Send + Sync,
109    T: Eq + Clone + Send + Sync,
110{
111    /// List of intervals
112    pub intervals: Vec<Interval<I, T>>,
113    /// Sorted list of start positions,
114    starts: Vec<I>,
115    /// Sorted list of end positions,
116    stops: Vec<I>,
117    /// The length of the longest interval
118    max_len: I,
119    /// The calculated number of positions covered by the intervals
120    cov: Option<I>,
121    /// Whether or not overlaps have been merged
122    pub overlaps_merged: bool,
123}
124
125impl<I, T> Interval<I, T>
126where
127    I: PrimInt + Unsigned + Ord + Clone + Send + Sync,
128    T: Eq + Clone + Send + Sync,
129{
130    /// Compute the intsect between two intervals
131    #[inline]
132    pub fn intersect(&self, other: &Interval<I, T>) -> I {
133        std::cmp::min(self.stop, other.stop)
134            .checked_sub(std::cmp::max(&self.start, &other.start))
135            .unwrap_or_else(zero::<I>)
136    }
137
138    /// Check if two intervals overlap
139    #[inline]
140    pub fn overlap(&self, start: I, stop: I) -> bool {
141        self.start < stop && self.stop > start
142    }
143}
144
145impl<I, T> Ord for Interval<I, T>
146where
147    I: PrimInt + Unsigned + Ord + Clone + Send + Sync,
148    T: Eq + Clone + Send + Sync,
149{
150    #[inline]
151    fn cmp(&self, other: &Interval<I, T>) -> Ordering {
152        match self.start.cmp(&other.start) {
153            Ordering::Less => Ordering::Less,
154            Ordering::Greater => Ordering::Greater,
155            Ordering::Equal => self.stop.cmp(&other.stop),
156        }
157    }
158}
159
160impl<I, T> PartialOrd for Interval<I, T>
161where
162    I: PrimInt + Unsigned + Ord + Clone + Send + Sync,
163    T: Eq + Clone + Send + Sync,
164{
165    #[inline]
166    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
167        Some(self.cmp(other))
168    }
169}
170
171impl<I, T> PartialEq for Interval<I, T>
172where
173    I: PrimInt + Unsigned + Ord + Clone + Send + Sync,
174    T: Eq + Clone + Send + Sync,
175{
176    #[inline]
177    fn eq(&self, other: &Interval<I, T>) -> bool {
178        self.start == other.start && self.stop == other.stop
179    }
180}
181
182impl<I, T> Lapper<I, T>
183where
184    I: PrimInt + Unsigned + Ord + Clone + Send + Sync,
185    T: Eq + Clone + Send + Sync,
186{
187    /// Create a new instance of Lapper by passing in a vector of Intervals. This vector will
188    /// immediately be sorted by start order.
189    /// ```
190    /// use rust_lapper::{Lapper, Interval};
191    /// let data = (0..20).step_by(5)
192    ///                   .map(|x| Interval{start: x, stop: x + 10, val: true})
193    ///                   .collect::<Vec<Interval<usize, bool>>>();
194    /// let lapper = Lapper::new(data);
195    /// ```
196    pub fn new(mut intervals: Vec<Interval<I, T>>) -> Self {
197        intervals.sort();
198        let (mut starts, mut stops): (Vec<_>, Vec<_>) =
199            intervals.iter().map(|x| (x.start, x.stop)).unzip();
200        starts.sort();
201        stops.sort();
202        let mut max_len = zero::<I>();
203        for interval in intervals.iter() {
204            let i_len = interval
205                .stop
206                .checked_sub(&interval.start)
207                .unwrap_or_else(zero::<I>);
208            if i_len > max_len {
209                max_len = i_len;
210            }
211        }
212        Lapper {
213            intervals,
214            starts,
215            stops,
216            max_len,
217            cov: None,
218            overlaps_merged: false,
219        }
220    }
221
222    /// Insert a new interval after the Lapper has been created. This is very
223    /// inefficient and should be avoided if possible.
224    ///
225    /// SIDE EFFECTS: This clears cov() and overlaps_merged
226    /// meaning that those will have to be recomputed after a insert
227    /// ```
228    /// use rust_lapper::{Lapper, Interval};
229    /// let data : Vec<Interval<usize, usize>>= vec!{
230    ///     Interval{start:0,  stop:5,  val:1},
231    ///     Interval{start:6,  stop:10, val:2},
232    /// };
233    /// let mut lapper = Lapper::new(data);
234    /// lapper.insert(Interval{start:0, stop:20, val:5});
235    /// assert_eq!(lapper.len(), 3);
236    /// assert_eq!(lapper.find(1,3).collect::<Vec<&Interval<usize,usize>>>(),
237    ///     vec![
238    ///         &Interval{start:0, stop:5, val:1},
239    ///         &Interval{start:0, stop:20, val:5},
240    ///     ]
241    /// );
242    ///
243    /// ```
244    pub fn insert(&mut self, elem: Interval<I, T>) {
245        let starts_insert_index = Self::bsearch_seq(elem.start, &self.starts);
246        let stops_insert_index = Self::bsearch_seq(elem.stop, &self.stops);
247        let intervals_insert_index = Self::bsearch_seq_ref(&elem, &self.intervals);
248        let i_len = elem.stop.checked_sub(&elem.start).unwrap_or_else(zero::<I>);
249        if i_len > self.max_len {
250            self.max_len = i_len;
251        }
252        self.starts.insert(starts_insert_index, elem.start);
253        self.stops.insert(stops_insert_index, elem.stop);
254        self.intervals.insert(intervals_insert_index, elem);
255        self.cov = None;
256        self.overlaps_merged = false;
257    }
258
259    /// Get the number over intervals in Lapper
260    /// ```
261    /// use rust_lapper::{Lapper, Interval};
262    /// let data = (0..20).step_by(5)
263    ///                   .map(|x| Interval{start: x, stop: x + 10, val: true})
264    ///                   .collect::<Vec<Interval<usize, bool>>>();
265    /// let lapper = Lapper::new(data);
266    /// assert_eq!(lapper.len(), 4);
267    /// ```
268    #[inline]
269    pub fn len(&self) -> usize {
270        self.intervals.len()
271    }
272
273    /// Check if lapper is empty
274    /// ```
275    /// use rust_lapper::{Lapper, Interval};
276    /// let data: Vec<Interval<usize, bool>> = vec![];
277    /// let lapper = Lapper::new(data);
278    /// assert_eq!(lapper.is_empty(), true);
279    /// ```
280    #[inline]
281    pub fn is_empty(&self) -> bool {
282        self.intervals.is_empty()
283    }
284
285    /// Get the number of positions covered by the intervals in Lapper. This provides immutable
286    /// access if it has already been set, or on the fly calculation.
287    /// ```
288    /// use rust_lapper::{Lapper, Interval};
289    /// let data = (0..20).step_by(5)
290    ///                   .map(|x| Interval{start: x, stop: x + 10, val: true})
291    ///                   .collect::<Vec<Interval<usize, bool>>>();
292    /// let lapper = Lapper::new(data);
293    /// assert_eq!(lapper.cov(), 25);
294    #[inline]
295    pub fn cov(&self) -> I {
296        match self.cov {
297            None => self.calculate_coverage(),
298            Some(cov) => cov,
299        }
300    }
301
302    /// Get the number fo positions covered by the intervals in Lapper and store it. If you are
303    /// going to be using the coverage, you should set it to avoid calculating it over and over.
304    pub fn set_cov(&mut self) -> I {
305        let cov = self.calculate_coverage();
306        self.cov = Some(cov);
307        cov
308    }
309
310    /// Calculate the actual coverage behind the scenes.
311    fn calculate_coverage(&self) -> I {
312        let mut moving_interval = Interval {
313            start: zero::<I>(),
314            stop: zero::<I>(),
315            val: zero::<I>(),
316        };
317        let mut cov = zero::<I>();
318
319        for interval in self.intervals.iter() {
320            // If it overlaps, embrace, extend, extinguish
321            if moving_interval.overlap(interval.start, interval.stop) {
322                moving_interval.start = std::cmp::min(moving_interval.start, interval.start);
323                moving_interval.stop = std::cmp::max(moving_interval.stop, interval.stop);
324            } else {
325                // add the set and move on
326                cov = cov + (moving_interval.stop - moving_interval.start);
327                moving_interval.start = interval.start;
328                moving_interval.stop = interval.stop;
329            }
330        }
331        // add in the last bit
332        cov = cov + (moving_interval.stop - moving_interval.start);
333        cov
334    }
335
336    /// Return an iterator over the intervals in Lapper
337    #[inline]
338    pub fn iter(&self) -> IterLapper<I, T> {
339        IterLapper {
340            inner: self,
341            pos: 0,
342        }
343    }
344
345    /// Merge any intervals that overlap with eachother within the Lapper. This is an easy way to
346    /// speed up queries.
347    pub fn merge_overlaps(&mut self) {
348        let mut stack: VecDeque<&mut Interval<I, T>> = VecDeque::new();
349        let mut ivs = self.intervals.iter_mut();
350        if let Some(first) = ivs.next() {
351            stack.push_back(first);
352            for interval in ivs {
353                let top = stack.pop_back().unwrap();
354                if top.stop < interval.start {
355                    stack.push_back(top);
356                    stack.push_back(interval);
357                } else if top.stop < interval.stop {
358                    top.stop = interval.stop;
359                    //stack.pop_back();
360                    stack.push_back(top);
361                } else {
362                    // they were equal
363                    stack.push_back(top);
364                }
365            }
366            self.overlaps_merged = true;
367            self.intervals = stack
368                .into_iter()
369                .map(|x| Interval {
370                    start: x.start,
371                    stop: x.stop,
372                    val: x.val.clone(),
373                })
374                .collect();
375        }
376        // Fix the starts and stops used by counts
377        let (mut starts, mut stops): (Vec<_>, Vec<_>) =
378            self.intervals.iter().map(|x| (x.start, x.stop)).unzip();
379        starts.sort();
380        stops.sort();
381        self.starts = starts;
382        self.stops = stops;
383        self.max_len = self
384            .intervals
385            .iter()
386            .map(|x| x.stop.checked_sub(&x.start).unwrap_or_else(zero::<I>))
387            .max()
388            .unwrap_or_else(zero::<I>);
389    }
390
391    /// Determine the first index that we should start checking for overlaps for via a binary
392    /// search.
393    /// Assumes that the maximum interval length in `intervals` has been subtracted from
394    /// `start`, otherwise the result is undefined
395    #[inline]
396    pub fn lower_bound(start: I, intervals: &[Interval<I, T>]) -> usize {
397        let mut size = intervals.len();
398        let mut low = 0;
399
400        while size > 0 {
401            let half = size / 2;
402            let other_half = size - half;
403            let probe = low + half;
404            let other_low = low + other_half;
405            let v = &intervals[probe];
406            size = half;
407            low = if v.start < start { other_low } else { low }
408        }
409        low
410    }
411
412    #[inline]
413    pub fn bsearch_seq<K>(key: K, elems: &[K]) -> usize
414    where
415        K: PartialEq + PartialOrd,
416    {
417        Self::bsearch_seq_ref(&key, elems)
418    }
419
420    #[inline]
421    pub fn bsearch_seq_ref<K>(key: &K, elems: &[K]) -> usize
422    where
423        K: PartialEq + PartialOrd,
424    {
425        if elems.is_empty() || elems[0] >= *key {
426            return 0;
427        } else if elems[elems.len() - 1] < *key {
428            return elems.len();
429        }
430
431        let mut cursor = 0;
432        let mut length = elems.len();
433        while length > 1 {
434            let half = length >> 1;
435            length -= half;
436            cursor += (usize::from(elems[cursor + half - 1] < *key)) * half;
437        }
438        cursor
439    }
440
441    /// Find the union and the intersect of two lapper objects.
442    /// Union: The set of positions found in both lappers
443    /// Intersect: The number of positions where both lappers intersect. Note that a position only
444    /// counts one time, multiple Intervals covering the same position don't add up.
445    /// ``` rust
446    /// use rust_lapper::{Lapper, Interval};
447    /// type Iv = Interval<u32, u32>;
448    /// let data1: Vec<Iv> = vec![
449    ///     Iv{start: 70, stop: 120, val: 0}, // max_len = 50
450    ///     Iv{start: 10, stop: 15, val: 0}, // exact overlap
451    ///     Iv{start: 12, stop: 15, val: 0}, // inner overlap
452    ///     Iv{start: 14, stop: 16, val: 0}, // overlap end
453    ///     Iv{start: 68, stop: 71, val: 0}, // overlap start
454    /// ];
455    /// let data2: Vec<Iv> = vec![
456    ///
457    ///     Iv{start: 10, stop: 15, val: 0},
458    ///     Iv{start: 40, stop: 45, val: 0},
459    ///     Iv{start: 50, stop: 55, val: 0},
460    ///     Iv{start: 60, stop: 65, val: 0},
461    ///     Iv{start: 70, stop: 75, val: 0},
462    /// ];
463    ///
464    /// let (mut lapper1, mut lapper2) = (Lapper::new(data1), Lapper::new(data2)) ;
465    /// // Should be the same either way it's calculated
466    /// let (union, intersect) = lapper1.union_and_intersect(&lapper2);
467    /// assert_eq!(intersect, 10);
468    /// assert_eq!(union, 73);
469    /// let (union, intersect) = lapper2.union_and_intersect(&lapper1);
470    /// assert_eq!(intersect, 10);
471    /// assert_eq!(union, 73);
472    /// lapper1.merge_overlaps();
473    /// lapper1.set_cov();
474    /// lapper2.merge_overlaps();
475    /// lapper2.set_cov();
476    ///
477    /// // Should be the same either way it's calculated
478    /// let (union, intersect) = lapper1.union_and_intersect(&lapper2);
479    /// assert_eq!(intersect, 10);
480    /// assert_eq!(union, 73);
481    /// let (union, intersect) = lapper2.union_and_intersect(&lapper1);
482    /// assert_eq!(intersect, 10);
483    /// assert_eq!(union, 73);
484    /// ```
485    #[inline]
486    pub fn union_and_intersect(&self, other: &Self) -> (I, I) {
487        let mut cursor: usize = 0;
488
489        if !self.overlaps_merged || !other.overlaps_merged {
490            let mut intersections: Vec<Interval<I, bool>> = vec![];
491            for self_iv in self.iter() {
492                for other_iv in other.seek(self_iv.start, self_iv.stop, &mut cursor) {
493                    let start = std::cmp::max(self_iv.start, other_iv.start);
494                    let stop = std::cmp::min(self_iv.stop, other_iv.stop);
495                    intersections.push(Interval {
496                        start,
497                        stop,
498                        val: true,
499                    });
500                }
501            }
502            let mut temp_lapper = Lapper::new(intersections);
503            temp_lapper.merge_overlaps();
504            temp_lapper.set_cov();
505            let union = self.cov() + other.cov() - temp_lapper.cov();
506            (union, temp_lapper.cov())
507        } else {
508            let mut intersect = zero::<I>();
509            for c1_iv in self.iter() {
510                for c2_iv in other.seek(c1_iv.start, c1_iv.stop, &mut cursor) {
511                    let local_intersect = c1_iv.intersect(c2_iv);
512                    intersect = intersect + local_intersect;
513                }
514            }
515            let union = self.cov() + other.cov() - intersect;
516            (union, intersect)
517        }
518    }
519
520    /// Find the intersect of two lapper objects.
521    /// Intersect: The number of positions where both lappers intersect. Note that a position only
522    /// counts one time, multiple Intervals covering the same position don't add up
523    #[inline]
524    pub fn intersect(&self, other: &Self) -> I {
525        self.union_and_intersect(other).1
526    }
527
528    /// Find the union of two lapper objects.
529    #[inline]
530    pub fn union(&self, other: &Self) -> I {
531        self.union_and_intersect(other).0
532    }
533
534    /// Return the contiguous intervals of coverage, `val` represents the number of intervals
535    /// covering the returned interval.
536    ///
537    /// # Examples
538    /// ```
539    /// use rust_lapper::{Lapper, Interval};
540    /// let data = (0..20).step_by(5)
541    ///                   .map(|x| Interval{start: x, stop: x + 10, val: true})
542    ///                   .collect::<Vec<Interval<usize, bool>>>();
543    /// let lapper = Lapper::new(data);
544    /// assert_eq!(lapper.depth().collect::<Vec<Interval<usize, usize>>>(), vec![
545    ///             Interval { start: 0, stop: 5, val: 1 },
546    ///             Interval { start: 5, stop: 20, val: 2 },
547    ///             Interval { start: 20, stop: 25, val: 1 }]);
548    /// ```
549    #[inline]
550    pub fn depth(&self) -> IterDepth<I, T> {
551        let mut merged_lapper = Lapper::new(
552            self.intervals
553                .iter()
554                .map(|i| Interval {
555                    start: i.start,
556                    stop: i.stop,
557                    val: true,
558                })
559                .collect::<Vec<Interval<I, bool>>>(),
560        );
561        merged_lapper.merge_overlaps();
562        let merged_len = merged_lapper.intervals.len();
563        IterDepth {
564            inner: self,
565            merged: merged_lapper,
566            curr_merged_pos: zero::<I>(),
567            curr_pos: 0,
568            cursor: 0,
569            end: merged_len,
570        }
571    }
572
573    /// Count all intervals that overlap start .. stop. This performs two binary search in order to
574    /// find all the excluded elements, and then deduces the intersection from there. See
575    /// [BITS](https://arxiv.org/pdf/1208.3407.pdf) for more details.
576    /// ```
577    /// use rust_lapper::{Lapper, Interval};
578    /// let lapper = Lapper::new((0..100).step_by(5)
579    ///                                 .map(|x| Interval{start: x, stop: x+2 , val: true})
580    ///                                 .collect::<Vec<Interval<usize, bool>>>());
581    /// assert_eq!(lapper.count(5, 11), 2);
582    /// ```
583    #[inline]
584    pub fn count(&self, start: I, stop: I) -> usize {
585        let len = self.intervals.len();
586        // Plus one to account for half-openness of lapper intervals compared to BITS paper
587        let first = Self::bsearch_seq(start + one::<I>(), &self.stops);
588        let last = Self::bsearch_seq(stop, &self.starts);
589        let num_cant_after = len - last;
590        len - first - num_cant_after
591    }
592
593    /// Find all intervals that overlap start .. stop
594    /// ```
595    /// use rust_lapper::{Lapper, Interval};
596    /// let lapper = Lapper::new((0..100).step_by(5)
597    ///                                 .map(|x| Interval{start: x, stop: x+2 , val: true})
598    ///                                 .collect::<Vec<Interval<usize, bool>>>());
599    /// assert_eq!(lapper.find(5, 11).count(), 2);
600    /// ```
601    #[inline]
602    pub fn find(&self, start: I, stop: I) -> IterFind<I, T> {
603        IterFind {
604            inner: self,
605            off: Self::lower_bound(
606                start.checked_sub(&self.max_len).unwrap_or_else(zero::<I>),
607                &self.intervals,
608            ),
609            start,
610            stop,
611        }
612    }
613
614    /// Find all intevals that overlap start .. stop. This method will work when queries
615    /// to this lapper are in sorted (start) order. It uses a linear search from the last query
616    /// instead of a binary search. A reference to a cursor must be passed in. This reference will
617    /// be modified and should be reused in the next query. This allows seek to not need to make
618    /// the lapper object mutable, and thus use the same lapper accross threads.
619    /// ```
620    /// use rust_lapper::{Lapper, Interval};
621    /// let lapper = Lapper::new((0..100).step_by(5)
622    ///                                 .map(|x| Interval{start: x, stop: x+2 , val: true})
623    ///                                 .collect::<Vec<Interval<usize, bool>>>());
624    /// let mut cursor = 0;
625    /// for i in lapper.iter() {
626    ///    assert_eq!(lapper.seek(i.start, i.stop, &mut cursor).count(), 1);
627    /// }
628    /// ```
629    #[inline]
630    pub fn seek<'a>(&'a self, start: I, stop: I, cursor: &mut usize) -> IterFind<'a, I, T> {
631        if *cursor == 0 || (*cursor < self.intervals.len() && self.intervals[*cursor].start > start)
632        {
633            *cursor = Self::lower_bound(
634                start.checked_sub(&self.max_len).unwrap_or_else(zero::<I>),
635                &self.intervals,
636            );
637        }
638
639        while *cursor + 1 < self.intervals.len()
640            && self.intervals[*cursor + 1].start
641                < start.checked_sub(&self.max_len).unwrap_or_else(zero::<I>)
642        {
643            *cursor += 1;
644        }
645
646        IterFind {
647            inner: self,
648            off: *cursor,
649            start,
650            stop,
651        }
652    }
653}
654
655/// Find Iterator
656#[derive(Debug)]
657pub struct IterFind<'a, I, T>
658where
659    T: Eq + Clone + Send + Sync + 'a,
660    I: PrimInt + Unsigned + Ord + Clone + Send + Sync,
661{
662    inner: &'a Lapper<I, T>,
663    off: usize,
664    start: I,
665    stop: I,
666}
667
668impl<'a, I, T> Iterator for IterFind<'a, I, T>
669where
670    T: Eq + Clone + Send + Sync + 'a,
671    I: PrimInt + Unsigned + Ord + Clone + Send + Sync,
672{
673    type Item = &'a Interval<I, T>;
674
675    #[inline]
676    // interval.start < stop && interval.stop > start
677    fn next(&mut self) -> Option<Self::Item> {
678        while self.off < self.inner.intervals.len() {
679            //let mut generator = self.inner.intervals[self.off..].iter();
680            //while let Some(interval) = generator.next() {
681            let interval = &self.inner.intervals[self.off];
682            self.off += 1;
683            if interval.overlap(self.start, self.stop) {
684                return Some(interval);
685            } else if interval.start >= self.stop {
686                break;
687            }
688        }
689        None
690    }
691}
692
693/// Depth Iterator
694#[derive(Debug)]
695pub struct IterDepth<'a, I, T>
696where
697    T: Eq + Clone + Send + Sync + 'a,
698    I: PrimInt + Unsigned + Ord + Clone + Send + Sync,
699{
700    inner: &'a Lapper<I, T>,
701    merged: Lapper<I, bool>, // A lapper that is the merged_lapper of inner
702    curr_merged_pos: I,      // Current start position in current interval
703    curr_pos: usize,         // In merged list of non-overlapping intervals
704    cursor: usize,           // cursor for seek over inner lapper
705    end: usize,              // len of merged
706}
707
708impl<'a, I, T> Iterator for IterDepth<'a, I, T>
709where
710    T: Eq + Clone + Send + Sync + 'a,
711    I: PrimInt + Unsigned + Ord + Clone + Send + Sync,
712{
713    type Item = Interval<I, I>;
714
715    #[inline]
716    fn next(&mut self) -> Option<Self::Item> {
717        let mut interval: &Interval<I, bool> = &self.merged.intervals[self.curr_pos];
718        if self.curr_merged_pos == zero::<I>() {
719            self.curr_merged_pos = interval.start;
720        }
721        if interval.stop == self.curr_merged_pos {
722            if self.curr_pos + 1 != self.end {
723                self.curr_pos += 1;
724                interval = &self.merged.intervals[self.curr_pos];
725                self.curr_merged_pos = interval.start;
726            } else {
727                return None;
728            }
729        }
730        let start = self.curr_merged_pos;
731        let depth_at_point = self
732            .inner
733            .seek(
734                self.curr_merged_pos,
735                self.curr_merged_pos + one::<I>(),
736                &mut self.cursor,
737            )
738            .count();
739        let mut new_depth_at_point = depth_at_point;
740        while new_depth_at_point == depth_at_point && self.curr_merged_pos < interval.stop {
741            self.curr_merged_pos = self.curr_merged_pos + one::<I>();
742            new_depth_at_point = self
743                .inner
744                .seek(
745                    self.curr_merged_pos,
746                    self.curr_merged_pos + one::<I>(),
747                    &mut self.cursor,
748                )
749                .count();
750        }
751        Some(Interval {
752            start,
753            stop: self.curr_merged_pos,
754            val: I::from(depth_at_point).unwrap(), // from usize should always work
755        })
756    }
757}
758/// Lapper Iterator
759pub struct IterLapper<'a, I, T>
760where
761    T: Eq + Clone + Send + Sync + 'a,
762    I: PrimInt + Unsigned + Ord + Clone + Send + Sync,
763{
764    inner: &'a Lapper<I, T>,
765    pos: usize,
766}
767
768impl<'a, I, T> Iterator for IterLapper<'a, I, T>
769where
770    T: Eq + Clone + Send + Sync + 'a,
771    I: PrimInt + Unsigned + Ord + Clone + Send + Sync,
772{
773    type Item = &'a Interval<I, T>;
774
775    fn next(&mut self) -> Option<Self::Item> {
776        if self.pos >= self.inner.intervals.len() {
777            None
778        } else {
779            self.pos += 1;
780            self.inner.intervals.get(self.pos - 1)
781        }
782    }
783}
784
785impl<I, T> IntoIterator for Lapper<I, T>
786where
787    T: Eq + Clone + Send + Sync,
788    I: PrimInt + Unsigned + Ord + Clone + Send + Sync,
789{
790    type Item = Interval<I, T>;
791    type IntoIter = ::std::vec::IntoIter<Self::Item>;
792
793    fn into_iter(self) -> Self::IntoIter {
794        self.intervals.into_iter()
795    }
796}
797
798impl<'a, I, T> IntoIterator for &'a Lapper<I, T>
799where
800    T: Eq + Clone + Send + Sync + 'a,
801    I: PrimInt + Unsigned + Ord + Clone + Send + Sync,
802{
803    type Item = &'a Interval<I, T>;
804    type IntoIter = std::slice::Iter<'a, Interval<I, T>>;
805
806    fn into_iter(self) -> std::slice::Iter<'a, Interval<I, T>> {
807        self.intervals.iter()
808    }
809}
810
811impl<'a, I, T> IntoIterator for &'a mut Lapper<I, T>
812where
813    T: Eq + Clone + Send + Sync + 'a,
814    I: PrimInt + Unsigned + Ord + Clone + Send + Sync,
815{
816    type Item = &'a mut Interval<I, T>;
817    type IntoIter = std::slice::IterMut<'a, Interval<I, T>>;
818
819    fn into_iter(self) -> std::slice::IterMut<'a, Interval<I, T>> {
820        self.intervals.iter_mut()
821    }
822}
823
824#[cfg(test)]
825#[rustfmt::skip]
826mod tests {
827    use super::*;
828
829    type Iv = Interval<usize, u32>;
830    fn setup_nonoverlapping() -> Lapper<usize, u32> {
831        let data: Vec<Iv> = (0..100)
832            .step_by(20)
833            .map(|x| Iv {
834                start: x,
835                stop: x + 10,
836                val: 0,
837            })
838            .collect();
839        Lapper::new(data)
840    }
841
842    fn setup_overlapping() -> Lapper<usize, u32> {
843        let data: Vec<Iv> = (0..100)
844            .step_by(10)
845            .map(|x| Iv {
846                start: x,
847                stop: x + 15,
848                val: 0,
849            })
850            .collect();
851        Lapper::new(data)
852    }
853
854    fn setup_badlapper() -> Lapper<usize, u32> {
855        let data: Vec<Iv> = vec![
856            Iv{start: 70, stop: 120, val: 0}, // max_len = 50
857            Iv{start: 10, stop: 15, val: 0},
858            Iv{start: 10, stop: 15, val: 0}, // exact overlap
859            Iv{start: 12, stop: 15, val: 0}, // inner overlap
860            Iv{start: 14, stop: 16, val: 0}, // overlap end
861            Iv{start: 40, stop: 45, val: 0},
862            Iv{start: 50, stop: 55, val: 0},
863            Iv{start: 60, stop: 65, val: 0},
864            Iv{start: 68, stop: 71, val: 0}, // overlap start
865            Iv{start: 70, stop: 75, val: 0},
866        ];
867        Lapper::new(data)
868    }
869
870    fn setup_single() -> Lapper<usize, u32> {
871        let data: Vec<Iv> = vec![Iv {
872            start: 10,
873            stop: 35,
874            val: 0,
875        }];
876        Lapper::new(data)
877    }
878
879    // Test that inserting data ends up with the same lapper (nonoverlapping)
880    #[test]
881    fn insert_equality_nonoverlapping() {
882        let data: Vec<Iv> = (0..100)
883            .step_by(20)
884            .map(|x| Iv {
885                start: x,
886                stop: x + 10,
887                val: 0,
888            })
889            .collect();
890        let new_lapper = Lapper::new(data.clone());
891        let mut insert_lapper = Lapper::new(vec![]);
892        for elem in data {
893            insert_lapper.insert(elem);
894        }
895        assert_eq!(new_lapper.starts, insert_lapper.starts);
896        assert_eq!(new_lapper.stops, insert_lapper.stops);
897        assert_eq!(new_lapper.intervals, insert_lapper.intervals);
898        assert_eq!(new_lapper.max_len, insert_lapper.max_len);
899    }
900
901    // Test that inserting data ends up with the same lapper (overlapping)
902    #[test]
903    fn insert_equality_overlapping() {
904        let data: Vec<Iv> = (0..100)
905            .step_by(10)
906            .map(|x| Iv {
907                start: x,
908                stop: x + 15,
909                val: 0,
910            })
911            .collect();
912        let new_lapper = Lapper::new(data.clone());
913        let mut insert_lapper = Lapper::new(vec![]);
914        for elem in data {
915            insert_lapper.insert(elem);
916        }
917        assert_eq!(new_lapper.starts, insert_lapper.starts);
918        assert_eq!(new_lapper.stops, insert_lapper.stops);
919        assert_eq!(new_lapper.intervals, insert_lapper.intervals);
920        assert_eq!(new_lapper.max_len, insert_lapper.max_len);
921    }
922
923    // Test that inserting data half with new and half with insert
924    // ends up with the same lapper
925    #[test]
926    fn insert_equality_half_and_half() {
927        let data: Vec<Iv> = (0..100)
928            .step_by(1)
929            .map(|x| Iv {
930                start: x,
931                stop: x + 15,
932                val: 0,
933            })
934            .collect();
935        let new_lapper = Lapper::new(data.clone());
936        let (new_data, insert_data) = data.split_at(50);
937        let mut insert_lapper = Lapper::new(new_data.to_vec());
938        let mut insert_data = insert_data.to_vec();
939        insert_data.reverse();
940        for elem in insert_data {
941            insert_lapper.insert(elem);
942        }
943        assert_eq!(new_lapper.starts, insert_lapper.starts);
944        assert_eq!(new_lapper.stops, insert_lapper.stops);
945        assert_eq!(new_lapper.intervals, insert_lapper.intervals);
946        assert_eq!(new_lapper.max_len, insert_lapper.max_len);
947    }
948
949    // Test that inserting data ends up with the same lapper (badlapper)
950    #[test]
951    fn insert_equality_badlapper() {
952        let data: Vec<Iv> = vec![
953            Iv{start: 70, stop: 120, val: 0}, // max_len = 50
954            Iv{start: 10, stop: 15, val: 0},
955            Iv{start: 10, stop: 15, val: 0}, // exact overlap
956            Iv{start: 12, stop: 15, val: 0}, // inner overlap
957            Iv{start: 14, stop: 16, val: 0}, // overlap end
958            Iv{start: 40, stop: 45, val: 0},
959            Iv{start: 50, stop: 55, val: 0},
960            Iv{start: 60, stop: 65, val: 0},
961            Iv{start: 68, stop: 71, val: 0}, // overlap start
962            Iv{start: 70, stop: 75, val: 0},
963        ];
964        let new_lapper = Lapper::new(data.clone());
965        let mut insert_lapper = Lapper::new(vec![]);
966        for elem in data {
967            insert_lapper.insert(elem);
968        }
969        assert_eq!(new_lapper.starts, insert_lapper.starts);
970        assert_eq!(new_lapper.stops, insert_lapper.stops);
971        assert_eq!(new_lapper.intervals, insert_lapper.intervals);
972        assert_eq!(new_lapper.max_len, insert_lapper.max_len);
973    }
974
975    // Test that inserting data ends up with the same lapper (single)
976    #[test]
977    fn insert_equality_single() {
978        let data: Vec<Iv> = vec![Iv {
979            start: 10,
980            stop: 35,
981            val: 0,
982        }];
983        let new_lapper = Lapper::new(data.clone());
984        let mut insert_lapper = Lapper::new(vec![]);
985        for elem in data {
986            insert_lapper.insert(elem);
987        }
988        assert_eq!(new_lapper.starts, insert_lapper.starts);
989        assert_eq!(new_lapper.stops, insert_lapper.stops);
990        assert_eq!(new_lapper.intervals, insert_lapper.intervals);
991        assert_eq!(new_lapper.max_len, insert_lapper.max_len);
992    }
993
994    // Test that a query stop that hits an interval start returns no interval
995    #[test]
996    fn test_query_stop_interval_start() {
997        let lapper = setup_nonoverlapping();
998        let mut cursor = 0;
999        assert_eq!(None, lapper.find(15, 20).next());
1000        assert_eq!(None, lapper.seek(15, 20, &mut cursor).next());
1001        assert_eq!(lapper.find(15, 20).count(), lapper.count(15, 20));
1002    }
1003
1004    // Test that a query start that hits an interval end returns no interval
1005    #[test]
1006    fn test_query_start_interval_stop() {
1007        let lapper = setup_nonoverlapping();
1008        let mut cursor = 0;
1009        assert_eq!(None, lapper.find(30, 35).next());
1010        assert_eq!(None, lapper.seek(30, 35, &mut cursor).next());
1011        assert_eq!(lapper.find(30, 35).count(), lapper.count(30, 35));
1012    }
1013
1014    // Test that a query that overlaps the start of an interval returns that interval
1015    #[test]
1016    fn test_query_overlaps_interval_start() {
1017        let lapper = setup_nonoverlapping();
1018        let mut cursor = 0;
1019        let expected = Iv {
1020            start: 20,
1021            stop: 30,
1022            val: 0,
1023        };
1024        assert_eq!(Some(&expected), lapper.find(15, 25).next());
1025        assert_eq!(Some(&expected), lapper.seek(15, 25, &mut cursor).next());
1026        assert_eq!(lapper.find(15, 25).count(), lapper.count(15, 25));
1027    }
1028
1029    // Test that a query that overlaps the stop of an interval returns that interval
1030    #[test]
1031    fn test_query_overlaps_interval_stop() {
1032        let lapper = setup_nonoverlapping();
1033        let mut cursor = 0;
1034        let expected = Iv {
1035            start: 20,
1036            stop: 30,
1037            val: 0,
1038        };
1039        assert_eq!(Some(&expected), lapper.find(25, 35).next());
1040        assert_eq!(Some(&expected), lapper.seek(25, 35, &mut cursor).next());
1041        assert_eq!(lapper.find(25, 35).count(), lapper.count(25, 35));
1042    }
1043
1044    // Test that a query that is enveloped by interval returns interval
1045    #[test]
1046    fn test_interval_envelops_query() {
1047        let lapper = setup_nonoverlapping();
1048        let mut cursor = 0;
1049        let expected = Iv {
1050            start: 20,
1051            stop: 30,
1052            val: 0,
1053        };
1054        assert_eq!(Some(&expected), lapper.find(22, 27).next());
1055        assert_eq!(Some(&expected), lapper.seek(22, 27, &mut cursor).next());
1056        assert_eq!(lapper.find(22, 27).count(), lapper.count(22, 27));
1057    }
1058
1059    // Test that a query that envolops an interval returns that interval
1060    #[test]
1061    fn test_query_envolops_interval() {
1062        let lapper = setup_nonoverlapping();
1063        let mut cursor = 0;
1064        let expected = Iv {
1065            start: 20,
1066            stop: 30,
1067            val: 0,
1068        };
1069        assert_eq!(Some(&expected), lapper.find(15, 35).next());
1070        assert_eq!(Some(&expected), lapper.seek(15, 35, &mut cursor).next());
1071        assert_eq!(lapper.find(15, 35).count(), lapper.count(15, 35));
1072    }
1073
1074    #[test]
1075    fn test_overlapping_intervals() {
1076        let lapper = setup_overlapping();
1077        let mut cursor = 0;
1078        let e1 = Iv {
1079            start: 0,
1080            stop: 15,
1081            val: 0,
1082        };
1083        let e2 = Iv {
1084            start: 10,
1085            stop: 25,
1086            val: 0,
1087        };
1088        assert_eq!(vec![&e1, &e2], lapper.find(8, 20).collect::<Vec<&Iv>>());
1089        assert_eq!(
1090            vec![&e1, &e2],
1091            lapper.seek(8, 20, &mut cursor).collect::<Vec<&Iv>>()
1092        );
1093        assert_eq!(lapper.count(8, 20), 2);
1094    }
1095
1096    #[test]
1097    fn test_merge_overlaps() {
1098        let mut lapper = setup_badlapper();
1099        let expected: Vec<&Iv> = vec![
1100            &Iv{start: 10, stop: 16, val: 0},
1101            &Iv{start: 40, stop: 45, val: 0},
1102            &Iv{start: 50, stop: 55, val: 0},
1103            &Iv{start: 60, stop: 65, val: 0},
1104            &Iv{start: 68, stop: 120, val: 0}, // max_len = 50
1105        ];
1106        assert_eq!(lapper.intervals.len(), lapper.starts.len());
1107        lapper.merge_overlaps();
1108        assert_eq!(expected, lapper.iter().collect::<Vec<&Iv>>());
1109        assert_eq!(lapper.intervals.len(), lapper.starts.len())
1110
1111    }
1112
1113    // This test was added because this breakage was found in a library user's code, where after
1114    // calling merge_overlaps(), the find() call returned an empty iterator.
1115    #[test]
1116    fn test_merge_overlaps_find() {
1117        let data = vec![
1118                Iv{start: 2, stop: 3, val: 0},
1119                Iv{start: 3, stop: 4, val: 0},
1120                Iv{start: 4, stop: 6, val: 0},
1121                Iv{start: 6, stop: 7, val: 0},
1122                Iv{start: 7, stop: 8, val: 0},
1123        ];
1124        let mut lapper = Lapper::new(data);
1125
1126        let found = lapper.find(7, 9).collect::<Vec<&Interval<_,_>>>();
1127        assert_eq!(found, vec![
1128            &Iv{start:7, stop: 8, val: 0},
1129        ]);
1130
1131        // merge_overlaps should merge all intervals to one, which should be returned in the find call.
1132        lapper.merge_overlaps();
1133
1134        let found = lapper.find(7, 9).collect::<Vec<&Interval<_,_>>>();
1135        assert_eq!(found, vec![
1136            &Iv{start:2, stop: 8, val: 0},
1137        ]);
1138    }
1139
1140    #[test]
1141    fn test_lapper_cov() {
1142        let mut lapper = setup_badlapper();
1143        let before = lapper.cov();
1144        lapper.merge_overlaps();
1145        let after = lapper.cov();
1146        assert_eq!(before, after);
1147
1148        let mut lapper = setup_nonoverlapping();
1149        lapper.set_cov();
1150        assert_eq!(lapper.cov(), 50);
1151    }
1152
1153    #[test]
1154    fn test_interval_intersects() {
1155        let i1 = Iv{start: 70, stop: 120, val: 0}; // max_len = 50
1156        let i2 = Iv{start: 10, stop: 15, val: 0};
1157        let i3 = Iv{start: 10, stop: 15, val: 0}; // exact overlap
1158        let i4 = Iv{start: 12, stop: 15, val: 0}; // inner overlap
1159        let i5 = Iv{start: 14, stop: 16, val: 0}; // overlap end
1160        let i6 = Iv{start: 40, stop: 50, val: 0};
1161        let i7 = Iv{start: 50, stop: 55, val: 0};
1162        let i_8 = Iv{start: 60, stop: 65, val: 0};
1163        let i9 = Iv{start: 68, stop: 71, val: 0}; // overlap start
1164        let i10 = Iv{start: 70, stop: 75, val: 0};
1165
1166        assert_eq!(i2.intersect(&i3), 5); // exact match
1167        assert_eq!(i2.intersect(&i4), 3); // inner intersect
1168        assert_eq!(i2.intersect(&i5), 1); // end intersect
1169        assert_eq!(i9.intersect(&i10), 1); // start intersect
1170        assert_eq!(i7.intersect(&i_8), 0); // no intersect
1171        assert_eq!(i6.intersect(&i7), 0); // no intersect stop = start
1172        assert_eq!(i1.intersect(&i10), 5); // inner intersect at start
1173    }
1174
1175    #[test]
1176    fn test_union_and_intersect() {
1177        let data1: Vec<Iv> = vec![
1178            Iv{start: 70, stop: 120, val: 0}, // max_len = 50
1179            Iv{start: 10, stop: 15, val: 0}, // exact overlap
1180            Iv{start: 12, stop: 15, val: 0}, // inner overlap
1181            Iv{start: 14, stop: 16, val: 0}, // overlap end
1182            Iv{start: 68, stop: 71, val: 0}, // overlap start
1183        ];
1184        let data2: Vec<Iv> = vec![
1185
1186            Iv{start: 10, stop: 15, val: 0},
1187            Iv{start: 40, stop: 45, val: 0},
1188            Iv{start: 50, stop: 55, val: 0},
1189            Iv{start: 60, stop: 65, val: 0},
1190            Iv{start: 70, stop: 75, val: 0},
1191        ];
1192
1193        let (mut lapper1, mut lapper2) = (Lapper::new(data1), Lapper::new(data2)) ;
1194        // Should be the same either way it's calculated
1195        let (union, intersect) = lapper1.union_and_intersect(&lapper2);
1196        assert_eq!(intersect, 10);
1197        assert_eq!(union, 73);
1198        let (union, intersect) = lapper2.union_and_intersect(&lapper1);
1199        assert_eq!(intersect, 10);
1200        assert_eq!(union, 73);
1201        lapper1.merge_overlaps();
1202        lapper1.set_cov();
1203        lapper2.merge_overlaps();
1204        lapper2.set_cov();
1205
1206        // Should be the same either way it's calculated
1207        let (union, intersect) = lapper1.union_and_intersect(&lapper2);
1208        assert_eq!(intersect, 10);
1209        assert_eq!(union, 73);
1210        let (union, intersect) = lapper2.union_and_intersect(&lapper1);
1211        assert_eq!(intersect, 10);
1212        assert_eq!(union, 73);
1213    }
1214
1215    #[test]
1216    fn test_find_overlaps_in_large_intervals() {
1217        let data1: Vec<Iv> = vec![
1218            Iv{start: 0, stop: 8, val: 0},
1219            Iv{start: 1, stop: 10, val: 0},
1220            Iv{start: 2, stop: 5, val: 0},
1221            Iv{start: 3, stop: 8, val: 0},
1222            Iv{start: 4, stop: 7, val: 0},
1223            Iv{start: 5, stop: 8, val: 0},
1224            Iv{start: 8, stop: 8, val: 0},
1225            Iv{start: 9, stop: 11, val: 0},
1226            Iv{start: 10, stop: 13, val: 0},
1227            Iv{start: 100, stop: 200, val: 0},
1228            Iv{start: 110, stop: 120, val: 0},
1229            Iv{start: 110, stop: 124, val: 0},
1230            Iv{start: 111, stop: 160, val: 0},
1231            Iv{start: 150, stop: 200, val: 0},
1232        ];
1233        let lapper = Lapper::new(data1);
1234        let found = lapper.find(8, 11).collect::<Vec<&Iv>>();
1235        assert_eq!(found, vec![
1236            &Iv{start: 1, stop: 10, val: 0},
1237            &Iv{start: 9, stop: 11, val: 0},
1238            &Iv{start: 10, stop: 13, val: 0},
1239        ]);
1240        assert_eq!(lapper.count(8, 11), 3);
1241        let found = lapper.find(145, 151).collect::<Vec<&Iv>>();
1242        assert_eq!(found, vec![
1243            &Iv{start: 100, stop: 200, val: 0},
1244            &Iv{start: 111, stop: 160, val: 0},
1245            &Iv{start: 150, stop: 200, val: 0},
1246        ]);
1247
1248        assert_eq!(lapper.count(145, 151), 3);
1249    }
1250
1251    #[test]
1252    fn test_depth_sanity() {
1253        let data1: Vec<Iv> = vec![
1254            Iv{start: 0, stop: 10, val: 0},
1255            Iv{start: 5, stop: 10, val: 0}
1256        ];
1257        let lapper = Lapper::new(data1);
1258        let found = lapper.depth().collect::<Vec<Interval<usize, usize>>>();
1259        assert_eq!(found, vec![
1260                   Interval{start: 0, stop: 5, val: 1},
1261                   Interval{start: 5, stop: 10, val: 2}
1262        ]);
1263    }
1264
1265    #[test]
1266    fn test_depth_hard() {
1267        let data1: Vec<Iv> = vec![
1268            Iv{start: 1, stop: 10, val: 0},
1269            Iv{start: 2, stop: 5, val: 0},
1270            Iv{start: 3, stop: 8, val: 0},
1271            Iv{start: 3, stop: 8, val: 0},
1272            Iv{start: 3, stop: 8, val: 0},
1273            Iv{start: 5, stop: 8, val: 0},
1274            Iv{start: 9, stop: 11, val: 0},
1275        ];
1276        let lapper = Lapper::new(data1);
1277        let found = lapper.depth().collect::<Vec<Interval<usize, usize>>>();
1278        assert_eq!(found, vec![
1279                   Interval{start: 1, stop: 2, val: 1},
1280                   Interval{start: 2, stop: 3, val: 2},
1281                   Interval{start: 3, stop: 8, val: 5},
1282                   Interval{start: 8, stop: 9, val: 1},
1283                   Interval{start: 9, stop: 10, val: 2},
1284                   Interval{start: 10, stop: 11, val: 1},
1285        ]);
1286    }
1287    #[test]
1288    fn test_depth_harder() {
1289        let data1: Vec<Iv> = vec![
1290            Iv{start: 1, stop: 10, val: 0},
1291            Iv{start: 2, stop: 5, val: 0},
1292            Iv{start: 3, stop: 8, val: 0},
1293            Iv{start: 3, stop: 8, val: 0},
1294            Iv{start: 3, stop: 8, val: 0},
1295            Iv{start: 5, stop: 8, val: 0},
1296            Iv{start: 9, stop: 11, val: 0},
1297            Iv{start: 15, stop: 20, val: 0},
1298        ];
1299        let lapper = Lapper::new(data1);
1300        let found = lapper.depth().collect::<Vec<Interval<usize, usize>>>();
1301        assert_eq!(found, vec![
1302                   Interval{start: 1, stop: 2, val: 1},
1303                   Interval{start: 2, stop: 3, val: 2},
1304                   Interval{start: 3, stop: 8, val: 5},
1305                   Interval{start: 8, stop: 9, val: 1},
1306                   Interval{start: 9, stop: 10, val: 2},
1307                   Interval{start: 10, stop: 11, val: 1},
1308                   Interval{start: 15, stop: 20, val: 1},
1309        ]);
1310    }
1311    // BUG TESTS - these are tests that came from real life
1312
1313    // Test that it's not possible to induce index out of bounds by pushing the cursor past the end
1314    // of the lapper.
1315    #[test]
1316    fn test_seek_over_len() {
1317        let lapper = setup_nonoverlapping();
1318        let single = setup_single();
1319        let mut cursor: usize = 0;
1320
1321        for interval in lapper.iter() {
1322            for o_interval in single.seek(interval.start, interval.stop, &mut cursor) {
1323                println!("{:#?}", o_interval);
1324            }
1325        }
1326    }
1327
1328    // Test that if lower_bound puts us before the first match, we still return a match
1329    #[test]
1330    fn test_find_over_behind_first_match() {
1331        let lapper = setup_badlapper();
1332        let e1 = Iv {start: 50, stop: 55, val: 0};
1333        let found = lapper.find(50, 55).next();
1334        assert_eq!(found, Some(&e1));
1335        assert_eq!(lapper.find(50, 55).count(), lapper.count(50,55));
1336    }
1337
1338    // When there is a very long interval that spans many little intervals, test that the little
1339    // intevals still get returne properly
1340    #[test]
1341    fn test_bad_skips() {
1342        let data = vec![
1343            Iv{start:25264912, stop: 25264986, val: 0},
1344            Iv{start:27273024, stop: 27273065	, val: 0},
1345            Iv{start:27440273, stop: 27440318	, val: 0},
1346            Iv{start:27488033, stop: 27488125	, val: 0},
1347            Iv{start:27938410, stop: 27938470	, val: 0},
1348            Iv{start:27959118, stop: 27959171	, val: 0},
1349            Iv{start:28866309, stop: 33141404	, val: 0},
1350        ];
1351        let lapper = Lapper::new(data);
1352
1353        let found = lapper.find(28974798, 33141355).collect::<Vec<&Iv>>();
1354        assert_eq!(found, vec![
1355            &Iv{start:28866309, stop: 33141404	, val: 0},
1356        ]);
1357        assert_eq!(lapper.count(28974798, 33141355), 1);
1358    }
1359
1360    #[test]
1361    fn serde_test() {
1362        let data = vec![
1363            Iv{start:25264912, stop: 25264986, val: 0},
1364            Iv{start:27273024, stop: 27273065	, val: 0},
1365            Iv{start:27440273, stop: 27440318	, val: 0},
1366            Iv{start:27488033, stop: 27488125	, val: 0},
1367            Iv{start:27938410, stop: 27938470	, val: 0},
1368            Iv{start:27959118, stop: 27959171	, val: 0},
1369            Iv{start:28866309, stop: 33141404	, val: 0},
1370        ];
1371        let lapper = Lapper::new(data);
1372
1373        let serialized = bincode::serialize(&lapper).unwrap();
1374        let deserialzed: Lapper<usize, u32> = bincode::deserialize(&serialized).unwrap();
1375
1376        let found = deserialzed.find(28974798, 33141355).collect::<Vec<&Iv>>();
1377        assert_eq!(found, vec![
1378            &Iv{start:28866309, stop: 33141404	, val: 0},
1379        ]);
1380        assert_eq!(deserialzed.count(28974798, 33141355), 1);
1381    }
1382
1383}