src/vendor/num-iter/src/lib.rs

   1 // Copyright 2013-2014 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 //! External iterators for generic mathematics
  12 #![doc(html_logo_url = "https://rust-num.github.io/num/rust-logo-128x128-blk-v2.png",
  13        html_favicon_url = "https://rust-num.github.io/num/favicon.ico",
  14        html_root_url = "https://rust-num.github.io/num/",
  15        html_playground_url = "http://play.integer32.com/")]
  16
  17 extern crate num_traits as traits;
  18 extern crate num_integer as integer;
  19
  20 use integer::Integer;
  21 use traits::{Zero, One, CheckedAdd, ToPrimitive};
  22 use std::ops::{Add, Sub};
  23
  24 /// An iterator over the range [start, stop)
  25 #[derive(Clone)]
  26 pub struct Range<A> {
  27     state: A,
  28     stop: A,
  29     one: A
  30 }
  31
  32 /// Returns an iterator over the given range [start, stop) (that is, starting
  33 /// at start (inclusive), and ending at stop (exclusive)).
  34 ///
  35 /// # Example
  36 ///
  37 /// ```rust
  38 /// let array = [0, 1, 2, 3, 4];
  39 ///
  40 /// for i in num_iter::range(0, 5) {
  41 ///     println!("{}", i);
  42 ///     assert_eq!(i,  array[i]);
  43 /// }
  44 /// ```
  45 #[inline]
  46 pub fn range<A>(start: A, stop: A) -> Range<A>
  47     where A: Add<A, Output = A> + PartialOrd + Clone + One
  48 {
  49     Range{state: start, stop: stop, one: One::one()}
  50 }
  51
  52 // FIXME: rust-lang/rust#10414: Unfortunate type bound
  53 impl<A> Iterator for Range<A>
  54     where A: Add<A, Output = A> + PartialOrd + Clone + ToPrimitive
  55 {
  56     type Item = A;
  57
  58     #[inline]
  59     fn next(&mut self) -> Option<A> {
  60         if self.state < self.stop {
  61             let result = self.state.clone();
  62             self.state = self.state.clone() + self.one.clone();
  63             Some(result)
  64         } else {
  65             None
  66         }
  67     }
  68
  69     #[inline]
  70     fn size_hint(&self) -> (usize, Option<usize>) {
  71         // This first checks if the elements are representable as i64. If they aren't, try u64 (to
  72         // handle cases like range(huge, huger)). We don't use usize/int because the difference of
  73         // the i64/u64 might lie within their range.
  74         let bound = match self.state.to_i64() {
  75             Some(a) => {
  76                 let sz = self.stop.to_i64().map(|b| b.checked_sub(a));
  77                 match sz {
  78                     Some(Some(bound)) => bound.to_usize(),
  79                     _ => None,
  80                 }
  81             },
  82             None => match self.state.to_u64() {
  83                 Some(a) => {
  84                     let sz = self.stop.to_u64().map(|b| b.checked_sub(a));
  85                     match sz {
  86                         Some(Some(bound)) => bound.to_usize(),
  87                         _ => None
  88                     }
  89                 },
  90                 None => None
  91             }
  92         };
  93
  94         match bound {
  95             Some(b) => (b, Some(b)),
  96             // Standard fallback for unbounded/unrepresentable bounds
  97             None => (0, None)
  98         }
  99     }
 100 }
 101
 102 /// `Integer` is required to ensure the range will be the same regardless of
 103 /// the direction it is consumed.
 104 impl<A> DoubleEndedIterator for Range<A>
 105     where A: Integer + Clone + ToPrimitive
 106 {
 107     #[inline]
 108     fn next_back(&mut self) -> Option<A> {
 109         if self.stop > self.state {
 110             self.stop = self.stop.clone() - self.one.clone();
 111             Some(self.stop.clone())
 112         } else {
 113             None
 114         }
 115     }
 116 }
 117
 118 /// An iterator over the range [start, stop]
 119 #[derive(Clone)]
 120 pub struct RangeInclusive<A> {
 121     range: Range<A>,
 122     done: bool,
 123 }
 124
 125 /// Return an iterator over the range [start, stop]
 126 #[inline]
 127 pub fn range_inclusive<A>(start: A, stop: A) -> RangeInclusive<A>
 128     where A: Add<A, Output = A> + PartialOrd + Clone + One
 129 {
 130     RangeInclusive{range: range(start, stop), done: false}
 131 }
 132
 133 impl<A> Iterator for RangeInclusive<A>
 134     where A: Add<A, Output = A> + PartialOrd + Clone + ToPrimitive
 135 {
 136     type Item = A;
 137
 138     #[inline]
 139     fn next(&mut self) -> Option<A> {
 140         match self.range.next() {
 141             Some(x) => Some(x),
 142             None => {
 143                 if !self.done && self.range.state == self.range.stop {
 144                     self.done = true;
 145                     Some(self.range.stop.clone())
 146                 } else {
 147                     None
 148                 }
 149             }
 150         }
 151     }
 152
 153     #[inline]
 154     fn size_hint(&self) -> (usize, Option<usize>) {
 155         let (lo, hi) = self.range.size_hint();
 156         if self.done {
 157             (lo, hi)
 158         } else {
 159             let lo = lo.saturating_add(1);
 160             let hi = match hi {
 161                 Some(x) => x.checked_add(1),
 162                 None => None
 163             };
 164             (lo, hi)
 165         }
 166     }
 167 }
 168
 169 impl<A> DoubleEndedIterator for RangeInclusive<A>
 170     where A: Sub<A, Output = A> + Integer + Clone + ToPrimitive
 171 {
 172     #[inline]
 173     fn next_back(&mut self) -> Option<A> {
 174         if self.range.stop > self.range.state {
 175             let result = self.range.stop.clone();
 176             self.range.stop = self.range.stop.clone() - self.range.one.clone();
 177             Some(result)
 178         } else if !self.done && self.range.state == self.range.stop {
 179             self.done = true;
 180             Some(self.range.stop.clone())
 181         } else {
 182             None
 183         }
 184     }
 185 }
 186
 187 /// An iterator over the range [start, stop) by `step`. It handles overflow by stopping.
 188 #[derive(Clone)]
 189 pub struct RangeStep<A> {
 190     state: A,
 191     stop: A,
 192     step: A,
 193     rev: bool,
 194 }
 195
 196 /// Return an iterator over the range [start, stop) by `step`. It handles overflow by stopping.
 197 #[inline]
 198 pub fn range_step<A>(start: A, stop: A, step: A) -> RangeStep<A>
 199     where A: CheckedAdd + PartialOrd + Clone + Zero
 200 {
 201     let rev = step < Zero::zero();
 202     RangeStep{state: start, stop: stop, step: step, rev: rev}
 203 }
 204
 205 impl<A> Iterator for RangeStep<A>
 206     where A: CheckedAdd + PartialOrd + Clone
 207 {
 208     type Item = A;
 209
 210     #[inline]
 211     fn next(&mut self) -> Option<A> {
 212         if (self.rev && self.state > self.stop) || (!self.rev && self.state < self.stop) {
 213             let result = self.state.clone();
 214             match self.state.checked_add(&self.step) {
 215                 Some(x) => self.state = x,
 216                 None => self.state = self.stop.clone()
 217             }
 218             Some(result)
 219         } else {
 220             None
 221         }
 222     }
 223 }
 224
 225 /// An iterator over the range [start, stop] by `step`. It handles overflow by stopping.
 226 #[derive(Clone)]
 227 pub struct RangeStepInclusive<A> {
 228     state: A,
 229     stop: A,
 230     step: A,
 231     rev: bool,
 232     done: bool,
 233 }
 234
 235 /// Return an iterator over the range [start, stop] by `step`. It handles overflow by stopping.
 236 #[inline]
 237 pub fn range_step_inclusive<A>(start: A, stop: A, step: A) -> RangeStepInclusive<A>
 238     where A: CheckedAdd + PartialOrd + Clone + Zero
 239 {
 240     let rev = step < Zero::zero();
 241     RangeStepInclusive{state: start, stop: stop, step: step, rev: rev, done: false}
 242 }
 243
 244 impl<A> Iterator for RangeStepInclusive<A>
 245     where A: CheckedAdd + PartialOrd + Clone + PartialEq
 246 {
 247     type Item = A;
 248
 249     #[inline]
 250     fn next(&mut self) -> Option<A> {
 251         if !self.done && ((self.rev && self.state >= self.stop) ||
 252                           (!self.rev && self.state <= self.stop)) {
 253             let result = self.state.clone();
 254             match self.state.checked_add(&self.step) {
 255                 Some(x) => self.state = x,
 256                 None => self.done = true
 257             }
 258             Some(result)
 259         } else {
 260             None
 261         }
 262     }
 263 }
 264
 265 #[cfg(test)]
 266 mod tests {
 267     use std::usize;
 268     use std::ops::{Add, Mul};
 269     use std::cmp::Ordering;
 270     use traits::{One, ToPrimitive};
 271
 272     #[test]
 273     fn test_range() {
 274         /// A mock type to check Range when ToPrimitive returns None
 275         struct Foo;
 276
 277         impl ToPrimitive for Foo {
 278             fn to_i64(&self) -> Option<i64> { None }
 279             fn to_u64(&self) -> Option<u64> { None }
 280         }
 281
 282         impl Add<Foo> for Foo {
 283             type Output = Foo;
 284
 285             fn add(self, _: Foo) -> Foo {
 286                 Foo
 287             }
 288         }
 289
 290         impl PartialEq for Foo {
 291             fn eq(&self, _: &Foo) -> bool {
 292                 true
 293             }
 294         }
 295
 296         impl PartialOrd for Foo {
 297             fn partial_cmp(&self, _: &Foo) -> Option<Ordering> {
 298                 None
 299             }
 300         }
 301
 302         impl Clone for Foo {
 303             fn clone(&self) -> Foo {
 304                 Foo
 305             }
 306         }
 307
 308         impl Mul<Foo> for Foo {
 309             type Output = Foo;
 310
 311             fn mul(self, _: Foo) -> Foo {
 312                 Foo
 313             }
 314         }
 315
 316         impl One for Foo {
 317             fn one() -> Foo {
 318                 Foo
 319             }
 320         }
 321
 322         assert!(super::range(0, 5).collect::<Vec<isize>>() == vec![0, 1, 2, 3, 4]);
 323         assert!(super::range(-10, -1).collect::<Vec<isize>>() ==
 324                 vec![-10, -9, -8, -7, -6, -5, -4, -3, -2]);
 325         assert!(super::range(0, 5).rev().collect::<Vec<isize>>() == vec![4, 3, 2, 1, 0]);
 326         assert_eq!(super::range(200, -5).count(), 0);
 327         assert_eq!(super::range(200, -5).rev().count(), 0);
 328         assert_eq!(super::range(200, 200).count(), 0);
 329         assert_eq!(super::range(200, 200).rev().count(), 0);
 330
 331         assert_eq!(super::range(0, 100).size_hint(), (100, Some(100)));
 332         // this test is only meaningful when sizeof usize < sizeof u64
 333         assert_eq!(super::range(usize::MAX - 1, usize::MAX).size_hint(), (1, Some(1)));
 334         assert_eq!(super::range(-10, -1).size_hint(), (9, Some(9)));
 335     }
 336
 337     #[test]
 338     fn test_range_inclusive() {
 339         assert!(super::range_inclusive(0, 5).collect::<Vec<isize>>() ==
 340                 vec![0, 1, 2, 3, 4, 5]);
 341         assert!(super::range_inclusive(0, 5).rev().collect::<Vec<isize>>() ==
 342                 vec![5, 4, 3, 2, 1, 0]);
 343         assert_eq!(super::range_inclusive(200, -5).count(), 0);
 344         assert_eq!(super::range_inclusive(200, -5).rev().count(), 0);
 345         assert!(super::range_inclusive(200, 200).collect::<Vec<isize>>() == vec![200]);
 346         assert!(super::range_inclusive(200, 200).rev().collect::<Vec<isize>>() == vec![200]);
 347     }
 348
 349     #[test]
 350     fn test_range_step() {
 351         assert!(super::range_step(0, 20, 5).collect::<Vec<isize>>() ==
 352                 vec![0, 5, 10, 15]);
 353         assert!(super::range_step(20, 0, -5).collect::<Vec<isize>>() ==
 354                 vec![20, 15, 10, 5]);
 355         assert!(super::range_step(20, 0, -6).collect::<Vec<isize>>() ==
 356                 vec![20, 14, 8, 2]);
 357         assert!(super::range_step(200u8, 255, 50).collect::<Vec<u8>>() ==
 358                 vec![200u8, 250]);
 359         assert!(super::range_step(200, -5, 1).collect::<Vec<isize>>() == vec![]);
 360         assert!(super::range_step(200, 200, 1).collect::<Vec<isize>>() == vec![]);
 361     }
 362
 363     #[test]
 364     fn test_range_step_inclusive() {
 365         assert!(super::range_step_inclusive(0, 20, 5).collect::<Vec<isize>>() ==
 366                 vec![0, 5, 10, 15, 20]);
 367         assert!(super::range_step_inclusive(20, 0, -5).collect::<Vec<isize>>() ==
 368                 vec![20, 15, 10, 5, 0]);
 369         assert!(super::range_step_inclusive(20, 0, -6).collect::<Vec<isize>>() ==
 370                 vec![20, 14, 8, 2]);
 371         assert!(super::range_step_inclusive(200u8, 255, 50).collect::<Vec<u8>>() ==
 372                 vec![200u8, 250]);
 373         assert!(super::range_step_inclusive(200, -5, 1).collect::<Vec<isize>>() ==
 374                 vec![]);
 375         assert!(super::range_step_inclusive(200, 200, 1).collect::<Vec<isize>>() ==
 376                 vec![200]);
 377     }
 378 }