selen 0.15.5

Constraint Satisfaction Problem (CSP) solver
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203

use crate::{
    constraints::props::{Propagate, Prune},
    variables::VarId,
    variables::views::{Context, View},
};

/// Count constraint implementation
/// 
/// Ensures that exactly `count_var` variables from `vars` equal `target`.
/// This is a global constraint commonly used in scheduling, resource allocation,
/// and counting problems. 
///
/// The target parameter is generic over any View implementation, allowing:
/// - VarId for dynamic targets
/// - Val for constant targets  
/// - VarIdBin for computed targets
#[derive(Clone, Debug)]
#[doc(hidden)]
pub struct Count<T: View> {
    vars: Vec<VarId>,
    target: T,
    count_var: VarId,
}

impl<T: View> Count<T> {
    pub const fn new(vars: Vec<VarId>, target: T, count_var: VarId) -> Self {
        Self {
            vars,
            target,
            count_var,
        }
    }

    /// Count number of variables that definitely equal the target's value
    fn count_definitely_equal(&self, ctx: &Context) -> i64 {
        let target_min = self.target.min(ctx);
        let target_max = self.target.max(ctx);
        
        // If target is not fixed, we can't determine definite equality yet
        if target_min != target_max {
            return 0;
        }
        
        self.vars.iter()
            .filter(|&&var| {
                let min = var.min(ctx);
                let max = var.max(ctx);
                min == max && min == target_min
            })
            .count() as i64
    }

    /// Count number of variables that could possibly equal the target's value
    fn count_possibly_equal(&self, ctx: &Context) -> i64 {
        let target_min = self.target.min(ctx);
        let target_max = self.target.max(ctx);
        
        self.vars.iter()
            .filter(|&&var| {
                let var_min = var.min(ctx);
                let var_max = var.max(ctx);
                // Variable possibly equals target if their domains overlap
                var_min <= target_max && var_max >= target_min
            })
            .count() as i64
    }

    /// Propagate bounds on the count variable based on current variable states
    fn propagate_count_bounds(&self, ctx: &mut Context) -> Option<()> {
        let definitely_equal = self.count_definitely_equal(ctx);
        let possibly_equal = self.count_possibly_equal(ctx);
        
        // The count variable must be at least the number of variables definitely equal
        // and at most the number of variables possibly equal
        let definitely_equal_val = crate::variables::Val::ValI(definitely_equal as i32);
        let possibly_equal_val = crate::variables::Val::ValI(possibly_equal as i32);
        
        // Set lower bound: at least definitely_equal
        self.count_var.try_set_min(definitely_equal_val, ctx)?;
        
        // Set upper bound: at most possibly_equal  
        self.count_var.try_set_max(possibly_equal_val, ctx)?;
        
        // If count is fixed and target is fixed, we might be able to propagate to the vars
        let count_min = self.count_var.min(ctx);
        let count_max = self.count_var.max(ctx);
        let target_min = self.target.min(ctx);
        let target_max = self.target.max(ctx);
        
        if count_min == count_max && target_min == target_max {
            let target_count = match count_min {
                crate::variables::Val::ValI(i) => i as i64,
                crate::variables::Val::ValF(f) => f as i64,
            };
            
            // If we already have enough variables equal to target, forbid others from having target value
            if definitely_equal == target_count {
                for &var in &self.vars {
                    let min = var.min(ctx);
                    let max = var.max(ctx);
                    if min != max && min <= target_min && target_min <= max {
                        // Remove target_min from this variable's domain by constraining around it
                        // This is a simplified version - full domain removal is complex
                        match (target_min, min, max) {
                            (crate::variables::Val::ValI(tgt), crate::variables::Val::ValI(min_val), crate::variables::Val::ValI(max_val)) => {
                                if tgt == min_val && tgt < max_val {
                                    var.try_set_min(crate::variables::Val::ValI(tgt + 1), ctx)?;
                                } else if tgt == max_val && tgt > min_val {
                                    var.try_set_max(crate::variables::Val::ValI(tgt - 1), ctx)?;
                                }
                            }
                            _ => {} // Skip for float values
                        }
                    }
                }
            }
            // If we need all remaining possible variables to be equal to target
            else if possibly_equal == target_count {
                for &var in &self.vars {
                    let min = var.min(ctx);
                    let max = var.max(ctx);
                    if min != max && min <= target_min && target_min <= max {
                        // Force this variable to equal target_min
                        var.try_set_min(target_min, ctx)?;
                        var.try_set_max(target_min, ctx)?;
                    }
                }
            }
        }
        
        Some(())
    }
}

impl<T: View> Prune for Count<T> {
    fn prune(&self, ctx: &mut Context) -> Option<()> {
        // Propagate bounds on the count variable based on current variable states
        self.propagate_count_bounds(ctx)
    }
}

impl<T: View + 'static> Propagate for Count<T> {
    fn list_trigger_vars(&self) -> impl Iterator<Item = VarId> {
        let target_vars: Vec<VarId> = self.target.get_underlying_var().into_iter().collect();
        self.vars.iter()
            .copied()
            .chain(target_vars.into_iter())
            .chain(std::iter::once(self.count_var))
    }
}

#[cfg(test)]
mod test_count_direct {
    use super::*;
    use crate::variables::Vars;
    use crate::variables::views::Context;
    use crate::variables::Val;
    
    #[test]
    fn test_count_constraint_direct() {
        let mut vars = Vars::new();
        let v1 = vars.new_var_with_bounds(Val::int(1), Val::int(3));
        let v2 = vars.new_var_with_bounds(Val::int(1), Val::int(3));
        let v3 = vars.new_var_with_bounds(Val::int(1), Val::int(3));
        let target_var = vars.new_var_with_bounds(Val::int(1), Val::int(1));
        let count_var = vars.new_var_with_bounds(Val::int(0), Val::int(3));
        
        let count = Count::new(vec![v1, v2, v3], target_var, count_var);
        let mut events = Vec::new();
        let mut ctx = Context::new(&mut vars, &mut events);
        
        // This should work now - our implementation should run
        let result = count.prune(&mut ctx);
        
        assert!(result.is_some());
    }

    #[test]
    fn test_count_trait_object_dispatch() {
        println!("=== Testing Count trait object dispatch ===");
        
        let mut vars = Vars::new();
        let v1 = vars.new_var_with_bounds(Val::int(1), Val::int(3));
        let v2 = vars.new_var_with_bounds(Val::int(1), Val::int(3));
        let target_var = vars.new_var_with_bounds(Val::int(2), Val::int(2));
        let count_var = vars.new_var_with_bounds(Val::int(0), Val::int(2));
        
        let count = Count::new(vec![v1, v2], target_var, count_var);
        
        // Store as trait object exactly like the propagator system does
        let trait_object: Box<dyn Prune> = Box::new(count);
        let shared_trait_object = std::rc::Rc::new(trait_object);
        
        let mut events = Vec::new();
        let mut ctx = Context::new(&mut vars, &mut events);
        
        println!("Calling prune through trait object...");
        let result = shared_trait_object.as_ref().prune(&mut ctx);
        println!("Trait object prune result: {:?}", result.is_some());
        
        assert!(result.is_some(), "Count constraint should work through trait object");
    }
}