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