1use alloc::vec;
2use alloc::vec::Vec;
3
4use crate::ranking::Ranking;
5use crate::{Abstraction, LabeledTransitionSystem, State, Task, Transition, Value, VarId};
6
7#[derive(Clone, Debug)]
22pub struct Projection {
23 ranking: Ranking,
24 lts: LabeledTransitionSystem,
25}
26
27impl Projection {
28 pub fn new(task: &Task, mut pattern: Vec<VarId>) -> Self {
29 pattern.retain(|&v| !task.variables[v].is_derived());
30 pattern.sort_unstable();
31 pattern.dedup();
32 let ranking = Ranking::new(task, pattern);
33
34 let mut transitions = Vec::new();
35 let mut outcomes: Vec<Vec<Value>> = vec![Vec::new(); ranking.vars.len()];
37 let mut touched: Vec<usize> = Vec::new();
38 let mut digits: Vec<usize> = Vec::new();
39 for (label, op) in task.operators.iter().enumerate() {
40 let effects: Vec<(usize, Value, &[crate::Fact], bool)> = op
43 .eff
44 .iter()
45 .filter_map(|e| {
46 let i = ranking.position(e.fact.var)?;
47 let sure = e
48 .conditions
49 .iter()
50 .all(|c| ranking.position(c.var).is_some());
51 Some((i, e.fact.value, e.conditions.as_slice(), sure))
52 })
53 .collect();
54 let unconditional = effects.iter().all(|e| e.2.is_empty());
55 for src in ranking.matching(&op.pre) {
57 if unconditional {
58 let dst = effects.iter().fold(src, |d, e| ranking.set(d, e.0, e.1));
59 transitions.push(Transition { src, label, dst });
60 continue;
61 }
62 for &i in &touched {
67 outcomes[i].clear();
68 }
69 touched.clear();
70 for &(i, value, conditions, sure) in &effects {
71 if !ranking.holds(src, conditions) {
72 continue;
73 }
74 let values = &mut outcomes[i];
75 if values.is_empty() {
76 touched.push(i);
77 values.push(ranking.value(src, i) as Value);
78 }
79 if sure {
80 values.clear();
81 values.push(value);
82 } else if !values.contains(&value) {
83 values.push(value);
84 }
85 }
86 digits.clear();
87 digits.resize(touched.len(), 0);
88 loop {
89 let dst = touched
90 .iter()
91 .zip(&digits)
92 .fold(src, |d, (&i, &k)| ranking.set(d, i, outcomes[i][k]));
93 transitions.push(Transition { src, label, dst });
94 let Some(j) =
95 (0..touched.len()).find(|&j| digits[j] + 1 < outcomes[touched[j]].len())
96 else {
97 break;
98 };
99 digits[j] += 1;
100 digits[..j].fill(0);
101 }
102 }
103 }
104 let mut goal = vec![false; ranking.num_states];
105 ranking.matching(&task.goal).for_each(|s| goal[s] = true);
106 let lts = LabeledTransitionSystem {
107 num_states: ranking.num_states,
108 num_labels: task.operators.len(),
109 transitions,
110 goal,
111 initial: Some(ranking.rank(&task.initial)),
112 };
113 Self { ranking, lts }
114 }
115
116 pub fn pattern(&self) -> &[VarId] {
117 &self.ranking.vars
118 }
119
120 pub fn rank(&self, state: &State) -> usize {
122 self.ranking.rank(state)
123 }
124}
125
126impl Abstraction for Projection {
127 fn lts(&self) -> &LabeledTransitionSystem {
128 &self.lts
129 }
130 fn abstract_state(&self, state: &State) -> Option<usize> {
131 Some(self.rank(state))
132 }
133}