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