Mon, 24 Oct 2022 09:41:43 +0300
Allow step closure of AlgIterators to indicate succesfull termination or failure.
0 | 1 | /// Iteration utilities; [stateful][StatefulIterator] and |
2 | /// [restartable][RestartableIterator] iterators. | |
3 | ||
4 | use crate::types::Integer; | |
5 | use std::marker::PhantomData; | |
6 | ||
7 | /// Trait for iterators that can be queried the current state without advancing. | |
8 | pub trait StatefulIterator : Iterator { | |
9 | /// Return current value of iterator. If the iterator has not yet started, | |
10 | /// `None` should be returned. | |
11 | fn current(&self) -> Option<Self::Item>; | |
12 | } | |
13 | ||
14 | /// Iterators that can be restarted and queried the current state without | |
15 | /// advancing to next state. | |
16 | pub trait RestartableIterator : StatefulIterator { | |
17 | /// Restart the iterator. Return the first item. | |
18 | fn restart(&mut self) -> Option<Self::Item>; | |
19 | } | |
20 | ||
21 | /// A variant of `std::iter::Map` that works for methods instead of closures, | |
22 | /// so can be returned from functions without `dyn`. | |
23 | /// Use [`Mappable::mapF`] to create this iterator. | |
24 | pub struct MapF<I,J> where I : Iterator { | |
25 | iter : I, | |
26 | func : fn(I::Item) -> J, | |
27 | } | |
28 | ||
29 | impl<I,J> Iterator for MapF<I,J> where I : Iterator { | |
30 | type Item = J; | |
31 | fn next(&mut self) -> Option<J> { | |
32 | self.iter.next().map(|item| (self.func)(item)) | |
33 | } | |
34 | } | |
35 | ||
36 | /// A variant of [`MapF`] with extra data for the function stored as a reference. | |
37 | /// See also [`MapZ`] and use [`Mappable::mapX`] to create this iteartor. | |
38 | pub struct MapX<'a,I,T,J> where I : Iterator { | |
39 | iter : I, | |
40 | data : &'a T, | |
41 | func : fn(&'a T, I::Item) -> J, | |
42 | } | |
43 | ||
44 | impl<'a,I,T,J> Iterator for MapX<'a,I,T,J> where I : Iterator { | |
45 | type Item = J; | |
46 | fn next(&mut self) -> Option<J> { | |
47 | self.iter.next().map(|item| (self.func)(self.data, item)) | |
48 | } | |
49 | } | |
50 | ||
51 | /// A variant of [`MapF`] and [`MapX`] with extra data for the function stored in the struct. | |
52 | /// Use [`Mappable::mapZ`] to create this iterator. | |
53 | pub struct MapZ<I,T,J> where I : Iterator { | |
54 | iter : I, | |
55 | data : T, | |
56 | func : fn(&T, I::Item) -> J, | |
57 | } | |
58 | ||
59 | impl<'a,I,T,J> Iterator for MapZ<I,T,J> where I : Iterator { | |
60 | type Item = J; | |
61 | fn next(&mut self) -> Option<J> { | |
62 | self.iter.next().map(|item| (self.func)(&self.data, item)) | |
63 | } | |
64 | } | |
65 | ||
66 | /// A variant of `std::iter::FilterMap` that works for methods instead of closures, | |
67 | /// so can be returned from functions without `dyn`. | |
68 | pub struct FilterMapX<'a,I,T,J> where I : Iterator { | |
69 | iter : I, | |
70 | data : &'a T, | |
71 | func : fn(&'a T, I::Item) -> Option<J>, | |
72 | } | |
73 | ||
74 | impl<'a,I,T,J> Iterator for FilterMapX<'a,I,T,J> where I : Iterator { | |
75 | type Item = J; | |
76 | fn next(&mut self) -> Option<J> { | |
77 | while let Some(item) = self.iter.next() { | |
78 | let v = (self.func)(self.data, item); | |
79 | if v.is_some() { | |
80 | return v | |
81 | } | |
82 | } | |
83 | None | |
84 | } | |
85 | } | |
86 | ||
87 | /// Helper for [`Mappable::filter_zip`]. | |
88 | pub struct FilterZip<I, J> | |
89 | where I : Iterator, | |
90 | J : Iterator<Item=bool> { | |
91 | iter : I, | |
92 | filter : J, | |
93 | } | |
94 | ||
95 | impl<I,J> Iterator for FilterZip<I, J> | |
96 | where I : Iterator, | |
97 | J : Iterator<Item=bool> { | |
98 | type Item = I::Item; | |
99 | #[inline] | |
100 | fn next(&mut self) -> Option<I::Item> { | |
101 | while let (v@Some(..), Some(filt)) = (self.iter.next(), self.filter.next()) { | |
102 | if filt { | |
103 | return v | |
104 | } | |
105 | } | |
106 | None | |
107 | } | |
108 | } | |
109 | ||
110 | /// This trait implements several mapping methods on iterators. | |
111 | pub trait Mappable : Iterator + Sized { | |
112 | /// Apply `func` to the output of the iterator. | |
113 | #[allow(non_snake_case)] | |
114 | fn mapF<J>(self, func : fn(Self::Item) -> J) -> MapF<Self,J>; | |
115 | /// Apply `func` to the output of the iterator, passing also `d` to it. | |
116 | #[allow(non_snake_case)] | |
117 | fn mapX<'a,T,J>(self, d : &'a T, func : fn(&'a T, Self::Item) -> J) -> MapX<'a,Self,T,J>; | |
118 | /// Apply `func` to the output of the iterator, passing also `d` to it. | |
119 | #[allow(non_snake_case)] | |
120 | fn mapZ<T,J>(self, d : T, func : fn(&T, Self::Item) -> J) -> MapZ<Self,T,J>; | |
121 | /// Apply `func` to the output of the iterator, filtering based on the result. | |
122 | /// The data `d` is passed to `func`. | |
123 | #[allow(non_snake_case)] | |
124 | fn filter_mapX<'a,T,J>(self, d : &'a T, func : fn(&'a T, Self::Item) -> Option<J>) -> FilterMapX<'a,Self,T,J>; | |
125 | ||
126 | /// Filter `self` based on another iterator `iter` with `bool` items. | |
127 | fn filter_zip<J>(self, filter : J) -> FilterZip<Self, J> where J : Iterator<Item=bool>; | |
128 | } | |
129 | ||
130 | impl<I> Mappable for I where I : Iterator + Sized { | |
131 | #[inline] | |
132 | fn mapF<J>(self, func : fn(Self::Item) -> J) -> MapF<Self,J> { | |
133 | MapF{ iter : self, func : func } | |
134 | } | |
135 | #[inline] | |
136 | fn mapX<'a,T,J>(self, d : &'a T, func : fn(&'a T, Self::Item) -> J) -> MapX<'a,Self,T,J> { | |
137 | MapX{ iter : self, data : d, func : func } | |
138 | } | |
139 | #[inline] | |
140 | fn mapZ<T,J>(self, d : T, func : fn(&T, Self::Item) -> J) -> MapZ<Self,T,J> { | |
141 | MapZ{ iter : self, data : d, func : func } | |
142 | } | |
143 | #[inline] | |
144 | fn filter_mapX<'a,T,J>(self, d : &'a T, func : fn(&'a T, Self::Item) -> Option<J>) | |
145 | -> FilterMapX<'a,Self,T,J> { | |
146 | FilterMapX{ iter : self, data : d, func : func } | |
147 | } | |
148 | ||
149 | #[inline] | |
150 | fn filter_zip<J>(self, filter : J) -> FilterZip<Self, J> | |
151 | where J : Iterator<Item=bool> { | |
152 | FilterZip{ iter : self, filter : filter } | |
153 | } | |
154 | } | |
155 | ||
156 | /* | |
157 | /// This is a helper struct returning iterators with a lifetime from trait functions. | |
158 | /// `T` will typically be `&'a Self` or some other reference that can only be | |
159 | /// specified in the trait function declaration without having to parametrise the entire | |
160 | /// trait with `'a`. The parameter `ImplData` is supposed to be a unique type that idenfiers | |
161 | /// the iterator for the implementation of the trait. Then `Iterator` is to be implemented | |
162 | /// for `ProxyIterator<T, ImplState>`. For example: | |
163 | /// TODO: not updated. | |
164 | /// ``` | |
165 | /// trait Test { | |
166 | /// type ImplData; | |
167 | /// fn returns_iterator<'a>(&'a self) -> ProxyIterator<&'a Self, Self::ImplData>; | |
168 | /// } | |
169 | /// struct MyIndex{ | |
170 | /// index : usize, | |
171 | /// } | |
172 | /// impl<const N : usize> Test for [f64; N] { | |
173 | /// type ImplData = MyIndex; | |
174 | /// fn returns_iterator<'a>(&'a self) -> ProxyIterator<&'a Self, MyIndex> { | |
175 | /// TraitIterator::new(self, MyIndex{ index : 0 }) | |
176 | /// } | |
177 | /// } | |
178 | /// impl<'a, const N : usize> Iterator for `TraitIterator<&'a [f64; N], MyIndex> { | |
179 | /// type Item = f64; | |
180 | /// fn next(&mut self) -> Option<f64> { | |
181 | /// if self.state.index < N { | |
182 | /// let v = self.data[self.state.index]; | |
183 | /// self.state.index += 1; | |
184 | /// Some(v) | |
185 | /// } else { | |
186 | /// None | |
187 | /// } | |
188 | /// } | |
189 | /// } | |
190 | /// ``` | |
191 | */ | |
192 | ||
193 | macro_rules! impl_trait_iterator { | |
194 | ($name:ident, $proxyname:ident, &'a $($mut:ident)?, $($itemref:tt)*) => { | |
195 | pub trait $name { | |
196 | type Item : 'static; | |
197 | type Data : ?Sized; | |
198 | fn next_with<'a>(&mut self, data : &'a $($mut)? Self::Data) -> Option<$($itemref)* Self::Item>; | |
199 | } | |
200 | ||
201 | pub struct $proxyname<'a, Impl> | |
202 | where Impl : $name { | |
203 | pub data : &'a $($mut)? Impl::Data, | |
204 | pub iter : Impl, | |
205 | } | |
206 | ||
207 | impl<'a, Impl> $proxyname<'a, Impl> | |
208 | where Impl : $name { | |
209 | #[inline] | |
210 | pub fn new(data : &'a $($mut)? Impl::Data, iter : Impl) -> $proxyname<'a, Impl> { | |
211 | $proxyname{ data : data, iter : iter} | |
212 | } | |
213 | } | |
214 | ||
215 | impl<'a, Impl> Iterator for $proxyname<'a, Impl> | |
216 | where Impl : $name { | |
217 | type Item = $($itemref)* Impl::Item; | |
218 | #[inline] | |
219 | fn next(&mut self) -> Option<Self::Item> { | |
220 | self.iter.next_with(self.data) | |
221 | } | |
222 | } | |
223 | } | |
224 | } | |
225 | ||
226 | impl_trait_iterator!(TraitIterator, ProxyIterator, &'a, ); | |
227 | impl_trait_iterator!(TraitIteratorRef, ProxyIteratorRef, &'a, &'a); | |
228 | // TODO: Lifetime errors. Probably due to potential overlapping mutable borrows. | |
229 | // So should use some unsafe pointer hacks or so. | |
230 | //impl_trait_iterator!(TraitIteratorMut, ProxyIteratorMut, &'a mut, &'a mut); | |
231 | ||
232 | /* | |
233 | pub struct FlattenTI<SI> | |
234 | where SI : TraitIterator, | |
235 | SI::Item : Iterator { | |
236 | iter_iter : SI, | |
237 | element_iter : Option<SI::Item>, | |
238 | } | |
239 | ||
240 | impl<SI> FlattenTI<SI> | |
241 | where SI : TraitIterator, | |
242 | SI::Item : Iterator { | |
243 | fn new(iter : SI) -> Self { | |
244 | FlattenTI{ iter_iter : iter, element_iter : None } | |
245 | } | |
246 | } | |
247 | ||
248 | impl<SI : TraitIterator> TraitIterator for FlattenTI<SI> | |
249 | where SI::Item : Iterator { | |
250 | type Item = <SI::Item as Iterator>::Item; | |
251 | type Data = SI::Data; | |
252 | ||
253 | fn next_with<'a>(&mut self, data : &'a $($mut)? SI::Data) -> Option<Self::Item> { | |
254 | loop { | |
255 | if let Some(ei) = self.element_iter { | |
256 | if let n @ Some(_) = ei.next() { | |
257 | return n | |
258 | } | |
259 | } else { | |
260 | self.element_iter = self.iter_iter.next_with(data); | |
261 | if let None = self.element_iter { | |
262 | return None | |
263 | } | |
264 | } | |
265 | } | |
266 | } | |
267 | } | |
268 | */ | |
269 | ||
270 | /* | |
271 | pub enum EitherIterator<T, L : Iterator<Item=T>, R : Iterator<Item=T>> { | |
272 | Left(L), | |
273 | Right(R) | |
274 | } | |
275 | ||
276 | impl<T, L : Iterator<Item=T>, R : Iterator<Item=T>> Iterator for EitherIterator<T, L, R> { | |
277 | type Item = T; | |
278 | #[inline] | |
279 | fn next(&mut self) -> Option<T> { | |
280 | match self { | |
281 | EitherIterator::Left(ref l) => { l.next() } | |
282 | EitherIterator::Right(ref r) => { r.next() } | |
283 | } | |
284 | } | |
285 | } | |
286 | */ | |
287 | ||
288 | /// A [`RestartableIterator`] over the range ´[start, end)`. | |
289 | #[derive(Clone,Copy,Debug)] | |
290 | pub struct RangeIter<T> { | |
291 | start : T, | |
292 | end : T, | |
293 | value : Option<T>, | |
294 | } | |
295 | ||
296 | pub trait StepNext : Ord + Copy { | |
297 | fn step_next(&self) -> Self; | |
298 | fn dist_to(&self, other : &Self) -> usize; | |
299 | } | |
300 | ||
301 | impl<T : Integer + Into<usize>> StepNext for T { | |
302 | #[inline] | |
303 | fn step_next(&self) -> Self { *self + Self::ONE } | |
304 | ||
305 | #[inline] | |
306 | fn dist_to(&self, other : &Self) -> usize { | |
307 | if *other >= *self { | |
308 | (*other - *self).into() | |
309 | } else { | |
310 | 0 | |
311 | } | |
312 | } | |
313 | } | |
314 | ||
315 | impl<T : StepNext> RangeIter<T> { | |
316 | /// Create a new [`RangeIter`]. | |
317 | pub fn new(start : T, end : T) -> Self { | |
318 | RangeIter{ start : start.min(end), end : end, value : None } | |
319 | } | |
320 | } | |
321 | ||
322 | impl<T : StepNext> Iterator for RangeIter<T> { | |
323 | type Item = T; | |
324 | ||
325 | #[inline] | |
326 | fn next(&mut self) -> Option<Self::Item> { | |
327 | match self.value { | |
328 | None => { | |
329 | if self.start < self.end { | |
330 | self.value = Some(self.start); | |
331 | self.value | |
332 | } else { | |
333 | None | |
334 | } | |
335 | } | |
336 | Some(v) => { | |
337 | let vn = v.step_next(); | |
338 | if vn < self.end { | |
339 | self.value = Some(vn); | |
340 | self.value | |
341 | } else { | |
342 | None | |
343 | } | |
344 | } | |
345 | } | |
346 | } | |
347 | } | |
348 | ||
349 | impl<T : StepNext> ExactSizeIterator for RangeIter<T> { | |
350 | #[inline] | |
351 | fn len(&self) -> usize { self.start.dist_to(&self.end) } | |
352 | } | |
353 | ||
354 | impl<T : StepNext> StatefulIterator for RangeIter<T> { | |
355 | #[inline] | |
356 | fn current(&self) -> Option<Self::Item> { | |
357 | self.value | |
358 | } | |
359 | } | |
360 | ||
361 | impl<T : StepNext> RestartableIterator for RangeIter<T> { | |
362 | fn restart(&mut self) -> Option<Self::Item> { | |
363 | if self.start < self.end { | |
364 | self.value = Some(self.start); | |
365 | self.value | |
366 | } else { | |
367 | None | |
368 | } | |
369 | } | |
370 | } | |
371 | ||
372 | ||
373 | pub struct RestartableIter<'a, T> { | |
374 | inner : RangeIter<*const T>, | |
375 | _phantom : PhantomData<&'a[T]> | |
376 | } | |
377 | ||
378 | impl<T> StepNext for *const T { | |
379 | #[inline] | |
380 | fn step_next(&self) -> Self { unsafe { self.add(1) } } | |
381 | ||
382 | #[inline] | |
383 | fn dist_to(&self, other : &Self) -> usize { | |
384 | unsafe { other.offset_from(*self).max(0) as usize } | |
385 | } | |
386 | } | |
387 | ||
388 | impl<'a, T : 'a> RestartableIter<'a, T> { | |
389 | fn map_result(result : Option<*const T>) -> Option<&'a T> { | |
390 | match result { | |
391 | None => { None } | |
392 | Some(ptr) => { Some(unsafe{ &*ptr }) } | |
393 | } | |
394 | } | |
395 | ||
396 | pub fn new(slice : &'a [T]) -> Self { | |
397 | let ptr_range = slice.as_ptr_range(); | |
398 | let inner = RangeIter::new(ptr_range.start, ptr_range.end); | |
399 | RestartableIter{ inner : inner, _phantom : PhantomData } | |
400 | } | |
401 | } | |
402 | ||
403 | impl<'a, T : 'a> Iterator for RestartableIter<'a, T> { | |
404 | type Item = &'a T; | |
405 | #[inline] | |
406 | fn next(&mut self) -> Option<&'a T> { | |
407 | Self::map_result(self.inner.next()) | |
408 | } | |
409 | } | |
410 | ||
411 | impl<'a, T : 'a> ExactSizeIterator for RestartableIter<'a, T> { | |
412 | #[inline] | |
413 | fn len(&self) -> usize { self.inner.len() } | |
414 | } | |
415 | ||
416 | impl<'a, T : 'a> StatefulIterator for RestartableIter<'a, T> { | |
417 | #[inline] | |
418 | fn current(&self) -> Option<Self::Item> { | |
419 | Self::map_result(self.inner.current()) | |
420 | } | |
421 | } | |
422 | ||
423 | impl<'a, T : 'a> RestartableIterator for RestartableIter<'a, T> { | |
424 | fn restart(&mut self) -> Option<Self::Item> { | |
425 | Self::map_result(self.inner.current()) | |
426 | } | |
427 | } | |
428 | ||
429 | pub struct RestartableCloned<I : Iterator> { | |
430 | inner : I, | |
431 | } | |
432 | ||
433 | impl<'a, T : Clone + 'a , I : Iterator<Item=&'a T>> RestartableCloned<I> { | |
434 | fn map_result(result : Option<I::Item>) -> Option<T> { | |
435 | match result { | |
436 | None => { None } | |
437 | Some(v) => { Some(v.clone()) } | |
438 | } | |
439 | } | |
440 | ||
441 | pub fn new(inner : I) -> Self { | |
442 | RestartableCloned{ inner : inner } | |
443 | } | |
444 | } | |
445 | ||
446 | impl<'a, T : Clone + 'a , I : Iterator<Item=&'a T>> Iterator | |
447 | for RestartableCloned<I> { | |
448 | type Item = T; | |
449 | fn next(&mut self) -> Option<Self::Item> { | |
450 | Self::map_result(self.inner.next()) | |
451 | } | |
452 | } | |
453 | ||
454 | impl<'a, T : Clone + 'a , I : ExactSizeIterator<Item=&'a T>> ExactSizeIterator | |
455 | for RestartableCloned<I> { | |
456 | fn len(&self) -> usize { | |
457 | self.inner.len() | |
458 | } | |
459 | } | |
460 | ||
461 | impl<'a, T : Clone + 'a , I : StatefulIterator<Item=&'a T>> StatefulIterator | |
462 | for RestartableCloned<I> { | |
463 | fn current(&self) -> Option<Self::Item> { | |
464 | Self::map_result(self.inner.current()) | |
465 | } | |
466 | } | |
467 | ||
468 | impl<'a, T : Clone + 'a , I : RestartableIterator<Item=&'a T>> RestartableIterator | |
469 | for RestartableCloned<I> { | |
470 | fn restart(&mut self) -> Option<Self::Item> { | |
471 | Self::map_result(self.inner.restart()) | |
472 | } | |
473 | } |