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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97

// Copyright 2017 Matthew Plant. This file is part of MGF.
//
// MGF is free software: you can redistribute it and/or modify
// it under the terms of the GNU Lesser General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
//
// MGF is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU Lesser General Public License for more details.
//
// You should have received a copy of the GNU Lesser General Public License
// along with MGF. If not, see <http://www.gnu.org/licenses/>.

use std::fmt::Binary;

/// A bit set of fixed, limited capacity.
pub trait FixedSizeBitSet : Default + Binary {
    /// Maximum number of bits allowed in the set.
    const NUM_BITS: usize;

    /// Retrieve a bit value at the index.
    fn get(&self, i: usize) -> bool;

    /// Set the bit at the given index.
    fn insert(&mut self, i: usize);

    /// Unset the bit at the given index.
    fn remove(&mut self, i: usize);
}

macro_rules! impl_bit_set {
    (
        $type:ty, $num_bits:expr
    ) => {
        impl FixedSizeBitSet for $type {
            const NUM_BITS: usize = $num_bits;

            #[inline(always)]
            fn get(&self, i: usize) -> bool {
                if i >= Self::NUM_BITS {
                    panic!("index is out of bounds: the len is {} but the index is {}",
                           Self::NUM_BITS, i);
                }
                (*self >> i & 0b_1) == 1
            }

            #[inline(always)]
            fn insert(&mut self, i: usize) {
                if i >= Self::NUM_BITS {
                    panic!("index is out of bounds: the len is {} but the index is {}",
                           Self::NUM_BITS, i);
                }
                *self |= 1 << i;
            }

            #[inline(always)]
            fn remove(&mut self, i: usize) {
                if i >= Self::NUM_BITS {
                    panic!("index is out of bounds: the len is {} but the index is {}",
                           Self::NUM_BITS, i);
                }
                *self &= !(1 << i);
            }
        }
    };
}

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

#[cfg(test)]
mod tests {
    mod bitset {
        #[test]
        fn test_bitset() {
            use bitset::FixedSizeBitSet;

            let mut bitset: u64 = 0;

            bitset.insert(3);
            bitset.insert(10);
            bitset.insert(13);
            bitset.insert(35);

            for i in 0..32 {
                match i {
                    3 | 10 | 13 | 35 => { assert!(bitset.get(i)); },
                    _ => { assert!(!bitset.get(i)); },
                }
            }
        }
    }
}