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