core/ops/
range.rs

1use crate::fmt;
2use 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]); // This is the `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/// [slicing index]: crate::slice::SliceIndex
39#[lang = "RangeFull"]
40#[doc(alias = "..")]
41#[derive(Copy, Clone, Default, PartialEq, Eq, Hash)]
42#[stable(feature = "rust1", since = "1.0.0")]
43pub struct RangeFull;
44
45#[stable(feature = "rust1", since = "1.0.0")]
46impl fmt::Debug for RangeFull {
47    fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result {
48        write!(fmt, "..")
49    }
50}
51
52/// A (half-open) range bounded inclusively below and exclusively above
53/// (`start..end`).
54///
55/// The range `start..end` contains all values with `start <= x < end`.
56/// It is empty if `start >= end`.
57///
58/// # Examples
59///
60/// The `start..end` syntax is a `Range`:
61///
62/// ```
63/// assert_eq!((3..5), std::ops::Range { start: 3, end: 5 });
64/// assert_eq!(3 + 4 + 5, (3..6).sum());
65/// ```
66///
67/// ```
68/// let arr = [0, 1, 2, 3, 4];
69/// assert_eq!(arr[ ..  ], [0, 1, 2, 3, 4]);
70/// assert_eq!(arr[ .. 3], [0, 1, 2      ]);
71/// assert_eq!(arr[ ..=3], [0, 1, 2, 3   ]);
72/// assert_eq!(arr[1..  ], [   1, 2, 3, 4]);
73/// assert_eq!(arr[1.. 3], [   1, 2      ]); // This is a `Range`
74/// assert_eq!(arr[1..=3], [   1, 2, 3   ]);
75/// ```
76#[lang = "Range"]
77#[doc(alias = "..")]
78#[derive(Clone, Default, PartialEq, Eq, Hash)] // not Copy -- see #27186
79#[stable(feature = "rust1", since = "1.0.0")]
80pub struct Range<Idx> {
81    /// The lower bound of the range (inclusive).
82    #[stable(feature = "rust1", since = "1.0.0")]
83    pub start: Idx,
84    /// The upper bound of the range (exclusive).
85    #[stable(feature = "rust1", since = "1.0.0")]
86    pub end: Idx,
87}
88
89#[stable(feature = "rust1", since = "1.0.0")]
90impl<Idx: fmt::Debug> fmt::Debug for Range<Idx> {
91    fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result {
92        self.start.fmt(fmt)?;
93        write!(fmt, "..")?;
94        self.end.fmt(fmt)?;
95        Ok(())
96    }
97}
98
99impl<Idx: PartialOrd<Idx>> Range<Idx> {
100    /// Returns `true` if `item` is contained in the range.
101    ///
102    /// # Examples
103    ///
104    /// ```
105    /// assert!(!(3..5).contains(&2));
106    /// assert!( (3..5).contains(&3));
107    /// assert!( (3..5).contains(&4));
108    /// assert!(!(3..5).contains(&5));
109    ///
110    /// assert!(!(3..3).contains(&3));
111    /// assert!(!(3..2).contains(&3));
112    ///
113    /// assert!( (0.0..1.0).contains(&0.5));
114    /// assert!(!(0.0..1.0).contains(&f32::NAN));
115    /// assert!(!(0.0..f32::NAN).contains(&0.5));
116    /// assert!(!(f32::NAN..1.0).contains(&0.5));
117    /// ```
118    #[inline]
119    #[stable(feature = "range_contains", since = "1.35.0")]
120    pub fn contains<U>(&self, item: &U) -> bool
121    where
122        Idx: PartialOrd<U>,
123        U: ?Sized + PartialOrd<Idx>,
124    {
125        <Self as RangeBounds<Idx>>::contains(self, item)
126    }
127
128    /// Returns `true` if the range contains no items.
129    ///
130    /// # Examples
131    ///
132    /// ```
133    /// assert!(!(3..5).is_empty());
134    /// assert!( (3..3).is_empty());
135    /// assert!( (3..2).is_empty());
136    /// ```
137    ///
138    /// The range is empty if either side is incomparable:
139    ///
140    /// ```
141    /// assert!(!(3.0..5.0).is_empty());
142    /// assert!( (3.0..f32::NAN).is_empty());
143    /// assert!( (f32::NAN..5.0).is_empty());
144    /// ```
145    #[inline]
146    #[stable(feature = "range_is_empty", since = "1.47.0")]
147    pub fn is_empty(&self) -> bool {
148        !(self.start < self.end)
149    }
150}
151
152/// A range only bounded inclusively below (`start..`).
153///
154/// The `RangeFrom` `start..` contains all values with `x >= start`.
155///
156/// *Note*: Overflow in the [`Iterator`] implementation (when the contained
157/// data type reaches its numerical limit) is allowed to panic, wrap, or
158/// saturate. This behavior is defined by the implementation of the [`Step`]
159/// trait. For primitive integers, this follows the normal rules, and respects
160/// the overflow checks profile (panic in debug, wrap in release). Note also
161/// that overflow happens earlier than you might assume: the overflow happens
162/// in the call to `next` that yields the maximum value, as the range must be
163/// set to a state to yield the next value.
164///
165/// [`Step`]: crate::iter::Step
166///
167/// # Examples
168///
169/// The `start..` syntax is a `RangeFrom`:
170///
171/// ```
172/// assert_eq!((2..), std::ops::RangeFrom { start: 2 });
173/// assert_eq!(2 + 3 + 4, (2..).take(3).sum());
174/// ```
175///
176/// ```
177/// let arr = [0, 1, 2, 3, 4];
178/// assert_eq!(arr[ ..  ], [0, 1, 2, 3, 4]);
179/// assert_eq!(arr[ .. 3], [0, 1, 2      ]);
180/// assert_eq!(arr[ ..=3], [0, 1, 2, 3   ]);
181/// assert_eq!(arr[1..  ], [   1, 2, 3, 4]); // This is a `RangeFrom`
182/// assert_eq!(arr[1.. 3], [   1, 2      ]);
183/// assert_eq!(arr[1..=3], [   1, 2, 3   ]);
184/// ```
185#[lang = "RangeFrom"]
186#[doc(alias = "..")]
187#[derive(Clone, PartialEq, Eq, Hash)] // not Copy -- see #27186
188#[stable(feature = "rust1", since = "1.0.0")]
189pub struct RangeFrom<Idx> {
190    /// The lower bound of the range (inclusive).
191    #[stable(feature = "rust1", since = "1.0.0")]
192    pub start: Idx,
193}
194
195#[stable(feature = "rust1", since = "1.0.0")]
196impl<Idx: fmt::Debug> fmt::Debug for RangeFrom<Idx> {
197    fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result {
198        self.start.fmt(fmt)?;
199        write!(fmt, "..")?;
200        Ok(())
201    }
202}
203
204impl<Idx: PartialOrd<Idx>> RangeFrom<Idx> {
205    /// Returns `true` if `item` is contained in the range.
206    ///
207    /// # Examples
208    ///
209    /// ```
210    /// assert!(!(3..).contains(&2));
211    /// assert!( (3..).contains(&3));
212    /// assert!( (3..).contains(&1_000_000_000));
213    ///
214    /// assert!( (0.0..).contains(&0.5));
215    /// assert!(!(0.0..).contains(&f32::NAN));
216    /// assert!(!(f32::NAN..).contains(&0.5));
217    /// ```
218    #[inline]
219    #[stable(feature = "range_contains", since = "1.35.0")]
220    pub fn contains<U>(&self, item: &U) -> bool
221    where
222        Idx: PartialOrd<U>,
223        U: ?Sized + PartialOrd<Idx>,
224    {
225        <Self as RangeBounds<Idx>>::contains(self, item)
226    }
227}
228
229/// A range only bounded exclusively above (`..end`).
230///
231/// The `RangeTo` `..end` contains all values with `x < end`.
232/// It cannot serve as an [`Iterator`] because it doesn't have a starting point.
233///
234/// # Examples
235///
236/// The `..end` syntax is a `RangeTo`:
237///
238/// ```
239/// assert_eq!((..5), std::ops::RangeTo { end: 5 });
240/// ```
241///
242/// It does not have an [`IntoIterator`] implementation, so you can't use it in
243/// a `for` loop directly. This won't compile:
244///
245/// ```compile_fail,E0277
246/// // error[E0277]: the trait bound `std::ops::RangeTo<{integer}>:
247/// // std::iter::Iterator` is not satisfied
248/// for i in ..5 {
249///     // ...
250/// }
251/// ```
252///
253/// When used as a [slicing index], `RangeTo` produces a slice of all array
254/// elements before the index indicated by `end`.
255///
256/// ```
257/// let arr = [0, 1, 2, 3, 4];
258/// assert_eq!(arr[ ..  ], [0, 1, 2, 3, 4]);
259/// assert_eq!(arr[ .. 3], [0, 1, 2      ]); // This is a `RangeTo`
260/// assert_eq!(arr[ ..=3], [0, 1, 2, 3   ]);
261/// assert_eq!(arr[1..  ], [   1, 2, 3, 4]);
262/// assert_eq!(arr[1.. 3], [   1, 2      ]);
263/// assert_eq!(arr[1..=3], [   1, 2, 3   ]);
264/// ```
265///
266/// [slicing index]: crate::slice::SliceIndex
267#[lang = "RangeTo"]
268#[doc(alias = "..")]
269#[derive(Copy, Clone, PartialEq, Eq, Hash)]
270#[stable(feature = "rust1", since = "1.0.0")]
271pub struct RangeTo<Idx> {
272    /// The upper bound of the range (exclusive).
273    #[stable(feature = "rust1", since = "1.0.0")]
274    pub end: Idx,
275}
276
277#[stable(feature = "rust1", since = "1.0.0")]
278impl<Idx: fmt::Debug> fmt::Debug for RangeTo<Idx> {
279    fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result {
280        write!(fmt, "..")?;
281        self.end.fmt(fmt)?;
282        Ok(())
283    }
284}
285
286impl<Idx: PartialOrd<Idx>> RangeTo<Idx> {
287    /// Returns `true` if `item` is contained in the range.
288    ///
289    /// # Examples
290    ///
291    /// ```
292    /// assert!( (..5).contains(&-1_000_000_000));
293    /// assert!( (..5).contains(&4));
294    /// assert!(!(..5).contains(&5));
295    ///
296    /// assert!( (..1.0).contains(&0.5));
297    /// assert!(!(..1.0).contains(&f32::NAN));
298    /// assert!(!(..f32::NAN).contains(&0.5));
299    /// ```
300    #[inline]
301    #[stable(feature = "range_contains", since = "1.35.0")]
302    pub fn contains<U>(&self, item: &U) -> bool
303    where
304        Idx: PartialOrd<U>,
305        U: ?Sized + PartialOrd<Idx>,
306    {
307        <Self as RangeBounds<Idx>>::contains(self, item)
308    }
309}
310
311/// A range bounded inclusively below and above (`start..=end`).
312///
313/// The `RangeInclusive` `start..=end` contains all values with `x >= start`
314/// and `x <= end`. It is empty unless `start <= end`.
315///
316/// This iterator is [fused], but the specific values of `start` and `end` after
317/// iteration has finished are **unspecified** other than that [`.is_empty()`]
318/// will return `true` once no more values will be produced.
319///
320/// [fused]: crate::iter::FusedIterator
321/// [`.is_empty()`]: RangeInclusive::is_empty
322///
323/// # Examples
324///
325/// The `start..=end` syntax is a `RangeInclusive`:
326///
327/// ```
328/// assert_eq!((3..=5), std::ops::RangeInclusive::new(3, 5));
329/// assert_eq!(3 + 4 + 5, (3..=5).sum());
330/// ```
331///
332/// ```
333/// let arr = [0, 1, 2, 3, 4];
334/// assert_eq!(arr[ ..  ], [0, 1, 2, 3, 4]);
335/// assert_eq!(arr[ .. 3], [0, 1, 2      ]);
336/// assert_eq!(arr[ ..=3], [0, 1, 2, 3   ]);
337/// assert_eq!(arr[1..  ], [   1, 2, 3, 4]);
338/// assert_eq!(arr[1.. 3], [   1, 2      ]);
339/// assert_eq!(arr[1..=3], [   1, 2, 3   ]); // This is a `RangeInclusive`
340/// ```
341#[lang = "RangeInclusive"]
342#[doc(alias = "..=")]
343#[derive(Clone, PartialEq, Eq, Hash)] // not Copy -- see #27186
344#[stable(feature = "inclusive_range", since = "1.26.0")]
345pub struct RangeInclusive<Idx> {
346    // Note that the fields here are not public to allow changing the
347    // representation in the future; in particular, while we could plausibly
348    // expose start/end, modifying them without changing (future/current)
349    // private fields may lead to incorrect behavior, so we don't want to
350    // support that mode.
351    pub(crate) start: Idx,
352    pub(crate) end: Idx,
353
354    // This field is:
355    //  - `false` upon construction
356    //  - `false` when iteration has yielded an element and the iterator is not exhausted
357    //  - `true` when iteration has been used to exhaust the iterator
358    //
359    // This is required to support PartialEq and Hash without a PartialOrd bound or specialization.
360    pub(crate) exhausted: bool,
361}
362
363impl<Idx> RangeInclusive<Idx> {
364    /// Creates a new inclusive range. Equivalent to writing `start..=end`.
365    ///
366    /// # Examples
367    ///
368    /// ```
369    /// use std::ops::RangeInclusive;
370    ///
371    /// assert_eq!(3..=5, RangeInclusive::new(3, 5));
372    /// ```
373    #[lang = "range_inclusive_new"]
374    #[stable(feature = "inclusive_range_methods", since = "1.27.0")]
375    #[inline]
376    #[rustc_promotable]
377    #[rustc_const_stable(feature = "const_range_new", since = "1.32.0")]
378    pub const fn new(start: Idx, end: Idx) -> Self {
379        Self { start, end, exhausted: false }
380    }
381
382    /// Returns the lower bound of the range (inclusive).
383    ///
384    /// When using an inclusive range for iteration, the values of `start()` and
385    /// [`end()`] are unspecified after the iteration ended. To determine
386    /// whether the inclusive range is empty, use the [`is_empty()`] method
387    /// instead of comparing `start() > end()`.
388    ///
389    /// Note: the value returned by this method is unspecified after the range
390    /// has been iterated to exhaustion.
391    ///
392    /// [`end()`]: RangeInclusive::end
393    /// [`is_empty()`]: RangeInclusive::is_empty
394    ///
395    /// # Examples
396    ///
397    /// ```
398    /// assert_eq!((3..=5).start(), &3);
399    /// ```
400    #[stable(feature = "inclusive_range_methods", since = "1.27.0")]
401    #[rustc_const_stable(feature = "const_inclusive_range_methods", since = "1.32.0")]
402    #[inline]
403    pub const fn start(&self) -> &Idx {
404        &self.start
405    }
406
407    /// Returns the upper bound of the range (inclusive).
408    ///
409    /// When using an inclusive range for iteration, the values of [`start()`]
410    /// and `end()` are unspecified after the iteration ended. To determine
411    /// whether the inclusive range is empty, use the [`is_empty()`] method
412    /// instead of comparing `start() > end()`.
413    ///
414    /// Note: the value returned by this method is unspecified after the range
415    /// has been iterated to exhaustion.
416    ///
417    /// [`start()`]: RangeInclusive::start
418    /// [`is_empty()`]: RangeInclusive::is_empty
419    ///
420    /// # Examples
421    ///
422    /// ```
423    /// assert_eq!((3..=5).end(), &5);
424    /// ```
425    #[stable(feature = "inclusive_range_methods", since = "1.27.0")]
426    #[rustc_const_stable(feature = "const_inclusive_range_methods", since = "1.32.0")]
427    #[inline]
428    pub const fn end(&self) -> &Idx {
429        &self.end
430    }
431
432    /// Destructures the `RangeInclusive` into (lower bound, upper (inclusive) bound).
433    ///
434    /// Note: the value returned by this method is unspecified after the range
435    /// has been iterated to exhaustion.
436    ///
437    /// # Examples
438    ///
439    /// ```
440    /// assert_eq!((3..=5).into_inner(), (3, 5));
441    /// ```
442    #[stable(feature = "inclusive_range_methods", since = "1.27.0")]
443    #[inline]
444    #[rustc_const_unstable(feature = "const_range_bounds", issue = "108082")]
445    pub const fn into_inner(self) -> (Idx, Idx) {
446        (self.start, self.end)
447    }
448}
449
450impl RangeInclusive<usize> {
451    /// Converts to an exclusive `Range` for `SliceIndex` implementations.
452    /// The caller is responsible for dealing with `end == usize::MAX`.
453    #[inline]
454    pub(crate) const fn into_slice_range(self) -> Range<usize> {
455        // If we're not exhausted, we want to simply slice `start..end + 1`.
456        // If we are exhausted, then slicing with `end + 1..end + 1` gives us an
457        // empty range that is still subject to bounds-checks for that endpoint.
458        let exclusive_end = self.end + 1;
459        let start = if self.exhausted { exclusive_end } else { self.start };
460        start..exclusive_end
461    }
462}
463
464#[stable(feature = "inclusive_range", since = "1.26.0")]
465impl<Idx: fmt::Debug> fmt::Debug for RangeInclusive<Idx> {
466    fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result {
467        self.start.fmt(fmt)?;
468        write!(fmt, "..=")?;
469        self.end.fmt(fmt)?;
470        if self.exhausted {
471            write!(fmt, " (exhausted)")?;
472        }
473        Ok(())
474    }
475}
476
477impl<Idx: PartialOrd<Idx>> RangeInclusive<Idx> {
478    /// Returns `true` if `item` is contained in the range.
479    ///
480    /// # Examples
481    ///
482    /// ```
483    /// assert!(!(3..=5).contains(&2));
484    /// assert!( (3..=5).contains(&3));
485    /// assert!( (3..=5).contains(&4));
486    /// assert!( (3..=5).contains(&5));
487    /// assert!(!(3..=5).contains(&6));
488    ///
489    /// assert!( (3..=3).contains(&3));
490    /// assert!(!(3..=2).contains(&3));
491    ///
492    /// assert!( (0.0..=1.0).contains(&1.0));
493    /// assert!(!(0.0..=1.0).contains(&f32::NAN));
494    /// assert!(!(0.0..=f32::NAN).contains(&0.0));
495    /// assert!(!(f32::NAN..=1.0).contains(&1.0));
496    /// ```
497    ///
498    /// This method always returns `false` after iteration has finished:
499    ///
500    /// ```
501    /// let mut r = 3..=5;
502    /// assert!(r.contains(&3) && r.contains(&5));
503    /// for _ in r.by_ref() {}
504    /// // Precise field values are unspecified here
505    /// assert!(!r.contains(&3) && !r.contains(&5));
506    /// ```
507    #[inline]
508    #[stable(feature = "range_contains", since = "1.35.0")]
509    pub fn contains<U>(&self, item: &U) -> bool
510    where
511        Idx: PartialOrd<U>,
512        U: ?Sized + PartialOrd<Idx>,
513    {
514        <Self as RangeBounds<Idx>>::contains(self, item)
515    }
516
517    /// Returns `true` if the range contains no items.
518    ///
519    /// # Examples
520    ///
521    /// ```
522    /// assert!(!(3..=5).is_empty());
523    /// assert!(!(3..=3).is_empty());
524    /// assert!( (3..=2).is_empty());
525    /// ```
526    ///
527    /// The range is empty if either side is incomparable:
528    ///
529    /// ```
530    /// assert!(!(3.0..=5.0).is_empty());
531    /// assert!( (3.0..=f32::NAN).is_empty());
532    /// assert!( (f32::NAN..=5.0).is_empty());
533    /// ```
534    ///
535    /// This method returns `true` after iteration has finished:
536    ///
537    /// ```
538    /// let mut r = 3..=5;
539    /// for _ in r.by_ref() {}
540    /// // Precise field values are unspecified here
541    /// assert!(r.is_empty());
542    /// ```
543    #[stable(feature = "range_is_empty", since = "1.47.0")]
544    #[inline]
545    pub fn is_empty(&self) -> bool {
546        self.exhausted || !(self.start <= self.end)
547    }
548}
549
550/// A range only bounded inclusively above (`..=end`).
551///
552/// The `RangeToInclusive` `..=end` contains all values with `x <= end`.
553/// It cannot serve as an [`Iterator`] because it doesn't have a starting point.
554///
555/// # Examples
556///
557/// The `..=end` syntax is a `RangeToInclusive`:
558///
559/// ```
560/// assert_eq!((..=5), std::ops::RangeToInclusive{ end: 5 });
561/// ```
562///
563/// It does not have an [`IntoIterator`] implementation, so you can't use it in a
564/// `for` loop directly. This won't compile:
565///
566/// ```compile_fail,E0277
567/// // error[E0277]: the trait bound `std::ops::RangeToInclusive<{integer}>:
568/// // std::iter::Iterator` is not satisfied
569/// for i in ..=5 {
570///     // ...
571/// }
572/// ```
573///
574/// When used as a [slicing index], `RangeToInclusive` produces a slice of all
575/// array elements up to and including the index indicated by `end`.
576///
577/// ```
578/// let arr = [0, 1, 2, 3, 4];
579/// assert_eq!(arr[ ..  ], [0, 1, 2, 3, 4]);
580/// assert_eq!(arr[ .. 3], [0, 1, 2      ]);
581/// assert_eq!(arr[ ..=3], [0, 1, 2, 3   ]); // This is a `RangeToInclusive`
582/// assert_eq!(arr[1..  ], [   1, 2, 3, 4]);
583/// assert_eq!(arr[1.. 3], [   1, 2      ]);
584/// assert_eq!(arr[1..=3], [   1, 2, 3   ]);
585/// ```
586///
587/// [slicing index]: crate::slice::SliceIndex
588#[lang = "RangeToInclusive"]
589#[doc(alias = "..=")]
590#[derive(Copy, Clone, PartialEq, Eq, Hash)]
591#[stable(feature = "inclusive_range", since = "1.26.0")]
592pub struct RangeToInclusive<Idx> {
593    /// The upper bound of the range (inclusive)
594    #[stable(feature = "inclusive_range", since = "1.26.0")]
595    pub end: Idx,
596}
597
598#[stable(feature = "inclusive_range", since = "1.26.0")]
599impl<Idx: fmt::Debug> fmt::Debug for RangeToInclusive<Idx> {
600    fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result {
601        write!(fmt, "..=")?;
602        self.end.fmt(fmt)?;
603        Ok(())
604    }
605}
606
607impl<Idx: PartialOrd<Idx>> RangeToInclusive<Idx> {
608    /// Returns `true` if `item` is contained in the range.
609    ///
610    /// # Examples
611    ///
612    /// ```
613    /// assert!( (..=5).contains(&-1_000_000_000));
614    /// assert!( (..=5).contains(&5));
615    /// assert!(!(..=5).contains(&6));
616    ///
617    /// assert!( (..=1.0).contains(&1.0));
618    /// assert!(!(..=1.0).contains(&f32::NAN));
619    /// assert!(!(..=f32::NAN).contains(&0.5));
620    /// ```
621    #[inline]
622    #[stable(feature = "range_contains", since = "1.35.0")]
623    pub fn contains<U>(&self, item: &U) -> bool
624    where
625        Idx: PartialOrd<U>,
626        U: ?Sized + PartialOrd<Idx>,
627    {
628        <Self as RangeBounds<Idx>>::contains(self, item)
629    }
630}
631
632// RangeToInclusive<Idx> cannot impl From<RangeTo<Idx>>
633// because underflow would be possible with (..0).into()
634
635/// An endpoint of a range of keys.
636///
637/// # Examples
638///
639/// `Bound`s are range endpoints:
640///
641/// ```
642/// use std::ops::Bound::*;
643/// use std::ops::RangeBounds;
644///
645/// assert_eq!((..100).start_bound(), Unbounded);
646/// assert_eq!((1..12).start_bound(), Included(&1));
647/// assert_eq!((1..12).end_bound(), Excluded(&12));
648/// ```
649///
650/// Using a tuple of `Bound`s as an argument to [`BTreeMap::range`].
651/// Note that in most cases, it's better to use range syntax (`1..5`) instead.
652///
653/// ```
654/// use std::collections::BTreeMap;
655/// use std::ops::Bound::{Excluded, Included, Unbounded};
656///
657/// let mut map = BTreeMap::new();
658/// map.insert(3, "a");
659/// map.insert(5, "b");
660/// map.insert(8, "c");
661///
662/// for (key, value) in map.range((Excluded(3), Included(8))) {
663///     println!("{key}: {value}");
664/// }
665///
666/// assert_eq!(Some((&3, &"a")), map.range((Unbounded, Included(5))).next());
667/// ```
668///
669/// [`BTreeMap::range`]: ../../std/collections/btree_map/struct.BTreeMap.html#method.range
670#[stable(feature = "collections_bound", since = "1.17.0")]
671#[derive(Clone, Copy, Debug, Hash, PartialEq, Eq)]
672pub enum Bound<T> {
673    /// An inclusive bound.
674    #[stable(feature = "collections_bound", since = "1.17.0")]
675    Included(#[stable(feature = "collections_bound", since = "1.17.0")] T),
676    /// An exclusive bound.
677    #[stable(feature = "collections_bound", since = "1.17.0")]
678    Excluded(#[stable(feature = "collections_bound", since = "1.17.0")] T),
679    /// An infinite endpoint. Indicates that there is no bound in this direction.
680    #[stable(feature = "collections_bound", since = "1.17.0")]
681    Unbounded,
682}
683
684impl<T> Bound<T> {
685    /// Converts from `&Bound<T>` to `Bound<&T>`.
686    #[inline]
687    #[stable(feature = "bound_as_ref_shared", since = "1.65.0")]
688    pub fn as_ref(&self) -> Bound<&T> {
689        match *self {
690            Included(ref x) => Included(x),
691            Excluded(ref x) => Excluded(x),
692            Unbounded => Unbounded,
693        }
694    }
695
696    /// Converts from `&mut Bound<T>` to `Bound<&mut T>`.
697    #[inline]
698    #[unstable(feature = "bound_as_ref", issue = "80996")]
699    pub fn as_mut(&mut self) -> Bound<&mut T> {
700        match *self {
701            Included(ref mut x) => Included(x),
702            Excluded(ref mut x) => Excluded(x),
703            Unbounded => Unbounded,
704        }
705    }
706
707    /// Maps a `Bound<T>` to a `Bound<U>` by applying a function to the contained value (including
708    /// both `Included` and `Excluded`), returning a `Bound` of the same kind.
709    ///
710    /// # Examples
711    ///
712    /// ```
713    /// use std::ops::Bound::*;
714    ///
715    /// let bound_string = Included("Hello, World!");
716    ///
717    /// assert_eq!(bound_string.map(|s| s.len()), Included(13));
718    /// ```
719    ///
720    /// ```
721    /// use std::ops::Bound;
722    /// use Bound::*;
723    ///
724    /// let unbounded_string: Bound<String> = Unbounded;
725    ///
726    /// assert_eq!(unbounded_string.map(|s| s.len()), Unbounded);
727    /// ```
728    #[inline]
729    #[stable(feature = "bound_map", since = "1.77.0")]
730    pub fn map<U, F: FnOnce(T) -> U>(self, f: F) -> Bound<U> {
731        match self {
732            Unbounded => Unbounded,
733            Included(x) => Included(f(x)),
734            Excluded(x) => Excluded(f(x)),
735        }
736    }
737}
738
739impl<T: Clone> Bound<&T> {
740    /// Map a `Bound<&T>` to a `Bound<T>` by cloning the contents of the bound.
741    ///
742    /// # Examples
743    ///
744    /// ```
745    /// use std::ops::Bound::*;
746    /// use std::ops::RangeBounds;
747    ///
748    /// assert_eq!((1..12).start_bound(), Included(&1));
749    /// assert_eq!((1..12).start_bound().cloned(), Included(1));
750    /// ```
751    #[must_use = "`self` will be dropped if the result is not used"]
752    #[stable(feature = "bound_cloned", since = "1.55.0")]
753    pub fn cloned(self) -> Bound<T> {
754        match self {
755            Bound::Unbounded => Bound::Unbounded,
756            Bound::Included(x) => Bound::Included(x.clone()),
757            Bound::Excluded(x) => Bound::Excluded(x.clone()),
758        }
759    }
760}
761
762/// `RangeBounds` is implemented by Rust's built-in range types, produced
763/// by range syntax like `..`, `a..`, `..b`, `..=c`, `d..e`, or `f..=g`.
764#[stable(feature = "collections_range", since = "1.28.0")]
765#[rustc_diagnostic_item = "RangeBounds"]
766pub trait RangeBounds<T: ?Sized> {
767    /// Start index bound.
768    ///
769    /// Returns the start value as a `Bound`.
770    ///
771    /// # Examples
772    ///
773    /// ```
774    /// # fn main() {
775    /// use std::ops::Bound::*;
776    /// use std::ops::RangeBounds;
777    ///
778    /// assert_eq!((..10).start_bound(), Unbounded);
779    /// assert_eq!((3..10).start_bound(), Included(&3));
780    /// # }
781    /// ```
782    #[stable(feature = "collections_range", since = "1.28.0")]
783    fn start_bound(&self) -> Bound<&T>;
784
785    /// End index bound.
786    ///
787    /// Returns the end value as a `Bound`.
788    ///
789    /// # Examples
790    ///
791    /// ```
792    /// # fn main() {
793    /// use std::ops::Bound::*;
794    /// use std::ops::RangeBounds;
795    ///
796    /// assert_eq!((3..).end_bound(), Unbounded);
797    /// assert_eq!((3..10).end_bound(), Excluded(&10));
798    /// # }
799    /// ```
800    #[stable(feature = "collections_range", since = "1.28.0")]
801    fn end_bound(&self) -> Bound<&T>;
802
803    /// Returns `true` if `item` is contained in the range.
804    ///
805    /// # Examples
806    ///
807    /// ```
808    /// assert!( (3..5).contains(&4));
809    /// assert!(!(3..5).contains(&2));
810    ///
811    /// assert!( (0.0..1.0).contains(&0.5));
812    /// assert!(!(0.0..1.0).contains(&f32::NAN));
813    /// assert!(!(0.0..f32::NAN).contains(&0.5));
814    /// assert!(!(f32::NAN..1.0).contains(&0.5));
815    #[inline]
816    #[stable(feature = "range_contains", since = "1.35.0")]
817    fn contains<U>(&self, item: &U) -> bool
818    where
819        T: PartialOrd<U>,
820        U: ?Sized + PartialOrd<T>,
821    {
822        (match self.start_bound() {
823            Included(start) => start <= item,
824            Excluded(start) => start < item,
825            Unbounded => true,
826        }) && (match self.end_bound() {
827            Included(end) => item <= end,
828            Excluded(end) => item < end,
829            Unbounded => true,
830        })
831    }
832}
833
834/// Used to convert a range into start and end bounds, consuming the
835/// range by value.
836///
837/// `IntoBounds` is implemented by Rust’s built-in range types, produced
838/// by range syntax like `..`, `a..`, `..b`, `..=c`, `d..e`, or `f..=g`.
839#[unstable(feature = "range_into_bounds", issue = "136903")]
840pub trait IntoBounds<T>: RangeBounds<T> {
841    /// Convert this range into the start and end bounds.
842    /// Returns `(start_bound, end_bound)`.
843    ///
844    /// # Examples
845    ///
846    /// ```
847    /// #![feature(range_into_bounds)]
848    ///
849    /// use std::ops::Bound::*;
850    /// use std::ops::IntoBounds;
851    ///
852    /// assert_eq!((0..5).into_bounds(), (Included(0), Excluded(5)));
853    /// assert_eq!((..=7).into_bounds(), (Unbounded, Included(7)));
854    /// ```
855    fn into_bounds(self) -> (Bound<T>, Bound<T>);
856}
857
858use self::Bound::{Excluded, Included, Unbounded};
859
860#[stable(feature = "collections_range", since = "1.28.0")]
861impl<T: ?Sized> RangeBounds<T> for RangeFull {
862    fn start_bound(&self) -> Bound<&T> {
863        Unbounded
864    }
865    fn end_bound(&self) -> Bound<&T> {
866        Unbounded
867    }
868}
869
870#[unstable(feature = "range_into_bounds", issue = "136903")]
871impl<T> IntoBounds<T> for RangeFull {
872    fn into_bounds(self) -> (Bound<T>, Bound<T>) {
873        (Unbounded, Unbounded)
874    }
875}
876
877#[stable(feature = "collections_range", since = "1.28.0")]
878impl<T> RangeBounds<T> for RangeFrom<T> {
879    fn start_bound(&self) -> Bound<&T> {
880        Included(&self.start)
881    }
882    fn end_bound(&self) -> Bound<&T> {
883        Unbounded
884    }
885}
886
887#[unstable(feature = "range_into_bounds", issue = "136903")]
888impl<T> IntoBounds<T> for RangeFrom<T> {
889    fn into_bounds(self) -> (Bound<T>, Bound<T>) {
890        (Included(self.start), Unbounded)
891    }
892}
893
894#[stable(feature = "collections_range", since = "1.28.0")]
895impl<T> RangeBounds<T> for RangeTo<T> {
896    fn start_bound(&self) -> Bound<&T> {
897        Unbounded
898    }
899    fn end_bound(&self) -> Bound<&T> {
900        Excluded(&self.end)
901    }
902}
903
904#[unstable(feature = "range_into_bounds", issue = "136903")]
905impl<T> IntoBounds<T> for RangeTo<T> {
906    fn into_bounds(self) -> (Bound<T>, Bound<T>) {
907        (Unbounded, Excluded(self.end))
908    }
909}
910
911#[stable(feature = "collections_range", since = "1.28.0")]
912impl<T> RangeBounds<T> for Range<T> {
913    fn start_bound(&self) -> Bound<&T> {
914        Included(&self.start)
915    }
916    fn end_bound(&self) -> Bound<&T> {
917        Excluded(&self.end)
918    }
919}
920
921#[unstable(feature = "range_into_bounds", issue = "136903")]
922impl<T> IntoBounds<T> for Range<T> {
923    fn into_bounds(self) -> (Bound<T>, Bound<T>) {
924        (Included(self.start), Excluded(self.end))
925    }
926}
927
928#[stable(feature = "collections_range", since = "1.28.0")]
929impl<T> RangeBounds<T> for RangeInclusive<T> {
930    fn start_bound(&self) -> Bound<&T> {
931        Included(&self.start)
932    }
933    fn end_bound(&self) -> Bound<&T> {
934        if self.exhausted {
935            // When the iterator is exhausted, we usually have start == end,
936            // but we want the range to appear empty, containing nothing.
937            Excluded(&self.end)
938        } else {
939            Included(&self.end)
940        }
941    }
942}
943
944#[unstable(feature = "range_into_bounds", issue = "136903")]
945impl<T> IntoBounds<T> for RangeInclusive<T> {
946    fn into_bounds(self) -> (Bound<T>, Bound<T>) {
947        (
948            Included(self.start),
949            if self.exhausted {
950                // When the iterator is exhausted, we usually have start == end,
951                // but we want the range to appear empty, containing nothing.
952                Excluded(self.end)
953            } else {
954                Included(self.end)
955            },
956        )
957    }
958}
959
960#[stable(feature = "collections_range", since = "1.28.0")]
961impl<T> RangeBounds<T> for RangeToInclusive<T> {
962    fn start_bound(&self) -> Bound<&T> {
963        Unbounded
964    }
965    fn end_bound(&self) -> Bound<&T> {
966        Included(&self.end)
967    }
968}
969
970#[unstable(feature = "range_into_bounds", issue = "136903")]
971impl<T> IntoBounds<T> for RangeToInclusive<T> {
972    fn into_bounds(self) -> (Bound<T>, Bound<T>) {
973        (Unbounded, Included(self.end))
974    }
975}
976
977#[stable(feature = "collections_range", since = "1.28.0")]
978impl<T> RangeBounds<T> for (Bound<T>, Bound<T>) {
979    fn start_bound(&self) -> Bound<&T> {
980        match *self {
981            (Included(ref start), _) => Included(start),
982            (Excluded(ref start), _) => Excluded(start),
983            (Unbounded, _) => Unbounded,
984        }
985    }
986
987    fn end_bound(&self) -> Bound<&T> {
988        match *self {
989            (_, Included(ref end)) => Included(end),
990            (_, Excluded(ref end)) => Excluded(end),
991            (_, Unbounded) => Unbounded,
992        }
993    }
994}
995
996#[unstable(feature = "range_into_bounds", issue = "136903")]
997impl<T> IntoBounds<T> for (Bound<T>, Bound<T>) {
998    fn into_bounds(self) -> (Bound<T>, Bound<T>) {
999        self
1000    }
1001}
1002
1003#[stable(feature = "collections_range", since = "1.28.0")]
1004impl<'a, T: ?Sized + 'a> RangeBounds<T> for (Bound<&'a T>, Bound<&'a T>) {
1005    fn start_bound(&self) -> Bound<&T> {
1006        self.0
1007    }
1008
1009    fn end_bound(&self) -> Bound<&T> {
1010        self.1
1011    }
1012}
1013
1014#[stable(feature = "collections_range", since = "1.28.0")]
1015impl<T> RangeBounds<T> for RangeFrom<&T> {
1016    fn start_bound(&self) -> Bound<&T> {
1017        Included(self.start)
1018    }
1019    fn end_bound(&self) -> Bound<&T> {
1020        Unbounded
1021    }
1022}
1023
1024#[stable(feature = "collections_range", since = "1.28.0")]
1025impl<T> RangeBounds<T> for RangeTo<&T> {
1026    fn start_bound(&self) -> Bound<&T> {
1027        Unbounded
1028    }
1029    fn end_bound(&self) -> Bound<&T> {
1030        Excluded(self.end)
1031    }
1032}
1033
1034#[stable(feature = "collections_range", since = "1.28.0")]
1035impl<T> RangeBounds<T> for Range<&T> {
1036    fn start_bound(&self) -> Bound<&T> {
1037        Included(self.start)
1038    }
1039    fn end_bound(&self) -> Bound<&T> {
1040        Excluded(self.end)
1041    }
1042}
1043
1044#[stable(feature = "collections_range", since = "1.28.0")]
1045impl<T> RangeBounds<T> for RangeInclusive<&T> {
1046    fn start_bound(&self) -> Bound<&T> {
1047        Included(self.start)
1048    }
1049    fn end_bound(&self) -> Bound<&T> {
1050        Included(self.end)
1051    }
1052}
1053
1054#[stable(feature = "collections_range", since = "1.28.0")]
1055impl<T> RangeBounds<T> for RangeToInclusive<&T> {
1056    fn start_bound(&self) -> Bound<&T> {
1057        Unbounded
1058    }
1059    fn end_bound(&self) -> Bound<&T> {
1060        Included(self.end)
1061    }
1062}
1063
1064/// An internal helper for `split_off` functions indicating
1065/// which end a `OneSidedRange` is bounded on.
1066#[unstable(feature = "one_sided_range", issue = "69780")]
1067#[allow(missing_debug_implementations)]
1068pub enum OneSidedRangeBound {
1069    /// The range is bounded inclusively from below and is unbounded above.
1070    StartInclusive,
1071    /// The range is bounded exclusively from above and is unbounded below.
1072    End,
1073    /// The range is bounded inclusively from above and is unbounded below.
1074    EndInclusive,
1075}
1076
1077/// `OneSidedRange` is implemented for built-in range types that are unbounded
1078/// on one side. For example, `a..`, `..b` and `..=c` implement `OneSidedRange`,
1079/// but `..`, `d..e`, and `f..=g` do not.
1080///
1081/// Types that implement `OneSidedRange<T>` must return `Bound::Unbounded`
1082/// from one of `RangeBounds::start_bound` or `RangeBounds::end_bound`.
1083#[unstable(feature = "one_sided_range", issue = "69780")]
1084pub trait OneSidedRange<T: ?Sized>: RangeBounds<T> {
1085    /// An internal-only helper function for `split_off` and
1086    /// `split_off_mut` that returns the bound of the one-sided range.
1087    fn bound(self) -> (OneSidedRangeBound, T);
1088}
1089
1090#[unstable(feature = "one_sided_range", issue = "69780")]
1091impl<T> OneSidedRange<T> for RangeTo<T>
1092where
1093    Self: RangeBounds<T>,
1094{
1095    fn bound(self) -> (OneSidedRangeBound, T) {
1096        (OneSidedRangeBound::End, self.end)
1097    }
1098}
1099
1100#[unstable(feature = "one_sided_range", issue = "69780")]
1101impl<T> OneSidedRange<T> for RangeFrom<T>
1102where
1103    Self: RangeBounds<T>,
1104{
1105    fn bound(self) -> (OneSidedRangeBound, T) {
1106        (OneSidedRangeBound::StartInclusive, self.start)
1107    }
1108}
1109
1110#[unstable(feature = "one_sided_range", issue = "69780")]
1111impl<T> OneSidedRange<T> for RangeToInclusive<T>
1112where
1113    Self: RangeBounds<T>,
1114{
1115    fn bound(self) -> (OneSidedRangeBound, T) {
1116        (OneSidedRangeBound::EndInclusive, self.end)
1117    }
1118}