pumpkin_core/propagators/hypercube_linear/
hypercube.rs

1use pumpkin_checking::IntExt;
2use pumpkin_checking::VariableState;
3
4use crate::predicate;
5use crate::predicates::Predicate;
6use crate::variables::DomainId;
7
8/// Error that occurs when constructing a [`Hypercube`].
9///
10/// If the domain of a variable becomes empty, the hypercube is inconsistent and cannot be
11/// constructed.
12#[derive(Clone, Copy, Debug, thiserror::Error, PartialEq, Eq)]
13#[error("domain {0} is empty in the hypercube")]
14pub struct InconsistentHypercube(DomainId);
15
16/// A region in the solution space.
17///
18/// The hypercube will always be consistent.
19#[derive(Clone, Debug)]
20pub struct Hypercube {
21    state: VariableState<Predicate>,
22}
23
24impl Hypercube {
25    /// Create a new hypercube from a sequence of predicates.
26    ///
27    /// If the predicates are inconsistent, the [`Err`] variant is returned.
28    pub fn new(
29        predicates: impl IntoIterator<Item = Predicate>,
30    ) -> Result<Self, InconsistentHypercube> {
31        // Note: Ideally this would be an implementation of [`TryFrom`], however, that cannot be
32        // done in the same way due to a 'conflicting implementations' error.
33
34        let state = VariableState::prepare_for_conflict_check(predicates, None)
35            .map_err(InconsistentHypercube)?;
36
37        Ok(Hypercube { state })
38    }
39
40    /// Get all predicates that define the hypercube.
41    pub fn iter_predicates(&self) -> impl Iterator<Item = Predicate> + '_ {
42        self.state.domains().flat_map(|domain_id| {
43            let lower_bound_predicate =
44                if let IntExt::Int(lower_bound) = self.state.lower_bound(domain_id) {
45                    Some(predicate![domain_id >= lower_bound])
46                } else {
47                    None
48                };
49            let upper_bound_predicate =
50                if let IntExt::Int(upper_bound) = self.state.upper_bound(domain_id) {
51                    Some(predicate![domain_id <= upper_bound])
52                } else {
53                    None
54                };
55
56            [lower_bound_predicate, upper_bound_predicate]
57                .into_iter()
58                .flatten()
59                .chain(
60                    self.state
61                        .holes(domain_id)
62                        .map(|value| predicate![domain_id != value]),
63                )
64        })
65    }
66}
67
68#[cfg(test)]
69mod tests {
70    use super::*;
71    use crate::containers::HashSet;
72    use crate::predicate;
73    use crate::state::State;
74
75    #[test]
76    fn consistent_hypercube_can_be_created() {
77        let mut state = State::default();
78
79        let x = state.new_interval_variable(1, 10, Some("x".into()));
80        let y = state.new_interval_variable(1, 10, Some("y".into()));
81
82        let maybe_hypercube = Hypercube::new([predicate![x >= 2], predicate![y >= 2]]);
83
84        assert!(maybe_hypercube.is_ok());
85    }
86
87    #[test]
88    fn inconsistent_hypercube_can_be_created() {
89        let mut state = State::default();
90
91        let x = state.new_interval_variable(1, 10, Some("x".into()));
92        let y = state.new_interval_variable(1, 10, Some("y".into()));
93
94        let error = Hypercube::new([predicate![x >= 2], predicate![y >= 2], predicate![x <= 1]])
95            .expect_err("hypercube is inconsistent");
96
97        assert_eq!(InconsistentHypercube(x), error);
98    }
99
100    #[test]
101    fn hypercube_iters_predicates_from_constructor() {
102        let mut state = State::default();
103
104        let x = state.new_interval_variable(1, 10, Some("x".into()));
105        let y = state.new_interval_variable(1, 10, Some("y".into()));
106
107        let hypercube =
108            Hypercube::new([predicate![x >= 2], predicate![y >= 2]]).expect("not inconsistent");
109
110        assert_eq!(
111            [predicate![x >= 2], predicate![y >= 2]]
112                .into_iter()
113                .collect::<HashSet<_>>(),
114            hypercube.iter_predicates().collect::<HashSet<_>>(),
115        );
116    }
117
118    #[test]
119    fn iterating_predicates_ignores_subsumed_predicates() {
120        let mut state = State::default();
121
122        let x = state.new_interval_variable(1, 10, Some("x".into()));
123
124        let hypercube =
125            Hypercube::new([predicate![x >= 2], predicate![x >= 4]]).expect("not inconsistent");
126
127        assert_eq!(
128            [predicate![x >= 4]].into_iter().collect::<HashSet<_>>(),
129            hypercube.iter_predicates().collect::<HashSet<_>>(),
130        );
131    }
132}
pumpkin_core/propagators/hypercube_linear/hypercube.rs

pumpkin_core/propagators/hypercube_linear/
hypercube.rs
