chronologic/iter/union.rs
1use std::iter::{Fuse, FusedIterator};
2use std::mem::swap;
3use crate::*;
4use crate::iter::*;
5
6/// # Time window union iterator
7pub trait TimeUnion<TW>: TimeConvexIterator
8{
9 type Output:TimeConvexIterator<TimePoint=Self::TimePoint>;
10 fn union(self, tw: TW) -> Self::Output;
11}
12
13
14impl<TW1,TW2> TimeUnion<TW2> for TW1
15 where
16 TW1: TimeConvexIterator,
17 TW2: TimeConvexIterator<TimePoint=TW1::TimePoint>
18{
19 type Output = IterUnion<Self,TW2>;
20
21 #[inline]
22 fn union(self, tw: TW2) -> Self::Output {
23 IterUnion::new(self, tw)
24 }
25}
26
27impl<TW:TimeConvexIterator> TimeUnion<TimeInterval<TW::TimePoint>> for TW
28{
29 type Output = IterUnion<Self,<TimeInterval<TW::TimePoint> as IntoIterator>::IntoIter>;
30
31 #[inline]
32 fn union(self, tw: TimeInterval<TW::TimePoint>) -> Self::Output {
33 IterUnion::new(self, tw.into_iter())
34 }
35}
36
37impl<TW:TimeConvexIterator> TimeUnion<&TimeInterval<TW::TimePoint>> for TW
38{
39 type Output = IterUnion<Self,<TimeInterval<TW::TimePoint> as IntoIterator>::IntoIter>;
40
41 #[inline]
42 fn union(self, tw: &TimeInterval<TW::TimePoint>) -> Self::Output {
43 IterUnion::new(self, tw.into_iter())
44 }
45}
46
47
48impl<TW:TimeConvexIterator> TimeUnion<TimeSet<TW::TimePoint>> for TW
49{
50 type Output = IterUnion<Self,<TimeSet<TW::TimePoint> as IntoIterator>::IntoIter>;
51
52 #[inline]
53 fn union(self, tw: TimeSet<TW::TimePoint>) -> Self::Output {
54 IterUnion::new(self, tw.into_iter())
55 }
56}
57
58impl<TW:TimeConvexIterator> TimeUnion<&TimeSet<TW::TimePoint>> for TW
59{
60 type Output = IterUnion<Self,<TimeSet<TW::TimePoint> as IntoIterator>::IntoIter>;
61
62 #[inline]
63 fn union(self, tw: &TimeSet<TW::TimePoint>) -> Self::Output {
64 // todo: suppress the clone function
65 IterUnion::new(self, tw.clone().into_iter())
66 }
67}
68
69
70
71#[derive(Copy,Clone,Debug)]
72enum UnionState {
73 Init, // computation didn’t start yet
74 WaitI, // I should be next, J is temporary
75 WaitJ, // J should be next, I is temporary
76 OnlyI, // I should be next, J is empty (only I remains)
77 OnlyJ, // J should be next, I is empty (only J remains)
78 End // nothing more to do
79}
80
81
82pub struct IterUnion<I,J>
83 where
84 I:TimeConvexIterator,
85 J:TimeConvexIterator<TimePoint=I::TimePoint>
86{
87 i: Fuse<I>, j: Fuse<J>, state: UnionState, tmp: TimeInterval<I::TimePoint>
88}
89
90impl<I,J> IterUnion<I,J>
91 where
92 I:TimeConvexIterator,
93 J:TimeConvexIterator<TimePoint=I::TimePoint>
94{
95 fn new(i:I, j:J) -> Self {
96 Self { i: i.fuse(), j: j.fuse(), state: UnionState::Init, tmp:TimeInterval::all() }
97 }
98}
99
100
101impl<I,J> Iterator for IterUnion<I,J>
102 where
103 I:TimeConvexIterator,
104 J:TimeConvexIterator<TimePoint=I::TimePoint>
105{
106 type Item = TimeInterval<I::TimePoint>;
107
108 fn next(&mut self) -> Option<Self::Item>
109 {
110 loop {
111 match self.state {
112 UnionState::Init => {
113 match (self.i.next(), self.j.next()) {
114 (None,None) => { self.state = UnionState::End; return None; }
115 (Some(i), None) => { self.state = UnionState::OnlyI; return Some(i); },
116 (None, Some(j)) => { self.state = UnionState::OnlyJ; return Some(j); },
117
118 (Some(i), Some(j)) if i.upper < j.lower.just_before() => {
119 // i: [------------------]
120 // j: [--------]
121 //=>tmp: [--------]
122 self.state = UnionState::WaitI;
123 self.tmp=j; return Some(i);
124 },
125
126 (Some(i), Some(j)) if j.upper < i.lower.just_before() => {
127 // i: [------------------]
128 // j: [--------]
129 //=>tmp: [------------------]
130 self.state = UnionState::WaitJ;
131 self.tmp=i; return Some(j);
132 },
133 (Some(i), Some(j)) if i.upper <= j.upper => {
134 // i: [------------------] or [-----------]
135 // j: [--------] or [----------------------]
136 //=>tmp: [---------------------] or [----------------------]
137 self.state = UnionState::WaitI;
138 self.tmp = TimeInterval { lower: i.lower.min(j.lower), upper: j.upper };
139 },
140 (Some(i), Some(j)) => {
141 // i: [------------------] or [----------------]
142 // j: [--------] or [------------------]
143 //=>tmp [------------------] or [----------------------]
144 self.state = UnionState::WaitJ;
145 self.tmp = TimeInterval { lower: i.lower.min(j.lower), upper: i.upper };
146 },
147 }
148 }
149 UnionState::WaitI => {
150 match self.i.next() {
151 None => {
152 /* end of the iterator over i...*/
153 self.state = UnionState::OnlyJ;
154 return Some(self.tmp);
155 },
156 Some(i) if i.upper < self.tmp.lower.just_before() => {
157 // i: [------------------]
158 // tmp: [--------]
159 //=>tmp: [--------]
160 return Some(i);
161 },
162 Some(mut i) if self.tmp.upper < i.lower.just_before() => {
163 // i: [------------------]
164 // tmp: [--------]
165 //=>tmp: [------------------]
166 self.state = UnionState::WaitJ;
167 swap(&mut self.tmp, &mut i);
168 return Some(i);
169 },
170 Some(i) if i.upper <= self.tmp.upper => {
171 // i: [------------------] or [-----------]
172 // tmp: [--------] or [----------------------]
173 //=>tmp: [---------------------] or [----------------------]
174 if self.tmp.lower > i.lower { self.tmp.lower = i.lower; }
175 },
176 Some(i) => {
177 // i: [------------------] or [----------------]
178 // tmp: [--------] or [------------------]
179 //=>tmp [------------------] or [----------------------]
180 self.state = UnionState::WaitJ;
181 if self.tmp.lower > i.lower { self.tmp.lower = i.lower; }
182 self.tmp.upper = i.upper;
183 },
184 }
185 }
186 UnionState::WaitJ => {
187 match self.j.next() {
188 None => {
189 /* end of the iterator over i...*/
190 self.state = UnionState::OnlyJ;
191 return Some(self.tmp);
192 },
193 Some(j) if j.upper < self.tmp.lower.just_before() => {
194 // tmp: [--------]
195 // j: [------------------]
196 //=>tmp: [--------]
197 return Some(j);
198 },
199 Some(mut j) if self.tmp.upper < j.lower.just_before() => {
200 // tmp: [--------]
201 // j: [------------------]
202 //=>tmp: [------------------]
203 self.state = UnionState::WaitI;
204 swap(&mut self.tmp, &mut j);
205 return Some(j);
206 },
207 Some(j) if j.upper <= self.tmp.upper => {
208 // tmp: [--------] or [----------------------]
209 // j: [------------------] or [-----------]
210 //=>tmp: [---------------------] or [----------------------]
211 if self.tmp.lower > j.lower { self.tmp.lower = j.lower; }
212 }
213 Some(j) => {
214 // tmp: [--------] or [------------------]
215 // j: [------------------] or [----------------]
216 //=>tmp [------------------] or [----------------------]
217 self.state = UnionState::WaitI;
218 if self.tmp.lower > j.lower { self.tmp.lower = j.lower; }
219 self.tmp.upper = j.upper;
220 }
221 }
222 }
223 UnionState::OnlyI => { return self.i.next(); }
224 UnionState::OnlyJ => { return self.j.next(); }
225 UnionState::End => { return None; }
226 }
227 }
228 }
229
230 fn size_hint(&self) -> (usize, Option<usize>)
231 {
232 match self.state {
233 UnionState::OnlyI => { self.i.size_hint() }
234 UnionState::OnlyJ => { self.j.size_hint() }
235 UnionState::End => { (0, Some(0)) }
236 _ => {
237 if let (_,Some(imax)) = self.i.size_hint() {
238 if let (_,Some(jmax)) = self.j.size_hint() {
239 return (0, Some(imax.saturating_add(jmax)));
240 }
241 }
242 (0, None)
243 }
244 }
245 }
246}
247
248impl<I,J> TimeConvexIterator for IterUnion<I,J>
249 where
250 I:TimeConvexIterator,
251 J:TimeConvexIterator<TimePoint=I::TimePoint>
252{
253 type TimePoint = I::TimePoint;
254}
255
256impl<I,J> FusedIterator for IterUnion<I,J>
257 where
258 I:TimeConvexIterator,
259 J:TimeConvexIterator<TimePoint=I::TimePoint> {}
260
261