1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86

use std::fmt::Debug;

use super::{is_subset, C3Error, Sets, C3};

// TODO: Re-implement using single Classes.
pub fn c3_linearization(mut input: C3) -> Result<C3, C3Error> {
    let mut output = C3::new();
    loop {
        let solved = output.all_classes();
        let mut found = false;
        for base in input.all_classes() {
            let parents = input.path(&base)?;
            if is_subset(&solved, &parents) {
                let sets = output.sets_for(parents)?;
                let solution = merge(&base, sets)?;
                input.remove(&base)?;
                output.add(base, solution);
                found = true;
            }
        }
        if !found {
            break;
        }
    }
    Ok(output)
}

pub fn merge<T: Clone + Debug + Eq>(base: &T, mut sets: Sets<T>) -> Result<Vec<T>, C3Error> {
    let mut solutions = vec![base.clone()];
    loop {
        if sets.is_empty() {
            return Ok(solutions);
        }
        let solution = sets.find_solution()?;
        solutions.push(solution);
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_c3() {
        let mut input = C3::new();
        input.add_class_str("A", "");
        input.add_class_str("B", "A");
        input.add_class_str("C", "A");
        input.add_class_str("D", "B, C");

        let mut target = C3::new();
        target.add_class_str("A", "A");
        target.add_class_str("B", "B, A");
        target.add_class_str("C", "C, A");
        target.add_class_str("D", "D, B, C, A");

        assert_eq!(c3_linearization(input).unwrap(), target);
    }

    #[test]
    fn test_merge() {
        let head = "K";
        let mut sets: Sets<&str> = Sets::new();
        sets.push(vec!["B", "O"]).unwrap();
        sets.push(vec!["A", "O"]).unwrap();
        sets.push(vec!["C", "O"]).unwrap();
        sets.push(vec!["B", "A", "C"]).unwrap();

        let result = merge(&head, sets).unwrap();
        assert_eq!(result, vec!["K", "B", "A", "C", "O"]);
    }

    #[test]
    fn test_merge_2() {
        let head = "Z";
        let mut sets: Sets<&str> = Sets::new();
        sets.push(vec!["K1", "C", "B", "A", "O"]).unwrap();
        sets.push(vec!["K3", "A", "D", "O"]).unwrap();
        sets.push(vec!["K2", "B", "D", "E", "O"]).unwrap();
        sets.push(vec!["K1", "K3", "K2"]).unwrap();

        let result = merge(&head, sets).unwrap();
        let expected = vec!["Z", "K1", "C", "K3", "K2", "B", "A", "D", "E", "O"];
        assert_eq!(result, expected);
    }
}