mimir_node_map/
contraction.rs1use std::collections::{BTreeMap, BTreeSet};
4
5pub type Position = (u32, u32);
6pub type Pair = (u32, u32, u32);
7
8#[derive(Clone, Debug, Default, PartialEq, Eq)]
9pub struct Relation {
10 pub nodes: BTreeSet<Position>,
11 pub first: BTreeSet<Position>,
12 pub pairs: BTreeSet<Pair>,
13}
14
15#[derive(Clone, Debug, PartialEq, Eq)]
16pub enum Refusal {
17 UnknownPosition(Position),
18 ConflictingPosition(Position),
19 OrdinaryCall(Position),
20 NewCallPair(Pair),
21}
22
23pub fn contract(
26 raw: &Relation,
27 never: &BTreeSet<Position>,
28 optional: &BTreeSet<Position>,
29 calls: &BTreeSet<u32>,
30) -> Result<Relation, Refusal> {
31 for &p in never.union(optional) {
32 if !raw.nodes.contains(&p) {
33 return Err(Refusal::UnknownPosition(p));
34 }
35 if never.contains(&p) && optional.contains(&p) {
36 return Err(Refusal::ConflictingPosition(p));
37 }
38 if calls.contains(&p.1) {
39 return Err(Refusal::OrdinaryCall(p));
40 }
41 }
42 let mut next = BTreeMap::<Position, BTreeSet<Position>>::new();
43 for &(entry, a, b) in &raw.pairs {
44 for p in [(entry, a), (entry, b)] {
45 if !raw.nodes.contains(&p) {
46 return Err(Refusal::UnknownPosition(p));
47 }
48 }
49 next.entry((entry, a)).or_default().insert((entry, b));
50 }
51 for &p in &raw.first {
52 if !raw.nodes.contains(&p) {
53 return Err(Refusal::UnknownPosition(p));
54 }
55 }
56 let mut result = Relation {
57 nodes: raw.nodes.difference(never).copied().collect(),
58 first: through(&next, raw.first.iter().copied(), never, optional),
59 pairs: BTreeSet::new(),
60 };
61 for (&(entry, a), successors) in &next {
62 if never.contains(&(entry, a)) {
63 continue;
64 }
65 for (_, b) in through(&next, successors.iter().copied(), never, optional) {
66 let pair = (entry, a, b);
67 if calls.contains(&a) && calls.contains(&b) && !raw.pairs.contains(&pair) {
68 return Err(Refusal::NewCallPair(pair));
69 }
70 result.pairs.insert(pair);
71 }
72 }
73 Ok(result)
74}
75
76pub fn through<N: Ord + Clone>(
80 next: &BTreeMap<N, BTreeSet<N>>,
81 starts: impl IntoIterator<Item = N>,
82 never: &BTreeSet<N>,
83 optional: &BTreeSet<N>,
84) -> BTreeSet<N> {
85 let mut out = BTreeSet::new();
86 let mut seen = BTreeSet::new();
87 let mut work: Vec<_> = starts.into_iter().collect();
88 while let Some(n) = work.pop() {
89 if !seen.insert(n.clone()) {
90 continue;
91 }
92 if !never.contains(&n) {
93 out.insert(n.clone());
94 }
95 if never.contains(&n) || optional.contains(&n) {
96 work.extend(next.get(&n).into_iter().flatten().cloned());
97 }
98 }
99 out
100}