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: Eq {
  46     /// This method must return the same value as `eq`. It exists to prevent
  47     /// deriving `TotalEq` from fields not implementing the `TotalEq` trait.
  48     fn equals(&self, other: &Self) -> bool {
  49         self.eq(other)
  50     }
  51 }
  52
  53 macro_rules! totaleq_impl(
  54     ($t:ty) => {
  55         impl TotalEq for $t {
  56             #[inline]
  57             fn equals(&self, other: &$t) -> bool { *self == *other }
  58         }
  59     }
  60 )
  61
  62 totaleq_impl!(bool)
  63
  64 totaleq_impl!(u8)
  65 totaleq_impl!(u16)
  66 totaleq_impl!(u32)
  67 totaleq_impl!(u64)
  68
  69 totaleq_impl!(i8)
  70 totaleq_impl!(i16)
  71 totaleq_impl!(i32)
  72 totaleq_impl!(i64)
  73
  74 totaleq_impl!(int)
  75 totaleq_impl!(uint)
  76
  77 totaleq_impl!(char)
  78
  79 #[deriving(Clone, Eq, Show)]
  80 pub enum Ordering { Less = -1, Equal = 0, Greater = 1 }
  81
  82 /// Trait for types that form a total order
  83 pub trait TotalOrd: TotalEq + Ord {
  84     fn cmp(&self, other: &Self) -> Ordering;
  85 }
  86
  87 impl TotalEq for Ordering {
  88     #[inline]
  89     fn equals(&self, other: &Ordering) -> bool {
  90         *self == *other
  91     }
  92 }
  93 impl TotalOrd for Ordering {
  94     #[inline]
  95     fn cmp(&self, other: &Ordering) -> Ordering {
  96         (*self as int).cmp(&(*other as int))
  97     }
  98 }
  99
 100 impl Ord for Ordering {
 101     #[inline]
 102     fn lt(&self, other: &Ordering) -> bool { (*self as int) < (*other as int) }
 103 }
 104
 105 macro_rules! totalord_impl(
 106     ($t:ty) => {
 107         impl TotalOrd for $t {
 108             #[inline]
 109             fn cmp(&self, other: &$t) -> Ordering {
 110                 if *self < *other { Less }
 111                 else if *self > *other { Greater }
 112                 else { Equal }
 113             }
 114         }
 115     }
 116 )
 117
 118 totalord_impl!(u8)
 119 totalord_impl!(u16)
 120 totalord_impl!(u32)
 121 totalord_impl!(u64)
 122
 123 totalord_impl!(i8)
 124 totalord_impl!(i16)
 125 totalord_impl!(i32)
 126 totalord_impl!(i64)
 127
 128 totalord_impl!(int)
 129 totalord_impl!(uint)
 130
 131 totalord_impl!(char)
 132
 133 /// Compares (a1, b1) against (a2, b2), where the a values are more significant.
 134 pub fn cmp2<A:TotalOrd,B:TotalOrd>(
 135     a1: &A, b1: &B,
 136     a2: &A, b2: &B) -> Ordering
 137 {
 138     match a1.cmp(a2) {
 139         Less => Less,
 140         Greater => Greater,
 141         Equal => b1.cmp(b2)
 142     }
 143 }
 144
 145 /**
 146 Return `o1` if it is not `Equal`, otherwise `o2`. Simulates the
 147 lexical ordering on a type `(int, int)`.
 148 */
 149 #[inline]
 150 pub fn lexical_ordering(o1: Ordering, o2: Ordering) -> Ordering {
 151     match o1 {
 152         Equal => o2,
 153         _ => o1
 154     }
 155 }
 156
 157 /**
 158 * Trait for values that can be compared for a sort-order.
 159 *
 160 * Ord only requires implementation of the `lt` method,
 161 * with the others generated from default implementations.
 162 *
 163 * However it remains possible to implement the others separately,
 164 * for compatibility with floating-point NaN semantics
 165 * (cf. IEEE 754-2008 section 5.11).
 166 */
 167 #[lang="ord"]
 168 pub trait Ord: Eq {
 169     fn lt(&self, other: &Self) -> bool;
 170     #[inline]
 171     fn le(&self, other: &Self) -> bool { !other.lt(self) }
 172     #[inline]
 173     fn gt(&self, other: &Self) -> bool {  other.lt(self) }
 174     #[inline]
 175     fn ge(&self, other: &Self) -> bool { !self.lt(other) }
 176 }
 177
 178 /// The equivalence relation. Two values may be equivalent even if they are
 179 /// of different types. The most common use case for this relation is
 180 /// container types; e.g. it is often desirable to be able to use `&str`
 181 /// values to look up entries in a container with `~str` keys.
 182 pub trait Equiv<T> {
 183     fn equiv(&self, other: &T) -> bool;
 184 }
 185
 186 #[inline]
 187 pub fn min<T:Ord>(v1: T, v2: T) -> T {
 188     if v1 < v2 { v1 } else { v2 }
 189 }
 190
 191 #[inline]
 192 pub fn max<T:Ord>(v1: T, v2: T) -> T {
 193     if v1 > v2 { v1 } else { v2 }
 194 }
 195
 196 #[cfg(test)]
 197 mod test {
 198     use super::lexical_ordering;
 199
 200     #[test]
 201     fn test_int_totalord() {
 202         assert_eq!(5.cmp(&10), Less);
 203         assert_eq!(10.cmp(&5), Greater);
 204         assert_eq!(5.cmp(&5), Equal);
 205         assert_eq!((-5).cmp(&12), Less);
 206         assert_eq!(12.cmp(-5), Greater);
 207     }
 208
 209     #[test]
 210     fn test_cmp2() {
 211         assert_eq!(cmp2(1, 2, 3, 4), Less);
 212         assert_eq!(cmp2(3, 2, 3, 4), Less);
 213         assert_eq!(cmp2(5, 2, 3, 4), Greater);
 214         assert_eq!(cmp2(5, 5, 5, 4), Greater);
 215     }
 216
 217     #[test]
 218     fn test_int_totaleq() {
 219         assert!(5.equals(&5));
 220         assert!(!2.equals(&17));
 221     }
 222
 223     #[test]
 224     fn test_ordering_order() {
 225         assert!(Less < Equal);
 226         assert_eq!(Greater.cmp(&Less), Greater);
 227     }
 228
 229     #[test]
 230     fn test_lexical_ordering() {
 231         fn t(o1: Ordering, o2: Ordering, e: Ordering) {
 232             assert_eq!(lexical_ordering(o1, o2), e);
 233         }
 234
 235         let xs = [Less, Equal, Greater];
 236         for &o in xs.iter() {
 237             t(Less, o, Less);
 238             t(Equal, o, o);
 239             t(Greater, o, Greater);
 240          }
 241     }
 242 }