layered_bitset/
lib.rs

1#![cfg_attr(not(test), no_std)]
2#![deprecated(note = "use `bitsetium` crate instead")]
3
4#[cfg(feature = "alloc")]
5extern crate alloc;
6
7mod indirect;
8mod layered;
9mod option;
10mod primitive;
11
12pub use layered::Layered;
13
14/// Common trait for all bitsets in `bitseto` crate.
15pub trait BitSet {
16    /// Upper bound for this bitset indices.
17    /// Implementation is expected to panic if index equal to or greter than `UPPER_BOUND` is speicifed.
18    const UPPER_BOUND: u32;
19
20    /// Returns bit state at specified index.
21    ///
22    /// # Panics
23    ///
24    /// This function may panic if `index` is equal to or greter than `UPPER_BOUND`.
25    fn get(&self, index: u32) -> bool;
26
27    /// Returns index of first set bit at index equal to or greter than specified.
28    ///
29    /// # Panics
30    ///
31    /// This function may panic if `index` is equal to or greter than `UPPER_BOUND`.
32    fn find_set(&self, lower_bound: u32) -> Option<u32>;
33
34    /// Returns true if no bit is set.
35    fn is_empty(&self) -> bool {
36        self.find_set(0).is_none()
37    }
38}
39
40/// Common trait for all mutable bitsets in `bitseto` crate.
41pub trait BitSetMut: BitSet {
42    /// Sets bit state at specified index.
43    ///
44    /// # Panics
45    ///
46    /// This function may panic if `index` is equal to or greter than `UPPER_BOUND`.
47    fn set(&mut self, index: u32, bit: bool);
48}
49
50pub type BitSet8 = u8;
51pub type BitSet16 = u16;
52pub type BitSet32 = u32;
53pub type BitSet64 = u64;
54pub type BitSet128 = u128;
55pub type BitSet256 = layered::Layered<u32, u8, 32>;
56pub type BitSet512 = layered::Layered<u64, u8, 64>;
57pub type BitSet1024 = layered::Layered<u64, u16, 64>;
58pub type BitSet2048 = layered::Layered<u64, u32, 64>;
59pub type BitSet4096 = layered::Layered<u64, u64, 64>;
60pub type BitSet8192 = layered::Layered<u64, u128, 64>;
61pub type BitSet16384 = layered::Layered<u128, u128, 128>;
62
63#[cfg(feature = "alloc")]
64pub type BitSet32768 = layered::Layered<u64, Option<alloc::boxed::Box<BitSet512>>, 64>;
65
66#[cfg(feature = "alloc")]
67pub type BitSet65536 = layered::Layered<u64, Option<alloc::boxed::Box<BitSet1024>>, 64>;
68
69#[cfg(feature = "alloc")]
70pub type BitSet131072 = layered::Layered<u64, Option<alloc::boxed::Box<BitSet2048>>, 64>;
71
72#[cfg(feature = "alloc")]
73pub type BitSet262144 = layered::Layered<u64, Option<alloc::boxed::Box<BitSet4096>>, 64>;
74
75#[cfg(feature = "alloc")]
76pub type BitSet524288 = layered::Layered<u64, Option<alloc::boxed::Box<BitSet8192>>, 64>;
77
78#[cfg(feature = "alloc")]
79pub type BitSet1048576 = layered::Layered<u64, Option<alloc::boxed::Box<BitSet16384>>, 64>;
80
81#[cfg(feature = "alloc")]
82pub type BitSet2097152 = layered::Layered<u64, Option<alloc::boxed::Box<BitSet32768>>, 64>;
83
84#[cfg(feature = "alloc")]
85pub type BitSet4194304 = layered::Layered<u64, Option<alloc::boxed::Box<BitSet65536>>, 64>;
86
87#[cfg(feature = "alloc")]
88pub type BitSet8388608 = layered::Layered<u64, Option<alloc::boxed::Box<BitSet131072>>, 64>;
89
90#[cfg(feature = "alloc")]
91pub type BitSet16777216 = layered::Layered<u64, Option<alloc::boxed::Box<BitSet262144>>, 64>;
92
93#[cfg(feature = "alloc")]
94pub type BitSet33554432 = layered::Layered<u64, Option<alloc::boxed::Box<BitSet524288>>, 64>;
95
96#[cfg(feature = "alloc")]
97pub type BitSet67108864 = layered::Layered<u64, Option<alloc::boxed::Box<BitSet1048576>>, 64>;
98
99#[cfg(test)]
100mod tests {
101    use super::*;
102
103    #[test]
104    fn check_bounds() {
105        assert_eq!(BitSet8::UPPER_BOUND, 8);
106        assert_eq!(BitSet16::UPPER_BOUND, 16);
107        assert_eq!(BitSet32::UPPER_BOUND, 32);
108        assert_eq!(BitSet64::UPPER_BOUND, 64);
109        assert_eq!(BitSet128::UPPER_BOUND, 128);
110        assert_eq!(BitSet256::UPPER_BOUND, 256);
111        assert_eq!(BitSet512::UPPER_BOUND, 512);
112        assert_eq!(BitSet1024::UPPER_BOUND, 1024);
113        assert_eq!(BitSet2048::UPPER_BOUND, 2048);
114        assert_eq!(BitSet4096::UPPER_BOUND, 4096);
115        assert_eq!(BitSet8192::UPPER_BOUND, 8192);
116        assert_eq!(BitSet16384::UPPER_BOUND, 16384);
117    }
118
119    #[cfg(feature = "alloc")]
120    #[test]
121    fn check_large_bounds() {
122        assert_eq!(BitSet32768::UPPER_BOUND, 32768);
123        assert_eq!(BitSet65536::UPPER_BOUND, 65536);
124        assert_eq!(BitSet131072::UPPER_BOUND, 131072);
125        assert_eq!(BitSet262144::UPPER_BOUND, 262144);
126        assert_eq!(BitSet524288::UPPER_BOUND, 524288);
127        assert_eq!(BitSet1048576::UPPER_BOUND, 1048576);
128        assert_eq!(BitSet2097152::UPPER_BOUND, 2097152);
129        assert_eq!(BitSet4194304::UPPER_BOUND, 4194304);
130        assert_eq!(BitSet8388608::UPPER_BOUND, 8388608);
131        assert_eq!(BitSet16777216::UPPER_BOUND, 16777216);
132        assert_eq!(BitSet33554432::UPPER_BOUND, 33554432);
133        assert_eq!(BitSet67108864::UPPER_BOUND, 67108864);
134    }
135
136    #[cfg(feature = "alloc")]
137    #[test]
138    fn check_set() {
139        let mut bits = Layered::<u64, u64, 64>::default();
140
141        assert_eq!(bits.get(421), false);
142        bits.set(421, true);
143        assert_eq!(bits.get(421), true);
144
145        bits.set(213, true);
146
147        assert_eq!(bits.find_set(0), Some(213));
148        assert_eq!(bits.find_set(300), Some(421));
149        assert_eq!(bits.find_set(421 + 1), None);
150
151        bits.set(213, false);
152        assert_eq!(bits.find_set(0), Some(421));
153        assert_eq!(bits.find_set(421 + 1), None);
154
155        bits.set(421, false);
156        assert_eq!(bits.get(421), false);
157    }
158}
layered_bitset/lib.rs

layered_bitset/
lib.rs
