library/core/src/cmp.rs

   1 //! Utilities for comparing and ordering values.
   2 //!
   3 //! This module contains various tools for comparing and ordering values. In
   4 //! summary:
   5 //!
   6 //! * [`Eq`] and [`PartialEq`] are traits that allow you to define total and
   7 //!   partial equality between values, respectively. Implementing them overloads
   8 //!   the `==` and `!=` operators.
   9 //! * [`Ord`] and [`PartialOrd`] are traits that allow you to define total and
  10 //!   partial orderings between values, respectively. Implementing them overloads
  11 //!   the `<`, `<=`, `>`, and `>=` operators.
  12 //! * [`Ordering`] is an enum returned by the main functions of [`Ord`] and
  13 //!   [`PartialOrd`], and describes an ordering.
  14 //! * [`Reverse`] is a struct that allows you to easily reverse an ordering.
  15 //! * [`max`] and [`min`] are functions that build off of [`Ord`] and allow you
  16 //!   to find the maximum or minimum of two values.
  17 //!
  18 //! For more details, see the respective documentation of each item in the list.
  19 //!
  20 //! [`max`]: Ord::max
  21 //! [`min`]: Ord::min
  22
  23 #![stable(feature = "rust1", since = "1.0.0")]
  24
  25 use crate::const_closure::ConstFnMutClosure;
  26 use crate::marker::Destruct;
  27 #[cfg(bootstrap)]
  28 use crate::marker::StructuralPartialEq;
  29
  30 use self::Ordering::*;
  31
  32 /// Trait for equality comparisons which are [partial equivalence
  33 /// relations](https://en.wikipedia.org/wiki/Partial_equivalence_relation).
  34 ///
  35 /// `x.eq(y)` can also be written `x == y`, and `x.ne(y)` can be written `x != y`.
  36 /// We use the easier-to-read infix notation in the remainder of this documentation.
  37 ///
  38 /// This trait allows for partial equality, for types that do not have a full
  39 /// equivalence relation. For example, in floating point numbers `NaN != NaN`,
  40 /// so floating point types implement `PartialEq` but not [`trait@Eq`].
  41 ///
  42 /// Implementations must ensure that `eq` and `ne` are consistent with each other:
  43 ///
  44 /// - `a != b` if and only if `!(a == b)`.
  45 ///
  46 /// The default implementation of `ne` provides this consistency and is almost
  47 /// always sufficient. It should not be overridden without very good reason.
  48 ///
  49 /// If [`PartialOrd`] or [`Ord`] are also implemented for `Self` and `Rhs`, their methods must also
  50 /// be consistent with `PartialEq` (see the documentation of those traits for the exact
  51 /// requirements). It's easy to accidentally make them disagree by deriving some of the traits and
  52 /// manually implementing others.
  53 ///
  54 /// The equality relation `==` must satisfy the following conditions
  55 /// (for all `a`, `b`, `c` of type `A`, `B`, `C`):
  56 ///
  57 /// - **Symmetric**: if `A: PartialEq<B>` and `B: PartialEq<A>`, then **`a == b`
  58 ///   implies `b == a`**; and
  59 ///
  60 /// - **Transitive**: if `A: PartialEq<B>` and `B: PartialEq<C>` and `A:
  61 ///   PartialEq<C>`, then **`a == b` and `b == c` implies `a == c`**.
  62 ///
  63 /// Note that the `B: PartialEq<A>` (symmetric) and `A: PartialEq<C>`
  64 /// (transitive) impls are not forced to exist, but these requirements apply
  65 /// whenever they do exist.
  66 ///
  67 /// ## Derivable
  68 ///
  69 /// This trait can be used with `#[derive]`. When `derive`d on structs, two
  70 /// instances are equal if all fields are equal, and not equal if any fields
  71 /// are not equal. When `derive`d on enums, two instances are equal if they
  72 /// are the same variant and all fields are equal.
  73 ///
  74 /// ## How can I implement `PartialEq`?
  75 ///
  76 /// An example implementation for a domain in which two books are considered
  77 /// the same book if their ISBN matches, even if the formats differ:
  78 ///
  79 /// ```
  80 /// enum BookFormat {
  81 ///     Paperback,
  82 ///     Hardback,
  83 ///     Ebook,
  84 /// }
  85 ///
  86 /// struct Book {
  87 ///     isbn: i32,
  88 ///     format: BookFormat,
  89 /// }
  90 ///
  91 /// impl PartialEq for Book {
  92 ///     fn eq(&self, other: &Self) -> bool {
  93 ///         self.isbn == other.isbn
  94 ///     }
  95 /// }
  96 ///
  97 /// let b1 = Book { isbn: 3, format: BookFormat::Paperback };
  98 /// let b2 = Book { isbn: 3, format: BookFormat::Ebook };
  99 /// let b3 = Book { isbn: 10, format: BookFormat::Paperback };
 100 ///
 101 /// assert!(b1 == b2);
 102 /// assert!(b1 != b3);
 103 /// ```
 104 ///
 105 /// ## How can I compare two different types?
 106 ///
 107 /// The type you can compare with is controlled by `PartialEq`'s type parameter.
 108 /// For example, let's tweak our previous code a bit:
 109 ///
 110 /// ```
 111 /// // The derive implements <BookFormat> == <BookFormat> comparisons
 112 /// #[derive(PartialEq)]
 113 /// enum BookFormat {
 114 ///     Paperback,
 115 ///     Hardback,
 116 ///     Ebook,
 117 /// }
 118 ///
 119 /// struct Book {
 120 ///     isbn: i32,
 121 ///     format: BookFormat,
 122 /// }
 123 ///
 124 /// // Implement <Book> == <BookFormat> comparisons
 125 /// impl PartialEq<BookFormat> for Book {
 126 ///     fn eq(&self, other: &BookFormat) -> bool {
 127 ///         self.format == *other
 128 ///     }
 129 /// }
 130 ///
 131 /// // Implement <BookFormat> == <Book> comparisons
 132 /// impl PartialEq<Book> for BookFormat {
 133 ///     fn eq(&self, other: &Book) -> bool {
 134 ///         *self == other.format
 135 ///     }
 136 /// }
 137 ///
 138 /// let b1 = Book { isbn: 3, format: BookFormat::Paperback };
 139 ///
 140 /// assert!(b1 == BookFormat::Paperback);
 141 /// assert!(BookFormat::Ebook != b1);
 142 /// ```
 143 ///
 144 /// By changing `impl PartialEq for Book` to `impl PartialEq<BookFormat> for Book`,
 145 /// we allow `BookFormat`s to be compared with `Book`s.
 146 ///
 147 /// A comparison like the one above, which ignores some fields of the struct,
 148 /// can be dangerous. It can easily lead to an unintended violation of the
 149 /// requirements for a partial equivalence relation. For example, if we kept
 150 /// the above implementation of `PartialEq<Book>` for `BookFormat` and added an
 151 /// implementation of `PartialEq<Book>` for `Book` (either via a `#[derive]` or
 152 /// via the manual implementation from the first example) then the result would
 153 /// violate transitivity:
 154 ///
 155 /// ```should_panic
 156 /// #[derive(PartialEq)]
 157 /// enum BookFormat {
 158 ///     Paperback,
 159 ///     Hardback,
 160 ///     Ebook,
 161 /// }
 162 ///
 163 /// #[derive(PartialEq)]
 164 /// struct Book {
 165 ///     isbn: i32,
 166 ///     format: BookFormat,
 167 /// }
 168 ///
 169 /// impl PartialEq<BookFormat> for Book {
 170 ///     fn eq(&self, other: &BookFormat) -> bool {
 171 ///         self.format == *other
 172 ///     }
 173 /// }
 174 ///
 175 /// impl PartialEq<Book> for BookFormat {
 176 ///     fn eq(&self, other: &Book) -> bool {
 177 ///         *self == other.format
 178 ///     }
 179 /// }
 180 ///
 181 /// fn main() {
 182 ///     let b1 = Book { isbn: 1, format: BookFormat::Paperback };
 183 ///     let b2 = Book { isbn: 2, format: BookFormat::Paperback };
 184 ///
 185 ///     assert!(b1 == BookFormat::Paperback);
 186 ///     assert!(BookFormat::Paperback == b2);
 187 ///
 188 ///     // The following should hold by transitivity but doesn't.
 189 ///     assert!(b1 == b2); // <-- PANICS
 190 /// }
 191 /// ```
 192 ///
 193 /// # Examples
 194 ///
 195 /// ```
 196 /// let x: u32 = 0;
 197 /// let y: u32 = 1;
 198 ///
 199 /// assert_eq!(x == y, false);
 200 /// assert_eq!(x.eq(&y), false);
 201 /// ```
 202 ///
 203 /// [`eq`]: PartialEq::eq
 204 /// [`ne`]: PartialEq::ne
 205 #[lang = "eq"]
 206 #[stable(feature = "rust1", since = "1.0.0")]
 207 #[doc(alias = "==")]
 208 #[doc(alias = "!=")]
 209 #[rustc_on_unimplemented(
 210     message = "can't compare `{Self}` with `{Rhs}`",
 211     label = "no implementation for `{Self} == {Rhs}`",
 212     append_const_msg
 213 )]
 214 #[const_trait]
 215 #[rustc_diagnostic_item = "PartialEq"]
 216 pub trait PartialEq<Rhs: ?Sized = Self> {
 217     /// This method tests for `self` and `other` values to be equal, and is used
 218     /// by `==`.
 219     #[must_use]
 220     #[stable(feature = "rust1", since = "1.0.0")]
 221     fn eq(&self, other: &Rhs) -> bool;
 222
 223     /// This method tests for `!=`. The default implementation is almost always
 224     /// sufficient, and should not be overridden without very good reason.
 225     #[inline]
 226     #[must_use]
 227     #[stable(feature = "rust1", since = "1.0.0")]
 228     fn ne(&self, other: &Rhs) -> bool {
 229         !self.eq(other)
 230     }
 231 }
 232
 233 /// Derive macro generating an impl of the trait `PartialEq`.
 234 #[rustc_builtin_macro]
 235 #[stable(feature = "builtin_macro_prelude", since = "1.38.0")]
 236 #[allow_internal_unstable(core_intrinsics, structural_match)]
 237 pub macro PartialEq($item:item) {
 238     /* compiler built-in */
 239 }
 240
 241 /// Trait for equality comparisons which are [equivalence relations](
 242 /// https://en.wikipedia.org/wiki/Equivalence_relation).
 243 ///
 244 /// This means, that in addition to `a == b` and `a != b` being strict inverses, the equality must
 245 /// be (for all `a`, `b` and `c`):
 246 ///
 247 /// - reflexive: `a == a`;
 248 /// - symmetric: `a == b` implies `b == a`; and
 249 /// - transitive: `a == b` and `b == c` implies `a == c`.
 250 ///
 251 /// This property cannot be checked by the compiler, and therefore `Eq` implies
 252 /// [`PartialEq`], and has no extra methods.
 253 ///
 254 /// ## Derivable
 255 ///
 256 /// This trait can be used with `#[derive]`. When `derive`d, because `Eq` has
 257 /// no extra methods, it is only informing the compiler that this is an
 258 /// equivalence relation rather than a partial equivalence relation. Note that
 259 /// the `derive` strategy requires all fields are `Eq`, which isn't
 260 /// always desired.
 261 ///
 262 /// ## How can I implement `Eq`?
 263 ///
 264 /// If you cannot use the `derive` strategy, specify that your type implements
 265 /// `Eq`, which has no methods:
 266 ///
 267 /// ```
 268 /// enum BookFormat { Paperback, Hardback, Ebook }
 269 /// struct Book {
 270 ///     isbn: i32,
 271 ///     format: BookFormat,
 272 /// }
 273 /// impl PartialEq for Book {
 274 ///     fn eq(&self, other: &Self) -> bool {
 275 ///         self.isbn == other.isbn
 276 ///     }
 277 /// }
 278 /// impl Eq for Book {}
 279 /// ```
 280 #[doc(alias = "==")]
 281 #[doc(alias = "!=")]
 282 #[stable(feature = "rust1", since = "1.0.0")]
 283 #[rustc_diagnostic_item = "Eq"]
 284 pub trait Eq: PartialEq<Self> {
 285     // this method is used solely by #[deriving] to assert
 286     // that every component of a type implements #[deriving]
 287     // itself, the current deriving infrastructure means doing this
 288     // assertion without using a method on this trait is nearly
 289     // impossible.
 290     //
 291     // This should never be implemented by hand.
 292     #[doc(hidden)]
 293     #[no_coverage] // rust-lang/rust#84605
 294     #[inline]
 295     #[stable(feature = "rust1", since = "1.0.0")]
 296     fn assert_receiver_is_total_eq(&self) {}
 297 }
 298
 299 /// Derive macro generating an impl of the trait `Eq`.
 300 #[rustc_builtin_macro]
 301 #[stable(feature = "builtin_macro_prelude", since = "1.38.0")]
 302 #[allow_internal_unstable(core_intrinsics, derive_eq, structural_match, no_coverage)]
 303 pub macro Eq($item:item) {
 304     /* compiler built-in */
 305 }
 306
 307 // FIXME: this struct is used solely by #[derive] to
 308 // assert that every component of a type implements Eq.
 309 //
 310 // This struct should never appear in user code.
 311 #[doc(hidden)]
 312 #[allow(missing_debug_implementations)]
 313 #[unstable(feature = "derive_eq", reason = "deriving hack, should not be public", issue = "none")]
 314 pub struct AssertParamIsEq<T: Eq + ?Sized> {
 315     _field: crate::marker::PhantomData<T>,
 316 }
 317
 318 /// An `Ordering` is the result of a comparison between two values.
 319 ///
 320 /// # Examples
 321 ///
 322 /// ```
 323 /// use std::cmp::Ordering;
 324 ///
 325 /// let result = 1.cmp(&2);
 326 /// assert_eq!(Ordering::Less, result);
 327 ///
 328 /// let result = 1.cmp(&1);
 329 /// assert_eq!(Ordering::Equal, result);
 330 ///
 331 /// let result = 2.cmp(&1);
 332 /// assert_eq!(Ordering::Greater, result);
 333 /// ```
 334 #[derive(Clone, Copy, Eq, Debug, Hash)]
 335 #[cfg_attr(not(bootstrap), derive_const(PartialOrd, Ord, PartialEq))]
 336 #[stable(feature = "rust1", since = "1.0.0")]
 337 #[repr(i8)]
 338 pub enum Ordering {
 339     /// An ordering where a compared value is less than another.
 340     #[stable(feature = "rust1", since = "1.0.0")]
 341     Less = -1,
 342     /// An ordering where a compared value is equal to another.
 343     #[stable(feature = "rust1", since = "1.0.0")]
 344     Equal = 0,
 345     /// An ordering where a compared value is greater than another.
 346     #[stable(feature = "rust1", since = "1.0.0")]
 347     Greater = 1,
 348 }
 349
 350 impl Ordering {
 351     /// Returns `true` if the ordering is the `Equal` variant.
 352     ///
 353     /// # Examples
 354     ///
 355     /// ```
 356     /// use std::cmp::Ordering;
 357     ///
 358     /// assert_eq!(Ordering::Less.is_eq(), false);
 359     /// assert_eq!(Ordering::Equal.is_eq(), true);
 360     /// assert_eq!(Ordering::Greater.is_eq(), false);
 361     /// ```
 362     #[inline]
 363     #[must_use]
 364     #[rustc_const_stable(feature = "ordering_helpers", since = "1.53.0")]
 365     #[stable(feature = "ordering_helpers", since = "1.53.0")]
 366     pub const fn is_eq(self) -> bool {
 367         matches!(self, Equal)
 368     }
 369
 370     /// Returns `true` if the ordering is not the `Equal` variant.
 371     ///
 372     /// # Examples
 373     ///
 374     /// ```
 375     /// use std::cmp::Ordering;
 376     ///
 377     /// assert_eq!(Ordering::Less.is_ne(), true);
 378     /// assert_eq!(Ordering::Equal.is_ne(), false);
 379     /// assert_eq!(Ordering::Greater.is_ne(), true);
 380     /// ```
 381     #[inline]
 382     #[must_use]
 383     #[rustc_const_stable(feature = "ordering_helpers", since = "1.53.0")]
 384     #[stable(feature = "ordering_helpers", since = "1.53.0")]
 385     pub const fn is_ne(self) -> bool {
 386         !matches!(self, Equal)
 387     }
 388
 389     /// Returns `true` if the ordering is the `Less` variant.
 390     ///
 391     /// # Examples
 392     ///
 393     /// ```
 394     /// use std::cmp::Ordering;
 395     ///
 396     /// assert_eq!(Ordering::Less.is_lt(), true);
 397     /// assert_eq!(Ordering::Equal.is_lt(), false);
 398     /// assert_eq!(Ordering::Greater.is_lt(), false);
 399     /// ```
 400     #[inline]
 401     #[must_use]
 402     #[rustc_const_stable(feature = "ordering_helpers", since = "1.53.0")]
 403     #[stable(feature = "ordering_helpers", since = "1.53.0")]
 404     pub const fn is_lt(self) -> bool {
 405         matches!(self, Less)
 406     }
 407
 408     /// Returns `true` if the ordering is the `Greater` variant.
 409     ///
 410     /// # Examples
 411     ///
 412     /// ```
 413     /// use std::cmp::Ordering;
 414     ///
 415     /// assert_eq!(Ordering::Less.is_gt(), false);
 416     /// assert_eq!(Ordering::Equal.is_gt(), false);
 417     /// assert_eq!(Ordering::Greater.is_gt(), true);
 418     /// ```
 419     #[inline]
 420     #[must_use]
 421     #[rustc_const_stable(feature = "ordering_helpers", since = "1.53.0")]
 422     #[stable(feature = "ordering_helpers", since = "1.53.0")]
 423     pub const fn is_gt(self) -> bool {
 424         matches!(self, Greater)
 425     }
 426
 427     /// Returns `true` if the ordering is either the `Less` or `Equal` variant.
 428     ///
 429     /// # Examples
 430     ///
 431     /// ```
 432     /// use std::cmp::Ordering;
 433     ///
 434     /// assert_eq!(Ordering::Less.is_le(), true);
 435     /// assert_eq!(Ordering::Equal.is_le(), true);
 436     /// assert_eq!(Ordering::Greater.is_le(), false);
 437     /// ```
 438     #[inline]
 439     #[must_use]
 440     #[rustc_const_stable(feature = "ordering_helpers", since = "1.53.0")]
 441     #[stable(feature = "ordering_helpers", since = "1.53.0")]
 442     pub const fn is_le(self) -> bool {
 443         !matches!(self, Greater)
 444     }
 445
 446     /// Returns `true` if the ordering is either the `Greater` or `Equal` variant.
 447     ///
 448     /// # Examples
 449     ///
 450     /// ```
 451     /// use std::cmp::Ordering;
 452     ///
 453     /// assert_eq!(Ordering::Less.is_ge(), false);
 454     /// assert_eq!(Ordering::Equal.is_ge(), true);
 455     /// assert_eq!(Ordering::Greater.is_ge(), true);
 456     /// ```
 457     #[inline]
 458     #[must_use]
 459     #[rustc_const_stable(feature = "ordering_helpers", since = "1.53.0")]
 460     #[stable(feature = "ordering_helpers", since = "1.53.0")]
 461     pub const fn is_ge(self) -> bool {
 462         !matches!(self, Less)
 463     }
 464
 465     /// Reverses the `Ordering`.
 466     ///
 467     /// * `Less` becomes `Greater`.
 468     /// * `Greater` becomes `Less`.
 469     /// * `Equal` becomes `Equal`.
 470     ///
 471     /// # Examples
 472     ///
 473     /// Basic behavior:
 474     ///
 475     /// ```
 476     /// use std::cmp::Ordering;
 477     ///
 478     /// assert_eq!(Ordering::Less.reverse(), Ordering::Greater);
 479     /// assert_eq!(Ordering::Equal.reverse(), Ordering::Equal);
 480     /// assert_eq!(Ordering::Greater.reverse(), Ordering::Less);
 481     /// ```
 482     ///
 483     /// This method can be used to reverse a comparison:
 484     ///
 485     /// ```
 486     /// let data: &mut [_] = &mut [2, 10, 5, 8];
 487     ///
 488     /// // sort the array from largest to smallest.
 489     /// data.sort_by(|a, b| a.cmp(b).reverse());
 490     ///
 491     /// let b: &mut [_] = &mut [10, 8, 5, 2];
 492     /// assert!(data == b);
 493     /// ```
 494     #[inline]
 495     #[must_use]
 496     #[rustc_const_stable(feature = "const_ordering", since = "1.48.0")]
 497     #[stable(feature = "rust1", since = "1.0.0")]
 498     pub const fn reverse(self) -> Ordering {
 499         match self {
 500             Less => Greater,
 501             Equal => Equal,
 502             Greater => Less,
 503         }
 504     }
 505
 506     /// Chains two orderings.
 507     ///
 508     /// Returns `self` when it's not `Equal`. Otherwise returns `other`.
 509     ///
 510     /// # Examples
 511     ///
 512     /// ```
 513     /// use std::cmp::Ordering;
 514     ///
 515     /// let result = Ordering::Equal.then(Ordering::Less);
 516     /// assert_eq!(result, Ordering::Less);
 517     ///
 518     /// let result = Ordering::Less.then(Ordering::Equal);
 519     /// assert_eq!(result, Ordering::Less);
 520     ///
 521     /// let result = Ordering::Less.then(Ordering::Greater);
 522     /// assert_eq!(result, Ordering::Less);
 523     ///
 524     /// let result = Ordering::Equal.then(Ordering::Equal);
 525     /// assert_eq!(result, Ordering::Equal);
 526     ///
 527     /// let x: (i64, i64, i64) = (1, 2, 7);
 528     /// let y: (i64, i64, i64) = (1, 5, 3);
 529     /// let result = x.0.cmp(&y.0).then(x.1.cmp(&y.1)).then(x.2.cmp(&y.2));
 530     ///
 531     /// assert_eq!(result, Ordering::Less);
 532     /// ```
 533     #[inline]
 534     #[must_use]
 535     #[rustc_const_stable(feature = "const_ordering", since = "1.48.0")]
 536     #[stable(feature = "ordering_chaining", since = "1.17.0")]
 537     pub const fn then(self, other: Ordering) -> Ordering {
 538         match self {
 539             Equal => other,
 540             _ => self,
 541         }
 542     }
 543
 544     /// Chains the ordering with the given function.
 545     ///
 546     /// Returns `self` when it's not `Equal`. Otherwise calls `f` and returns
 547     /// the result.
 548     ///
 549     /// # Examples
 550     ///
 551     /// ```
 552     /// use std::cmp::Ordering;
 553     ///
 554     /// let result = Ordering::Equal.then_with(|| Ordering::Less);
 555     /// assert_eq!(result, Ordering::Less);
 556     ///
 557     /// let result = Ordering::Less.then_with(|| Ordering::Equal);
 558     /// assert_eq!(result, Ordering::Less);
 559     ///
 560     /// let result = Ordering::Less.then_with(|| Ordering::Greater);
 561     /// assert_eq!(result, Ordering::Less);
 562     ///
 563     /// let result = Ordering::Equal.then_with(|| Ordering::Equal);
 564     /// assert_eq!(result, Ordering::Equal);
 565     ///
 566     /// let x: (i64, i64, i64) = (1, 2, 7);
 567     /// let y: (i64, i64, i64) = (1, 5, 3);
 568     /// let result = x.0.cmp(&y.0).then_with(|| x.1.cmp(&y.1)).then_with(|| x.2.cmp(&y.2));
 569     ///
 570     /// assert_eq!(result, Ordering::Less);
 571     /// ```
 572     #[inline]
 573     #[must_use]
 574     #[stable(feature = "ordering_chaining", since = "1.17.0")]
 575     pub fn then_with<F: FnOnce() -> Ordering>(self, f: F) -> Ordering {
 576         match self {
 577             Equal => f(),
 578             _ => self,
 579         }
 580     }
 581 }
 582
 583 /// A helper struct for reverse ordering.
 584 ///
 585 /// This struct is a helper to be used with functions like [`Vec::sort_by_key`] and
 586 /// can be used to reverse order a part of a key.
 587 ///
 588 /// [`Vec::sort_by_key`]: ../../std/vec/struct.Vec.html#method.sort_by_key
 589 ///
 590 /// # Examples
 591 ///
 592 /// ```
 593 /// use std::cmp::Reverse;
 594 ///
 595 /// let mut v = vec![1, 2, 3, 4, 5, 6];
 596 /// v.sort_by_key(|&num| (num > 3, Reverse(num)));
 597 /// assert_eq!(v, vec![3, 2, 1, 6, 5, 4]);
 598 /// ```
 599 #[derive(PartialEq, Eq, Debug, Copy, Default, Hash)]
 600 #[stable(feature = "reverse_cmp_key", since = "1.19.0")]
 601 #[repr(transparent)]
 602 pub struct Reverse<T>(#[stable(feature = "reverse_cmp_key", since = "1.19.0")] pub T);
 603
 604 #[stable(feature = "reverse_cmp_key", since = "1.19.0")]
 605 #[rustc_const_unstable(feature = "const_cmp", issue = "92391")]
 606 impl<T: ~const PartialOrd> const PartialOrd for Reverse<T> {
 607     #[inline]
 608     fn partial_cmp(&self, other: &Reverse<T>) -> Option<Ordering> {
 609         other.0.partial_cmp(&self.0)
 610     }
 611
 612     #[inline]
 613     fn lt(&self, other: &Self) -> bool {
 614         other.0 < self.0
 615     }
 616     #[inline]
 617     fn le(&self, other: &Self) -> bool {
 618         other.0 <= self.0
 619     }
 620     #[inline]
 621     fn gt(&self, other: &Self) -> bool {
 622         other.0 > self.0
 623     }
 624     #[inline]
 625     fn ge(&self, other: &Self) -> bool {
 626         other.0 >= self.0
 627     }
 628 }
 629
 630 #[stable(feature = "reverse_cmp_key", since = "1.19.0")]
 631 impl<T: Ord> Ord for Reverse<T> {
 632     #[inline]
 633     fn cmp(&self, other: &Reverse<T>) -> Ordering {
 634         other.0.cmp(&self.0)
 635     }
 636 }
 637
 638 #[stable(feature = "reverse_cmp_key", since = "1.19.0")]
 639 impl<T: Clone> Clone for Reverse<T> {
 640     #[inline]
 641     fn clone(&self) -> Reverse<T> {
 642         Reverse(self.0.clone())
 643     }
 644
 645     #[inline]
 646     fn clone_from(&mut self, other: &Self) {
 647         self.0.clone_from(&other.0)
 648     }
 649 }
 650
 651 /// Trait for types that form a [total order](https://en.wikipedia.org/wiki/Total_order).
 652 ///
 653 /// Implementations must be consistent with the [`PartialOrd`] implementation, and ensure
 654 /// `max`, `min`, and `clamp` are consistent with `cmp`:
 655 ///
 656 /// - `partial_cmp(a, b) == Some(cmp(a, b))`.
 657 /// - `max(a, b) == max_by(a, b, cmp)` (ensured by the default implementation).
 658 /// - `min(a, b) == min_by(a, b, cmp)` (ensured by the default implementation).
 659 /// - For `a.clamp(min, max)`, see the [method docs](#method.clamp)
 660 ///   (ensured by the default implementation).
 661 ///
 662 /// It's easy to accidentally make `cmp` and `partial_cmp` disagree by
 663 /// deriving some of the traits and manually implementing others.
 664 ///
 665 /// ## Corollaries
 666 ///
 667 /// From the above and the requirements of `PartialOrd`, it follows that `<` defines a strict total order.
 668 /// This means that for all `a`, `b` and `c`:
 669 ///
 670 /// - exactly one of `a < b`, `a == b` or `a > b` is true; and
 671 /// - `<` is transitive: `a < b` and `b < c` implies `a < c`. The same must hold for both `==` and `>`.
 672 ///
 673 /// ## Derivable
 674 ///
 675 /// This trait can be used with `#[derive]`.
 676 ///
 677 /// When `derive`d on structs, it will produce a
 678 /// [lexicographic](https://en.wikipedia.org/wiki/Lexicographic_order) ordering
 679 /// based on the top-to-bottom declaration order of the struct's members.
 680 ///
 681 /// When `derive`d on enums, variants are ordered by their discriminants.
 682 /// By default, the discriminant is smallest for variants at the top, and
 683 /// largest for variants at the bottom. Here's an example:
 684 ///
 685 /// ```
 686 /// #[derive(PartialEq, Eq, PartialOrd, Ord)]
 687 /// enum E {
 688 ///     Top,
 689 ///     Bottom,
 690 /// }
 691 ///
 692 /// assert!(E::Top < E::Bottom);
 693 /// ```
 694 ///
 695 /// However, manually setting the discriminants can override this default
 696 /// behavior:
 697 ///
 698 /// ```
 699 /// #[derive(PartialEq, Eq, PartialOrd, Ord)]
 700 /// enum E {
 701 ///     Top = 2,
 702 ///     Bottom = 1,
 703 /// }
 704 ///
 705 /// assert!(E::Bottom < E::Top);
 706 /// ```
 707 ///
 708 /// ## Lexicographical comparison
 709 ///
 710 /// Lexicographical comparison is an operation with the following properties:
 711 ///  - Two sequences are compared element by element.
 712 ///  - The first mismatching element defines which sequence is lexicographically less or greater than the other.
 713 ///  - If one sequence is a prefix of another, the shorter sequence is lexicographically less than the other.
 714 ///  - If two sequence have equivalent elements and are of the same length, then the sequences are lexicographically equal.
 715 ///  - An empty sequence is lexicographically less than any non-empty sequence.
 716 ///  - Two empty sequences are lexicographically equal.
 717 ///
 718 /// ## How can I implement `Ord`?
 719 ///
 720 /// `Ord` requires that the type also be [`PartialOrd`] and [`Eq`] (which requires [`PartialEq`]).
 721 ///
 722 /// Then you must define an implementation for [`cmp`]. You may find it useful to use
 723 /// [`cmp`] on your type's fields.
 724 ///
 725 /// Here's an example where you want to sort people by height only, disregarding `id`
 726 /// and `name`:
 727 ///
 728 /// ```
 729 /// use std::cmp::Ordering;
 730 ///
 731 /// #[derive(Eq)]
 732 /// struct Person {
 733 ///     id: u32,
 734 ///     name: String,
 735 ///     height: u32,
 736 /// }
 737 ///
 738 /// impl Ord for Person {
 739 ///     fn cmp(&self, other: &Self) -> Ordering {
 740 ///         self.height.cmp(&other.height)
 741 ///     }
 742 /// }
 743 ///
 744 /// impl PartialOrd for Person {
 745 ///     fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
 746 ///         Some(self.cmp(other))
 747 ///     }
 748 /// }
 749 ///
 750 /// impl PartialEq for Person {
 751 ///     fn eq(&self, other: &Self) -> bool {
 752 ///         self.height == other.height
 753 ///     }
 754 /// }
 755 /// ```
 756 ///
 757 /// [`cmp`]: Ord::cmp
 758 #[doc(alias = "<")]
 759 #[doc(alias = ">")]
 760 #[doc(alias = "<=")]
 761 #[doc(alias = ">=")]
 762 #[stable(feature = "rust1", since = "1.0.0")]
 763 #[rustc_diagnostic_item = "Ord"]
 764 #[const_trait]
 765 pub trait Ord: Eq + PartialOrd<Self> {
 766     /// This method returns an [`Ordering`] between `self` and `other`.
 767     ///
 768     /// By convention, `self.cmp(&other)` returns the ordering matching the expression
 769     /// `self <operator> other` if true.
 770     ///
 771     /// # Examples
 772     ///
 773     /// ```
 774     /// use std::cmp::Ordering;
 775     ///
 776     /// assert_eq!(5.cmp(&10), Ordering::Less);
 777     /// assert_eq!(10.cmp(&5), Ordering::Greater);
 778     /// assert_eq!(5.cmp(&5), Ordering::Equal);
 779     /// ```
 780     #[must_use]
 781     #[stable(feature = "rust1", since = "1.0.0")]
 782     fn cmp(&self, other: &Self) -> Ordering;
 783
 784     /// Compares and returns the maximum of two values.
 785     ///
 786     /// Returns the second argument if the comparison determines them to be equal.
 787     ///
 788     /// # Examples
 789     ///
 790     /// ```
 791     /// assert_eq!(2, 1.max(2));
 792     /// assert_eq!(2, 2.max(2));
 793     /// ```
 794     #[stable(feature = "ord_max_min", since = "1.21.0")]
 795     #[inline]
 796     #[must_use]
 797     fn max(self, other: Self) -> Self
 798     where
 799         Self: Sized,
 800         Self: ~const Destruct,
 801     {
 802         // HACK(fee1-dead): go back to using `self.max_by(other, Ord::cmp)`
 803         // when trait methods are allowed to be used when a const closure is
 804         // expected.
 805         match self.cmp(&other) {
 806             Ordering::Less | Ordering::Equal => other,
 807             Ordering::Greater => self,
 808         }
 809     }
 810
 811     /// Compares and returns the minimum of two values.
 812     ///
 813     /// Returns the first argument if the comparison determines them to be equal.
 814     ///
 815     /// # Examples
 816     ///
 817     /// ```
 818     /// assert_eq!(1, 1.min(2));
 819     /// assert_eq!(2, 2.min(2));
 820     /// ```
 821     #[stable(feature = "ord_max_min", since = "1.21.0")]
 822     #[inline]
 823     #[must_use]
 824     fn min(self, other: Self) -> Self
 825     where
 826         Self: Sized,
 827         Self: ~const Destruct,
 828     {
 829         // HACK(fee1-dead): go back to using `self.min_by(other, Ord::cmp)`
 830         // when trait methods are allowed to be used when a const closure is
 831         // expected.
 832         match self.cmp(&other) {
 833             Ordering::Less | Ordering::Equal => self,
 834             Ordering::Greater => other,
 835         }
 836     }
 837
 838     /// Restrict a value to a certain interval.
 839     ///
 840     /// Returns `max` if `self` is greater than `max`, and `min` if `self` is
 841     /// less than `min`. Otherwise this returns `self`.
 842     ///
 843     /// # Panics
 844     ///
 845     /// Panics if `min > max`.
 846     ///
 847     /// # Examples
 848     ///
 849     /// ```
 850     /// assert!((-3).clamp(-2, 1) == -2);
 851     /// assert!(0.clamp(-2, 1) == 0);
 852     /// assert!(2.clamp(-2, 1) == 1);
 853     /// ```
 854     #[must_use]
 855     #[stable(feature = "clamp", since = "1.50.0")]
 856     fn clamp(self, min: Self, max: Self) -> Self
 857     where
 858         Self: Sized,
 859         Self: ~const Destruct,
 860         Self: ~const PartialOrd,
 861     {
 862         assert!(min <= max);
 863         if self < min {
 864             min
 865         } else if self > max {
 866             max
 867         } else {
 868             self
 869         }
 870     }
 871 }
 872
 873 /// Derive macro generating an impl of the trait `Ord`.
 874 #[rustc_builtin_macro]
 875 #[stable(feature = "builtin_macro_prelude", since = "1.38.0")]
 876 #[allow_internal_unstable(core_intrinsics)]
 877 pub macro Ord($item:item) {
 878     /* compiler built-in */
 879 }
 880
 881 #[stable(feature = "rust1", since = "1.0.0")]
 882 #[cfg(bootstrap)]
 883 impl StructuralPartialEq for Ordering {}
 884
 885 #[stable(feature = "rust1", since = "1.0.0")]
 886 #[rustc_const_unstable(feature = "const_cmp", issue = "92391")]
 887 #[cfg(bootstrap)]
 888 impl const PartialEq for Ordering {
 889     #[inline]
 890     fn eq(&self, other: &Self) -> bool {
 891         (*self as i32).eq(&(*other as i32))
 892     }
 893 }
 894
 895 #[stable(feature = "rust1", since = "1.0.0")]
 896 #[rustc_const_unstable(feature = "const_cmp", issue = "92391")]
 897 #[cfg(bootstrap)]
 898 impl const Ord for Ordering {
 899     #[inline]
 900     fn cmp(&self, other: &Ordering) -> Ordering {
 901         (*self as i32).cmp(&(*other as i32))
 902     }
 903 }
 904
 905 #[stable(feature = "rust1", since = "1.0.0")]
 906 #[rustc_const_unstable(feature = "const_cmp", issue = "92391")]
 907 #[cfg(bootstrap)]
 908 impl const PartialOrd for Ordering {
 909     #[inline]
 910     fn partial_cmp(&self, other: &Ordering) -> Option<Ordering> {
 911         (*self as i32).partial_cmp(&(*other as i32))
 912     }
 913 }
 914
 915 /// Trait for types that form a [partial order](https://en.wikipedia.org/wiki/Partial_order).
 916 ///
 917 /// The `lt`, `le`, `gt`, and `ge` methods of this trait can be called using
 918 /// the `<`, `<=`, `>`, and `>=` operators, respectively.
 919 ///
 920 /// The methods of this trait must be consistent with each other and with those of [`PartialEq`].
 921 /// The following conditions must hold:
 922 ///
 923 /// 1. `a == b` if and only if `partial_cmp(a, b) == Some(Equal)`.
 924 /// 2. `a < b` if and only if `partial_cmp(a, b) == Some(Less)`
 925 /// 3. `a > b` if and only if `partial_cmp(a, b) == Some(Greater)`
 926 /// 4. `a <= b` if and only if `a < b || a == b`
 927 /// 5. `a >= b` if and only if `a > b || a == b`
 928 /// 6. `a != b` if and only if `!(a == b)`.
 929 ///
 930 /// Conditions 2–5 above are ensured by the default implementation.
 931 /// Condition 6 is already ensured by [`PartialEq`].
 932 ///
 933 /// If [`Ord`] is also implemented for `Self` and `Rhs`, it must also be consistent with
 934 /// `partial_cmp` (see the documentation of that trait for the exact requirements). It's
 935 /// easy to accidentally make them disagree by deriving some of the traits and manually
 936 /// implementing others.
 937 ///
 938 /// The comparison must satisfy, for all `a`, `b` and `c`:
 939 ///
 940 /// - transitivity: `a < b` and `b < c` implies `a < c`. The same must hold for both `==` and `>`.
 941 /// - duality: `a < b` if and only if `b > a`.
 942 ///
 943 /// Note that these requirements mean that the trait itself must be implemented symmetrically and
 944 /// transitively: if `T: PartialOrd<U>` and `U: PartialOrd<V>` then `U: PartialOrd<T>` and `T:
 945 /// PartialOrd<V>`.
 946 ///
 947 /// ## Corollaries
 948 ///
 949 /// The following corollaries follow from the above requirements:
 950 ///
 951 /// - irreflexivity of `<` and `>`: `!(a < a)`, `!(a > a)`
 952 /// - transitivity of `>`: if `a > b` and `b > c` then `a > c`
 953 /// - duality of `partial_cmp`: `partial_cmp(a, b) == partial_cmp(b, a).map(Ordering::reverse)`
 954 ///
 955 /// ## Derivable
 956 ///
 957 /// This trait can be used with `#[derive]`.
 958 ///
 959 /// When `derive`d on structs, it will produce a
 960 /// [lexicographic](https://en.wikipedia.org/wiki/Lexicographic_order) ordering
 961 /// based on the top-to-bottom declaration order of the struct's members.
 962 ///
 963 /// When `derive`d on enums, variants are ordered by their discriminants.
 964 /// By default, the discriminant is smallest for variants at the top, and
 965 /// largest for variants at the bottom. Here's an example:
 966 ///
 967 /// ```
 968 /// #[derive(PartialEq, PartialOrd)]
 969 /// enum E {
 970 ///     Top,
 971 ///     Bottom,
 972 /// }
 973 ///
 974 /// assert!(E::Top < E::Bottom);
 975 /// ```
 976 ///
 977 /// However, manually setting the discriminants can override this default
 978 /// behavior:
 979 ///
 980 /// ```
 981 /// #[derive(PartialEq, PartialOrd)]
 982 /// enum E {
 983 ///     Top = 2,
 984 ///     Bottom = 1,
 985 /// }
 986 ///
 987 /// assert!(E::Bottom < E::Top);
 988 /// ```
 989 ///
 990 /// ## How can I implement `PartialOrd`?
 991 ///
 992 /// `PartialOrd` only requires implementation of the [`partial_cmp`] method, with the others
 993 /// generated from default implementations.
 994 ///
 995 /// However it remains possible to implement the others separately for types which do not have a
 996 /// total order. For example, for floating point numbers, `NaN < 0 == false` and `NaN >= 0 ==
 997 /// false` (cf. IEEE 754-2008 section 5.11).
 998 ///
 999 /// `PartialOrd` requires your type to be [`PartialEq`].
1000 ///
1001 /// If your type is [`Ord`], you can implement [`partial_cmp`] by using [`cmp`]:
1002 ///
1003 /// ```
1004 /// use std::cmp::Ordering;
1005 ///
1006 /// #[derive(Eq)]
1007 /// struct Person {
1008 ///     id: u32,
1009 ///     name: String,
1010 ///     height: u32,
1011 /// }
1012 ///
1013 /// impl PartialOrd for Person {
1014 ///     fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
1015 ///         Some(self.cmp(other))
1016 ///     }
1017 /// }
1018 ///
1019 /// impl Ord for Person {
1020 ///     fn cmp(&self, other: &Self) -> Ordering {
1021 ///         self.height.cmp(&other.height)
1022 ///     }
1023 /// }
1024 ///
1025 /// impl PartialEq for Person {
1026 ///     fn eq(&self, other: &Self) -> bool {
1027 ///         self.height == other.height
1028 ///     }
1029 /// }
1030 /// ```
1031 ///
1032 /// You may also find it useful to use [`partial_cmp`] on your type's fields. Here
1033 /// is an example of `Person` types who have a floating-point `height` field that
1034 /// is the only field to be used for sorting:
1035 ///
1036 /// ```
1037 /// use std::cmp::Ordering;
1038 ///
1039 /// struct Person {
1040 ///     id: u32,
1041 ///     name: String,
1042 ///     height: f64,
1043 /// }
1044 ///
1045 /// impl PartialOrd for Person {
1046 ///     fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
1047 ///         self.height.partial_cmp(&other.height)
1048 ///     }
1049 /// }
1050 ///
1051 /// impl PartialEq for Person {
1052 ///     fn eq(&self, other: &Self) -> bool {
1053 ///         self.height == other.height
1054 ///     }
1055 /// }
1056 /// ```
1057 ///
1058 /// # Examples
1059 ///
1060 /// ```
1061 /// let x: u32 = 0;
1062 /// let y: u32 = 1;
1063 ///
1064 /// assert_eq!(x < y, true);
1065 /// assert_eq!(x.lt(&y), true);
1066 /// ```
1067 ///
1068 /// [`partial_cmp`]: PartialOrd::partial_cmp
1069 /// [`cmp`]: Ord::cmp
1070 #[lang = "partial_ord"]
1071 #[stable(feature = "rust1", since = "1.0.0")]
1072 #[doc(alias = ">")]
1073 #[doc(alias = "<")]
1074 #[doc(alias = "<=")]
1075 #[doc(alias = ">=")]
1076 #[rustc_on_unimplemented(
1077     message = "can't compare `{Self}` with `{Rhs}`",
1078     label = "no implementation for `{Self} < {Rhs}` and `{Self} > {Rhs}`",
1079     append_const_msg
1080 )]
1081 #[const_trait]
1082 #[rustc_diagnostic_item = "PartialOrd"]
1083 pub trait PartialOrd<Rhs: ?Sized = Self>: PartialEq<Rhs> {
1084     /// This method returns an ordering between `self` and `other` values if one exists.
1085     ///
1086     /// # Examples
1087     ///
1088     /// ```
1089     /// use std::cmp::Ordering;
1090     ///
1091     /// let result = 1.0.partial_cmp(&2.0);
1092     /// assert_eq!(result, Some(Ordering::Less));
1093     ///
1094     /// let result = 1.0.partial_cmp(&1.0);
1095     /// assert_eq!(result, Some(Ordering::Equal));
1096     ///
1097     /// let result = 2.0.partial_cmp(&1.0);
1098     /// assert_eq!(result, Some(Ordering::Greater));
1099     /// ```
1100     ///
1101     /// When comparison is impossible:
1102     ///
1103     /// ```
1104     /// let result = f64::NAN.partial_cmp(&1.0);
1105     /// assert_eq!(result, None);
1106     /// ```
1107     #[must_use]
1108     #[stable(feature = "rust1", since = "1.0.0")]
1109     fn partial_cmp(&self, other: &Rhs) -> Option<Ordering>;
1110
1111     /// This method tests less than (for `self` and `other`) and is used by the `<` operator.
1112     ///
1113     /// # Examples
1114     ///
1115     /// ```
1116     /// let result = 1.0 < 2.0;
1117     /// assert_eq!(result, true);
1118     ///
1119     /// let result = 2.0 < 1.0;
1120     /// assert_eq!(result, false);
1121     /// ```
1122     #[inline]
1123     #[must_use]
1124     #[stable(feature = "rust1", since = "1.0.0")]
1125     fn lt(&self, other: &Rhs) -> bool {
1126         matches!(self.partial_cmp(other), Some(Less))
1127     }
1128
1129     /// This method tests less than or equal to (for `self` and `other`) and is used by the `<=`
1130     /// operator.
1131     ///
1132     /// # Examples
1133     ///
1134     /// ```
1135     /// let result = 1.0 <= 2.0;
1136     /// assert_eq!(result, true);
1137     ///
1138     /// let result = 2.0 <= 2.0;
1139     /// assert_eq!(result, true);
1140     /// ```
1141     #[inline]
1142     #[must_use]
1143     #[stable(feature = "rust1", since = "1.0.0")]
1144     fn le(&self, other: &Rhs) -> bool {
1145         matches!(self.partial_cmp(other), Some(Less | Equal))
1146     }
1147
1148     /// This method tests greater than (for `self` and `other`) and is used by the `>` operator.
1149     ///
1150     /// # Examples
1151     ///
1152     /// ```
1153     /// let result = 1.0 > 2.0;
1154     /// assert_eq!(result, false);
1155     ///
1156     /// let result = 2.0 > 2.0;
1157     /// assert_eq!(result, false);
1158     /// ```
1159     #[inline]
1160     #[must_use]
1161     #[stable(feature = "rust1", since = "1.0.0")]
1162     fn gt(&self, other: &Rhs) -> bool {
1163         matches!(self.partial_cmp(other), Some(Greater))
1164     }
1165
1166     /// This method tests greater than or equal to (for `self` and `other`) and is used by the `>=`
1167     /// operator.
1168     ///
1169     /// # Examples
1170     ///
1171     /// ```
1172     /// let result = 2.0 >= 1.0;
1173     /// assert_eq!(result, true);
1174     ///
1175     /// let result = 2.0 >= 2.0;
1176     /// assert_eq!(result, true);
1177     /// ```
1178     #[inline]
1179     #[must_use]
1180     #[stable(feature = "rust1", since = "1.0.0")]
1181     fn ge(&self, other: &Rhs) -> bool {
1182         matches!(self.partial_cmp(other), Some(Greater | Equal))
1183     }
1184 }
1185
1186 /// Derive macro generating an impl of the trait `PartialOrd`.
1187 #[rustc_builtin_macro]
1188 #[stable(feature = "builtin_macro_prelude", since = "1.38.0")]
1189 #[allow_internal_unstable(core_intrinsics)]
1190 pub macro PartialOrd($item:item) {
1191     /* compiler built-in */
1192 }
1193
1194 /// Compares and returns the minimum of two values.
1195 ///
1196 /// Returns the first argument if the comparison determines them to be equal.
1197 ///
1198 /// Internally uses an alias to [`Ord::min`].
1199 ///
1200 /// # Examples
1201 ///
1202 /// ```
1203 /// use std::cmp;
1204 ///
1205 /// assert_eq!(1, cmp::min(1, 2));
1206 /// assert_eq!(2, cmp::min(2, 2));
1207 /// ```
1208 #[inline]
1209 #[must_use]
1210 #[stable(feature = "rust1", since = "1.0.0")]
1211 #[rustc_const_unstable(feature = "const_cmp", issue = "92391")]
1212 #[cfg_attr(not(test), rustc_diagnostic_item = "cmp_min")]
1213 pub const fn min<T: ~const Ord + ~const Destruct>(v1: T, v2: T) -> T {
1214     v1.min(v2)
1215 }
1216
1217 /// Returns the minimum of two values with respect to the specified comparison function.
1218 ///
1219 /// Returns the first argument if the comparison determines them to be equal.
1220 ///
1221 /// # Examples
1222 ///
1223 /// ```
1224 /// use std::cmp;
1225 ///
1226 /// assert_eq!(cmp::min_by(-2, 1, |x: &i32, y: &i32| x.abs().cmp(&y.abs())), 1);
1227 /// assert_eq!(cmp::min_by(-2, 2, |x: &i32, y: &i32| x.abs().cmp(&y.abs())), -2);
1228 /// ```
1229 #[inline]
1230 #[must_use]
1231 #[stable(feature = "cmp_min_max_by", since = "1.53.0")]
1232 #[rustc_const_unstable(feature = "const_cmp", issue = "92391")]
1233 pub const fn min_by<T, F: ~const FnOnce(&T, &T) -> Ordering>(v1: T, v2: T, compare: F) -> T
1234 where
1235     T: ~const Destruct,
1236     F: ~const Destruct,
1237 {
1238     match compare(&v1, &v2) {
1239         Ordering::Less | Ordering::Equal => v1,
1240         Ordering::Greater => v2,
1241     }
1242 }
1243
1244 /// Returns the element that gives the minimum value from the specified function.
1245 ///
1246 /// Returns the first argument if the comparison determines them to be equal.
1247 ///
1248 /// # Examples
1249 ///
1250 /// ```
1251 /// use std::cmp;
1252 ///
1253 /// assert_eq!(cmp::min_by_key(-2, 1, |x: &i32| x.abs()), 1);
1254 /// assert_eq!(cmp::min_by_key(-2, 2, |x: &i32| x.abs()), -2);
1255 /// ```
1256 #[inline]
1257 #[must_use]
1258 #[stable(feature = "cmp_min_max_by", since = "1.53.0")]
1259 #[rustc_const_unstable(feature = "const_cmp", issue = "92391")]
1260 pub const fn min_by_key<T, F: ~const FnMut(&T) -> K, K: ~const Ord>(v1: T, v2: T, mut f: F) -> T
1261 where
1262     T: ~const Destruct,
1263     F: ~const Destruct,
1264     K: ~const Destruct,
1265 {
1266     const fn imp<T, F: ~const FnMut(&T) -> K, K: ~const Ord>(
1267         f: &mut F,
1268         (v1, v2): (&T, &T),
1269     ) -> Ordering
1270     where
1271         T: ~const Destruct,
1272         K: ~const Destruct,
1273     {
1274         f(v1).cmp(&f(v2))
1275     }
1276     min_by(v1, v2, ConstFnMutClosure::new(&mut f, imp))
1277 }
1278
1279 /// Compares and returns the maximum of two values.
1280 ///
1281 /// Returns the second argument if the comparison determines them to be equal.
1282 ///
1283 /// Internally uses an alias to [`Ord::max`].
1284 ///
1285 /// # Examples
1286 ///
1287 /// ```
1288 /// use std::cmp;
1289 ///
1290 /// assert_eq!(2, cmp::max(1, 2));
1291 /// assert_eq!(2, cmp::max(2, 2));
1292 /// ```
1293 #[inline]
1294 #[must_use]
1295 #[stable(feature = "rust1", since = "1.0.0")]
1296 #[rustc_const_unstable(feature = "const_cmp", issue = "92391")]
1297 #[cfg_attr(not(test), rustc_diagnostic_item = "cmp_max")]
1298 pub const fn max<T: ~const Ord + ~const Destruct>(v1: T, v2: T) -> T {
1299     v1.max(v2)
1300 }
1301
1302 /// Returns the maximum of two values with respect to the specified comparison function.
1303 ///
1304 /// Returns the second argument if the comparison determines them to be equal.
1305 ///
1306 /// # Examples
1307 ///
1308 /// ```
1309 /// use std::cmp;
1310 ///
1311 /// assert_eq!(cmp::max_by(-2, 1, |x: &i32, y: &i32| x.abs().cmp(&y.abs())), -2);
1312 /// assert_eq!(cmp::max_by(-2, 2, |x: &i32, y: &i32| x.abs().cmp(&y.abs())), 2);
1313 /// ```
1314 #[inline]
1315 #[must_use]
1316 #[stable(feature = "cmp_min_max_by", since = "1.53.0")]
1317 #[rustc_const_unstable(feature = "const_cmp", issue = "92391")]
1318 pub const fn max_by<T, F: ~const FnOnce(&T, &T) -> Ordering>(v1: T, v2: T, compare: F) -> T
1319 where
1320     T: ~const Destruct,
1321     F: ~const Destruct,
1322 {
1323     match compare(&v1, &v2) {
1324         Ordering::Less | Ordering::Equal => v2,
1325         Ordering::Greater => v1,
1326     }
1327 }
1328
1329 /// Returns the element that gives the maximum value from the specified function.
1330 ///
1331 /// Returns the second argument if the comparison determines them to be equal.
1332 ///
1333 /// # Examples
1334 ///
1335 /// ```
1336 /// use std::cmp;
1337 ///
1338 /// assert_eq!(cmp::max_by_key(-2, 1, |x: &i32| x.abs()), -2);
1339 /// assert_eq!(cmp::max_by_key(-2, 2, |x: &i32| x.abs()), 2);
1340 /// ```
1341 #[inline]
1342 #[must_use]
1343 #[stable(feature = "cmp_min_max_by", since = "1.53.0")]
1344 #[rustc_const_unstable(feature = "const_cmp", issue = "92391")]
1345 pub const fn max_by_key<T, F: ~const FnMut(&T) -> K, K: ~const Ord>(v1: T, v2: T, mut f: F) -> T
1346 where
1347     T: ~const Destruct,
1348     F: ~const Destruct,
1349     K: ~const Destruct,
1350 {
1351     const fn imp<T, F: ~const FnMut(&T) -> K, K: ~const Ord>(
1352         f: &mut F,
1353         (v1, v2): (&T, &T),
1354     ) -> Ordering
1355     where
1356         T: ~const Destruct,
1357         K: ~const Destruct,
1358     {
1359         f(v1).cmp(&f(v2))
1360     }
1361     max_by(v1, v2, ConstFnMutClosure::new(&mut f, imp))
1362 }
1363
1364 // Implementation of PartialEq, Eq, PartialOrd and Ord for primitive types
1365 mod impls {
1366     use crate::cmp::Ordering::{self, Equal, Greater, Less};
1367     use crate::hint::unreachable_unchecked;
1368
1369     macro_rules! partial_eq_impl {
1370         ($($t:ty)*) => ($(
1371             #[stable(feature = "rust1", since = "1.0.0")]
1372             #[rustc_const_unstable(feature = "const_cmp", issue = "92391")]
1373             impl const PartialEq for $t {
1374                 #[inline]
1375                 fn eq(&self, other: &$t) -> bool { (*self) == (*other) }
1376                 #[inline]
1377                 fn ne(&self, other: &$t) -> bool { (*self) != (*other) }
1378             }
1379         )*)
1380     }
1381
1382     #[stable(feature = "rust1", since = "1.0.0")]
1383     #[rustc_const_unstable(feature = "const_cmp", issue = "92391")]
1384     impl const PartialEq for () {
1385         #[inline]
1386         fn eq(&self, _other: &()) -> bool {
1387             true
1388         }
1389         #[inline]
1390         fn ne(&self, _other: &()) -> bool {
1391             false
1392         }
1393     }
1394
1395     partial_eq_impl! {
1396         bool char usize u8 u16 u32 u64 u128 isize i8 i16 i32 i64 i128 f32 f64
1397     }
1398
1399     macro_rules! eq_impl {
1400         ($($t:ty)*) => ($(
1401             #[stable(feature = "rust1", since = "1.0.0")]
1402             impl Eq for $t {}
1403         )*)
1404     }
1405
1406     eq_impl! { () bool char usize u8 u16 u32 u64 u128 isize i8 i16 i32 i64 i128 }
1407
1408     macro_rules! partial_ord_impl {
1409         ($($t:ty)*) => ($(
1410             #[stable(feature = "rust1", since = "1.0.0")]
1411             #[rustc_const_unstable(feature = "const_cmp", issue = "92391")]
1412             impl const PartialOrd for $t {
1413                 #[inline]
1414                 fn partial_cmp(&self, other: &$t) -> Option<Ordering> {
1415                     match (*self <= *other, *self >= *other) {
1416                         (false, false) => None,
1417                         (false, true) => Some(Greater),
1418                         (true, false) => Some(Less),
1419                         (true, true) => Some(Equal),
1420                     }
1421                 }
1422                 #[inline]
1423                 fn lt(&self, other: &$t) -> bool { (*self) < (*other) }
1424                 #[inline]
1425                 fn le(&self, other: &$t) -> bool { (*self) <= (*other) }
1426                 #[inline]
1427                 fn ge(&self, other: &$t) -> bool { (*self) >= (*other) }
1428                 #[inline]
1429                 fn gt(&self, other: &$t) -> bool { (*self) > (*other) }
1430             }
1431         )*)
1432     }
1433
1434     #[stable(feature = "rust1", since = "1.0.0")]
1435     #[rustc_const_unstable(feature = "const_cmp", issue = "92391")]
1436     impl const PartialOrd for () {
1437         #[inline]
1438         fn partial_cmp(&self, _: &()) -> Option<Ordering> {
1439             Some(Equal)
1440         }
1441     }
1442
1443     #[stable(feature = "rust1", since = "1.0.0")]
1444     #[rustc_const_unstable(feature = "const_cmp", issue = "92391")]
1445     impl const PartialOrd for bool {
1446         #[inline]
1447         fn partial_cmp(&self, other: &bool) -> Option<Ordering> {
1448             Some(self.cmp(other))
1449         }
1450     }
1451
1452     partial_ord_impl! { f32 f64 }
1453
1454     macro_rules! ord_impl {
1455         ($($t:ty)*) => ($(
1456             #[stable(feature = "rust1", since = "1.0.0")]
1457             #[rustc_const_unstable(feature = "const_cmp", issue = "92391")]
1458             impl const PartialOrd for $t {
1459                 #[inline]
1460                 fn partial_cmp(&self, other: &$t) -> Option<Ordering> {
1461                     Some(self.cmp(other))
1462                 }
1463                 #[inline]
1464                 fn lt(&self, other: &$t) -> bool { (*self) < (*other) }
1465                 #[inline]
1466                 fn le(&self, other: &$t) -> bool { (*self) <= (*other) }
1467                 #[inline]
1468                 fn ge(&self, other: &$t) -> bool { (*self) >= (*other) }
1469                 #[inline]
1470                 fn gt(&self, other: &$t) -> bool { (*self) > (*other) }
1471             }
1472
1473             #[stable(feature = "rust1", since = "1.0.0")]
1474             #[rustc_const_unstable(feature = "const_cmp", issue = "92391")]
1475             impl const Ord for $t {
1476                 #[inline]
1477                 fn cmp(&self, other: &$t) -> Ordering {
1478                     // The order here is important to generate more optimal assembly.
1479                     // See <https://github.com/rust-lang/rust/issues/63758> for more info.
1480                     if *self < *other { Less }
1481                     else if *self == *other { Equal }
1482                     else { Greater }
1483                 }
1484             }
1485         )*)
1486     }
1487
1488     #[stable(feature = "rust1", since = "1.0.0")]
1489     #[rustc_const_unstable(feature = "const_cmp", issue = "92391")]
1490     impl const Ord for () {
1491         #[inline]
1492         fn cmp(&self, _other: &()) -> Ordering {
1493             Equal
1494         }
1495     }
1496
1497     #[stable(feature = "rust1", since = "1.0.0")]
1498     #[rustc_const_unstable(feature = "const_cmp", issue = "92391")]
1499     impl const Ord for bool {
1500         #[inline]
1501         fn cmp(&self, other: &bool) -> Ordering {
1502             // Casting to i8's and converting the difference to an Ordering generates
1503             // more optimal assembly.
1504             // See <https://github.com/rust-lang/rust/issues/66780> for more info.
1505             match (*self as i8) - (*other as i8) {
1506                 -1 => Less,
1507                 0 => Equal,
1508                 1 => Greater,
1509                 // SAFETY: bool as i8 returns 0 or 1, so the difference can't be anything else
1510                 _ => unsafe { unreachable_unchecked() },
1511             }
1512         }
1513     }
1514
1515     ord_impl! { char usize u8 u16 u32 u64 u128 isize i8 i16 i32 i64 i128 }
1516
1517     #[unstable(feature = "never_type", issue = "35121")]
1518     #[rustc_const_unstable(feature = "const_cmp", issue = "92391")]
1519     impl const PartialEq for ! {
1520         fn eq(&self, _: &!) -> bool {
1521             *self
1522         }
1523     }
1524
1525     #[unstable(feature = "never_type", issue = "35121")]
1526     impl Eq for ! {}
1527
1528     #[unstable(feature = "never_type", issue = "35121")]
1529     #[rustc_const_unstable(feature = "const_cmp", issue = "92391")]
1530     impl const PartialOrd for ! {
1531         fn partial_cmp(&self, _: &!) -> Option<Ordering> {
1532             *self
1533         }
1534     }
1535
1536     #[unstable(feature = "never_type", issue = "35121")]
1537     #[rustc_const_unstable(feature = "const_cmp", issue = "92391")]
1538     impl const Ord for ! {
1539         fn cmp(&self, _: &!) -> Ordering {
1540             *self
1541         }
1542     }
1543
1544     // & pointers
1545
1546     #[stable(feature = "rust1", since = "1.0.0")]
1547     #[rustc_const_unstable(feature = "const_cmp", issue = "92391")]
1548     impl<A: ?Sized, B: ?Sized> const PartialEq<&B> for &A
1549     where
1550         A: ~const PartialEq<B>,
1551     {
1552         #[inline]
1553         fn eq(&self, other: &&B) -> bool {
1554             PartialEq::eq(*self, *other)
1555         }
1556         #[inline]
1557         fn ne(&self, other: &&B) -> bool {
1558             PartialEq::ne(*self, *other)
1559         }
1560     }
1561     #[stable(feature = "rust1", since = "1.0.0")]
1562     impl<A: ?Sized, B: ?Sized> PartialOrd<&B> for &A
1563     where
1564         A: PartialOrd<B>,
1565     {
1566         #[inline]
1567         fn partial_cmp(&self, other: &&B) -> Option<Ordering> {
1568             PartialOrd::partial_cmp(*self, *other)
1569         }
1570         #[inline]
1571         fn lt(&self, other: &&B) -> bool {
1572             PartialOrd::lt(*self, *other)
1573         }
1574         #[inline]
1575         fn le(&self, other: &&B) -> bool {
1576             PartialOrd::le(*self, *other)
1577         }
1578         #[inline]
1579         fn gt(&self, other: &&B) -> bool {
1580             PartialOrd::gt(*self, *other)
1581         }
1582         #[inline]
1583         fn ge(&self, other: &&B) -> bool {
1584             PartialOrd::ge(*self, *other)
1585         }
1586     }
1587     #[stable(feature = "rust1", since = "1.0.0")]
1588     impl<A: ?Sized> Ord for &A
1589     where
1590         A: Ord,
1591     {
1592         #[inline]
1593         fn cmp(&self, other: &Self) -> Ordering {
1594             Ord::cmp(*self, *other)
1595         }
1596     }
1597     #[stable(feature = "rust1", since = "1.0.0")]
1598     impl<A: ?Sized> Eq for &A where A: Eq {}
1599
1600     // &mut pointers
1601
1602     #[stable(feature = "rust1", since = "1.0.0")]
1603     impl<A: ?Sized, B: ?Sized> PartialEq<&mut B> for &mut A
1604     where
1605         A: PartialEq<B>,
1606     {
1607         #[inline]
1608         fn eq(&self, other: &&mut B) -> bool {
1609             PartialEq::eq(*self, *other)
1610         }
1611         #[inline]
1612         fn ne(&self, other: &&mut B) -> bool {
1613             PartialEq::ne(*self, *other)
1614         }
1615     }
1616     #[stable(feature = "rust1", since = "1.0.0")]
1617     impl<A: ?Sized, B: ?Sized> PartialOrd<&mut B> for &mut A
1618     where
1619         A: PartialOrd<B>,
1620     {
1621         #[inline]
1622         fn partial_cmp(&self, other: &&mut B) -> Option<Ordering> {
1623             PartialOrd::partial_cmp(*self, *other)
1624         }
1625         #[inline]
1626         fn lt(&self, other: &&mut B) -> bool {
1627             PartialOrd::lt(*self, *other)
1628         }
1629         #[inline]
1630         fn le(&self, other: &&mut B) -> bool {
1631             PartialOrd::le(*self, *other)
1632         }
1633         #[inline]
1634         fn gt(&self, other: &&mut B) -> bool {
1635             PartialOrd::gt(*self, *other)
1636         }
1637         #[inline]
1638         fn ge(&self, other: &&mut B) -> bool {
1639             PartialOrd::ge(*self, *other)
1640         }
1641     }
1642     #[stable(feature = "rust1", since = "1.0.0")]
1643     impl<A: ?Sized> Ord for &mut A
1644     where
1645         A: Ord,
1646     {
1647         #[inline]
1648         fn cmp(&self, other: &Self) -> Ordering {
1649             Ord::cmp(*self, *other)
1650         }
1651     }
1652     #[stable(feature = "rust1", since = "1.0.0")]
1653     impl<A: ?Sized> Eq for &mut A where A: Eq {}
1654
1655     #[stable(feature = "rust1", since = "1.0.0")]
1656     impl<A: ?Sized, B: ?Sized> PartialEq<&mut B> for &A
1657     where
1658         A: PartialEq<B>,
1659     {
1660         #[inline]
1661         fn eq(&self, other: &&mut B) -> bool {
1662             PartialEq::eq(*self, *other)
1663         }
1664         #[inline]
1665         fn ne(&self, other: &&mut B) -> bool {
1666             PartialEq::ne(*self, *other)
1667         }
1668     }
1669
1670     #[stable(feature = "rust1", since = "1.0.0")]
1671     impl<A: ?Sized, B: ?Sized> PartialEq<&B> for &mut A
1672     where
1673         A: PartialEq<B>,
1674     {
1675         #[inline]
1676         fn eq(&self, other: &&B) -> bool {
1677             PartialEq::eq(*self, *other)
1678         }
1679         #[inline]
1680         fn ne(&self, other: &&B) -> bool {
1681             PartialEq::ne(*self, *other)
1682         }
1683     }
1684 }