How to sort a Vec of floats?

help
3

For completeness, here's an implementation of the total ordering predicate from IEEE 754-2008. I haven't tested it with varying NaN payloads because I've stopped caring at this point.

#![allow(non_snake_case)]

macro_rules! assert_really_eq {
    ($lhs:expr, $rhs:expr) => {
        {
            let left = $lhs;
            let right = $rhs;
            if !left.really_eq(&right) {
                panic!("assertion failed: `(left === right)` (left: `{:?}`, right: `{:?}`)", left, right);
            }
        }
    };
}

fn main() {
    {
        let mut v: [f32; 5] = [5.0, 4.0, 1.0, 3.0, 2.0];
        v.sort_by(|a, b| a.partial_cmp(b).unwrap());
        assert!(v == [1.0, 2.0, 3.0, 4.0, 5.0]);
    }

    {
        use std::f32::{NAN, INFINITY, NEG_INFINITY};
        let NNAN = unsafe {
            use std::mem::transmute;
            transmute::<_, f32>(transmute::<_, u32>(NAN) | 0x8000_0000)
        };

        let mut v: [f32; 7] = [5.0, NAN, 4.0, 1.0, NNAN, 3.0, 2.0];
        v.sort_by(Ieee754::total_cmp);
        assert_really_eq!(v, [NNAN, 1.0, 2.0, 3.0, 4.0, 5.0, NAN]);

        let mut v: [f32; 7] = [5.0, NAN, INFINITY, 1.0, NNAN, -3.0, NEG_INFINITY];
        v.sort_by(Ieee754::total_cmp);
        assert_really_eq!(v, [NNAN, NEG_INFINITY, -3.0, 1.0, 5.0, INFINITY, NAN]);

        let mut v: [f32; 4] = [-1.0, 1.0, 0.0, -0.0];
        v.sort_by(Ieee754::total_cmp);
        assert_really_eq!(v, [-1.0, -0.0, 0.0, 1.0]);
    }
}

use std::cmp::Ordering;

pub trait Ieee754 {
    type Exponent;
    type NanPayload;

    fn exponent(self) -> Self::Exponent;
    fn is_really_neg(self) -> bool;
    fn is_signalling_nan(self) -> bool;
    fn nan_payload(self) -> Self::NanPayload;
    fn total_ord(&self, rhs: &Self) -> bool;
    fn total_cmp(&self, rhs: &Self) -> Ordering;
}

impl Ieee754 for f32 {
    type Exponent = i16;
    type NanPayload = u32;

    #[inline]
    fn exponent(self) -> Self::Exponent {
        use std::mem::transmute;
        unsafe {
            (((transmute::<_, u32>(self) >> 23) & 0xff) - 127) as i16
        }
    }
    
    #[inline]
    fn is_really_neg(self) -> bool {
        use std::mem::transmute;
        unsafe {
            (transmute::<_, u32>(self) & 0x8000_0000) != 0
        }
    }
    
    #[inline]
    fn is_signalling_nan(self) -> bool {
        use std::mem::transmute;
        unsafe {
            ((transmute::<_, u32>(self) >> 22) & 1) != 0
        }
    }
    
    #[inline]
    fn nan_payload(self) -> Self::NanPayload {
        use std::mem::transmute;
        unsafe {
            transmute::<_, u32>(self) & 0x1f_ffff
        }
    }

    #[inline]
    fn total_ord(&self, rhs: &Self) -> bool {
        // IEEE 754-2008 ยง5.10.
        let lhs = *self;
        let rhs = *rhs;

        if lhs < rhs { return true; }
        if lhs > rhs { return false; }
        if lhs == rhs {
            if lhs.really_eq(&-0.0) && rhs.really_eq(&0.0) { return true; }
            if lhs.really_eq(&0.0) && rhs.really_eq(&-0.0) { return false; }
            let lhs_exp = lhs.exponent();
            let rhs_exp = rhs.exponent();
            if lhs.is_sign_negative() && rhs.is_sign_negative() {
                return lhs_exp >= rhs_exp;
            }
            return lhs_exp <= rhs_exp;
        }

        // x and or y is/are unordered
        match (lhs.is_nan(), lhs.is_really_neg(), rhs.is_nan(), rhs.is_really_neg()) {
            (true, neg,     false, _)       => return neg,
            (false, _,      true, neg)      => return !neg,
            (true, true,    true, false)    => return true,
            (true, false,   true, true)     => return false,
            (true, _,       true, _)        => (),
            _ => unreachable!()
        }

        let lhs_payload = lhs.nan_payload();
        let rhs_payload = rhs.nan_payload();
        let lhs_sig = lhs.is_signalling_nan();
        let rhs_sig = rhs.is_signalling_nan();
        
        match (!lhs.is_really_neg(), lhs_sig, rhs_sig, lhs_payload < rhs_payload) {
            (true, true, false, _) => true,
            (true, false, true, _) => false,
            (true, _, _, c) => c,
            (false, true, false, _) => false,
            (false, false, true, _) => true,
            (false, _, _, c) => !c
        }
    }

    fn total_cmp(&self, rhs: &Self) -> Ordering {
        match (self.total_ord(rhs), rhs.total_ord(self)) {
            (true, false) => Ordering::Less,
            (false, true) => Ordering::Greater,
            (true, true) => Ordering::Equal,
            _ => panic!("could not order {:?}, {:?}", self, rhs)
        }
    }
}

trait ReallyEq {
    fn really_eq(&self, rhs: &Self) -> bool;
}

impl ReallyEq for f32 {
    fn really_eq(&self, rhs: &Self) -> bool {
        use std::mem::transmute;
        unsafe {
            transmute::<_, u32>(*self) == transmute::<_, u32>(*rhs)
        }
    }
}

impl<T> ReallyEq for [T]
where T: ReallyEq {
    fn really_eq(&self, rhs: &Self) -> bool {
        if self.len() != rhs.len() { return false; }
        self.iter().zip(rhs.iter()).all(|(a, b)| a.really_eq(b))
    }
}

impl ReallyEq for [f32; 7] {
    fn really_eq(&self, rhs: &Self) -> bool {
        <[f32] as ReallyEq>::really_eq(self, rhs)
    }
}
6 Likes