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 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: FxHashMap<Nulls, NullsId>,
117 created: FxHashMap<Key, NullsId>,
118 pub array: Vec<Nulls>,
119}
120
121impl NullsBuilder {
122 pub fn new() -> NullsBuilder {
123 let mut inst = Self {
124 cache: FxHashMap::default(),
125 array: Vec::new(),
126 created: FxHashMap::default(),
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}