src/libstd/cmp.rs

   1 // Copyright 2012-2013 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 /*!
  12
  13 The `Ord` and `Eq` comparison traits
  14
  15 This module contains the definition of both `Ord` and `Eq` which define
  16 the common interfaces for doing comparison. Both are language items
  17 that the compiler uses to implement the comparison operators. Rust code
  18 may implement `Ord` to overload the `<`, `<=`, `>`, and `>=` operators,
  19 and `Eq` to overload the `==` and `!=` operators.
  20
  21 */
  22
  23 #[allow(missing_doc)];
  24
  25 /**
  26 * Trait for values that can be compared for equality and inequality.
  27 *
  28 * This trait allows partial equality, where types can be unordered instead of strictly equal or
  29 * unequal. For example, with the built-in floating-point types `a == b` and `a != b` will both
  30 * evaluate to false if either `a` or `b` is NaN (cf. IEEE 754-2008 section 5.11).
  31 *
  32 * Eq only requires the `eq` method to be implemented; `ne` is its negation by default.
  33 *
  34 * Eventually, this will be implemented by default for types that implement `TotalEq`.
  35 */
  36 #[lang="eq"]
  37 pub trait Eq {
  38     fn eq(&self, other: &Self) -> bool;
  39
  40     #[inline]
  41     fn ne(&self, other: &Self) -> bool { !self.eq(other) }
  42 }
  43
  44 /// Trait for equality comparisons where `a == b` and `a != b` are strict inverses.
  45 pub trait TotalEq {
  46     fn equals(&self, other: &Self) -> bool;
  47 }
  48
  49 macro_rules! totaleq_impl(
  50     ($t:ty) => {
  51         impl TotalEq for $t {
  52             #[inline]
  53             fn equals(&self, other: &$t) -> bool { *self == *other }
  54         }
  55     }
  56 )
  57
  58 totaleq_impl!(bool)
  59
  60 totaleq_impl!(u8)
  61 totaleq_impl!(u16)
  62 totaleq_impl!(u32)
  63 totaleq_impl!(u64)
  64
  65 totaleq_impl!(i8)
  66 totaleq_impl!(i16)
  67 totaleq_impl!(i32)
  68 totaleq_impl!(i64)
  69
  70 totaleq_impl!(int)
  71 totaleq_impl!(uint)
  72
  73 totaleq_impl!(char)
  74
  75 /// Trait for testing approximate equality
  76 pub trait ApproxEq<Eps> {
  77     fn approx_epsilon() -> Eps;
  78     fn approx_eq(&self, other: &Self) -> bool;
  79     fn approx_eq_eps(&self, other: &Self, approx_epsilon: &Eps) -> bool;
  80 }
  81
  82 #[deriving(Clone, Eq)]
  83 pub enum Ordering { Less = -1, Equal = 0, Greater = 1 }
  84
  85 /// Trait for types that form a total order
  86 pub trait TotalOrd: TotalEq {
  87     fn cmp(&self, other: &Self) -> Ordering;
  88 }
  89
  90 impl TotalEq for Ordering {
  91     #[inline]
  92     fn equals(&self, other: &Ordering) -> bool {
  93         *self == *other
  94     }
  95 }
  96 impl TotalOrd for Ordering {
  97     #[inline]
  98     fn cmp(&self, other: &Ordering) -> Ordering {
  99         (*self as int).cmp(&(*other as int))
 100     }
 101 }
 102
 103 impl Ord for Ordering {
 104     #[inline]
 105     fn lt(&self, other: &Ordering) -> bool { (*self as int) < (*other as int) }
 106 }
 107
 108 macro_rules! totalord_impl(
 109     ($t:ty) => {
 110         impl TotalOrd for $t {
 111             #[inline]
 112             fn cmp(&self, other: &$t) -> Ordering {
 113                 if *self < *other { Less }
 114                 else if *self > *other { Greater }
 115                 else { Equal }
 116             }
 117         }
 118     }
 119 )
 120
 121 totalord_impl!(u8)
 122 totalord_impl!(u16)
 123 totalord_impl!(u32)
 124 totalord_impl!(u64)
 125
 126 totalord_impl!(i8)
 127 totalord_impl!(i16)
 128 totalord_impl!(i32)
 129 totalord_impl!(i64)
 130
 131 totalord_impl!(int)
 132 totalord_impl!(uint)
 133
 134 totalord_impl!(char)
 135
 136 /// Compares (a1, b1) against (a2, b2), where the a values are more significant.
 137 pub fn cmp2<A:TotalOrd,B:TotalOrd>(
 138     a1: &A, b1: &B,
 139     a2: &A, b2: &B) -> Ordering
 140 {
 141     match a1.cmp(a2) {
 142         Less => Less,
 143         Greater => Greater,
 144         Equal => b1.cmp(b2)
 145     }
 146 }
 147
 148 /**
 149 Return `o1` if it is not `Equal`, otherwise `o2`. Simulates the
 150 lexical ordering on a type `(int, int)`.
 151 */
 152 #[inline]
 153 pub fn lexical_ordering(o1: Ordering, o2: Ordering) -> Ordering {
 154     match o1 {
 155         Equal => o2,
 156         _ => o1
 157     }
 158 }
 159
 160 /**
 161 * Trait for values that can be compared for a sort-order.
 162 *
 163 * Ord only requires implementation of the `lt` method,
 164 * with the others generated from default implementations.
 165 *
 166 * However it remains possible to implement the others separately,
 167 * for compatibility with floating-point NaN semantics
 168 * (cf. IEEE 754-2008 section 5.11).
 169 */
 170 #[lang="ord"]
 171 pub trait Ord {
 172     fn lt(&self, other: &Self) -> bool;
 173     #[inline]
 174     fn le(&self, other: &Self) -> bool { !other.lt(self) }
 175     #[inline]
 176     fn gt(&self, other: &Self) -> bool {  other.lt(self) }
 177     #[inline]
 178     fn ge(&self, other: &Self) -> bool { !self.lt(other) }
 179 }
 180
 181 /// The equivalence relation. Two values may be equivalent even if they are
 182 /// of different types. The most common use case for this relation is
 183 /// container types; e.g. it is often desirable to be able to use `&str`
 184 /// values to look up entries in a container with `~str` keys.
 185 pub trait Equiv<T> {
 186     fn equiv(&self, other: &T) -> bool;
 187 }
 188
 189 #[inline]
 190 pub fn min<T:Ord>(v1: T, v2: T) -> T {
 191     if v1 < v2 { v1 } else { v2 }
 192 }
 193
 194 #[inline]
 195 pub fn max<T:Ord>(v1: T, v2: T) -> T {
 196     if v1 > v2 { v1 } else { v2 }
 197 }
 198
 199 #[cfg(test)]
 200 mod test {
 201     use super::lexical_ordering;
 202
 203     #[test]
 204     fn test_int_totalord() {
 205         assert_eq!(5.cmp(&10), Less);
 206         assert_eq!(10.cmp(&5), Greater);
 207         assert_eq!(5.cmp(&5), Equal);
 208         assert_eq!((-5).cmp(&12), Less);
 209         assert_eq!(12.cmp(-5), Greater);
 210     }
 211
 212     #[test]
 213     fn test_cmp2() {
 214         assert_eq!(cmp2(1, 2, 3, 4), Less);
 215         assert_eq!(cmp2(3, 2, 3, 4), Less);
 216         assert_eq!(cmp2(5, 2, 3, 4), Greater);
 217         assert_eq!(cmp2(5, 5, 5, 4), Greater);
 218     }
 219
 220     #[test]
 221     fn test_int_totaleq() {
 222         assert!(5.equals(&5));
 223         assert!(!2.equals(&17));
 224     }
 225
 226     #[test]
 227     fn test_ordering_order() {
 228         assert!(Less < Equal);
 229         assert_eq!(Greater.cmp(&Less), Greater);
 230     }
 231
 232     #[test]
 233     fn test_lexical_ordering() {
 234         fn t(o1: Ordering, o2: Ordering, e: Ordering) {
 235             assert_eq!(lexical_ordering(o1, o2), e);
 236         }
 237
 238         let xs = [Less, Equal, Greater];
 239         for &o in xs.iter() {
 240             t(Less, o, Less);
 241             t(Equal, o, o);
 242             t(Greater, o, Greater);
 243          }
 244     }
 245 }