1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78
use core::ops::{BitAnd, BitOr, BitXor, Shr};
use Integer;
/// Provides methods to compute the average of two integers, without overflows.
pub trait Average: Integer {
/// Returns the ceiling value of the average of `self` and `other`.
/// -- `⌈(self + other)/2⌉`
///
/// # Examples
///
/// ```
/// use num_integer::Average;
///
/// assert_eq!(( 3).average_ceil(&10), 7);
/// assert_eq!((-2).average_ceil(&-5), -3);
/// assert_eq!(( 4).average_ceil(& 4), 4);
///
/// assert_eq!(u8::max_value().average_ceil(&2), 129);
/// assert_eq!(i8::min_value().average_ceil(&-1), -64);
/// assert_eq!(i8::min_value().average_ceil(&i8::max_value()), 0);
/// ```
///
fn average_ceil(&self, other: &Self) -> Self;
/// Returns the floor value of the average of `self` and `other`.
/// -- `⌊(self + other)/2⌋`
///
/// # Examples
///
/// ```
/// use num_integer::Average;
///
/// assert_eq!(( 3).average_floor(&10), 6);
/// assert_eq!((-2).average_floor(&-5), -4);
/// assert_eq!(( 4).average_floor(& 4), 4);
///
/// assert_eq!(u8::max_value().average_floor(&2), 128);
/// assert_eq!(i8::min_value().average_floor(&-1), -65);
/// assert_eq!(i8::min_value().average_floor(&i8::max_value()), -1);
/// ```
///
fn average_floor(&self, other: &Self) -> Self;
}
impl<I> Average for I
where
I: Integer + Shr<usize, Output = I>,
for<'a, 'b> &'a I:
BitAnd<&'b I, Output = I> + BitOr<&'b I, Output = I> + BitXor<&'b I, Output = I>,
{
// The Henry Gordon Dietz implementation as shown in the Hacker's Delight,
// see http://aggregate.org/MAGIC/#Average%20of%20Integers
/// Returns the floor value of the average of `self` and `other`.
#[inline]
fn average_floor(&self, other: &I) -> I {
(self & other) + ((self ^ other) >> 1)
}
/// Returns the ceil value of the average of `self` and `other`.
#[inline]
fn average_ceil(&self, other: &I) -> I {
(self | other) - ((self ^ other) >> 1)
}
}
/// Returns the floor value of the average of `x` and `y` --
/// see [Average::average_floor](trait.Average.html#tymethod.average_floor).
#[inline]
pub fn average_floor<T: Average>(x: T, y: T) -> T {
x.average_floor(&y)
}
/// Returns the ceiling value of the average of `x` and `y` --
/// see [Average::average_ceil](trait.Average.html#tymethod.average_ceil).
#[inline]
pub fn average_ceil<T: Average>(x: T, y: T) -> T {
x.average_ceil(&y)
}