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