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;
  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 = "27741")]
  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 = "27741")]
  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, 0)
  90             }
  91
  92             #[inline]
  93             fn replace_zero(&mut self) -> Self {
  94                 mem::replace(self, 1)
  95             }
  96
  97             #[inline]
  98             fn add_one(&self) -> Self {
  99                 *self + 1
 100             }
 101
 102             #[inline]
 103             fn sub_one(&self) -> Self {
 104                 *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 = "27741")]
 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, 0)
 161             }
 162
 163             #[inline]
 164             fn replace_zero(&mut self) -> Self {
 165                 mem::replace(self, 1)
 166             }
 167
 168             #[inline]
 169             fn add_one(&self) -> Self {
 170                 *self + 1
 171             }
 172
 173             #[inline]
 174             fn sub_one(&self) -> Self {
 175                 *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 = "27741")]
 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, 0)
 210             }
 211
 212             #[inline]
 213             fn replace_zero(&mut self) -> Self {
 214                 mem::replace(self, 1)
 215             }
 216
 217             #[inline]
 218             fn add_one(&self) -> Self {
 219                 *self + 1
 220             }
 221
 222             #[inline]
 223             fn sub_one(&self) -> Self {
 224                 *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
 246 /// An adapter for stepping range iterators by a custom amount.
 247 ///
 248 /// The resulting iterator handles overflow by stopping. The `A`
 249 /// parameter is the type being iterated over, while `R` is the range
 250 /// type (usually one of `std::ops::{Range, RangeFrom, RangeInclusive}`.
 251 #[derive(Clone, Debug)]
 252 #[unstable(feature = "step_by", reason = "recent addition",
 253            issue = "27741")]
 254 pub struct StepBy<A, R> {
 255     step_by: A,
 256     range: R,
 257 }
 258
 259 impl<A: Step> ops::RangeFrom<A> {
 260     /// Creates an iterator starting at the same point, but stepping by
 261     /// the given amount at each iteration.
 262     ///
 263     /// # Examples
 264     ///
 265     /// ```
 266     /// #![feature(step_by)]
 267     /// fn main() {
 268     ///     let result: Vec<_> = (0..).step_by(2).take(5).collect();
 269     ///     assert_eq!(result, vec![0, 2, 4, 6, 8]);
 270     /// }
 271     /// ```
 272     #[unstable(feature = "step_by", reason = "recent addition",
 273                issue = "27741")]
 274     pub fn step_by(self, by: A) -> StepBy<A, Self> {
 275         StepBy {
 276             step_by: by,
 277             range: self
 278         }
 279     }
 280 }
 281
 282 impl<A: Step> ops::Range<A> {
 283     /// Creates an iterator with the same range, but stepping by the
 284     /// given amount at each iteration.
 285     ///
 286     /// The resulting iterator handles overflow by stopping.
 287     ///
 288     /// # Examples
 289     ///
 290     /// ```
 291     /// #![feature(step_by)]
 292     /// fn main() {
 293     ///     let result: Vec<_> = (0..10).step_by(2).collect();
 294     ///     assert_eq!(result, vec![0, 2, 4, 6, 8]);
 295     /// }
 296     /// ```
 297     #[unstable(feature = "step_by", reason = "recent addition",
 298                issue = "27741")]
 299     pub fn step_by(self, by: A) -> StepBy<A, Self> {
 300         StepBy {
 301             step_by: by,
 302             range: self
 303         }
 304     }
 305 }
 306
 307 impl<A: Step> ops::RangeInclusive<A> {
 308     /// Creates an iterator with the same range, but stepping by the
 309     /// given amount at each iteration.
 310     ///
 311     /// The resulting iterator handles overflow by stopping.
 312     ///
 313     /// # Examples
 314     ///
 315     /// ```
 316     /// #![feature(step_by, inclusive_range_syntax)]
 317     ///
 318     /// let result: Vec<_> = (0...10).step_by(2).collect();
 319     /// assert_eq!(result, vec![0, 2, 4, 6, 8, 10]);
 320     /// ```
 321     #[unstable(feature = "step_by", reason = "recent addition",
 322                issue = "27741")]
 323     pub fn step_by(self, by: A) -> StepBy<A, Self> {
 324         StepBy {
 325             step_by: by,
 326             range: self
 327         }
 328     }
 329 }
 330
 331 #[stable(feature = "rust1", since = "1.0.0")]
 332 impl<A> Iterator for StepBy<A, ops::RangeFrom<A>> where
 333     A: Clone,
 334     for<'a> &'a A: Add<&'a A, Output = A>
 335 {
 336     type Item = A;
 337
 338     #[inline]
 339     fn next(&mut self) -> Option<A> {
 340         let mut n = &self.range.start + &self.step_by;
 341         mem::swap(&mut n, &mut self.range.start);
 342         Some(n)
 343     }
 344
 345     #[inline]
 346     fn size_hint(&self) -> (usize, Option<usize>) {
 347         (usize::MAX, None) // Too bad we can't specify an infinite lower bound
 348     }
 349 }
 350
 351 #[unstable(feature = "fused", issue = "35602")]
 352 impl<A> FusedIterator for StepBy<A, ops::RangeFrom<A>>
 353     where A: Clone, for<'a> &'a A: Add<&'a A, Output = A> {}
 354
 355 #[stable(feature = "rust1", since = "1.0.0")]
 356 impl<A: Step + Clone> Iterator for StepBy<A, ops::Range<A>> {
 357     type Item = A;
 358
 359     #[inline]
 360     fn next(&mut self) -> Option<A> {
 361         let rev = self.step_by.is_negative();
 362         if (rev && self.range.start > self.range.end) ||
 363            (!rev && self.range.start < self.range.end)
 364         {
 365             match self.range.start.step(&self.step_by) {
 366                 Some(mut n) => {
 367                     mem::swap(&mut self.range.start, &mut n);
 368                     Some(n)
 369                 },
 370                 None => {
 371                     let mut n = self.range.end.clone();
 372                     mem::swap(&mut self.range.start, &mut n);
 373                     Some(n)
 374                 }
 375             }
 376         } else {
 377             None
 378         }
 379     }
 380
 381     #[inline]
 382     fn size_hint(&self) -> (usize, Option<usize>) {
 383         match Step::steps_between(&self.range.start,
 384                                   &self.range.end,
 385                                   &self.step_by) {
 386             Some(hint) => (hint, Some(hint)),
 387             None       => (0, None)
 388         }
 389     }
 390 }
 391
 392 #[unstable(feature = "fused", issue = "35602")]
 393 impl<A: Step + Clone> FusedIterator for StepBy<A, ops::Range<A>> {}
 394
 395 #[unstable(feature = "inclusive_range",
 396            reason = "recently added, follows RFC",
 397            issue = "28237")]
 398 impl<A: Step + Clone> Iterator for StepBy<A, ops::RangeInclusive<A>> {
 399     type Item = A;
 400
 401     #[inline]
 402     fn next(&mut self) -> Option<A> {
 403         use ops::RangeInclusive::*;
 404
 405         // this function has a sort of odd structure due to borrowck issues
 406         // we may need to replace self.range, so borrows of start and end need to end early
 407
 408         let (finishing, n) = match self.range {
 409             Empty { .. } => return None, // empty iterators yield no values
 410
 411             NonEmpty { ref mut start, ref mut end } => {
 412                 let rev = self.step_by.is_negative();
 413
 414                 // march start towards (maybe past!) end and yield the old value
 415                 if (rev && start >= end) ||
 416                    (!rev && start <= end)
 417                 {
 418                     match start.step(&self.step_by) {
 419                         Some(mut n) => {
 420                             mem::swap(start, &mut n);
 421                             (None, Some(n)) // yield old value, remain non-empty
 422                         },
 423                         None => {
 424                             let mut n = end.clone();
 425                             mem::swap(start, &mut n);
 426                             (None, Some(n)) // yield old value, remain non-empty
 427                         }
 428                     }
 429                 } else {
 430                     // found range in inconsistent state (start at or past end), so become empty
 431                     (Some(end.replace_zero()), None)
 432                 }
 433             }
 434         };
 435
 436         // turn into an empty iterator if we've reached the end
 437         if let Some(end) = finishing {
 438             self.range = Empty { at: end };
 439         }
 440
 441         n
 442     }
 443
 444     #[inline]
 445     fn size_hint(&self) -> (usize, Option<usize>) {
 446         use ops::RangeInclusive::*;
 447
 448         match self.range {
 449             Empty { .. } => (0, Some(0)),
 450
 451             NonEmpty { ref start, ref end } =>
 452                 match Step::steps_between(start,
 453                                           end,
 454                                           &self.step_by) {
 455                     Some(hint) => (hint.saturating_add(1), hint.checked_add(1)),
 456                     None       => (0, None)
 457                 }
 458         }
 459     }
 460 }
 461
 462 #[unstable(feature = "fused", issue = "35602")]
 463 impl<A: Step + Clone> FusedIterator for StepBy<A, ops::RangeInclusive<A>> {}
 464
 465 macro_rules! range_exact_iter_impl {
 466     ($($t:ty)*) => ($(
 467         #[stable(feature = "rust1", since = "1.0.0")]
 468         impl ExactSizeIterator for ops::Range<$t> { }
 469
 470         #[unstable(feature = "inclusive_range",
 471                    reason = "recently added, follows RFC",
 472                    issue = "28237")]
 473         impl ExactSizeIterator for ops::RangeInclusive<$t> { }
 474     )*)
 475 }
 476
 477 #[stable(feature = "rust1", since = "1.0.0")]
 478 impl<A: Step> Iterator for ops::Range<A> where
 479     for<'a> &'a A: Add<&'a A, Output = A>
 480 {
 481     type Item = A;
 482
 483     #[inline]
 484     fn next(&mut self) -> Option<A> {
 485         if self.start < self.end {
 486             let mut n = self.start.add_one();
 487             mem::swap(&mut n, &mut self.start);
 488             Some(n)
 489         } else {
 490             None
 491         }
 492     }
 493
 494     #[inline]
 495     fn size_hint(&self) -> (usize, Option<usize>) {
 496         match Step::steps_between_by_one(&self.start, &self.end) {
 497             Some(hint) => (hint, Some(hint)),
 498             None => (0, None)
 499         }
 500     }
 501 }
 502
 503 // Ranges of u64 and i64 are excluded because they cannot guarantee having
 504 // a length <= usize::MAX, which is required by ExactSizeIterator.
 505 range_exact_iter_impl!(usize u8 u16 u32 isize i8 i16 i32);
 506
 507 #[stable(feature = "rust1", since = "1.0.0")]
 508 impl<A: Step + Clone> DoubleEndedIterator for ops::Range<A> where
 509     for<'a> &'a A: Add<&'a A, Output = A>,
 510     for<'a> &'a A: Sub<&'a A, Output = A>
 511 {
 512     #[inline]
 513     fn next_back(&mut self) -> Option<A> {
 514         if self.start < self.end {
 515             self.end = self.end.sub_one();
 516             Some(self.end.clone())
 517         } else {
 518             None
 519         }
 520     }
 521 }
 522
 523 #[unstable(feature = "fused", issue = "35602")]
 524 impl<A> FusedIterator for ops::Range<A>
 525     where A: Step, for<'a> &'a A: Add<&'a A, Output = A> {}
 526
 527 #[stable(feature = "rust1", since = "1.0.0")]
 528 impl<A: Step> Iterator for ops::RangeFrom<A> where
 529     for<'a> &'a A: Add<&'a A, Output = A>
 530 {
 531     type Item = A;
 532
 533     #[inline]
 534     fn next(&mut self) -> Option<A> {
 535         let mut n = self.start.add_one();
 536         mem::swap(&mut n, &mut self.start);
 537         Some(n)
 538     }
 539 }
 540
 541 #[unstable(feature = "fused", issue = "35602")]
 542 impl<A> FusedIterator for ops::RangeFrom<A>
 543     where A: Step, for<'a> &'a A: Add<&'a A, Output = A> {}
 544
 545 #[unstable(feature = "inclusive_range", reason = "recently added, follows RFC", issue = "28237")]
 546 impl<A: Step> Iterator for ops::RangeInclusive<A> where
 547     for<'a> &'a A: Add<&'a A, Output = A>
 548 {
 549     type Item = A;
 550
 551     #[inline]
 552     fn next(&mut self) -> Option<A> {
 553         use ops::RangeInclusive::*;
 554
 555         // this function has a sort of odd structure due to borrowck issues
 556         // we may need to replace self, so borrows of self.start and self.end need to end early
 557
 558         let (finishing, n) = match *self {
 559             Empty { .. } => (None, None), // empty iterators yield no values
 560
 561             NonEmpty { ref mut start, ref mut end } => {
 562                 if start == end {
 563                     (Some(end.replace_one()), Some(start.replace_one()))
 564                 } else if start < end {
 565                     let mut n = start.add_one();
 566                     mem::swap(&mut n, start);
 567
 568                     // if the iterator is done iterating, it will change from
 569                     // NonEmpty to Empty to avoid unnecessary drops or clones,
 570                     // we'll reuse either start or end (they are equal now, so
 571                     // it doesn't matter which) to pull out end, we need to swap
 572                     // something back in
 573
 574                     (if n == *end { Some(end.replace_one()) } else { None },
 575                     // ^ are we done yet?
 576                     Some(n)) // < the value to output
 577                 } else {
 578                     (Some(start.replace_one()), None)
 579                 }
 580             }
 581         };
 582
 583         // turn into an empty iterator if this is the last value
 584         if let Some(end) = finishing {
 585             *self = Empty { at: end };
 586         }
 587
 588         n
 589     }
 590
 591     #[inline]
 592     fn size_hint(&self) -> (usize, Option<usize>) {
 593         use ops::RangeInclusive::*;
 594
 595         match *self {
 596             Empty { .. } => (0, Some(0)),
 597
 598             NonEmpty { ref start, ref end } =>
 599                 match Step::steps_between_by_one(start, end) {
 600                     Some(hint) => (hint.saturating_add(1), hint.checked_add(1)),
 601                     None => (0, None),
 602                 }
 603         }
 604     }
 605 }
 606
 607 #[unstable(feature = "inclusive_range", reason = "recently added, follows RFC", issue = "28237")]
 608 impl<A: Step> DoubleEndedIterator for ops::RangeInclusive<A> where
 609     for<'a> &'a A: Add<&'a A, Output = A>,
 610     for<'a> &'a A: Sub<&'a A, Output = A>
 611 {
 612     #[inline]
 613     fn next_back(&mut self) -> Option<A> {
 614         use ops::RangeInclusive::*;
 615
 616         // see Iterator::next for comments
 617
 618         let (finishing, n) = match *self {
 619             Empty { .. } => return None,
 620
 621             NonEmpty { ref mut start, ref mut end } => {
 622                 if start == end {
 623                     (Some(start.replace_one()), Some(end.replace_one()))
 624                 } else if start < end {
 625                     let mut n = end.sub_one();
 626                     mem::swap(&mut n, end);
 627
 628                     (if n == *start { Some(start.replace_one()) } else { None },
 629                      Some(n))
 630                 } else {
 631                     (Some(end.replace_one()), None)
 632                 }
 633             }
 634         };
 635
 636         if let Some(start) = finishing {
 637             *self = Empty { at: start };
 638         }
 639
 640         n
 641     }
 642 }
 643
 644 #[unstable(feature = "fused", issue = "35602")]
 645 impl<A> FusedIterator for ops::RangeInclusive<A>
 646     where A: Step, for<'a> &'a A: Add<&'a A, Output = A> {}