hooo 0.10.0

Propositional logic with exponentials
Documentation 
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

use crate::*;

use std::sync::mpsc::Receiver;

pub struct CycleDetector {
    pub ids: HashMap<grader::Name, usize>,
    pub edges: Vec<(usize, usize)>,
}

impl CycleDetector {
    /// Constructs cycle detector from receiver.
    ///
    /// Remember to drop the last sender before calling this.
    pub fn new(
        loader: &Loader,
        rc: Receiver<(Arc<String>, grader::Name)>
    ) -> CycleDetector {
        let mut ids = HashMap::default();
        for fun in loader.functions.keys() {
            if !ids.contains_key(&(vec![], fun.clone())) {
                let id = ids.len();
                ids.insert((vec![], fun.clone()), id);
            }
        }

        let mut edges = vec![];
        for (a, b) in rc.iter() {
            let a_id = if !ids.contains_key(&(vec![], a.clone())) {
                let id = ids.len();
                ids.insert((vec![], a.clone()), id);
                id
            } else {*ids.get(&(vec![], a.clone())).unwrap()};
            let b_id = if !ids.contains_key(&b) {
                let id = ids.len();
                ids.insert(b, id);
                id
            } else {*ids.get(&b).unwrap()};
            edges.push((a_id, b_id));
        }
        edges.sort();
        edges.dedup();
        CycleDetector {
            ids,
            edges,
        }
    }

    /// Detects cycles, if any.
    pub fn cycles(&self) -> Option<Vec<(usize, usize)>> {
        let mut visited = vec![false; self.ids.len()];
        // Mark all leaves.
        for &(a, b) in &self.edges {
            if !self.edges.iter().any(|&(_, d)| d == a) {
                visited[a] = true;
            }
            if !self.edges.iter().any(|&(c, _)| c == b) {
                visited[b] = true;
            }
        }
        loop {
            let mut changed = false;
            for &(a, b) in &self.edges {
                if !visited[a] {
                    if self.edges.iter().all(|&(c, d)| a != c || visited[d]) {
                        visited[a] = true;
                        changed = true;
                    }
                }
                if !visited[b] {
                    if self.edges.iter().all(|&(c, d)| b != d || visited[c]) {
                        visited[b] = true;
                        changed = true;
                    }
                }
            }
            if !changed {break}
        }

        let mut cycles = vec![];
        for &(a, b) in &self.edges {
            if !visited[a] && !visited[b] {cycles.push((a, b))}
        }
        if cycles.len() == 0 {None} else {Some(cycles)}
    }
}