]> git.lizzy.rs Git - rust.git/blob - src/libcore/cmp.rs
Rollup merge of #31412 - tshepang:add-trailing-commas, r=steveklabnik
[rust.git] / src / libcore / cmp.rs
1 // Copyright 2012-2014 The Rust Project Developers. See the COPYRIGHT
2 // file at the top-level directory of this distribution and at
3 // http://rust-lang.org/COPYRIGHT.
4 //
5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
8 // option. This file may not be copied, modified, or distributed
9 // except according to those terms.
10
11 //! Functionality for ordering and comparison.
12 //!
13 //! This module defines both `PartialOrd` and `PartialEq` traits which are used
14 //! by the compiler to implement comparison operators. Rust programs may
15 //! implement `PartialOrd` to overload the `<`, `<=`, `>`, and `>=` operators,
16 //! and may implement `PartialEq` to overload the `==` and `!=` operators.
17
18 #![stable(feature = "rust1", since = "1.0.0")]
19
20 use self::Ordering::*;
21
22 use marker::Sized;
23 use option::Option::{self, Some};
24
25 /// Trait for equality comparisons which are [partial equivalence
26 /// relations](http://en.wikipedia.org/wiki/Partial_equivalence_relation).
27 ///
28 /// This trait allows for partial equality, for types that do not have a full
29 /// equivalence relation.  For example, in floating point numbers `NaN != NaN`,
30 /// so floating point types implement `PartialEq` but not `Eq`.
31 ///
32 /// Formally, the equality must be (for all `a`, `b` and `c`):
33 ///
34 /// - symmetric: `a == b` implies `b == a`; and
35 /// - transitive: `a == b` and `b == c` implies `a == c`.
36 ///
37 /// Note that these requirements mean that the trait itself must be implemented
38 /// symmetrically and transitively: if `T: PartialEq<U>` and `U: PartialEq<V>`
39 /// then `U: PartialEq<T>` and `T: PartialEq<V>`.
40 ///
41 /// PartialEq only requires the `eq` method to be implemented; `ne` is defined
42 /// in terms of it by default. Any manual implementation of `ne` *must* respect
43 /// the rule that `eq` is a strict inverse of `ne`; that is, `!(a == b)` if and
44 /// only if `a != b`.
45 ///
46 /// This trait can be used with `#[derive]`.
47 #[lang = "eq"]
48 #[stable(feature = "rust1", since = "1.0.0")]
49 pub trait PartialEq<Rhs: ?Sized = Self> {
50     /// This method tests for `self` and `other` values to be equal, and is used
51     /// by `==`.
52     #[stable(feature = "rust1", since = "1.0.0")]
53     fn eq(&self, other: &Rhs) -> bool;
54
55     /// This method tests for `!=`.
56     #[inline]
57     #[stable(feature = "rust1", since = "1.0.0")]
58     fn ne(&self, other: &Rhs) -> bool { !self.eq(other) }
59 }
60
61 /// Trait for equality comparisons which are [equivalence relations](
62 /// https://en.wikipedia.org/wiki/Equivalence_relation).
63 ///
64 /// This means, that in addition to `a == b` and `a != b` being strict inverses, the equality must
65 /// be (for all `a`, `b` and `c`):
66 ///
67 /// - reflexive: `a == a`;
68 /// - symmetric: `a == b` implies `b == a`; and
69 /// - transitive: `a == b` and `b == c` implies `a == c`.
70 ///
71 /// This property cannot be checked by the compiler, and therefore `Eq` implies
72 /// `PartialEq`, and has no extra methods.
73 ///
74 /// This trait can be used with `#[derive]`.
75 #[stable(feature = "rust1", since = "1.0.0")]
76 pub trait Eq: PartialEq<Self> {
77     // FIXME #13101: this method is used solely by #[deriving] to
78     // assert that every component of a type implements #[deriving]
79     // itself, the current deriving infrastructure means doing this
80     // assertion without using a method on this trait is nearly
81     // impossible.
82     //
83     // This should never be implemented by hand.
84     #[doc(hidden)]
85     #[inline(always)]
86     #[stable(feature = "rust1", since = "1.0.0")]
87     fn assert_receiver_is_total_eq(&self) {}
88 }
89
90 /// An `Ordering` is the result of a comparison between two values.
91 ///
92 /// # Examples
93 ///
94 /// ```
95 /// use std::cmp::Ordering;
96 ///
97 /// let result = 1.cmp(&2);
98 /// assert_eq!(Ordering::Less, result);
99 ///
100 /// let result = 1.cmp(&1);
101 /// assert_eq!(Ordering::Equal, result);
102 ///
103 /// let result = 2.cmp(&1);
104 /// assert_eq!(Ordering::Greater, result);
105 /// ```
106 #[derive(Clone, Copy, PartialEq, Debug)]
107 #[stable(feature = "rust1", since = "1.0.0")]
108 pub enum Ordering {
109     /// An ordering where a compared value is less [than another].
110     #[stable(feature = "rust1", since = "1.0.0")]
111     Less = -1,
112     /// An ordering where a compared value is equal [to another].
113     #[stable(feature = "rust1", since = "1.0.0")]
114     Equal = 0,
115     /// An ordering where a compared value is greater [than another].
116     #[stable(feature = "rust1", since = "1.0.0")]
117     Greater = 1,
118 }
119
120 impl Ordering {
121     /// Reverse the `Ordering`.
122     ///
123     /// * `Less` becomes `Greater`.
124     /// * `Greater` becomes `Less`.
125     /// * `Equal` becomes `Equal`.
126     ///
127     /// # Examples
128     ///
129     /// Basic behavior:
130     ///
131     /// ```
132     /// use std::cmp::Ordering;
133     ///
134     /// assert_eq!(Ordering::Less.reverse(), Ordering::Greater);
135     /// assert_eq!(Ordering::Equal.reverse(), Ordering::Equal);
136     /// assert_eq!(Ordering::Greater.reverse(), Ordering::Less);
137     /// ```
138     ///
139     /// This method can be used to reverse a comparison:
140     ///
141     /// ```
142     /// let mut data: &mut [_] = &mut [2, 10, 5, 8];
143     ///
144     /// // sort the array from largest to smallest.
145     /// data.sort_by(|a, b| a.cmp(b).reverse());
146     ///
147     /// let b: &mut [_] = &mut [10, 8, 5, 2];
148     /// assert!(data == b);
149     /// ```
150     #[inline]
151     #[stable(feature = "rust1", since = "1.0.0")]
152     pub fn reverse(self) -> Ordering {
153         match self {
154             Less => Greater,
155             Equal => Equal,
156             Greater => Less,
157         }
158     }
159 }
160
161 /// Trait for types that form a [total order](https://en.wikipedia.org/wiki/Total_order).
162 ///
163 /// An order is a total order if it is (for all `a`, `b` and `c`):
164 ///
165 /// - total and antisymmetric: exactly one of `a < b`, `a == b` or `a > b` is true; and
166 /// - transitive, `a < b` and `b < c` implies `a < c`. The same must hold for both `==` and `>`.
167 ///
168 /// When this trait is `derive`d, it produces a lexicographic ordering.
169 ///
170 /// This trait can be used with `#[derive]`.
171 #[stable(feature = "rust1", since = "1.0.0")]
172 pub trait Ord: Eq + PartialOrd<Self> {
173     /// This method returns an `Ordering` between `self` and `other`.
174     ///
175     /// By convention, `self.cmp(&other)` returns the ordering matching the expression
176     /// `self <operator> other` if true.
177     ///
178     /// # Examples
179     ///
180     /// ```
181     /// use std::cmp::Ordering;
182     ///
183     /// assert_eq!(5.cmp(&10), Ordering::Less);
184     /// assert_eq!(10.cmp(&5), Ordering::Greater);
185     /// assert_eq!(5.cmp(&5), Ordering::Equal);
186     /// ```
187     #[stable(feature = "rust1", since = "1.0.0")]
188     fn cmp(&self, other: &Self) -> Ordering;
189 }
190
191 #[stable(feature = "rust1", since = "1.0.0")]
192 impl Eq for Ordering {}
193
194 #[stable(feature = "rust1", since = "1.0.0")]
195 impl Ord for Ordering {
196     #[inline]
197     fn cmp(&self, other: &Ordering) -> Ordering {
198         (*self as i32).cmp(&(*other as i32))
199     }
200 }
201
202 #[stable(feature = "rust1", since = "1.0.0")]
203 impl PartialOrd for Ordering {
204     #[inline]
205     fn partial_cmp(&self, other: &Ordering) -> Option<Ordering> {
206         (*self as i32).partial_cmp(&(*other as i32))
207     }
208 }
209
210 /// Trait for values that can be compared for a sort-order.
211 ///
212 /// The comparison must satisfy, for all `a`, `b` and `c`:
213 ///
214 /// - antisymmetry: if `a < b` then `!(a > b)`, as well as `a > b` implying `!(a < b)`; and
215 /// - transitivity: `a < b` and `b < c` implies `a < c`. The same must hold for both `==` and `>`.
216 ///
217 /// Note that these requirements mean that the trait itself must be implemented symmetrically and
218 /// transitively: if `T: PartialOrd<U>` and `U: PartialOrd<V>` then `U: PartialOrd<T>` and `T:
219 /// PartialOrd<V>`.
220 ///
221 /// PartialOrd only requires implementation of the `partial_cmp` method, with the others generated
222 /// from default implementations.
223 ///
224 /// However it remains possible to implement the others separately for types which do not have a
225 /// total order. For example, for floating point numbers, `NaN < 0 == false` and `NaN >= 0 ==
226 /// false` (cf. IEEE 754-2008 section 5.11).
227 ///
228 /// This trait can be used with `#[derive]`.
229 #[lang = "ord"]
230 #[stable(feature = "rust1", since = "1.0.0")]
231 pub trait PartialOrd<Rhs: ?Sized = Self>: PartialEq<Rhs> {
232     /// This method returns an ordering between `self` and `other` values if one exists.
233     ///
234     /// # Examples
235     ///
236     /// ```
237     /// use std::cmp::Ordering;
238     ///
239     /// let result = 1.0.partial_cmp(&2.0);
240     /// assert_eq!(result, Some(Ordering::Less));
241     ///
242     /// let result = 1.0.partial_cmp(&1.0);
243     /// assert_eq!(result, Some(Ordering::Equal));
244     ///
245     /// let result = 2.0.partial_cmp(&1.0);
246     /// assert_eq!(result, Some(Ordering::Greater));
247     /// ```
248     ///
249     /// When comparison is impossible:
250     ///
251     /// ```
252     /// let result = std::f64::NAN.partial_cmp(&1.0);
253     /// assert_eq!(result, None);
254     /// ```
255     #[stable(feature = "rust1", since = "1.0.0")]
256     fn partial_cmp(&self, other: &Rhs) -> Option<Ordering>;
257
258     /// This method tests less than (for `self` and `other`) and is used by the `<` operator.
259     ///
260     /// # Examples
261     ///
262     /// ```
263     /// let result = 1.0 < 2.0;
264     /// assert_eq!(result, true);
265     ///
266     /// let result = 2.0 < 1.0;
267     /// assert_eq!(result, false);
268     /// ```
269     #[inline]
270     #[stable(feature = "rust1", since = "1.0.0")]
271     fn lt(&self, other: &Rhs) -> bool {
272         match self.partial_cmp(other) {
273             Some(Less) => true,
274             _ => false,
275         }
276     }
277
278     /// This method tests less than or equal to (for `self` and `other`) and is used by the `<=`
279     /// operator.
280     ///
281     /// # Examples
282     ///
283     /// ```
284     /// let result = 1.0 <= 2.0;
285     /// assert_eq!(result, true);
286     ///
287     /// let result = 2.0 <= 2.0;
288     /// assert_eq!(result, true);
289     /// ```
290     #[inline]
291     #[stable(feature = "rust1", since = "1.0.0")]
292     fn le(&self, other: &Rhs) -> bool {
293         match self.partial_cmp(other) {
294             Some(Less) | Some(Equal) => true,
295             _ => false,
296         }
297     }
298
299     /// This method tests greater than (for `self` and `other`) and is used by the `>` operator.
300     ///
301     /// # Examples
302     ///
303     /// ```
304     /// let result = 1.0 > 2.0;
305     /// assert_eq!(result, false);
306     ///
307     /// let result = 2.0 > 2.0;
308     /// assert_eq!(result, false);
309     /// ```
310     #[inline]
311     #[stable(feature = "rust1", since = "1.0.0")]
312     fn gt(&self, other: &Rhs) -> bool {
313         match self.partial_cmp(other) {
314             Some(Greater) => true,
315             _ => false,
316         }
317     }
318
319     /// This method tests greater than or equal to (for `self` and `other`) and is used by the `>=`
320     /// operator.
321     ///
322     /// # Examples
323     ///
324     /// ```
325     /// let result = 2.0 >= 1.0;
326     /// assert_eq!(result, true);
327     ///
328     /// let result = 2.0 >= 2.0;
329     /// assert_eq!(result, true);
330     /// ```
331     #[inline]
332     #[stable(feature = "rust1", since = "1.0.0")]
333     fn ge(&self, other: &Rhs) -> bool {
334         match self.partial_cmp(other) {
335             Some(Greater) | Some(Equal) => true,
336             _ => false,
337         }
338     }
339 }
340
341 /// Compare and return the minimum of two values.
342 ///
343 /// Returns the first argument if the comparison determines them to be equal.
344 ///
345 /// # Examples
346 ///
347 /// ```
348 /// use std::cmp;
349 ///
350 /// assert_eq!(1, cmp::min(1, 2));
351 /// assert_eq!(2, cmp::min(2, 2));
352 /// ```
353 #[inline]
354 #[stable(feature = "rust1", since = "1.0.0")]
355 pub fn min<T: Ord>(v1: T, v2: T) -> T {
356     if v1 <= v2 { v1 } else { v2 }
357 }
358
359 /// Compare and return the maximum of two values.
360 ///
361 /// Returns the second argument if the comparison determines them to be equal.
362 ///
363 /// # Examples
364 ///
365 /// ```
366 /// use std::cmp;
367 ///
368 /// assert_eq!(2, cmp::max(1, 2));
369 /// assert_eq!(2, cmp::max(2, 2));
370 /// ```
371 #[inline]
372 #[stable(feature = "rust1", since = "1.0.0")]
373 pub fn max<T: Ord>(v1: T, v2: T) -> T {
374     if v2 >= v1 { v2 } else { v1 }
375 }
376
377 // Implementation of PartialEq, Eq, PartialOrd and Ord for primitive types
378 mod impls {
379     use cmp::{PartialOrd, Ord, PartialEq, Eq, Ordering};
380     use cmp::Ordering::{Less, Greater, Equal};
381     use marker::Sized;
382     use option::Option;
383     use option::Option::{Some, None};
384
385     macro_rules! partial_eq_impl {
386         ($($t:ty)*) => ($(
387             #[stable(feature = "rust1", since = "1.0.0")]
388             impl PartialEq for $t {
389                 #[inline]
390                 fn eq(&self, other: &$t) -> bool { (*self) == (*other) }
391                 #[inline]
392                 fn ne(&self, other: &$t) -> bool { (*self) != (*other) }
393             }
394         )*)
395     }
396
397     #[stable(feature = "rust1", since = "1.0.0")]
398     impl PartialEq for () {
399         #[inline]
400         fn eq(&self, _other: &()) -> bool { true }
401         #[inline]
402         fn ne(&self, _other: &()) -> bool { false }
403     }
404
405     partial_eq_impl! {
406         bool char usize u8 u16 u32 u64 isize i8 i16 i32 i64 f32 f64
407     }
408
409     macro_rules! eq_impl {
410         ($($t:ty)*) => ($(
411             #[stable(feature = "rust1", since = "1.0.0")]
412             impl Eq for $t {}
413         )*)
414     }
415
416     eq_impl! { () bool char usize u8 u16 u32 u64 isize i8 i16 i32 i64 }
417
418     macro_rules! partial_ord_impl {
419         ($($t:ty)*) => ($(
420             #[stable(feature = "rust1", since = "1.0.0")]
421             impl PartialOrd for $t {
422                 #[inline]
423                 fn partial_cmp(&self, other: &$t) -> Option<Ordering> {
424                     match (self <= other, self >= other) {
425                         (false, false) => None,
426                         (false, true) => Some(Greater),
427                         (true, false) => Some(Less),
428                         (true, true) => Some(Equal),
429                     }
430                 }
431                 #[inline]
432                 fn lt(&self, other: &$t) -> bool { (*self) < (*other) }
433                 #[inline]
434                 fn le(&self, other: &$t) -> bool { (*self) <= (*other) }
435                 #[inline]
436                 fn ge(&self, other: &$t) -> bool { (*self) >= (*other) }
437                 #[inline]
438                 fn gt(&self, other: &$t) -> bool { (*self) > (*other) }
439             }
440         )*)
441     }
442
443     #[stable(feature = "rust1", since = "1.0.0")]
444     impl PartialOrd for () {
445         #[inline]
446         fn partial_cmp(&self, _: &()) -> Option<Ordering> {
447             Some(Equal)
448         }
449     }
450
451     #[stable(feature = "rust1", since = "1.0.0")]
452     impl PartialOrd for bool {
453         #[inline]
454         fn partial_cmp(&self, other: &bool) -> Option<Ordering> {
455             (*self as u8).partial_cmp(&(*other as u8))
456         }
457     }
458
459     partial_ord_impl! { f32 f64 }
460
461     macro_rules! ord_impl {
462         ($($t:ty)*) => ($(
463             #[stable(feature = "rust1", since = "1.0.0")]
464             impl PartialOrd for $t {
465                 #[inline]
466                 fn partial_cmp(&self, other: &$t) -> Option<Ordering> {
467                     Some(self.cmp(other))
468                 }
469                 #[inline]
470                 fn lt(&self, other: &$t) -> bool { (*self) < (*other) }
471                 #[inline]
472                 fn le(&self, other: &$t) -> bool { (*self) <= (*other) }
473                 #[inline]
474                 fn ge(&self, other: &$t) -> bool { (*self) >= (*other) }
475                 #[inline]
476                 fn gt(&self, other: &$t) -> bool { (*self) > (*other) }
477             }
478
479             #[stable(feature = "rust1", since = "1.0.0")]
480             impl Ord for $t {
481                 #[inline]
482                 fn cmp(&self, other: &$t) -> Ordering {
483                     if *self == *other { Equal }
484                     else if *self < *other { Less }
485                     else { Greater }
486                 }
487             }
488         )*)
489     }
490
491     #[stable(feature = "rust1", since = "1.0.0")]
492     impl Ord for () {
493         #[inline]
494         fn cmp(&self, _other: &()) -> Ordering { Equal }
495     }
496
497     #[stable(feature = "rust1", since = "1.0.0")]
498     impl Ord for bool {
499         #[inline]
500         fn cmp(&self, other: &bool) -> Ordering {
501             (*self as u8).cmp(&(*other as u8))
502         }
503     }
504
505     ord_impl! { char usize u8 u16 u32 u64 isize i8 i16 i32 i64 }
506
507     // & pointers
508
509     #[stable(feature = "rust1", since = "1.0.0")]
510     impl<'a, 'b, A: ?Sized, B: ?Sized> PartialEq<&'b B> for &'a A where A: PartialEq<B> {
511         #[inline]
512         fn eq(&self, other: & &'b B) -> bool { PartialEq::eq(*self, *other) }
513         #[inline]
514         fn ne(&self, other: & &'b B) -> bool { PartialEq::ne(*self, *other) }
515     }
516     #[stable(feature = "rust1", since = "1.0.0")]
517     impl<'a, 'b, A: ?Sized, B: ?Sized> PartialOrd<&'b B> for &'a A where A: PartialOrd<B> {
518         #[inline]
519         fn partial_cmp(&self, other: &&'b B) -> Option<Ordering> {
520             PartialOrd::partial_cmp(*self, *other)
521         }
522         #[inline]
523         fn lt(&self, other: & &'b B) -> bool { PartialOrd::lt(*self, *other) }
524         #[inline]
525         fn le(&self, other: & &'b B) -> bool { PartialOrd::le(*self, *other) }
526         #[inline]
527         fn ge(&self, other: & &'b B) -> bool { PartialOrd::ge(*self, *other) }
528         #[inline]
529         fn gt(&self, other: & &'b B) -> bool { PartialOrd::gt(*self, *other) }
530     }
531     #[stable(feature = "rust1", since = "1.0.0")]
532     impl<'a, A: ?Sized> Ord for &'a A where A: Ord {
533         #[inline]
534         fn cmp(&self, other: & &'a A) -> Ordering { Ord::cmp(*self, *other) }
535     }
536     #[stable(feature = "rust1", since = "1.0.0")]
537     impl<'a, A: ?Sized> Eq for &'a A where A: Eq {}
538
539     // &mut pointers
540
541     #[stable(feature = "rust1", since = "1.0.0")]
542     impl<'a, 'b, A: ?Sized, B: ?Sized> PartialEq<&'b mut B> for &'a mut A where A: PartialEq<B> {
543         #[inline]
544         fn eq(&self, other: &&'b mut B) -> bool { PartialEq::eq(*self, *other) }
545         #[inline]
546         fn ne(&self, other: &&'b mut B) -> bool { PartialEq::ne(*self, *other) }
547     }
548     #[stable(feature = "rust1", since = "1.0.0")]
549     impl<'a, 'b, A: ?Sized, B: ?Sized> PartialOrd<&'b mut B> for &'a mut A where A: PartialOrd<B> {
550         #[inline]
551         fn partial_cmp(&self, other: &&'b mut B) -> Option<Ordering> {
552             PartialOrd::partial_cmp(*self, *other)
553         }
554         #[inline]
555         fn lt(&self, other: &&'b mut B) -> bool { PartialOrd::lt(*self, *other) }
556         #[inline]
557         fn le(&self, other: &&'b mut B) -> bool { PartialOrd::le(*self, *other) }
558         #[inline]
559         fn ge(&self, other: &&'b mut B) -> bool { PartialOrd::ge(*self, *other) }
560         #[inline]
561         fn gt(&self, other: &&'b mut B) -> bool { PartialOrd::gt(*self, *other) }
562     }
563     #[stable(feature = "rust1", since = "1.0.0")]
564     impl<'a, A: ?Sized> Ord for &'a mut A where A: Ord {
565         #[inline]
566         fn cmp(&self, other: &&'a mut A) -> Ordering { Ord::cmp(*self, *other) }
567     }
568     #[stable(feature = "rust1", since = "1.0.0")]
569     impl<'a, A: ?Sized> Eq for &'a mut A where A: Eq {}
570
571     #[stable(feature = "rust1", since = "1.0.0")]
572     impl<'a, 'b, A: ?Sized, B: ?Sized> PartialEq<&'b mut B> for &'a A where A: PartialEq<B> {
573         #[inline]
574         fn eq(&self, other: &&'b mut B) -> bool { PartialEq::eq(*self, *other) }
575         #[inline]
576         fn ne(&self, other: &&'b mut B) -> bool { PartialEq::ne(*self, *other) }
577     }
578
579     #[stable(feature = "rust1", since = "1.0.0")]
580     impl<'a, 'b, A: ?Sized, B: ?Sized> PartialEq<&'b B> for &'a mut A where A: PartialEq<B> {
581         #[inline]
582         fn eq(&self, other: &&'b B) -> bool { PartialEq::eq(*self, *other) }
583         #[inline]
584         fn ne(&self, other: &&'b B) -> bool { PartialEq::ne(*self, *other) }
585     }
586 }