num_iter/
lib.rs

1// Copyright 2013-2014 The Rust Project Developers. See the COPYRIGHT
2// file at the top-level directory of this distribution and at
3// http://rust-lang.org/COPYRIGHT.
4//
5// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
6// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
7// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
8// option. This file may not be copied, modified, or distributed
9// except according to those terms.
10
11//! External iterators for generic mathematics
12//!
13//! ## Compatibility
14//!
15//! The `num-iter` crate is tested for rustc 1.31 and greater.
16
17#![doc(html_root_url = "https://docs.rs/num-iter/0.1")]
18#![no_std]
19
20use core::ops::{Add, Bound, RangeBounds, Sub};
21use core::usize;
22use num_integer::Integer;
23use num_traits::{CheckedAdd, One, ToPrimitive, Zero};
24
25/// An iterator over the range [start, stop)
26#[derive(Clone)]
27pub struct Range<A> {
28    state: A,
29    stop: A,
30    one: A,
31}
32
33/// Returns an iterator over the given range [start, stop) (that is, starting
34/// at start (inclusive), and ending at stop (exclusive)).
35///
36/// # Example
37///
38/// ```rust
39/// let array = [0, 1, 2, 3, 4];
40///
41/// for i in num_iter::range(0, 5) {
42///     println!("{}", i);
43///     assert_eq!(i,  array[i]);
44/// }
45/// ```
46#[inline]
47pub fn range<A>(start: A, stop: A) -> Range<A>
48where
49    A: Add<A, Output = A> + PartialOrd + Clone + One,
50{
51    Range {
52        state: start,
53        stop,
54        one: One::one(),
55    }
56}
57
58#[inline]
59fn unsigned<T: ToPrimitive>(x: &T) -> Option<u128> {
60    match x.to_u128() {
61        Some(u) => Some(u),
62        None => Some(x.to_i128()? as u128),
63    }
64}
65
66impl<A> RangeBounds<A> for Range<A> {
67    fn start_bound(&self) -> Bound<&A> {
68        Bound::Included(&self.state)
69    }
70
71    fn end_bound(&self) -> Bound<&A> {
72        Bound::Excluded(&self.stop)
73    }
74}
75
76// FIXME: rust-lang/rust#10414: Unfortunate type bound
77impl<A> Iterator for Range<A>
78where
79    A: Add<A, Output = A> + PartialOrd + Clone + ToPrimitive,
80{
81    type Item = A;
82
83    #[inline]
84    fn next(&mut self) -> Option<A> {
85        if self.state < self.stop {
86            let result = self.state.clone();
87            self.state = self.state.clone() + self.one.clone();
88            Some(result)
89        } else {
90            None
91        }
92    }
93
94    #[inline]
95    fn size_hint(&self) -> (usize, Option<usize>) {
96        // Check for empty ranges first.
97        if self.state >= self.stop {
98            return (0, Some(0));
99        }
100
101        // Try to cast both ends to the largest unsigned primitive.
102        // Note that negative values will wrap to a large positive.
103        if let Some(a) = unsigned(&self.state) {
104            if let Some(b) = unsigned(&self.stop) {
105                // We've lost signs, but we already know state < stop, so
106                // a `wrapping_sub` will give the correct unsigned delta.
107                return match b.wrapping_sub(a).to_usize() {
108                    Some(len) => (len, Some(len)),
109                    None => (usize::MAX, None),
110                };
111            }
112        }
113
114        // Standard fallback for unbounded/unrepresentable bounds
115        (0, None)
116    }
117}
118
119/// `Integer` is required to ensure the range will be the same regardless of
120/// the direction it is consumed.
121impl<A> DoubleEndedIterator for Range<A>
122where
123    A: Integer + Clone + ToPrimitive,
124{
125    #[inline]
126    fn next_back(&mut self) -> Option<A> {
127        if self.stop > self.state {
128            self.stop.dec();
129            Some(self.stop.clone())
130        } else {
131            None
132        }
133    }
134}
135
136/// An iterator over the range [start, stop]
137#[derive(Clone)]
138pub struct RangeInclusive<A> {
139    range: Range<A>,
140    done: bool,
141}
142
143/// Return an iterator over the range [start, stop]
144#[inline]
145pub fn range_inclusive<A>(start: A, stop: A) -> RangeInclusive<A>
146where
147    A: Add<A, Output = A> + PartialOrd + Clone + One,
148{
149    RangeInclusive {
150        range: range(start, stop),
151        done: false,
152    }
153}
154
155impl<A> RangeBounds<A> for RangeInclusive<A> {
156    fn start_bound(&self) -> Bound<&A> {
157        Bound::Included(&self.range.state)
158    }
159
160    fn end_bound(&self) -> Bound<&A> {
161        Bound::Included(&self.range.stop)
162    }
163}
164
165impl<A> Iterator for RangeInclusive<A>
166where
167    A: Add<A, Output = A> + PartialOrd + Clone + ToPrimitive,
168{
169    type Item = A;
170
171    #[inline]
172    fn next(&mut self) -> Option<A> {
173        match self.range.next() {
174            Some(x) => Some(x),
175            None => {
176                if !self.done && self.range.state == self.range.stop {
177                    self.done = true;
178                    Some(self.range.stop.clone())
179                } else {
180                    None
181                }
182            }
183        }
184    }
185
186    #[inline]
187    fn size_hint(&self) -> (usize, Option<usize>) {
188        let (lo, hi) = self.range.size_hint();
189        if self.done {
190            (lo, hi)
191        } else {
192            let lo = lo.saturating_add(1);
193            let hi = match hi {
194                Some(x) => x.checked_add(1),
195                None => None,
196            };
197            (lo, hi)
198        }
199    }
200}
201
202impl<A> DoubleEndedIterator for RangeInclusive<A>
203where
204    A: Sub<A, Output = A> + Integer + Clone + ToPrimitive,
205{
206    #[inline]
207    fn next_back(&mut self) -> Option<A> {
208        if self.range.stop > self.range.state {
209            let result = self.range.stop.clone();
210            self.range.stop.dec();
211            Some(result)
212        } else if !self.done && self.range.state == self.range.stop {
213            self.done = true;
214            Some(self.range.stop.clone())
215        } else {
216            None
217        }
218    }
219}
220
221/// An iterator over the range [start, stop) by `step`. It handles overflow by stopping.
222#[derive(Clone)]
223pub struct RangeStep<A> {
224    state: A,
225    stop: A,
226    step: A,
227    rev: bool,
228}
229
230/// Return an iterator over the range [start, stop) by `step`. It handles overflow by stopping.
231#[inline]
232pub fn range_step<A>(start: A, stop: A, step: A) -> RangeStep<A>
233where
234    A: CheckedAdd + PartialOrd + Clone + Zero,
235{
236    let rev = step < Zero::zero();
237    RangeStep {
238        state: start,
239        stop,
240        step,
241        rev,
242    }
243}
244
245impl<A> Iterator for RangeStep<A>
246where
247    A: CheckedAdd + PartialOrd + Clone,
248{
249    type Item = A;
250
251    #[inline]
252    fn next(&mut self) -> Option<A> {
253        if (self.rev && self.state > self.stop) || (!self.rev && self.state < self.stop) {
254            let result = self.state.clone();
255            match self.state.checked_add(&self.step) {
256                Some(x) => self.state = x,
257                None => self.state = self.stop.clone(),
258            }
259            Some(result)
260        } else {
261            None
262        }
263    }
264}
265
266/// An iterator over the range [start, stop] by `step`. It handles overflow by stopping.
267#[derive(Clone)]
268pub struct RangeStepInclusive<A> {
269    state: A,
270    stop: A,
271    step: A,
272    rev: bool,
273    done: bool,
274}
275
276/// Return an iterator over the range [start, stop] by `step`. It handles overflow by stopping.
277#[inline]
278pub fn range_step_inclusive<A>(start: A, stop: A, step: A) -> RangeStepInclusive<A>
279where
280    A: CheckedAdd + PartialOrd + Clone + Zero,
281{
282    let rev = step < Zero::zero();
283    RangeStepInclusive {
284        state: start,
285        stop,
286        step,
287        rev,
288        done: false,
289    }
290}
291
292impl<A> Iterator for RangeStepInclusive<A>
293where
294    A: CheckedAdd + PartialOrd + Clone + PartialEq,
295{
296    type Item = A;
297
298    #[inline]
299    fn next(&mut self) -> Option<A> {
300        if !self.done
301            && ((self.rev && self.state >= self.stop) || (!self.rev && self.state <= self.stop))
302        {
303            let result = self.state.clone();
304            match self.state.checked_add(&self.step) {
305                Some(x) => self.state = x,
306                None => self.done = true,
307            }
308            Some(result)
309        } else {
310            None
311        }
312    }
313}
314
315/// An iterator over the infinite range starting at `start`
316#[derive(Clone)]
317pub struct RangeFrom<A> {
318    state: A,
319    one: A,
320}
321
322/// Return an iterator over the infinite range starting at `start` and continuing forever.
323///
324/// *Note*: Currently, the `Iterator` implementation is not checked for overflow.
325/// If you use a finite-sized integer type and the integer overflows,
326/// it might panic in debug mode or wrap around in release mode.
327/// **This behavior is not guaranteed and may change at any time.**
328#[inline]
329pub fn range_from<A>(start: A) -> RangeFrom<A>
330where
331    A: Add<A, Output = A> + Clone + One,
332{
333    RangeFrom {
334        state: start,
335        one: One::one(),
336    }
337}
338
339impl<A> RangeBounds<A> for RangeFrom<A> {
340    fn start_bound(&self) -> Bound<&A> {
341        Bound::Included(&self.state)
342    }
343
344    fn end_bound(&self) -> Bound<&A> {
345        Bound::Unbounded
346    }
347}
348
349impl<A> Iterator for RangeFrom<A>
350where
351    A: Add<A, Output = A> + Clone,
352{
353    type Item = A;
354
355    #[inline]
356    fn next(&mut self) -> Option<A> {
357        let result = self.state.clone();
358        self.state = self.state.clone() + self.one.clone();
359        Some(result)
360    }
361
362    #[inline]
363    fn size_hint(&self) -> (usize, Option<usize>) {
364        (usize::MAX, None)
365    }
366}
367
368/// An iterator over the infinite range starting at `start` by `step`
369#[derive(Clone)]
370pub struct RangeStepFrom<A> {
371    state: A,
372    step: A,
373}
374
375/// Return an iterator over the infinite range starting at `start` and continuing forever by `step`.
376///
377/// *Note*: Currently, the `Iterator` implementation is not checked for overflow.
378/// If you use a finite-sized integer type and the integer overflows,
379/// it might panic in debug mode or wrap around in release mode.
380/// **This behavior is not guaranteed and may change at any time.**
381#[inline]
382pub fn range_step_from<A>(start: A, step: A) -> RangeStepFrom<A>
383where
384    A: Add<A, Output = A> + Clone,
385{
386    RangeStepFrom { state: start, step }
387}
388
389impl<A> Iterator for RangeStepFrom<A>
390where
391    A: Add<A, Output = A> + Clone,
392{
393    type Item = A;
394
395    #[inline]
396    fn next(&mut self) -> Option<A> {
397        let result = self.state.clone();
398        self.state = self.state.clone() + self.step.clone();
399        Some(result)
400    }
401
402    #[inline]
403    fn size_hint(&self) -> (usize, Option<usize>) {
404        (usize::MAX, None)
405    }
406}
407
408#[cfg(test)]
409mod tests {
410    use core::cmp::Ordering;
411    use core::iter;
412    use core::ops::{Add, Mul};
413    use core::{isize, usize};
414    use num_traits::{One, ToPrimitive};
415
416    #[test]
417    fn test_range() {
418        /// A mock type to check Range when ToPrimitive returns None
419        struct Foo;
420
421        impl ToPrimitive for Foo {
422            fn to_i64(&self) -> Option<i64> {
423                None
424            }
425            fn to_u64(&self) -> Option<u64> {
426                None
427            }
428        }
429
430        impl Add<Foo> for Foo {
431            type Output = Foo;
432
433            fn add(self, _: Foo) -> Foo {
434                Foo
435            }
436        }
437
438        impl PartialEq for Foo {
439            fn eq(&self, _: &Foo) -> bool {
440                true
441            }
442        }
443
444        impl PartialOrd for Foo {
445            fn partial_cmp(&self, _: &Foo) -> Option<Ordering> {
446                None
447            }
448        }
449
450        impl Clone for Foo {
451            fn clone(&self) -> Foo {
452                Foo
453            }
454        }
455
456        impl Mul<Foo> for Foo {
457            type Output = Foo;
458
459            fn mul(self, _: Foo) -> Foo {
460                Foo
461            }
462        }
463
464        impl One for Foo {
465            fn one() -> Foo {
466                Foo
467            }
468        }
469
470        assert!(super::range(0, 5).eq([0, 1, 2, 3, 4].iter().cloned()));
471        assert!(super::range(-10, -1).eq([-10, -9, -8, -7, -6, -5, -4, -3, -2].iter().cloned()));
472        assert!(super::range(0, 5).rev().eq([4, 3, 2, 1, 0].iter().cloned()));
473        assert_eq!(super::range(200, -5).count(), 0);
474        assert_eq!(super::range(200, -5).rev().count(), 0);
475        assert_eq!(super::range(200, 200).count(), 0);
476        assert_eq!(super::range(200, 200).rev().count(), 0);
477
478        assert_eq!(super::range(0, 100).size_hint(), (100, Some(100)));
479        // this test is only meaningful when sizeof usize < sizeof u64
480        assert_eq!(
481            super::range(usize::MAX - 1, usize::MAX).size_hint(),
482            (1, Some(1))
483        );
484        assert_eq!(super::range(-10, -1).size_hint(), (9, Some(9)));
485        assert_eq!(
486            super::range(isize::MIN, isize::MAX).size_hint(),
487            (usize::MAX, Some(usize::MAX))
488        );
489    }
490
491    #[test]
492    fn test_range_128() {
493        use core::{i128, u128};
494
495        assert!(super::range(0i128, 5).eq([0, 1, 2, 3, 4].iter().cloned()));
496        assert!(super::range(-10i128, -1).eq([-10, -9, -8, -7, -6, -5, -4, -3, -2].iter().cloned()));
497        assert!(super::range(0u128, 5)
498            .rev()
499            .eq([4, 3, 2, 1, 0].iter().cloned()));
500
501        assert_eq!(
502            super::range(i128::MIN, i128::MIN + 1).size_hint(),
503            (1, Some(1))
504        );
505        assert_eq!(
506            super::range(i128::MAX - 1, i128::MAX).size_hint(),
507            (1, Some(1))
508        );
509        assert_eq!(
510            super::range(i128::MIN, i128::MAX).size_hint(),
511            (usize::MAX, None)
512        );
513
514        assert_eq!(
515            super::range(u128::MAX - 1, u128::MAX).size_hint(),
516            (1, Some(1))
517        );
518        assert_eq!(
519            super::range(0, usize::MAX as u128).size_hint(),
520            (usize::MAX, Some(usize::MAX))
521        );
522        assert_eq!(
523            super::range(0, usize::MAX as u128 + 1).size_hint(),
524            (usize::MAX, None)
525        );
526        assert_eq!(super::range(0, i128::MAX).size_hint(), (usize::MAX, None));
527    }
528
529    #[test]
530    fn test_range_inclusive() {
531        assert!(super::range_inclusive(0, 5).eq([0, 1, 2, 3, 4, 5].iter().cloned()));
532        assert!(super::range_inclusive(0, 5)
533            .rev()
534            .eq([5, 4, 3, 2, 1, 0].iter().cloned()));
535        assert_eq!(super::range_inclusive(200, -5).count(), 0);
536        assert_eq!(super::range_inclusive(200, -5).rev().count(), 0);
537        assert!(super::range_inclusive(200, 200).eq(iter::once(200)));
538        assert!(super::range_inclusive(200, 200).rev().eq(iter::once(200)));
539        assert_eq!(
540            super::range_inclusive(isize::MIN, isize::MAX - 1).size_hint(),
541            (usize::MAX, Some(usize::MAX))
542        );
543        assert_eq!(
544            super::range_inclusive(isize::MIN, isize::MAX).size_hint(),
545            (usize::MAX, None)
546        );
547    }
548
549    #[test]
550    fn test_range_inclusive_128() {
551        use core::i128;
552
553        assert!(super::range_inclusive(0u128, 5).eq([0, 1, 2, 3, 4, 5].iter().cloned()));
554        assert!(super::range_inclusive(0u128, 5)
555            .rev()
556            .eq([5, 4, 3, 2, 1, 0].iter().cloned()));
557        assert_eq!(super::range_inclusive(200i128, -5).count(), 0);
558        assert_eq!(super::range_inclusive(200i128, -5).rev().count(), 0);
559        assert!(super::range_inclusive(200u128, 200).eq(iter::once(200)));
560        assert!(super::range_inclusive(200u128, 200)
561            .rev()
562            .eq(iter::once(200)));
563        assert_eq!(
564            super::range_inclusive(isize::MIN as i128, isize::MAX as i128 - 1).size_hint(),
565            (usize::MAX, Some(usize::MAX))
566        );
567        assert_eq!(
568            super::range_inclusive(isize::MIN as i128, isize::MAX as i128).size_hint(),
569            (usize::MAX, None)
570        );
571        assert_eq!(
572            super::range_inclusive(isize::MIN as i128, isize::MAX as i128 + 1).size_hint(),
573            (usize::MAX, None)
574        );
575        assert_eq!(
576            super::range_inclusive(i128::MIN, i128::MAX).size_hint(),
577            (usize::MAX, None)
578        );
579    }
580
581    #[test]
582    fn test_range_step() {
583        assert!(super::range_step(0, 20, 5).eq([0, 5, 10, 15].iter().cloned()));
584        assert!(super::range_step(20, 0, -5).eq([20, 15, 10, 5].iter().cloned()));
585        assert!(super::range_step(20, 0, -6).eq([20, 14, 8, 2].iter().cloned()));
586        assert!(super::range_step(200u8, 255, 50).eq([200u8, 250].iter().cloned()));
587        assert!(super::range_step(200, -5, 1).eq(iter::empty()));
588        assert!(super::range_step(200, 200, 1).eq(iter::empty()));
589    }
590
591    #[test]
592    fn test_range_step_128() {
593        use core::u128::MAX as UMAX;
594
595        assert!(super::range_step(0u128, 20, 5).eq([0, 5, 10, 15].iter().cloned()));
596        assert!(super::range_step(20i128, 0, -5).eq([20, 15, 10, 5].iter().cloned()));
597        assert!(super::range_step(20i128, 0, -6).eq([20, 14, 8, 2].iter().cloned()));
598        assert!(super::range_step(UMAX - 55, UMAX, 50).eq([UMAX - 55, UMAX - 5].iter().cloned()));
599        assert!(super::range_step(200i128, -5, 1).eq(iter::empty()));
600        assert!(super::range_step(200i128, 200, 1).eq(iter::empty()));
601    }
602
603    #[test]
604    fn test_range_step_inclusive() {
605        assert!(super::range_step_inclusive(0, 20, 5).eq([0, 5, 10, 15, 20].iter().cloned()));
606        assert!(super::range_step_inclusive(20, 0, -5).eq([20, 15, 10, 5, 0].iter().cloned()));
607        assert!(super::range_step_inclusive(20, 0, -6).eq([20, 14, 8, 2].iter().cloned()));
608        assert!(super::range_step_inclusive(200u8, 255, 50).eq([200u8, 250].iter().cloned()));
609        assert!(super::range_step_inclusive(200, -5, 1).eq(iter::empty()));
610        assert!(super::range_step_inclusive(200, 200, 1).eq(iter::once(200)));
611    }
612
613    #[test]
614    fn test_range_step_inclusive_128() {
615        use core::u128::MAX as UMAX;
616
617        assert!(super::range_step_inclusive(0u128, 20, 5).eq([0, 5, 10, 15, 20].iter().cloned()));
618        assert!(super::range_step_inclusive(20i128, 0, -5).eq([20, 15, 10, 5, 0].iter().cloned()));
619        assert!(super::range_step_inclusive(20i128, 0, -6).eq([20, 14, 8, 2].iter().cloned()));
620        assert!(super::range_step_inclusive(UMAX - 55, UMAX, 50)
621            .eq([UMAX - 55, UMAX - 5].iter().cloned()));
622        assert!(super::range_step_inclusive(200i128, -5, 1).eq(iter::empty()));
623        assert!(super::range_step_inclusive(200i128, 200, 1).eq(iter::once(200)));
624    }
625
626    #[test]
627    fn test_range_from() {
628        assert!(super::range_from(10u8)
629            .take(5)
630            .eq([10, 11, 12, 13, 14].iter().cloned()));
631        assert_eq!(super::range_from(10u8).size_hint(), (usize::MAX, None));
632    }
633
634    #[test]
635    fn test_range_step_from() {
636        assert!(super::range_step_from(10u8, 2u8)
637            .take(5)
638            .eq([10, 12, 14, 16, 18].iter().cloned()));
639        assert_eq!(
640            super::range_step_from(10u8, 2u8).size_hint(),
641            (usize::MAX, None)
642        );
643
644        assert!(super::range_step_from(10u8, 1u8)
645            .take(5)
646            .eq([10, 11, 12, 13, 14].iter().cloned()));
647        assert_eq!(
648            super::range_step_from(10u8, 1u8).size_hint(),
649            (usize::MAX, None)
650        );
651
652        assert!(super::range_step_from(10u8, 0u8)
653            .take(5)
654            .eq([10, 10, 10, 10, 10].iter().cloned()));
655        assert_eq!(
656            super::range_step_from(10u8, 0u8).size_hint(),
657            (usize::MAX, None)
658        );
659
660        assert!(super::range_step_from(10i8, 2i8)
661            .take(5)
662            .eq([10, 12, 14, 16, 18].iter().cloned()));
663        assert_eq!(
664            super::range_step_from(10i8, 2i8).size_hint(),
665            (usize::MAX, None)
666        );
667
668        assert!(super::range_step_from(10i8, 1i8)
669            .take(5)
670            .eq([10, 11, 12, 13, 14].iter().cloned()));
671        assert_eq!(
672            super::range_step_from(10i8, 1i8).size_hint(),
673            (usize::MAX, None)
674        );
675
676        assert!(super::range_step_from(10i8, 0i8)
677            .take(5)
678            .eq([10, 10, 10, 10, 10].iter().cloned()));
679        assert_eq!(
680            super::range_step_from(10i8, 0i8).size_hint(),
681            (usize::MAX, None)
682        );
683
684        assert!(super::range_step_from(10i8, -1i8)
685            .take(5)
686            .eq([10, 9, 8, 7, 6].iter().cloned()));
687        assert_eq!(
688            super::range_step_from(10i8, -1i8).size_hint(),
689            (usize::MAX, None)
690        );
691
692        assert!(super::range_step_from(10i8, -2i8)
693            .take(5)
694            .eq([10, 8, 6, 4, 2].iter().cloned()));
695        assert_eq!(
696            super::range_step_from(10i8, -2i8).size_hint(),
697            (usize::MAX, None)
698        );
699    }
700}
num_iter/lib.rs

num_iter/
lib.rs
