1use 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#[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#[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 pub intervals: Vec<Interval<I, T>>,
113 starts: Vec<I>,
115 stops: Vec<I>,
117 max_len: I,
119 cov: Option<I>,
121 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 #[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 #[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 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 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 #[inline]
269 pub fn len(&self) -> usize {
270 self.intervals.len()
271 }
272
273 #[inline]
281 pub fn is_empty(&self) -> bool {
282 self.intervals.is_empty()
283 }
284
285 #[inline]
295 pub fn cov(&self) -> I {
296 match self.cov {
297 None => self.calculate_coverage(),
298 Some(cov) => cov,
299 }
300 }
301
302 pub fn set_cov(&mut self) -> I {
305 let cov = self.calculate_coverage();
306 self.cov = Some(cov);
307 cov
308 }
309
310 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 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 cov = cov + (moving_interval.stop - moving_interval.start);
327 moving_interval.start = interval.start;
328 moving_interval.stop = interval.stop;
329 }
330 }
331 cov = cov + (moving_interval.stop - moving_interval.start);
333 cov
334 }
335
336 #[inline]
338 pub fn iter(&self) -> IterLapper<I, T> {
339 IterLapper {
340 inner: self,
341 pos: 0,
342 }
343 }
344
345 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.push_back(top);
361 } else {
362 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 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 #[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 #[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 #[inline]
524 pub fn intersect(&self, other: &Self) -> I {
525 self.union_and_intersect(other).1
526 }
527
528 #[inline]
530 pub fn union(&self, other: &Self) -> I {
531 self.union_and_intersect(other).0
532 }
533
534 #[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 #[inline]
584 pub fn count(&self, start: I, stop: I) -> usize {
585 let len = self.intervals.len();
586 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 #[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 #[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#[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 fn next(&mut self) -> Option<Self::Item> {
678 while self.off < self.inner.intervals.len() {
679 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#[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>, curr_merged_pos: I, curr_pos: usize, cursor: usize, end: usize, }
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(), })
756 }
757}
758pub 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}, Iv{start: 10, stop: 15, val: 0},
858 Iv{start: 10, stop: 15, val: 0}, Iv{start: 12, stop: 15, val: 0}, Iv{start: 14, stop: 16, val: 0}, 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}, 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]
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]
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]
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]
951 fn insert_equality_badlapper() {
952 let data: Vec<Iv> = vec![
953 Iv{start: 70, stop: 120, val: 0}, Iv{start: 10, stop: 15, val: 0},
955 Iv{start: 10, stop: 15, val: 0}, Iv{start: 12, stop: 15, val: 0}, Iv{start: 14, stop: 16, val: 0}, 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}, 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]
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]
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]
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]
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]
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]
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]
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}, ];
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 #[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 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}; let i2 = Iv{start: 10, stop: 15, val: 0};
1157 let i3 = Iv{start: 10, stop: 15, val: 0}; let i4 = Iv{start: 12, stop: 15, val: 0}; let i5 = Iv{start: 14, stop: 16, val: 0}; 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}; let i10 = Iv{start: 70, stop: 75, val: 0};
1165
1166 assert_eq!(i2.intersect(&i3), 5); assert_eq!(i2.intersect(&i4), 3); assert_eq!(i2.intersect(&i5), 1); assert_eq!(i9.intersect(&i10), 1); assert_eq!(i7.intersect(&i_8), 0); assert_eq!(i6.intersect(&i7), 0); assert_eq!(i1.intersect(&i10), 5); }
1174
1175 #[test]
1176 fn test_union_and_intersect() {
1177 let data1: Vec<Iv> = vec![
1178 Iv{start: 70, stop: 120, val: 0}, Iv{start: 10, stop: 15, val: 0}, Iv{start: 12, stop: 15, val: 0}, Iv{start: 14, stop: 16, val: 0}, Iv{start: 68, stop: 71, val: 0}, ];
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 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 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 #[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]
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 #[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}