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 `Ord` and `Eq` comparison traits.
  12 //!
  13 //! This module defines both `Ord` and `Eq` traits which are used by the
  14 //! compiler to implement comparison operators. Rust programs may implement
  15 //!`Ord` to overload the `<`, `<=`, `>`, and `>=` operators, and may implement
  16 //! `Eq` to overload the `==` and `!=` operators.
  17 //!
  18 //! For example, to define a type with a customized definition for the Eq
  19 //! operators, you could do the following:
  20 //!
  21 //! ```rust
  22 //! // Our type.
  23 //! struct SketchyNum {
  24 //!     num : int
  25 //! }
  26 //!
  27 //! // Our implementation of `Eq` to support `==` and `!=`.
  28 //! impl Eq for SketchyNum {
  29 //!     // Our custom eq allows numbers which are near each other to be equal! :D
  30 //!     fn eq(&self, other: &SketchyNum) -> bool {
  31 //!         (self.num - other.num).abs() < 5
  32 //!     }
  33 //! }
  34 //!
  35 //! // Now these binary operators will work when applied!
  36 //! assert!(SketchyNum {num: 37} == SketchyNum {num: 34});
  37 //! assert!(SketchyNum {num: 25} != SketchyNum {num: 57});
  38 //! ```
  39
  40 pub use PartialEq = cmp::Eq;
  41 pub use PartialOrd = cmp::Ord;
  42
  43 /// Trait for values that can be compared for equality and inequality.
  44 ///
  45 /// This trait allows partial equality, where types can be unordered instead of
  46 /// strictly equal or unequal. For example, with the built-in floating-point
  47 /// types `a == b` and `a != b` will both evaluate to false if either `a` or
  48 /// `b` is NaN (cf. IEEE 754-2008 section 5.11).
  49 ///
  50 /// Eq only requires the `eq` method to be implemented; `ne` is its negation by
  51 /// default.
  52 ///
  53 /// Eventually, this will be implemented by default for types that implement
  54 /// `TotalEq`.
  55 #[lang="eq"]
  56 pub trait Eq {
  57     /// This method tests for `self` and `other` values to be equal, and is used by `==`.
  58     fn eq(&self, other: &Self) -> bool;
  59
  60     /// This method tests for `!=`.
  61     #[inline]
  62     fn ne(&self, other: &Self) -> bool { !self.eq(other) }
  63 }
  64
  65 /// Trait for equality comparisons which are [equivalence relations](
  66 /// https://en.wikipedia.org/wiki/Equivalence_relation).
  67 ///
  68 /// This means, that in addition to `a == b` and `a != b` being strict
  69 /// inverses, the equality must be (for all `a`, `b` and `c`):
  70 ///
  71 /// - reflexive: `a == a`;
  72 /// - symmetric: `a == b` implies `b == a`; and
  73 /// - transitive: `a == b` and `b == c` implies `a == c`.
  74 pub trait TotalEq: Eq {
  75     // FIXME #13101: this method is used solely by #[deriving] to
  76     // assert that every component of a type implements #[deriving]
  77     // itself, the current deriving infrastructure means doing this
  78     // assertion without using a method on this trait is nearly
  79     // impossible.
  80     //
  81     // This should never be implemented by hand.
  82     #[doc(hidden)]
  83     #[inline(always)]
  84     fn assert_receiver_is_total_eq(&self) {}
  85 }
  86
  87 /// An ordering is, e.g, a result of a comparison between two values.
  88 #[deriving(Clone, Eq, Show)]
  89 pub enum Ordering {
  90    /// An ordering where a compared value is less [than another].
  91    Less = -1,
  92    /// An ordering where a compared value is equal [to another].
  93    Equal = 0,
  94    /// An ordering where a compared value is greater [than another].
  95    Greater = 1
  96 }
  97
  98 /// Trait for types that form a [total order](
  99 /// https://en.wikipedia.org/wiki/Total_order).
 100 ///
 101 /// An order is a total order if it is (for all `a`, `b` and `c`):
 102 ///
 103 /// - total and antisymmetric: exactly one of `a < b`, `a == b` or `a > b` is
 104 ///   true; and
 105 /// - transitive, `a < b` and `b < c` implies `a < c`. The same must hold for
 106 ///   both `==` and `>`.
 107 pub trait TotalOrd: TotalEq + Ord {
 108     /// This method returns an ordering between `self` and `other` values.
 109     ///
 110     /// By convention, `self.cmp(&other)` returns the ordering matching
 111     /// the expression `self <operator> other` if true.  For example:
 112     ///
 113     /// ```
 114     /// assert_eq!( 5u.cmp(&10), Less);     // because 5 < 10
 115     /// assert_eq!(10u.cmp(&5),  Greater);  // because 10 > 5
 116     /// assert_eq!( 5u.cmp(&5),  Equal);    // because 5 == 5
 117     /// ```
 118     fn cmp(&self, other: &Self) -> Ordering;
 119 }
 120
 121 impl TotalEq for Ordering {}
 122
 123 impl TotalOrd for Ordering {
 124     #[inline]
 125     fn cmp(&self, other: &Ordering) -> Ordering {
 126         (*self as int).cmp(&(*other as int))
 127     }
 128 }
 129
 130 impl Ord for Ordering {
 131     #[inline]
 132     fn lt(&self, other: &Ordering) -> bool { (*self as int) < (*other as int) }
 133 }
 134
 135 /// Combine orderings, lexically.
 136 ///
 137 /// For example for a type `(int, int)`, two comparisons could be done.
 138 /// If the first ordering is different, the first ordering is all that must be returned.
 139 /// If the first ordering is equal, then second ordering is returned.
 140 #[inline]
 141 pub fn lexical_ordering(o1: Ordering, o2: Ordering) -> Ordering {
 142     match o1 {
 143         Equal => o2,
 144         _ => o1
 145     }
 146 }
 147
 148 /// Trait for values that can be compared for a sort-order.
 149 ///
 150 /// Ord only requires implementation of the `lt` method,
 151 /// with the others generated from default implementations.
 152 ///
 153 /// However it remains possible to implement the others separately,
 154 /// for compatibility with floating-point NaN semantics
 155 /// (cf. IEEE 754-2008 section 5.11).
 156 #[lang="ord"]
 157 pub trait Ord: Eq {
 158     /// This method tests less than (for `self` and `other`) and is used by the `<` operator.
 159     fn lt(&self, other: &Self) -> bool;
 160
 161     /// This method tests less than or equal to (`<=`).
 162     #[inline]
 163     fn le(&self, other: &Self) -> bool { !other.lt(self) }
 164
 165     /// This method tests greater than (`>`).
 166     #[inline]
 167     fn gt(&self, other: &Self) -> bool {  other.lt(self) }
 168
 169     /// This method tests greater than or equal to (`>=`).
 170     #[inline]
 171     fn ge(&self, other: &Self) -> bool { !self.lt(other) }
 172 }
 173
 174 /// The equivalence relation. Two values may be equivalent even if they are
 175 /// of different types. The most common use case for this relation is
 176 /// container types; e.g. it is often desirable to be able to use `&str`
 177 /// values to look up entries in a container with `String` keys.
 178 pub trait Equiv<T> {
 179     /// Implement this function to decide equivalent values.
 180     fn equiv(&self, other: &T) -> bool;
 181 }
 182
 183 /// Compare and return the minimum of two values.
 184 #[inline]
 185 pub fn min<T: TotalOrd>(v1: T, v2: T) -> T {
 186     if v1 < v2 { v1 } else { v2 }
 187 }
 188
 189 /// Compare and return the maximum of two values.
 190 #[inline]
 191 pub fn max<T: TotalOrd>(v1: T, v2: T) -> T {
 192     if v1 > v2 { v1 } else { v2 }
 193 }
 194
 195 // Implementation of Eq, TotalEq, Ord and TotalOrd for primitive types
 196 #[cfg(not(test))]
 197 mod impls {
 198     use cmp::{Ord, TotalOrd, Eq, TotalEq, Ordering, Less, Greater, Equal};
 199
 200     macro_rules! eq_impl(
 201         ($($t:ty)*) => ($(
 202             impl Eq for $t {
 203                 #[inline]
 204                 fn eq(&self, other: &$t) -> bool { (*self) == (*other) }
 205                 #[inline]
 206                 fn ne(&self, other: &$t) -> bool { (*self) != (*other) }
 207             }
 208         )*)
 209     )
 210
 211     impl Eq for () {
 212         #[inline]
 213         fn eq(&self, _other: &()) -> bool { true }
 214         #[inline]
 215         fn ne(&self, _other: &()) -> bool { false }
 216     }
 217
 218     eq_impl!(bool char uint u8 u16 u32 u64 int i8 i16 i32 i64 f32 f64)
 219
 220     macro_rules! totaleq_impl(
 221         ($($t:ty)*) => ($(
 222             impl TotalEq for $t {}
 223         )*)
 224     )
 225
 226     totaleq_impl!(() bool char uint u8 u16 u32 u64 int i8 i16 i32 i64)
 227
 228     macro_rules! ord_impl(
 229         ($($t:ty)*) => ($(
 230             impl Ord for $t {
 231                 #[inline]
 232                 fn lt(&self, other: &$t) -> bool { (*self) < (*other) }
 233                 #[inline]
 234                 fn le(&self, other: &$t) -> bool { (*self) <= (*other) }
 235                 #[inline]
 236                 fn ge(&self, other: &$t) -> bool { (*self) >= (*other) }
 237                 #[inline]
 238                 fn gt(&self, other: &$t) -> bool { (*self) > (*other) }
 239             }
 240         )*)
 241     )
 242
 243     impl Ord for () {
 244         #[inline]
 245         fn lt(&self, _other: &()) -> bool { false }
 246     }
 247
 248     impl Ord for bool {
 249         #[inline]
 250         fn lt(&self, other: &bool) -> bool {
 251             (*self as u8) < (*other as u8)
 252         }
 253     }
 254
 255     ord_impl!(char uint u8 u16 u32 u64 int i8 i16 i32 i64 f32 f64)
 256
 257     macro_rules! totalord_impl(
 258         ($($t:ty)*) => ($(
 259             impl TotalOrd for $t {
 260                 #[inline]
 261                 fn cmp(&self, other: &$t) -> Ordering {
 262                     if *self < *other { Less }
 263                     else if *self > *other { Greater }
 264                     else { Equal }
 265                 }
 266             }
 267         )*)
 268     )
 269
 270     impl TotalOrd for () {
 271         #[inline]
 272         fn cmp(&self, _other: &()) -> Ordering { Equal }
 273     }
 274
 275     impl TotalOrd for bool {
 276         #[inline]
 277         fn cmp(&self, other: &bool) -> Ordering {
 278             (*self as u8).cmp(&(*other as u8))
 279         }
 280     }
 281
 282     totalord_impl!(char uint u8 u16 u32 u64 int i8 i16 i32 i64)
 283
 284     // & pointers
 285     impl<'a, T: Eq> Eq for &'a T {
 286         #[inline]
 287         fn eq(&self, other: & &'a T) -> bool { *(*self) == *(*other) }
 288         #[inline]
 289         fn ne(&self, other: & &'a T) -> bool { *(*self) != *(*other) }
 290     }
 291     impl<'a, T: Ord> Ord for &'a T {
 292         #[inline]
 293         fn lt(&self, other: & &'a T) -> bool { *(*self) < *(*other) }
 294         #[inline]
 295         fn le(&self, other: & &'a T) -> bool { *(*self) <= *(*other) }
 296         #[inline]
 297         fn ge(&self, other: & &'a T) -> bool { *(*self) >= *(*other) }
 298         #[inline]
 299         fn gt(&self, other: & &'a T) -> bool { *(*self) > *(*other) }
 300     }
 301     impl<'a, T: TotalOrd> TotalOrd for &'a T {
 302         #[inline]
 303         fn cmp(&self, other: & &'a T) -> Ordering { (**self).cmp(*other) }
 304     }
 305     impl<'a, T: TotalEq> TotalEq for &'a T {}
 306
 307     // &mut pointers
 308     impl<'a, T: Eq> Eq for &'a mut T {
 309         #[inline]
 310         fn eq(&self, other: &&'a mut T) -> bool { **self == *(*other) }
 311         #[inline]
 312         fn ne(&self, other: &&'a mut T) -> bool { **self != *(*other) }
 313     }
 314     impl<'a, T: Ord> Ord for &'a mut T {
 315         #[inline]
 316         fn lt(&self, other: &&'a mut T) -> bool { **self < **other }
 317         #[inline]
 318         fn le(&self, other: &&'a mut T) -> bool { **self <= **other }
 319         #[inline]
 320         fn ge(&self, other: &&'a mut T) -> bool { **self >= **other }
 321         #[inline]
 322         fn gt(&self, other: &&'a mut T) -> bool { **self > **other }
 323     }
 324     impl<'a, T: TotalOrd> TotalOrd for &'a mut T {
 325         #[inline]
 326         fn cmp(&self, other: &&'a mut T) -> Ordering { (**self).cmp(*other) }
 327     }
 328     impl<'a, T: TotalEq> TotalEq for &'a mut T {}
 329
 330     // @ pointers
 331     impl<T:Eq> Eq for @T {
 332         #[inline]
 333         fn eq(&self, other: &@T) -> bool { *(*self) == *(*other) }
 334         #[inline]
 335         fn ne(&self, other: &@T) -> bool { *(*self) != *(*other) }
 336     }
 337     impl<T:Ord> Ord for @T {
 338         #[inline]
 339         fn lt(&self, other: &@T) -> bool { *(*self) < *(*other) }
 340         #[inline]
 341         fn le(&self, other: &@T) -> bool { *(*self) <= *(*other) }
 342         #[inline]
 343         fn ge(&self, other: &@T) -> bool { *(*self) >= *(*other) }
 344         #[inline]
 345         fn gt(&self, other: &@T) -> bool { *(*self) > *(*other) }
 346     }
 347     impl<T: TotalOrd> TotalOrd for @T {
 348         #[inline]
 349         fn cmp(&self, other: &@T) -> Ordering { (**self).cmp(*other) }
 350     }
 351     impl<T: TotalEq> TotalEq for @T {}
 352 }
 353
 354 #[cfg(test)]
 355 mod test {
 356     use super::lexical_ordering;
 357
 358     #[test]
 359     fn test_int_totalord() {
 360         assert_eq!(5u.cmp(&10), Less);
 361         assert_eq!(10u.cmp(&5), Greater);
 362         assert_eq!(5u.cmp(&5), Equal);
 363         assert_eq!((-5u).cmp(&12), Less);
 364         assert_eq!(12u.cmp(-5), Greater);
 365     }
 366
 367     #[test]
 368     fn test_mut_int_totalord() {
 369         assert_eq!((&mut 5u).cmp(&10), Less);
 370         assert_eq!((&mut 10u).cmp(&5), Greater);
 371         assert_eq!((&mut 5u).cmp(&5), Equal);
 372         assert_eq!((&mut -5u).cmp(&12), Less);
 373         assert_eq!((&mut 12u).cmp(-5), Greater);
 374     }
 375
 376     #[test]
 377     fn test_ordering_order() {
 378         assert!(Less < Equal);
 379         assert_eq!(Greater.cmp(&Less), Greater);
 380     }
 381
 382     #[test]
 383     fn test_lexical_ordering() {
 384         fn t(o1: Ordering, o2: Ordering, e: Ordering) {
 385             assert_eq!(lexical_ordering(o1, o2), e);
 386         }
 387
 388         let xs = [Less, Equal, Greater];
 389         for &o in xs.iter() {
 390             t(Less, o, Less);
 391             t(Equal, o, o);
 392             t(Greater, o, Greater);
 393          }
 394     }
 395
 396     #[test]
 397     fn test_user_defined_eq() {
 398         // Our type.
 399         struct SketchyNum {
 400             num : int
 401         }
 402
 403         // Our implementation of `Eq` to support `==` and `!=`.
 404         impl Eq for SketchyNum {
 405             // Our custom eq allows numbers which are near each other to be equal! :D
 406             fn eq(&self, other: &SketchyNum) -> bool {
 407                 (self.num - other.num).abs() < 5
 408             }
 409         }
 410
 411         // Now these binary operators will work when applied!
 412         assert!(SketchyNum {num: 37} == SketchyNum {num: 34});
 413         assert!(SketchyNum {num: 25} != SketchyNum {num: 57});
 414     }
 415 }