substrate_median/
average.rs

1use core::cmp::Ord;
2
3/// A trait to take the average of two values
4pub trait Average {
5  /// Calculate the average of two values.
6  fn average(value: Self, other: Self) -> Self;
7}
8
9macro_rules! impl_prim_uint {
10  ($type: ident) => {
11    impl Average for $type {
12      /// This rounds as integer division does: by flooring the result.
13      fn average(value: Self, other: Self) -> Self {
14        /*
15          Since `value + other` may overflow, without promotion to a wider integer, we perform the
16          halving as the first operation. Then we add back the truncated bit as necessary. This
17          methodology doesn't overflow and doesn't require the existence of a wider integer type.
18        */
19        (value / 2) + (other / 2) + (value & other & 1)
20      }
21    }
22  };
23}
24impl_prim_uint!(u8);
25impl_prim_uint!(u16);
26impl_prim_uint!(u32);
27impl_prim_uint!(u64);
28impl_prim_uint!(u128);
29
30#[test]
31fn average() {
32  use rand_core::{RngCore, OsRng};
33
34  // Basic sanity checks
35  {
36    assert_eq!(u64::average(0, 0), 0);
37    assert_eq!(u64::average(0, 1), 0);
38    assert_eq!(u64::average(0, 2), 1);
39    assert_eq!(u64::average(u64::MAX, u64::MAX), u64::MAX);
40    assert_eq!(u64::average(u64::MAX - 1, u64::MAX), u64::MAX - 1);
41    assert_eq!(u64::average(u64::MAX - 2, u64::MAX), u64::MAX - 1);
42    assert_eq!(u64::average(u64::MAX - 1, u64::MAX - 1), u64::MAX - 1);
43  }
44
45  // Fuzz test the function
46  for _ in 0 .. 100 {
47    let a = OsRng.next_u64();
48    let b = OsRng.next_u64();
49    assert_eq!(u64::average(a, b), u64::try_from((u128::from(a) + u128::from(b)) / 2).unwrap());
50  }
51}
substrate_median/average.rs

substrate_median/
average.rs
