1mod cycles;
18mod groups;
19
20use super::PlanningSolution;
21
22const UNVISITED: usize = usize::MAX;
23
24#[derive(Default)]
31pub struct CascadePropagation {
32 offsets: Vec<usize>,
35 dependents: Vec<usize>,
36 node: Vec<usize>,
41 member_offsets: Vec<usize>,
42 members: Vec<usize>,
43 in_cone: Vec<bool>,
45 dirty: Vec<bool>,
46 done: Vec<bool>,
47 cycle: Vec<bool>,
48 pending_inputs: Vec<usize>,
49 order: Vec<usize>,
50 low: Vec<usize>,
51 on_stack: Vec<bool>,
52 cone: Vec<usize>,
53 stack: Vec<usize>,
54 ready: Vec<usize>,
55 scratch: Vec<usize>,
56}
57
58impl CascadePropagation {
59 pub fn new<S: PlanningSolution>(solution: &S) -> Self {
61 let mut propagation = Self::default();
62 propagation.rebuild_dependencies(solution);
63 propagation
64 }
65
66 pub fn rebuild_dependencies<S: PlanningSolution>(&mut self, solution: &S) {
73 let count = solution.cascading_element_count();
74 self.offsets.clear();
75 self.offsets.resize(count + 1, 0);
76 for element in 0..count {
77 self.scratch.clear();
78 solution.cascading_dependencies(element, &mut self.scratch);
79 for &dependency in &self.scratch {
80 assert!(
81 dependency < count,
82 "cascading element {element} depends on element {dependency}, but there are only {count} elements"
83 );
84 self.offsets[dependency + 1] += 1;
85 }
86 }
87 for element in 0..count {
88 self.offsets[element + 1] += self.offsets[element];
89 }
90 self.dependents.clear();
91 self.dependents.resize(self.offsets[count], 0);
92 let mut fill = self.offsets.clone();
93 for element in 0..count {
94 self.scratch.clear();
95 solution.cascading_dependencies(element, &mut self.scratch);
96 for &dependency in &self.scratch {
97 self.dependents[fill[dependency]] = element;
98 fill[dependency] += 1;
99 }
100 }
101 self.scratch.clear();
102 self.rebuild_groups(solution, count);
103 for flags in [
104 &mut self.in_cone,
105 &mut self.dirty,
106 &mut self.done,
107 &mut self.cycle,
108 &mut self.on_stack,
109 ] {
110 flags.clear();
111 flags.resize(count, false);
112 }
113 self.pending_inputs.clear();
114 self.pending_inputs.resize(count, 0);
115 self.order.clear();
116 self.order.resize(count, UNVISITED);
117 self.low.clear();
118 self.low.resize(count, UNVISITED);
119 }
120
121 pub fn refresh_all<S: PlanningSolution>(solution: &mut S) {
123 let mut propagation = Self::new(solution);
124 let count = solution.cascading_element_count();
125 propagation.propagate(solution, 0..count, |_, _| {});
126 }
127
128 pub fn propagate<S, I, W>(&mut self, solution: &mut S, changed: I, before_write: W)
140 where
141 S: PlanningSolution,
142 I: IntoIterator<Item = usize>,
143 W: FnMut(&S, usize),
144 {
145 if self.node.is_empty() {
148 self.propagate_nodes::<false, S, I, W>(solution, changed, before_write);
149 } else {
150 self.propagate_nodes::<true, S, I, W>(solution, changed, before_write);
151 }
152 }
153
154 fn propagate_nodes<const GROUPED: bool, S, I, W>(
155 &mut self,
156 solution: &mut S,
157 changed: I,
158 mut before_write: W,
159 ) where
160 S: PlanningSolution,
161 I: IntoIterator<Item = usize>,
162 W: FnMut(&S, usize),
163 {
164 for element in changed {
165 let node = self.node_of::<GROUPED>(element);
166 self.dirty[node] = true;
167 if !self.in_cone[node] {
168 self.in_cone[node] = true;
169 self.cone.push(node);
170 self.stack.push(node);
171 }
172 }
173 while let Some(node) = self.stack.pop() {
174 for index in 0..self.member_count::<GROUPED>(node) {
175 let member = self.member::<GROUPED>(node, index);
176 if let Some(next) = solution.cascading_next(member) {
177 self.reach(self.node_of::<GROUPED>(next));
178 }
179 for position in self.offsets[member]..self.offsets[member + 1] {
180 self.reach(self.node_of::<GROUPED>(self.dependents[position]));
181 }
182 }
183 }
184
185 self.ready.extend(
186 self.cone
187 .iter()
188 .copied()
189 .filter(|&node| self.pending_inputs[node] == 0),
190 );
191 let mut finished = 0;
192 loop {
193 while let Some(node) = self.ready.pop() {
194 self.done[node] = true;
195 finished += 1;
196 let stale = self.dirty[node]
197 || (0..self.member_count::<GROUPED>(node)).any(|index| {
198 let member = self.member::<GROUPED>(node, index);
199 solution.cascading_assigned(member) && solution.cascading_unset(member)
200 });
201 if stale {
202 for index in 0..self.member_count::<GROUPED>(node) {
203 let member = self.member::<GROUPED>(node, index);
204 let assigned = solution.cascading_assigned(member);
205 if solution.update_cascading_shadow(member, assigned, |solution| {
206 before_write(solution, member)
207 }) {
208 self.mark_outputs_dirty::<GROUPED, S>(solution, member);
209 }
210 }
211 }
212 self.release_outputs::<GROUPED, S>(solution, node);
213 }
214 if finished == self.cone.len() {
215 break;
216 }
217 self.mark_cycles(solution);
221 for position in 0..self.cone.len() {
222 let node = self.cone[position];
223 if self.cycle[node] && !self.done[node] {
224 self.done[node] = true;
225 finished += 1;
226 for index in 0..self.member_count::<GROUPED>(node) {
227 let member = self.member::<GROUPED>(node, index);
228 if solution.update_cascading_shadow(member, false, |solution| {
229 before_write(solution, member)
230 }) {
231 self.mark_outputs_dirty::<GROUPED, S>(solution, member);
232 }
233 }
234 }
235 }
236 for position in 0..self.cone.len() {
237 let node = self.cone[position];
238 if self.cycle[node] {
239 self.release_outputs::<GROUPED, S>(solution, node);
240 }
241 }
242 }
243
244 for &node in &self.cone {
245 self.in_cone[node] = false;
246 self.dirty[node] = false;
247 self.done[node] = false;
248 self.cycle[node] = false;
249 self.pending_inputs[node] = 0;
250 self.order[node] = UNVISITED;
251 self.low[node] = UNVISITED;
252 }
253 self.cone.clear();
254 }
255
256 fn reach(&mut self, node: usize) {
257 self.pending_inputs[node] += 1;
258 if !self.in_cone[node] {
259 self.in_cone[node] = true;
260 self.cone.push(node);
261 self.stack.push(node);
262 }
263 }
264
265 fn mark_outputs_dirty<const GROUPED: bool, S: PlanningSolution>(
266 &mut self,
267 solution: &S,
268 element: usize,
269 ) {
270 if let Some(next) = solution.cascading_next(element) {
271 let node = self.node_of::<GROUPED>(next);
272 self.dirty[node] = true;
273 }
274 for position in self.offsets[element]..self.offsets[element + 1] {
275 let node = self.node_of::<GROUPED>(self.dependents[position]);
276 self.dirty[node] = true;
277 }
278 }
279
280 fn release_outputs<const GROUPED: bool, S: PlanningSolution>(
281 &mut self,
282 solution: &S,
283 node: usize,
284 ) {
285 for index in 0..self.member_count::<GROUPED>(node) {
286 let member = self.member::<GROUPED>(node, index);
287 if let Some(next) = solution.cascading_next(member) {
288 self.release(self.node_of::<GROUPED>(next));
289 }
290 for position in self.offsets[member]..self.offsets[member + 1] {
291 self.release(self.node_of::<GROUPED>(self.dependents[position]));
292 }
293 }
294 }
295
296 fn release(&mut self, node: usize) {
297 self.pending_inputs[node] -= 1;
298 if self.pending_inputs[node] == 0 && !self.done[node] && !self.cycle[node] {
299 self.ready.push(node);
300 }
301 }
302}