library/core/src/cmp.rs

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