igraph/
bitset.rs

1//! Fixed-size sets of bits (`igraph_bitset.h`, `igraph_bitset_list.h`).
2//!
3//! [`Bitset`] is igraph's `igraph_bitset_t` made Rusty: a compact, owned
4//! sequence of bits (one machine word stores 64 of them) that frees its
5//! storage on [`Drop`], can be cloned, compared, iterated and combined with
6//! the usual bit operators `&`, `|`, `^` and `!`. igraph uses bitsets e.g. to
7//! mark visited vertices; [`BitsetList`] is the owned list of bitsets
8//! (`igraph_bitset_list_t`) returned by some algorithms, such as
9//! `igraph_reachability` (wrapped by
10//! [`Graph::reachability`](crate::Graph::reachability), which unpacks the
11//! bitsets into booleans).
12//!
13//! Bits are indexed from `0` (the *least* significant bit); [`Display`](std::fmt::Display)
14//! prints them like igraph does, most significant first, as a binary number.
15//!
16//! ```
17//! use igraph::bitset::Bitset;
18//!
19//! let mut visited = Bitset::new(10);
20//! visited.set(2, true);
21//! visited.set(7, true);
22//! assert_eq!(visited.count_ones(), 2);
23//! assert_eq!(visited.iter_ones().collect::<Vec<_>>(), vec![2, 7]);
24//! assert_eq!(visited.to_string(), "0010000100");
25//!
26//! let evens: Bitset = (0..10).map(|i| i % 2 == 0).collect();
27//! assert_eq!((&visited & &evens).iter_ones().collect::<Vec<_>>(), vec![2]);
28//! assert_eq!((!&evens).count_ones(), 5);
29//! ```
30//!
31//! | Rust                                    | C                                       |
32//! |-----------------------------------------|-----------------------------------------|
33//! | [`Bitset::new`], [`Bitset::clone`]      | `igraph_bitset_init`, `igraph_bitset_init_copy` |
34//! | [`len`](Bitset::len), [`capacity`](Bitset::capacity) | `igraph_bitset_size`, `igraph_bitset_capacity` |
35//! | [`resize`](Bitset::resize), [`reserve`](Bitset::reserve) | `igraph_bitset_resize`, `igraph_bitset_reserve` |
36//! | [`get`](Bitset::get), [`set`](Bitset::set), [`toggle`](Bitset::toggle) | `IGRAPH_BIT_TEST`, `IGRAPH_BIT_SET`, `IGRAPH_BIT_CLEAR` |
37//! | [`count_ones`](Bitset::count_ones)      | `igraph_bitset_popcount`                |
38//! | [`leading_zeros`](Bitset::leading_zeros), [`leading_ones`](Bitset::leading_ones) | `igraph_bitset_countl_zero`, `igraph_bitset_countl_one` |
39//! | [`trailing_zeros`](Bitset::trailing_zeros), [`trailing_ones`](Bitset::trailing_ones) | `igraph_bitset_countr_zero`, `igraph_bitset_countr_one` |
40//! | [`all`](Bitset::all), [`any`](Bitset::any), [`none`](Bitset::none), [`not_all`](Bitset::not_all) | `igraph_bitset_is_all_one`, `igraph_bitset_is_any_one`, `igraph_bitset_is_all_zero`, `igraph_bitset_is_any_zero` |
41//! | `&`, `\|`, `^`, `!` (and `&=`, ...)       | `igraph_bitset_and`, `igraph_bitset_or`, `igraph_bitset_xor`, `igraph_bitset_not` |
42//! | [`fill`](Bitset::fill), [`clear`](Bitset::clear) | `igraph_bitset_fill`, `igraph_bitset_null` |
43//! | [`Display`](std::fmt::Display)                             | `igraph_bitset_print`                   |
44
45use crate::ffi::*;
46use std::{fmt, mem::MaybeUninit, ops};
47
48pub use crate::list::BitsetList;
49
50/// An owned, fixed-size set of bits (`igraph_bitset_t`), see the [module docs](self).
51pub type Bitset = igraph_bitset_t;
52
53const WORD_BITS: usize = igraph_uint_t::BITS as usize;
54
55impl igraph_bitset_t {
56    /// Creates a bitset of `len` bits, all zero
57    /// ([`igraph_bitset_init`](https://igraph.org/c/html/latest/igraph-Data-structures.html#igraph_bitset_init)).
58    pub fn new(len: usize) -> Self {
59        crate::error::ensure_init();
60        let mut raw = MaybeUninit::<Self>::uninit();
61        crate::error::check(unsafe {
62            igraph_bitset_init(raw.as_mut_ptr(), crate::error::int_size(len))
63        })
64        .expect("igraph failed to allocate a bitset");
65        unsafe { raw.assume_init() }
66    }
67
68    /// Creates a bitset from a slice of booleans (`bits[i]` is bit `i`).
69    pub fn from_bools(bits: &[bool]) -> Self {
70        let mut b = Self::new(bits.len());
71        for (i, &x) in bits.iter().enumerate() {
72            if x {
73                b.set(i, true);
74            }
75        }
76        b
77    }
78
79    /// Creates a bitset of `len` bits where exactly the listed positions are
80    /// set.
81    ///
82    /// # Panics
83    /// If a position is `>= len`.
84    pub fn from_ones(len: usize, ones: impl IntoIterator<Item = usize>) -> Self {
85        let mut b = Self::new(len);
86        for i in ones {
87            b.set(i, true);
88        }
89        b
90    }
91
92    /// Number of bits
93    /// ([`igraph_bitset_size`](https://igraph.org/c/html/latest/igraph-Data-structures.html#igraph_bitset_size)).
94    pub fn len(&self) -> usize {
95        self.size as usize
96    }
97
98    /// Whether the bitset has no bits at all (not whether all bits are zero:
99    /// see [`none`](Self::none)).
100    pub fn is_empty(&self) -> bool {
101        self.size == 0
102    }
103
104    /// Number of bits that fit in the allocated storage
105    /// ([`igraph_bitset_capacity`](https://igraph.org/c/html/latest/igraph-Data-structures.html#igraph_bitset_capacity)).
106    pub fn capacity(&self) -> usize {
107        unsafe { igraph_bitset_capacity(self) as usize }
108    }
109
110    /// Reserves storage for at least `capacity` bits in total
111    /// ([`igraph_bitset_reserve`](https://igraph.org/c/html/latest/igraph-Data-structures.html#igraph_bitset_reserve)).
112    pub fn reserve(&mut self, capacity: usize) {
113        crate::error::check(unsafe {
114            igraph_bitset_reserve(self, crate::error::int_size(capacity))
115        })
116        .expect("igraph failed to reserve bitset storage");
117    }
118
119    /// Changes the number of bits; new bits are zero
120    /// ([`igraph_bitset_resize`](https://igraph.org/c/html/latest/igraph-Data-structures.html#igraph_bitset_resize)).
121    pub fn resize(&mut self, len: usize) {
122        crate::error::check(unsafe { igraph_bitset_resize(self, crate::error::int_size(len)) })
123            .expect("igraph failed to resize a bitset");
124    }
125
126    fn words(&self) -> &[igraph_uint_t] {
127        let n = self.len().div_ceil(WORD_BITS);
128        if n == 0 {
129            return &[];
130        }
131        unsafe { std::slice::from_raw_parts(self.stor_begin, n) }
132    }
133
134    fn words_mut(&mut self) -> &mut [igraph_uint_t] {
135        let n = self.len().div_ceil(WORD_BITS);
136        if n == 0 {
137            return &mut [];
138        }
139        unsafe { std::slice::from_raw_parts_mut(self.stor_begin, n) }
140    }
141
142    fn check_index(&self, i: usize) {
143        assert!(
144            i < self.len(),
145            "bit index {i} out of bounds (len {})",
146            self.len()
147        );
148    }
149
150    /// The value of bit `i` (`IGRAPH_BIT_TEST`).
151    ///
152    /// # Panics
153    /// If `i >= len`.
154    pub fn get(&self, i: usize) -> bool {
155        self.check_index(i);
156        self.words()[i / WORD_BITS] & (1 << (i % WORD_BITS)) != 0
157    }
158
159    /// Sets bit `i` to `value` (`IGRAPH_BIT_SET` / `IGRAPH_BIT_CLEAR`).
160    ///
161    /// # Panics
162    /// If `i >= len`.
163    pub fn set(&mut self, i: usize, value: bool) {
164        self.check_index(i);
165        let w = &mut self.words_mut()[i / WORD_BITS];
166        if value {
167            *w |= 1 << (i % WORD_BITS);
168        } else {
169            *w &= !(1 << (i % WORD_BITS));
170        }
171    }
172
173    /// Flips bit `i` and returns its new value.
174    ///
175    /// # Panics
176    /// If `i >= len`.
177    pub fn toggle(&mut self, i: usize) -> bool {
178        let v = !self.get(i);
179        self.set(i, v);
180        v
181    }
182
183    /// Sets bit `i` and returns whether it was *not* set before (like
184    /// [`HashSet::insert`](std::collections::HashSet::insert)).
185    ///
186    /// # Panics
187    /// If `i >= len`.
188    pub fn insert(&mut self, i: usize) -> bool {
189        let was = self.get(i);
190        self.set(i, true);
191        !was
192    }
193
194    /// Appends a bit at the end, growing the bitset by one.
195    pub fn push(&mut self, value: bool) {
196        let n = self.len();
197        self.resize(n + 1);
198        self.set(n, value);
199    }
200
201    /// Number of set bits (the population count)
202    /// ([`igraph_bitset_popcount`](https://igraph.org/c/html/latest/igraph-Data-structures.html#igraph_bitset_popcount)).
203    pub fn count_ones(&self) -> usize {
204        unsafe { igraph_bitset_popcount(self) as usize }
205    }
206
207    /// Number of zero bits.
208    pub fn count_zeros(&self) -> usize {
209        self.len() - self.count_ones()
210    }
211
212    /// Number of zeros before the first one, starting from the *most*
213    /// significant bit (`len` if all zero)
214    /// ([`igraph_bitset_countl_zero`](https://igraph.org/c/html/latest/igraph-Data-structures.html#igraph_bitset_countl_zero)).
215    pub fn leading_zeros(&self) -> usize {
216        unsafe { igraph_bitset_countl_zero(self) as usize }
217    }
218
219    /// Number of ones before the first zero, starting from the *most*
220    /// significant bit
221    /// ([`igraph_bitset_countl_one`](https://igraph.org/c/html/latest/igraph-Data-structures.html#igraph_bitset_countl_one)).
222    pub fn leading_ones(&self) -> usize {
223        unsafe { igraph_bitset_countl_one(self) as usize }
224    }
225
226    /// Number of zeros before the first one, starting from bit 0 (`len` if
227    /// all zero); i.e. the index of the first set bit
228    /// ([`igraph_bitset_countr_zero`](https://igraph.org/c/html/latest/igraph-Data-structures.html#igraph_bitset_countr_zero)).
229    pub fn trailing_zeros(&self) -> usize {
230        unsafe { igraph_bitset_countr_zero(self) as usize }
231    }
232
233    /// Number of ones before the first zero, starting from bit 0
234    /// ([`igraph_bitset_countr_one`](https://igraph.org/c/html/latest/igraph-Data-structures.html#igraph_bitset_countr_one)).
235    pub fn trailing_ones(&self) -> usize {
236        unsafe { igraph_bitset_countr_one(self) as usize }
237    }
238
239    /// Whether all bits are one (true for an empty bitset)
240    /// ([`igraph_bitset_is_all_one`](https://igraph.org/c/html/latest/igraph-Data-structures.html#igraph_bitset_is_all_one)).
241    pub fn all(&self) -> bool {
242        unsafe { igraph_bitset_is_all_one(self) }
243    }
244
245    /// Whether some bit is one
246    /// ([`igraph_bitset_is_any_one`](https://igraph.org/c/html/latest/igraph-Data-structures.html#igraph_bitset_is_any_one)).
247    pub fn any(&self) -> bool {
248        unsafe { igraph_bitset_is_any_one(self) }
249    }
250
251    /// Whether all bits are zero (true for an empty bitset)
252    /// ([`igraph_bitset_is_all_zero`](https://igraph.org/c/html/latest/igraph-Data-structures.html#igraph_bitset_is_all_zero)).
253    pub fn none(&self) -> bool {
254        unsafe { igraph_bitset_is_all_zero(self) }
255    }
256
257    /// Whether some bit is zero
258    /// ([`igraph_bitset_is_any_zero`](https://igraph.org/c/html/latest/igraph-Data-structures.html#igraph_bitset_is_any_zero)).
259    pub fn not_all(&self) -> bool {
260        unsafe { igraph_bitset_is_any_zero(self) }
261    }
262
263    /// Sets every bit to `value`
264    /// ([`igraph_bitset_fill`](https://igraph.org/c/html/latest/igraph-Data-structures.html#igraph_bitset_fill)).
265    pub fn fill(&mut self, value: bool) {
266        unsafe { igraph_bitset_fill(self, value) }
267    }
268
269    /// Sets every bit to zero, keeping the length
270    /// ([`igraph_bitset_null`](https://igraph.org/c/html/latest/igraph-Data-structures.html#igraph_bitset_null)).
271    pub fn clear(&mut self) {
272        unsafe { igraph_bitset_null(self) }
273    }
274
275    /// Iterates over all the bits, from bit 0.
276    pub fn iter(&self) -> impl Iterator<Item = bool> + '_ {
277        (0..self.len()).map(move |i| self.get(i))
278    }
279
280    /// Iterates over the positions of the set bits, in increasing order,
281    /// skipping whole zero words.
282    pub fn iter_ones(&self) -> impl Iterator<Item = usize> + '_ {
283        let len = self.len();
284        self.words().iter().enumerate().flat_map(move |(k, &w)| {
285            let mut w = w;
286            std::iter::from_fn(move || {
287                if w == 0 {
288                    return None;
289                }
290                let b = w.trailing_zeros() as usize;
291                w &= w - 1;
292                Some(k * WORD_BITS + b)
293            })
294            .take_while(move |&i| i < len)
295        })
296    }
297
298    /// The bits as a `Vec<bool>`.
299    pub fn to_vec(&self) -> Vec<bool> {
300        self.iter().collect()
301    }
302
303    fn binary(
304        &self,
305        other: &Self,
306        op: unsafe extern "C" fn(*mut Self, *const Self, *const Self),
307    ) -> Self {
308        assert_eq!(self.len(), other.len(), "bitsets of different lengths");
309        let mut res = Self::new(self.len());
310        unsafe { op(&mut res, self, other) };
311        res
312    }
313
314    /// Bitwise AND ([`igraph_bitset_and`](https://igraph.org/c/html/latest/igraph-Data-structures.html#igraph_bitset_and)).
315    ///
316    /// # Panics
317    /// If the lengths differ.
318    pub fn and(&self, other: &Self) -> Self {
319        self.binary(other, igraph_bitset_and)
320    }
321
322    /// Bitwise OR ([`igraph_bitset_or`](https://igraph.org/c/html/latest/igraph-Data-structures.html#igraph_bitset_or)).
323    ///
324    /// # Panics
325    /// If the lengths differ.
326    pub fn or(&self, other: &Self) -> Self {
327        self.binary(other, igraph_bitset_or)
328    }
329
330    /// Bitwise XOR ([`igraph_bitset_xor`](https://igraph.org/c/html/latest/igraph-Data-structures.html#igraph_bitset_xor)).
331    ///
332    /// # Panics
333    /// If the lengths differ.
334    pub fn xor(&self, other: &Self) -> Self {
335        self.binary(other, igraph_bitset_xor)
336    }
337
338    /// Bitwise complement ([`igraph_bitset_not`](https://igraph.org/c/html/latest/igraph-Data-structures.html#igraph_bitset_not)).
339    pub fn complement(&self) -> Self {
340        let mut res = Self::new(self.len());
341        unsafe { igraph_bitset_not(&mut res, self) };
342        res
343    }
344
345    /// Replaces the content with a copy of `other`, reusing the storage
346    /// when possible ([`igraph_bitset_update`](https://igraph.org/c/html/latest/igraph-Data-structures.html#igraph_bitset_update)).
347    pub fn update(&mut self, other: &Self) {
348        crate::error::check(unsafe { igraph_bitset_update(self, other) })
349            .expect("igraph failed to copy a bitset");
350    }
351}
352
353impl Drop for igraph_bitset_t {
354    /// Frees the storage with `igraph_bitset_destroy`.
355    fn drop(&mut self) {
356        if !self.stor_begin.is_null() {
357            unsafe { igraph_bitset_destroy(self) };
358            self.stor_begin = std::ptr::null_mut();
359        }
360    }
361}
362
363impl Clone for igraph_bitset_t {
364    /// Deep copy with `igraph_bitset_init_copy`.
365    fn clone(&self) -> Self {
366        crate::error::ensure_init();
367        let mut raw = MaybeUninit::<Self>::uninit();
368        crate::error::check(unsafe { igraph_bitset_init_copy(raw.as_mut_ptr(), self) })
369            .expect("igraph failed to copy a bitset");
370        unsafe { raw.assume_init() }
371    }
372}
373
374impl Default for igraph_bitset_t {
375    /// An empty bitset.
376    fn default() -> Self {
377        Self::new(0)
378    }
379}
380
381impl PartialEq for igraph_bitset_t {
382    /// Two bitsets are equal when they have the same length and bits (the
383    /// unused padding bits of the last word are ignored).
384    fn eq(&self, other: &Self) -> bool {
385        self.len() == other.len() && self.iter().eq(other.iter())
386    }
387}
388
389impl Eq for igraph_bitset_t {}
390
391impl fmt::Display for igraph_bitset_t {
392    /// Writes the bits as `0`/`1` characters, most significant (highest
393    /// index) first, like `igraph_bitset_print`.
394    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
395        let s: String = (0..self.len())
396            .rev()
397            .map(|i| if self.get(i) { '1' } else { '0' })
398            .collect();
399        f.pad(&s)
400    }
401}
402
403impl FromIterator<bool> for igraph_bitset_t {
404    fn from_iter<I: IntoIterator<Item = bool>>(iter: I) -> Self {
405        let bits: Vec<bool> = iter.into_iter().collect();
406        Self::from_bools(&bits)
407    }
408}
409
410impl From<&[bool]> for igraph_bitset_t {
411    fn from(bits: &[bool]) -> Self {
412        Self::from_bools(bits)
413    }
414}
415
416impl From<&igraph_bitset_t> for Vec<bool> {
417    fn from(b: &igraph_bitset_t) -> Self {
418        b.to_vec()
419    }
420}
421
422macro_rules! bitset_op {
423    ($trait:ident, $method:ident, $assign_trait:ident, $assign:ident, $c:ident) => {
424        impl ops::$trait for &igraph_bitset_t {
425            type Output = igraph_bitset_t;
426            /// # Panics
427            /// If the lengths differ.
428            fn $method(self, rhs: Self) -> igraph_bitset_t {
429                self.binary(rhs, $c)
430            }
431        }
432        impl ops::$assign_trait<&igraph_bitset_t> for igraph_bitset_t {
433            /// # Panics
434            /// If the lengths differ.
435            fn $assign(&mut self, rhs: &igraph_bitset_t) {
436                assert_eq!(self.len(), rhs.len(), "bitsets of different lengths");
437                let me: *mut igraph_bitset_t = self;
438                // igraph computes word by word, so aliasing dest and src is fine.
439                unsafe { $c(me, me, rhs) };
440            }
441        }
442    };
443}
444
445bitset_op!(
446    BitAnd,
447    bitand,
448    BitAndAssign,
449    bitand_assign,
450    igraph_bitset_and
451);
452bitset_op!(BitOr, bitor, BitOrAssign, bitor_assign, igraph_bitset_or);
453bitset_op!(
454    BitXor,
455    bitxor,
456    BitXorAssign,
457    bitxor_assign,
458    igraph_bitset_xor
459);
460
461impl ops::Not for &igraph_bitset_t {
462    type Output = igraph_bitset_t;
463    fn not(self) -> igraph_bitset_t {
464        self.complement()
465    }
466}
467
468// The storage is uniquely owned and only mutated through `&mut`.
469unsafe impl Send for igraph_bitset_t {}
470unsafe impl Sync for igraph_bitset_t {}
igraph/bitset.rs

igraph/
bitset.rs
