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