num_iter/
lib.rs

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

num_iter/
lib.rs
