resharp_algebra/
nulls.rs

1use std::collections::HashMap;
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        return NullState { mask, rel };
47    }
48    pub fn new0(mask: Nullability) -> NullState {
49        return 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        match other.rel.partial_cmp(&self.rel) {
70            Some(core::cmp::Ordering::Equal) => {}
71            ord => return ord,
72        }
73        match self.mask.partial_cmp(&other.mask) {
74            Some(core::cmp::Ordering::Equal) => {}
75            ord => return ord,
76        }
77        Some(core::cmp::Ordering::Equal)
78    }
79}
80
81impl Debug for NullState {
82    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
83        f.debug_set().entry(&self.mask).entry(&self.rel).finish()
84    }
85}
86
87type Nulls = BTreeSet<NullState>;
88
89#[derive(Clone, Copy, PartialEq, Hash, Eq, Debug, PartialOrd, Ord)]
90pub struct NullsId(pub u32);
91impl NullsId {
92    pub const EMPTY: NullsId = NullsId(0);
93    pub const ALWAYS0: NullsId = NullsId(1);
94    pub const CENTER0: NullsId = NullsId(2);
95    pub const BEGIN0: NullsId = NullsId(3);
96    pub const END0: NullsId = NullsId(4);
97}
98
99use std::{collections::BTreeSet, hash::Hash};
100
101#[repr(u8)]
102#[derive(Hash, PartialEq, Eq)]
103enum Operation {
104    Or,
105    Inter,
106}
107
108#[derive(Hash, PartialEq, Eq)]
109struct Key {
110    op: Operation,
111    left: NullsId,
112    right: NullsId,
113}
114
115pub struct NullsBuilder {
116    cache: HashMap<Nulls, NullsId>,
117    created: HashMap<Key, NullsId>,
118    pub array: Vec<Nulls>,
119}
120
121impl NullsBuilder {
122    pub fn new() -> NullsBuilder {
123        let mut inst = Self {
124            cache: HashMap::new(),
125            array: Vec::new(),
126            created: HashMap::new(),
127        };
128        let _ = inst.init(BTreeSet::new());
129        let _ = inst.init1(NullState::new0(Nullability::ALWAYS));
130        let _ = inst.init1(NullState::new0(Nullability::CENTER));
131        let _ = inst.init1(NullState::new0(Nullability::BEGIN));
132        let _ = inst.init1(NullState::new0(Nullability::END));
133        inst
134    }
135
136    fn init(&mut self, inst: Nulls) -> NullsId {
137        let new_id = NullsId(self.cache.len() as u32);
138        self.cache.insert(inst.clone(), new_id);
139        self.array.push(inst);
140        new_id
141    }
142
143    fn init1(&mut self, inst: NullState) -> NullsId {
144        let mut b = BTreeSet::new();
145        b.insert(inst);
146        let new_id = NullsId(self.cache.len() as u32);
147        self.cache.insert(b.clone(), new_id);
148        self.array.push(b);
149        new_id
150    }
151
152    pub fn get_set_ref(&self, set_id: NullsId) -> &Nulls {
153        &self.array[set_id.0 as usize]
154    }
155
156    pub fn get_id(&mut self, inst: Nulls) -> NullsId {
157        match self.cache.get(&inst) {
158            Some(&id) => id,
159            None => self.init(inst),
160        }
161    }
162}
163
164impl NullsBuilder {
165    #[inline]
166    fn is_created(&self, inst: &Key) -> Option<&NullsId> {
167        self.created.get(inst)
168    }
169
170    #[inline]
171    pub fn or_id(&mut self, set1: NullsId, set2: NullsId) -> NullsId {
172        if set1 > set2 {
173            return self.or_id(set2, set1);
174        }
175        let key = Key {
176            op: Operation::Or,
177            left: set1,
178            right: set2,
179        };
180        if let Some(v) = self.is_created(&key) {
181            return *v;
182        }
183        if set1 == set2 {
184            return set1;
185        }
186        if set1 == NullsId::ALWAYS0 && set2 == NullsId::END0 {
187            return NullsId::ALWAYS0;
188        }
189        if set1 == NullsId::END0 && set2 == NullsId::ALWAYS0 {
190            return NullsId::ALWAYS0;
191        }
192
193        let all = self.get_set_ref(set1) | self.get_set_ref(set2);
194        let mut result: BTreeSet<&NullState> = BTreeSet::new();
195        for m in all.iter().rev() {
196            let found = result.iter().find(|v| v.mask == m.mask && v.rel == m.rel);
197            if found.is_none() {
198                result.insert(m);
199            }
200        }
201
202        let result = result
203            .into_iter()
204            .map(|v| v.clone())
205            .collect::<BTreeSet<_>>();
206
207        let new_id = self.get_id(result);
208        self.created.insert(key, new_id);
209        new_id
210    }
211
212    #[inline]
213    pub fn and_id(&mut self, set1: NullsId, set2: NullsId) -> NullsId {
214        if NullsId::EMPTY == set1 {
215            return NullsId::EMPTY;
216        }
217        if NullsId::EMPTY == set2 {
218            return NullsId::EMPTY;
219        }
220        if set1 > set2 {
221            return self.and_id(set2, set1);
222        }
223        let key = Key {
224            op: Operation::Inter,
225            left: set1,
226            right: set2,
227        };
228        if let Some(v) = self.is_created(&key) {
229            return *v;
230        }
231        if set1 == set2 {
232            return set1;
233        }
234        if set1 == NullsId::ALWAYS0 && set2 == NullsId::END0 {
235            return NullsId::END0;
236        }
237        if set1 == NullsId::END0 && set2 == NullsId::ALWAYS0 {
238            return NullsId::END0;
239        }
240
241        let result = self.get_id(self.get_set_ref(set1) | self.get_set_ref(set2));
242        self.created.insert(key, result);
243        result
244    }
245
246    #[inline]
247    pub fn and_mask(&mut self, set1: NullsId, mask: Nullability) -> NullsId {
248        if NullsId::EMPTY == set1 || mask == Nullability::NEVER {
249            return NullsId::EMPTY;
250        }
251        if mask == Nullability::ALWAYS {
252            return set1;
253        }
254        let remaining = self
255            .get_set_ref(set1)
256            .iter()
257            .filter_map(|v| {
258                let newmask = v.mask.and(mask);
259                if newmask == Nullability::NEVER {
260                    None
261                } else {
262                    Some(NullState::new(newmask, v.rel))
263                }
264            })
265            .collect::<BTreeSet<_>>();
266
267        self.get_id(remaining)
268    }
269
270    #[inline]
271    pub fn not_id(&mut self, set_id: NullsId) -> NullsId {
272        if set_id == NullsId::EMPTY {
273            return NullsId::ALWAYS0;
274        }
275        if set_id == NullsId::ALWAYS0 {
276            return NullsId::EMPTY;
277        }
278        if set_id == NullsId::BEGIN0 {
279            return self.or_id(NullsId::CENTER0, NullsId::END0);
280        }
281        if set_id == NullsId::END0 {
282            return self.or_id(NullsId::CENTER0, NullsId::BEGIN0);
283        }
284        NullsId::EMPTY
285    }
286
287    #[inline]
288    pub fn add_rel(&mut self, set_id: NullsId, rel: u32) -> NullsId {
289        if rel == 0 || rel == u32::MAX {
290            return set_id;
291        }
292        let res = self.get_set_ref(set_id).clone();
293        let with_rel = res
294            .iter()
295            .map(|v| NullState::new(v.mask, v.rel + rel))
296            .collect();
297
298        self.get_id(with_rel)
299    }
300}
resharp_algebra/nulls.rs

resharp_algebra/
nulls.rs
