range_set_blaze/
merge_map.rs

1use core::iter::FusedIterator;
2use core::ops::RangeInclusive;
3
4use itertools::{Itertools, KMergeBy, MergeBy};
5
6use crate::Integer;
7use crate::map::ValueRef;
8use crate::range_values::SetPriorityMap;
9
10use crate::sorted_disjoint_map::{Priority, PrioritySortedStartsMap, SortedDisjointMap};
11
12/// Used internally by `UnionIterMap` and `SymDiffIterMap`.
13#[derive(Clone, Debug)]
14#[must_use = "iterators are lazy and do nothing unless consumed"]
15pub struct MergeMap<
16    T,
17    VR,
18    L: Iterator<Item = (RangeInclusive<T>, VR)>,
19    R: Iterator<Item = (RangeInclusive<T>, VR)>,
20> {
21    #[allow(clippy::type_complexity)]
22    iter: MergeBy<
23        SetPriorityMap<T, VR, L>,
24        SetPriorityMap<T, VR, R>,
25        fn(&Priority<T, VR>, &Priority<T, VR>) -> bool,
26    >,
27}
28
29impl<T, VR, L, R> MergeMap<T, VR, L, R>
30where
31    T: Integer,
32    VR: ValueRef,
33    L: SortedDisjointMap<T, VR>,
34    R: SortedDisjointMap<T, VR>,
35{
36    pub(crate) fn new(left: L, right: R) -> Self {
37        let left = SetPriorityMap::new(left, 0);
38        let right = SetPriorityMap::new(right, 1);
39        Self {
40            // We sort only by start -- priority is not used until later.
41            iter: left.merge_by(right, |a, b| a.start() < b.start()),
42        }
43    }
44}
45
46impl<T, VR, L, R> FusedIterator for MergeMap<T, VR, L, R>
47where
48    T: Integer,
49    VR: ValueRef,
50    L: SortedDisjointMap<T, VR>,
51    R: SortedDisjointMap<T, VR>,
52{
53}
54
55impl<T, VR, L, R> Iterator for MergeMap<T, VR, L, R>
56where
57    T: Integer,
58    VR: ValueRef,
59    L: SortedDisjointMap<T, VR>,
60    R: SortedDisjointMap<T, VR>,
61{
62    type Item = Priority<T, VR>;
63
64    fn next(&mut self) -> Option<Self::Item> {
65        self.iter.next()
66    }
67
68    fn size_hint(&self) -> (usize, Option<usize>) {
69        self.iter.size_hint()
70    }
71}
72
73impl<T, VR, L, R> PrioritySortedStartsMap<T, VR> for MergeMap<T, VR, L, R>
74where
75    T: Integer,
76    VR: ValueRef,
77    L: SortedDisjointMap<T, VR>,
78    R: SortedDisjointMap<T, VR>,
79{
80}
81
82/// Used internally by `UnionIterMap` and `SymDiffIterMap`.
83#[derive(Clone, Debug)]
84#[allow(clippy::module_name_repetitions)]
85#[must_use = "iterators are lazy and do nothing unless consumed"]
86pub struct KMergeMap<T, VR, I>
87where
88    I: Iterator<Item = (RangeInclusive<T>, VR)>,
89{
90    #[allow(clippy::type_complexity)]
91    iter: KMergeBy<SetPriorityMap<T, VR, I>, fn(&Priority<T, VR>, &Priority<T, VR>) -> bool>,
92}
93
94type KMergeSetPriorityMap<T, VR, I> =
95    KMergeBy<SetPriorityMap<T, VR, I>, fn(&Priority<T, VR>, &Priority<T, VR>) -> bool>;
96
97impl<T, VR, I> KMergeMap<T, VR, I>
98where
99    T: Integer,
100    VR: ValueRef,
101    I: SortedDisjointMap<T, VR>,
102{
103    /// Creates a new [`KMergeMap`] iterator from zero or more [`SortedDisjointMap`] iterators. See [`KMergeMap`] for more details and examples.
104    ///
105    /// [`SortedDisjointMap`]: trait.SortedDisjointMap.html#table-of-contents
106    pub(crate) fn new<K>(iter: K) -> Self
107    where
108        K: IntoIterator<Item = I>,
109    {
110        // Prioritize from right to left
111        let iter = iter.into_iter().enumerate().map(|(i, x)| {
112            let priority_number = i;
113            SetPriorityMap::new(x, priority_number)
114        });
115        // Merge RangeValues by start with ties broken by priority
116        let iter: KMergeSetPriorityMap<T, VR, I> = iter.kmerge_by(|a, b| {
117            // We sort only by start -- priority is not used until later.
118            a.start() < b.start()
119        });
120        Self { iter }
121    }
122}
123
124impl<T, VR, I> FusedIterator for KMergeMap<T, VR, I>
125where
126    T: Integer,
127    VR: ValueRef,
128    I: SortedDisjointMap<T, VR>,
129{
130}
131
132impl<T, VR, I> Iterator for KMergeMap<T, VR, I>
133where
134    T: Integer,
135    VR: ValueRef,
136    I: SortedDisjointMap<T, VR>,
137{
138    type Item = Priority<T, VR>;
139
140    fn next(&mut self) -> Option<Self::Item> {
141        self.iter.next()
142    }
143
144    fn size_hint(&self) -> (usize, Option<usize>) {
145        self.iter.size_hint()
146    }
147}
148
149impl<T, VR, I> PrioritySortedStartsMap<T, VR> for KMergeMap<T, VR, I>
150where
151    T: Integer,
152    VR: ValueRef,
153    I: SortedDisjointMap<T, VR>,
154{
155}
range_set_blaze/merge_map.rs

range_set_blaze/
merge_map.rs
