triblespace_core/query/
intersectionconstraint.rs

1use super::*;
2
3/// Logical conjunction of constraints (AND).
4///
5/// All children must agree on every variable binding. Built by the
6/// [`and!`](crate::and) macro or directly via [`new`](Self::new).
7///
8/// The intersection delegates to its children using cardinality-aware
9/// ordering: the child with the lowest [`estimate`](Constraint::estimate)
10/// proposes candidates, and the remaining children
11/// [`confirm`](Constraint::confirm) them in order of increasing estimate.
12/// This strategy keeps the candidate set small from the start and avoids
13/// materialising cross products.
14///
15/// Variables from all children are exposed as a single union, so the
16/// engine sees one flat set of variables regardless of how many
17/// sub-constraints contribute.
18pub struct IntersectionConstraint<C> {
19    constraints: Vec<C>,
20}
21
22impl<'a, C> IntersectionConstraint<C>
23where
24    C: Constraint<'a> + 'a,
25{
26    /// Creates an intersection over the given constraints.
27    pub fn new(constraints: Vec<C>) -> Self {
28        IntersectionConstraint { constraints }
29    }
30}
31
32impl<'a, C> Constraint<'a> for IntersectionConstraint<C>
33where
34    C: Constraint<'a> + 'a,
35{
36    /// Returns the union of all children's variable sets.
37    fn variables(&self) -> VariableSet {
38        self.constraints
39            .iter()
40            .fold(VariableSet::new_empty(), |vs, c| vs.union(c.variables()))
41    }
42
43    /// Returns the **minimum** estimate across children that constrain
44    /// `variable`. The tightest child bounds the search, reflecting the
45    /// intersection semantics: every child must agree, so the smallest
46    /// candidate set dominates.
47    fn estimate(&self, variable: VariableId, binding: &Binding) -> Option<usize> {
48        self.constraints
49            .iter()
50            .filter_map(|c| c.estimate(variable, binding))
51            .min()
52    }
53
54    /// Sorts children by estimate, lets the tightest one propose, then
55    /// confirms through the rest in ascending estimate order. Children
56    /// that return `None` for this variable are skipped entirely.
57    fn propose(&self, variable: VariableId, binding: &Binding, proposals: &mut Vec<RawValue>) {
58        let mut relevant_constraints: Vec<_> = self
59            .constraints
60            .iter()
61            .filter_map(|c| Some((c.estimate(variable, binding)?, c)))
62            .collect();
63        if relevant_constraints.is_empty() {
64            return;
65        }
66        relevant_constraints.sort_unstable_by_key(|(estimate, _)| *estimate);
67
68        relevant_constraints[0]
69            .1
70            .propose(variable, binding, proposals);
71
72        relevant_constraints[1..]
73            .iter()
74            .for_each(|(_, c)| c.confirm(variable, binding, proposals));
75    }
76
77    /// Confirms proposals through all children that constrain `variable`,
78    /// in order of increasing estimate.
79    fn confirm(&self, variable: VariableId, binding: &Binding, proposals: &mut Vec<RawValue>) {
80        let mut relevant_constraints: Vec<_> = self
81            .constraints
82            .iter()
83            .filter_map(|c| Some((c.estimate(variable, binding)?, c)))
84            .collect();
85        relevant_constraints.sort_unstable_by_key(|(estimate, _)| *estimate);
86
87        relevant_constraints
88            .iter()
89            .for_each(|(_, c)| c.confirm(variable, binding, proposals));
90    }
91
92    /// Returns `true` only when **every** child is satisfied.
93    fn satisfied(&self, binding: &Binding) -> bool {
94        self.constraints.iter().all(|c| c.satisfied(binding))
95    }
96
97    /// Returns the union of all children's influence sets for `variable`.
98    fn influence(&self, variable: VariableId) -> VariableSet {
99        self.constraints
100            .iter()
101            .fold(VariableSet::new_empty(), |acc, c| {
102                acc.union(c.influence(variable))
103            })
104    }
105}
106
107/// Combines constraints into an [`IntersectionConstraint`] (logical AND).
108///
109/// All constraints must agree on every variable binding for a result to
110/// be produced. Accepts one or more constraint expressions.
111///
112/// ```rust,ignore
113/// and!(set.pattern(e, a, v), allowed.has(v))
114/// ```
115#[macro_export]
116macro_rules! and {
117    ($($c:expr),+ $(,)?) => (
118        $crate::query::intersectionconstraint::IntersectionConstraint::new(vec![
119            $(Box::new($c) as Box<dyn $crate::query::Constraint>),+
120        ])
121    )
122}
123
124/// Re-export of the [`and!`] macro.
125pub use and;
triblespace_core/query/intersectionconstraint.rs

triblespace_core/query/
intersectionconstraint.rs
