src/libcore/ops/range.rs

   1 // Copyright 2012 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 fmt;
  12
  13 /// An unbounded range (`..`).
  14 ///
  15 /// `RangeFull` is primarily used as a [slicing index], its shorthand is `..`.
  16 /// It cannot serve as an [`Iterator`] because it doesn't have a starting point.
  17 ///
  18 /// # Examples
  19 ///
  20 /// The `..` syntax is a `RangeFull`:
  21 ///
  22 /// ```
  23 /// assert_eq!((..), std::ops::RangeFull);
  24 /// ```
  25 ///
  26 /// It does not have an [`IntoIterator`] implementation, so you can't use it in
  27 /// a `for` loop directly. This won't compile:
  28 ///
  29 /// ```compile_fail,E0277
  30 /// for i in .. {
  31 ///    // ...
  32 /// }
  33 /// ```
  34 ///
  35 /// Used as a [slicing index], `RangeFull` produces the full array as a slice.
  36 ///
  37 /// ```
  38 /// let arr = [0, 1, 2, 3];
  39 /// assert_eq!(arr[ .. ], [0,1,2,3]);  // RangeFull
  40 /// assert_eq!(arr[ ..3], [0,1,2  ]);
  41 /// assert_eq!(arr[1.. ], [  1,2,3]);
  42 /// assert_eq!(arr[1..3], [  1,2  ]);
  43 /// ```
  44 ///
  45 /// [`IntoIterator`]: ../iter/trait.Iterator.html
  46 /// [`Iterator`]: ../iter/trait.IntoIterator.html
  47 /// [slicing index]: ../slice/trait.SliceIndex.html
  48 #[doc(alias = "..")]
  49 #[derive(Copy, Clone, PartialEq, Eq, Hash)]
  50 #[stable(feature = "rust1", since = "1.0.0")]
  51 pub struct RangeFull;
  52
  53 #[stable(feature = "rust1", since = "1.0.0")]
  54 impl fmt::Debug for RangeFull {
  55     fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
  56         write!(fmt, "..")
  57     }
  58 }
  59
  60 /// A (half-open) range bounded inclusively below and exclusively above
  61 /// (`start..end`).
  62 ///
  63 /// The `Range` `start..end` contains all values with `x >= start` and
  64 /// `x < end`.  It is empty unless `start < end`.
  65 ///
  66 /// # Examples
  67 ///
  68 /// ```
  69 /// assert_eq!((3..5), std::ops::Range { start: 3, end: 5 });
  70 /// assert_eq!(3 + 4 + 5, (3..6).sum());
  71 ///
  72 /// let arr = ['a', 'b', 'c', 'd'];
  73 /// assert_eq!(arr[ .. ], ['a', 'b', 'c', 'd']);
  74 /// assert_eq!(arr[ ..3], ['a', 'b', 'c',    ]);
  75 /// assert_eq!(arr[1.. ], [     'b', 'c', 'd']);
  76 /// assert_eq!(arr[1..3], [     'b', 'c'     ]);  // Range
  77 /// ```
  78 #[doc(alias = "..")]
  79 #[derive(Clone, PartialEq, Eq, Hash)]  // not Copy -- see #27186
  80 #[stable(feature = "rust1", since = "1.0.0")]
  81 pub struct Range<Idx> {
  82     /// The lower bound of the range (inclusive).
  83     #[stable(feature = "rust1", since = "1.0.0")]
  84     pub start: Idx,
  85     /// The upper bound of the range (exclusive).
  86     #[stable(feature = "rust1", since = "1.0.0")]
  87     pub end: Idx,
  88 }
  89
  90 #[stable(feature = "rust1", since = "1.0.0")]
  91 impl<Idx: fmt::Debug> fmt::Debug for Range<Idx> {
  92     fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
  93         write!(fmt, "{:?}..{:?}", self.start, self.end)
  94     }
  95 }
  96
  97 impl<Idx: PartialOrd<Idx>> Range<Idx> {
  98     /// Returns `true` if `item` is contained in the range.
  99     ///
 100     /// # Examples
 101     ///
 102     /// ```
 103     /// #![feature(range_contains)]
 104     ///
 105     /// use std::f32;
 106     ///
 107     /// assert!(!(3..5).contains(&2));
 108     /// assert!( (3..5).contains(&3));
 109     /// assert!( (3..5).contains(&4));
 110     /// assert!(!(3..5).contains(&5));
 111     ///
 112     /// assert!(!(3..3).contains(&3));
 113     /// assert!(!(3..2).contains(&3));
 114     ///
 115     /// assert!( (0.0..1.0).contains(&0.5));
 116     /// assert!(!(0.0..1.0).contains(&f32::NAN));
 117     /// assert!(!(0.0..f32::NAN).contains(&0.5));
 118     /// assert!(!(f32::NAN..1.0).contains(&0.5));
 119     /// ```
 120     #[unstable(feature = "range_contains", reason = "recently added as per RFC", issue = "32311")]
 121     pub fn contains<U>(&self, item: &U) -> bool
 122     where
 123         Idx: PartialOrd<U>,
 124         U: ?Sized + PartialOrd<Idx>,
 125     {
 126         <Self as RangeBounds<Idx>>::contains(self, item)
 127     }
 128
 129     /// Returns `true` if the range contains no items.
 130     ///
 131     /// # Examples
 132     ///
 133     /// ```
 134     /// #![feature(range_is_empty)]
 135     ///
 136     /// assert!(!(3..5).is_empty());
 137     /// assert!( (3..3).is_empty());
 138     /// assert!( (3..2).is_empty());
 139     /// ```
 140     ///
 141     /// The range is empty if either side is incomparable:
 142     ///
 143     /// ```
 144     /// #![feature(range_is_empty)]
 145     ///
 146     /// use std::f32::NAN;
 147     /// assert!(!(3.0..5.0).is_empty());
 148     /// assert!( (3.0..NAN).is_empty());
 149     /// assert!( (NAN..5.0).is_empty());
 150     /// ```
 151     #[unstable(feature = "range_is_empty", reason = "recently added", issue = "48111")]
 152     pub fn is_empty(&self) -> bool {
 153         !(self.start < self.end)
 154     }
 155 }
 156
 157 /// A range only bounded inclusively below (`start..`).
 158 ///
 159 /// The `RangeFrom` `start..` contains all values with `x >= start`.
 160 ///
 161 /// *Note*: Currently, no overflow checking is done for the [`Iterator`]
 162 /// implementation; if you use an integer range and the integer overflows, it
 163 /// might panic in debug mode or create an endless loop in release mode. **This
 164 /// overflow behavior might change in the future.**
 165 ///
 166 /// # Examples
 167 ///
 168 /// ```
 169 /// assert_eq!((2..), std::ops::RangeFrom { start: 2 });
 170 /// assert_eq!(2 + 3 + 4, (2..).take(3).sum());
 171 ///
 172 /// let arr = [0, 1, 2, 3];
 173 /// assert_eq!(arr[ .. ], [0,1,2,3]);
 174 /// assert_eq!(arr[ ..3], [0,1,2  ]);
 175 /// assert_eq!(arr[1.. ], [  1,2,3]);  // RangeFrom
 176 /// assert_eq!(arr[1..3], [  1,2  ]);
 177 /// ```
 178 ///
 179 /// [`Iterator`]: ../iter/trait.IntoIterator.html
 180 #[doc(alias = "..")]
 181 #[derive(Clone, PartialEq, Eq, Hash)]  // not Copy -- see #27186
 182 #[stable(feature = "rust1", since = "1.0.0")]
 183 pub struct RangeFrom<Idx> {
 184     /// The lower bound of the range (inclusive).
 185     #[stable(feature = "rust1", since = "1.0.0")]
 186     pub start: Idx,
 187 }
 188
 189 #[stable(feature = "rust1", since = "1.0.0")]
 190 impl<Idx: fmt::Debug> fmt::Debug for RangeFrom<Idx> {
 191     fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
 192         write!(fmt, "{:?}..", self.start)
 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     /// #![feature(range_contains)]
 203     ///
 204     /// use std::f32;
 205     ///
 206     /// assert!(!(3..).contains(&2));
 207     /// assert!( (3..).contains(&3));
 208     /// assert!( (3..).contains(&1_000_000_000));
 209     ///
 210     /// assert!( (0.0..).contains(&0.5));
 211     /// assert!(!(0.0..).contains(&f32::NAN));
 212     /// assert!(!(f32::NAN..).contains(&0.5));
 213     /// ```
 214     #[unstable(feature = "range_contains", reason = "recently added as per RFC", issue = "32311")]
 215     pub fn contains<U>(&self, item: &U) -> bool
 216     where
 217         Idx: PartialOrd<U>,
 218         U: ?Sized + PartialOrd<Idx>,
 219     {
 220         <Self as RangeBounds<Idx>>::contains(self, item)
 221     }
 222 }
 223
 224 /// A range only bounded exclusively above (`..end`).
 225 ///
 226 /// The `RangeTo` `..end` contains all values with `x < end`.
 227 /// It cannot serve as an [`Iterator`] because it doesn't have a starting point.
 228 ///
 229 /// # Examples
 230 ///
 231 /// The `..end` syntax is a `RangeTo`:
 232 ///
 233 /// ```
 234 /// assert_eq!((..5), std::ops::RangeTo { end: 5 });
 235 /// ```
 236 ///
 237 /// It does not have an [`IntoIterator`] implementation, so you can't use it in
 238 /// a `for` loop directly. This won't compile:
 239 ///
 240 /// ```compile_fail,E0277
 241 /// // error[E0277]: the trait bound `std::ops::RangeTo<{integer}>:
 242 /// // std::iter::Iterator` is not satisfied
 243 /// for i in ..5 {
 244 ///     // ...
 245 /// }
 246 /// ```
 247 ///
 248 /// When used as a [slicing index], `RangeTo` produces a slice of all array
 249 /// elements before the index indicated by `end`.
 250 ///
 251 /// ```
 252 /// let arr = [0, 1, 2, 3];
 253 /// assert_eq!(arr[ .. ], [0,1,2,3]);
 254 /// assert_eq!(arr[ ..3], [0,1,2  ]);  // RangeTo
 255 /// assert_eq!(arr[1.. ], [  1,2,3]);
 256 /// assert_eq!(arr[1..3], [  1,2  ]);
 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, "..{:?}", self.end)
 275     }
 276 }
 277
 278 impl<Idx: PartialOrd<Idx>> RangeTo<Idx> {
 279     /// Returns `true` if `item` is contained in the range.
 280     ///
 281     /// # Examples
 282     ///
 283     /// ```
 284     /// #![feature(range_contains)]
 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     #[unstable(feature = "range_contains", reason = "recently added as per RFC", issue = "32311")]
 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 /// An 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 /// #![feature(inclusive_range_methods)]
 322 ///
 323 /// assert_eq!((3..=5), std::ops::RangeInclusive::new(3, 5));
 324 /// assert_eq!(3 + 4 + 5, (3..=5).sum());
 325 ///
 326 /// let arr = [0, 1, 2, 3];
 327 /// assert_eq!(arr[ ..=2], [0,1,2  ]);
 328 /// assert_eq!(arr[1..=2], [  1,2  ]);  // RangeInclusive
 329 /// ```
 330 #[doc(alias = "..=")]
 331 #[derive(Clone, PartialEq, Eq, Hash)]  // not Copy -- see #27186
 332 #[stable(feature = "inclusive_range", since = "1.26.0")]
 333 pub struct RangeInclusive<Idx> {
 334     // FIXME: The current representation follows RFC 1980,
 335     // but it is known that LLVM is not able to optimize loops following that RFC.
 336     // Consider adding an extra `bool` field to indicate emptiness of the range.
 337     // See #45222 for performance test cases.
 338     #[cfg(not(stage0))]
 339     pub(crate) start: Idx,
 340     #[cfg(not(stage0))]
 341     pub(crate) end: Idx,
 342     /// The lower bound of the range (inclusive).
 343     #[cfg(stage0)]
 344     #[unstable(feature = "inclusive_range_fields", issue = "49022")]
 345     pub start: Idx,
 346     /// The upper bound of the range (inclusive).
 347     #[cfg(stage0)]
 348     #[unstable(feature = "inclusive_range_fields", issue = "49022")]
 349     pub end: Idx,
 350 }
 351
 352 impl<Idx> RangeInclusive<Idx> {
 353     /// Creates a new inclusive range. Equivalent to writing `start..=end`.
 354     ///
 355     /// # Examples
 356     ///
 357     /// ```
 358     /// #![feature(inclusive_range_methods)]
 359     /// use std::ops::RangeInclusive;
 360     ///
 361     /// assert_eq!(3..=5, RangeInclusive::new(3, 5));
 362     /// ```
 363     #[unstable(feature = "inclusive_range_methods", issue = "49022")]
 364     #[inline]
 365     pub fn new(start: Idx, end: Idx) -> Self {
 366         Self { start, end }
 367     }
 368
 369     /// Returns the lower bound of the range (inclusive).
 370     ///
 371     /// # Examples
 372     ///
 373     /// ```
 374     /// #![feature(inclusive_range_methods)]
 375     ///
 376     /// assert_eq!((3..=5).start(), &3);
 377     /// ```
 378     #[unstable(feature = "inclusive_range_methods", issue = "49022")]
 379     #[inline]
 380     pub fn start(&self) -> &Idx {
 381         &self.start
 382     }
 383
 384     /// Returns the upper bound of the range (inclusive).
 385     ///
 386     /// # Examples
 387     ///
 388     /// ```
 389     /// #![feature(inclusive_range_methods)]
 390     ///
 391     /// assert_eq!((3..=5).end(), &5);
 392     /// ```
 393     #[unstable(feature = "inclusive_range_methods", issue = "49022")]
 394     #[inline]
 395     pub fn end(&self) -> &Idx {
 396         &self.end
 397     }
 398 }
 399
 400 #[stable(feature = "inclusive_range", since = "1.26.0")]
 401 impl<Idx: fmt::Debug> fmt::Debug for RangeInclusive<Idx> {
 402     fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
 403         write!(fmt, "{:?}..={:?}", self.start, self.end)
 404     }
 405 }
 406
 407 impl<Idx: PartialOrd<Idx>> RangeInclusive<Idx> {
 408     /// Returns `true` if `item` is contained in the range.
 409     ///
 410     /// # Examples
 411     ///
 412     /// ```
 413     /// #![feature(range_contains)]
 414     ///
 415     /// use std::f32;
 416     ///
 417     /// assert!(!(3..=5).contains(&2));
 418     /// assert!( (3..=5).contains(&3));
 419     /// assert!( (3..=5).contains(&4));
 420     /// assert!( (3..=5).contains(&5));
 421     /// assert!(!(3..=5).contains(&6));
 422     ///
 423     /// assert!( (3..=3).contains(&3));
 424     /// assert!(!(3..=2).contains(&3));
 425     ///
 426     /// assert!( (0.0..=1.0).contains(&1.0));
 427     /// assert!(!(0.0..=1.0).contains(&f32::NAN));
 428     /// assert!(!(0.0..=f32::NAN).contains(&0.0));
 429     /// assert!(!(f32::NAN..=1.0).contains(&1.0));
 430     /// ```
 431     #[unstable(feature = "range_contains", reason = "recently added as per RFC", issue = "32311")]
 432     pub fn contains<U>(&self, item: &U) -> bool
 433     where
 434         Idx: PartialOrd<U>,
 435         U: ?Sized + PartialOrd<Idx>,
 436     {
 437         <Self as RangeBounds<Idx>>::contains(self, item)
 438     }
 439
 440     /// Returns `true` if the range contains no items.
 441     ///
 442     /// # Examples
 443     ///
 444     /// ```
 445     /// #![feature(range_is_empty)]
 446     ///
 447     /// assert!(!(3..=5).is_empty());
 448     /// assert!(!(3..=3).is_empty());
 449     /// assert!( (3..=2).is_empty());
 450     /// ```
 451     ///
 452     /// The range is empty if either side is incomparable:
 453     ///
 454     /// ```
 455     /// #![feature(range_is_empty)]
 456     ///
 457     /// use std::f32::NAN;
 458     /// assert!(!(3.0..=5.0).is_empty());
 459     /// assert!( (3.0..=NAN).is_empty());
 460     /// assert!( (NAN..=5.0).is_empty());
 461     /// ```
 462     ///
 463     /// This method returns `true` after iteration has finished:
 464     ///
 465     /// ```
 466     /// #![feature(range_is_empty)]
 467     ///
 468     /// let mut r = 3..=5;
 469     /// for _ in r.by_ref() {}
 470     /// // Precise field values are unspecified here
 471     /// assert!(r.is_empty());
 472     /// ```
 473     #[unstable(feature = "range_is_empty", reason = "recently added", issue = "48111")]
 474     pub fn is_empty(&self) -> bool {
 475         !(self.start <= self.end)
 476     }
 477 }
 478
 479 /// A range only bounded inclusively above (`..=end`).
 480 ///
 481 /// The `RangeToInclusive` `..=end` contains all values with `x <= end`.
 482 /// It cannot serve as an [`Iterator`] because it doesn't have a starting point.
 483 ///
 484 /// # Examples
 485 ///
 486 /// The `..=end` syntax is a `RangeToInclusive`:
 487 ///
 488 /// ```
 489 /// assert_eq!((..=5), std::ops::RangeToInclusive{ end: 5 });
 490 /// ```
 491 ///
 492 /// It does not have an [`IntoIterator`] implementation, so you can't use it in a
 493 /// `for` loop directly. This won't compile:
 494 ///
 495 /// ```compile_fail,E0277
 496 /// // error[E0277]: the trait bound `std::ops::RangeToInclusive<{integer}>:
 497 /// // std::iter::Iterator` is not satisfied
 498 /// for i in ..=5 {
 499 ///     // ...
 500 /// }
 501 /// ```
 502 ///
 503 /// When used as a [slicing index], `RangeToInclusive` produces a slice of all
 504 /// array elements up to and including the index indicated by `end`.
 505 ///
 506 /// ```
 507 /// let arr = [0, 1, 2, 3];
 508 /// assert_eq!(arr[ ..=2], [0,1,2  ]);  // RangeToInclusive
 509 /// assert_eq!(arr[1..=2], [  1,2  ]);
 510 /// ```
 511 ///
 512 /// [`IntoIterator`]: ../iter/trait.Iterator.html
 513 /// [`Iterator`]: ../iter/trait.IntoIterator.html
 514 /// [slicing index]: ../slice/trait.SliceIndex.html
 515 #[doc(alias = "..=")]
 516 #[derive(Copy, Clone, PartialEq, Eq, Hash)]
 517 #[stable(feature = "inclusive_range", since = "1.26.0")]
 518 pub struct RangeToInclusive<Idx> {
 519     /// The upper bound of the range (inclusive)
 520     #[stable(feature = "inclusive_range", since = "1.26.0")]
 521     pub end: Idx,
 522 }
 523
 524 #[stable(feature = "inclusive_range", since = "1.26.0")]
 525 impl<Idx: fmt::Debug> fmt::Debug for RangeToInclusive<Idx> {
 526     fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
 527         write!(fmt, "..={:?}", self.end)
 528     }
 529 }
 530
 531 #[unstable(feature = "range_contains", reason = "recently added as per RFC", issue = "32311")]
 532 impl<Idx: PartialOrd<Idx>> RangeToInclusive<Idx> {
 533     /// Returns `true` if `item` is contained in the range.
 534     ///
 535     /// # Examples
 536     ///
 537     /// ```
 538     /// #![feature(range_contains)]
 539     ///
 540     /// use std::f32;
 541     ///
 542     /// assert!( (..=5).contains(&-1_000_000_000));
 543     /// assert!( (..=5).contains(&5));
 544     /// assert!(!(..=5).contains(&6));
 545     ///
 546     /// assert!( (..=1.0).contains(&1.0));
 547     /// assert!(!(..=1.0).contains(&f32::NAN));
 548     /// assert!(!(..=f32::NAN).contains(&0.5));
 549     /// ```
 550     #[unstable(feature = "range_contains", reason = "recently added as per RFC", issue = "32311")]
 551     pub fn contains<U>(&self, item: &U) -> bool
 552     where
 553         Idx: PartialOrd<U>,
 554         U: ?Sized + PartialOrd<Idx>,
 555     {
 556         <Self as RangeBounds<Idx>>::contains(self, item)
 557     }
 558 }
 559
 560 // RangeToInclusive<Idx> cannot impl From<RangeTo<Idx>>
 561 // because underflow would be possible with (..0).into()
 562
 563 /// An endpoint of a range of keys.
 564 ///
 565 /// # Examples
 566 ///
 567 /// `Bound`s are range endpoints:
 568 ///
 569 /// ```
 570 /// #![feature(collections_range)]
 571 ///
 572 /// use std::ops::Bound::*;
 573 /// use std::ops::RangeBounds;
 574 ///
 575 /// assert_eq!((..100).start(), Unbounded);
 576 /// assert_eq!((1..12).start(), Included(&1));
 577 /// assert_eq!((1..12).end(), Excluded(&12));
 578 /// ```
 579 ///
 580 /// Using a tuple of `Bound`s as an argument to [`BTreeMap::range`].
 581 /// Note that in most cases, it's better to use range syntax (`1..5`) instead.
 582 ///
 583 /// ```
 584 /// use std::collections::BTreeMap;
 585 /// use std::ops::Bound::{Excluded, Included, Unbounded};
 586 ///
 587 /// let mut map = BTreeMap::new();
 588 /// map.insert(3, "a");
 589 /// map.insert(5, "b");
 590 /// map.insert(8, "c");
 591 ///
 592 /// for (key, value) in map.range((Excluded(3), Included(8))) {
 593 ///     println!("{}: {}", key, value);
 594 /// }
 595 ///
 596 /// assert_eq!(Some((&3, &"a")), map.range((Unbounded, Included(5))).next());
 597 /// ```
 598 ///
 599 /// [`BTreeMap::range`]: ../../std/collections/btree_map/struct.BTreeMap.html#method.range
 600 #[stable(feature = "collections_bound", since = "1.17.0")]
 601 #[derive(Clone, Copy, Debug, Hash, PartialEq, Eq)]
 602 pub enum Bound<T> {
 603     /// An inclusive bound.
 604     #[stable(feature = "collections_bound", since = "1.17.0")]
 605     Included(#[stable(feature = "collections_bound", since = "1.17.0")] T),
 606     /// An exclusive bound.
 607     #[stable(feature = "collections_bound", since = "1.17.0")]
 608     Excluded(#[stable(feature = "collections_bound", since = "1.17.0")] T),
 609     /// An infinite endpoint. Indicates that there is no bound in this direction.
 610     #[stable(feature = "collections_bound", since = "1.17.0")]
 611     Unbounded,
 612 }
 613
 614 #[unstable(feature = "collections_range",
 615            reason = "might be replaced with `Into<_>` and a type containing two `Bound` values",
 616            issue = "30877")]
 617 /// `RangeBounds` is implemented by Rust's built-in range types, produced
 618 /// by range syntax like `..`, `a..`, `..b` or `c..d`.
 619 pub trait RangeBounds<T: ?Sized> {
 620     /// Start index bound.
 621     ///
 622     /// Returns the start value as a `Bound`.
 623     ///
 624     /// # Examples
 625     ///
 626     /// ```
 627     /// #![feature(collections_range)]
 628     ///
 629     /// # fn main() {
 630     /// use std::ops::Bound::*;
 631     /// use std::ops::RangeBounds;
 632     ///
 633     /// assert_eq!((..10).start(), Unbounded);
 634     /// assert_eq!((3..10).start(), Included(&3));
 635     /// # }
 636     /// ```
 637     fn start(&self) -> Bound<&T>;
 638
 639     /// End index bound.
 640     ///
 641     /// Returns the end value as a `Bound`.
 642     ///
 643     /// # Examples
 644     ///
 645     /// ```
 646     /// #![feature(collections_range)]
 647     ///
 648     /// # fn main() {
 649     /// use std::ops::Bound::*;
 650     /// use std::ops::RangeBounds;
 651     ///
 652     /// assert_eq!((3..).end(), Unbounded);
 653     /// assert_eq!((3..10).end(), Excluded(&10));
 654     /// # }
 655     /// ```
 656     fn end(&self) -> Bound<&T>;
 657
 658
 659     /// Returns `true` if `item` is contained in the range.
 660     ///
 661     /// # Examples
 662     ///
 663     /// ```
 664     /// #![feature(range_contains)]
 665     ///
 666     /// use std::f32;
 667     ///
 668     /// assert!( (3..5).contains(&4));
 669     /// assert!(!(3..5).contains(&2));
 670     ///
 671     /// assert!( (0.0..1.0).contains(&0.5));
 672     /// assert!(!(0.0..1.0).contains(&f32::NAN));
 673     /// assert!(!(0.0..f32::NAN).contains(&0.5));
 674     /// assert!(!(f32::NAN..1.0).contains(&0.5));
 675     #[unstable(feature = "range_contains", reason = "recently added as per RFC", issue = "32311")]
 676     fn contains<U>(&self, item: &U) -> bool
 677     where
 678         T: PartialOrd<U>,
 679         U: ?Sized + PartialOrd<T>,
 680     {
 681         (match self.start() {
 682             Included(ref start) => *start <= item,
 683             Excluded(ref start) => *start < item,
 684             Unbounded => true,
 685         })
 686         &&
 687         (match self.end() {
 688             Included(ref end) => item <= *end,
 689             Excluded(ref end) => item < *end,
 690             Unbounded => true,
 691         })
 692     }
 693 }
 694
 695 use self::Bound::{Excluded, Included, Unbounded};
 696
 697 #[unstable(feature = "collections_range",
 698            reason = "might be replaced with `Into<_>` and a type containing two `Bound` values",
 699            issue = "30877")]
 700 impl<T: ?Sized> RangeBounds<T> for RangeFull {
 701     fn start(&self) -> Bound<&T> {
 702         Unbounded
 703     }
 704     fn end(&self) -> Bound<&T> {
 705         Unbounded
 706     }
 707 }
 708
 709 #[unstable(feature = "collections_range",
 710            reason = "might be replaced with `Into<_>` and a type containing two `Bound` values",
 711            issue = "30877")]
 712 impl<T> RangeBounds<T> for RangeFrom<T> {
 713     fn start(&self) -> Bound<&T> {
 714         Included(&self.start)
 715     }
 716     fn end(&self) -> Bound<&T> {
 717         Unbounded
 718     }
 719 }
 720
 721 #[unstable(feature = "collections_range",
 722            reason = "might be replaced with `Into<_>` and a type containing two `Bound` values",
 723            issue = "30877")]
 724 impl<T> RangeBounds<T> for RangeTo<T> {
 725     fn start(&self) -> Bound<&T> {
 726         Unbounded
 727     }
 728     fn end(&self) -> Bound<&T> {
 729         Excluded(&self.end)
 730     }
 731 }
 732
 733 #[unstable(feature = "collections_range",
 734            reason = "might be replaced with `Into<_>` and a type containing two `Bound` values",
 735            issue = "30877")]
 736 impl<T> RangeBounds<T> for Range<T> {
 737     fn start(&self) -> Bound<&T> {
 738         Included(&self.start)
 739     }
 740     fn end(&self) -> Bound<&T> {
 741         Excluded(&self.end)
 742     }
 743 }
 744
 745 #[unstable(feature = "collections_range",
 746            reason = "might be replaced with `Into<_>` and a type containing two `Bound` values",
 747            issue = "30877")]
 748 impl<T> RangeBounds<T> for RangeInclusive<T> {
 749     fn start(&self) -> Bound<&T> {
 750         Included(&self.start)
 751     }
 752     fn end(&self) -> Bound<&T> {
 753         Included(&self.end)
 754     }
 755 }
 756
 757 #[unstable(feature = "collections_range",
 758            reason = "might be replaced with `Into<_>` and a type containing two `Bound` values",
 759            issue = "30877")]
 760 impl<T> RangeBounds<T> for RangeToInclusive<T> {
 761     fn start(&self) -> Bound<&T> {
 762         Unbounded
 763     }
 764     fn end(&self) -> Bound<&T> {
 765         Included(&self.end)
 766     }
 767 }
 768
 769 #[unstable(feature = "collections_range",
 770            reason = "might be replaced with `Into<_>` and a type containing two `Bound` values",
 771            issue = "30877")]
 772 impl<T> RangeBounds<T> for (Bound<T>, Bound<T>) {
 773     fn start(&self) -> Bound<&T> {
 774         match *self {
 775             (Included(ref start), _) => Included(start),
 776             (Excluded(ref start), _) => Excluded(start),
 777             (Unbounded, _)           => Unbounded,
 778         }
 779     }
 780
 781     fn end(&self) -> Bound<&T> {
 782         match *self {
 783             (_, Included(ref end)) => Included(end),
 784             (_, Excluded(ref end)) => Excluded(end),
 785             (_, Unbounded)         => Unbounded,
 786         }
 787     }
 788 }
 789
 790 #[unstable(feature = "collections_range",
 791            reason = "might be replaced with `Into<_>` and a type containing two `Bound` values",
 792            issue = "30877")]
 793 impl<'a, T: ?Sized + 'a> RangeBounds<T> for (Bound<&'a T>, Bound<&'a T>) {
 794     fn start(&self) -> Bound<&T> {
 795         self.0
 796     }
 797
 798     fn end(&self) -> Bound<&T> {
 799         self.1
 800     }
 801 }
 802
 803 #[unstable(feature = "collections_range",
 804            reason = "might be replaced with `Into<_>` and a type containing two `Bound` values",
 805            issue = "30877")]
 806 impl<'a, T> RangeBounds<T> for RangeFrom<&'a T> {
 807     fn start(&self) -> Bound<&T> {
 808         Included(self.start)
 809     }
 810     fn end(&self) -> Bound<&T> {
 811         Unbounded
 812     }
 813 }
 814
 815 #[unstable(feature = "collections_range",
 816            reason = "might be replaced with `Into<_>` and a type containing two `Bound` values",
 817            issue = "30877")]
 818 impl<'a, T> RangeBounds<T> for RangeTo<&'a T> {
 819     fn start(&self) -> Bound<&T> {
 820         Unbounded
 821     }
 822     fn end(&self) -> Bound<&T> {
 823         Excluded(self.end)
 824     }
 825 }
 826
 827 #[unstable(feature = "collections_range",
 828            reason = "might be replaced with `Into<_>` and a type containing two `Bound` values",
 829            issue = "30877")]
 830 impl<'a, T> RangeBounds<T> for Range<&'a T> {
 831     fn start(&self) -> Bound<&T> {
 832         Included(self.start)
 833     }
 834     fn end(&self) -> Bound<&T> {
 835         Excluded(self.end)
 836     }
 837 }
 838
 839 #[unstable(feature = "collections_range",
 840            reason = "might be replaced with `Into<_>` and a type containing two `Bound` values",
 841            issue = "30877")]
 842 impl<'a, T> RangeBounds<T> for RangeInclusive<&'a T> {
 843     fn start(&self) -> Bound<&T> {
 844         Included(self.start)
 845     }
 846     fn end(&self) -> Bound<&T> {
 847         Included(self.end)
 848     }
 849 }
 850
 851 #[unstable(feature = "collections_range",
 852            reason = "might be replaced with `Into<_>` and a type containing two `Bound` values",
 853            issue = "30877")]
 854 impl<'a, T> RangeBounds<T> for RangeToInclusive<&'a T> {
 855     fn start(&self) -> Bound<&T> {
 856         Unbounded
 857     }
 858     fn end(&self) -> Bound<&T> {
 859         Included(self.end)
 860     }
 861 }