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)
}