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: u128) => 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: A = 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: bool = 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: A = self.state.clone();
255 match self.state.checked_add(&self.step) {
256 Some(x: A) => 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: bool = 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: A = self.state.clone();
304 match self.state.checked_add(&self.step) {
305 Some(x: A) => 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: A = 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: A = 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}
701