resharp_algebra/
nulls.rs

1use rustc_hash::FxHashMap;
2use std::fmt::Debug;
3
4#[derive(Clone, Copy, PartialEq, Hash, Eq, PartialOrd, Ord)]
5pub struct Nullability(pub u8);
6
7impl Debug for Nullability {
8    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
9        let num = &self.0;
10        f.write_str(format!("{num}").as_str())
11    }
12}
13impl Nullability {
14    pub const NEVER: Nullability = Nullability(0b000);
15    pub const CENTER: Nullability = Nullability(0b001);
16    pub const ALWAYS: Nullability = Nullability(0b111);
17    pub const BEGIN: Nullability = Nullability(0b010);
18    pub const END: Nullability = Nullability(0b100);
19    pub const NONBEGIN: Nullability = Nullability(0b011);
20    pub const EMPTYSTRING: Nullability = Nullability(0b110);
21    #[inline]
22    pub fn has(self, flag: Nullability) -> bool {
23        self.0 & flag.0 != 0
24    }
25    #[inline]
26    pub fn and(self, other: Nullability) -> Nullability {
27        Nullability(self.0 & other.0)
28    }
29    #[inline]
30    pub fn or(self, other: Nullability) -> Nullability {
31        Nullability(self.0 | other.0)
32    }
33    #[inline]
34    pub fn not(self) -> Nullability {
35        Nullability(!self.0)
36    }
37}
38
39#[derive(PartialEq, Eq, Clone, Hash)]
40pub struct NullState {
41    pub mask: Nullability,
42    pub rel: u32,
43}
44impl NullState {
45    pub fn new(mask: Nullability, rel: u32) -> NullState {
46        NullState { mask, rel }
47    }
48    pub fn new0(mask: Nullability) -> NullState {
49        NullState { mask, rel: 0 }
50    }
51
52    pub fn is_center_nullable(&self) -> bool {
53        self.mask.and(Nullability::CENTER) != Nullability::NEVER
54    }
55    pub fn is_mask_nullable(&self, mask: Nullability) -> bool {
56        self.mask.and(mask) != Nullability::NEVER
57    }
58}
59impl Ord for NullState {
60    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
61        other
62            .rel
63            .cmp(&self.rel)
64            .then_with(|| self.mask.cmp(&other.mask))
65    }
66}
67impl PartialOrd for NullState {
68    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
69        Some(self.cmp(other))
70    }
71}
72
73impl Debug for NullState {
74    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
75        f.debug_set().entry(&self.mask).entry(&self.rel).finish()
76    }
77}
78
79type Nulls = BTreeSet<NullState>;
80
81#[derive(Clone, Copy, PartialEq, Hash, Eq, Debug, PartialOrd, Ord)]
82pub struct NullsId(pub u32);
83impl NullsId {
84    pub const EMPTY: NullsId = NullsId(0);
85    pub const ALWAYS0: NullsId = NullsId(1);
86    pub const CENTER0: NullsId = NullsId(2);
87    pub const BEGIN0: NullsId = NullsId(3);
88    pub const END0: NullsId = NullsId(4);
89}
90
91use std::{collections::BTreeSet, hash::Hash};
92
93#[repr(u8)]
94#[derive(Hash, PartialEq, Eq)]
95enum Operation {
96    Or,
97    Inter,
98}
99
100#[derive(Hash, PartialEq, Eq)]
101struct Key {
102    op: Operation,
103    left: NullsId,
104    right: NullsId,
105}
106
107pub struct NullsBuilder {
108    cache: FxHashMap<Nulls, NullsId>,
109    created: FxHashMap<Key, NullsId>,
110    pub array: Vec<Nulls>,
111}
112
113impl Default for NullsBuilder {
114    fn default() -> Self {
115        Self::new()
116    }
117}
118
119impl NullsBuilder {
120    pub fn new() -> NullsBuilder {
121        let mut inst = Self {
122            cache: FxHashMap::default(),
123            array: Vec::new(),
124            created: FxHashMap::default(),
125        };
126        let _ = inst.init(BTreeSet::new());
127        let _ = inst.init1(NullState::new0(Nullability::ALWAYS));
128        let _ = inst.init1(NullState::new0(Nullability::CENTER));
129        let _ = inst.init1(NullState::new0(Nullability::BEGIN));
130        let _ = inst.init1(NullState::new0(Nullability::END));
131        inst
132    }
133
134    fn init(&mut self, inst: Nulls) -> NullsId {
135        let new_id = NullsId(self.cache.len() as u32);
136        self.cache.insert(inst.clone(), new_id);
137        self.array.push(inst);
138        new_id
139    }
140
141    fn init1(&mut self, inst: NullState) -> NullsId {
142        let mut b = BTreeSet::new();
143        b.insert(inst);
144        let new_id = NullsId(self.cache.len() as u32);
145        self.cache.insert(b.clone(), new_id);
146        self.array.push(b);
147        new_id
148    }
149
150    pub fn get_set_ref(&self, set_id: NullsId) -> &Nulls {
151        &self.array[set_id.0 as usize]
152    }
153
154    pub fn get_id(&mut self, inst: Nulls) -> NullsId {
155        match self.cache.get(&inst) {
156            Some(&id) => id,
157            None => self.init(inst),
158        }
159    }
160}
161
162impl NullsBuilder {
163    #[inline]
164    fn is_created(&self, inst: &Key) -> Option<&NullsId> {
165        self.created.get(inst)
166    }
167
168    #[inline]
169    pub fn or_id(&mut self, set1: NullsId, set2: NullsId) -> NullsId {
170        if set1 > set2 {
171            return self.or_id(set2, set1);
172        }
173        let key = Key {
174            op: Operation::Or,
175            left: set1,
176            right: set2,
177        };
178        if let Some(v) = self.is_created(&key) {
179            return *v;
180        }
181        if set1 == set2 {
182            return set1;
183        }
184        if set1 == NullsId::ALWAYS0 && set2 == NullsId::END0 {
185            return NullsId::ALWAYS0;
186        }
187        if set1 == NullsId::END0 && set2 == NullsId::ALWAYS0 {
188            return NullsId::ALWAYS0;
189        }
190
191        let all = self.get_set_ref(set1) | self.get_set_ref(set2);
192        let mut result: BTreeSet<&NullState> = BTreeSet::new();
193        for m in all.iter().rev() {
194            let found = result.iter().find(|v| v.mask == m.mask && v.rel == m.rel);
195            if found.is_none() {
196                result.insert(m);
197            }
198        }
199
200        let result = result
201            .into_iter().cloned()
202            .collect::<BTreeSet<_>>();
203
204        let new_id = self.get_id(result);
205        self.created.insert(key, new_id);
206        new_id
207    }
208
209    #[inline]
210    pub fn and_id(&mut self, set1: NullsId, set2: NullsId) -> NullsId {
211        if NullsId::EMPTY == set1 {
212            return NullsId::EMPTY;
213        }
214        if NullsId::EMPTY == set2 {
215            return NullsId::EMPTY;
216        }
217        if set1 > set2 {
218            return self.and_id(set2, set1);
219        }
220        let key = Key {
221            op: Operation::Inter,
222            left: set1,
223            right: set2,
224        };
225        if let Some(v) = self.is_created(&key) {
226            return *v;
227        }
228        if set1 == set2 {
229            return set1;
230        }
231        if set1 == NullsId::ALWAYS0 && set2 == NullsId::END0 {
232            return NullsId::END0;
233        }
234        if set1 == NullsId::END0 && set2 == NullsId::ALWAYS0 {
235            return NullsId::END0;
236        }
237
238        let result = self.get_id(self.get_set_ref(set1) | self.get_set_ref(set2));
239        self.created.insert(key, result);
240        result
241    }
242
243    #[inline]
244    pub fn and_mask(&mut self, set1: NullsId, mask: Nullability) -> NullsId {
245        if NullsId::EMPTY == set1 || mask == Nullability::NEVER {
246            return NullsId::EMPTY;
247        }
248        if mask == Nullability::ALWAYS {
249            return set1;
250        }
251        let remaining = self
252            .get_set_ref(set1)
253            .iter()
254            .filter_map(|v| {
255                let newmask = v.mask.and(mask);
256                if newmask == Nullability::NEVER {
257                    None
258                } else {
259                    Some(NullState::new(newmask, v.rel))
260                }
261            })
262            .collect::<BTreeSet<_>>();
263
264        self.get_id(remaining)
265    }
266
267    #[inline]
268    pub fn not_id(&mut self, set_id: NullsId) -> NullsId {
269        if set_id == NullsId::EMPTY {
270            return NullsId::ALWAYS0;
271        }
272        if set_id == NullsId::ALWAYS0 {
273            return NullsId::EMPTY;
274        }
275        if set_id == NullsId::BEGIN0 {
276            return self.or_id(NullsId::CENTER0, NullsId::END0);
277        }
278        if set_id == NullsId::END0 {
279            return self.or_id(NullsId::CENTER0, NullsId::BEGIN0);
280        }
281        NullsId::EMPTY
282    }
283
284    #[inline]
285    pub fn add_rel(&mut self, set_id: NullsId, rel: u32) -> NullsId {
286        if rel == 0 || rel == u32::MAX {
287            return set_id;
288        }
289        let res = self.get_set_ref(set_id).clone();
290        let with_rel = res
291            .iter()
292            .map(|v| NullState::new(v.mask, v.rel + rel))
293            .collect();
294
295        self.get_id(with_rel)
296    }
297}
resharp_algebra/nulls.rs

resharp_algebra/
nulls.rs
