feat: transform cubes to logic

1 files changed, 181 insertions, 5 deletions

diff --git a/src/main.rs b/src/main.rs
index 18d6ca2..988a684 100644
--- a/src/main.rs
+++ b/src/main.rs
@@ -1,4 +1,7 @@
-use std::collections::{HashMap, HashSet};
+use std::{
+    collections::{HashMap, HashSet},
+    fmt::Display,
+};
 
 use itertools::Itertools;
 
@@ -255,10 +258,170 @@ fn minimize(n: usize, minterms: &[usize], maxterms: &[usize]) -> Vec<Cube> {
     solve_prime_implicants_table(minterms, &prime_implicants)
 }
 
+#[derive(Clone, Debug, Hash)]
+#[allow(dead_code)]
+enum Logic {
+    Constant(bool),
+
+    Variable(String),
+    Not(Box<Logic>),
+
+    And(Vec<Logic>),
+    Or(Vec<Logic>),
+
+    Nand(Vec<Logic>),
+    Nor(Vec<Logic>),
+}
+
+impl Logic {
+    fn inverse(&self) -> Self {
+        match self {
+            Logic::Constant(v) => Logic::Constant(!*v),
+            Logic::Variable(name) => Logic::Not(Box::new(Logic::Variable(name.clone()))),
+            Logic::Not(logic) => *logic.clone(),
+
+            Logic::And(logics) => Logic::Nand(logics.clone()),
+            Logic::Or(logics) => Logic::Nor(logics.clone()),
+
+            Logic::Nand(logics) => Logic::And(logics.clone()),
+            Logic::Nor(logics) => Logic::Or(logics.clone()),
+        }
+    }
+}
+
+impl Display for Logic {
+    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
+        match self {
+            Logic::Constant(v) => f.write_str(if *v { "1" } else { "0" }),
+            Logic::Variable(name) => f.write_str(name),
+            Logic::Not(logic) => f.write_fmt(format_args!("!{}", logic)),
+
+            Logic::And(logics) => {
+                let s = logics.iter().map(|logic| logic.to_string()).join(" & ");
+                f.write_fmt(format_args!("({s})"))
+            }
+
+            Logic::Or(logics) => {
+                let s = logics.iter().map(|logic| logic.to_string()).join(" | ");
+                f.write_fmt(format_args!("({s})"))
+            }
+
+            Logic::Nand(logics) => {
+                let s = logics.iter().map(|logic| logic.to_string()).join(" !& ");
+                f.write_fmt(format_args!("({s})"))
+            }
+
+            Logic::Nor(logics) => {
+                let s = logics.iter().map(|logic| logic.to_string()).join(" !| ");
+                f.write_fmt(format_args!("({s})"))
+            }
+
+            _ => unreachable!(),
+        }
+    }
+}
+
+fn cubes_to_dnf(cubes: &[Cube], vars: &[&str]) -> Logic {
+    if cubes.is_empty() {
+        return Logic::Constant(false);
+    } else if cubes.len() == 1 && cubes[0].t == 0 && cubes[0].f == 0 {
+        return Logic::Constant(true);
+    }
+
+    let mut dnf = vec![];
+    for &Cube { mut t, mut f } in cubes {
+        let mut used_vars = Vec::new();
+
+        for i in (0..vars.len()).rev() {
+            match (t & 1, f & 1) {
+                (1, 0) => used_vars.push(Logic::Variable(vars[i].to_owned())),
+                (0, 1) => used_vars.push(Logic::Not(Box::new(Logic::Variable(vars[i].to_owned())))),
+                (0, 0) => (),
+                _ => unreachable!(),
+            }
+
+            t >>= 1;
+            f >>= 1;
+        }
+
+        if used_vars.len() == 1 {
+            dnf.push(used_vars[0].clone());
+        } else {
+            dnf.push(Logic::And(used_vars));
+        }
+    }
+
+    if dnf.len() == 1 {
+        dnf[0].clone()
+    } else {
+        Logic::Or(dnf)
+    }
+}
+
+// NOTE: returns inverted result
+fn cubes_to_cnf(cubes: &[Cube], vars: &[&str]) -> Logic {
+    if cubes.is_empty() {
+        return Logic::Constant(false);
+    } else if cubes.len() == 1 && cubes[0].t == 0 && cubes[0].f == 0 {
+        return Logic::Constant(true);
+    }
+
+    let mut dnf = vec![];
+    for &Cube { mut t, mut f } in cubes {
+        let mut used_vars = Vec::new();
+
+        for i in (0..vars.len()).rev() {
+            match (t & 1, f & 1) {
+                (1, 0) => used_vars.push(Logic::Not(Box::new(Logic::Variable(vars[i].to_owned())))),
+                (0, 1) => used_vars.push(Logic::Variable(vars[i].to_owned())),
+                (0, 0) => (),
+                _ => unreachable!(),
+            }
+
+            t >>= 1;
+            f >>= 1;
+        }
+
+        if used_vars.len() == 1 {
+            dnf.push(used_vars[0].clone());
+        } else {
+            dnf.push(Logic::Or(used_vars));
+        }
+    }
+
+    if dnf.len() == 1 {
+        dnf[0].clone()
+    } else {
+        Logic::And(dnf)
+    }
+}
+
+fn cubes_to_nand(cubes: &[Cube], vars: &[&str]) -> Logic {
+    let dnf = cubes_to_dnf(cubes, vars);
+    match dnf {
+        Logic::Or(logics) => Logic::Nand(logics.into_iter().map(|logic| logic.inverse()).collect()),
+        Logic::And(logics) => Logic::Not(Box::new(Logic::Nand(logics))),
+        logic => logic,
+    }
+}
+
+fn cubes_to_nor(cubes: &[Cube], vars: &[&str]) -> Logic {
+    let cnf = cubes_to_cnf(cubes, vars);
+    match cnf {
+        Logic::Or(logics) => Logic::Not(Box::new(Logic::Nor(logics))),
+        Logic::And(logics) => Logic::Nor(logics.into_iter().map(|logic| logic.inverse()).collect()),
+        logic => logic,
+    }
+}
+
 fn main() {
-    let vars = ["X4", "X3", "X2", "X1"];
-    let minterms = [0, 1, 2, 3, 4]; // Термы со значением 1
-    let maxterms = [5, 6, 7, 8, 9]; // Термы со значением 0
+    let vars = &["X4", "X3", "X2", "X1"];
+    // let minterms = [0, 1, 2, 3, 4]; // Термы со значением 1
+    // let maxterms = [5, 6, 7, 8, 9]; // Термы со значением 0
+    // let minterms = [0, 1, 2, 3, 4, 5, 6, 7]; // Термы со значением 1
+    // let maxterms = [9]; // Термы со значением 0
+    let minterms = [0, 3, 4, 7]; // Термы со значением 1
+    let maxterms = [1, 2, 5, 6]; // Термы со значением 0
 
     let min_cubes = minimize(4, &minterms, &maxterms);
 
@@ -267,7 +430,20 @@ fn main() {
         println!(
             "{} -> {}",
             cube_to_string(4, &cube),
-            cube_to_var_string(&vars, &cube)
+            cube_to_var_string(vars, &cube)
         );
     }
+
+    let cubes = minimize(4, &minterms, &maxterms);
+    let inv_cubes = minimize(4, &maxterms, &minterms);
+
+    println!("{}", cubes_to_dnf(&cubes, vars));
+    println!("{}", cubes_to_nand(&cubes, vars));
+    println!("{}", cubes_to_cnf(&inv_cubes, vars));
+    println!("{}", cubes_to_nor(&inv_cubes, vars));
+
+    // dbg!(cubes_to_dnf(&cubes, vars));
+    // dbg!(cubes_to_nand(&cubes, vars));
+    // dbg!(cubes_to_cnf(&inv_cubes, vars));
+    // dbg!(cubes_to_nor(&inv_cubes, vars));
 }