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