range_set_blaze/
merge_map.rs

1use core::iter::FusedIterator;
2
3use itertools::{Itertools, KMergeBy, MergeBy};
4
5use crate::Integer;
6use crate::map::ValueRef;
7use crate::range_values::SetPriorityMap;
8
9use crate::sorted_disjoint_map::{Priority, PrioritySortedStartsMap, SortedDisjointMap};
10
11/// Used internally by `UnionIterMap` and `SymDiffIterMap`.
12#[derive(Clone, Debug)]
13#[must_use = "iterators are lazy and do nothing unless consumed"]
14pub struct MergeMap<T, VR, L, R>
15where
16    T: Integer,
17    VR: ValueRef,
18    L: SortedDisjointMap<T, VR>,
19    R: SortedDisjointMap<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    T: Integer,
89    VR: ValueRef,
90    I: SortedDisjointMap<T, VR>,
91{
92    #[allow(clippy::type_complexity)]
93    iter: KMergeBy<SetPriorityMap<T, VR, I>, fn(&Priority<T, VR>, &Priority<T, VR>) -> bool>,
94}
95
96type KMergeSetPriorityMap<T, VR, I> =
97    KMergeBy<SetPriorityMap<T, VR, I>, fn(&Priority<T, VR>, &Priority<T, VR>) -> bool>;
98
99impl<T, VR, I> KMergeMap<T, VR, I>
100where
101    T: Integer,
102    VR: ValueRef,
103    I: SortedDisjointMap<T, VR>,
104{
105    /// Creates a new [`KMergeMap`] iterator from zero or more [`SortedDisjointMap`] iterators. See [`KMergeMap`] for more details and examples.
106    ///
107    /// [`SortedDisjointMap`]: trait.SortedDisjointMap.html#table-of-contents
108    pub(crate) fn new<K>(iter: K) -> Self
109    where
110        K: IntoIterator<Item = I>,
111    {
112        // Prioritize from right to left
113        let iter = iter.into_iter().enumerate().map(|(i, x)| {
114            let priority_number =  i;
115            SetPriorityMap::new(x, priority_number)
116        });
117        // Merge RangeValues by start with ties broken by priority
118        let iter: KMergeSetPriorityMap<T, VR, I> = iter.kmerge_by(|a, b| {
119            // We sort only by start -- priority is not used until later.
120            a.start() < b.start()
121        });
122        Self { iter }
123    }
124}
125
126impl<T, VR, I> FusedIterator for KMergeMap<T, VR, I>
127where
128    T: Integer,
129    VR: ValueRef,
130    I: SortedDisjointMap<T, VR>,
131{
132}
133
134impl<T, VR, I> Iterator for KMergeMap<T, VR, I>
135where
136    T: Integer,
137    VR: ValueRef,
138    I: SortedDisjointMap<T, VR>,
139{
140    type Item = Priority<T, VR>;
141
142    fn next(&mut self) -> Option<Self::Item> {
143        self.iter.next()
144    }
145
146    fn size_hint(&self) -> (usize, Option<usize>) {
147        self.iter.size_hint()
148    }
149}
150
151impl<T, VR, I> PrioritySortedStartsMap<T, VR> for KMergeMap<T, VR, I>
152where
153    T: Integer,
154    VR: ValueRef,
155    I: SortedDisjointMap<T, VR>,
156{
157}
range_set_blaze/merge_map.rs

range_set_blaze/
merge_map.rs
