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(src: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}
182