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