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}