newtype_tools/iter.rs
1#[cfg(test)]
2mod tests;
3
4/// Blanket `Step` implementation for all `Newtype`s.
5impl<T> Step for T
6where
7 T: crate::Newtype + Clone + From<T::Inner> + PartialOrd + MinMax,
8 T::Inner: Step,
9{
10 #[inline]
11 fn steps_between(start: &Self, end: &Self) -> (usize, Option<usize>) {
12 <T::Inner as Step>::steps_between(start.as_ref(), end.as_ref())
13 }
14
15 #[inline]
16 fn forward_checked(start: Self, count: usize) -> Option<Self> {
17 <T::Inner as Step>::forward_checked(start.as_ref().clone(), count).map(T::from)
18 }
19
20 #[inline]
21 fn backward_checked(start: Self, count: usize) -> Option<Self> {
22 <T::Inner as Step>::backward_checked(start.as_ref().clone(), count).map(Self::from)
23 }
24}
25
26/// Blanket `Iterator`` implementation for all `Newtype`s.
27#[derive(Clone)]
28pub struct Iterator<T>
29where
30 T: crate::Newtype,
31{
32 start: T::Inner,
33 last: T::Inner,
34}
35
36impl<T> Iterator<T>
37where
38 T: crate::Newtype,
39 T::Inner: Step,
40{
41 /// Returns `true` if the iterator is empty.
42 #[inline]
43 pub fn is_empty(&self) -> bool {
44 self.start > self.last
45 }
46
47 /// Creates a new `Iterator` instance based on the given range.
48 /// The internal `Newtype` representation must implement `Step` trait.
49 ///
50 /// # Example
51 /// ```
52 /// # #[cfg(feature = "derive")]
53 /// # {
54 /// #[derive(Debug, newtype_tools::Newtype, PartialEq)]
55 /// struct Apples(u64);
56 /// let range = Apples(1)..Apples(3);
57 /// let mut iter = newtype_tools::Iterator::from(&range);
58 /// assert_eq!(iter.len(), 2);
59 /// assert_eq!(iter.next(), Some(Apples(1)));
60 /// assert_eq!(iter.next(), Some(Apples(2)));
61 /// assert_eq!(iter.next(), None);
62 /// # }
63 /// ```
64 #[inline]
65 pub fn from<R: std::ops::RangeBounds<T>>(range: &R) -> Self {
66 use crate::iter::Step;
67 use std::ops::Bound;
68 let start = match range.start_bound() {
69 Bound::Included(s) => s.as_ref().clone(),
70 Bound::Excluded(s) => Step::forward(s.as_ref().clone(), 1),
71 Bound::Unbounded => T::Inner::MIN,
72 };
73 let last = match range.end_bound() {
74 Bound::Included(e) => e.as_ref().clone(),
75 Bound::Excluded(e) => Step::backward(e.as_ref().clone(), 1),
76 Bound::Unbounded => T::Inner::MAX,
77 };
78 Self { start, last }
79 }
80}
81
82impl<T> std::iter::Iterator for Iterator<T>
83where
84 T: crate::Newtype + From<T::Inner>,
85 T::Inner: Step + std::fmt::Debug,
86{
87 type Item = T;
88
89 #[inline]
90 fn next(&mut self) -> Option<Self::Item> {
91 if Iterator::is_empty(self) {
92 return None;
93 }
94
95 let next = crate::iter::Step::forward_checked(self.start.clone(), 1)?;
96 Some(T::from(core::mem::replace(&mut self.start, next)))
97 }
98
99 #[inline]
100 fn size_hint(&self) -> (usize, Option<usize>) {
101 if self.is_empty() {
102 return (0, Some(0));
103 }
104
105 println!(
106 "XXX getting steps between start:{:?} end:{:?}",
107 self.start, self.last
108 );
109 let hint = Step::steps_between(&self.start, &self.last);
110 println!("XXX hint:{hint:?}");
111 (
112 hint.0.saturating_add(1),
113 hint.1.and_then(|steps| steps.checked_add(1)),
114 )
115 }
116
117 #[inline]
118 fn count(self) -> usize {
119 if self.is_empty() {
120 return 0;
121 }
122
123 crate::iter::Step::steps_between(&self.start, &self.last)
124 .1
125 .and_then(|steps| steps.checked_add(1))
126 .expect("count overflowed usize")
127 }
128
129 #[inline]
130 fn is_sorted(self) -> bool {
131 true
132 }
133}
134
135impl<T> DoubleEndedIterator for Iterator<T>
136where
137 T: crate::Newtype + From<T::Inner>,
138 T::Inner: Step + std::fmt::Debug,
139{
140 fn next_back(&mut self) -> Option<Self::Item> {
141 if Iterator::is_empty(self) {
142 return None;
143 }
144 let next = crate::iter::Step::backward_checked(self.last.clone(), 1)?;
145 Some(T::from(core::mem::replace(&mut self.last, next)))
146 }
147}
148
149impl<T> ExactSizeIterator for Iterator<T>
150where
151 T: crate::Newtype + From<T::Inner>,
152 T::Inner: Step + std::fmt::Debug,
153{
154}
155
156impl<T> std::iter::FusedIterator for Iterator<T>
157where
158 T: crate::Newtype + From<T::Inner>,
159 T::Inner: Step + std::fmt::Debug,
160{
161}
162
163////////////////////////////////////////////////////////////////////////
164// The following complexity should go away once the `Step` trait is stable.
165// Mostly it's a copy-paste from the unstable `std::iter::Step` trait.
166
167/// A helper trait to support inner values ranges.
168pub trait MinMax {
169 const MIN: Self;
170 const MAX: Self;
171}
172
173macro_rules! impl_min_max {
174 ($($t:ty),*) => {
175 $(
176 impl MinMax for $t {
177 const MIN: Self = <$t>::MIN;
178 const MAX: Self = <$t>::MAX;
179 }
180 )+
181 };
182}
183
184impl_min_max!(
185 u8, u16, u32, u64, u128, i8, i16, i32, i64, i128, usize, isize
186);
187
188/// A copy of the unstable `std::iter::Step` trait required for the `iter`
189/// derive.
190pub trait Step: Clone + PartialOrd + MinMax + Sized {
191 /// Returns the bounds on the number of *successor* steps required to get from `start` to `end`
192 /// like [`Iterator::size_hint()`][Iterator::size_hint()].
193 ///
194 /// Returns `(usize::MAX, None)` if the number of steps would overflow `usize`, or is infinite.
195 ///
196 /// # Invariants
197 ///
198 /// For any `a`, `b`, and `n`:
199 ///
200 /// * `steps_between(&a, &b) == (n, Some(n))` if and only if `Step::forward_checked(&a, n) == Some(b)`
201 /// * `steps_between(&a, &b) == (n, Some(n))` if and only if `Step::backward_checked(&b, n) == Some(a)`
202 /// * `steps_between(&a, &b) == (n, Some(n))` only if `a <= b`
203 /// * Corollary: `steps_between(&a, &b) == (0, Some(0))` if and only if `a == b`
204 /// * `steps_between(&a, &b) == (0, None)` if `a > b`
205 fn steps_between(start: &Self, end: &Self) -> (usize, Option<usize>);
206
207 /// Returns the value that would be obtained by taking the *successor*
208 /// of `self` `count` times.
209 ///
210 /// If this would overflow the range of values supported by `Self`, returns `None`.
211 ///
212 /// # Invariants
213 ///
214 /// For any `a`, `n`, and `m`:
215 ///
216 /// * `Step::forward_checked(a, n).and_then(|x| Step::forward_checked(x, m)) == Step::forward_checked(a, m).and_then(|x| Step::forward_checked(x, n))`
217 /// * `Step::forward_checked(a, n).and_then(|x| Step::forward_checked(x, m)) == try { Step::forward_checked(a, n.checked_add(m)) }`
218 ///
219 /// For any `a` and `n`:
220 ///
221 /// * `Step::forward_checked(a, n) == (0..n).try_fold(a, |x, _| Step::forward_checked(&x, 1))`
222 /// * Corollary: `Step::forward_checked(a, 0) == Some(a)`
223 fn forward_checked(start: Self, count: usize) -> Option<Self>;
224
225 /// Returns the value that would be obtained by taking the *successor*
226 /// of `self` `count` times.
227 ///
228 /// If this would overflow the range of values supported by `Self`,
229 /// this function is allowed to panic, wrap, or saturate.
230 /// The suggested behavior is to panic when debug assertions are enabled,
231 /// and to wrap or saturate otherwise.
232 ///
233 /// # Invariants
234 ///
235 /// For any `a`, `n`, and `m`, where no overflow occurs:
236 ///
237 /// * `Step::forward(Step::forward(a, n), m) == Step::forward(a, n + m)`
238 ///
239 /// For any `a` and `n`, where no overflow occurs:
240 ///
241 /// * `Step::forward_checked(a, n) == Some(Step::forward(a, n))`
242 /// * `Step::forward(a, n) == (0..n).fold(a, |x, _| Step::forward(x, 1))`
243 /// * Corollary: `Step::forward(a, 0) == a`
244 /// * `Step::forward(a, n) >= a`
245 /// * `Step::backward(Step::forward(a, n), n) == a`
246 fn forward(start: Self, count: usize) -> Self {
247 Step::forward_checked(start, count).expect("overflow in `Step::forward`")
248 }
249
250 /// Returns the value that would be obtained by taking the *predecessor*
251 /// of `self` `count` times.
252 ///
253 /// If this would overflow the range of values supported by `Self`, returns `None`.
254 ///
255 /// # Invariants
256 ///
257 /// For any `a`, `n`, and `m`:
258 ///
259 /// * `Step::backward_checked(a, n).and_then(|x| Step::backward_checked(x, m)) == n.checked_add(m).and_then(|x| Step::backward_checked(a, x))`
260 /// * `Step::backward_checked(a, n).and_then(|x| Step::backward_checked(x, m)) == try { Step::backward_checked(a, n.checked_add(m)?) }`
261 ///
262 /// For any `a` and `n`:
263 ///
264 /// * `Step::backward_checked(a, n) == (0..n).try_fold(a, |x, _| Step::backward_checked(x, 1))`
265 /// * Corollary: `Step::backward_checked(a, 0) == Some(a)`
266 fn backward_checked(start: Self, count: usize) -> Option<Self>;
267
268 /// Returns the value that would be obtained by taking the *predecessor*
269 /// of `self` `count` times.
270 ///
271 /// If this would overflow the range of values supported by `Self`,
272 /// this function is allowed to panic, wrap, or saturate.
273 /// The suggested behavior is to panic when debug assertions are enabled,
274 /// and to wrap or saturate otherwise.
275 ///
276 /// # Invariants
277 ///
278 /// For any `a`, `n`, and `m`, where no overflow occurs:
279 ///
280 /// * `Step::backward(Step::backward(a, n), m) == Step::backward(a, n + m)`
281 ///
282 /// For any `a` and `n`, where no overflow occurs:
283 ///
284 /// * `Step::backward_checked(a, n) == Some(Step::backward(a, n))`
285 /// * `Step::backward(a, n) == (0..n).fold(a, |x, _| Step::backward(x, 1))`
286 /// * Corollary: `Step::backward(a, 0) == a`
287 /// * `Step::backward(a, n) <= a`
288 /// * `Step::forward(Step::backward(a, n), n) == a`
289 fn backward(start: Self, count: usize) -> Self {
290 Step::backward_checked(start, count).expect("overflow in `Step::backward`")
291 }
292}
293
294// These are still macro-generated because the integer literals resolve to different types.
295macro_rules! step_identical_methods {
296 () => {
297 #[inline]
298 #[allow(arithmetic_overflow)]
299 fn forward(start: Self, n: usize) -> Self {
300 // In debug builds, trigger a panic on overflow.
301 // This should optimize completely out in release builds.
302 if Self::forward_checked(start, n).is_none() {
303 let _ = Self::MAX + 1;
304 }
305 // Do wrapping math to allow e.g. `Step::forward(-128i8, 255)`.
306 start.wrapping_add(n as Self)
307 }
308
309 #[inline]
310 #[allow(arithmetic_overflow)]
311 fn backward(start: Self, n: usize) -> Self {
312 // In debug builds, trigger a panic on overflow.
313 // This should optimize completely out in release builds.
314 if Self::backward_checked(start, n).is_none() {
315 let _ = Self::MIN - 1;
316 }
317 // Do wrapping math to allow e.g. `Step::backward(127i8, 255)`.
318 start.wrapping_sub(n as Self)
319 }
320 };
321}
322
323macro_rules! step_integer_impls {
324 {
325 [ $( [ $u_narrower:ident $i_narrower:ident ] ),+ ] <= usize <
326 [ $( [ $u_wider:ident $i_wider:ident ] ),+ ]
327 } => {
328 $(
329 #[allow(unreachable_patterns)]
330 impl Step for $u_narrower {
331 step_identical_methods!();
332
333 #[inline]
334 fn steps_between(start: &Self, end: &Self) -> (usize, Option<usize>) {
335 if *start <= *end {
336 // This relies on $u_narrower <= usize
337 let steps = (*end - *start) as usize;
338 (steps, Some(steps))
339 } else {
340 (0, None)
341 }
342 }
343
344 #[inline]
345 fn forward_checked(start: Self, n: usize) -> Option<Self> {
346 match Self::try_from(n) {
347 Ok(n) => start.checked_add(n),
348 Err(_) => None, // if n is out of range, `unsigned_start + n` is too
349 }
350 }
351
352 #[inline]
353 fn backward_checked(start: Self, n: usize) -> Option<Self> {
354 match Self::try_from(n) {
355 Ok(n) => start.checked_sub(n),
356 Err(_) => None, // if n is out of range, `unsigned_start - n` is too
357 }
358 }
359 }
360
361 #[allow(unreachable_patterns)]
362 impl Step for $i_narrower {
363 step_identical_methods!();
364
365 #[inline]
366 fn steps_between(start: &Self, end: &Self) -> (usize, Option<usize>) {
367 if *start <= *end {
368 // This relies on $i_narrower <= usize
369 //
370 // Casting to isize extends the width but preserves the sign.
371 // Use wrapping_sub in isize space and cast to usize to compute
372 // the difference that might not fit inside the range of isize.
373 let steps = (*end as isize).wrapping_sub(*start as isize) as usize;
374 (steps, Some(steps))
375 } else {
376 (0, None)
377 }
378 }
379
380 #[inline]
381 fn forward_checked(start: Self, n: usize) -> Option<Self> {
382 match $u_narrower::try_from(n) {
383 Ok(n) => {
384 // Wrapping handles cases like
385 // `Step::forward(-120_i8, 200) == Some(80_i8)`,
386 // even though 200 is out of range for i8.
387 let wrapped = start.wrapping_add(n as Self);
388 if wrapped >= start {
389 Some(wrapped)
390 } else {
391 None // Addition overflowed
392 }
393 }
394 // If n is out of range of e.g. u8,
395 // then it is bigger than the entire range for i8 is wide
396 // so `any_i8 + n` necessarily overflows i8.
397 Err(_) => None,
398 }
399 }
400
401 #[inline]
402 fn backward_checked(start: Self, n: usize) -> Option<Self> {
403 match $u_narrower::try_from(n) {
404 Ok(n) => {
405 // Wrapping handles cases like
406 // `Step::forward(-120_i8, 200) == Some(80_i8)`,
407 // even though 200 is out of range for i8.
408 let wrapped = start.wrapping_sub(n as Self);
409 if wrapped <= start {
410 Some(wrapped)
411 } else {
412 None // Subtraction overflowed
413 }
414 }
415 // If n is out of range of e.g. u8,
416 // then it is bigger than the entire range for i8 is wide
417 // so `any_i8 - n` necessarily overflows i8.
418 Err(_) => None,
419 }
420 }
421 }
422 )+
423
424 $(
425 #[allow(unreachable_patterns)]
426 impl Step for $u_wider {
427 step_identical_methods!();
428
429 #[inline]
430 fn steps_between(start: &Self, end: &Self) -> (usize, Option<usize>) {
431 if *start <= *end {
432 if let Ok(steps) = usize::try_from(*end - *start) {
433 (steps, Some(steps))
434 } else {
435 (usize::MAX, None)
436 }
437 } else {
438 (0, None)
439 }
440 }
441
442 #[inline]
443 fn forward_checked(start: Self, n: usize) -> Option<Self> {
444 start.checked_add(n as Self)
445 }
446
447 #[inline]
448 fn backward_checked(start: Self, n: usize) -> Option<Self> {
449 start.checked_sub(n as Self)
450 }
451 }
452
453 #[allow(unreachable_patterns)]
454 impl Step for $i_wider {
455 step_identical_methods!();
456
457 #[inline]
458 fn steps_between(start: &Self, end: &Self) -> (usize, Option<usize>) {
459 if *start <= *end {
460 match end.checked_sub(*start) {
461 Some(result) => {
462 if let Ok(steps) = usize::try_from(result) {
463 (steps, Some(steps))
464 } else {
465 (usize::MAX, None)
466 }
467 }
468 // If the difference is too big for e.g. i128,
469 // it's also gonna be too big for usize with fewer bits.
470 None => (usize::MAX, None),
471 }
472 } else {
473 (0, None)
474 }
475 }
476
477 #[inline]
478 fn forward_checked(start: Self, n: usize) -> Option<Self> {
479 start.checked_add(n as Self)
480 }
481
482 #[inline]
483 fn backward_checked(start: Self, n: usize) -> Option<Self> {
484 start.checked_sub(n as Self)
485 }
486 }
487 )+
488 };
489}
490
491#[cfg(target_pointer_width = "64")]
492step_integer_impls! {
493 [ [u8 i8], [u16 i16], [u32 i32], [u64 i64], [usize isize] ] <= usize < [ [u128 i128] ]
494}
495
496#[cfg(target_pointer_width = "32")]
497step_integer_impls! {
498 [ [u8 i8], [u16 i16], [u32 i32], [usize isize] ] <= usize < [ [u64 i64], [u128 i128] ]
499}
500
501#[cfg(target_pointer_width = "16")]
502step_integer_impls! {
503 [ [u8 i8], [u16 i16], [usize isize] ] <= usize < [ [u32 i32], [u64 i64], [u128 i128] ]
504}