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     /// 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 /// The equivalence relation. Two values may be equivalent even if they are
 275 /// of different types. The most common use case for this relation is
 276 /// container types; e.g. it is often desirable to be able to use `&str`
 277 /// values to look up entries in a container with `String` keys.
 278 #[deprecated = "Use overloaded core::cmp::PartialEq"]
 279 pub trait Equiv<Sized? T> for Sized? {
 280     /// Implement this function to decide equivalent values.
 281     fn equiv(&self, other: &T) -> bool;
 282 }
 283
 284 /// Compare and return the minimum of two values.
 285 #[inline]
 286 #[stable]
 287 pub fn min<T: Ord>(v1: T, v2: T) -> T {
 288     if v1 < v2 { v1 } else { v2 }
 289 }
 290
 291 /// Compare and return the maximum of two values.
 292 #[inline]
 293 #[stable]
 294 pub fn max<T: Ord>(v1: T, v2: T) -> T {
 295     if v1 > v2 { v1 } else { v2 }
 296 }
 297
 298 /// Compare and return the minimum of two values if there is one.
 299 ///
 300 /// Returns the first argument if the comparison determines them to be equal.
 301 #[inline]
 302 #[experimental]
 303 pub fn partial_min<T: PartialOrd>(v1: T, v2: T) -> Option<T> {
 304     match v1.partial_cmp(&v2) {
 305         Some(Less) | Some(Equal) => Some(v1),
 306         Some(Greater) => Some(v2),
 307         None => None
 308     }
 309 }
 310
 311 /// Compare and return the maximum of two values if there is one.
 312 ///
 313 /// Returns the first argument if the comparison determines them to be equal.
 314 #[inline]
 315 #[experimental]
 316 pub fn partial_max<T: PartialOrd>(v1: T, v2: T) -> Option<T> {
 317     match v1.partial_cmp(&v2) {
 318         Some(Less) => Some(v2),
 319         Some(Equal) | Some(Greater) => Some(v1),
 320         None => None
 321     }
 322 }
 323
 324 // Implementation of PartialEq, Eq, PartialOrd and Ord for primitive types
 325 mod impls {
 326     use cmp::{PartialOrd, Ord, PartialEq, Eq, Ordering};
 327     use cmp::Ordering::{Less, Greater, Equal};
 328     use kinds::Sized;
 329     use option::Option;
 330     use option::Option::{Some, None};
 331
 332     macro_rules! partial_eq_impl {
 333         ($($t:ty)*) => ($(
 334             #[stable]
 335             impl PartialEq for $t {
 336                 #[inline]
 337                 fn eq(&self, other: &$t) -> bool { (*self) == (*other) }
 338                 #[inline]
 339                 fn ne(&self, other: &$t) -> bool { (*self) != (*other) }
 340             }
 341         )*)
 342     }
 343
 344     #[stable]
 345     impl PartialEq for () {
 346         #[inline]
 347         fn eq(&self, _other: &()) -> bool { true }
 348         #[inline]
 349         fn ne(&self, _other: &()) -> bool { false }
 350     }
 351
 352     partial_eq_impl! {
 353         bool char uint u8 u16 u32 u64 int i8 i16 i32 i64 f32 f64
 354     }
 355
 356     macro_rules! eq_impl {
 357         ($($t:ty)*) => ($(
 358             #[stable]
 359             impl Eq for $t {}
 360         )*)
 361     }
 362
 363     eq_impl! { () bool char uint u8 u16 u32 u64 int i8 i16 i32 i64 }
 364
 365     macro_rules! partial_ord_impl {
 366         ($($t:ty)*) => ($(
 367             #[stable]
 368             impl PartialOrd for $t {
 369                 #[inline]
 370                 fn partial_cmp(&self, other: &$t) -> Option<Ordering> {
 371                     match (self <= other, self >= other) {
 372                         (false, false) => None,
 373                         (false, true) => Some(Greater),
 374                         (true, false) => Some(Less),
 375                         (true, true) => Some(Equal),
 376                     }
 377                 }
 378                 #[inline]
 379                 fn lt(&self, other: &$t) -> bool { (*self) < (*other) }
 380                 #[inline]
 381                 fn le(&self, other: &$t) -> bool { (*self) <= (*other) }
 382                 #[inline]
 383                 fn ge(&self, other: &$t) -> bool { (*self) >= (*other) }
 384                 #[inline]
 385                 fn gt(&self, other: &$t) -> bool { (*self) > (*other) }
 386             }
 387         )*)
 388     }
 389
 390     #[stable]
 391     impl PartialOrd for () {
 392         #[inline]
 393         fn partial_cmp(&self, _: &()) -> Option<Ordering> {
 394             Some(Equal)
 395         }
 396     }
 397
 398     #[stable]
 399     impl PartialOrd for bool {
 400         #[inline]
 401         fn partial_cmp(&self, other: &bool) -> Option<Ordering> {
 402             (*self as u8).partial_cmp(&(*other as u8))
 403         }
 404     }
 405
 406     partial_ord_impl! { char uint u8 u16 u32 u64 int i8 i16 i32 i64 f32 f64 }
 407
 408     macro_rules! ord_impl {
 409         ($($t:ty)*) => ($(
 410             #[stable]
 411             impl Ord for $t {
 412                 #[inline]
 413                 fn cmp(&self, other: &$t) -> Ordering {
 414                     if *self < *other { Less }
 415                     else if *self > *other { Greater }
 416                     else { Equal }
 417                 }
 418             }
 419         )*)
 420     }
 421
 422     #[stable]
 423     impl Ord for () {
 424         #[inline]
 425         fn cmp(&self, _other: &()) -> Ordering { Equal }
 426     }
 427
 428     #[stable]
 429     impl Ord for bool {
 430         #[inline]
 431         fn cmp(&self, other: &bool) -> Ordering {
 432             (*self as u8).cmp(&(*other as u8))
 433         }
 434     }
 435
 436     ord_impl! { char uint u8 u16 u32 u64 int i8 i16 i32 i64 }
 437
 438     // & pointers
 439
 440     #[stable]
 441     impl<'a, 'b, Sized? A, Sized? B> PartialEq<&'b B> for &'a A where A: PartialEq<B> {
 442         #[inline]
 443         fn eq(&self, other: & &'b B) -> bool { PartialEq::eq(*self, *other) }
 444         #[inline]
 445         fn ne(&self, other: & &'b B) -> bool { PartialEq::ne(*self, *other) }
 446     }
 447     #[stable]
 448     impl<'a, 'b, Sized? A, Sized? B> PartialOrd<&'b B> for &'a A where A: PartialOrd<B> {
 449         #[inline]
 450         fn partial_cmp(&self, other: &&'b B) -> Option<Ordering> {
 451             PartialOrd::partial_cmp(*self, *other)
 452         }
 453         #[inline]
 454         fn lt(&self, other: & &'b B) -> bool { PartialOrd::lt(*self, *other) }
 455         #[inline]
 456         fn le(&self, other: & &'b B) -> bool { PartialOrd::le(*self, *other) }
 457         #[inline]
 458         fn ge(&self, other: & &'b B) -> bool { PartialOrd::ge(*self, *other) }
 459         #[inline]
 460         fn gt(&self, other: & &'b B) -> bool { PartialOrd::gt(*self, *other) }
 461     }
 462     #[stable]
 463     impl<'a, Sized? A> Ord for &'a A where A: Ord {
 464         #[inline]
 465         fn cmp(&self, other: & &'a A) -> Ordering { Ord::cmp(*self, *other) }
 466     }
 467     #[stable]
 468     impl<'a, Sized? A> Eq for &'a A where A: Eq {}
 469
 470     // &mut pointers
 471
 472     #[stable]
 473     impl<'a, 'b, Sized? A, Sized? B> PartialEq<&'b mut B> for &'a mut A where A: PartialEq<B> {
 474         #[inline]
 475         fn eq(&self, other: &&'b mut B) -> bool { PartialEq::eq(*self, *other) }
 476         #[inline]
 477         fn ne(&self, other: &&'b mut B) -> bool { PartialEq::ne(*self, *other) }
 478     }
 479     #[stable]
 480     impl<'a, 'b, Sized? A, Sized? B> PartialOrd<&'b mut B> for &'a mut A where A: PartialOrd<B> {
 481         #[inline]
 482         fn partial_cmp(&self, other: &&'b mut B) -> Option<Ordering> {
 483             PartialOrd::partial_cmp(*self, *other)
 484         }
 485         #[inline]
 486         fn lt(&self, other: &&'b mut B) -> bool { PartialOrd::lt(*self, *other) }
 487         #[inline]
 488         fn le(&self, other: &&'b mut B) -> bool { PartialOrd::le(*self, *other) }
 489         #[inline]
 490         fn ge(&self, other: &&'b mut B) -> bool { PartialOrd::ge(*self, *other) }
 491         #[inline]
 492         fn gt(&self, other: &&'b mut B) -> bool { PartialOrd::gt(*self, *other) }
 493     }
 494     #[stable]
 495     impl<'a, Sized? A> Ord for &'a mut A where A: Ord {
 496         #[inline]
 497         fn cmp(&self, other: &&'a mut A) -> Ordering { Ord::cmp(*self, *other) }
 498     }
 499     #[stable]
 500     impl<'a, Sized? A> Eq for &'a mut A where A: Eq {}
 501
 502     #[stable]
 503     impl<'a, 'b, Sized? A, Sized? B> PartialEq<&'b mut B> for &'a A where A: PartialEq<B> {
 504         #[inline]
 505         fn eq(&self, other: &&'b mut B) -> bool { PartialEq::eq(*self, *other) }
 506         #[inline]
 507         fn ne(&self, other: &&'b mut B) -> bool { PartialEq::ne(*self, *other) }
 508     }
 509
 510     #[stable]
 511     impl<'a, 'b, Sized? A, Sized? B> PartialEq<&'b B> for &'a mut A where A: PartialEq<B> {
 512         #[inline]
 513         fn eq(&self, other: &&'b B) -> bool { PartialEq::eq(*self, *other) }
 514         #[inline]
 515         fn ne(&self, other: &&'b B) -> bool { PartialEq::ne(*self, *other) }
 516     }
 517 }