src/libcore/iter/range.rs - third_party/rust - Git at Google

 // Copyright 2013-2016 The Rust Project Developers. See the COPYRIGHT
 // file at the top-level directory of this distribution and at
 // http://rust-lang.org/COPYRIGHT.
 //
 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.

 use clone::Clone;
 use cmp::PartialOrd;
 use mem;
 use ops::{self, Add, Sub};
 use option::Option::{self, Some, None};
 use marker::Sized;
 use usize;

 use super::{DoubleEndedIterator, ExactSizeIterator, Iterator};

 /// Objects that can be stepped over in both directions.
 ///
 /// The `steps_between` function provides a way to efficiently compare
 /// two `Step` objects.
 #[unstable(feature = "step_trait",
            reason = "likely to be replaced by finer-grained traits",
            issue = "27741")]
 pub trait Step: PartialOrd + Sized {
     /// Steps `self` if possible.
     fn step(&self, by: &Self) -> Option<Self>;

     /// Returns the number of steps between two step objects. The count is
     /// inclusive of `start` and exclusive of `end`.
     ///
     /// Returns `None` if it is not possible to calculate `steps_between`
     /// without overflow.
     fn steps_between(start: &Self, end: &Self, by: &Self) -> Option<usize>;

     /// Same as `steps_between`, but with a `by` of 1
     fn steps_between_by_one(start: &Self, end: &Self) -> Option<usize>;

     /// Tests whether this step is negative or not (going backwards)
     fn is_negative(&self) -> bool;

     /// Replaces this step with `1`, returning itself
     fn replace_one(&mut self) -> Self;

     /// Replaces this step with `0`, returning itself
     fn replace_zero(&mut self) -> Self;

     /// Adds one to this step, returning the result
     fn add_one(&self) -> Self;

     /// Subtracts one to this step, returning the result
     fn sub_one(&self) -> Self;
 }

 macro_rules! step_impl_unsigned {
     ($($t:ty)*) => ($(
         #[unstable(feature = "step_trait",
                    reason = "likely to be replaced by finer-grained traits",
                    issue = "27741")]
         impl Step for $t {
             #[inline]
             fn step(&self, by: &$t) -> Option<$t> {
                 (*self).checked_add(*by)
             }
             #[inline]
             #[allow(trivial_numeric_casts)]
             fn steps_between(start: &$t, end: &$t, by: &$t) -> Option<usize> {
                 if *by == 0 { return None; }
                 if *start < *end {
                     // Note: We assume $t <= usize here
                     let diff = (*end - *start) as usize;
                     let by = *by as usize;
                     if diff % by > 0 {
                         Some(diff / by + 1)
                     } else {
                         Some(diff / by)
                     }
                 } else {
                     Some(0)
                 }
             }

             #[inline]
             fn is_negative(&self) -> bool {
                 false
             }

             #[inline]
             fn replace_one(&mut self) -> Self {
                 mem::replace(self, 0)
             }

             #[inline]
             fn replace_zero(&mut self) -> Self {
                 mem::replace(self, 1)
             }

             #[inline]
             fn add_one(&self) -> Self {
                 *self + 1
             }

             #[inline]
             fn sub_one(&self) -> Self {
                 *self - 1
             }

             #[inline]
             fn steps_between_by_one(start: &Self, end: &Self) -> Option<usize> {
                 Self::steps_between(start, end, &1)
             }
         }
     )*)
 }
 macro_rules! step_impl_signed {
     ($($t:ty)*) => ($(
         #[unstable(feature = "step_trait",
                    reason = "likely to be replaced by finer-grained traits",
                    issue = "27741")]
         impl Step for $t {
             #[inline]
             fn step(&self, by: &$t) -> Option<$t> {
                 (*self).checked_add(*by)
             }
             #[inline]
             #[allow(trivial_numeric_casts)]
             fn steps_between(start: &$t, end: &$t, by: &$t) -> Option<usize> {
                 if *by == 0 { return None; }
                 let diff: usize;
                 let by_u: usize;
                 if *by > 0 {
                     if *start >= *end {
                         return Some(0);
                     }
                     // Note: We assume $t <= isize here
                     // Use .wrapping_sub and cast to usize to compute the
                     // difference that may not fit inside the range of isize.
                     diff = (*end as isize).wrapping_sub(*start as isize) as usize;
                     by_u = *by as usize;
                 } else {
                     if *start <= *end {
                         return Some(0);
                     }
                     diff = (*start as isize).wrapping_sub(*end as isize) as usize;
                     by_u = (*by as isize).wrapping_mul(-1) as usize;
                 }
                 if diff % by_u > 0 {
                     Some(diff / by_u + 1)
                 } else {
                     Some(diff / by_u)
                 }
             }

             #[inline]
             fn is_negative(&self) -> bool {
                 *self < 0
             }

             #[inline]
             fn replace_one(&mut self) -> Self {
                 mem::replace(self, 0)
             }

             #[inline]
             fn replace_zero(&mut self) -> Self {
                 mem::replace(self, 1)
             }

             #[inline]
             fn add_one(&self) -> Self {
                 *self + 1
             }

             #[inline]
             fn sub_one(&self) -> Self {
                 *self - 1
             }

             #[inline]
             fn steps_between_by_one(start: &Self, end: &Self) -> Option<usize> {
                 Self::steps_between(start, end, &1)
             }
         }
     )*)
 }

 macro_rules! step_impl_no_between {
     ($($t:ty)*) => ($(
         #[unstable(feature = "step_trait",
                    reason = "likely to be replaced by finer-grained traits",
                    issue = "27741")]
         impl Step for $t {
             #[inline]
             fn step(&self, by: &$t) -> Option<$t> {
                 (*self).checked_add(*by)
             }
             #[inline]
             fn steps_between(_a: &$t, _b: &$t, _by: &$t) -> Option<usize> {
                 None
             }

             #[inline]
             #[allow(unused_comparisons)]
             fn is_negative(&self) -> bool {
                 *self < 0
             }

             #[inline]
             fn replace_one(&mut self) -> Self {
                 mem::replace(self, 0)
             }

             #[inline]
             fn replace_zero(&mut self) -> Self {
                 mem::replace(self, 1)
             }

             #[inline]
             fn add_one(&self) -> Self {
                 *self + 1
             }

             #[inline]
             fn sub_one(&self) -> Self {
                 *self - 1
             }

             #[inline]
             fn steps_between_by_one(start: &Self, end: &Self) -> Option<usize> {
                 Self::steps_between(start, end, &1)
             }
         }
     )*)
 }

 step_impl_unsigned!(usize u8 u16 u32);
 step_impl_signed!(isize i8 i16 i32);
 #[cfg(target_pointer_width = "64")]
 step_impl_unsigned!(u64);
 #[cfg(target_pointer_width = "64")]
 step_impl_signed!(i64);
 // If the target pointer width is not 64-bits, we
 // assume here that it is less than 64-bits.
 #[cfg(not(target_pointer_width = "64"))]
 step_impl_no_between!(u64 i64);

 /// An adapter for stepping range iterators by a custom amount.
 ///
 /// The resulting iterator handles overflow by stopping. The `A`
 /// parameter is the type being iterated over, while `R` is the range
 /// type (usually one of `std::ops::{Range, RangeFrom, RangeInclusive}`.
 #[derive(Clone, Debug)]
 #[unstable(feature = "step_by", reason = "recent addition",
            issue = "27741")]
 pub struct StepBy<A, R> {
     step_by: A,
     range: R,
 }

 impl<A: Step> ops::RangeFrom<A> {
     /// Creates an iterator starting at the same point, but stepping by
     /// the given amount at each iteration.
     ///
     /// # Examples
     ///
     /// ```
     /// # #![feature(step_by)]
     ///
     /// for i in (0u8..).step_by(2).take(10) {
     ///     println!("{}", i);
     /// }
     /// ```
     ///
     /// This prints the first ten even natural integers (0 to 18).
     #[unstable(feature = "step_by", reason = "recent addition",
                issue = "27741")]
     pub fn step_by(self, by: A) -> StepBy<A, Self> {
         StepBy {
             step_by: by,
             range: self
         }
     }
 }

 impl<A: Step> ops::Range<A> {
     /// Creates an iterator with the same range, but stepping by the
     /// given amount at each iteration.
     ///
     /// The resulting iterator handles overflow by stopping.
     ///
     /// # Examples
     ///
     /// ```
     /// #![feature(step_by)]
     ///
     /// for i in (0..10).step_by(2) {
     ///     println!("{}", i);
     /// }
     /// ```
     ///
     /// This prints:
     ///
     /// ```text
     /// 0
     /// 2
     /// 4
     /// 6
     /// 8
     /// ```
     #[unstable(feature = "step_by", reason = "recent addition",
                issue = "27741")]
     pub fn step_by(self, by: A) -> StepBy<A, Self> {
         StepBy {
             step_by: by,
             range: self
         }
     }
 }

 impl<A: Step> ops::RangeInclusive<A> {
     /// Creates an iterator with the same range, but stepping by the
     /// given amount at each iteration.
     ///
     /// The resulting iterator handles overflow by stopping.
     ///
     /// # Examples
     ///
     /// ```
     /// #![feature(step_by, inclusive_range_syntax)]
     ///
     /// for i in (0...10).step_by(2) {
     ///     println!("{}", i);
     /// }
     /// ```
     ///
     /// This prints:
     ///
     /// ```text
     /// 0
     /// 2
     /// 4
     /// 6
     /// 8
     /// 10
     /// ```
     #[unstable(feature = "step_by", reason = "recent addition",
                issue = "27741")]
     pub fn step_by(self, by: A) -> StepBy<A, Self> {
         StepBy {
             step_by: by,
             range: self
         }
     }
 }

 #[stable(feature = "rust1", since = "1.0.0")]
 impl<A> Iterator for StepBy<A, ops::RangeFrom<A>> where
     A: Clone,
     for<'a> &'a A: Add<&'a A, Output = A>
 {
     type Item = A;

     #[inline]
     fn next(&mut self) -> Option<A> {
         let mut n = &self.range.start + &self.step_by;
         mem::swap(&mut n, &mut self.range.start);
         Some(n)
     }

     #[inline]
     fn size_hint(&self) -> (usize, Option<usize>) {
         (usize::MAX, None) // Too bad we can't specify an infinite lower bound
     }
 }

 #[stable(feature = "rust1", since = "1.0.0")]
 impl<A: Step + Clone> Iterator for StepBy<A, ops::Range<A>> {
     type Item = A;

     #[inline]
     fn next(&mut self) -> Option<A> {
         let rev = self.step_by.is_negative();
         if (rev && self.range.start > self.range.end) ||
            (!rev && self.range.start < self.range.end)
         {
             match self.range.start.step(&self.step_by) {
                 Some(mut n) => {
                     mem::swap(&mut self.range.start, &mut n);
                     Some(n)
                 },
                 None => {
                     let mut n = self.range.end.clone();
                     mem::swap(&mut self.range.start, &mut n);
                     Some(n)
                 }
             }
         } else {
             None
         }
     }

     #[inline]
     fn size_hint(&self) -> (usize, Option<usize>) {
         match Step::steps_between(&self.range.start,
                                   &self.range.end,
                                   &self.step_by) {
             Some(hint) => (hint, Some(hint)),
             None       => (0, None)
         }
     }
 }

 #[unstable(feature = "inclusive_range",
            reason = "recently added, follows RFC",
            issue = "28237")]
 impl<A: Step + Clone> Iterator for StepBy<A, ops::RangeInclusive<A>> {
     type Item = A;

     #[inline]
     fn next(&mut self) -> Option<A> {
         use ops::RangeInclusive::*;

         // this function has a sort of odd structure due to borrowck issues
         // we may need to replace self.range, so borrows of start and end need to end early

         let (finishing, n) = match self.range {
             Empty { .. } => return None, // empty iterators yield no values

             NonEmpty { ref mut start, ref mut end } => {
                 let rev = self.step_by.is_negative();

                 // march start towards (maybe past!) end and yield the old value
                 if (rev && start >= end) ||
                    (!rev && start <= end)
                 {
                     match start.step(&self.step_by) {
                         Some(mut n) => {
                             mem::swap(start, &mut n);
                             (None, Some(n)) // yield old value, remain non-empty
                         },
                         None => {
                             let mut n = end.clone();
                             mem::swap(start, &mut n);
                             (None, Some(n)) // yield old value, remain non-empty
                         }
                     }
                 } else {
                     // found range in inconsistent state (start at or past end), so become empty
                     (Some(end.replace_zero()), None)
                 }
             }
         };

         // turn into an empty iterator if we've reached the end
         if let Some(end) = finishing {
             self.range = Empty { at: end };
         }

         n
     }

     #[inline]
     fn size_hint(&self) -> (usize, Option<usize>) {
         use ops::RangeInclusive::*;

         match self.range {
             Empty { .. } => (0, Some(0)),

             NonEmpty { ref start, ref end } =>
                 match Step::steps_between(start,
                                           end,
                                           &self.step_by) {
                     Some(hint) => (hint.saturating_add(1), hint.checked_add(1)),
                     None       => (0, None)
                 }
         }
     }
 }

 macro_rules! range_exact_iter_impl {
     ($($t:ty)*) => ($(
         #[stable(feature = "rust1", since = "1.0.0")]
         impl ExactSizeIterator for ops::Range<$t> { }

         #[unstable(feature = "inclusive_range",
                    reason = "recently added, follows RFC",
                    issue = "28237")]
         impl ExactSizeIterator for ops::RangeInclusive<$t> { }
     )*)
 }

 #[stable(feature = "rust1", since = "1.0.0")]
 impl<A: Step> Iterator for ops::Range<A> where
     for<'a> &'a A: Add<&'a A, Output = A>
 {
     type Item = A;

     #[inline]
     fn next(&mut self) -> Option<A> {
         if self.start < self.end {
             let mut n = self.start.add_one();
             mem::swap(&mut n, &mut self.start);
             Some(n)
         } else {
             None
         }
     }

     #[inline]
     fn size_hint(&self) -> (usize, Option<usize>) {
         match Step::steps_between_by_one(&self.start, &self.end) {
             Some(hint) => (hint, Some(hint)),
             None => (0, None)
         }
     }
 }

 // Ranges of u64 and i64 are excluded because they cannot guarantee having
 // a length <= usize::MAX, which is required by ExactSizeIterator.
 range_exact_iter_impl!(usize u8 u16 u32 isize i8 i16 i32);

 #[stable(feature = "rust1", since = "1.0.0")]
 impl<A: Step + Clone> DoubleEndedIterator for ops::Range<A> where
     for<'a> &'a A: Add<&'a A, Output = A>,
     for<'a> &'a A: Sub<&'a A, Output = A>
 {
     #[inline]
     fn next_back(&mut self) -> Option<A> {
         if self.start < self.end {
             self.end = self.end.sub_one();
             Some(self.end.clone())
         } else {
             None
         }
     }
 }

 #[stable(feature = "rust1", since = "1.0.0")]
 impl<A: Step> Iterator for ops::RangeFrom<A> where
     for<'a> &'a A: Add<&'a A, Output = A>
 {
     type Item = A;

     #[inline]
     fn next(&mut self) -> Option<A> {
         let mut n = self.start.add_one();
         mem::swap(&mut n, &mut self.start);
         Some(n)
     }
 }

 #[unstable(feature = "inclusive_range", reason = "recently added, follows RFC", issue = "28237")]
 impl<A: Step> Iterator for ops::RangeInclusive<A> where
     for<'a> &'a A: Add<&'a A, Output = A>
 {
     type Item = A;

     #[inline]
     fn next(&mut self) -> Option<A> {
         use ops::RangeInclusive::*;

         // this function has a sort of odd structure due to borrowck issues
         // we may need to replace self, so borrows of self.start and self.end need to end early

         let (finishing, n) = match *self {
             Empty { .. } => (None, None), // empty iterators yield no values

             NonEmpty { ref mut start, ref mut end } => {
                 if start == end {
                     (Some(end.replace_one()), Some(start.replace_one()))
                 } else if start < end {
                     let mut n = start.add_one();
                     mem::swap(&mut n, start);

                     // if the iterator is done iterating, it will change from
                     // NonEmpty to Empty to avoid unnecessary drops or clones,
                     // we'll reuse either start or end (they are equal now, so
                     // it doesn't matter which) to pull out end, we need to swap
                     // something back in

                     (if n == *end { Some(end.replace_one()) } else { None },
                     // ^ are we done yet?
                     Some(n)) // < the value to output
                 } else {
                     (Some(start.replace_one()), None)
                 }
             }
         };

         // turn into an empty iterator if this is the last value
         if let Some(end) = finishing {
             *self = Empty { at: end };
         }

         n
     }

     #[inline]
     fn size_hint(&self) -> (usize, Option<usize>) {
         use ops::RangeInclusive::*;

         match *self {
             Empty { .. } => (0, Some(0)),

             NonEmpty { ref start, ref end } =>
                 match Step::steps_between_by_one(start, end) {
                     Some(hint) => (hint.saturating_add(1), hint.checked_add(1)),
                     None => (0, None),
                 }
         }
     }
 }

 #[unstable(feature = "inclusive_range", reason = "recently added, follows RFC", issue = "28237")]
 impl<A: Step> DoubleEndedIterator for ops::RangeInclusive<A> where
     for<'a> &'a A: Add<&'a A, Output = A>,
     for<'a> &'a A: Sub<&'a A, Output = A>
 {
     #[inline]
     fn next_back(&mut self) -> Option<A> {
         use ops::RangeInclusive::*;

         // see Iterator::next for comments

         let (finishing, n) = match *self {
             Empty { .. } => return None,

             NonEmpty { ref mut start, ref mut end } => {
                 if start == end {
                     (Some(start.replace_one()), Some(end.replace_one()))
                 } else if start < end {
                     let mut n = end.sub_one();
                     mem::swap(&mut n, end);

                     (if n == *start { Some(start.replace_one()) } else { None },
                      Some(n))
                 } else {
                     (Some(end.replace_one()), None)
                 }
             }
         };

         if let Some(start) = finishing {
             *self = Empty { at: start };
         }

         n
     }
 }
	// Copyright 2013-2016 The Rust Project Developers. See the COPYRIGHT
	// file at the top-level directory of this distribution and at
	// http://rust-lang.org/COPYRIGHT.
	//
	// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
	// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
	// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
	// option. This file may not be copied, modified, or distributed
	// except according to those terms.

	use clone::Clone;
	use cmp::PartialOrd;
	use mem;
	use ops::{self, Add, Sub};
	use option::Option::{self, Some, None};
	use marker::Sized;
	use usize;

	use super::{DoubleEndedIterator, ExactSizeIterator, Iterator};

	/// Objects that can be stepped over in both directions.
	///
	/// The `steps_between` function provides a way to efficiently compare
	/// two `Step` objects.
	#[unstable(feature = "step_trait",
	reason = "likely to be replaced by finer-grained traits",
	issue = "27741")]
	pub trait Step: PartialOrd + Sized {
	/// Steps `self` if possible.
	fn step(&self, by: &Self) -> Option<Self>;

	/// Returns the number of steps between two step objects. The count is
	/// inclusive of `start` and exclusive of `end`.
	///
	/// Returns `None` if it is not possible to calculate `steps_between`
	/// without overflow.
	fn steps_between(start: &Self, end: &Self, by: &Self) -> Option<usize>;

	/// Same as `steps_between`, but with a `by` of 1
	fn steps_between_by_one(start: &Self, end: &Self) -> Option<usize>;

	/// Tests whether this step is negative or not (going backwards)
	fn is_negative(&self) -> bool;

	/// Replaces this step with `1`, returning itself
	fn replace_one(&mut self) -> Self;

	/// Replaces this step with `0`, returning itself
	fn replace_zero(&mut self) -> Self;

	/// Adds one to this step, returning the result
	fn add_one(&self) -> Self;

	/// Subtracts one to this step, returning the result
	fn sub_one(&self) -> Self;
	}

	macro_rules! step_impl_unsigned {
	($($t:ty)*) => ($(
	#[unstable(feature = "step_trait",
	reason = "likely to be replaced by finer-grained traits",
	issue = "27741")]
	impl Step for $t {
	#[inline]
	fn step(&self, by: &$t) -> Option<$t> {
	(self).checked_add(by)
	}
	#[inline]
	#[allow(trivial_numeric_casts)]
	fn steps_between(start: &$t, end: &$t, by: &$t) -> Option<usize> {
	if *by == 0 { return None; }
	if start < end {
	// Note: We assume $t <= usize here
	let diff = (end - start) as usize;
	let by = *by as usize;
	if diff % by > 0 {
	Some(diff / by + 1)
	} else {
	Some(diff / by)
	}
	} else {
	Some(0)
	}
	}

	#[inline]
	fn is_negative(&self) -> bool {
	false
	}

	#[inline]
	fn replace_one(&mut self) -> Self {
	mem::replace(self, 0)
	}

	#[inline]
	fn replace_zero(&mut self) -> Self {
	mem::replace(self, 1)
	}

	#[inline]
	fn add_one(&self) -> Self {
	*self + 1
	}

	#[inline]
	fn sub_one(&self) -> Self {
	*self - 1
	}

	#[inline]
	fn steps_between_by_one(start: &Self, end: &Self) -> Option<usize> {
	Self::steps_between(start, end, &1)
	}
	}
	)*)
	}
	macro_rules! step_impl_signed {
	($($t:ty)*) => ($(
	#[unstable(feature = "step_trait",
	reason = "likely to be replaced by finer-grained traits",
	issue = "27741")]
	impl Step for $t {
	#[inline]
	fn step(&self, by: &$t) -> Option<$t> {
	(self).checked_add(by)
	}
	#[inline]
	#[allow(trivial_numeric_casts)]
	fn steps_between(start: &$t, end: &$t, by: &$t) -> Option<usize> {
	if *by == 0 { return None; }
	let diff: usize;
	let by_u: usize;
	if *by > 0 {
	if start >= end {
	return Some(0);
	}
	// Note: We assume $t <= isize here
	// Use .wrapping_sub and cast to usize to compute the
	// difference that may not fit inside the range of isize.
	diff = (end as isize).wrapping_sub(start as isize) as usize;
	by_u = *by as usize;
	} else {
	if start <= end {
	return Some(0);
	}
	diff = (start as isize).wrapping_sub(end as isize) as usize;
	by_u = (*by as isize).wrapping_mul(-1) as usize;
	}
	if diff % by_u > 0 {
	Some(diff / by_u + 1)
	} else {
	Some(diff / by_u)
	}
	}

	#[inline]
	fn is_negative(&self) -> bool {
	*self < 0
	}

	#[inline]
	fn replace_one(&mut self) -> Self {
	mem::replace(self, 0)
	}

	#[inline]
	fn replace_zero(&mut self) -> Self {
	mem::replace(self, 1)
	}

	#[inline]
	fn add_one(&self) -> Self {
	*self + 1
	}

	#[inline]
	fn sub_one(&self) -> Self {
	*self - 1
	}

	#[inline]
	fn steps_between_by_one(start: &Self, end: &Self) -> Option<usize> {
	Self::steps_between(start, end, &1)
	}
	}
	)*)
	}

	macro_rules! step_impl_no_between {
	($($t:ty)*) => ($(
	#[unstable(feature = "step_trait",
	reason = "likely to be replaced by finer-grained traits",
	issue = "27741")]
	impl Step for $t {
	#[inline]
	fn step(&self, by: &$t) -> Option<$t> {
	(self).checked_add(by)
	}
	#[inline]
	fn steps_between(_a: &$t, _b: &$t, _by: &$t) -> Option<usize> {
	None
	}

	#[inline]
	#[allow(unused_comparisons)]
	fn is_negative(&self) -> bool {
	*self < 0
	}

	#[inline]
	fn replace_one(&mut self) -> Self {
	mem::replace(self, 0)
	}

	#[inline]
	fn replace_zero(&mut self) -> Self {
	mem::replace(self, 1)
	}

	#[inline]
	fn add_one(&self) -> Self {
	*self + 1
	}

	#[inline]
	fn sub_one(&self) -> Self {
	*self - 1
	}

	#[inline]
	fn steps_between_by_one(start: &Self, end: &Self) -> Option<usize> {
	Self::steps_between(start, end, &1)
	}
	}
	)*)
	}

	step_impl_unsigned!(usize u8 u16 u32);
	step_impl_signed!(isize i8 i16 i32);
	#[cfg(target_pointer_width = "64")]
	step_impl_unsigned!(u64);
	#[cfg(target_pointer_width = "64")]
	step_impl_signed!(i64);
	// If the target pointer width is not 64-bits, we
	// assume here that it is less than 64-bits.
	#[cfg(not(target_pointer_width = "64"))]
	step_impl_no_between!(u64 i64);

	/// An adapter for stepping range iterators by a custom amount.
	///
	/// The resulting iterator handles overflow by stopping. The `A`
	/// parameter is the type being iterated over, while `R` is the range
	/// type (usually one of `std::ops::{Range, RangeFrom, RangeInclusive}`.
	#[derive(Clone, Debug)]
	#[unstable(feature = "step_by", reason = "recent addition",
	issue = "27741")]
	pub struct StepBy<A, R> {
	step_by: A,
	range: R,
	}

	impl<A: Step> ops::RangeFrom<A> {
	/// Creates an iterator starting at the same point, but stepping by
	/// the given amount at each iteration.
	///
	/// # Examples
	///
	/// ```
	/// # #![feature(step_by)]
	///
	/// for i in (0u8..).step_by(2).take(10) {
	/// println!("{}", i);
	/// }
	/// ```
	///
	/// This prints the first ten even natural integers (0 to 18).
	#[unstable(feature = "step_by", reason = "recent addition",
	issue = "27741")]
	pub fn step_by(self, by: A) -> StepBy<A, Self> {
	StepBy {
	step_by: by,
	range: self
	}
	}
	}

	impl<A: Step> ops::Range<A> {
	/// Creates an iterator with the same range, but stepping by the
	/// given amount at each iteration.
	///
	/// The resulting iterator handles overflow by stopping.
	///
	/// # Examples
	///
	/// ```
	/// #![feature(step_by)]
	///
	/// for i in (0..10).step_by(2) {
	/// println!("{}", i);
	/// }
	/// ```
	///
	/// This prints:
	///
	/// ```text
	/// 0
	/// 2
	/// 4
	/// 6
	/// 8
	/// ```
	#[unstable(feature = "step_by", reason = "recent addition",
	issue = "27741")]
	pub fn step_by(self, by: A) -> StepBy<A, Self> {
	StepBy {
	step_by: by,
	range: self
	}
	}
	}

	impl<A: Step> ops::RangeInclusive<A> {
	/// Creates an iterator with the same range, but stepping by the
	/// given amount at each iteration.
	///
	/// The resulting iterator handles overflow by stopping.
	///
	/// # Examples
	///
	/// ```
	/// #![feature(step_by, inclusive_range_syntax)]
	///
	/// for i in (0...10).step_by(2) {
	/// println!("{}", i);
	/// }
	/// ```
	///
	/// This prints:
	///
	/// ```text
	/// 0
	/// 2
	/// 4
	/// 6
	/// 8
	/// 10
	/// ```
	#[unstable(feature = "step_by", reason = "recent addition",
	issue = "27741")]
	pub fn step_by(self, by: A) -> StepBy<A, Self> {
	StepBy {
	step_by: by,
	range: self
	}
	}
	}

	#[stable(feature = "rust1", since = "1.0.0")]
	impl<A> Iterator for StepBy<A, ops::RangeFrom<A>> where
	A: Clone,
	for<'a> &'a A: Add<&'a A, Output = A>
	{
	type Item = A;

	#[inline]
	fn next(&mut self) -> Option<A> {
	let mut n = &self.range.start + &self.step_by;
	mem::swap(&mut n, &mut self.range.start);
	Some(n)
	}

	#[inline]
	fn size_hint(&self) -> (usize, Option<usize>) {
	(usize::MAX, None) // Too bad we can't specify an infinite lower bound
	}
	}

	#[stable(feature = "rust1", since = "1.0.0")]
	impl<A: Step + Clone> Iterator for StepBy<A, ops::Range<A>> {
	type Item = A;

	#[inline]
	fn next(&mut self) -> Option<A> {
	let rev = self.step_by.is_negative();
	if (rev && self.range.start > self.range.end) \|\|
	(!rev && self.range.start < self.range.end)
	{
	match self.range.start.step(&self.step_by) {
	Some(mut n) => {
	mem::swap(&mut self.range.start, &mut n);
	Some(n)
	},
	None => {
	let mut n = self.range.end.clone();
	mem::swap(&mut self.range.start, &mut n);
	Some(n)
	}
	}
	} else {
	None
	}
	}

	#[inline]
	fn size_hint(&self) -> (usize, Option<usize>) {
	match Step::steps_between(&self.range.start,
	&self.range.end,
	&self.step_by) {
	Some(hint) => (hint, Some(hint)),
	None => (0, None)
	}
	}
	}

	#[unstable(feature = "inclusive_range",
	reason = "recently added, follows RFC",
	issue = "28237")]
	impl<A: Step + Clone> Iterator for StepBy<A, ops::RangeInclusive<A>> {
	type Item = A;

	#[inline]
	fn next(&mut self) -> Option<A> {
	use ops::RangeInclusive::*;

	// this function has a sort of odd structure due to borrowck issues
	// we may need to replace self.range, so borrows of start and end need to end early

	let (finishing, n) = match self.range {
	Empty { .. } => return None, // empty iterators yield no values

	NonEmpty { ref mut start, ref mut end } => {
	let rev = self.step_by.is_negative();

	// march start towards (maybe past!) end and yield the old value
	if (rev && start >= end) \|\|
	(!rev && start <= end)
	{
	match start.step(&self.step_by) {
	Some(mut n) => {
	mem::swap(start, &mut n);
	(None, Some(n)) // yield old value, remain non-empty
	},
	None => {
	let mut n = end.clone();
	mem::swap(start, &mut n);
	(None, Some(n)) // yield old value, remain non-empty
	}
	}
	} else {
	// found range in inconsistent state (start at or past end), so become empty
	(Some(end.replace_zero()), None)
	}
	}
	};

	// turn into an empty iterator if we've reached the end
	if let Some(end) = finishing {
	self.range = Empty { at: end };
	}

	n
	}

	#[inline]
	fn size_hint(&self) -> (usize, Option<usize>) {
	use ops::RangeInclusive::*;

	match self.range {
	Empty { .. } => (0, Some(0)),

	NonEmpty { ref start, ref end } =>
	match Step::steps_between(start,
	end,
	&self.step_by) {
	Some(hint) => (hint.saturating_add(1), hint.checked_add(1)),
	None => (0, None)
	}
	}
	}
	}

	macro_rules! range_exact_iter_impl {
	($($t:ty)*) => ($(
	#[stable(feature = "rust1", since = "1.0.0")]
	impl ExactSizeIterator for ops::Range<$t> { }

	#[unstable(feature = "inclusive_range",
	reason = "recently added, follows RFC",
	issue = "28237")]
	impl ExactSizeIterator for ops::RangeInclusive<$t> { }
	)*)
	}

	#[stable(feature = "rust1", since = "1.0.0")]
	impl<A: Step> Iterator for ops::Range<A> where
	for<'a> &'a A: Add<&'a A, Output = A>
	{
	type Item = A;

	#[inline]
	fn next(&mut self) -> Option<A> {
	if self.start < self.end {
	let mut n = self.start.add_one();
	mem::swap(&mut n, &mut self.start);
	Some(n)
	} else {
	None
	}
	}

	#[inline]
	fn size_hint(&self) -> (usize, Option<usize>) {
	match Step::steps_between_by_one(&self.start, &self.end) {
	Some(hint) => (hint, Some(hint)),
	None => (0, None)
	}
	}
	}

	// Ranges of u64 and i64 are excluded because they cannot guarantee having
	// a length <= usize::MAX, which is required by ExactSizeIterator.
	range_exact_iter_impl!(usize u8 u16 u32 isize i8 i16 i32);

	#[stable(feature = "rust1", since = "1.0.0")]
	impl<A: Step + Clone> DoubleEndedIterator for ops::Range<A> where
	for<'a> &'a A: Add<&'a A, Output = A>,
	for<'a> &'a A: Sub<&'a A, Output = A>
	{
	#[inline]
	fn next_back(&mut self) -> Option<A> {
	if self.start < self.end {
	self.end = self.end.sub_one();
	Some(self.end.clone())
	} else {
	None
	}
	}
	}

	#[stable(feature = "rust1", since = "1.0.0")]
	impl<A: Step> Iterator for ops::RangeFrom<A> where
	for<'a> &'a A: Add<&'a A, Output = A>
	{
	type Item = A;

	#[inline]
	fn next(&mut self) -> Option<A> {
	let mut n = self.start.add_one();
	mem::swap(&mut n, &mut self.start);
	Some(n)
	}
	}

	#[unstable(feature = "inclusive_range", reason = "recently added, follows RFC", issue = "28237")]
	impl<A: Step> Iterator for ops::RangeInclusive<A> where
	for<'a> &'a A: Add<&'a A, Output = A>
	{
	type Item = A;

	#[inline]
	fn next(&mut self) -> Option<A> {
	use ops::RangeInclusive::*;

	// this function has a sort of odd structure due to borrowck issues
	// we may need to replace self, so borrows of self.start and self.end need to end early

	let (finishing, n) = match *self {
	Empty { .. } => (None, None), // empty iterators yield no values

	NonEmpty { ref mut start, ref mut end } => {
	if start == end {
	(Some(end.replace_one()), Some(start.replace_one()))
	} else if start < end {
	let mut n = start.add_one();
	mem::swap(&mut n, start);

	// if the iterator is done iterating, it will change from
	// NonEmpty to Empty to avoid unnecessary drops or clones,
	// we'll reuse either start or end (they are equal now, so
	// it doesn't matter which) to pull out end, we need to swap
	// something back in

	(if n == *end { Some(end.replace_one()) } else { None },
	// ^ are we done yet?
	Some(n)) // < the value to output
	} else {
	(Some(start.replace_one()), None)
	}
	}
	};

	// turn into an empty iterator if this is the last value
	if let Some(end) = finishing {
	*self = Empty { at: end };
	}

	n
	}

	#[inline]
	fn size_hint(&self) -> (usize, Option<usize>) {
	use ops::RangeInclusive::*;

	match *self {
	Empty { .. } => (0, Some(0)),

	NonEmpty { ref start, ref end } =>
	match Step::steps_between_by_one(start, end) {
	Some(hint) => (hint.saturating_add(1), hint.checked_add(1)),
	None => (0, None),
	}
	}
	}
	}

	#[unstable(feature = "inclusive_range", reason = "recently added, follows RFC", issue = "28237")]
	impl<A: Step> DoubleEndedIterator for ops::RangeInclusive<A> where
	for<'a> &'a A: Add<&'a A, Output = A>,
	for<'a> &'a A: Sub<&'a A, Output = A>
	{
	#[inline]
	fn next_back(&mut self) -> Option<A> {
	use ops::RangeInclusive::*;

	// see Iterator::next for comments

	let (finishing, n) = match *self {
	Empty { .. } => return None,

	NonEmpty { ref mut start, ref mut end } => {
	if start == end {
	(Some(start.replace_one()), Some(end.replace_one()))
	} else if start < end {
	let mut n = end.sub_one();
	mem::swap(&mut n, end);

	(if n == *start { Some(start.replace_one()) } else { None },
	Some(n))
	} else {
	(Some(end.replace_one()), None)
	}
	}
	};

	if let Some(start) = finishing {
	*self = Empty { at: start };
	}

	n
	}
	}