compacts_prim/
lib.rs

1#![feature(i128_type)]
2
3pub trait UnsignedInt: PartialEq + PartialOrd + Eq + Ord + Copy {
4    const WIDTH: usize;
5
6    const MIN_BOUND: Self;
7    const MAX_BOUND: Self;
8
9    fn count_ones(self) -> u32;
10    fn count_zeros(self) -> u32;
11
12    fn succ(&self) -> Self;
13    fn pred(&self) -> Self;
14}
15
16macro_rules! impl_UnsignedInt {
17    ( $( ( $this:ty, $size:expr ) ),* ) => ($(
18        impl UnsignedInt for $this {
19            const WIDTH: usize = $size;
20
21            const MIN_BOUND: Self = 0;
22            const MAX_BOUND: Self = !(0 as Self);
23
24            #[inline(always)] fn count_ones(self)  -> u32 {self.count_ones()}
25            #[inline(always)] fn count_zeros(self) -> u32 {self.count_zeros()}
26
27            #[inline(always)] fn succ(&self) -> Self {*self + 1}
28            #[inline(always)] fn pred(&self) -> Self {*self - 1}
29        }
30    )*)
31}
32
33impl_UnsignedInt!((u64, 64), (u32, 32), (u16, 16), (u8, 8));
34
35#[cfg(target_pointer_width = "32")]
36impl_UnsignedInt!((usize, 32));
37#[cfg(target_pointer_width = "64")]
38impl_UnsignedInt!((usize, 64));
39
40impl_UnsignedInt!((u128, 128));
41
42/// Find the smallest index i in range at which f(i) is true, assuming that
43/// f(i) == true implies f(i+1) == true.
44#[macro_export]
45macro_rules! search {
46    ( $start:expr, $end:expr, $func:expr ) => {
47        {
48            let mut i = $start;
49            let mut j = $end;
50            while i < j {
51                let h = i + (j - i) / 2;
52                if $func(h) {
53                    j = h; // f(j) == true
54                } else {
55                    i = h + 1; // f(i-1) == false
56                }
57            }
58            i
59        }
60    }
61}