src/libcore/ops/range.rs

   1 use crate::fmt;
   2 use crate::hash::{Hash, Hasher};
   3
   4 /// An unbounded range (`..`).
   5 ///
   6 /// `RangeFull` is primarily used as a [slicing index], its shorthand is `..`.
   7 /// It cannot serve as an [`Iterator`] because it doesn't have a starting point.
   8 ///
   9 /// # Examples
  10 ///
  11 /// The `..` syntax is a `RangeFull`:
  12 ///
  13 /// ```
  14 /// assert_eq!((..), std::ops::RangeFull);
  15 /// ```
  16 ///
  17 /// It does not have an [`IntoIterator`] implementation, so you can't use it in
  18 /// a `for` loop directly. This won't compile:
  19 ///
  20 /// ```compile_fail,E0277
  21 /// for i in .. {
  22 ///    // ...
  23 /// }
  24 /// ```
  25 ///
  26 /// Used as a [slicing index], `RangeFull` produces the full array as a slice.
  27 ///
  28 /// ```
  29 /// let arr = [0, 1, 2, 3, 4];
  30 /// assert_eq!(arr[ ..  ], [0,1,2,3,4]);  // RangeFull
  31 /// assert_eq!(arr[ .. 3], [0,1,2    ]);
  32 /// assert_eq!(arr[ ..=3], [0,1,2,3  ]);
  33 /// assert_eq!(arr[1..  ], [  1,2,3,4]);
  34 /// assert_eq!(arr[1.. 3], [  1,2    ]);
  35 /// assert_eq!(arr[1..=3], [  1,2,3  ]);
  36 /// ```
  37 ///
  38 /// [`IntoIterator`]: ../iter/trait.Iterator.html
  39 /// [`Iterator`]: ../iter/trait.IntoIterator.html
  40 /// [slicing index]: ../slice/trait.SliceIndex.html
  41 #[doc(alias = "..")]
  42 #[derive(Copy, Clone, PartialEq, Eq, Hash)]
  43 #[stable(feature = "rust1", since = "1.0.0")]
  44 pub struct RangeFull;
  45
  46 #[stable(feature = "rust1", since = "1.0.0")]
  47 impl fmt::Debug for RangeFull {
  48     fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result {
  49         write!(fmt, "..")
  50     }
  51 }
  52
  53 /// A (half-open) range bounded inclusively below and exclusively above
  54 /// (`start..end`).
  55 ///
  56 /// The `Range` `start..end` contains all values with `x >= start` and
  57 /// `x < end`. It is empty unless `start < end`.
  58 ///
  59 /// # Examples
  60 ///
  61 /// ```
  62 /// assert_eq!((3..5), std::ops::Range { start: 3, end: 5 });
  63 /// assert_eq!(3 + 4 + 5, (3..6).sum());
  64 ///
  65 /// let arr = [0, 1, 2, 3, 4];
  66 /// assert_eq!(arr[ ..  ], [0,1,2,3,4]);
  67 /// assert_eq!(arr[ .. 3], [0,1,2    ]);
  68 /// assert_eq!(arr[ ..=3], [0,1,2,3  ]);
  69 /// assert_eq!(arr[1..  ], [  1,2,3,4]);
  70 /// assert_eq!(arr[1.. 3], [  1,2    ]);  // Range
  71 /// assert_eq!(arr[1..=3], [  1,2,3  ]);
  72 /// ```
  73 #[doc(alias = "..")]
  74 #[derive(Clone, PartialEq, Eq, Hash)] // not Copy -- see #27186
  75 #[stable(feature = "rust1", since = "1.0.0")]
  76 pub struct Range<Idx> {
  77     /// The lower bound of the range (inclusive).
  78     #[stable(feature = "rust1", since = "1.0.0")]
  79     pub start: Idx,
  80     /// The upper bound of the range (exclusive).
  81     #[stable(feature = "rust1", since = "1.0.0")]
  82     pub end: Idx,
  83 }
  84
  85 #[stable(feature = "rust1", since = "1.0.0")]
  86 impl<Idx: fmt::Debug> fmt::Debug for Range<Idx> {
  87     fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result {
  88         self.start.fmt(fmt)?;
  89         write!(fmt, "..")?;
  90         self.end.fmt(fmt)?;
  91         Ok(())
  92     }
  93 }
  94
  95 impl<Idx: PartialOrd<Idx>> Range<Idx> {
  96     /// Returns `true` if `item` is contained in the range.
  97     ///
  98     /// # Examples
  99     ///
 100     /// ```
 101     /// use std::f32;
 102     ///
 103     /// assert!(!(3..5).contains(&2));
 104     /// assert!( (3..5).contains(&3));
 105     /// assert!( (3..5).contains(&4));
 106     /// assert!(!(3..5).contains(&5));
 107     ///
 108     /// assert!(!(3..3).contains(&3));
 109     /// assert!(!(3..2).contains(&3));
 110     ///
 111     /// assert!( (0.0..1.0).contains(&0.5));
 112     /// assert!(!(0.0..1.0).contains(&f32::NAN));
 113     /// assert!(!(0.0..f32::NAN).contains(&0.5));
 114     /// assert!(!(f32::NAN..1.0).contains(&0.5));
 115     /// ```
 116     #[stable(feature = "range_contains", since = "1.35.0")]
 117     pub fn contains<U>(&self, item: &U) -> bool
 118     where
 119         Idx: PartialOrd<U>,
 120         U: ?Sized + PartialOrd<Idx>,
 121     {
 122         <Self as RangeBounds<Idx>>::contains(self, item)
 123     }
 124
 125     /// Returns `true` if the range contains no items.
 126     ///
 127     /// # Examples
 128     ///
 129     /// ```
 130     /// #![feature(range_is_empty)]
 131     ///
 132     /// assert!(!(3..5).is_empty());
 133     /// assert!( (3..3).is_empty());
 134     /// assert!( (3..2).is_empty());
 135     /// ```
 136     ///
 137     /// The range is empty if either side is incomparable:
 138     ///
 139     /// ```
 140     /// #![feature(range_is_empty)]
 141     ///
 142     /// use std::f32::NAN;
 143     /// assert!(!(3.0..5.0).is_empty());
 144     /// assert!( (3.0..NAN).is_empty());
 145     /// assert!( (NAN..5.0).is_empty());
 146     /// ```
 147     #[unstable(feature = "range_is_empty", reason = "recently added", issue = "48111")]
 148     pub fn is_empty(&self) -> bool {
 149         !(self.start < self.end)
 150     }
 151 }
 152
 153 /// A range only bounded inclusively below (`start..`).
 154 ///
 155 /// The `RangeFrom` `start..` contains all values with `x >= start`.
 156 ///
 157 /// *Note*: Currently, no overflow checking is done for the [`Iterator`]
 158 /// implementation; if you use an integer range and the integer overflows, it
 159 /// might panic in debug mode or create an endless loop in release mode. **This
 160 /// overflow behavior might change in the future.**
 161 ///
 162 /// # Examples
 163 ///
 164 /// ```
 165 /// assert_eq!((2..), std::ops::RangeFrom { start: 2 });
 166 /// assert_eq!(2 + 3 + 4, (2..).take(3).sum());
 167 ///
 168 /// let arr = [0, 1, 2, 3, 4];
 169 /// assert_eq!(arr[ ..  ], [0,1,2,3,4]);
 170 /// assert_eq!(arr[ .. 3], [0,1,2    ]);
 171 /// assert_eq!(arr[ ..=3], [0,1,2,3  ]);
 172 /// assert_eq!(arr[1..  ], [  1,2,3,4]);  // RangeFrom
 173 /// assert_eq!(arr[1.. 3], [  1,2    ]);
 174 /// assert_eq!(arr[1..=3], [  1,2,3  ]);
 175 /// ```
 176 ///
 177 /// [`Iterator`]: ../iter/trait.IntoIterator.html
 178 #[doc(alias = "..")]
 179 #[derive(Clone, PartialEq, Eq, Hash)] // not Copy -- see #27186
 180 #[stable(feature = "rust1", since = "1.0.0")]
 181 pub struct RangeFrom<Idx> {
 182     /// The lower bound of the range (inclusive).
 183     #[stable(feature = "rust1", since = "1.0.0")]
 184     pub start: Idx,
 185 }
 186
 187 #[stable(feature = "rust1", since = "1.0.0")]
 188 impl<Idx: fmt::Debug> fmt::Debug for RangeFrom<Idx> {
 189     fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result {
 190         self.start.fmt(fmt)?;
 191         write!(fmt, "..")?;
 192         Ok(())
 193     }
 194 }
 195
 196 impl<Idx: PartialOrd<Idx>> RangeFrom<Idx> {
 197     /// Returns `true` if `item` is contained in the range.
 198     ///
 199     /// # Examples
 200     ///
 201     /// ```
 202     /// use std::f32;
 203     ///
 204     /// assert!(!(3..).contains(&2));
 205     /// assert!( (3..).contains(&3));
 206     /// assert!( (3..).contains(&1_000_000_000));
 207     ///
 208     /// assert!( (0.0..).contains(&0.5));
 209     /// assert!(!(0.0..).contains(&f32::NAN));
 210     /// assert!(!(f32::NAN..).contains(&0.5));
 211     /// ```
 212     #[stable(feature = "range_contains", since = "1.35.0")]
 213     pub fn contains<U>(&self, item: &U) -> bool
 214     where
 215         Idx: PartialOrd<U>,
 216         U: ?Sized + PartialOrd<Idx>,
 217     {
 218         <Self as RangeBounds<Idx>>::contains(self, item)
 219     }
 220 }
 221
 222 /// A range only bounded exclusively above (`..end`).
 223 ///
 224 /// The `RangeTo` `..end` contains all values with `x < end`.
 225 /// It cannot serve as an [`Iterator`] because it doesn't have a starting point.
 226 ///
 227 /// # Examples
 228 ///
 229 /// The `..end` syntax is a `RangeTo`:
 230 ///
 231 /// ```
 232 /// assert_eq!((..5), std::ops::RangeTo { end: 5 });
 233 /// ```
 234 ///
 235 /// It does not have an [`IntoIterator`] implementation, so you can't use it in
 236 /// a `for` loop directly. This won't compile:
 237 ///
 238 /// ```compile_fail,E0277
 239 /// // error[E0277]: the trait bound `std::ops::RangeTo<{integer}>:
 240 /// // std::iter::Iterator` is not satisfied
 241 /// for i in ..5 {
 242 ///     // ...
 243 /// }
 244 /// ```
 245 ///
 246 /// When used as a [slicing index], `RangeTo` produces a slice of all array
 247 /// elements before the index indicated by `end`.
 248 ///
 249 /// ```
 250 /// let arr = [0, 1, 2, 3, 4];
 251 /// assert_eq!(arr[ ..  ], [0,1,2,3,4]);
 252 /// assert_eq!(arr[ .. 3], [0,1,2    ]);  // RangeTo
 253 /// assert_eq!(arr[ ..=3], [0,1,2,3  ]);
 254 /// assert_eq!(arr[1..  ], [  1,2,3,4]);
 255 /// assert_eq!(arr[1.. 3], [  1,2    ]);
 256 /// assert_eq!(arr[1..=3], [  1,2,3  ]);
 257 /// ```
 258 ///
 259 /// [`IntoIterator`]: ../iter/trait.Iterator.html
 260 /// [`Iterator`]: ../iter/trait.IntoIterator.html
 261 /// [slicing index]: ../slice/trait.SliceIndex.html
 262 #[doc(alias = "..")]
 263 #[derive(Copy, Clone, PartialEq, Eq, Hash)]
 264 #[stable(feature = "rust1", since = "1.0.0")]
 265 pub struct RangeTo<Idx> {
 266     /// The upper bound of the range (exclusive).
 267     #[stable(feature = "rust1", since = "1.0.0")]
 268     pub end: Idx,
 269 }
 270
 271 #[stable(feature = "rust1", since = "1.0.0")]
 272 impl<Idx: fmt::Debug> fmt::Debug for RangeTo<Idx> {
 273     fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result {
 274         write!(fmt, "..")?;
 275         self.end.fmt(fmt)?;
 276         Ok(())
 277     }
 278 }
 279
 280 impl<Idx: PartialOrd<Idx>> RangeTo<Idx> {
 281     /// Returns `true` if `item` is contained in the range.
 282     ///
 283     /// # Examples
 284     ///
 285     /// ```
 286     /// use std::f32;
 287     ///
 288     /// assert!( (..5).contains(&-1_000_000_000));
 289     /// assert!( (..5).contains(&4));
 290     /// assert!(!(..5).contains(&5));
 291     ///
 292     /// assert!( (..1.0).contains(&0.5));
 293     /// assert!(!(..1.0).contains(&f32::NAN));
 294     /// assert!(!(..f32::NAN).contains(&0.5));
 295     /// ```
 296     #[stable(feature = "range_contains", since = "1.35.0")]
 297     pub fn contains<U>(&self, item: &U) -> bool
 298     where
 299         Idx: PartialOrd<U>,
 300         U: ?Sized + PartialOrd<Idx>,
 301     {
 302         <Self as RangeBounds<Idx>>::contains(self, item)
 303     }
 304 }
 305
 306 /// A range bounded inclusively below and above (`start..=end`).
 307 ///
 308 /// The `RangeInclusive` `start..=end` contains all values with `x >= start`
 309 /// and `x <= end`. It is empty unless `start <= end`.
 310 ///
 311 /// This iterator is [fused], but the specific values of `start` and `end` after
 312 /// iteration has finished are **unspecified** other than that [`.is_empty()`]
 313 /// will return `true` once no more values will be produced.
 314 ///
 315 /// [fused]: ../iter/trait.FusedIterator.html
 316 /// [`.is_empty()`]: #method.is_empty
 317 ///
 318 /// # Examples
 319 ///
 320 /// ```
 321 /// assert_eq!((3..=5), std::ops::RangeInclusive::new(3, 5));
 322 /// assert_eq!(3 + 4 + 5, (3..=5).sum());
 323 ///
 324 /// let arr = [0, 1, 2, 3, 4];
 325 /// assert_eq!(arr[ ..  ], [0,1,2,3,4]);
 326 /// assert_eq!(arr[ .. 3], [0,1,2    ]);
 327 /// assert_eq!(arr[ ..=3], [0,1,2,3  ]);
 328 /// assert_eq!(arr[1..  ], [  1,2,3,4]);
 329 /// assert_eq!(arr[1.. 3], [  1,2    ]);
 330 /// assert_eq!(arr[1..=3], [  1,2,3  ]);  // RangeInclusive
 331 /// ```
 332 #[doc(alias = "..=")]
 333 #[derive(Clone)] // not Copy -- see #27186
 334 #[stable(feature = "inclusive_range", since = "1.26.0")]
 335 pub struct RangeInclusive<Idx> {
 336     // Note that the fields here are not public to allow changing the
 337     // representation in the future; in particular, while we could plausibly
 338     // expose start/end, modifying them without changing (future/current)
 339     // private fields may lead to incorrect behavior, so we don't want to
 340     // support that mode.
 341     pub(crate) start: Idx,
 342     pub(crate) end: Idx,
 343     pub(crate) is_empty: Option<bool>,
 344     // This field is:
 345     //  - `None` when next() or next_back() was never called
 346     //  - `Some(false)` when `start <= end` assuming no overflow
 347     //  - `Some(true)` otherwise
 348     // The field cannot be a simple `bool` because the `..=` constructor can
 349     // accept non-PartialOrd types, also we want the constructor to be const.
 350 }
 351
 352 trait RangeInclusiveEquality: Sized {
 353     fn canonicalized_is_empty(range: &RangeInclusive<Self>) -> bool;
 354 }
 355
 356 impl<T> RangeInclusiveEquality for T {
 357     #[inline]
 358     default fn canonicalized_is_empty(range: &RangeInclusive<Self>) -> bool {
 359         range.is_empty.unwrap_or_default()
 360     }
 361 }
 362
 363 impl<T: PartialOrd> RangeInclusiveEquality for T {
 364     #[inline]
 365     fn canonicalized_is_empty(range: &RangeInclusive<Self>) -> bool {
 366         range.is_empty()
 367     }
 368 }
 369
 370 #[stable(feature = "inclusive_range", since = "1.26.0")]
 371 impl<Idx: PartialEq> PartialEq for RangeInclusive<Idx> {
 372     #[inline]
 373     fn eq(&self, other: &Self) -> bool {
 374         self.start == other.start
 375             && self.end == other.end
 376             && RangeInclusiveEquality::canonicalized_is_empty(self)
 377                 == RangeInclusiveEquality::canonicalized_is_empty(other)
 378     }
 379 }
 380
 381 #[stable(feature = "inclusive_range", since = "1.26.0")]
 382 impl<Idx: Eq> Eq for RangeInclusive<Idx> {}
 383
 384 #[stable(feature = "inclusive_range", since = "1.26.0")]
 385 impl<Idx: Hash> Hash for RangeInclusive<Idx> {
 386     fn hash<H: Hasher>(&self, state: &mut H) {
 387         self.start.hash(state);
 388         self.end.hash(state);
 389         RangeInclusiveEquality::canonicalized_is_empty(self).hash(state);
 390     }
 391 }
 392
 393 impl<Idx> RangeInclusive<Idx> {
 394     /// Creates a new inclusive range. Equivalent to writing `start..=end`.
 395     ///
 396     /// # Examples
 397     ///
 398     /// ```
 399     /// use std::ops::RangeInclusive;
 400     ///
 401     /// assert_eq!(3..=5, RangeInclusive::new(3, 5));
 402     /// ```
 403     #[stable(feature = "inclusive_range_methods", since = "1.27.0")]
 404     #[inline]
 405     #[rustc_promotable]
 406     #[rustc_const_stable(feature = "const_range_new", since = "1.32.0")]
 407     pub const fn new(start: Idx, end: Idx) -> Self {
 408         Self { start, end, is_empty: None }
 409     }
 410
 411     /// Returns the lower bound of the range (inclusive).
 412     ///
 413     /// When using an inclusive range for iteration, the values of `start()` and
 414     /// [`end()`] are unspecified after the iteration ended. To determine
 415     /// whether the inclusive range is empty, use the [`is_empty()`] method
 416     /// instead of comparing `start() > end()`.
 417     ///
 418     /// Note: the value returned by this method is unspecified after the range
 419     /// has been iterated to exhaustion.
 420     ///
 421     /// [`end()`]: #method.end
 422     /// [`is_empty()`]: #method.is_empty
 423     ///
 424     /// # Examples
 425     ///
 426     /// ```
 427     /// assert_eq!((3..=5).start(), &3);
 428     /// ```
 429     #[stable(feature = "inclusive_range_methods", since = "1.27.0")]
 430     #[rustc_const_stable(feature = "const_inclusive_range_methods", since = "1.32.0")]
 431     #[inline]
 432     pub const fn start(&self) -> &Idx {
 433         &self.start
 434     }
 435
 436     /// Returns the upper bound of the range (inclusive).
 437     ///
 438     /// When using an inclusive range for iteration, the values of [`start()`]
 439     /// and `end()` are unspecified after the iteration ended. To determine
 440     /// whether the inclusive range is empty, use the [`is_empty()`] method
 441     /// instead of comparing `start() > end()`.
 442     ///
 443     /// Note: the value returned by this method is unspecified after the range
 444     /// has been iterated to exhaustion.
 445     ///
 446     /// [`start()`]: #method.start
 447     /// [`is_empty()`]: #method.is_empty
 448     ///
 449     /// # Examples
 450     ///
 451     /// ```
 452     /// assert_eq!((3..=5).end(), &5);
 453     /// ```
 454     #[stable(feature = "inclusive_range_methods", since = "1.27.0")]
 455     #[rustc_const_stable(feature = "const_inclusive_range_methods", since = "1.32.0")]
 456     #[inline]
 457     pub const fn end(&self) -> &Idx {
 458         &self.end
 459     }
 460
 461     /// Destructures the `RangeInclusive` into (lower bound, upper (inclusive) bound).
 462     ///
 463     /// Note: the value returned by this method is unspecified after the range
 464     /// has been iterated to exhaustion.
 465     ///
 466     /// # Examples
 467     ///
 468     /// ```
 469     /// assert_eq!((3..=5).into_inner(), (3, 5));
 470     /// ```
 471     #[stable(feature = "inclusive_range_methods", since = "1.27.0")]
 472     #[inline]
 473     pub fn into_inner(self) -> (Idx, Idx) {
 474         (self.start, self.end)
 475     }
 476 }
 477
 478 #[stable(feature = "inclusive_range", since = "1.26.0")]
 479 impl<Idx: fmt::Debug> fmt::Debug for RangeInclusive<Idx> {
 480     fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result {
 481         self.start.fmt(fmt)?;
 482         write!(fmt, "..=")?;
 483         self.end.fmt(fmt)?;
 484         Ok(())
 485     }
 486 }
 487
 488 impl<Idx: PartialOrd<Idx>> RangeInclusive<Idx> {
 489     /// Returns `true` if `item` is contained in the range.
 490     ///
 491     /// # Examples
 492     ///
 493     /// ```
 494     /// use std::f32;
 495     ///
 496     /// assert!(!(3..=5).contains(&2));
 497     /// assert!( (3..=5).contains(&3));
 498     /// assert!( (3..=5).contains(&4));
 499     /// assert!( (3..=5).contains(&5));
 500     /// assert!(!(3..=5).contains(&6));
 501     ///
 502     /// assert!( (3..=3).contains(&3));
 503     /// assert!(!(3..=2).contains(&3));
 504     ///
 505     /// assert!( (0.0..=1.0).contains(&1.0));
 506     /// assert!(!(0.0..=1.0).contains(&f32::NAN));
 507     /// assert!(!(0.0..=f32::NAN).contains(&0.0));
 508     /// assert!(!(f32::NAN..=1.0).contains(&1.0));
 509     /// ```
 510     #[stable(feature = "range_contains", since = "1.35.0")]
 511     pub fn contains<U>(&self, item: &U) -> bool
 512     where
 513         Idx: PartialOrd<U>,
 514         U: ?Sized + PartialOrd<Idx>,
 515     {
 516         <Self as RangeBounds<Idx>>::contains(self, item)
 517     }
 518
 519     /// Returns `true` if the range contains no items.
 520     ///
 521     /// # Examples
 522     ///
 523     /// ```
 524     /// #![feature(range_is_empty)]
 525     ///
 526     /// assert!(!(3..=5).is_empty());
 527     /// assert!(!(3..=3).is_empty());
 528     /// assert!( (3..=2).is_empty());
 529     /// ```
 530     ///
 531     /// The range is empty if either side is incomparable:
 532     ///
 533     /// ```
 534     /// #![feature(range_is_empty)]
 535     ///
 536     /// use std::f32::NAN;
 537     /// assert!(!(3.0..=5.0).is_empty());
 538     /// assert!( (3.0..=NAN).is_empty());
 539     /// assert!( (NAN..=5.0).is_empty());
 540     /// ```
 541     ///
 542     /// This method returns `true` after iteration has finished:
 543     ///
 544     /// ```
 545     /// #![feature(range_is_empty)]
 546     ///
 547     /// let mut r = 3..=5;
 548     /// for _ in r.by_ref() {}
 549     /// // Precise field values are unspecified here
 550     /// assert!(r.is_empty());
 551     /// ```
 552     #[unstable(feature = "range_is_empty", reason = "recently added", issue = "48111")]
 553     #[inline]
 554     pub fn is_empty(&self) -> bool {
 555         self.is_empty.unwrap_or_else(|| !(self.start <= self.end))
 556     }
 557
 558     // If this range's `is_empty` is field is unknown (`None`), update it to be a concrete value.
 559     #[inline]
 560     pub(crate) fn compute_is_empty(&mut self) {
 561         if self.is_empty.is_none() {
 562             self.is_empty = Some(!(self.start <= self.end));
 563         }
 564     }
 565 }
 566
 567 /// A range only bounded inclusively above (`..=end`).
 568 ///
 569 /// The `RangeToInclusive` `..=end` contains all values with `x <= end`.
 570 /// It cannot serve as an [`Iterator`] because it doesn't have a starting point.
 571 ///
 572 /// # Examples
 573 ///
 574 /// The `..=end` syntax is a `RangeToInclusive`:
 575 ///
 576 /// ```
 577 /// assert_eq!((..=5), std::ops::RangeToInclusive{ end: 5 });
 578 /// ```
 579 ///
 580 /// It does not have an [`IntoIterator`] implementation, so you can't use it in a
 581 /// `for` loop directly. This won't compile:
 582 ///
 583 /// ```compile_fail,E0277
 584 /// // error[E0277]: the trait bound `std::ops::RangeToInclusive<{integer}>:
 585 /// // std::iter::Iterator` is not satisfied
 586 /// for i in ..=5 {
 587 ///     // ...
 588 /// }
 589 /// ```
 590 ///
 591 /// When used as a [slicing index], `RangeToInclusive` produces a slice of all
 592 /// array elements up to and including the index indicated by `end`.
 593 ///
 594 /// ```
 595 /// let arr = [0, 1, 2, 3, 4];
 596 /// assert_eq!(arr[ ..  ], [0,1,2,3,4]);
 597 /// assert_eq!(arr[ .. 3], [0,1,2    ]);
 598 /// assert_eq!(arr[ ..=3], [0,1,2,3  ]);  // RangeToInclusive
 599 /// assert_eq!(arr[1..  ], [  1,2,3,4]);
 600 /// assert_eq!(arr[1.. 3], [  1,2    ]);
 601 /// assert_eq!(arr[1..=3], [  1,2,3  ]);
 602 /// ```
 603 ///
 604 /// [`IntoIterator`]: ../iter/trait.Iterator.html
 605 /// [`Iterator`]: ../iter/trait.IntoIterator.html
 606 /// [slicing index]: ../slice/trait.SliceIndex.html
 607 #[doc(alias = "..=")]
 608 #[derive(Copy, Clone, PartialEq, Eq, Hash)]
 609 #[stable(feature = "inclusive_range", since = "1.26.0")]
 610 pub struct RangeToInclusive<Idx> {
 611     /// The upper bound of the range (inclusive)
 612     #[stable(feature = "inclusive_range", since = "1.26.0")]
 613     pub end: Idx,
 614 }
 615
 616 #[stable(feature = "inclusive_range", since = "1.26.0")]
 617 impl<Idx: fmt::Debug> fmt::Debug for RangeToInclusive<Idx> {
 618     fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result {
 619         write!(fmt, "..=")?;
 620         self.end.fmt(fmt)?;
 621         Ok(())
 622     }
 623 }
 624
 625 impl<Idx: PartialOrd<Idx>> RangeToInclusive<Idx> {
 626     /// Returns `true` if `item` is contained in the range.
 627     ///
 628     /// # Examples
 629     ///
 630     /// ```
 631     /// use std::f32;
 632     ///
 633     /// assert!( (..=5).contains(&-1_000_000_000));
 634     /// assert!( (..=5).contains(&5));
 635     /// assert!(!(..=5).contains(&6));
 636     ///
 637     /// assert!( (..=1.0).contains(&1.0));
 638     /// assert!(!(..=1.0).contains(&f32::NAN));
 639     /// assert!(!(..=f32::NAN).contains(&0.5));
 640     /// ```
 641     #[stable(feature = "range_contains", since = "1.35.0")]
 642     pub fn contains<U>(&self, item: &U) -> bool
 643     where
 644         Idx: PartialOrd<U>,
 645         U: ?Sized + PartialOrd<Idx>,
 646     {
 647         <Self as RangeBounds<Idx>>::contains(self, item)
 648     }
 649 }
 650
 651 // RangeToInclusive<Idx> cannot impl From<RangeTo<Idx>>
 652 // because underflow would be possible with (..0).into()
 653
 654 /// An endpoint of a range of keys.
 655 ///
 656 /// # Examples
 657 ///
 658 /// `Bound`s are range endpoints:
 659 ///
 660 /// ```
 661 /// use std::ops::Bound::*;
 662 /// use std::ops::RangeBounds;
 663 ///
 664 /// assert_eq!((..100).start_bound(), Unbounded);
 665 /// assert_eq!((1..12).start_bound(), Included(&1));
 666 /// assert_eq!((1..12).end_bound(), Excluded(&12));
 667 /// ```
 668 ///
 669 /// Using a tuple of `Bound`s as an argument to [`BTreeMap::range`].
 670 /// Note that in most cases, it's better to use range syntax (`1..5`) instead.
 671 ///
 672 /// ```
 673 /// use std::collections::BTreeMap;
 674 /// use std::ops::Bound::{Excluded, Included, Unbounded};
 675 ///
 676 /// let mut map = BTreeMap::new();
 677 /// map.insert(3, "a");
 678 /// map.insert(5, "b");
 679 /// map.insert(8, "c");
 680 ///
 681 /// for (key, value) in map.range((Excluded(3), Included(8))) {
 682 ///     println!("{}: {}", key, value);
 683 /// }
 684 ///
 685 /// assert_eq!(Some((&3, &"a")), map.range((Unbounded, Included(5))).next());
 686 /// ```
 687 ///
 688 /// [`BTreeMap::range`]: ../../std/collections/btree_map/struct.BTreeMap.html#method.range
 689 #[stable(feature = "collections_bound", since = "1.17.0")]
 690 #[derive(Clone, Copy, Debug, Hash, PartialEq, Eq)]
 691 pub enum Bound<T> {
 692     /// An inclusive bound.
 693     #[stable(feature = "collections_bound", since = "1.17.0")]
 694     Included(#[stable(feature = "collections_bound", since = "1.17.0")] T),
 695     /// An exclusive bound.
 696     #[stable(feature = "collections_bound", since = "1.17.0")]
 697     Excluded(#[stable(feature = "collections_bound", since = "1.17.0")] T),
 698     /// An infinite endpoint. Indicates that there is no bound in this direction.
 699     #[stable(feature = "collections_bound", since = "1.17.0")]
 700     Unbounded,
 701 }
 702
 703 impl<T: Clone> Bound<&T> {
 704     /// Map a `Bound<&T>` to a `Bound<T>` by cloning the contents of the bound.
 705     ///
 706     /// # Examples
 707     ///
 708     /// ```
 709     /// #![feature(bound_cloned)]
 710     /// use std::ops::Bound::*;
 711     /// use std::ops::RangeBounds;
 712     ///
 713     /// assert_eq!((1..12).start_bound(), Included(&1));
 714     /// assert_eq!((1..12).start_bound().cloned(), Included(1));
 715     /// ```
 716     #[unstable(feature = "bound_cloned", issue = "61356")]
 717     pub fn cloned(self) -> Bound<T> {
 718         match self {
 719             Bound::Unbounded => Bound::Unbounded,
 720             Bound::Included(x) => Bound::Included(x.clone()),
 721             Bound::Excluded(x) => Bound::Excluded(x.clone()),
 722         }
 723     }
 724 }
 725
 726 #[stable(feature = "collections_range", since = "1.28.0")]
 727 /// `RangeBounds` is implemented by Rust's built-in range types, produced
 728 /// by range syntax like `..`, `a..`, `..b`, `..=c`, `d..e`, or `f..=g`.
 729 pub trait RangeBounds<T: ?Sized> {
 730     /// Start index bound.
 731     ///
 732     /// Returns the start value as a `Bound`.
 733     ///
 734     /// # Examples
 735     ///
 736     /// ```
 737     /// # fn main() {
 738     /// use std::ops::Bound::*;
 739     /// use std::ops::RangeBounds;
 740     ///
 741     /// assert_eq!((..10).start_bound(), Unbounded);
 742     /// assert_eq!((3..10).start_bound(), Included(&3));
 743     /// # }
 744     /// ```
 745     #[stable(feature = "collections_range", since = "1.28.0")]
 746     fn start_bound(&self) -> Bound<&T>;
 747
 748     /// End index bound.
 749     ///
 750     /// Returns the end value as a `Bound`.
 751     ///
 752     /// # Examples
 753     ///
 754     /// ```
 755     /// # fn main() {
 756     /// use std::ops::Bound::*;
 757     /// use std::ops::RangeBounds;
 758     ///
 759     /// assert_eq!((3..).end_bound(), Unbounded);
 760     /// assert_eq!((3..10).end_bound(), Excluded(&10));
 761     /// # }
 762     /// ```
 763     #[stable(feature = "collections_range", since = "1.28.0")]
 764     fn end_bound(&self) -> Bound<&T>;
 765
 766     /// Returns `true` if `item` is contained in the range.
 767     ///
 768     /// # Examples
 769     ///
 770     /// ```
 771     /// use std::f32;
 772     ///
 773     /// assert!( (3..5).contains(&4));
 774     /// assert!(!(3..5).contains(&2));
 775     ///
 776     /// assert!( (0.0..1.0).contains(&0.5));
 777     /// assert!(!(0.0..1.0).contains(&f32::NAN));
 778     /// assert!(!(0.0..f32::NAN).contains(&0.5));
 779     /// assert!(!(f32::NAN..1.0).contains(&0.5));
 780     #[stable(feature = "range_contains", since = "1.35.0")]
 781     fn contains<U>(&self, item: &U) -> bool
 782     where
 783         T: PartialOrd<U>,
 784         U: ?Sized + PartialOrd<T>,
 785     {
 786         (match self.start_bound() {
 787             Included(ref start) => *start <= item,
 788             Excluded(ref start) => *start < item,
 789             Unbounded => true,
 790         }) && (match self.end_bound() {
 791             Included(ref end) => item <= *end,
 792             Excluded(ref end) => item < *end,
 793             Unbounded => true,
 794         })
 795     }
 796 }
 797
 798 use self::Bound::{Excluded, Included, Unbounded};
 799
 800 #[stable(feature = "collections_range", since = "1.28.0")]
 801 impl<T: ?Sized> RangeBounds<T> for RangeFull {
 802     fn start_bound(&self) -> Bound<&T> {
 803         Unbounded
 804     }
 805     fn end_bound(&self) -> Bound<&T> {
 806         Unbounded
 807     }
 808 }
 809
 810 #[stable(feature = "collections_range", since = "1.28.0")]
 811 impl<T> RangeBounds<T> for RangeFrom<T> {
 812     fn start_bound(&self) -> Bound<&T> {
 813         Included(&self.start)
 814     }
 815     fn end_bound(&self) -> Bound<&T> {
 816         Unbounded
 817     }
 818 }
 819
 820 #[stable(feature = "collections_range", since = "1.28.0")]
 821 impl<T> RangeBounds<T> for RangeTo<T> {
 822     fn start_bound(&self) -> Bound<&T> {
 823         Unbounded
 824     }
 825     fn end_bound(&self) -> Bound<&T> {
 826         Excluded(&self.end)
 827     }
 828 }
 829
 830 #[stable(feature = "collections_range", since = "1.28.0")]
 831 impl<T> RangeBounds<T> for Range<T> {
 832     fn start_bound(&self) -> Bound<&T> {
 833         Included(&self.start)
 834     }
 835     fn end_bound(&self) -> Bound<&T> {
 836         Excluded(&self.end)
 837     }
 838 }
 839
 840 #[stable(feature = "collections_range", since = "1.28.0")]
 841 impl<T> RangeBounds<T> for RangeInclusive<T> {
 842     fn start_bound(&self) -> Bound<&T> {
 843         Included(&self.start)
 844     }
 845     fn end_bound(&self) -> Bound<&T> {
 846         Included(&self.end)
 847     }
 848 }
 849
 850 #[stable(feature = "collections_range", since = "1.28.0")]
 851 impl<T> RangeBounds<T> for RangeToInclusive<T> {
 852     fn start_bound(&self) -> Bound<&T> {
 853         Unbounded
 854     }
 855     fn end_bound(&self) -> Bound<&T> {
 856         Included(&self.end)
 857     }
 858 }
 859
 860 #[stable(feature = "collections_range", since = "1.28.0")]
 861 impl<T> RangeBounds<T> for (Bound<T>, Bound<T>) {
 862     fn start_bound(&self) -> Bound<&T> {
 863         match *self {
 864             (Included(ref start), _) => Included(start),
 865             (Excluded(ref start), _) => Excluded(start),
 866             (Unbounded, _) => Unbounded,
 867         }
 868     }
 869
 870     fn end_bound(&self) -> Bound<&T> {
 871         match *self {
 872             (_, Included(ref end)) => Included(end),
 873             (_, Excluded(ref end)) => Excluded(end),
 874             (_, Unbounded) => Unbounded,
 875         }
 876     }
 877 }
 878
 879 #[stable(feature = "collections_range", since = "1.28.0")]
 880 impl<'a, T: ?Sized + 'a> RangeBounds<T> for (Bound<&'a T>, Bound<&'a T>) {
 881     fn start_bound(&self) -> Bound<&T> {
 882         self.0
 883     }
 884
 885     fn end_bound(&self) -> Bound<&T> {
 886         self.1
 887     }
 888 }
 889
 890 #[stable(feature = "collections_range", since = "1.28.0")]
 891 impl<T> RangeBounds<T> for RangeFrom<&T> {
 892     fn start_bound(&self) -> Bound<&T> {
 893         Included(self.start)
 894     }
 895     fn end_bound(&self) -> Bound<&T> {
 896         Unbounded
 897     }
 898 }
 899
 900 #[stable(feature = "collections_range", since = "1.28.0")]
 901 impl<T> RangeBounds<T> for RangeTo<&T> {
 902     fn start_bound(&self) -> Bound<&T> {
 903         Unbounded
 904     }
 905     fn end_bound(&self) -> Bound<&T> {
 906         Excluded(self.end)
 907     }
 908 }
 909
 910 #[stable(feature = "collections_range", since = "1.28.0")]
 911 impl<T> RangeBounds<T> for Range<&T> {
 912     fn start_bound(&self) -> Bound<&T> {
 913         Included(self.start)
 914     }
 915     fn end_bound(&self) -> Bound<&T> {
 916         Excluded(self.end)
 917     }
 918 }
 919
 920 #[stable(feature = "collections_range", since = "1.28.0")]
 921 impl<T> RangeBounds<T> for RangeInclusive<&T> {
 922     fn start_bound(&self) -> Bound<&T> {
 923         Included(self.start)
 924     }
 925     fn end_bound(&self) -> Bound<&T> {
 926         Included(self.end)
 927     }
 928 }
 929
 930 #[stable(feature = "collections_range", since = "1.28.0")]
 931 impl<T> RangeBounds<T> for RangeToInclusive<&T> {
 932     fn start_bound(&self) -> Bound<&T> {
 933         Unbounded
 934     }
 935     fn end_bound(&self) -> Bound<&T> {
 936         Included(self.end)
 937     }
 938 }