path: root/src/main.rs

use std::collections::{HashMap, HashSet};

use itertools::Itertools;

// NOTE: PartialOrd and Ord have no sense, but it is needed to sort them somehow
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
struct Cube {
    t: usize,
    f: usize,
}

impl Cube {
    fn cost(&self) -> usize {
        self.t.count_ones() as usize + self.f.count_ones() as usize
    }

    fn covers(&self, minterm: usize) -> bool {
        let mask = self.t | self.f;
        minterm & mask == self.t && !minterm & mask == self.f
    }

    fn combine(&self, other: &Self) -> Option<Self> {
        let dt = self.t ^ other.t;
        let df = self.f ^ other.f;

        if dt == df && dt.count_ones() == 1 {
            Some(Self {
                t: self.t & other.t,
                f: self.f & other.f,
            })
        } else {
            None
        }
    }
}

fn cube_to_string(n: usize, cube: &Cube) -> String {
    let mut s = String::new();

    let Cube { mut t, mut f } = *cube;
    for _ in 0..n {
        match (t & 1, f & 1) {
            (1, 0) => s.push('1'),
            (0, 1) => s.push('0'),
            (0, 0) => s.push('x'),
            _ => unreachable!(),
        }

        t >>= 1;
        f >>= 1;
    }

    s.chars().rev().collect()
}

fn cube_to_var_string(vars: &[&str], cube: &Cube) -> String {
    let mut used_vars: Vec<String> = Vec::with_capacity(vars.len());

    let Cube { mut t, mut f } = *cube;
    for i in (0..vars.len()).rev() {
        match (t & 1, f & 1) {
            (1, 0) => used_vars.push(vars[i].into()),
            (0, 1) => used_vars.push(format!("{}'", vars[i])),
            (0, 0) => (),
            _ => unreachable!(),
        }

        t >>= 1;
        f >>= 1;
    }

    used_vars.into_iter().rev().join(" * ")
}

fn minimize_prime_implicants(n: usize, minterms: &[usize], maxterms: &[usize]) -> Vec<Cube> {
    let minterms_set: HashSet<_> = minterms.iter().copied().collect();
    let maxterms_set: HashSet<_> = maxterms.iter().copied().collect();

    let mut anyterms_set = HashSet::new();
    for i in 0..2usize.pow(n as u32) {
        if !minterms_set.contains(&i) && !maxterms_set.contains(&i) {
            anyterms_set.insert(i);
        }
    }

    let mask = (1 << n) - 1;
    let initial_cubes: Vec<_> = minterms_set
        .union(&anyterms_set)
        .sorted()
        .map(|&i| Cube { t: i, f: !i & mask })
        .collect();

    let mut covered = vec![vec![false; initial_cubes.len()]];
    let mut cubes = vec![initial_cubes];

    for iteration in 0..n {
        let current_covered = &mut covered[iteration];
        let current_cubes = &cubes[iteration];

        let mut new_cubes = HashSet::new();
        for i in 0..current_cubes.len() {
            for j in i + 1..current_cubes.len() {
                let a = &current_cubes[i];
                let b = &current_cubes[j];

                if let Some(combined_cube) = a.combine(b) {
                    current_covered[i] = true;
                    current_covered[j] = true;
                    new_cubes.insert(combined_cube);
                }
            }
        }

        covered.push(vec![false; new_cubes.len()]);
        cubes.push(new_cubes.into_iter().collect());
    }

    let mut final_cubes = vec![];
    for (iteration, iteration_cubes) in cubes.into_iter().enumerate() {
        for (i, cube) in iteration_cubes.into_iter().enumerate() {
            if !covered[iteration][i] {
                final_cubes.push(cube);
            }
        }
    }

    final_cubes.sort();
    final_cubes
}

fn print_prime_implicants_table(n: usize, minterms: &[usize], prime_implicants: &[Cube]) {
    println!("Prime implicants:");
    for (i, prime_implicant) in prime_implicants.iter().enumerate() {
        let cube_str = cube_to_string(n, prime_implicant);
        println!("{i}: {cube_str}");
    }

    println!();
    println!("Prime Implicants Table (PIT):");
    print!(" ");
    println!(
        "{}",
        (0..minterms.len())
            .map(|i| format!(" {} ", minterms[i]))
            .join("")
    );
    for (i, prime_implicant) in prime_implicants.iter().enumerate() {
        print!("{i}");
        for &minterm in minterms {
            if prime_implicant.covers(minterm) {
                print!(" x ");
            } else {
                print!("   ");
            }
        }
        println!();
    }
}

fn solve_prime_implicants_table(minterms: &[usize], prime_implicants: &[Cube]) -> Vec<Cube> {
    let mut table: HashSet<(usize, usize)> = (0..prime_implicants.len())
        .cartesian_product(0..minterms.len())
        .filter(|&(i, j)| prime_implicants[i].covers(minterms[j]))
        .collect();

    let mut selected_implicants = vec![false; prime_implicants.len()];
    loop {
        // Select essential minterms
        let mut minterms_freq = vec![0; minterms.len()];
        table.iter().for_each(|&(_, j)| minterms_freq[j] += 1);
        table
            .iter()
            .for_each(|&(i, j)| selected_implicants[i] |= minterms_freq[j] == 1);

        // Check if minterms are fully covered
        let mut covered_minterms = vec![false; minterms.len()];
        table
            .iter()
            .filter(|&&(i, _)| selected_implicants[i])
            .for_each(|&(_, j)| covered_minterms[j] = true);
        if table.is_empty() || covered_minterms.iter().all(|&v| v) {
            break;
        }

        // Removing essential implicants
        let new_table: HashSet<_> = table
            .iter()
            .filter(|&&(i, j)| !selected_implicants[i] && !covered_minterms[j])
            .cloned()
            .collect();
        table = new_table;

        if table.is_empty() {
            // All implicants are used
            break;
        }

        // Finding minterm coverage by implicants
        let mut implicants = HashSet::new();
        let mut covered_by_implicants: HashMap<usize, HashSet<_>> = HashMap::new();
        table.iter().for_each(|&(i, j)| {
            implicants.insert(i);
            covered_by_implicants.entry(i).or_default().insert(j);
        });

        // Removing implicants by cost when essentials are not found
        // NOTE: when checking combinations, implicants must be sorted, to give constant result
        // (If not, it will variate due to order in HashSet)
        let mut removed = false;
        let mut implicants_to_remove = vec![false; prime_implicants.len()];
        for (a, b) in implicants.iter().sorted().tuple_combinations() {
            let a_set = &covered_by_implicants[a];
            let b_set = &covered_by_implicants[b];
            let eq = a_set == b_set;

            let a_cost = prime_implicants[*a].cost();
            let b_cost = prime_implicants[*b].cost();

            if eq && a_cost >= b_cost {
                implicants_to_remove[*a] = true;
                removed = true;
            } else if eq {
                implicants_to_remove[*b] = true;
                removed = true;
            }
        }

        if removed {
            let new_table: HashSet<_> = table
                .iter()
                .filter(|&&(i, _)| !implicants_to_remove[i])
                .cloned()
                .collect();
            table = new_table;
        } else {
            // We can't remove implicants by cost, have to choose by ourselves.
            // NOTE: this leads to non-minimal solution
            // NOTE: this SHOULD NOT happen, as we are filtering equal implicant costs too
            todo!()
        }
    }

    prime_implicants
        .iter()
        .zip(selected_implicants)
        .filter(|&(_, select)| select)
        .map(|(cube, _)| cube)
        .copied()
        .collect()
}

fn minimize(n: usize, minterms: &[usize], maxterms: &[usize]) -> Vec<Cube> {
    let prime_implicants = minimize_prime_implicants(n, minterms, maxterms);
    print_prime_implicants_table(n, minterms, &prime_implicants);
    solve_prime_implicants_table(minterms, &prime_implicants)
}

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 min_cubes = minimize(4, &minterms, &maxterms);

    println!("Итоговые термы: ");
    for cube in min_cubes {
        println!(
            "{} -> {}",
            cube_to_string(4, &cube),
            cube_to_var_string(&vars, &cube)
        );
    }
}