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