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

#![feature(i128_type)]

pub trait UnsignedInt: PartialEq + PartialOrd + Eq + Ord + Copy {
    const WIDTH: usize;

    const MIN_BOUND: Self;
    const MAX_BOUND: Self;

    fn count_ones(self) -> u32;
    fn count_zeros(self) -> u32;

    fn succ(&self) -> Self;
    fn pred(&self) -> Self;
}

macro_rules! impl_UnsignedInt {
    ( $( ( $this:ty, $size:expr ) ),* ) => ($(
        impl UnsignedInt for $this {
            const WIDTH: usize = $size;

            const MIN_BOUND: Self = 0;
            const MAX_BOUND: Self = !(0 as Self);

            #[inline(always)] fn count_ones(self)  -> u32 {self.count_ones()}
            #[inline(always)] fn count_zeros(self) -> u32 {self.count_zeros()}

            #[inline(always)] fn succ(&self) -> Self {*self + 1}
            #[inline(always)] fn pred(&self) -> Self {*self - 1}
        }
    )*)
}

impl_UnsignedInt!((u64, 64), (u32, 32), (u16, 16), (u8, 8));

#[cfg(target_pointer_width = "32")]
impl_UnsignedInt!((usize, 32));
#[cfg(target_pointer_width = "64")]
impl_UnsignedInt!((usize, 64));

impl_UnsignedInt!((u128, 128));

/// Find the smallest index i in range at which f(i) is true, assuming that
/// f(i) == true implies f(i+1) == true.
#[macro_export]
macro_rules! search {
    ( $start:expr, $end:expr, $func:expr ) => {
        {
            let mut i = $start;
            let mut j = $end;
            while i < j {
                let h = i + (j - i) / 2;
                if $func(h) {
                    j = h; // f(j) == true
                } else {
                    i = h + 1; // f(i-1) == false
                }
            }
            i
        }
    }
}