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 CENTER0: NullsId = NullsId(1);
86 pub const ALWAYS0: 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 _center = inst.init1(NullState::new0(Nullability::CENTER));
128 let _always = inst.init1(NullState::new0(Nullability::ALWAYS));
129 let _begin = inst.init1(NullState::new0(Nullability::BEGIN));
130 let _end = inst.init1(NullState::new0(Nullability::END));
131 debug_assert!(_center == NullsId::CENTER0);
132 debug_assert!(_always == NullsId::ALWAYS0);
133 debug_assert!(_begin == NullsId::BEGIN0);
134 debug_assert!(_end == NullsId::END0);
135 inst
136 }
137
138 fn init(&mut self, inst: Nulls) -> NullsId {
139 let new_id = NullsId(self.cache.len() as u32);
140 self.cache.insert(inst.clone(), new_id);
141 self.array.push(inst);
142 new_id
143 }
144
145 fn init1(&mut self, inst: NullState) -> NullsId {
146 let mut b = BTreeSet::new();
147 b.insert(inst);
148 let new_id = NullsId(self.cache.len() as u32);
149 self.cache.insert(b.clone(), new_id);
150 self.array.push(b);
151 new_id
152 }
153
154 pub fn get_set_ref(&self, set_id: NullsId) -> &Nulls {
155 &self.array[set_id.0 as usize]
156 }
157
158 pub fn get_id(&mut self, inst: Nulls) -> NullsId {
159 match self.cache.get(&inst) {
160 Some(&id) => id,
161 None => self.init(inst),
162 }
163 }
164}
165
166impl NullsBuilder {
167 #[inline]
168 fn is_created(&self, inst: &Key) -> Option<&NullsId> {
169 self.created.get(inst)
170 }
171
172 #[inline]
173 pub fn or_id(&mut self, set1: NullsId, set2: NullsId) -> NullsId {
174 if set1 > set2 {
175 return self.or_id(set2, set1);
176 }
177 let key = Key {
178 op: Operation::Or,
179 left: set1,
180 right: set2,
181 };
182 if let Some(v) = self.is_created(&key) {
183 return *v;
184 }
185 if set1 == set2 {
186 return set1;
187 }
188 if set1 == NullsId::ALWAYS0 && set2 == NullsId::END0 {
189 return NullsId::ALWAYS0;
190 }
191 if set1 == NullsId::END0 && set2 == NullsId::ALWAYS0 {
192 return NullsId::ALWAYS0;
193 }
194
195 let all = self.get_set_ref(set1) | self.get_set_ref(set2);
196 let mut result: BTreeSet<&NullState> = BTreeSet::new();
197 for m in all.iter().rev() {
198 let found = result.iter().find(|v| v.mask == m.mask && v.rel == m.rel);
199 if found.is_none() {
200 result.insert(m);
201 }
202 }
203
204 let result = result.into_iter().cloned().collect::<BTreeSet<_>>();
205
206 let new_id = self.get_id(result);
207 self.created.insert(key, new_id);
208 new_id
209 }
210
211 #[inline]
212 pub fn and_id(&mut self, set1: NullsId, set2: NullsId) -> NullsId {
213 if NullsId::EMPTY == set1 {
214 return NullsId::EMPTY;
215 }
216 if NullsId::EMPTY == set2 {
217 return NullsId::EMPTY;
218 }
219 if set1 > set2 {
220 return self.and_id(set2, set1);
221 }
222 let key = Key {
223 op: Operation::Inter,
224 left: set1,
225 right: set2,
226 };
227 if let Some(v) = self.is_created(&key) {
228 return *v;
229 }
230 if set1 == set2 {
231 return set1;
232 }
233 if set1 == NullsId::ALWAYS0 && set2 == NullsId::END0 {
234 return NullsId::END0;
235 }
236 if set1 == NullsId::END0 && set2 == NullsId::ALWAYS0 {
237 return NullsId::END0;
238 }
239
240 let result = self.get_id(self.get_set_ref(set1) | self.get_set_ref(set2));
241 self.created.insert(key, result);
242 result
243 }
244
245 #[inline]
246 pub fn and_mask(&mut self, set1: NullsId, mask: Nullability) -> NullsId {
247 if NullsId::EMPTY == set1 || mask == Nullability::NEVER {
248 return NullsId::EMPTY;
249 }
250 if mask == Nullability::ALWAYS {
251 return set1;
252 }
253 let remaining = self
254 .get_set_ref(set1)
255 .iter()
256 .filter_map(|v| {
257 let newmask = v.mask.and(mask);
258 if newmask == Nullability::NEVER {
259 None
260 } else {
261 Some(NullState::new(newmask, v.rel))
262 }
263 })
264 .collect::<BTreeSet<_>>();
265
266 self.get_id(remaining)
267 }
268
269 #[inline]
270 pub fn not_id(&mut self, set_id: NullsId) -> NullsId {
271 if set_id == NullsId::EMPTY {
272 return NullsId::ALWAYS0;
273 }
274 if set_id == NullsId::ALWAYS0 {
275 return NullsId::EMPTY;
276 }
277 if set_id == NullsId::BEGIN0 {
278 return self.or_id(NullsId::CENTER0, NullsId::END0);
279 }
280 if set_id == NullsId::END0 {
281 return self.or_id(NullsId::CENTER0, NullsId::BEGIN0);
282 }
283 NullsId::EMPTY
284 }
285
286 #[inline]
287 pub fn add_rel(&mut self, set_id: NullsId, rel: u32) -> NullsId {
288 if rel == 0 || rel == u32::MAX {
289 return set_id;
290 }
291 let res = self.get_set_ref(set_id).clone();
292 let with_rel = res
293 .iter()
294 .map(|v| NullState::new(v.mask, v.rel + rel))
295 .collect();
296
297 self.get_id(with_rel)
298 }
299}