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, 1)
164 fn replace_zero(&mut self) -> Self {
165 mem::replace(self, 0)
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, 1)
213 fn replace_zero(&mut self) -> Self {
214 mem::replace(self, 0)
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 let rev = self.step_by.is_negative();
408 if (rev && self.range.start >= self.range.end) ||
409 (!rev && self.range.start <= self.range.end)
411 match self.range.start.step(&self.step_by) {
413 Some(mem::replace(&mut self.range.start, n))
416 let last = self.range.start.replace_one();
417 self.range.end.replace_zero();
418 self.step_by.replace_one();
429 fn size_hint(&self) -> (usize, Option<usize>) {
430 match Step::steps_between(&self.range.start,
433 Some(hint) => (hint.saturating_add(1), hint.checked_add(1)),
439 #[unstable(feature = "fused", issue = "35602")]
440 impl<A: Step + Clone> FusedIterator for StepBy<A, ops::RangeInclusive<A>> {}
442 macro_rules! range_exact_iter_impl {
444 #[stable(feature = "rust1", since = "1.0.0")]
445 impl ExactSizeIterator for ops::Range<$t> { }
449 macro_rules! range_incl_exact_iter_impl {
451 #[unstable(feature = "inclusive_range",
452 reason = "recently added, follows RFC",
454 impl ExactSizeIterator for ops::RangeInclusive<$t> { }
458 macro_rules! range_trusted_len_impl {
460 #[unstable(feature = "trusted_len", issue = "37572")]
461 unsafe impl TrustedLen for ops::Range<$t> { }
465 macro_rules! range_incl_trusted_len_impl {
467 #[unstable(feature = "inclusive_range",
468 reason = "recently added, follows RFC",
470 unsafe impl TrustedLen for ops::RangeInclusive<$t> { }
474 #[stable(feature = "rust1", since = "1.0.0")]
475 impl<A: Step> Iterator for ops::Range<A> where
476 for<'a> &'a A: Add<&'a A, Output = A>
481 fn next(&mut self) -> Option<A> {
482 if self.start < self.end {
483 let mut n = self.start.add_one();
484 mem::swap(&mut n, &mut self.start);
492 fn size_hint(&self) -> (usize, Option<usize>) {
493 match Step::steps_between_by_one(&self.start, &self.end) {
494 Some(hint) => (hint, Some(hint)),
500 // These macros generate `ExactSizeIterator` impls for various range types.
501 // Range<{u,i}64> and RangeInclusive<{u,i}{32,64,size}> are excluded
502 // because they cannot guarantee having a length <= usize::MAX, which is
503 // required by ExactSizeIterator.
504 range_exact_iter_impl!(usize u8 u16 u32 isize i8 i16 i32);
505 range_incl_exact_iter_impl!(u8 u16 i8 i16);
507 // These macros generate `TrustedLen` impls.
509 // They need to guarantee that .size_hint() is either exact, or that
510 // the upper bound is None when it does not fit the type limits.
511 range_trusted_len_impl!(usize isize u8 i8 u16 i16 u32 i32 i64 u64);
512 range_incl_trusted_len_impl!(usize isize u8 i8 u16 i16 u32 i32 i64 u64);
514 #[stable(feature = "rust1", since = "1.0.0")]
515 impl<A: Step + Clone> DoubleEndedIterator for ops::Range<A> where
516 for<'a> &'a A: Add<&'a A, Output = A>,
517 for<'a> &'a A: Sub<&'a A, Output = A>
520 fn next_back(&mut self) -> Option<A> {
521 if self.start < self.end {
522 self.end = self.end.sub_one();
523 Some(self.end.clone())
530 #[unstable(feature = "fused", issue = "35602")]
531 impl<A> FusedIterator for ops::Range<A>
532 where A: Step, for<'a> &'a A: Add<&'a A, Output = A> {}
534 #[stable(feature = "rust1", since = "1.0.0")]
535 impl<A: Step> Iterator for ops::RangeFrom<A> where
536 for<'a> &'a A: Add<&'a A, Output = A>
541 fn next(&mut self) -> Option<A> {
542 let mut n = self.start.add_one();
543 mem::swap(&mut n, &mut self.start);
548 fn size_hint(&self) -> (usize, Option<usize>) {
553 #[unstable(feature = "fused", issue = "35602")]
554 impl<A> FusedIterator for ops::RangeFrom<A>
555 where A: Step, for<'a> &'a A: Add<&'a A, Output = A> {}
557 #[unstable(feature = "inclusive_range", reason = "recently added, follows RFC", issue = "28237")]
558 impl<A: Step> Iterator for ops::RangeInclusive<A> where
559 for<'a> &'a A: Add<&'a A, Output = A>
564 fn next(&mut self) -> Option<A> {
565 use cmp::Ordering::*;
567 match self.start.partial_cmp(&self.end) {
569 let n = self.start.add_one();
570 Some(mem::replace(&mut self.start, n))
573 let last = self.start.replace_one();
574 self.end.replace_zero();
582 fn size_hint(&self) -> (usize, Option<usize>) {
583 if !(self.start <= self.end) {
587 match Step::steps_between_by_one(&self.start, &self.end) {
588 Some(hint) => (hint.saturating_add(1), hint.checked_add(1)),
594 #[unstable(feature = "inclusive_range", reason = "recently added, follows RFC", issue = "28237")]
595 impl<A: Step> DoubleEndedIterator for ops::RangeInclusive<A> where
596 for<'a> &'a A: Add<&'a A, Output = A>,
597 for<'a> &'a A: Sub<&'a A, Output = A>
600 fn next_back(&mut self) -> Option<A> {
601 use cmp::Ordering::*;
603 match self.start.partial_cmp(&self.end) {
605 let n = self.end.sub_one();
606 Some(mem::replace(&mut self.end, n))
609 let last = self.end.replace_zero();
610 self.start.replace_one();
618 #[unstable(feature = "fused", issue = "35602")]
619 impl<A> FusedIterator for ops::RangeInclusive<A>
620 where A: Step, for<'a> &'a A: Add<&'a A, Output = A> {}