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