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; break None }
115 (Some(i), None) => { self.state = UnionState::OnlyI; break Some(i) },
116 (None, Some(j)) => { self.state = UnionState::OnlyJ; break 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;
124 break Some(i)
125 },
126
127 (Some(i), Some(j)) if j.upper < i.lower.just_before() => {
128 // i: [------------------]
129 // j: [--------]
130 //=>tmp: [------------------]
131 self.state = UnionState::WaitJ;
132 self.tmp=i;
133 break Some(j)
134 },
135 (Some(i), Some(j)) if i.upper <= j.upper => {
136 // i: [------------------] or [-----------]
137 // j: [--------] or [----------------------]
138 //=>tmp: [---------------------] or [----------------------]
139 self.state = UnionState::WaitI;
140 self.tmp = TimeInterval { lower: i.lower.min(j.lower), upper: j.upper };
141 },
142 (Some(i), Some(j)) => {
143 // i: [------------------] or [----------------]
144 // j: [--------] or [------------------]
145 //=>tmp [------------------] or [----------------------]
146 self.state = UnionState::WaitJ;
147 self.tmp = TimeInterval { lower: i.lower.min(j.lower), upper: i.upper };
148 },
149 }
150 }
151 UnionState::WaitI => {
152 match self.i.next() {
153 None => {
154 /* end of the iterator over i...*/
155 self.state = UnionState::OnlyJ;
156 break Some(self.tmp)
157 },
158 Some(i) if i.upper < self.tmp.lower.just_before() => {
159 // i: [------------------]
160 // tmp: [--------]
161 //=>tmp: [--------]
162 break Some(i)
163 },
164 Some(mut i) if self.tmp.upper < i.lower.just_before() => {
165 // i: [------------------]
166 // tmp: [--------]
167 //=>tmp: [------------------]
168 self.state = UnionState::WaitJ;
169 swap(&mut self.tmp, &mut i);
170 break Some(i)
171 },
172 Some(i) if i.upper <= self.tmp.upper => {
173 // i: [------------------] or [-----------]
174 // tmp: [--------] or [----------------------]
175 //=>tmp: [---------------------] or [----------------------]
176 if self.tmp.lower > i.lower { self.tmp.lower = i.lower; }
177 },
178 Some(i) => {
179 // i: [------------------] or [----------------]
180 // tmp: [--------] or [------------------]
181 //=>tmp [------------------] or [----------------------]
182 self.state = UnionState::WaitJ;
183 if self.tmp.lower > i.lower { self.tmp.lower = i.lower; }
184 self.tmp.upper = i.upper;
185 },
186 }
187 }
188 UnionState::WaitJ => {
189 match self.j.next() {
190 None => {
191 /* end of the iterator over j...*/
192 self.state = UnionState::OnlyI;
193 break Some(self.tmp)
194 },
195 Some(j) if j.upper < self.tmp.lower.just_before() => {
196 // tmp: [--------]
197 // j: [------------------]
198 //=>tmp: [--------]
199 break Some(j)
200 },
201 Some(mut j) if self.tmp.upper < j.lower.just_before() => {
202 // tmp: [--------]
203 // j: [------------------]
204 //=>tmp: [------------------]
205 self.state = UnionState::WaitI;
206 swap(&mut self.tmp, &mut j);
207 break Some(j)
208 },
209 Some(j) if j.upper <= self.tmp.upper => {
210 // tmp: [--------] or [----------------------]
211 // j: [------------------] or [-----------]
212 //=>tmp: [---------------------] or [----------------------]
213 if self.tmp.lower > j.lower { self.tmp.lower = j.lower; }
214 }
215 Some(j) => {
216 // tmp: [--------] or [------------------]
217 // j: [------------------] or [----------------]
218 //=>tmp [------------------] or [----------------------]
219 self.state = UnionState::WaitI;
220 if self.tmp.lower > j.lower { self.tmp.lower = j.lower; }
221 self.tmp.upper = j.upper;
222 }
223 }
224 }
225 UnionState::OnlyI => { break self.i.next() }
226 UnionState::OnlyJ => { break self.j.next() }
227 UnionState::End => { break None }
228 }
229 }
230 }
231
232 fn size_hint(&self) -> (usize, Option<usize>)
233 {
234 match self.state {
235 UnionState::OnlyI => { self.i.size_hint() }
236 UnionState::OnlyJ => { self.j.size_hint() }
237 UnionState::End => { (0, Some(0)) }
238 _ => {
239 if let (_,Some(imax)) = self.i.size_hint() {
240 if let (_,Some(jmax)) = self.j.size_hint() {
241 return (0, Some(imax.saturating_add(jmax)));
242 }
243 }
244 (0, None)
245 }
246 }
247 }
248}
249
250impl<I,J> TimeConvexIterator for IterUnion<I,J>
251 where
252 I:TimeConvexIterator,
253 J:TimeConvexIterator<TimePoint=I::TimePoint>
254{
255 type TimePoint = I::TimePoint;
256}
257
258impl<I,J> FusedIterator for IterUnion<I,J>
259 where
260 I:TimeConvexIterator,
261 J:TimeConvexIterator<TimePoint=I::TimePoint> {}
262
263