1 // Copyright 2013-2016 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.
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.
12 use ops::{self, Add, Sub};
15 use super::{FusedIterator, TrustedLen};
17 /// Objects that can be stepped over in both directions.
19 /// The `steps_between` function provides a way to efficiently compare
20 /// two `Step` objects.
21 #[unstable(feature = "step_trait",
22 reason = "likely to be replaced by finer-grained traits",
24 pub trait Step: PartialOrd + Sized {
25 /// Steps `self` if possible.
26 fn step(&self, by: &Self) -> Option<Self>;
28 /// Returns the number of steps between two step objects. The count is
29 /// inclusive of `start` and exclusive of `end`.
31 /// Returns `None` if it is not possible to calculate `steps_between`
33 fn steps_between(start: &Self, end: &Self, by: &Self) -> Option<usize>;
35 /// Same as `steps_between`, but with a `by` of 1
36 fn steps_between_by_one(start: &Self, end: &Self) -> Option<usize>;
38 /// Tests whether this step is negative or not (going backwards)
39 fn is_negative(&self) -> bool;
41 /// Replaces this step with `1`, returning itself
42 fn replace_one(&mut self) -> Self;
44 /// Replaces this step with `0`, returning itself
45 fn replace_zero(&mut self) -> Self;
47 /// Adds one to this step, returning the result
48 fn add_one(&self) -> Self;
50 /// Subtracts one to this step, returning the result
51 fn sub_one(&self) -> Self;
54 macro_rules! step_impl_unsigned {
56 #[unstable(feature = "step_trait",
57 reason = "likely to be replaced by finer-grained traits",
61 fn step(&self, by: &$t) -> Option<$t> {
62 (*self).checked_add(*by)
65 #[allow(trivial_numeric_casts)]
66 fn steps_between(start: &$t, end: &$t, by: &$t) -> Option<usize> {
67 if *by == 0 { return None; }
69 // Note: We assume $t <= usize here
70 let diff = (*end - *start) as usize;
71 let by = *by as usize;
83 fn is_negative(&self) -> bool {
88 fn replace_one(&mut self) -> Self {
93 fn replace_zero(&mut self) -> Self {
98 fn add_one(&self) -> Self {
103 fn sub_one(&self) -> Self {
108 fn steps_between_by_one(start: &Self, end: &Self) -> Option<usize> {
109 Self::steps_between(start, end, &1)
114 macro_rules! step_impl_signed {
116 #[unstable(feature = "step_trait",
117 reason = "likely to be replaced by finer-grained traits",
121 fn step(&self, by: &$t) -> Option<$t> {
122 (*self).checked_add(*by)
125 #[allow(trivial_numeric_casts)]
126 fn steps_between(start: &$t, end: &$t, by: &$t) -> Option<usize> {
127 if *by == 0 { return None; }
134 // Note: We assume $t <= isize here
135 // Use .wrapping_sub and cast to usize to compute the
136 // difference that may not fit inside the range of isize.
137 diff = (*end as isize).wrapping_sub(*start as isize) as usize;
143 diff = (*start as isize).wrapping_sub(*end as isize) as usize;
144 by_u = (*by as isize).wrapping_mul(-1) as usize;
147 Some(diff / by_u + 1)
154 fn is_negative(&self) -> bool {
159 fn replace_one(&mut self) -> Self {
160 mem::replace(self, 0)
164 fn replace_zero(&mut self) -> Self {
165 mem::replace(self, 1)
169 fn add_one(&self) -> Self {
174 fn sub_one(&self) -> Self {
179 fn steps_between_by_one(start: &Self, end: &Self) -> Option<usize> {
180 Self::steps_between(start, end, &1)
186 macro_rules! step_impl_no_between {
188 #[unstable(feature = "step_trait",
189 reason = "likely to be replaced by finer-grained traits",
193 fn step(&self, by: &$t) -> Option<$t> {
194 (*self).checked_add(*by)
197 fn steps_between(_a: &$t, _b: &$t, _by: &$t) -> Option<usize> {
202 #[allow(unused_comparisons)]
203 fn is_negative(&self) -> bool {
208 fn replace_one(&mut self) -> Self {
209 mem::replace(self, 0)
213 fn replace_zero(&mut self) -> Self {
214 mem::replace(self, 1)
218 fn add_one(&self) -> Self {
223 fn sub_one(&self) -> Self {
228 fn steps_between_by_one(start: &Self, end: &Self) -> Option<usize> {
229 Self::steps_between(start, end, &1)
235 step_impl_unsigned!(usize u8 u16 u32);
236 step_impl_signed!(isize i8 i16 i32);
237 #[cfg(target_pointer_width = "64")]
238 step_impl_unsigned!(u64);
239 #[cfg(target_pointer_width = "64")]
240 step_impl_signed!(i64);
241 // If the target pointer width is not 64-bits, we
242 // assume here that it is less than 64-bits.
243 #[cfg(not(target_pointer_width = "64"))]
244 step_impl_no_between!(u64 i64);
245 step_impl_no_between!(u128 i128);
247 /// An adapter for stepping range iterators by a custom amount.
249 /// The resulting iterator handles overflow by stopping. The `A`
250 /// parameter is the type being iterated over, while `R` is the range
251 /// type (usually one of `std::ops::{Range, RangeFrom, RangeInclusive}`.
252 #[derive(Clone, Debug)]
253 #[unstable(feature = "step_by", reason = "recent addition",
255 pub struct StepBy<A, R> {
260 impl<A: Step> ops::RangeFrom<A> {
261 /// Creates an iterator starting at the same point, but stepping by
262 /// the given amount at each iteration.
267 /// #![feature(step_by)]
269 /// let result: Vec<_> = (0..).step_by(2).take(5).collect();
270 /// assert_eq!(result, vec![0, 2, 4, 6, 8]);
273 #[unstable(feature = "step_by", reason = "recent addition",
275 pub fn step_by(self, by: A) -> StepBy<A, Self> {
283 impl<A: Step> ops::Range<A> {
284 /// Creates an iterator with the same range, but stepping by the
285 /// given amount at each iteration.
287 /// The resulting iterator handles overflow by stopping.
292 /// #![feature(step_by)]
294 /// let result: Vec<_> = (0..10).step_by(2).collect();
295 /// assert_eq!(result, vec![0, 2, 4, 6, 8]);
298 #[unstable(feature = "step_by", reason = "recent addition",
300 pub fn step_by(self, by: A) -> StepBy<A, Self> {
308 impl<A: Step> ops::RangeInclusive<A> {
309 /// Creates an iterator with the same range, but stepping by the
310 /// given amount at each iteration.
312 /// The resulting iterator handles overflow by stopping.
317 /// #![feature(step_by, inclusive_range_syntax)]
319 /// let result: Vec<_> = (0...10).step_by(2).collect();
320 /// assert_eq!(result, vec![0, 2, 4, 6, 8, 10]);
322 #[unstable(feature = "step_by", reason = "recent addition",
324 pub fn step_by(self, by: A) -> StepBy<A, Self> {
332 #[unstable(feature = "step_by", reason = "recent addition",
334 impl<A> Iterator for StepBy<A, ops::RangeFrom<A>> where
336 for<'a> &'a A: Add<&'a A, Output = A>
341 fn next(&mut self) -> Option<A> {
342 let mut n = &self.range.start + &self.step_by;
343 mem::swap(&mut n, &mut self.range.start);
348 fn size_hint(&self) -> (usize, Option<usize>) {
349 (usize::MAX, None) // Too bad we can't specify an infinite lower bound
353 #[unstable(feature = "fused", issue = "35602")]
354 impl<A> FusedIterator for StepBy<A, ops::RangeFrom<A>>
355 where A: Clone, for<'a> &'a A: Add<&'a A, Output = A> {}
357 #[unstable(feature = "step_by", reason = "recent addition",
359 impl<A: Step + Clone> Iterator for StepBy<A, ops::Range<A>> {
363 fn next(&mut self) -> Option<A> {
364 let rev = self.step_by.is_negative();
365 if (rev && self.range.start > self.range.end) ||
366 (!rev && self.range.start < self.range.end)
368 match self.range.start.step(&self.step_by) {
370 mem::swap(&mut self.range.start, &mut n);
374 let mut n = self.range.end.clone();
375 mem::swap(&mut self.range.start, &mut n);
385 fn size_hint(&self) -> (usize, Option<usize>) {
386 match Step::steps_between(&self.range.start,
389 Some(hint) => (hint, Some(hint)),
395 #[unstable(feature = "fused", issue = "35602")]
396 impl<A: Step + Clone> FusedIterator for StepBy<A, ops::Range<A>> {}
398 #[unstable(feature = "inclusive_range",
399 reason = "recently added, follows RFC",
401 impl<A: Step + Clone> Iterator for StepBy<A, ops::RangeInclusive<A>> {
405 fn next(&mut self) -> Option<A> {
406 use ops::RangeInclusive::*;
408 // this function has a sort of odd structure due to borrowck issues
409 // we may need to replace self.range, so borrows of start and end need to end early
411 let (finishing, n) = match self.range {
412 Empty { .. } => return None, // empty iterators yield no values
414 NonEmpty { ref mut start, ref mut end } => {
415 let rev = self.step_by.is_negative();
417 // march start towards (maybe past!) end and yield the old value
418 if (rev && start >= end) ||
419 (!rev && start <= end)
421 match start.step(&self.step_by) {
423 mem::swap(start, &mut n);
424 (None, Some(n)) // yield old value, remain non-empty
427 let mut n = end.clone();
428 mem::swap(start, &mut n);
429 (None, Some(n)) // yield old value, remain non-empty
433 // found range in inconsistent state (start at or past end), so become empty
434 (Some(end.replace_zero()), None)
439 // turn into an empty iterator if we've reached the end
440 if let Some(end) = finishing {
441 self.range = Empty { at: end };
448 fn size_hint(&self) -> (usize, Option<usize>) {
449 use ops::RangeInclusive::*;
452 Empty { .. } => (0, Some(0)),
454 NonEmpty { ref start, ref end } =>
455 match Step::steps_between(start,
458 Some(hint) => (hint.saturating_add(1), hint.checked_add(1)),
465 #[unstable(feature = "fused", issue = "35602")]
466 impl<A: Step + Clone> FusedIterator for StepBy<A, ops::RangeInclusive<A>> {}
468 macro_rules! range_exact_iter_impl {
470 #[stable(feature = "rust1", since = "1.0.0")]
471 impl ExactSizeIterator for ops::Range<$t> { }
475 macro_rules! range_incl_exact_iter_impl {
477 #[unstable(feature = "inclusive_range",
478 reason = "recently added, follows RFC",
480 impl ExactSizeIterator for ops::RangeInclusive<$t> { }
484 macro_rules! range_trusted_len_impl {
486 #[unstable(feature = "trusted_len", issue = "37572")]
487 unsafe impl TrustedLen for ops::Range<$t> { }
491 macro_rules! range_incl_trusted_len_impl {
493 #[unstable(feature = "inclusive_range",
494 reason = "recently added, follows RFC",
496 unsafe impl TrustedLen for ops::RangeInclusive<$t> { }
500 #[stable(feature = "rust1", since = "1.0.0")]
501 impl<A: Step> Iterator for ops::Range<A> where
502 for<'a> &'a A: Add<&'a A, Output = A>
507 fn next(&mut self) -> Option<A> {
508 if self.start < self.end {
509 let mut n = self.start.add_one();
510 mem::swap(&mut n, &mut self.start);
518 fn size_hint(&self) -> (usize, Option<usize>) {
519 match Step::steps_between_by_one(&self.start, &self.end) {
520 Some(hint) => (hint, Some(hint)),
526 // These macros generate `ExactSizeIterator` impls for various range types.
527 // Range<{u,i}64> and RangeInclusive<{u,i}{32,64,size}> are excluded
528 // because they cannot guarantee having a length <= usize::MAX, which is
529 // required by ExactSizeIterator.
530 range_exact_iter_impl!(usize u8 u16 u32 isize i8 i16 i32);
531 range_incl_exact_iter_impl!(u8 u16 i8 i16);
533 // These macros generate `TrustedLen` impls.
535 // They need to guarantee that .size_hint() is either exact, or that
536 // the upper bound is None when it does not fit the type limits.
537 range_trusted_len_impl!(usize isize u8 i8 u16 i16 u32 i32 i64 u64);
538 range_incl_trusted_len_impl!(usize isize u8 i8 u16 i16 u32 i32 i64 u64);
540 #[stable(feature = "rust1", since = "1.0.0")]
541 impl<A: Step + Clone> DoubleEndedIterator for ops::Range<A> where
542 for<'a> &'a A: Add<&'a A, Output = A>,
543 for<'a> &'a A: Sub<&'a A, Output = A>
546 fn next_back(&mut self) -> Option<A> {
547 if self.start < self.end {
548 self.end = self.end.sub_one();
549 Some(self.end.clone())
556 #[unstable(feature = "fused", issue = "35602")]
557 impl<A> FusedIterator for ops::Range<A>
558 where A: Step, for<'a> &'a A: Add<&'a A, Output = A> {}
560 #[stable(feature = "rust1", since = "1.0.0")]
561 impl<A: Step> Iterator for ops::RangeFrom<A> where
562 for<'a> &'a A: Add<&'a A, Output = A>
567 fn next(&mut self) -> Option<A> {
568 let mut n = self.start.add_one();
569 mem::swap(&mut n, &mut self.start);
574 #[unstable(feature = "fused", issue = "35602")]
575 impl<A> FusedIterator for ops::RangeFrom<A>
576 where A: Step, for<'a> &'a A: Add<&'a A, Output = A> {}
578 #[unstable(feature = "inclusive_range", reason = "recently added, follows RFC", issue = "28237")]
579 impl<A: Step> Iterator for ops::RangeInclusive<A> where
580 for<'a> &'a A: Add<&'a A, Output = A>
585 fn next(&mut self) -> Option<A> {
586 use ops::RangeInclusive::*;
588 // this function has a sort of odd structure due to borrowck issues
589 // we may need to replace self, so borrows of self.start and self.end need to end early
591 let (finishing, n) = match *self {
592 Empty { .. } => (None, None), // empty iterators yield no values
594 NonEmpty { ref mut start, ref mut end } => {
596 (Some(end.replace_one()), Some(start.replace_one()))
597 } else if start < end {
598 let mut n = start.add_one();
599 mem::swap(&mut n, start);
601 // if the iterator is done iterating, it will change from
602 // NonEmpty to Empty to avoid unnecessary drops or clones,
603 // we'll reuse either start or end (they are equal now, so
604 // it doesn't matter which) to pull out end, we need to swap
607 (if n == *end { Some(end.replace_one()) } else { None },
608 // ^ are we done yet?
609 Some(n)) // < the value to output
611 (Some(start.replace_one()), None)
616 // turn into an empty iterator if this is the last value
617 if let Some(end) = finishing {
618 *self = Empty { at: end };
625 fn size_hint(&self) -> (usize, Option<usize>) {
626 use ops::RangeInclusive::*;
629 Empty { .. } => (0, Some(0)),
631 NonEmpty { ref start, ref end } =>
632 match Step::steps_between_by_one(start, end) {
633 Some(hint) => (hint.saturating_add(1), hint.checked_add(1)),
640 #[unstable(feature = "inclusive_range", reason = "recently added, follows RFC", issue = "28237")]
641 impl<A: Step> DoubleEndedIterator for ops::RangeInclusive<A> where
642 for<'a> &'a A: Add<&'a A, Output = A>,
643 for<'a> &'a A: Sub<&'a A, Output = A>
646 fn next_back(&mut self) -> Option<A> {
647 use ops::RangeInclusive::*;
649 // see Iterator::next for comments
651 let (finishing, n) = match *self {
652 Empty { .. } => return None,
654 NonEmpty { ref mut start, ref mut end } => {
656 (Some(start.replace_one()), Some(end.replace_one()))
657 } else if start < end {
658 let mut n = end.sub_one();
659 mem::swap(&mut n, end);
661 (if n == *start { Some(start.replace_one()) } else { None },
664 (Some(end.replace_one()), None)
669 if let Some(start) = finishing {
670 *self = Empty { at: start };
677 #[unstable(feature = "fused", issue = "35602")]
678 impl<A> FusedIterator for ops::RangeInclusive<A>
679 where A: Step, for<'a> &'a A: Add<&'a A, Output = A> {}