src/libcore/ops/range.rs

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