open_vaf/data_structures/
bit_set.rs

1/*
2
3 * ******************************************************************************************
4 *  Copyright (c) 2019 Pascal Kuthe. This file is part of the OpenVAF project.
5 *  It is subject to the license terms in the LICENSE file found in the top-level directory
6 *  of this distribution and at  https://gitlab.com/DSPOM/OpenVAF/blob/master/LICENSE.
7 *  OpenVAF, including this file, may be copied, modified, propagated, or
8 *  distributed except according to the terms contained in the LICENSE file.
9 * *****************************************************************************************
10*/
11
12// Provides a wrapper around fixed bit_set similar to index vec
13
14use bitflags::_core::fmt::Binary;
15use bitflags::_core::iter::FromIterator;
16use bitflags::_core::marker::PhantomData;
17use bitflags::_core::ops::{BitAndAssign, BitOr, BitXor, BitXorAssign, Index};
18use fixedbitset::{FixedBitSet, IndexRange};
19use index_vec::Idx;
20use std::fmt;
21use std::fmt::{Display, Formatter};
22use std::ops::{BitAnd, BitOrAssign};
23
24//TODO switch to usize/u64
25//BLOCKS upstream
26type Block = u32;
27
28#[derive(Debug, PartialEq, Eq, PartialOrd, Ord, Hash, Default)]
29pub struct BitSet<I: Idx + From<usize>> {
30    internal: FixedBitSet,
31    tag: PhantomData<fn(&I)>,
32}
33
34impl<I: Idx + From<usize>> BitSet<I> {
35    /// Create a new empty `BitSet` which can hold elements x < end_index
36    pub fn new_empty(end_index: I) -> Self {
37        Self {
38            internal: FixedBitSet::with_capacity(end_index.index()),
39            tag: PhantomData,
40        }
41    }
42
43    /// Create a new empty `BitSet` which can hold elements x < end_index
44    pub fn new_filled(end_index: I) -> Self {
45        let mut res = Self {
46            internal: FixedBitSet::with_capacity(end_index.index()),
47            tag: PhantomData,
48        };
49        res.enable_all();
50        res
51    }
52
53    /// Create a new `BitSet` with a specific number of bits,
54    /// initialized from provided blocks.
55    ///
56    /// If the blocks are not the exact size needed for the capacity
57    /// they will be padded with zeros (if shorter) or truncated to
58    /// the capacity (if longer).
59    pub fn with_capacity_and_blocks<Iter: IntoIterator<Item = Block>>(
60        bits: I,
61        blocks: Iter,
62    ) -> Self {
63        Self {
64            internal: FixedBitSet::with_capacity_and_blocks(bits.index(), blocks),
65            tag: PhantomData,
66        }
67    }
68
69    /// Grow capacity to **bits**, all new bits initialized to zero
70    pub fn grow(&mut self, len_idx: I) {
71        self.internal.grow(len_idx.index())
72    }
73
74    /// Return the length of the `FixedBitSet` in bits.
75    #[inline]
76    pub fn len(&self) -> usize {
77        self.internal.len()
78    }
79
80    /// Return the length of the `FixedBitSet` in bits.
81    #[inline]
82    pub fn len_idx(&self) -> I {
83        self.internal.len().into()
84    }
85    /// Return the length of the `FixedBitSet` in bits.
86    #[inline]
87    pub fn max(&self) -> I {
88        I::from_usize(self.internal.len())
89    }
90
91    /// Return **true** if the bit is enabled in the **FixedBitSet**,
92    /// **false** otherwise.
93    ///
94    /// Note: bits outside the capacity are always disabled.
95    ///
96    /// Note: Also available with index syntax: `bitset[bit]`.
97    #[inline]
98    pub fn contains(&self, bit: I) -> bool {
99        self.internal.contains(bit.index())
100    }
101
102    /// Clear all bits.
103    #[inline]
104    pub fn clear(&mut self) {
105        self.internal.clear()
106    }
107
108    /// Enable `bit`.
109    ///
110    /// **Panics** if **bit** is out of bounds.
111    #[inline]
112    pub fn insert(&mut self, bit: I) {
113        self.internal.insert(bit.index())
114    }
115
116    /// Disable `bit`.
117    ///
118    /// **Panics** if **bit** is out of bounds.
119    #[inline]
120    pub fn remove(&mut self, bit: I) -> bool {
121        let prev = self.internal[bit.index()];
122        self.internal.set(bit.index(), false);
123        prev
124    }
125
126    /// Enable `bit`, and return its previous value.
127    ///
128    /// **Panics** if `bit` is out of bounds.
129    ///
130    #[inline]
131    pub fn put(&mut self, bit: I) -> bool {
132        self.internal.put(bit.index())
133    }
134
135    /// Toggle `bit` (inverting its state).
136    ///
137    /// `Panics` if `bit` is out of bounds
138    #[inline]
139    pub fn toggle(&mut self, bit: I) {
140        self.internal.toggle(bit.index())
141    }
142
143    /// **Panics** if **bit** is out of bounds.
144    #[inline]
145    pub fn set(&mut self, bit: I, enabled: bool) {
146        self.internal.set(bit.index(), enabled)
147    }
148
149    /// Copies boolean value from specified bit to the specified bit.
150    ///
151    /// **Panics** if **to** is out of bounds.
152    #[inline]
153    pub fn copy_bit(&mut self, from: I, to: I) {
154        self.internal.copy_bit(from.index(), to.index())
155    }
156
157    /// Count the number of set bits in the given bit range.
158    ///
159    /// Use `..` to count the whole content of the bitset.
160    ///
161    /// **Panics** if the range extends past the end of the bitset.
162    #[inline]
163    pub fn count_ones<T: IndexRange<I>>(&self, range: T) -> usize {
164        let start = range.start().map_or(0, |idx| idx.index());
165        let end = range.end().map_or(self.internal.len(), |idx| idx.index());
166        self.internal.count_ones(start..end)
167    }
168
169    /// Sets every bit in the given range to the given state (`enabled`)
170    ///
171    /// Use `..` to set the whole bitset.
172    ///
173    /// **Panics** if the range extends past the end of the bitset.
174    #[inline]
175    pub fn set_range<T: IndexRange<I>>(&mut self, range: T, enabled: bool) {
176        let start = range.start().map_or(0, |idx| idx.index());
177        let end = range.end().map_or(self.internal.len(), |idx| idx.index());
178        self.internal.set_range(start..end, enabled)
179    }
180
181    /// Enables every bit in the given range.
182    ///
183    /// Use `..` to make the whole bitset ones.
184    ///
185    /// **Panics** if the range extends past the end of the bitset.
186    #[inline]
187    pub fn insert_range<T: IndexRange<I>>(&mut self, range: T) {
188        let start = range.start().map_or(0, |idx| idx.index());
189        let end = range.end().map_or(self.internal.len(), |idx| idx.index());
190        self.internal.insert_range(start..end)
191    }
192
193    /// Equivalent to [`insert_range(..)`](insert_range) but significantly faster
194    #[inline]
195    pub fn enable_all(&mut self) {
196        for block in self.as_mut_slice().iter_mut() {
197            *block = Block::MAX
198        }
199    }
200
201    /// Toggles (inverts) every bit in the given range.
202    ///
203    /// Use `..` to toggle the whole bitset.
204    ///
205    /// **Panics** if the range extends past the end of the bitset.
206    #[inline]
207    pub fn toggle_range<T: IndexRange<I>>(&mut self, range: T) {
208        let start = range.start().map_or(0, |idx| idx.index());
209        let end = range.end().map_or(self.internal.len(), |idx| idx.index());
210        self.internal.toggle_range(start..end)
211    }
212
213    /// View the bitset as a slice of `u32` blocks
214    #[inline]
215    pub fn as_slice(&self) -> &[u32] {
216        self.internal.as_slice()
217    }
218
219    /// View the bitset as a mutable slice of `u32` blocks. Writing past the bitlength in the last
220    /// will cause `contains` to return potentially incorrect results for bits past the bitlength.
221    #[inline]
222    pub fn as_mut_slice(&mut self) -> &mut [u32] {
223        self.internal.as_mut_slice()
224    }
225
226    #[inline]
227    pub fn is_empty(&self) -> bool {
228        self.as_slice().iter().all(|block| *block == 0)
229    }
230
231    /// Iterates over all enabled bits.
232    ///
233    /// Iterator element is the index of the `1` bit, type `usize`.
234    #[inline]
235    pub fn ones(&self) -> Ones<'_, I> {
236        Ones {
237            iter: self.internal.ones(),
238            tag: PhantomData,
239        }
240    }
241
242    /// Returns a lazy iterator over the intersection of two `FixedBitSet`s
243    pub fn intersection<'a>(&'a self, other: &'a Self) -> Intersection<'a, I> {
244        Intersection {
245            iter: self.internal.intersection(&other.internal),
246            tag: PhantomData,
247        }
248    }
249
250    /// Returns a lazy iterator over the union of two `FixedBitSet`s.
251    pub fn union<'a>(&'a self, other: &'a Self) -> Union<'a, I> {
252        Union {
253            iter: self.internal.union(&other.internal),
254            tag: PhantomData,
255        }
256    }
257
258    /// Returns a lazy iterator over the difference of two `FixedBitSet`s. The difference of `a`
259    /// and `b` is the elements of `a` which are not in `b`.
260    pub fn difference<'a>(&'a self, other: &'a Self) -> Difference<'a, I> {
261        Difference {
262            iter: self.internal.difference(&other.internal),
263            tag: PhantomData,
264        }
265    }
266
267    /// Returns a lazy iterator over the symmetric difference of two `FixedBitSet`s.
268    /// The symmetric difference of `a` and `b` is the elements of one, but not both, sets.
269    pub fn symmetric_difference<'a>(&'a self, other: &'a Self) -> SymmetricDifference<'a, I> {
270        SymmetricDifference {
271            iter: self.internal.symmetric_difference(&other.internal),
272            tag: PhantomData,
273        }
274    }
275
276    /// In-place union of two `FixedBitSet`s.
277    ///
278    /// On calling this method, `self`'s capacity may be increased to match `other`'s.
279    pub fn union_with(&mut self, other: &Self) {
280        self.internal.union_with(&other.internal)
281    }
282
283    /// In-place intersection of two `FixedBitSet`s.
284    ///
285    /// On calling this method, `self`'s capacity will remain the same as before.
286    pub fn intersect_with(&mut self, other: &Self) {
287        self.internal.intersect_with(&other.internal)
288    }
289
290    /// In-place difference of two `FixedBitSet`s.
291    ///
292    /// On calling this method, `self`'s capacity will remain the same as before.
293    pub fn difference_with(&mut self, other: &Self) {
294        self.internal.difference_with(&other.internal)
295    }
296
297    /// In-place symmetric difference of two `FixedBitSet`s.
298    ///
299    /// On calling this method, `self`'s capacity may be increased to match `other`'s.
300    pub fn symmetric_difference_with(&mut self, other: &Self) {
301        self.internal.symmetric_difference_with(&other.internal)
302    }
303
304    /// Returns `true` if `self` has no elements in common with `other`. This
305    /// is equivalent to checking for an empty intersection.
306    pub fn is_disjoint(&self, other: &Self) -> bool {
307        self.internal.is_disjoint(&other.internal)
308    }
309
310    /// Returns `true` if the set is a subset of another, i.e. `other` contains
311    /// at least all the values in `self`.
312    pub fn is_subset(&self, other: &Self) -> bool {
313        self.internal.is_subset(&other.internal)
314    }
315
316    /// Returns `true` if the set is a superset of another, i.e. `self` contains
317    /// at least all the values in `other`.
318    pub fn is_superset(&self, other: &Self) -> bool {
319        self.internal.is_superset(&other.internal)
320    }
321}
322
323impl<I: Idx + From<usize>> Binary for BitSet<I> {
324    fn fmt(&self, f: &mut Formatter<'_>) -> Result<(), fmt::Error> {
325        Binary::fmt(&self.internal, f)
326    }
327}
328
329impl<I: Idx + From<usize> + Display> Display for BitSet<I> {
330    fn fmt(&self, f: &mut Formatter<'_>) -> Result<(), fmt::Error> {
331        f.write_str("{")?;
332        for idx in self.ones() {
333            Display::fmt(&idx, f)?;
334            f.write_str(",")?;
335        }
336        f.write_str("}")
337    }
338}
339
340/// An iterator producing elements in the difference of two sets.
341///
342/// This struct is created by the [`FixedBitSet::difference`] method.
343pub struct Difference<'a, I: Idx + From<usize>> {
344    iter: fixedbitset::Difference<'a>,
345    tag: PhantomData<fn(&I)>,
346}
347
348impl<'a, I: Idx + From<usize>> Iterator for Difference<'a, I> {
349    type Item = I;
350
351    #[inline]
352    fn next(&mut self) -> Option<Self::Item> {
353        self.iter.next().map(|idx| idx.into())
354    }
355}
356
357/// An iterator producing elements in the symmetric difference of two sets.
358///
359/// This struct is created by the [`FixedBitSet::symmetric_difference`] method.
360pub struct SymmetricDifference<'a, I: Idx + From<usize>> {
361    iter: fixedbitset::SymmetricDifference<'a>,
362    tag: PhantomData<fn(&I)>,
363}
364
365impl<'a, I: Idx + From<usize>> Iterator for SymmetricDifference<'a, I> {
366    type Item = I;
367
368    #[inline]
369    fn next(&mut self) -> Option<Self::Item> {
370        self.iter.next().map(|idx| idx.into())
371    }
372}
373
374/// An iterator producing elements in the intersection of two sets.
375///
376/// This struct is created by the [`FixedBitSet::intersection`] method.
377pub struct Intersection<'a, I: Idx + From<usize>> {
378    iter: fixedbitset::Intersection<'a>,
379    tag: PhantomData<fn(&I)>,
380}
381
382impl<'a, I: Idx + From<usize>> Iterator for Intersection<'a, I> {
383    type Item = I; // the bit position of the '1'
384
385    #[inline]
386    fn next(&mut self) -> Option<Self::Item> {
387        self.iter.next().map(|idx| idx.into())
388    }
389}
390
391/// An iterator producing elements in the union of two sets.
392///
393/// This struct is created by the [`FixedBitSet::union`] method.
394pub struct Union<'a, I: Idx + From<usize>> {
395    iter: fixedbitset::Union<'a>,
396    tag: PhantomData<fn(&I)>,
397}
398
399impl<'a, I: Idx + From<usize>> Iterator for Union<'a, I> {
400    type Item = I;
401
402    #[inline]
403    fn next(&mut self) -> Option<Self::Item> {
404        self.iter.next().map(|idx| idx.into())
405    }
406}
407
408/// An  iterator producing the indices of the set bit in a set.
409///
410/// This struct is created by the [`FixedBitSet::ones`] method.
411pub struct Ones<'a, I: Idx + From<usize>> {
412    iter: fixedbitset::Ones<'a>,
413    tag: PhantomData<fn(&I)>,
414}
415
416impl<'a, I: Idx + From<usize>> Iterator for Ones<'a, I> {
417    type Item = I; // the bit position of the '1'
418
419    #[inline]
420    fn next(&mut self) -> Option<Self::Item> {
421        self.iter.next().map(|idx| idx.into())
422    }
423}
424
425impl<I: Idx + From<usize>> Clone for BitSet<I> {
426    #[inline]
427    fn clone(&self) -> Self {
428        Self {
429            internal: self.internal.clone(),
430            tag: PhantomData,
431        }
432    }
433}
434
435/// Return **true** if the bit is enabled in the bitset,
436/// or **false** otherwise.
437///
438/// Note: bits outside the capacity are always disabled, and thus
439/// indexing a FixedBitSet will not panic.
440impl<I: Idx + From<usize>> Index<I> for BitSet<I> {
441    type Output = bool;
442
443    #[inline]
444    fn index(&self, bit: I) -> &bool {
445        &self.internal[bit.index()]
446    }
447}
448
449/// Sets the bit at index **i** to **true** for each item **i** in the input **src**.
450impl<I: Idx + From<usize>> Extend<I> for BitSet<I> {
451    fn extend<Iter: IntoIterator<Item = I>>(&mut self, src: Iter) {
452        let src = src.into_iter().map(|id| id.index());
453        self.internal.extend(src)
454    }
455}
456
457/// Return a FixedBitSet containing bits set to **true** for every bit index in
458/// the iterator, other bits are set to **false**.
459impl<I: Idx + From<usize>> FromIterator<I> for BitSet<I> {
460    fn from_iter<Iter: IntoIterator<Item = I>>(src: Iter) -> Self {
461        let iter = src.into_iter();
462        let mut res = BitSet::new_empty(iter.size_hint().0.into());
463        res.extend(iter);
464        res
465    }
466}
467
468impl<'a, I: Idx + From<usize>> BitAnd for &'a BitSet<I> {
469    type Output = BitSet<I>;
470    fn bitand(self, other: &BitSet<I>) -> BitSet<I> {
471        BitSet {
472            internal: (&self.internal) & (&other.internal),
473            tag: PhantomData,
474        }
475    }
476}
477
478impl<'a, I: Idx + From<usize>> BitAndAssign for BitSet<I> {
479    fn bitand_assign(&mut self, other: Self) {
480        self.internal &= other.internal
481    }
482}
483
484impl<'a, I: Idx + From<usize>> BitOr for &'a BitSet<I> {
485    type Output = BitSet<I>;
486    fn bitor(self, other: &BitSet<I>) -> BitSet<I> {
487        BitSet {
488            internal: (&self.internal) | (&other.internal),
489            tag: PhantomData,
490        }
491    }
492}
493
494impl<'a, I: Idx + From<usize>> BitOrAssign for BitSet<I> {
495    fn bitor_assign(&mut self, other: Self) {
496        self.internal |= other.internal
497    }
498}
499
500impl<'a, I: Idx + From<usize>> BitXor for &'a BitSet<I> {
501    type Output = BitSet<I>;
502    fn bitxor(self, other: &BitSet<I>) -> BitSet<I> {
503        BitSet {
504            internal: (&self.internal) ^ (&other.internal),
505            tag: PhantomData,
506        }
507    }
508}
509
510impl<'a, I: Idx + From<usize>> BitXorAssign for BitSet<I> {
511    fn bitxor_assign(&mut self, other: Self) {
512        self.internal ^= other.internal
513    }
514}
open_vaf/data_structures/bit_set.rs

open_vaf/data_structures/
bit_set.rs
