float_ord/
lib.rs

1//! Order floating point numbers, into this ordering:
2//!
3//!    NaN | -Infinity | x < 0 | -0 | +0 | x > 0 | +Infinity | NaN
4
5#![no_std]
6
7use core::cmp::{Eq, Ord, Ordering, PartialEq, PartialOrd};
8use core::hash::{Hash, Hasher};
9use core::mem::transmute;
10
11/// A wrapper for floats, that implements total equality and ordering
12/// and hashing.
13#[derive(Clone, Copy, Debug)]
14#[repr(transparent)]
15pub struct FloatOrd<T>(pub T);
16
17macro_rules! float_ord_impl {
18    ($f:ident, $i:ident, $n:expr) => {
19        impl FloatOrd<$f> {
20            fn convert(self) -> $i {
21                let u = unsafe { transmute::<$f, $i>(self.0) };
22                let bit = 1 << ($n - 1);
23                if u & bit == 0 {
24                    u | bit
25                } else {
26                    !u
27                }
28            }
29        }
30        impl PartialEq for FloatOrd<$f> {
31            fn eq(&self, other: &Self) -> bool {
32                self.convert() == other.convert()
33            }
34        }
35        impl Eq for FloatOrd<$f> {}
36        impl PartialOrd for FloatOrd<$f> {
37            fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
38                self.convert().partial_cmp(&other.convert())
39            }
40        }
41        impl Ord for FloatOrd<$f> {
42            fn cmp(&self, other: &Self) -> Ordering {
43                self.convert().cmp(&other.convert())
44            }
45        }
46        impl Hash for FloatOrd<$f> {
47            fn hash<H: Hasher>(&self, state: &mut H) {
48                self.convert().hash(state);
49            }
50        }
51    }
52}
53
54float_ord_impl!(f32, u32, 32);
55float_ord_impl!(f64, u64, 64);
56
57/// Sort a slice of floats.
58///
59/// # Allocation behavior
60///
61/// This routine uses a quicksort implementation that does not heap allocate.
62///
63/// # Example
64///
65/// ```
66/// let mut v = [-5.0, 4.0, 1.0, -3.0, 2.0];
67///
68/// float_ord::sort(&mut v);
69/// assert!(v == [-5.0, -3.0, 1.0, 2.0, 4.0]);
70/// ```
71pub fn sort<T>(v: &mut [T]) where FloatOrd<T>: Ord {
72    let v_: &mut [FloatOrd<T>] = unsafe { transmute(v) };
73    v_.sort_unstable();
74}
75
76#[cfg(test)]
77mod tests {
78    extern crate std;
79    extern crate rand;
80
81    use self::rand::{Rng, thread_rng};
82    use self::std::iter;
83    use self::std::prelude::v1::*;
84    use self::std::collections::hash_map::DefaultHasher;
85    use self::std::hash::{Hash, Hasher};
86    use super::FloatOrd;
87
88    #[test]
89    fn test_ord() {
90        assert!(FloatOrd(1.0f64) < FloatOrd(2.0f64));
91        assert!(FloatOrd(2.0f32) > FloatOrd(1.0f32));
92        assert!(FloatOrd(1.0f64) == FloatOrd(1.0f64));
93        assert!(FloatOrd(1.0f32) == FloatOrd(1.0f32));
94        assert!(FloatOrd(0.0f64) > FloatOrd(-0.0f64));
95        assert!(FloatOrd(0.0f32) > FloatOrd(-0.0f32));
96        assert!(FloatOrd(::core::f64::NAN) == FloatOrd(::core::f64::NAN));
97        assert!(FloatOrd(::core::f32::NAN) == FloatOrd(::core::f32::NAN));
98        assert!(FloatOrd(-::core::f64::NAN) < FloatOrd(::core::f64::NAN));
99        assert!(FloatOrd(-::core::f32::NAN) < FloatOrd(::core::f32::NAN));
100        assert!(FloatOrd(-::core::f64::INFINITY) < FloatOrd(::core::f64::INFINITY));
101        assert!(FloatOrd(-::core::f32::INFINITY) < FloatOrd(::core::f32::INFINITY));
102        assert!(FloatOrd(::core::f64::INFINITY) < FloatOrd(::core::f64::NAN));
103        assert!(FloatOrd(::core::f32::INFINITY) < FloatOrd(::core::f32::NAN));
104        assert!(FloatOrd(-::core::f64::NAN) < FloatOrd(::core::f64::INFINITY));
105        assert!(FloatOrd(-::core::f32::NAN) < FloatOrd(::core::f32::INFINITY));
106    }
107
108    #[test]
109    fn test_ord_numbers() {
110        let mut rng = thread_rng();
111        for n in 0..16 {
112            for l in 0..16 {
113                let v = iter::repeat(()).map(|()| rng.gen())
114                    .map(|x: f64| x % (1 << l) as i64 as f64)
115                    .take(1 << n)
116                    .collect::<Vec<_>>();
117                assert!(v.windows(2).all(|w| (w[0] <= w[1]) == (FloatOrd(w[0]) <= FloatOrd(w[1]))));
118            }
119        }
120    }
121
122    fn hash<F: Hash>(f: F) -> u64 {
123        let mut hasher = DefaultHasher::new();
124        f.hash(&mut hasher);
125        hasher.finish()
126    }
127
128    #[test]
129    fn test_hash() {
130        assert_ne!(hash(FloatOrd(0.0f64)), hash(FloatOrd(-0.0f64)));
131        assert_ne!(hash(FloatOrd(0.0f32)), hash(FloatOrd(-0.0f32)));
132        assert_eq!(hash(FloatOrd(-0.0f64)), hash(FloatOrd(-0.0f64)));
133        assert_eq!(hash(FloatOrd(0.0f32)), hash(FloatOrd(0.0f32)));
134        assert_ne!(hash(FloatOrd(::core::f64::NAN)), hash(FloatOrd(-::core::f64::NAN)));
135        assert_ne!(hash(FloatOrd(::core::f32::NAN)), hash(FloatOrd(-::core::f32::NAN)));
136        assert_eq!(hash(FloatOrd(::core::f64::NAN)), hash(FloatOrd(::core::f64::NAN)));
137        assert_eq!(hash(FloatOrd(-::core::f32::NAN)), hash(FloatOrd(-::core::f32::NAN)));
138    }
139
140    #[test]
141    fn test_sort_numbers() {
142        let mut rng = thread_rng();
143        for n in 0..16 {
144            for l in 0..16 {
145                let mut v = iter::repeat(()).map(|()| rng.gen())
146                    .map(|x: f64| x % (1 << l) as i64 as f64)
147                    .take(1 << n)
148                    .collect::<Vec<_>>();
149                let mut v1 = v.clone();
150
151                super::sort(&mut v);
152                assert!(v.windows(2).all(|w: &[f64]| w[0] <= w[1]));
153
154                v1.sort_by(|a, b| a.partial_cmp(b).unwrap());
155                assert!(v1.windows(2).all(|w| w[0] <= w[1]));
156
157                v1.sort_by(|a, b| b.partial_cmp(a).unwrap());
158                assert!(v1.windows(2).all(|w| w[0] >= w[1]));
159            }
160        }
161
162        let mut v = [5.0];
163        super::sort(&mut v);
164        assert!(v == [5.0]);
165    }
166
167    #[test]
168    fn test_sort_nan() {
169        let nan = ::core::f64::NAN;
170        let mut v = [-1.0, 5.0, 0.0, -0.0, nan, 1.5, nan, 3.7];
171        super::sort(&mut v);
172        assert!(v[0] == -1.0);
173        assert!(v[1] == 0.0 && v[1].is_sign_negative());
174        assert!(v[2] == 0.0 && !v[2].is_sign_negative());
175        assert!(v[3] == 1.5);
176        assert!(v[4] == 3.7);
177        assert!(v[5] == 5.0);
178        assert!(v[6].is_nan());
179        assert!(v[7].is_nan());
180    }
181}
float_ord/lib.rs

float_ord/
lib.rs
