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