src/libcore/iter/range.rs

   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.
   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 use mem;
  12 use ops::{self, Add, Sub};
  13 use usize;
  14
  15 use super::{FusedIterator, TrustedLen};
  16
  17 /// Objects that can be stepped over in both directions.
  18 ///
  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",
  23            issue = "42168")]
  24 pub trait Step: PartialOrd + Sized {
  25     /// Steps `self` if possible.
  26     fn step(&self, by: &Self) -> Option<Self>;
  27
  28     /// Returns the number of steps between two step objects. The count is
  29     /// inclusive of `start` and exclusive of `end`.
  30     ///
  31     /// Returns `None` if it is not possible to calculate `steps_between`
  32     /// without overflow.
  33     fn steps_between(start: &Self, end: &Self, by: &Self) -> Option<usize>;
  34
  35     /// Same as `steps_between`, but with a `by` of 1
  36     fn steps_between_by_one(start: &Self, end: &Self) -> Option<usize>;
  37
  38     /// Tests whether this step is negative or not (going backwards)
  39     fn is_negative(&self) -> bool;
  40
  41     /// Replaces this step with `1`, returning itself
  42     fn replace_one(&mut self) -> Self;
  43
  44     /// Replaces this step with `0`, returning itself
  45     fn replace_zero(&mut self) -> Self;
  46
  47     /// Adds one to this step, returning the result
  48     fn add_one(&self) -> Self;
  49
  50     /// Subtracts one to this step, returning the result
  51     fn sub_one(&self) -> Self;
  52 }
  53
  54 macro_rules! step_impl_unsigned {
  55     ($($t:ty)*) => ($(
  56         #[unstable(feature = "step_trait",
  57                    reason = "likely to be replaced by finer-grained traits",
  58                    issue = "42168")]
  59         impl Step for $t {
  60             #[inline]
  61             fn step(&self, by: &$t) -> Option<$t> {
  62                 (*self).checked_add(*by)
  63             }
  64             #[inline]
  65             #[allow(trivial_numeric_casts)]
  66             fn steps_between(start: &$t, end: &$t, by: &$t) -> Option<usize> {
  67                 if *by == 0 { return None; }
  68                 if *start < *end {
  69                     // Note: We assume $t <= usize here
  70                     let diff = (*end - *start) as usize;
  71                     let by = *by as usize;
  72                     if diff % by > 0 {
  73                         Some(diff / by + 1)
  74                     } else {
  75                         Some(diff / by)
  76                     }
  77                 } else {
  78                     Some(0)
  79                 }
  80             }
  81
  82             #[inline]
  83             fn is_negative(&self) -> bool {
  84                 false
  85             }
  86
  87             #[inline]
  88             fn replace_one(&mut self) -> Self {
  89                 mem::replace(self, 1)
  90             }
  91
  92             #[inline]
  93             fn replace_zero(&mut self) -> Self {
  94                 mem::replace(self, 0)
  95             }
  96
  97             #[inline]
  98             fn add_one(&self) -> Self {
  99                 Add::add(*self, 1)
 100             }
 101
 102             #[inline]
 103             fn sub_one(&self) -> Self {
 104                 Sub::sub(*self, 1)
 105             }
 106
 107             #[inline]
 108             fn steps_between_by_one(start: &Self, end: &Self) -> Option<usize> {
 109                 Self::steps_between(start, end, &1)
 110             }
 111         }
 112     )*)
 113 }
 114 macro_rules! step_impl_signed {
 115     ($($t:ty)*) => ($(
 116         #[unstable(feature = "step_trait",
 117                    reason = "likely to be replaced by finer-grained traits",
 118                    issue = "42168")]
 119         impl Step for $t {
 120             #[inline]
 121             fn step(&self, by: &$t) -> Option<$t> {
 122                 (*self).checked_add(*by)
 123             }
 124             #[inline]
 125             #[allow(trivial_numeric_casts)]
 126             fn steps_between(start: &$t, end: &$t, by: &$t) -> Option<usize> {
 127                 if *by == 0 { return None; }
 128                 let diff: usize;
 129                 let by_u: usize;
 130                 if *by > 0 {
 131                     if *start >= *end {
 132                         return Some(0);
 133                     }
 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;
 138                     by_u = *by as usize;
 139                 } else {
 140                     if *start <= *end {
 141                         return Some(0);
 142                     }
 143                     diff = (*start as isize).wrapping_sub(*end as isize) as usize;
 144                     by_u = (*by as isize).wrapping_mul(-1) as usize;
 145                 }
 146                 if diff % by_u > 0 {
 147                     Some(diff / by_u + 1)
 148                 } else {
 149                     Some(diff / by_u)
 150                 }
 151             }
 152
 153             #[inline]
 154             fn is_negative(&self) -> bool {
 155                 *self < 0
 156             }
 157
 158             #[inline]
 159             fn replace_one(&mut self) -> Self {
 160                 mem::replace(self, 1)
 161             }
 162
 163             #[inline]
 164             fn replace_zero(&mut self) -> Self {
 165                 mem::replace(self, 0)
 166             }
 167
 168             #[inline]
 169             fn add_one(&self) -> Self {
 170                 Add::add(*self, 1)
 171             }
 172
 173             #[inline]
 174             fn sub_one(&self) -> Self {
 175                 Sub::sub(*self, 1)
 176             }
 177
 178             #[inline]
 179             fn steps_between_by_one(start: &Self, end: &Self) -> Option<usize> {
 180                 Self::steps_between(start, end, &1)
 181             }
 182         }
 183     )*)
 184 }
 185
 186 macro_rules! step_impl_no_between {
 187     ($($t:ty)*) => ($(
 188         #[unstable(feature = "step_trait",
 189                    reason = "likely to be replaced by finer-grained traits",
 190                    issue = "42168")]
 191         impl Step for $t {
 192             #[inline]
 193             fn step(&self, by: &$t) -> Option<$t> {
 194                 (*self).checked_add(*by)
 195             }
 196             #[inline]
 197             fn steps_between(_a: &$t, _b: &$t, _by: &$t) -> Option<usize> {
 198                 None
 199             }
 200
 201             #[inline]
 202             #[allow(unused_comparisons)]
 203             fn is_negative(&self) -> bool {
 204                 *self < 0
 205             }
 206
 207             #[inline]
 208             fn replace_one(&mut self) -> Self {
 209                 mem::replace(self, 1)
 210             }
 211
 212             #[inline]
 213             fn replace_zero(&mut self) -> Self {
 214                 mem::replace(self, 0)
 215             }
 216
 217             #[inline]
 218             fn add_one(&self) -> Self {
 219                 Add::add(*self, 1)
 220             }
 221
 222             #[inline]
 223             fn sub_one(&self) -> Self {
 224                 Sub::sub(*self, 1)
 225             }
 226
 227             #[inline]
 228             fn steps_between_by_one(start: &Self, end: &Self) -> Option<usize> {
 229                 Self::steps_between(start, end, &1)
 230             }
 231         }
 232     )*)
 233 }
 234
 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);
 246
 247 /// An adapter for stepping range iterators by a custom amount.
 248 ///
 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",
 254            issue = "27741")]
 255 #[rustc_deprecated(since = "1.19.0",
 256                    reason = "replaced by `iter::StepBy`")]
 257 #[allow(deprecated)]
 258 pub struct StepBy<A, R> {
 259     step_by: A,
 260     range: R,
 261 }
 262
 263 impl<A: Step> ops::RangeFrom<A> {
 264     /// Creates an iterator starting at the same point, but stepping by
 265     /// the given amount at each iteration.
 266     ///
 267     /// # Examples
 268     ///
 269     /// ```
 270     /// #![feature(step_by)]
 271     /// fn main() {
 272     ///     let result: Vec<_> = (0..).step_by(2).take(5).collect();
 273     ///     assert_eq!(result, vec![0, 2, 4, 6, 8]);
 274     /// }
 275     /// ```
 276     #[unstable(feature = "step_by", reason = "recent addition",
 277                issue = "27741")]
 278     #[rustc_deprecated(since = "1.19.0",
 279                        reason = "replaced by `Iterator::step_by`")]
 280     #[allow(deprecated)]
 281     pub fn step_by(self, by: A) -> StepBy<A, Self> {
 282         StepBy {
 283             step_by: by,
 284             range: self
 285         }
 286     }
 287 }
 288
 289 impl<A: Step> ops::Range<A> {
 290     /// Creates an iterator with the same range, but stepping by the
 291     /// given amount at each iteration.
 292     ///
 293     /// The resulting iterator handles overflow by stopping.
 294     ///
 295     /// # Examples
 296     ///
 297     /// ```
 298     /// #![feature(step_by)]
 299     /// fn main() {
 300     ///     let result: Vec<_> = (0..10).step_by(2).collect();
 301     ///     assert_eq!(result, vec![0, 2, 4, 6, 8]);
 302     /// }
 303     /// ```
 304     #[unstable(feature = "step_by", reason = "recent addition",
 305                issue = "27741")]
 306     #[rustc_deprecated(since = "1.19.0",
 307                        reason = "replaced by `Iterator::step_by`")]
 308     #[allow(deprecated)]
 309     pub fn step_by(self, by: A) -> StepBy<A, Self> {
 310         StepBy {
 311             step_by: by,
 312             range: self
 313         }
 314     }
 315 }
 316
 317 impl<A: Step> ops::RangeInclusive<A> {
 318     /// Creates an iterator with the same range, but stepping by the
 319     /// given amount at each iteration.
 320     ///
 321     /// The resulting iterator handles overflow by stopping.
 322     ///
 323     /// # Examples
 324     ///
 325     /// ```
 326     /// #![feature(step_by, inclusive_range_syntax)]
 327     ///
 328     /// let result: Vec<_> = (0...10).step_by(2).collect();
 329     /// assert_eq!(result, vec![0, 2, 4, 6, 8, 10]);
 330     /// ```
 331     #[unstable(feature = "step_by", reason = "recent addition",
 332                issue = "27741")]
 333     #[rustc_deprecated(since = "1.19.0",
 334                        reason = "replaced by `Iterator::step_by`")]
 335     #[allow(deprecated)]
 336     pub fn step_by(self, by: A) -> StepBy<A, Self> {
 337         StepBy {
 338             step_by: by,
 339             range: self
 340         }
 341     }
 342 }
 343
 344 #[unstable(feature = "step_by", reason = "recent addition",
 345            issue = "27741")]
 346 #[allow(deprecated)]
 347 impl<A> Iterator for StepBy<A, ops::RangeFrom<A>> where
 348     A: Clone,
 349     for<'a> &'a A: Add<&'a A, Output = A>
 350 {
 351     type Item = A;
 352
 353     #[inline]
 354     fn next(&mut self) -> Option<A> {
 355         let mut n = &self.range.start + &self.step_by;
 356         mem::swap(&mut n, &mut self.range.start);
 357         Some(n)
 358     }
 359
 360     #[inline]
 361     fn size_hint(&self) -> (usize, Option<usize>) {
 362         (usize::MAX, None) // Too bad we can't specify an infinite lower bound
 363     }
 364 }
 365
 366 #[unstable(feature = "fused", issue = "35602")]
 367 #[allow(deprecated)]
 368 impl<A> FusedIterator for StepBy<A, ops::RangeFrom<A>>
 369     where A: Clone, for<'a> &'a A: Add<&'a A, Output = A> {}
 370
 371 #[unstable(feature = "step_by", reason = "recent addition",
 372            issue = "27741")]
 373 #[allow(deprecated)]
 374 impl<A: Step + Clone> Iterator for StepBy<A, ops::Range<A>> {
 375     type Item = A;
 376
 377     #[inline]
 378     fn next(&mut self) -> Option<A> {
 379         let rev = self.step_by.is_negative();
 380         if (rev && self.range.start > self.range.end) ||
 381            (!rev && self.range.start < self.range.end)
 382         {
 383             match self.range.start.step(&self.step_by) {
 384                 Some(mut n) => {
 385                     mem::swap(&mut self.range.start, &mut n);
 386                     Some(n)
 387                 },
 388                 None => {
 389                     let mut n = self.range.end.clone();
 390                     mem::swap(&mut self.range.start, &mut n);
 391                     Some(n)
 392                 }
 393             }
 394         } else {
 395             None
 396         }
 397     }
 398
 399     #[inline]
 400     fn size_hint(&self) -> (usize, Option<usize>) {
 401         match Step::steps_between(&self.range.start,
 402                                   &self.range.end,
 403                                   &self.step_by) {
 404             Some(hint) => (hint, Some(hint)),
 405             None       => (0, None)
 406         }
 407     }
 408 }
 409
 410 #[unstable(feature = "fused", issue = "35602")]
 411 #[allow(deprecated)]
 412 impl<A: Step + Clone> FusedIterator for StepBy<A, ops::Range<A>> {}
 413
 414 #[unstable(feature = "inclusive_range",
 415            reason = "recently added, follows RFC",
 416            issue = "28237")]
 417 #[allow(deprecated)]
 418 impl<A: Step + Clone> Iterator for StepBy<A, ops::RangeInclusive<A>> {
 419     type Item = A;
 420
 421     #[inline]
 422     fn next(&mut self) -> Option<A> {
 423         let rev = self.step_by.is_negative();
 424
 425         if (rev && self.range.start >= self.range.end) ||
 426            (!rev && self.range.start <= self.range.end)
 427         {
 428             match self.range.start.step(&self.step_by) {
 429                 Some(n) => {
 430                     Some(mem::replace(&mut self.range.start, n))
 431                 },
 432                 None => {
 433                     let last = self.range.start.replace_one();
 434                     self.range.end.replace_zero();
 435                     self.step_by.replace_one();
 436                     Some(last)
 437                 },
 438             }
 439         }
 440         else {
 441             None
 442         }
 443     }
 444
 445     #[inline]
 446     fn size_hint(&self) -> (usize, Option<usize>) {
 447         match Step::steps_between(&self.range.start,
 448                                   &self.range.end,
 449                                   &self.step_by) {
 450             Some(hint) => (hint.saturating_add(1), hint.checked_add(1)),
 451             None       => (0, None)
 452         }
 453     }
 454 }
 455
 456 #[unstable(feature = "fused", issue = "35602")]
 457 #[allow(deprecated)]
 458 impl<A: Step + Clone> FusedIterator for StepBy<A, ops::RangeInclusive<A>> {}
 459
 460 macro_rules! range_exact_iter_impl {
 461     ($($t:ty)*) => ($(
 462         #[stable(feature = "rust1", since = "1.0.0")]
 463         impl ExactSizeIterator for ops::Range<$t> { }
 464     )*)
 465 }
 466
 467 macro_rules! range_incl_exact_iter_impl {
 468     ($($t:ty)*) => ($(
 469         #[unstable(feature = "inclusive_range",
 470                    reason = "recently added, follows RFC",
 471                    issue = "28237")]
 472         impl ExactSizeIterator for ops::RangeInclusive<$t> { }
 473     )*)
 474 }
 475
 476 macro_rules! range_trusted_len_impl {
 477     ($($t:ty)*) => ($(
 478         #[unstable(feature = "trusted_len", issue = "37572")]
 479         unsafe impl TrustedLen for ops::Range<$t> { }
 480     )*)
 481 }
 482
 483 macro_rules! range_incl_trusted_len_impl {
 484     ($($t:ty)*) => ($(
 485         #[unstable(feature = "inclusive_range",
 486                    reason = "recently added, follows RFC",
 487                    issue = "28237")]
 488         unsafe impl TrustedLen for ops::RangeInclusive<$t> { }
 489     )*)
 490 }
 491
 492 #[stable(feature = "rust1", since = "1.0.0")]
 493 impl<A: Step> Iterator for ops::Range<A> where
 494     for<'a> &'a A: Add<&'a A, Output = A>
 495 {
 496     type Item = A;
 497
 498     #[inline]
 499     fn next(&mut self) -> Option<A> {
 500         if self.start < self.end {
 501             let mut n = self.start.add_one();
 502             mem::swap(&mut n, &mut self.start);
 503             Some(n)
 504         } else {
 505             None
 506         }
 507     }
 508
 509     #[inline]
 510     fn size_hint(&self) -> (usize, Option<usize>) {
 511         match Step::steps_between_by_one(&self.start, &self.end) {
 512             Some(hint) => (hint, Some(hint)),
 513             None => (0, None)
 514         }
 515     }
 516 }
 517
 518 // These macros generate `ExactSizeIterator` impls for various range types.
 519 // Range<{u,i}64> and RangeInclusive<{u,i}{32,64,size}> are excluded
 520 // because they cannot guarantee having a length <= usize::MAX, which is
 521 // required by ExactSizeIterator.
 522 range_exact_iter_impl!(usize u8 u16 u32 isize i8 i16 i32);
 523 range_incl_exact_iter_impl!(u8 u16 i8 i16);
 524
 525 // These macros generate `TrustedLen` impls.
 526 //
 527 // They need to guarantee that .size_hint() is either exact, or that
 528 // the upper bound is None when it does not fit the type limits.
 529 range_trusted_len_impl!(usize isize u8 i8 u16 i16 u32 i32 i64 u64);
 530 range_incl_trusted_len_impl!(usize isize u8 i8 u16 i16 u32 i32 i64 u64);
 531
 532 #[stable(feature = "rust1", since = "1.0.0")]
 533 impl<A: Step + Clone> DoubleEndedIterator for ops::Range<A> where
 534     for<'a> &'a A: Add<&'a A, Output = A>,
 535     for<'a> &'a A: Sub<&'a A, Output = A>
 536 {
 537     #[inline]
 538     fn next_back(&mut self) -> Option<A> {
 539         if self.start < self.end {
 540             self.end = self.end.sub_one();
 541             Some(self.end.clone())
 542         } else {
 543             None
 544         }
 545     }
 546 }
 547
 548 #[unstable(feature = "fused", issue = "35602")]
 549 impl<A> FusedIterator for ops::Range<A>
 550     where A: Step, for<'a> &'a A: Add<&'a A, Output = A> {}
 551
 552 #[stable(feature = "rust1", since = "1.0.0")]
 553 impl<A: Step> Iterator for ops::RangeFrom<A> where
 554     for<'a> &'a A: Add<&'a A, Output = A>
 555 {
 556     type Item = A;
 557
 558     #[inline]
 559     fn next(&mut self) -> Option<A> {
 560         let mut n = self.start.add_one();
 561         mem::swap(&mut n, &mut self.start);
 562         Some(n)
 563     }
 564
 565     #[inline]
 566     fn size_hint(&self) -> (usize, Option<usize>) {
 567         (usize::MAX, None)
 568     }
 569 }
 570
 571 #[unstable(feature = "fused", issue = "35602")]
 572 impl<A> FusedIterator for ops::RangeFrom<A>
 573     where A: Step, for<'a> &'a A: Add<&'a A, Output = A> {}
 574
 575 #[unstable(feature = "inclusive_range", reason = "recently added, follows RFC", issue = "28237")]
 576 impl<A: Step> Iterator for ops::RangeInclusive<A> where
 577     for<'a> &'a A: Add<&'a A, Output = A>
 578 {
 579     type Item = A;
 580
 581     #[inline]
 582     fn next(&mut self) -> Option<A> {
 583         use cmp::Ordering::*;
 584
 585         match self.start.partial_cmp(&self.end) {
 586             Some(Less) => {
 587                 let n = self.start.add_one();
 588                 Some(mem::replace(&mut self.start, n))
 589             },
 590             Some(Equal) => {
 591                 let last = self.start.replace_one();
 592                 self.end.replace_zero();
 593                 Some(last)
 594             },
 595             _ => None,
 596         }
 597     }
 598
 599     #[inline]
 600     fn size_hint(&self) -> (usize, Option<usize>) {
 601         if !(self.start <= self.end) {
 602             return (0, Some(0));
 603         }
 604
 605         match Step::steps_between_by_one(&self.start, &self.end) {
 606             Some(hint) => (hint.saturating_add(1), hint.checked_add(1)),
 607             None => (0, None),
 608         }
 609     }
 610 }
 611
 612 #[unstable(feature = "inclusive_range", reason = "recently added, follows RFC", issue = "28237")]
 613 impl<A: Step> DoubleEndedIterator for ops::RangeInclusive<A> where
 614     for<'a> &'a A: Add<&'a A, Output = A>,
 615     for<'a> &'a A: Sub<&'a A, Output = A>
 616 {
 617     #[inline]
 618     fn next_back(&mut self) -> Option<A> {
 619         use cmp::Ordering::*;
 620
 621         match self.start.partial_cmp(&self.end) {
 622             Some(Less) => {
 623                 let n = self.end.sub_one();
 624                 Some(mem::replace(&mut self.end, n))
 625             },
 626             Some(Equal) => {
 627                 let last = self.end.replace_zero();
 628                 self.start.replace_one();
 629                 Some(last)
 630             },
 631             _ => None,
 632         }
 633     }
 634 }
 635
 636 #[unstable(feature = "fused", issue = "35602")]
 637 impl<A> FusedIterator for ops::RangeInclusive<A>
 638     where A: Step, for<'a> &'a A: Add<&'a A, Output = A> {}