c3_linearization/
algorithm.rs

1use crate::{
2    errors::Error::{BadHead, Circular, NotFound},
3    Result, C3,
4};
5use std::{
6    collections::{HashMap, HashSet},
7    hash::Hash,
8};
9
10pub fn merge<T>(sequences: Vec<Vec<T>>) -> Result<Vec<T>>
11where
12    T: Clone + PartialEq,
13{
14    let mut result = vec![];
15    // let mut sequences = sequences.iter().map(|s| s.slice()).collect::<Vec<_>>();
16    let sequences = &mut sequences.clone();
17    while sequences.len() > 0 {
18        let mut found = false;
19        for seq in sequences.clone() {
20            // println!("{:?}", seq);
21            let head = seq[0].clone();
22            // check bad head
23            for s in sequences.clone() {
24                if s != seq && s[1..s.len()].contains(&head) {
25                    return Err(BadHead);
26                }
27            }
28            found = true;
29            result.push(head.clone());
30            for seq in sequences.iter_mut() {
31                if let Some(index) = seq.iter().position(|r| r == &head) {
32                    seq.remove(index);
33                }
34            }
35            break;
36        }
37        sequences.retain(|x| !x.is_empty());
38        if !found {
39            return Err(NotFound);
40        }
41    }
42
43    return Ok(result);
44}
45
46impl C3 {
47    pub fn linearize<T>(&self, graph: HashMap<T, Vec<T>>) -> Result<HashMap<T, Vec<T>>>
48    where
49        T: Clone + PartialEq + Eq + Hash,
50    {
51        let heads: Vec<_> = graph.keys().collect();
52        let results = &mut HashMap::new();
53        let visiting = &mut HashSet::new();
54        for head in heads {
55            self.solve(&graph, head, results, visiting)?;
56        }
57        return Ok(results.clone());
58    }
59
60    fn solve<T>(
61        &self,
62        graph: &HashMap<T, Vec<T>>,
63        head: &T,
64        results: &mut HashMap<T, Vec<T>>,
65        visiting: &mut HashSet<T>,
66    ) -> Result<Vec<T>>
67    where
68        T: Clone + PartialEq + Eq + Hash,
69    {
70        if let Some(s) = results.get(head) {
71            return Ok(s.clone());
72        }
73        if visiting.contains(head) {
74            return Err(Circular);
75        }
76        visiting.insert(head.clone());
77        let mut parents = graph[head].clone();
78        if parents.len() == 0 {
79            let res = vec![head.clone()];
80            results.insert(head.clone(), res.clone());
81            return Ok(res);
82        }
83        if self.reverse {
84            parents.reverse();
85        }
86        let mut sequences = vec![];
87        for x in parents.iter() {
88            let s = self.solve(graph, &x, results, visiting)?;
89            sequences.push(s)
90        }
91        if self.python {
92            sequences.extend(vec![parents])
93        }
94        let mut res = vec![head.clone()];
95        res.extend(merge(sequences)?);
96        results.insert(head.clone(), res.clone());
97        visiting.remove(head);
98        return Ok(res);
99    }
100}
c3_linearization/algorithm.rs

c3_linearization/
algorithm.rs
