fixed_bitmaps/oversized/
bitmap_256.rs

1use core::fmt::Formatter;
2use std::{
3    fmt::Display,
4    mem,
5    ops::{Add, AddAssign, BitAnd, BitAndAssign, BitOr, BitOrAssign, BitXor, BitXorAssign, Deref},
6};
7
8use crate::BitmapSize;
9
10const ELEMENT_SIZE: usize = mem::size_of::<usize>() * 8;
11const ELEMENT_COUNT: usize = Bitmap256::MAP_LENGTH / ELEMENT_SIZE;
12
13/// Experimental struct for now, a bitmap containing 256 bits.
14/// I wouldn't yet recommend using this struct until it's more stable!
15#[derive(PartialEq, Eq, PartialOrd, Ord, Clone, Copy, Hash, Debug)]
16pub struct Bitmap256([usize; ELEMENT_COUNT]);
17
18impl Default for Bitmap256 {
19    fn default() -> Self {
20        Self([0; ELEMENT_COUNT])
21    }
22}
23
24impl Bitmap256 {
25    fn get_element_location(bit_index: usize) -> usize {
26        ELEMENT_COUNT - 1 - bit_index / ELEMENT_SIZE
27    }
28
29    pub fn capacity() -> usize {
30        Bitmap256::MAP_LENGTH
31    }
32
33    pub fn to_array(&self) -> [usize; ELEMENT_COUNT] {
34        self.0
35    }
36
37    pub fn get(&self, index: usize) -> Result<bool, String> {
38        if index >= Bitmap256::MAP_LENGTH {
39            return Err(String::from(
40                "Tried to get bit that's out of range of the bitmap (range: ",
41            ) + &Bitmap256::MAP_LENGTH.to_string()
42                + ", index: "
43                + &index.to_string()
44                + ")");
45        }
46
47        let element_location = Bitmap256::get_element_location(index);
48        let mask = 1 << index % ELEMENT_SIZE;
49        Ok(self.0[element_location] & mask > 0)
50    }
51
52    pub fn set(&mut self, index: usize, value: bool) -> Result<(), String> {
53        if index >= Bitmap256::MAP_LENGTH {
54            return Err(String::from(
55                "Tried to set bit that's out of range of the bitmap (range: ",
56            ) + &Bitmap256::MAP_LENGTH.to_string()
57                + ", index: "
58                + &index.to_string()
59                + ")");
60        }
61
62        let element_location = Bitmap256::get_element_location(index);
63
64        if value {
65            let mask = 1 << index % ELEMENT_SIZE;
66            self.0[element_location] |= mask;
67        } else {
68            let mask = usize::MAX - (1 << index % ELEMENT_SIZE);
69            self.0[element_location] &= mask;
70        }
71
72        Ok(())
73    }
74
75    pub fn from_set(index: usize) -> Option<Bitmap256> {
76        if index >= Bitmap256::MAP_LENGTH {
77            return None;
78        }
79
80        let mut bitmap = Bitmap256::default();
81        bitmap.set(index, true).unwrap();
82        Some(bitmap)
83    }
84
85    pub fn new(value: bool) -> Bitmap256 {
86        Bitmap256(if value {
87            [usize::MAX; ELEMENT_COUNT]
88        } else {
89            [0; ELEMENT_COUNT]
90        })
91    }
92}
93
94impl Display for Bitmap256 {
95    fn fmt(&self, f: &mut Formatter<'_>) -> Result<(), std::fmt::Error> {
96        let mut bitmap = String::new();
97        for i in 0..ELEMENT_COUNT {
98            bitmap.push_str(format!("{:X}", self.0[i]).as_str());
99            if i < ELEMENT_COUNT - 1 {
100                bitmap.push_str("_");
101            }
102        }
103        write!(f, "{}", bitmap.chars().collect::<String>())
104    }
105}
106
107impl BitmapSize for Bitmap256 {
108    const MAP_LENGTH: usize = 256;
109}
110
111impl From<[usize; ELEMENT_COUNT]> for Bitmap256 {
112    fn from(value: [usize; ELEMENT_COUNT]) -> Self {
113        Bitmap256(value)
114    }
115}
116
117// Traits implementing bitwise operations between Bitmaps of the same type
118
119impl BitAnd for Bitmap256 {
120    type Output = Self;
121
122    fn bitand(self, rhs: Self) -> Self::Output {
123        let mut bitmap = self.0;
124        for i in 0..ELEMENT_COUNT {
125            bitmap[i] &= rhs.0[i];
126        }
127        Self(bitmap)
128    }
129}
130
131impl BitAndAssign for Bitmap256 {
132    fn bitand_assign(&mut self, rhs: Self) {
133        for i in 0..ELEMENT_COUNT {
134            self.0[i] &= rhs.0[i];
135        }
136    }
137}
138
139impl BitOr for Bitmap256 {
140    type Output = Self;
141
142    fn bitor(self, rhs: Self) -> Self::Output {
143        let mut bitmap = self.0;
144        for i in 0..ELEMENT_COUNT {
145            bitmap[i] |= rhs.0[i];
146        }
147        Self(bitmap)
148    }
149}
150
151impl BitOrAssign for Bitmap256 {
152    fn bitor_assign(&mut self, rhs: Self) {
153        for i in 0..ELEMENT_COUNT {
154            self.0[i] |= rhs.0[i];
155        }
156    }
157}
158
159impl BitXor for Bitmap256 {
160    type Output = Self;
161
162    fn bitxor(self, rhs: Self) -> Self::Output {
163        let mut bitmap = self.0;
164        for i in 0..ELEMENT_COUNT {
165            bitmap[i] ^= rhs.0[i];
166        }
167        Self(bitmap)
168    }
169}
170
171impl BitXorAssign for Bitmap256 {
172    fn bitxor_assign(&mut self, rhs: Self) {
173        for i in 0..ELEMENT_COUNT {
174            self.0[i] ^= rhs.0[i];
175        }
176    }
177}
178
179// Traits implementing bitwise operations between Bitmaps and their respective array type
180
181impl BitAnd<[usize; ELEMENT_COUNT]> for Bitmap256 {
182    type Output = Self;
183
184    fn bitand(self, rhs: [usize; ELEMENT_COUNT]) -> Self::Output {
185        let mut bitmap = self.0;
186        for i in 0..ELEMENT_COUNT {
187            bitmap[i] &= rhs[i];
188        }
189        Self(bitmap)
190    }
191}
192
193impl BitAndAssign<[usize; ELEMENT_COUNT]> for Bitmap256 {
194    fn bitand_assign(&mut self, rhs: [usize; ELEMENT_COUNT]) {
195        for i in 0..ELEMENT_COUNT {
196            self.0[i] &= rhs[i];
197        }
198    }
199}
200
201impl BitOr<[usize; ELEMENT_COUNT]> for Bitmap256 {
202    type Output = Self;
203
204    fn bitor(self, rhs: [usize; ELEMENT_COUNT]) -> Self::Output {
205        let mut bitmap = self.0;
206        for i in 0..ELEMENT_COUNT {
207            bitmap[i] |= rhs[i];
208        }
209        Self(bitmap)
210    }
211}
212
213impl BitOrAssign<[usize; ELEMENT_COUNT]> for Bitmap256 {
214    fn bitor_assign(&mut self, rhs: [usize; ELEMENT_COUNT]) {
215        for i in 0..ELEMENT_COUNT {
216            self.0[i] |= rhs[i];
217        }
218    }
219}
220
221impl BitXor<[usize; ELEMENT_COUNT]> for Bitmap256 {
222    type Output = Self;
223
224    fn bitxor(self, rhs: [usize; ELEMENT_COUNT]) -> Self::Output {
225        let mut bitmap = self.0;
226        for i in 0..ELEMENT_COUNT {
227            bitmap[i] ^= rhs[i];
228        }
229        Self(bitmap)
230    }
231}
232
233impl BitXorAssign<[usize; ELEMENT_COUNT]> for Bitmap256 {
234    fn bitxor_assign(&mut self, rhs: [usize; ELEMENT_COUNT]) {
235        for i in 0..ELEMENT_COUNT {
236            self.0[i] ^= rhs[i];
237        }
238    }
239}
240
241// Traits implementing arithmetic operations between Bitmaps and their respective integer types.
242
243impl Add<usize> for Bitmap256 {
244    type Output = Self;
245
246    fn add(self, rhs: usize) -> Self::Output {
247        let mut bitmap = self.0;
248        let mut carry = rhs;
249
250        for i in (0..ELEMENT_COUNT).rev() {
251            if usize::MAX - carry < bitmap[i] {
252                bitmap[i] = bitmap[i].wrapping_add(carry);
253                carry = 1;
254            } else {
255                bitmap[i] += carry;
256                carry = 0;
257                break;
258            }
259        }
260
261        if carry > 0 {
262            eprintln!("Warning: Adding led to overflow!");
263        }
264
265        Self(bitmap)
266    }
267}
268
269impl AddAssign<usize> for Bitmap256 {
270    fn add_assign(&mut self, rhs: usize) {
271        let mut carry = rhs;
272
273        for i in (0..ELEMENT_COUNT).rev() {
274            if usize::MAX - carry < self.0[i] {
275                self.0[i] = self.0[i].wrapping_add(carry);
276                carry = 1;
277            } else {
278                self.0[i] += carry;
279                carry = 0;
280                break;
281            }
282        }
283
284        if carry > 0 {
285            eprintln!("Warning: Adding led to overflow!");
286        }
287    }
288}
289
290impl Deref for Bitmap256 {
291    type Target = [usize; ELEMENT_COUNT];
292
293    fn deref(&self) -> &Self::Target {
294        &self.0
295    }
296}
297
298// An attempt at serialization so far, no idea how to implement deserialisation yet
299//
300// impl Serialize for Bitmap256 {
301//     fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
302//     where
303//         S: Serializer,
304//     {
305//         let mut seq = serializer.serialize_seq(Some(NUM_ELEMENTS))?;
306//         for e in self.0 {
307//             seq.serialize_element(&e)?;
308//         }
309//         seq.end()
310//     }
311// }
312
313#[cfg(test)]
314mod tests {
315    use super::BitmapSize;
316    use super::{Bitmap256, ELEMENT_COUNT, ELEMENT_SIZE};
317    use std::mem;
318
319    #[test]
320    fn create_default() {
321        let bitmap = Bitmap256::default();
322        assert_eq!([0; ELEMENT_COUNT], *bitmap);
323    }
324
325    #[test]
326    fn constants_correct() {
327        assert_eq!(ELEMENT_SIZE, mem::size_of::<usize>() * 8);
328        assert_eq!(Bitmap256::MAP_LENGTH, 256);
329        assert_eq!(ELEMENT_COUNT, Bitmap256::MAP_LENGTH / ELEMENT_SIZE);
330    }
331}
fixed_bitmaps/oversized/bitmap_256.rs

fixed_bitmaps/oversized/
bitmap_256.rs
