unifier 0.1.0

Constraint satisfaction / optimization (CSP/COP) modeling and solver framework for Rust, built on pathwise
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

//! Explicit allowed and forbidden domain value filtering constraints.
//!
//! Reference:
//! - Rossi, F., van Beek, P., & Walsh, T. (2006). *Handbook of Constraint Programming*. Elsevier.

use crate::constraint::{Constraint, PropagationResult};
use crate::model::domain::TrailedDomains;
use crate::model::variable::VariableId;
use std::collections::{HashMap, HashSet};

/// Constraint enforcing `v in allowed_values`.
#[derive(Debug, Clone)]
pub struct AllowedValues {
    var: VariableId,
    allowed: HashSet<i64>,
    scope: [VariableId; 1],
}

impl AllowedValues {
    /// Creates an `AllowedValues` constraint for a variable.
    ///
    /// # Complexity
    /// Time & Space: O(K) where K is number of allowed values.
    pub fn new(var: VariableId, allowed_values: impl IntoIterator<Item = i64>) -> Self {
        let allowed: HashSet<i64> = allowed_values.into_iter().collect();
        Self {
            var,
            allowed,
            scope: [var],
        }
    }
}

impl Constraint for AllowedValues {
    fn name(&self) -> &str {
        "AllowedValues"
    }

    fn scope(&self) -> &[VariableId] {
        &self.scope
    }

    fn is_satisfied(&self, assignment: &HashMap<VariableId, i64>) -> bool {
        match assignment.get(&self.var) {
            Some(&val) => self.allowed.contains(&val),
            None => true,
        }
    }

    fn propagate(&self, domains: &mut TrailedDomains) -> PropagationResult {
        let mut changed = false;

        if let Some(domain) = domains.get_mut(&self.var) {
            let current_values = domain.values();
            for val in current_values {
                if !self.allowed.contains(&val) && domain.remove(val) {
                    changed = true;
                }
            }
            if domain.is_empty() {
                return PropagationResult::Conflict;
            }
        }

        PropagationResult::Success { changed }
    }
}

/// Constraint enforcing `v not in forbidden_values`.
#[derive(Debug, Clone)]
pub struct ForbiddenValues {
    var: VariableId,
    forbidden: HashSet<i64>,
    scope: [VariableId; 1],
}

impl ForbiddenValues {
    /// Creates a `ForbiddenValues` constraint for a variable.
    ///
    /// # Complexity
    /// Time & Space: O(K) where K is number of forbidden values.
    pub fn new(var: VariableId, forbidden_values: impl IntoIterator<Item = i64>) -> Self {
        let forbidden: HashSet<i64> = forbidden_values.into_iter().collect();
        Self {
            var,
            forbidden,
            scope: [var],
        }
    }
}

impl Constraint for ForbiddenValues {
    fn name(&self) -> &str {
        "ForbiddenValues"
    }

    fn scope(&self) -> &[VariableId] {
        &self.scope
    }

    fn is_satisfied(&self, assignment: &HashMap<VariableId, i64>) -> bool {
        match assignment.get(&self.var) {
            Some(&val) => !self.forbidden.contains(&val),
            None => true,
        }
    }

    fn propagate(&self, domains: &mut TrailedDomains) -> PropagationResult {
        let mut changed = false;

        if let Some(domain) = domains.get_mut(&self.var) {
            for &val in &self.forbidden {
                if domain.remove(val) {
                    changed = true;
                }
            }
            if domain.is_empty() {
                return PropagationResult::Conflict;
            }
        }

        PropagationResult::Success { changed }
    }
}