logic_form/
utils.rs

1use crate::{Lit, Var};
2use std::{
3    ops::{Deref, DerefMut, Index, IndexMut},
4    ptr, slice,
5};
6
7#[derive(Debug, Default, Clone)]
8pub struct VarMap<T> {
9    map: Vec<T>,
10}
11
12impl<T: Default> VarMap<T> {
13    #[inline]
14    pub fn new() -> Self {
15        Self::default()
16    }
17
18    #[inline]
19    pub fn new_with(var: Var) -> Self {
20        let mut res = Self::new();
21        res.reserve(var);
22        res
23    }
24
25    #[inline]
26    pub fn reserve(&mut self, var: Var) {
27        let len = Into::<usize>::into(var) + 1;
28        if self.len() < len {
29            self.map.resize_with(len, Default::default)
30        }
31    }
32
33    #[inline]
34    pub fn swap(&mut self, x: Var, y: Var) {
35        let px = ptr::addr_of_mut!(self[x]);
36        let py = ptr::addr_of_mut!(self[y]);
37        unsafe {
38            ptr::swap(px, py);
39        }
40    }
41}
42
43impl<T> Index<Var> for VarMap<T> {
44    type Output = T;
45
46    #[inline]
47    fn index(&self, index: Var) -> &Self::Output {
48        #[cfg(not(debug_assertions))]
49        unsafe {
50            self.map.get_unchecked(index.0 as usize)
51        }
52        #[cfg(debug_assertions)]
53        &self.map[index.0 as usize]
54    }
55}
56
57impl<T> IndexMut<Var> for VarMap<T> {
58    #[inline]
59    fn index_mut(&mut self, index: Var) -> &mut Self::Output {
60        #[cfg(not(debug_assertions))]
61        unsafe {
62            self.map.get_unchecked_mut(index.0 as usize)
63        }
64        #[cfg(debug_assertions)]
65        &mut self.map[index.0 as usize]
66    }
67}
68
69impl<T> Index<Lit> for VarMap<T> {
70    type Output = T;
71
72    #[inline]
73    fn index(&self, index: Lit) -> &Self::Output {
74        #[cfg(not(debug_assertions))]
75        unsafe {
76            self.map.get_unchecked((index.0 >> 1) as usize)
77        }
78        #[cfg(debug_assertions)]
79        &self.map[(index.0 >> 1) as usize]
80    }
81}
82
83impl<T> IndexMut<Lit> for VarMap<T> {
84    #[inline]
85    fn index_mut(&mut self, index: Lit) -> &mut Self::Output {
86        #[cfg(not(debug_assertions))]
87        unsafe {
88            self.map.get_unchecked_mut((index.0 >> 1) as usize)
89        }
90        #[cfg(debug_assertions)]
91        &mut self.map[(index.0 >> 1) as usize]
92    }
93}
94
95impl<T> Deref for VarMap<T> {
96    type Target = Vec<T>;
97
98    #[inline]
99    fn deref(&self) -> &Self::Target {
100        &self.map
101    }
102}
103
104impl<T> DerefMut for VarMap<T> {
105    #[inline]
106    fn deref_mut(&mut self) -> &mut Self::Target {
107        &mut self.map
108    }
109}
110
111#[derive(Debug, Default, Clone)]
112pub struct LitMap<T> {
113    map: Vec<T>,
114}
115
116impl<T> LitMap<T> {
117    #[inline]
118    pub fn new() -> Self {
119        Self { map: Vec::new() }
120    }
121}
122
123impl<T: Default> LitMap<T> {
124    #[inline]
125    pub fn new_with(var: Var) -> Self {
126        let mut res = Self::new();
127        res.reserve(var);
128        res
129    }
130
131    #[inline]
132    pub fn reserve(&mut self, var: Var) {
133        let len = (Into::<usize>::into(var) + 1) * 2;
134        if self.len() < len {
135            self.map.resize_with(len, Default::default)
136        }
137    }
138
139    #[inline]
140    pub fn swap(&mut self, x: Lit, y: Lit) {
141        let px = ptr::addr_of_mut!(self[x]);
142        let py = ptr::addr_of_mut!(self[y]);
143        unsafe {
144            ptr::swap(px, py);
145        }
146    }
147}
148
149impl<T> Index<Lit> for LitMap<T> {
150    type Output = T;
151
152    #[inline]
153    fn index(&self, index: Lit) -> &Self::Output {
154        #[cfg(not(debug_assertions))]
155        unsafe {
156            self.map.get_unchecked(index.0 as usize)
157        }
158        #[cfg(debug_assertions)]
159        &self.map[index.0 as usize]
160    }
161}
162
163impl<T> IndexMut<Lit> for LitMap<T> {
164    #[inline]
165    fn index_mut(&mut self, index: Lit) -> &mut Self::Output {
166        #[cfg(not(debug_assertions))]
167        unsafe {
168            self.map.get_unchecked_mut(index.0 as usize)
169        }
170        #[cfg(debug_assertions)]
171        &mut self.map[index.0 as usize]
172    }
173}
174
175impl<T> Deref for LitMap<T> {
176    type Target = Vec<T>;
177
178    #[inline]
179    fn deref(&self) -> &Self::Target {
180        &self.map
181    }
182}
183
184impl<T> DerefMut for LitMap<T> {
185    #[inline]
186    fn deref_mut(&mut self) -> &mut Self::Target {
187        &mut self.map
188    }
189}
190
191#[derive(Default)]
192pub struct VarSet {
193    pub set: Vec<Var>,
194    pub has: VarMap<bool>,
195}
196
197impl VarSet {
198    #[inline]
199    pub fn new() -> Self {
200        Self::default()
201    }
202
203    #[inline]
204    pub fn new_with(var: Var) -> Self {
205        let mut res = Self::new();
206        res.reserve(var);
207        res
208    }
209
210    #[inline]
211    #[allow(clippy::len_without_is_empty)]
212    pub fn len(&self) -> u32 {
213        self.set.len() as _
214    }
215
216    #[inline]
217    pub fn reserve(&mut self, var: Var) {
218        self.has.reserve(var);
219    }
220
221    #[inline]
222    pub fn has(&self, var: Var) -> bool {
223        self.has[var]
224    }
225
226    #[inline]
227    pub fn insert(&mut self, var: Var) {
228        if !self.has[var] {
229            self.set.push(var);
230            self.has[var] = true;
231        }
232    }
233
234    #[inline]
235    pub fn clear(&mut self) {
236        for l in self.set.iter() {
237            self.has[*l] = false;
238        }
239        self.set.clear();
240    }
241
242    #[inline]
243    pub fn iter(&self) -> slice::Iter<Var> {
244        self.set.iter()
245    }
246
247    #[inline]
248    pub fn remove(&mut self, i: u32) {
249        let v = self.set.swap_remove(i as usize);
250        self.has[v] = false;
251    }
252
253    #[inline]
254    pub fn swap(&mut self, a: u32, b: u32) {
255        self.set.swap(a as usize, b as usize)
256    }
257
258    #[inline]
259    pub fn elements(&self) -> &[Var] {
260        &self.set
261    }
262}
263
264impl Index<u32> for VarSet {
265    type Output = Var;
266
267    #[inline]
268    fn index(&self, index: u32) -> &Self::Output {
269        &self.set[index as usize]
270    }
271}
272
273#[derive(Default, Debug, Clone)]
274pub struct LitSet {
275    set: Vec<Lit>,
276    has: LitMap<bool>,
277}
278
279impl LitSet {
280    #[inline]
281    pub fn new() -> Self {
282        Self::default()
283    }
284
285    #[inline]
286    pub fn new_with(var: Var) -> Self {
287        let mut res = Self::new();
288        res.reserve(var);
289        res
290    }
291
292    #[inline]
293    pub fn reserve(&mut self, var: Var) {
294        self.has.reserve(var);
295    }
296
297    #[inline]
298    pub fn insert(&mut self, lit: Lit) {
299        if !self.has[lit] {
300            self.set.push(lit);
301            self.has[lit] = true;
302        }
303    }
304
305    #[inline]
306    pub fn has(&self, lit: Lit) -> bool {
307        self.has[lit]
308    }
309
310    #[inline]
311    pub fn clear(&mut self) {
312        for l in self.set.iter() {
313            self.has[*l] = false;
314        }
315        self.set.clear();
316    }
317
318    #[inline]
319    pub fn iter(&self) -> slice::Iter<Lit> {
320        self.set.iter()
321    }
322
323    #[inline]
324    pub fn elements(&self) -> &[Lit] {
325        &self.set
326    }
327}
328
329#[derive(Default)]
330pub struct VarRef {
331    set: Vec<Var>,
332    refs: VarMap<u32>,
333    dirty: VarMap<bool>,
334}
335
336impl VarRef {
337    #[inline]
338    pub fn new() -> Self {
339        Self::default()
340    }
341
342    #[inline]
343    pub fn reserve(&mut self, var: Var) {
344        self.refs.reserve(var);
345        self.dirty.reserve(var);
346    }
347
348    #[inline]
349    pub fn inref(&mut self, var: Var) {
350        self.refs[var] += 1;
351        if self.refs[var] == 1 {
352            if self.dirty[var] {
353                self.dirty[var] = false
354            } else {
355                self.set.push(var)
356            }
357        }
358    }
359
360    #[inline]
361    pub fn deref(&mut self, var: Var) {
362        assert!(self.refs[var] > 0);
363        self.refs[var] -= 1;
364        if self.refs[var] == 0 {
365            self.dirty[var] = true;
366        }
367    }
368
369    #[inline]
370    pub fn iter(&self) -> VarRefIter {
371        VarRefIter {
372            varref: self as *const VarRef as *mut VarRef,
373            p: 0,
374        }
375    }
376}
377
378pub struct VarRefIter {
379    varref: *mut VarRef,
380    p: usize,
381}
382
383impl Iterator for VarRefIter {
384    type Item = Var;
385
386    #[inline]
387    fn next(&mut self) -> Option<Self::Item> {
388        let varref = unsafe { &mut *self.varref };
389        while self.p < varref.set.len() && varref.dirty[varref.set[self.p]] {
390            varref.dirty[varref.set[self.p]] = false;
391            varref.set.swap_remove(self.p);
392        }
393        if self.p >= varref.set.len() {
394            return None;
395        }
396        self.p += 1;
397        Some(varref.set[self.p - 1])
398    }
399}