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