vendor/num-integer/src/average.rs

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