Skip to main content

solverforge_scoring/constraint/projected/
bi.rs

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
17/// Symmetric self-join constraint over retained projected rows.
18///
19/// Projected rows from `Src` that pass `F` are bucketed by `KF`; each unordered
20/// pair of distinct rows with equal keys that passes the pair filter `PF` is
21/// scored by `W`, signed by the impact. Pairs are oriented by `RowCoordinate`,
22/// and the pair filter receives each row's primary owner entity index, not a
23/// storage row id. Produced by `stream::projected::Stream::join(equal(..))`.
24pub 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    /// Creates the constraint. `is_hard` is the reported hardness; `impact_type`
59    /// signs every pair weight.
60    #[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}