c3_lang_linearization/
c3_linearization.rs

1use std::fmt::Debug;
2
3use super::{is_subset, C3Error, Sets, C3};
4
5// TODO: Re-implement using single Classes.
6pub fn c3_linearization(mut input: C3) -> Result<C3, C3Error> {
7    let mut output = C3::new();
8    loop {
9        let solved = output.all_classes();
10        let mut found = false;
11        for base in input.all_classes() {
12            let parents = input.path(&base)?;
13            if is_subset(&solved, &parents) {
14                let sets = output.sets_for(parents)?;
15                let solution = merge(&base, sets)?;
16                input.remove(&base)?;
17                output.add(base, solution);
18                found = true;
19            }
20        }
21        if !found {
22            break;
23        }
24    }
25    Ok(output)
26}
27
28pub fn merge<T: Clone + Debug + Eq>(base: &T, mut sets: Sets<T>) -> Result<Vec<T>, C3Error> {
29    let mut solutions = vec![base.clone()];
30    loop {
31        if sets.is_empty() {
32            return Ok(solutions);
33        }
34        let solution = sets.find_solution()?;
35        solutions.push(solution);
36    }
37}
38
39#[cfg(test)]
40mod tests {
41    use super::*;
42
43    #[test]
44    fn test_c3() {
45        let mut input = C3::new();
46        input.add_class_str("A", "");
47        input.add_class_str("B", "A");
48        input.add_class_str("C", "A");
49        input.add_class_str("D", "B, C");
50
51        let mut target = C3::new();
52        target.add_class_str("A", "A");
53        target.add_class_str("B", "B, A");
54        target.add_class_str("C", "C, A");
55        target.add_class_str("D", "D, B, C, A");
56
57        assert_eq!(c3_linearization(input).unwrap(), target);
58    }
59
60    #[test]
61    fn test_merge() {
62        let head = "K";
63        let mut sets: Sets<&str> = Sets::new();
64        sets.push(vec!["B", "O"]).unwrap();
65        sets.push(vec!["A", "O"]).unwrap();
66        sets.push(vec!["C", "O"]).unwrap();
67        sets.push(vec!["B", "A", "C"]).unwrap();
68
69        let result = merge(&head, sets).unwrap();
70        assert_eq!(result, vec!["K", "B", "A", "C", "O"]);
71    }
72
73    #[test]
74    fn test_merge_2() {
75        let head = "Z";
76        let mut sets: Sets<&str> = Sets::new();
77        sets.push(vec!["K1", "C", "B", "A", "O"]).unwrap();
78        sets.push(vec!["K3", "A", "D", "O"]).unwrap();
79        sets.push(vec!["K2", "B", "D", "E", "O"]).unwrap();
80        sets.push(vec!["K1", "K3", "K2"]).unwrap();
81
82        let result = merge(&head, sets).unwrap();
83        let expected = vec!["Z", "K1", "C", "K3", "K2", "B", "A", "D", "E", "O"];
84        assert_eq!(result, expected);
85    }
86}
c3_lang_linearization/c3_linearization.rs

c3_lang_linearization/
c3_linearization.rs
