antecedent_graph/
workspace.rs

1//! Reusable traversal workspace.
2//!
3//! SPDX-License-Identifier: MIT OR Apache-2.0
4
5use crate::types::DenseNodeId;
6
7/// Bitset over dense node ids.
8#[derive(Clone, Debug, Default)]
9pub struct BitSet {
10    words: Vec<u64>,
11    len: usize,
12}
13
14impl BitSet {
15    /// Create a bitset for `len` bits.
16    #[must_use]
17    pub fn with_len(len: usize) -> Self {
18        Self { words: vec![0; len.div_ceil(64)], len }
19    }
20
21    /// Clear all bits (retain capacity).
22    pub fn clear(&mut self) {
23        for w in &mut self.words {
24            *w = 0;
25        }
26    }
27
28    /// Ensure capacity for `len` bits.
29    pub fn resize(&mut self, len: usize) {
30        self.len = len;
31        self.words.resize(len.div_ceil(64), 0);
32    }
33
34    /// Number of addressable bits.
35    #[must_use]
36    pub const fn bit_len(&self) -> usize {
37        self.len
38    }
39
40    /// Borrow the underlying word storage (for hashing / memo keys).
41    #[must_use]
42    pub fn words(&self) -> &[u64] {
43        &self.words
44    }
45
46    /// Set bit.
47    pub fn insert(&mut self, id: DenseNodeId) {
48        let i = id.as_usize();
49        debug_assert!(i < self.len);
50        self.words[i / 64] |= 1u64 << (i % 64);
51    }
52
53    /// Clear one bit.
54    pub fn remove(&mut self, id: DenseNodeId) {
55        let i = id.as_usize();
56        if i >= self.len {
57            return;
58        }
59        self.words[i / 64] &= !(1u64 << (i % 64));
60    }
61
62    /// Test bit.
63    #[must_use]
64    pub fn contains(&self, id: DenseNodeId) -> bool {
65        let i = id.as_usize();
66        if i >= self.len {
67            return false;
68        }
69        (self.words[i / 64] >> (i % 64)) & 1 == 1
70    }
71
72    /// Whether any bit is set.
73    #[must_use]
74    pub fn any(&self) -> bool {
75        self.words.iter().any(|w| *w != 0)
76    }
77
78    /// Number of set bits.
79    #[must_use]
80    pub fn count_ones(&self) -> usize {
81        self.words.iter().map(|w| w.count_ones() as usize).sum()
82    }
83
84    /// Collect set bit indices as dense node ids (ascending).
85    #[must_use]
86    pub fn to_dense_ids(&self) -> Vec<DenseNodeId> {
87        let mut out = Vec::with_capacity(self.count_ones());
88        for i in 0..self.len {
89            let Ok(raw) = u32::try_from(i) else {
90                break;
91            };
92            let id = DenseNodeId::from_raw(raw);
93            if self.contains(id) {
94                out.push(id);
95            }
96        }
97        out
98    }
99
100    /// Union `other` into `self` (same length).
101    pub fn union_with(&mut self, other: &Self) {
102        debug_assert_eq!(self.len, other.len);
103        for (a, b) in self.words.iter_mut().zip(other.words.iter()) {
104            *a |= *b;
105        }
106    }
107
108    /// Intersect `other` into `self` (same length).
109    pub fn intersect_with(&mut self, other: &Self) {
110        debug_assert_eq!(self.len, other.len);
111        for (a, b) in self.words.iter_mut().zip(other.words.iter()) {
112            *a &= *b;
113        }
114    }
115
116    /// Subtract `other` from `self` (same length).
117    pub fn difference_with(&mut self, other: &Self) {
118        debug_assert_eq!(self.len, other.len);
119        for (a, b) in self.words.iter_mut().zip(other.words.iter()) {
120            *a &= !*b;
121        }
122    }
123
124    /// Whether `self` is a subset of `other`.
125    #[must_use]
126    pub fn is_subset_of(&self, other: &Self) -> bool {
127        debug_assert_eq!(self.len, other.len);
128        self.words.iter().zip(other.words.iter()).all(|(a, b)| a & !b == 0)
129    }
130
131    /// Whether `self` equals `other`.
132    #[must_use]
133    pub fn equal_set(&self, other: &Self) -> bool {
134        self.len == other.len && self.words == other.words
135    }
136}
137
138impl std::hash::Hash for BitSet {
139    fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
140        self.len.hash(state);
141        self.words.hash(state);
142    }
143}
144
145impl PartialEq for BitSet {
146    fn eq(&self, other: &Self) -> bool {
147        self.equal_set(other)
148    }
149}
150
151impl Eq for BitSet {}
152
153/// Scratch space for graph traversals; may grow but is reused.
154#[derive(Clone, Debug, Default)]
155pub struct GraphWorkspace {
156    /// Visited set.
157    pub visited: BitSet,
158    /// BFS/DFS frontier.
159    pub frontier: Vec<DenseNodeId>,
160    /// Scratch node buffer.
161    pub scratch_nodes: Vec<DenseNodeId>,
162    /// Predecessor map (indexed by dense id).
163    pub predecessor: Vec<Option<DenseNodeId>>,
164}
165
166impl GraphWorkspace {
167    /// Prepare workspace for a graph with `n` nodes.
168    pub fn prepare(&mut self, n: usize) {
169        self.visited.resize(n);
170        self.visited.clear();
171        self.frontier.clear();
172        self.scratch_nodes.clear();
173        self.predecessor.clear();
174        self.predecessor.resize(n, None);
175    }
176}
antecedent_graph/workspace.rs

antecedent_graph/
workspace.rs
