1  //! Some numerical utilities.
  2  
  3  use std::hash::Hash;
  4  
  5  /// A wrapper for `f64` that implements `Ord`.
  6  ///
  7  /// Unlike the more principled wrappers in the `ordered_float` crate, this one
  8  /// just breaks the `Ord` rules when comparing NaNs -- it doesn't order them,
  9  /// nor does it panic or guard against them on construction. This makes things
 10  /// substantially faster: I measured a 20% improvement to some benchmarks by
 11  /// switching from `OrderedFloat` to `CheapOrderedFloat`.
 12  ///
 13  /// Ignoring NaNs should be ok: we check input for NaNs and infinities, and
 14  /// then we make some effort not to introduce them.
 15  #[cfg_attr(test, derive(serde::Serialize, serde::Deserialize))]
 16  #[cfg_attr(test, serde(transparent))]
 17  #[derive(Debug, Clone, Copy, PartialEq)]
 18  pub struct CheapOrderedFloat(f64);
 19  
 20  impl std::ops::Add<CheapOrderedFloat> for CheapOrderedFloat {
 21      type Output = Self;
 22  
 23      fn add(self, rhs: CheapOrderedFloat) -> Self::Output {
 24          CheapOrderedFloat(self.0 + rhs.0)
 25      }
 26  }
 27  
 28  impl<'a> std::ops::Add<&'a CheapOrderedFloat> for CheapOrderedFloat {
 29      type Output = Self;
 30  
 31      fn add(self, rhs: &'a CheapOrderedFloat) -> Self::Output {
 32          CheapOrderedFloat(self.0 + rhs.0)
 33      }
 34  }
 35  
 36  impl std::ops::Sub<CheapOrderedFloat> for CheapOrderedFloat {
 37      type Output = Self;
 38  
 39      fn sub(self, rhs: CheapOrderedFloat) -> Self::Output {
 40          CheapOrderedFloat(self.0 - rhs.0)
 41      }
 42  }
 43  
 44  impl<'a> std::ops::Sub<&'a CheapOrderedFloat> for CheapOrderedFloat {
 45      type Output = Self;
 46  
 47      fn sub(self, rhs: &'a CheapOrderedFloat) -> Self::Output {
 48          CheapOrderedFloat(self.0 - rhs.0)
 49      }
 50  }
 51  
 52  impl std::ops::Mul<CheapOrderedFloat> for CheapOrderedFloat {
 53      type Output = Self;
 54  
 55      fn mul(self, rhs: CheapOrderedFloat) -> Self::Output {
 56          CheapOrderedFloat(self.0 * rhs.0)
 57      }
 58  }
 59  
 60  impl<'a> std::ops::Mul<&'a CheapOrderedFloat> for CheapOrderedFloat {
 61      type Output = Self;
 62  
 63      fn mul(self, rhs: &'a CheapOrderedFloat) -> Self::Output {
 64          CheapOrderedFloat(self.0 * rhs.0)
 65      }
 66  }
 67  
 68  impl std::ops::Div<CheapOrderedFloat> for CheapOrderedFloat {
 69      type Output = Self;
 70  
 71      fn div(self, rhs: CheapOrderedFloat) -> Self::Output {
 72          CheapOrderedFloat(self.0 / rhs.0)
 73      }
 74  }
 75  
 76  impl<'a> std::ops::Div<&'a CheapOrderedFloat> for CheapOrderedFloat {
 77      type Output = Self;
 78  
 79      fn div(self, rhs: &'a CheapOrderedFloat) -> Self::Output {
 80          CheapOrderedFloat(self.0 / rhs.0)
 81      }
 82  }
 83  
 84  impl std::ops::Neg for CheapOrderedFloat {
 85      type Output = Self;
 86  
 87      fn neg(self) -> Self::Output {
 88          CheapOrderedFloat(-self.0)
 89      }
 90  }
 91  
 92  impl Hash for CheapOrderedFloat {
 93      fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
 94          self.0.to_bits().hash(state)
 95      }
 96  }
 97  
 98  impl CheapOrderedFloat {
 99      /// Retrieve the inner `f64`.
100      pub fn into_inner(self) -> f64 {
101          self.0
102      }
103  }
104  
105  // Now comes the fishy stuff.
106  impl Eq for CheapOrderedFloat {}
107  
108  impl PartialOrd for CheapOrderedFloat {
109      #[inline(always)]
110      fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
111          Some(self.cmp(other))
112      }
113  }
114  
115  impl Ord for CheapOrderedFloat {
116      #[inline(always)]
117      fn cmp(&self, other: &Self) -> std::cmp::Ordering {
118          if self.0 < other.0 {
119              std::cmp::Ordering::Less
120          } else if self.0 > other.0 {
121              std::cmp::Ordering::Greater
122          } else {
123              std::cmp::Ordering::Equal
124          }
125      }
126  }
127  
128  impl From<f64> for CheapOrderedFloat {
129      fn from(value: f64) -> Self {
130          CheapOrderedFloat(value)
131      }
132  }
133  
134  #[cfg(test)]
135  pub(crate) mod tests {
136      use proptest::prelude::*;
137  
138      // Kind of like Arbitrary, but
139      // - it's a local trait, so we can impl it for whatever we want, and
140      // - it only returns "reasonable" values.
141      pub trait Reasonable {
142          type Strategy: Strategy<Value = Self>;
143          fn reasonable() -> Self::Strategy;
144      }
145  
146      impl<S: Reasonable, T: Reasonable> Reasonable for (S, T) {
147          type Strategy = (S::Strategy, T::Strategy);
148  
149          fn reasonable() -> Self::Strategy {
150              (S::reasonable(), T::reasonable())
151          }
152      }
153  
154      impl Reasonable for f64 {
155          type Strategy = BoxedStrategy<f64>;
156  
157          fn reasonable() -> Self::Strategy {
158              (-1e6..1e6).boxed()
159          }
160      }
161  }