1use std::collections::BTreeMap;
2use std::fmt::{Display, Formatter};
3use std::ops::{BitAnd, BitOr, Not};
4
5use crate::{e_and, e_leaf, e_or};
6use crate::traits::BuildTruthTable;
7use crate::truth_table::TruthTable;
8
9#[derive(Debug, Eq, PartialEq, Clone)]
10pub enum ExpressionNode<T> {
11 Leaf(T),
12 And(Box<ExpressionNode<T>>, Box<ExpressionNode<T>>),
13 Or(Box<ExpressionNode<T>>, Box<ExpressionNode<T>>),
14 Not(Box<ExpressionNode<T>>),
15}
16
17impl<T> BitAnd for ExpressionNode<T> {
18 type Output = ExpressionNode<T>;
19
20 fn bitand(self, rhs: Self) -> Self::Output {
21 e_and!(self, rhs)
22 }
23}
24
25impl<T> BitOr for ExpressionNode<T> {
26 type Output = ExpressionNode<T>;
27
28 fn bitor(self, rhs: Self) -> Self::Output {
29 e_or!(self, rhs)
30 }
31}
32
33impl<T: Not<Output=T>> Not for ExpressionNode<T> {
34 type Output = ExpressionNode<T>;
35
36 fn not(self) -> Self::Output {
37 match self {
38 Self::Leaf(filter) => Self::Leaf(filter.not()),
39 Self::And(left, right) => e_or!(left.not(), right.not()),
40 Self::Or(left, right) => e_and!(left.not(), right.not()),
41 Self::Not(parse_tree) => *parse_tree,
42 }
43 }
44}
45
46impl<T: Not<Output=T>> ExpressionNode<T> {
47 pub fn to_nnf(self) -> Self {
48 match self {
49 leaf @ ExpressionNode::Leaf(_) => leaf,
50 Self::And(left, right) => e_and!(left.to_nnf(), right.to_nnf()),
51 Self::Or(left, right) => e_or!(left.to_nnf(), right.to_nnf()),
52
53 Self::Not(node) => match *node {
54 Self::Leaf(filter) => e_leaf!(filter.not()),
55 Self::And(left, right) => {
56 e_or!(left.not().to_nnf(), right.not().to_nnf())
57 }
58
59 Self::Or(left, right) => {
60 e_and!(left.not().to_nnf(), right.not().to_nnf())
61 }
62 Self::Not(nested) => nested.to_nnf(),
63 },
64 }
65 }
66}
67
68impl<T> ExpressionNode<T> {
69 pub fn sort_by_key<K: Ord>(&mut self, mut f: impl FnMut(&T) -> K) {
70 self.sort_by_key_internal(&mut f);
71 }
72
73 fn sort_by_key_internal<K: Ord>(&mut self, f: &mut impl FnMut(&T) -> K) -> K {
74 match self {
75 ExpressionNode::Leaf(a) => f(a),
76 ExpressionNode::And(left, right) | ExpressionNode::Or(left, right) => {
77 let left_value = left.sort_by_key_internal(f);
78 let right_value = right.sort_by_key_internal(f);
79
80 if left_value > right_value {
81 std::mem::swap(left, right);
82 left_value
83 } else {
84 right_value
85 }
86 }
87 ExpressionNode::Not(node) => {
88 node.sort_by_key_internal(f)
89 }
90 }
91 }
92
93 pub fn extract_leafs(&self) -> Vec<&T> {
94 let mut result = vec![];
95 self.extract_leafs_internal(&mut result);
96 result
97 }
98
99 fn extract_leafs_internal<'a>(&'a self, result: &mut Vec<&'a T>) {
100 match self {
101 ExpressionNode::Leaf(value) => {
102 result.push(value);
103 }
104 ExpressionNode::And(left, right) | ExpressionNode::Or(left, right) => {
105 left.extract_leafs_internal(result);
106 right.extract_leafs_internal(result);
107 }
108 ExpressionNode::Not(node) => {
109 node.extract_leafs_internal(result)
110 }
111 }
112 }
113}
114
115impl<T: Ord> ExpressionNode<T> {
116 fn evaluate_with(&self, index_map: &BTreeMap<&T, usize>, arrangement: u128) -> bool {
117 match self {
118 ExpressionNode::Leaf(value) => {
119 let index = *index_map.get(value).unwrap();
120 arrangement & (1 << index) != 0
121 }
122 ExpressionNode::And(left, right) => {
123 left.evaluate_with(index_map, arrangement) && right.evaluate_with(index_map, arrangement)
124 }
125 ExpressionNode::Or(left, right) => {
126 left.evaluate_with(index_map, arrangement) || right.evaluate_with(index_map, arrangement)
127 }
128 ExpressionNode::Not(node) => {
129 !node.evaluate_with(index_map, arrangement)
130 }
131 }
132 }
133}
134
135impl<T: Display> Display for ExpressionNode<T> {
136 fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
137 match self {
138 ExpressionNode::Leaf(value) => write!(f, "{value}"),
139 ExpressionNode::And(left, right) => write!(f, "({left} ∧ {right})"),
140 ExpressionNode::Or(left, right) => write!(f, "({left} ∨ {right})"),
141 ExpressionNode::Not(node) => write!(f, "¬{node}")
142 }
143 }
144}
145
146
147impl<'a, T: Ord> BuildTruthTable<'a, T> for ExpressionNode<T> {
148 fn build_truth_table(&'a self) -> TruthTable<'a, T> {
149 let mut tt = TruthTable::from(self.extract_leafs());
150
151 for arrangement in 0..(1 << tt.num_vars()) {
152 let evaluate_result = self.evaluate_with(&tt.var_to_index_map, arrangement);
153 tt.add_row(arrangement, evaluate_result);
154 }
155
156 tt
157 }
158}
159
160#[allow(unused_macros)]
161pub mod macros {
162 #[macro_export]
163 macro_rules! e_leaf {
164 ($node:expr) => {
165 $crate::parse_tree::ExpressionNode::Leaf($node)
166 };
167 }
168
169 #[macro_export]
170 macro_rules! e_not {
171 ($node:expr) => {
172 $crate::parse_tree::ExpressionNode::Not($node.into())
173 };
174 }
175
176 #[macro_export]
177 macro_rules! e_or {
178 ($left:expr, $right:expr) => {
179 $crate::parse_tree::ExpressionNode::Or($left.into(), $right.into())
180 };
181 }
182
183 #[macro_export]
184 macro_rules! e_and {
185 ($left:expr, $right:expr) => {
186 $crate::parse_tree::ExpressionNode::And($left.into(), $right.into())
187 };
188 }
189}
190
191#[cfg(test)]
192mod test {
193 use crate::{e_and, e_leaf, e_not, e_or};
194 use crate::parse_tree::ExpressionNode;
195 use crate::traits::BuildTruthTable;
196
197 #[test]
198 fn test_to_nnf() {
199 assert_eq!((e_leaf!(1) & e_leaf!(2)).to_nnf(), e_leaf!(1) & e_leaf!(2));
200
201 assert_eq!((e_not!(e_leaf!(1))).to_nnf(), e_leaf!(-2));
202
203 assert_eq!(
204 e_not!(e_leaf!(true) & e_leaf!(true)).to_nnf(),
205 e_or!(e_leaf!(false), e_leaf!(false))
206 );
207
208 assert_eq!(
209 e_not!(e_leaf!(true) | e_leaf!(true)).to_nnf(),
210 e_and!(e_leaf!(false), e_leaf!(false))
211 );
212
213 assert_eq!(
214 e_not!(e_not!(e_leaf!(true) | e_leaf!(true))).to_nnf(),
215 e_or!(e_leaf!(true), e_leaf!(true))
216 );
217 }
218
219 #[test]
220 fn test_not() {
221 assert_eq!(
222 !e_not!(e_leaf!(true)),
223 e_leaf!(true)
224 );
225
226 assert_eq!(
227 !e_and!(e_leaf!(true), e_leaf!(true)),
228 e_or!(e_leaf!(false), e_leaf!(false))
229 );
230
231 assert_eq!(
232 !e_or!(e_leaf!(true), e_leaf!(true)),
233 e_and!(e_leaf!(false), e_leaf!(false))
234 );
235
236 assert_eq!(
237 !ExpressionNode::Not(e_or!(e_leaf!(true), e_leaf!(true)).into()),
238 e_or!(e_leaf!(true), e_leaf!(true))
239 );
240 }
241
242 #[test]
243 fn test_sort() {
244 let mut root = e_or!(
245 e_not!(
246 e_and!(e_leaf!(2000), e_leaf!(1000))
247 ),
248 e_not!(
249 e_or!(
250 e_leaf!(200),
251 e_and!(
252 e_leaf!(5),
253 e_not!(
254 e_and!(
255 e_leaf!(2),
256 e_leaf!(1)
257 )
258 )
259 )
260 )
261 )
262 );
263
264 let expected = e_or!(
265 e_not!(
266 e_or!(
267 e_and!(
268 e_not!(
269 e_and!(
270 e_leaf!(1),
271 e_leaf!(2)
272 )
273 ),
274 e_leaf!(5)
275 ),
276 e_leaf!(200)
277 )
278 ),
279
280 e_not!(
281 e_and!(e_leaf!(1000), e_leaf!(2000))
282 )
283 );
284
285 root.sort_by_key(|&leaf_value| leaf_value);
286
287 assert_eq!(root, expected);
288 }
289
290 #[test]
291 fn test_display() {
292 let root = e_not!(
293 e_and!(
294 e_or!(
295 e_leaf!(1),
296 e_leaf!(2)
297 ),
298 e_and!(
299 e_leaf!(3),
300 e_leaf!(4)
301 )
302 )
303 );
304
305 assert_eq!(
306 format!("{root}"),
307 "¬((1 ∨ 2) ∧ (3 ∧ 4))"
308 );
309 }
310
311 #[test]
312 fn test_extract_leafs() {
313 let root = e_not!(
314 e_and!(
315 e_or!(
316 e_leaf!(1),
317 e_leaf!(2)
318 ),
319 e_and!(
320 e_leaf!(3),
321 e_leaf!(4)
322 )
323 )
324 );
325
326 assert_eq!(
327 root.extract_leafs(),
328 [&1, &2, &3, &4]
329 );
330 }
331
332 #[test]
333 fn test_build_truth_table() {
334 let root = e_and!(
335 e_leaf!("a"),
336 e_leaf!("b")
337 );
338
339 assert_eq!(
340 root.build_truth_table().to_matrix(),
341 [
342 [false, false, false],
343 [false, true, false],
344 [true, false, false],
345 [true, true, true],
346 ]
347 );
348
349 let root = e_or!(
350 e_leaf!("a"),
351 e_leaf!("b")
352 );
353
354 assert_eq!(
355 root.build_truth_table().to_matrix(),
356 [
357 [false, false, false],
358 [false, true, true],
359 [true, false, true],
360 [true, true, true],
361 ]
362 );
363
364 let root = e_not!(
365 e_or!(
366 e_leaf!("a"),
367 e_leaf!("b")
368 )
369 );
370
371 assert_eq!(
372 root.build_truth_table().to_matrix(),
373 [
374 [false, false, true],
375 [false, true, false],
376 [true, false, false],
377 [true, true, false],
378 ]
379 );
380
381 let root = e_and!(
382 e_leaf!("a"),
383 e_or!(
384 e_leaf!("b"),
385 e_leaf!("c")
386 )
387 );
388
389 assert_eq!(
390 root.build_truth_table().to_matrix(),
391 [
392 [false, false, false, false],
393 [false, false, true, false],
394 [false, true, false, false],
395 [false, true, true, false],
396 [true, false, false, false],
397 [true, false, true, true],
398 [true, true, false, true],
399 [true, true, true, true]
400 ]
401 );
402 }
403}