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::ValueCarrier;
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    VC,
18    L: Iterator<Item = (RangeInclusive<T>, VC)>,
19    R: Iterator<Item = (RangeInclusive<T>, VC)>,
20> {
21    #[allow(clippy::type_complexity)]
22    iter: MergeBy<
23        SetPriorityMap<T, VC, L>,
24        SetPriorityMap<T, VC, R>,
25        fn(&Priority<T, VC>, &Priority<T, VC>) -> bool,
26    >,
27}
28
29impl<T, VC, L, R> MergeMap<T, VC, L, R>
30where
31    T: Integer,
32    VC: ValueCarrier,
33    L: SortedDisjointMap<T, VC>,
34    R: SortedDisjointMap<T, VC>,
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, VC, L, R> FusedIterator for MergeMap<T, VC, L, R>
47where
48    T: Integer,
49    VC: ValueCarrier,
50    L: SortedDisjointMap<T, VC>,
51    R: SortedDisjointMap<T, VC>,
52{
53}
54
55impl<T, VC, L, R> Iterator for MergeMap<T, VC, L, R>
56where
57    T: Integer,
58    VC: ValueCarrier,
59    L: SortedDisjointMap<T, VC>,
60    R: SortedDisjointMap<T, VC>,
61{
62    type Item = Priority<T, VC>;
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, VC, L, R> PrioritySortedStartsMap<T, VC> for MergeMap<T, VC, L, R>
74where
75    T: Integer,
76    VC: ValueCarrier,
77    L: SortedDisjointMap<T, VC>,
78    R: SortedDisjointMap<T, VC>,
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, VC, I>
87where
88    I: Iterator<Item = (RangeInclusive<T>, VC)>,
89{
90    #[allow(clippy::type_complexity)]
91    iter: KMergeBy<SetPriorityMap<T, VC, I>, fn(&Priority<T, VC>, &Priority<T, VC>) -> bool>,
92}
93
94type KMergeSetPriorityMap<T, VC, I> =
95    KMergeBy<SetPriorityMap<T, VC, I>, fn(&Priority<T, VC>, &Priority<T, VC>) -> bool>;
96
97impl<T, VC, I> KMergeMap<T, VC, I>
98where
99    T: Integer,
100    VC: ValueCarrier,
101    I: SortedDisjointMap<T, VC>,
102{
103    /// Creates a new [`KMergeMap`] iterator from zero or more [`SortedDisjointMap`] iterators. See [`KMergeMap`] for more details and examples.
104    ///
105    /// [`SortedDisjointMap`]: crate::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, VC, 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, VC, I> FusedIterator for KMergeMap<T, VC, I>
125where
126    T: Integer,
127    VC: ValueCarrier,
128    I: SortedDisjointMap<T, VC>,
129{
130}
131
132impl<T, VC, I> Iterator for KMergeMap<T, VC, I>
133where
134    T: Integer,
135    VC: ValueCarrier,
136    I: SortedDisjointMap<T, VC>,
137{
138    type Item = Priority<T, VC>;
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, VC, I> PrioritySortedStartsMap<T, VC> for KMergeMap<T, VC, I>
150where
151    T: Integer,
152    VC: ValueCarrier,
153    I: SortedDisjointMap<T, VC>,
154{
155}
range_set_blaze/merge_map.rs

range_set_blaze/
merge_map.rs
