resolvo 0.11.0

Fast package resolver written in Rust (CDCL based SAT solving)
Documentation 
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

use std::marker::PhantomData;

use bitvec::vec::BitVec;

use crate::id::DenseIndex;

/// A dense set keyed by a [`DenseIndex`]. Equivalent to a `HashSet<Id>` but
/// backed by a [`BitVec`], so test-and-set is O(1) with no hashing overhead.
/// Grows on demand to fit the largest inserted index.
pub struct IndexedSet<Id> {
    bits: BitVec,
    _marker: PhantomData<fn(Id) -> Id>,
}

impl<Id> Default for IndexedSet<Id> {
    fn default() -> Self {
        Self {
            bits: BitVec::new(),
            _marker: PhantomData,
        }
    }
}

impl<Id: DenseIndex> IndexedSet<Id> {
    /// Inserts `id`. Returns `true` if `id` was not already present.
    #[inline]
    pub fn insert(&mut self, id: Id) -> bool {
        let idx = id.to_index();
        if idx >= self.bits.len() {
            self.bits.resize(idx + 1, false);
        }
        // SAFETY: `resize` above guarantees `idx < self.bits.len()`.
        !unsafe { self.bits.replace_unchecked(idx, true) }
    }

    /// Returns `true` if `id` is present.
    #[inline]
    pub fn contains(&self, id: Id) -> bool {
        self.bits.get(id.to_index()).is_some_and(|b| *b)
    }
}