1use std::hash::Hash;
2use std::marker::PhantomData;
3
4use solverforge_core::score::Score;
5use solverforge_core::{ConstraintRef, ImpactType};
6
7use crate::api::constraint_set::IncrementalConstraint;
8use crate::stream::filter::{BiFilter, UniFilter};
9use crate::stream::projected::{RowCoordinate, RowOwner, Source};
10use crate::stream::relational::hash::{FastMap, FastSet};
11
12struct ProjectedJoinRow<Out> {
13 output: Out,
14 coordinate: RowCoordinate,
15}
16
17pub struct Bi<S, Out, K, Src, F, KF, PF, W, Sc>
25where
26 Src: Source<S, Out>,
27 Sc: Score,
28{
29 constraint_ref: ConstraintRef,
30 impact_type: ImpactType,
31 source: Src,
32 filter: F,
33 key_fn: KF,
34 pair_filter: PF,
35 weight: W,
36 is_hard: bool,
37 source_state: Option<Src::State>,
38 rows: Vec<Option<ProjectedJoinRow<Out>>>,
39 free_row_ids: Vec<usize>,
40 rows_by_owner: FastMap<RowOwner, Vec<usize>>,
41 row_ids_by_coordinate: FastMap<RowCoordinate, usize>,
42 rows_by_key: FastMap<K, Vec<usize>>,
43 _phantom: PhantomData<(fn() -> S, fn() -> Out, fn() -> Sc)>,
44}
45
46impl<S, Out, K, Src, F, KF, PF, W, Sc> Bi<S, Out, K, Src, F, KF, PF, W, Sc>
47where
48 S: Send + Sync + 'static,
49 Out: Send + Sync + 'static,
50 K: Eq + Hash + Send + Sync + 'static,
51 Src: Source<S, Out>,
52 F: UniFilter<S, Out>,
53 KF: Fn(&Out) -> K + Send + Sync,
54 PF: BiFilter<S, Out, Out>,
55 W: Fn(&Out, &Out) -> Sc + Send + Sync,
56 Sc: Score + 'static,
57{
58 #[allow(clippy::too_many_arguments)]
61 pub fn new(
62 constraint_ref: ConstraintRef,
63 impact_type: ImpactType,
64 source: Src,
65 filter: F,
66 key_fn: KF,
67 pair_filter: PF,
68 weight: W,
69 is_hard: bool,
70 ) -> Self {
71 Self {
72 constraint_ref,
73 impact_type,
74 source,
75 filter,
76 key_fn,
77 pair_filter,
78 weight,
79 is_hard,
80 source_state: None,
81 rows: Vec::new(),
82 free_row_ids: Vec::new(),
83 rows_by_owner: FastMap::default(),
84 row_ids_by_coordinate: FastMap::default(),
85 rows_by_key: FastMap::default(),
86 _phantom: PhantomData,
87 }
88 }
89
90 fn compute_score(&self, left: &Out, right: &Out) -> Sc {
91 let base = (self.weight)(left, right);
92 match self.impact_type {
93 ImpactType::Penalty => -base,
94 ImpactType::Reward => base,
95 }
96 }
97
98 fn score_outputs(
99 &self,
100 solution: &S,
101 left: &Out,
102 right: &Out,
103 left_idx: usize,
104 right_idx: usize,
105 ) -> Sc {
106 if !self
107 .pair_filter
108 .test(solution, left, right, left_idx, right_idx)
109 {
110 return Sc::zero();
111 }
112 self.compute_score(left, right)
113 }
114
115 fn filter_index(coordinate: RowCoordinate) -> usize {
116 coordinate.primary_owner.entity_index
117 }
118
119 fn score_retained_rows(
120 &self,
121 solution: &S,
122 first: &ProjectedJoinRow<Out>,
123 second: &ProjectedJoinRow<Out>,
124 ) -> Sc {
125 let (left, right) = if first.coordinate <= second.coordinate {
126 (first, second)
127 } else {
128 (second, first)
129 };
130 self.score_outputs(
131 solution,
132 &left.output,
133 &right.output,
134 Self::filter_index(left.coordinate),
135 Self::filter_index(right.coordinate),
136 )
137 }
138
139 fn score_candidate_row(
140 &self,
141 solution: &S,
142 candidate_output: &Out,
143 candidate_coordinate: RowCoordinate,
144 other: &ProjectedJoinRow<Out>,
145 ) -> Sc {
146 let (left, right, left_idx, right_idx) = if candidate_coordinate <= other.coordinate {
147 (
148 candidate_output,
149 &other.output,
150 Self::filter_index(candidate_coordinate),
151 Self::filter_index(other.coordinate),
152 )
153 } else {
154 (
155 &other.output,
156 candidate_output,
157 Self::filter_index(other.coordinate),
158 Self::filter_index(candidate_coordinate),
159 )
160 };
161 self.score_outputs(solution, left, right, left_idx, right_idx)
162 }
163
164 fn score_pair(&self, solution: &S, first_id: usize, second_id: usize) -> Sc {
165 let Some(first) = self.rows.get(first_id).and_then(Option::as_ref) else {
166 return Sc::zero();
167 };
168 let Some(second) = self.rows.get(second_id).and_then(Option::as_ref) else {
169 return Sc::zero();
170 };
171 self.score_retained_rows(solution, first, second)
172 }
173
174 fn ensure_source_state(&mut self, solution: &S) {
175 if self.source_state.is_none() {
176 self.source_state = Some(self.source.build_state(solution));
177 }
178 }
179
180 fn index_row_owners(&mut self, coordinate: RowCoordinate, row_id: usize) {
181 coordinate.for_each_owner(|owner| {
182 self.rows_by_owner.entry(owner).or_default().push(row_id);
183 });
184 }
185
186 fn unindex_row_owners(&mut self, coordinate: RowCoordinate, row_id: usize) {
187 coordinate.for_each_owner(|owner| {
188 let mut remove_bucket = false;
189 if let Some(ids) = self.rows_by_owner.get_mut(&owner) {
190 ids.retain(|candidate| *candidate != row_id);
191 remove_bucket = ids.is_empty();
192 }
193 if remove_bucket {
194 self.rows_by_owner.remove(&owner);
195 }
196 });
197 }
198
199 fn insert_row(&mut self, solution: &S, coordinate: RowCoordinate, output: Out) -> Sc {
200 if self.row_ids_by_coordinate.contains_key(&coordinate) {
201 return Sc::zero();
202 }
203 let key = (self.key_fn)(&output);
204 let mut total = Sc::zero();
205 if let Some(existing) = self.rows_by_key.get(&key) {
206 for &other_id in existing {
207 if let Some(other) = self.rows.get(other_id).and_then(Option::as_ref) {
208 total = total + self.score_candidate_row(solution, &output, coordinate, other);
209 }
210 }
211 }
212 let row = Some(ProjectedJoinRow { output, coordinate });
213 let row_id = if let Some(row_id) = self.free_row_ids.pop() {
214 debug_assert!(self.rows[row_id].is_none());
215 self.rows[row_id] = row;
216 row_id
217 } else {
218 let row_id = self.rows.len();
219 self.rows.push(row);
220 row_id
221 };
222 self.row_ids_by_coordinate.insert(coordinate, row_id);
223 self.index_row_owners(coordinate, row_id);
224 self.rows_by_key.entry(key).or_default().push(row_id);
225 total
226 }
227
228 fn retract_row(&mut self, solution: &S, row_id: usize) -> Sc {
229 let Some((key, coordinate)) = self
230 .rows
231 .get(row_id)
232 .and_then(Option::as_ref)
233 .map(|row| ((self.key_fn)(&row.output), row.coordinate))
234 else {
235 return Sc::zero();
236 };
237 let mut total = Sc::zero();
238 if let Some(candidates) = self.rows_by_key.get(&key) {
239 for &other_id in candidates {
240 if other_id == row_id {
241 continue;
242 }
243 total = total - self.score_pair(solution, row_id, other_id);
244 }
245 }
246
247 if let Some(ids) = self.rows_by_key.get_mut(&key) {
248 ids.retain(|&id| id != row_id);
249 if ids.is_empty() {
250 self.rows_by_key.remove(&key);
251 }
252 }
253 self.row_ids_by_coordinate.remove(&coordinate);
254 self.unindex_row_owners(coordinate, row_id);
255 self.rows[row_id] = None;
256 self.free_row_ids.push(row_id);
257 total
258 }
259
260 fn evaluate_rows(&self, solution: &S) -> Vec<ProjectedJoinRow<Out>> {
261 let state = self.source.build_state(solution);
262 let mut rows = Vec::new();
263 self.source
264 .collect_all(solution, &state, |coordinate, output| {
265 if self.filter.test(solution, &output) {
266 rows.push(ProjectedJoinRow { output, coordinate });
267 }
268 });
269 rows
270 }
271
272 fn score_evaluation_pair(
273 &self,
274 solution: &S,
275 first: &ProjectedJoinRow<Out>,
276 second: &ProjectedJoinRow<Out>,
277 ) -> Sc {
278 if (self.key_fn)(&first.output) == (self.key_fn)(&second.output) {
279 let (left, right) = if first.coordinate <= second.coordinate {
280 (first, second)
281 } else {
282 (second, first)
283 };
284 self.score_outputs(
285 solution,
286 &left.output,
287 &right.output,
288 Self::filter_index(left.coordinate),
289 Self::filter_index(right.coordinate),
290 )
291 } else {
292 Sc::zero()
293 }
294 }
295
296 fn evaluation_pair_matches(
297 &self,
298 solution: &S,
299 first: &ProjectedJoinRow<Out>,
300 second: &ProjectedJoinRow<Out>,
301 ) -> bool {
302 if (self.key_fn)(&first.output) != (self.key_fn)(&second.output) {
303 return false;
304 }
305 let (left, right) = if first.coordinate <= second.coordinate {
306 (first, second)
307 } else {
308 (second, first)
309 };
310 self.pair_filter.test(
311 solution,
312 &left.output,
313 &right.output,
314 Self::filter_index(left.coordinate),
315 Self::filter_index(right.coordinate),
316 )
317 }
318
319 fn localized_owners(&self, descriptor_index: usize, entity_index: usize) -> Vec<RowOwner> {
320 let mut owners = Vec::new();
321 for slot in 0..self.source.source_count() {
322 if self
323 .source
324 .change_source(slot)
325 .owns_descriptor(descriptor_index)
326 {
327 owners.push(RowOwner {
328 source_slot: slot,
329 entity_index,
330 });
331 }
332 }
333 owners
334 }
335
336 fn row_ids_for_owners(&self, owners: &[RowOwner]) -> Vec<usize> {
337 let mut seen = FastSet::default();
338 let mut row_ids = Vec::new();
339 for owner in owners {
340 let Some(ids) = self.rows_by_owner.get(owner) else {
341 continue;
342 };
343 for &row_id in ids {
344 if seen.insert(row_id) {
345 row_ids.push(row_id);
346 }
347 }
348 }
349 row_ids
350 }
351
352 #[cfg(test)]
353 pub(crate) fn debug_row_storage_len(&self) -> usize {
354 self.rows.len()
355 }
356
357 #[cfg(test)]
358 pub(crate) fn debug_free_row_count(&self) -> usize {
359 self.free_row_ids.len()
360 }
361}
362
363impl<S, Out, K, Src, F, KF, PF, W, Sc> IncrementalConstraint<S, Sc>
364 for Bi<S, Out, K, Src, F, KF, PF, W, Sc>
365where
366 S: Send + Sync + 'static,
367 Out: Send + Sync + 'static,
368 K: Eq + Hash + Send + Sync + 'static,
369 Src: Source<S, Out>,
370 F: UniFilter<S, Out>,
371 KF: Fn(&Out) -> K + Send + Sync,
372 PF: BiFilter<S, Out, Out>,
373 W: Fn(&Out, &Out) -> Sc + Send + Sync,
374 Sc: Score + 'static,
375{
376 fn evaluate(&self, solution: &S) -> Sc {
377 let rows = self.evaluate_rows(solution);
378
379 let mut total = Sc::zero();
380 for left_index in 0..rows.len() {
381 for right_index in (left_index + 1)..rows.len() {
382 total = total
383 + self.score_evaluation_pair(solution, &rows[left_index], &rows[right_index]);
384 }
385 }
386 total
387 }
388
389 fn match_count(&self, solution: &S) -> usize {
390 let rows = self.evaluate_rows(solution);
391
392 let mut count = 0;
393 for left_index in 0..rows.len() {
394 for right_index in (left_index + 1)..rows.len() {
395 if self.evaluation_pair_matches(solution, &rows[left_index], &rows[right_index]) {
396 count += 1;
397 }
398 }
399 }
400 count
401 }
402
403 fn initialize(&mut self, solution: &S) -> Sc {
404 self.reset();
405 let state = self.source.build_state(solution);
406 let mut rows = Vec::new();
407 self.source
408 .collect_all(solution, &state, |coordinate, output| {
409 if self.filter.test(solution, &output) {
410 rows.push((coordinate, output));
411 }
412 });
413 self.source_state = Some(state);
414
415 rows.into_iter()
416 .fold(Sc::zero(), |total, (coordinate, output)| {
417 total + self.insert_row(solution, coordinate, output)
418 })
419 }
420
421 fn on_insert(&mut self, solution: &S, entity_index: usize, descriptor_index: usize) -> Sc {
422 let owners = self.localized_owners(descriptor_index, entity_index);
423 self.ensure_source_state(solution);
424 {
425 let state = self.source_state.as_mut().expect("projected source state");
426 for owner in &owners {
427 self.source.insert_entity_state(
428 solution,
429 state,
430 owner.source_slot,
431 owner.entity_index,
432 );
433 }
434 }
435 let mut rows = Vec::new();
436 let state = self.source_state.as_ref().expect("projected source state");
437 for owner in &owners {
438 self.source.collect_entity(
439 solution,
440 state,
441 owner.source_slot,
442 owner.entity_index,
443 |coordinate, output| {
444 if self.filter.test(solution, &output) {
445 rows.push((coordinate, output));
446 }
447 },
448 );
449 }
450 let mut total = Sc::zero();
451 for (coordinate, output) in rows {
452 total = total + self.insert_row(solution, coordinate, output);
453 }
454 total
455 }
456
457 fn on_retract(&mut self, solution: &S, entity_index: usize, descriptor_index: usize) -> Sc {
458 let owners = self.localized_owners(descriptor_index, entity_index);
459 let mut total = Sc::zero();
460 for row_id in self.row_ids_for_owners(&owners) {
461 total = total + self.retract_row(solution, row_id);
462 }
463 if let Some(state) = self.source_state.as_mut() {
464 for owner in &owners {
465 self.source.retract_entity_state(
466 solution,
467 state,
468 owner.source_slot,
469 owner.entity_index,
470 );
471 }
472 }
473 total
474 }
475
476 fn reset(&mut self) {
477 self.source_state = None;
478 self.rows.clear();
479 self.free_row_ids.clear();
480 self.rows_by_owner.clear();
481 self.row_ids_by_coordinate.clear();
482 self.rows_by_key.clear();
483 }
484
485 fn name(&self) -> &str {
486 &self.constraint_ref.name
487 }
488
489 fn constraint_ref(&self) -> &ConstraintRef {
490 &self.constraint_ref
491 }
492
493 fn is_hard(&self) -> bool {
494 self.is_hard
495 }
496}