use super::*;
use crate::modelling::*;
use rustc_hash::{FxHashMap, FxHashSet};
use std::hash::Hasher;
use std::sync::Arc;
#[derive(Clone, deepsize::DeepSizeOf)]
struct GccProperty {
map: Arc<FxHashMap<isize, usize>>,
lo: Arc<Vec<usize>>,
saturates: Arc<Vec<bool>>,
min: Vec<usize>,
max: Vec<usize>,
}
impl GccProperty {
fn new(
n: usize,
map: Arc<FxHashMap<isize, usize>>,
lo: Arc<Vec<usize>>,
saturates: Arc<Vec<bool>>,
min_seed: usize,
) -> Self {
Self {
map,
lo,
saturates,
min: vec![min_seed; n],
max: vec![0; n],
}
}
fn has_no_path(&self) -> bool {
self.min.iter().zip(&self.max).any(|(min, max)| min > max)
}
}
#[derive(Clone, deepsize::DeepSizeOf)]
pub struct Gcc {
variables: Vec<VariableIndex>,
bounds: Vec<(isize, usize, usize)>,
val_to_bit: Arc<FxHashMap<isize, usize>>,
lo: Arc<Vec<usize>>,
saturates: Arc<Vec<bool>>,
layer_in_scope: Vec<u64>,
}
impl Gcc {
pub fn new(variables: Vec<VariableIndex>, bounds: Vec<(isize, usize, usize)>) -> Self {
let distinct: FxHashSet<VariableIndex> = variables.iter().copied().collect();
if distinct.len() != variables.len() {
panic!("Gcc does not support a variable repeated in its scope");
}
let values: FxHashSet<isize> = bounds.iter().map(|&(value, _, _)| value).collect();
if values.len() != bounds.len() {
panic!("Gcc does not support two bounds for the same value");
}
let val_to_bit = Arc::new(
bounds
.iter()
.copied()
.enumerate()
.map(|(bit, (value, _, _))| (value, bit))
.collect(),
);
let lo: Vec<usize> = bounds.iter().copied().map(|(_, lo, _)| lo).collect();
let saturates: Vec<bool> = bounds
.iter()
.map(|&(_, _, hi)| hi >= variables.len())
.collect();
Self {
variables,
bounds,
val_to_bit,
lo: Arc::new(lo),
saturates: Arc::new(saturates),
layer_in_scope: vec![],
}
}
}
impl Constraint for Gcc {
fn structural_key(&self, _problem: &Problem) -> ConstraintShapeKey {
let mut bounds = self.bounds.clone();
bounds.sort_unstable_by_key(|&(value, _, _)| value);
ConstraintShapeKey::Gcc {
arity: self.variables.len(),
bounds,
}
}
fn update_variable_ordering(&mut self, order: &[VariableIndex]) {
let scope: FxHashSet<VariableIndex> = self.variables.iter().copied().collect();
let mut found = 0;
self.layer_in_scope = vec![0; order.len() / 64 + 1];
for (layer, variable) in order.iter().enumerate() {
if scope.contains(variable) {
self.layer_in_scope[layer / 64] |= 1 << (layer % 64);
found += 1;
}
}
debug_assert_eq!(
found,
scope.len(),
"a variable of the scope is missing from the ordering"
);
}
fn is_layer_in_scope(&self, layer: usize) -> bool {
debug_assert!(
!self.layer_in_scope.is_empty(),
"update_variable_ordering has not been called"
);
self.layer_in_scope[layer / 64] & (1 << (layer % 64)) != 0
}
fn is_assignment_invalid(
&self,
parent: &dyn ConstraintProperty,
child: &dyn ConstraintProperty,
_layer: usize,
assignment: isize,
) -> bool {
let parent = parent.as_any().downcast_ref::<GccProperty>().unwrap_or_else(|| {
panic!(
"Calling is_assignment_invalid on parent property of type {} instead of GccProperty",
parent.name()
);
});
let child = child.as_any().downcast_ref::<GccProperty>().unwrap_or_else(|| {
panic!(
"Calling is_assignment_invalid on child property of type {} instead of GccProperty",
child.name()
);
});
if parent.has_no_path() || child.has_no_path() {
return true;
}
let bit = self.val_to_bit.get(&assignment).copied();
for (slot, (_, lb, ub)) in self.bounds.iter().copied().enumerate() {
let delta = usize::from(bit == Some(slot));
let min = parent.min[slot] + child.min[slot] + delta;
if min > ub {
return true;
}
let max = parent.max[slot] + child.max[slot] + delta;
if max < lb {
return true;
}
}
false
}
fn iter_scope(&self) -> Box<dyn Iterator<Item = VariableIndex> + '_> {
Box::new(self.variables.iter().copied())
}
fn is_satisfied(&self, assignment: &[isize]) -> bool {
self.bounds.iter().all(|&(value, lo, hi)| {
let count = self
.variables
.iter()
.filter(|variable| assignment[variable.0] == value)
.count();
lo <= count && count <= hi
})
}
fn name(&self) -> &'static str {
"GCC"
}
fn as_any(&self) -> &dyn std::any::Any {
self
}
fn identity_property(&self) -> Box<dyn ConstraintProperty> {
Box::new(GccProperty::new(
self.bounds.len(),
self.val_to_bit.clone(),
self.lo.clone(),
self.saturates.clone(),
usize::MAX,
))
}
fn empty_property(&self) -> Box<dyn ConstraintProperty> {
Box::new(GccProperty::new(
self.bounds.len(),
self.val_to_bit.clone(),
self.lo.clone(),
self.saturates.clone(),
0,
))
}
}
impl ConstraintProperty for GccProperty {
fn update(&mut self, other: &dyn ConstraintProperty, assignment: isize, in_scope: bool) {
let other = other
.as_any()
.downcast_ref::<GccProperty>()
.unwrap_or_else(|| {
panic!(
"Calling update on property {} with other property of type {}",
self.name(),
other.name()
);
});
if other.has_no_path() {
return;
}
let target_bit = if in_scope {
match self.map.get(&assignment) {
None => self.min.len(),
Some(&bit) => bit,
}
} else {
self.min.len()
};
for bit in 0..self.min.len() {
if bit == target_bit {
let mut new_min = other.min[bit] + 1;
let mut new_max = other.max[bit] + 1;
if self.saturates[bit] {
new_min = new_min.min(self.lo[bit]);
new_max = new_max.min(self.lo[bit]);
}
self.min[bit] = self.min[bit].min(new_min);
self.max[bit] = self.max[bit].max(new_max);
} else {
self.min[bit] = self.min[bit].min(other.min[bit]);
self.max[bit] = self.max[bit].max(other.max[bit]);
}
}
}
fn merge(&mut self, other: &dyn ConstraintProperty) {
let other = other
.as_any()
.downcast_ref::<GccProperty>()
.unwrap_or_else(|| {
panic!(
"Calling merge on property {} with other property of type {}",
self.name(),
other.name()
);
});
for bit in 0..self.min.len() {
self.min[bit] = self.min[bit].min(other.min[bit]);
self.max[bit] = self.max[bit].max(other.max[bit]);
}
}
fn order_key(&self) -> Vec<f64> {
self.min
.iter()
.chain(self.max.iter())
.map(|&x| x as f64)
.collect()
}
fn hash(&self, hasher: &mut dyn Hasher) {
for &bound in self.min.iter() {
hasher.write_usize(bound);
}
for &bound in self.max.iter() {
hasher.write_usize(bound);
}
}
fn eq(&self, other: &dyn ConstraintProperty) -> bool {
let other = other
.as_any()
.downcast_ref::<GccProperty>()
.unwrap_or_else(|| {
panic!(
"Calling eq on property {} with other property of type {}",
self.name(),
other.name()
);
});
self.min == other.min && self.max == other.max
}
fn is_single_state(&self) -> bool {
!self.has_no_path() && self.min == self.max
}
fn as_any(&self) -> &dyn Any {
self
}
fn name(&self) -> &'static str {
"GccProperty"
}
}
#[cfg(test)]
mod test_gcc {
use super::GccProperty;
use crate::constraints::*;
use crate::constraints::{
AllDifferent, Constraint, ConstraintProperty, ConstraintShapeKey, Gcc,
};
use crate::mdd::compiler::test_mdd::*;
use crate::mdd::heuristics::*;
use crate::mdd::*;
use crate::modelling::*;
use rustc_hash::FxHasher;
use std::hash::Hasher;
use std::sync::Arc;
fn dom(n: isize) -> Vec<isize> {
(0..n).collect()
}
fn scoped(
domains: &[Vec<isize>],
scope: &[usize],
bounds: &[(isize, usize, usize)],
) -> (Problem, Vec<VariableIndex>) {
let mut problem = Problem::default();
let vars: Vec<VariableIndex> = domains
.iter()
.map(|d| problem.add_variable(d.clone()))
.collect();
gcc(
&mut problem,
scope.iter().map(|&i| vars[i]).collect(),
bounds.to_vec(),
);
(problem, vars)
}
fn full(
domains: &[Vec<isize>],
bounds: &[(isize, usize, usize)],
) -> (Problem, Vec<VariableIndex>) {
scoped(domains, &(0..domains.len()).collect::<Vec<_>>(), bounds)
}
fn gcc_of(n: usize, bounds: &[(isize, usize, usize)]) -> Gcc {
let mut problem = Problem::default();
let vars = problem.add_variables(n, dom(3));
let mut constraint = Gcc::new(vars.clone(), bounds.to_vec());
constraint.update_variable_ordering(&vars);
constraint
}
fn compile(problem: Problem, order: Vec<usize>, width: usize) -> Mdd {
compile_to_compiler(problem, order, width).into_mdd()
}
fn compile_to_compiler(problem: Problem, order: Vec<usize>, width: usize) -> Compiler {
let problem = Arc::new(problem);
let constraints: Vec<ConstraintIndex> = problem.iter_constraints().collect();
let mut compiler = Compiler::new(
problem,
CompilationHeuristic {
ordering: OrderingHeuristic::Custom(order),
merge: MergeHeuristic::LessRelaxed,
selection: SelectHeuristic::Greedy,
},
&constraints,
);
if width > 1 {
compiler.refine(width);
}
compiler
}
fn settled(problem: Problem, order: Vec<usize>) -> Mdd {
let mut compiler = compile_to_compiler(problem, order, usize::MAX);
for _ in 0..10 {
if compiler.mdd().is_unsat() {
break;
}
compiler.propagate_constraints();
}
compiler.into_mdd()
}
fn accepted(mdd: &Mdd) -> Vec<Vec<isize>> {
if mdd.is_unsat() {
return vec![];
}
let mut solutions = get_all_solutions(mdd);
solutions.sort();
solutions
}
type Case = (Vec<Vec<isize>>, Vec<(isize, usize, usize)>);
type Spec<'a> = (&'a [usize], &'a [(isize, usize, usize)]);
fn expected(domains: &[Vec<isize>], specs: &[Spec]) -> Vec<Vec<isize>> {
let mut tuples: Vec<Vec<isize>> = vec![vec![]];
for domain in domains {
let mut next = vec![];
for prefix in &tuples {
for &value in domain {
let mut tuple = prefix.clone();
tuple.push(value);
next.push(tuple);
}
}
tuples = next;
}
tuples.retain(|t| {
specs.iter().all(|(scope, bounds)| {
bounds.iter().all(|&(value, lo, hi)| {
let mut count = 0;
for &position in scope.iter() {
if t[position] == value {
count += 1;
}
}
lo <= count && count <= hi
})
})
});
tuples.sort();
tuples
}
fn path_property(constraint: &Gcc, values: &[isize]) -> Box<dyn ConstraintProperty> {
let mut property = constraint.empty_property();
for &value in values {
let mut next = constraint.identity_property();
next.update(&*property, value, true);
property = next;
}
property
}
fn interval(
constraint: &Gcc,
value: isize,
lo: usize,
hi: usize,
) -> Box<dyn ConstraintProperty> {
let mut property = path_property(constraint, &vec![value; lo]);
property.merge(&*path_property(constraint, &vec![value; hi]));
property
}
fn helper() -> Gcc {
gcc_of(10, &[(1, 0, 3), (2, 0, 3)])
}
fn clone_of(property: &dyn ConstraintProperty) -> Box<dyn ConstraintProperty> {
Box::new(
property
.as_any()
.downcast_ref::<GccProperty>()
.unwrap()
.clone(),
)
}
fn bounds_of(property: &dyn ConstraintProperty, value: isize) -> (usize, usize) {
let property = property.as_any().downcast_ref::<GccProperty>().unwrap();
let slot = property.map[&value];
(property.min[slot], property.max[slot])
}
fn same(a: &dyn ConstraintProperty, b: &dyn ConstraintProperty) -> bool {
ConstraintProperty::eq(a, b)
}
fn hash_of(property: &dyn ConstraintProperty) -> u64 {
let mut hasher = FxHasher::default();
property.hash(&mut hasher);
hasher.finish()
}
fn foreign() -> Box<dyn ConstraintProperty> {
let mut problem = Problem::default();
let vars = problem.add_variables(2, dom(2));
AllDifferent::new(vars, &problem).identity_property()
}
#[test]
fn is_satisfied_agrees_with_the_definition() {
let lists: Vec<Vec<(isize, usize, usize)>> = vec![
vec![(1, 1, 2)],
vec![(0, 0, 1), (1, 1, 1)],
vec![(2, 2, 3), (0, 0, 0)],
vec![(1, 3, 4)],
vec![(0, 1, 2), (1, 1, 2), (2, 1, 2)],
];
for bounds in lists {
let constraint = gcc_of(3, &bounds);
for a in 0..3 {
for b in 0..3 {
for c in 0..3 {
let tuple = [a, b, c];
let holds = bounds.iter().all(|&(value, lo, hi)| {
let count = tuple.iter().filter(|&&v| v == value).count();
lo <= count && count <= hi
});
assert_eq!(
constraint.is_satisfied(&tuple),
holds,
"{tuple:?} with {bounds:?}"
);
}
}
}
}
}
#[test]
fn is_satisfied_on_hand_written_cases() {
let constraint = gcc_of(4, &[(1, 1, 1), (2, 0, 1)]);
assert!(constraint.is_satisfied(&[0, 1, 2, 0]));
assert!(constraint.is_satisfied(&[0, 0, 1, 0]));
assert!(!constraint.is_satisfied(&[1, 1, 0, 0]));
assert!(!constraint.is_satisfied(&[2, 2, 1, 0]));
assert!(!constraint.is_satisfied(&[0, 0, 2, 0]));
}
#[test]
fn an_unbounded_value_is_free() {
let constraint = gcc_of(2, &[(0, 1, 1)]);
assert!(constraint.is_satisfied(&[0, 3]));
assert!(constraint.is_satisfied(&[3, 0]));
assert!(!constraint.is_satisfied(&[3, 3]));
assert!(!constraint.is_satisfied(&[0, 0]));
}
#[test]
fn a_value_that_never_occurs_counts_zero() {
let must_occur = gcc_of(2, &[(9, 1, 2)]);
let may_not_occur = gcc_of(2, &[(9, 0, 2)]);
for a in 0..2 {
for b in 0..2 {
assert!(!must_occur.is_satisfied(&[a, b]));
assert!(may_not_occur.is_satisfied(&[a, b]));
}
}
}
#[test]
fn no_bound_accepts_everything() {
let constraint = gcc_of(2, &[]);
assert!(constraint.is_satisfied(&[0, 0]));
assert!(constraint.is_satisfied(&[1, 2]));
}
#[test]
fn empty_scope_counts_zero() {
assert!(Gcc::new(vec![], vec![]).is_satisfied(&[]));
assert!(Gcc::new(vec![], vec![(1, 0, 2)]).is_satisfied(&[]));
assert!(!Gcc::new(vec![], vec![(1, 1, 2)]).is_satisfied(&[]));
}
#[test]
fn bounds_that_cannot_be_met_are_never_satisfied() {
let crossed = gcc_of(3, &[(1, 2, 1)]);
let too_many = gcc_of(3, &[(1, 4, 5)]);
for a in 0..2 {
for b in 0..2 {
for c in 0..2 {
assert!(!crossed.is_satisfied(&[a, b, c]));
assert!(!too_many.is_satisfied(&[a, b, c]));
}
}
}
}
#[test]
fn is_satisfied_ignores_out_of_scope_variables() {
let mut problem = Problem::default();
let vars = problem.add_variables(3, dom(2));
let constraint = Gcc::new(vec![vars[0], vars[2]], vec![(1, 2, 2)]);
assert!(constraint.is_satisfied(&[1, 0, 1]));
assert!(!constraint.is_satisfied(&[1, 1, 0]));
}
#[test]
#[should_panic]
fn is_satisfied_panics_on_an_assignment_that_is_too_short() {
gcc_of(3, &[(1, 0, 3)]).is_satisfied(&[0, 1]);
}
#[test]
#[should_panic(expected = "repeated")]
fn a_repeated_variable_is_rejected() {
let mut problem = Problem::default();
let x = problem.add_variable(dom(3));
let y = problem.add_variable(dom(3));
Gcc::new(vec![x, y, x], vec![(1, 0, 2)]);
}
#[test]
#[should_panic(expected = "two bounds")]
fn two_bounds_for_one_value_are_rejected() {
let mut problem = Problem::default();
let vars = problem.add_variables(3, dom(3));
Gcc::new(vars, vec![(1, 0, 2), (2, 0, 1), (1, 1, 3)]);
}
#[test]
fn scope_name_and_structural_key() {
let mut problem = Problem::default();
let vars = problem.add_variables(3, dom(5));
let constraint = Gcc::new(vars.clone(), vec![(2, 0, 1), (0, 1, 1)]);
assert_eq!(constraint.iter_scope().collect::<Vec<_>>(), vars);
assert_eq!(constraint.name(), "GCC");
assert_eq!(
constraint.structural_key(&problem),
ConstraintShapeKey::Gcc {
arity: 3,
bounds: vec![(0, 1, 1), (2, 0, 1)]
}
);
}
#[test]
fn the_structural_key_does_not_depend_on_the_order_of_the_bounds() {
let mut problem = Problem::default();
let vars = problem.add_variables(3, dom(5));
let a = Gcc::new(vars.clone(), vec![(0, 1, 1), (2, 0, 1), (4, 0, 2)]);
let b = Gcc::new(vars.clone(), vec![(4, 0, 2), (0, 1, 1), (2, 0, 1)]);
let different_bound = Gcc::new(vars.clone(), vec![(0, 1, 1), (2, 0, 1), (4, 0, 3)]);
let different_value = Gcc::new(vars, vec![(0, 1, 1), (2, 0, 1), (3, 0, 2)]);
assert_eq!(a.structural_key(&problem), b.structural_key(&problem));
assert_ne!(
a.structural_key(&problem),
different_bound.structural_key(&problem)
);
assert_ne!(
a.structural_key(&problem),
different_value.structural_key(&problem)
);
}
#[test]
fn layers_in_scope_follow_the_variable_ordering() {
let mut problem = Problem::default();
let vars = problem.add_variables(4, dom(2));
let mut constraint = Gcc::new(vec![vars[0], vars[2], vars[3]], vec![(1, 0, 1)]);
constraint.update_variable_ordering(&[vars[3], vars[1], vars[0], vars[2]]);
assert!(constraint.is_layer_in_scope(0));
assert!(!constraint.is_layer_in_scope(1));
assert!(constraint.is_layer_in_scope(2));
assert!(constraint.is_layer_in_scope(3));
}
#[test]
fn layers_beyond_the_first_word_are_tracked() {
let mut problem = Problem::default();
let vars = problem.add_variables(130, dom(2));
let scope_layers = [0usize, 63, 64, 65, 129];
let scope: Vec<VariableIndex> = scope_layers.iter().map(|&l| vars[l]).collect();
let mut constraint = Gcc::new(scope, vec![(1, 0, 2)]);
constraint.update_variable_ordering(&vars);
for layer in 0..130 {
assert_eq!(
constraint.is_layer_in_scope(layer),
scope_layers.contains(&layer),
"layer {layer}"
);
}
}
#[test]
fn a_new_ordering_replaces_the_previous_one() {
let mut problem = Problem::default();
let vars = problem.add_variables(3, dom(2));
let mut constraint = Gcc::new(vec![vars[0], vars[1]], vec![(1, 0, 1)]);
constraint.update_variable_ordering(&[vars[0], vars[1], vars[2]]);
assert!(
constraint.is_layer_in_scope(0)
&& constraint.is_layer_in_scope(1)
&& !constraint.is_layer_in_scope(2)
);
constraint.update_variable_ordering(&[vars[2], vars[0], vars[1]]);
assert!(
!constraint.is_layer_in_scope(0)
&& constraint.is_layer_in_scope(1)
&& constraint.is_layer_in_scope(2)
);
}
#[cfg(debug_assertions)]
#[test]
#[should_panic]
fn is_layer_in_scope_panics_before_the_ordering_is_set() {
let mut problem = Problem::default();
let vars = problem.add_variables(2, dom(2));
Gcc::new(vars, vec![(1, 0, 1)]).is_layer_in_scope(0);
}
#[cfg(debug_assertions)]
#[test]
#[should_panic]
fn update_variable_ordering_panics_when_a_scope_variable_is_missing() {
let mut problem = Problem::default();
let vars = problem.add_variables(2, dom(2));
let mut constraint = Gcc::new(vars.clone(), vec![(1, 0, 1)]);
constraint.update_variable_ordering(&[vars[0]]);
}
#[test]
fn empty_property_is_the_zero_interval_of_every_value() {
let constraint = gcc_of(4, &[(1, 0, 2), (2, 1, 3)]);
let empty = constraint.empty_property();
assert_eq!(bounds_of(&*empty, 1), (0, 0));
assert_eq!(bounds_of(&*empty, 2), (0, 0));
assert_eq!(empty.order_key(), vec![0.0; 4]);
}
#[test]
fn identity_property_holds_the_no_path_sentinels() {
let constraint = gcc_of(4, &[(1, 0, 2), (2, 1, 3)]);
let identity = constraint.identity_property();
assert_eq!(bounds_of(&*identity, 1), (usize::MAX, 0));
assert_eq!(bounds_of(&*identity, 2), (usize::MAX, 0));
assert!(!same(&*identity, &*constraint.empty_property()));
}
#[test]
fn update_counts_only_the_slot_of_the_value() {
let constraint = gcc_of(6, &[(1, 0, 3), (2, 0, 3)]);
let one = path_property(&constraint, &[1]);
assert_eq!(bounds_of(&*one, 1), (1, 1));
assert_eq!(bounds_of(&*one, 2), (0, 0));
let mixed = path_property(&constraint, &[1, 2, 2]);
assert_eq!(bounds_of(&*mixed, 1), (1, 1));
assert_eq!(bounds_of(&*mixed, 2), (2, 2));
}
#[test]
fn update_with_an_unbounded_value_copies_the_parent() {
let constraint = gcc_of(6, &[(1, 0, 3), (2, 0, 3)]);
let parent = path_property(&constraint, &[1, 2]);
let mut child = constraint.identity_property();
child.update(&*parent, 0, true);
assert!(same(&*child, &*parent));
}
#[test]
fn update_out_of_scope_copies_the_parent() {
let constraint = gcc_of(6, &[(1, 0, 3), (2, 0, 3)]);
let parent = path_property(&constraint, &[1, 2]);
let mut child = constraint.identity_property();
child.update(&*parent, 1, false);
assert!(same(&*child, &*parent));
}
#[test]
fn a_value_whose_upper_bound_can_be_reached_keeps_exact_counts() {
let constraint = gcc_of(4, &[(1, 2, 3)]);
assert_eq!(bounds_of(&*path_property(&constraint, &[1; 3]), 1), (3, 3));
}
#[test]
fn a_value_whose_upper_bound_can_never_be_reached_is_capped_at_its_lower_bound() {
let constraint = gcc_of(3, &[(1, 2, 3)]);
assert_eq!(bounds_of(&*path_property(&constraint, &[1]), 1), (1, 1));
assert_eq!(bounds_of(&*path_property(&constraint, &[1, 1]), 1), (2, 2));
assert_eq!(
bounds_of(&*path_property(&constraint, &[1, 1, 1]), 1),
(2, 2)
);
}
#[test]
fn the_cap_applies_to_each_value_on_its_own() {
let constraint = gcc_of(3, &[(1, 1, 3), (2, 0, 1)]);
let property = path_property(&constraint, &[1, 1, 2, 2]);
assert_eq!(bounds_of(&*property, 1), (1, 1));
assert_eq!(bounds_of(&*property, 2), (2, 2));
}
#[test]
fn folding_two_parents_takes_the_extreme_counts_of_each_value() {
let constraint = helper();
let mut node = constraint.identity_property();
node.update(&*path_property(&constraint, &[1]), 1, true);
node.update(&*path_property(&constraint, &[2]), 1, true);
assert_eq!(bounds_of(&*node, 1), (1, 2));
assert_eq!(bounds_of(&*node, 2), (0, 1));
}
#[test]
fn folding_a_wide_interval_shifts_both_ends() {
let constraint = helper();
let mut node = constraint.identity_property();
node.update(&*interval(&constraint, 1, 0, 1), 1, true);
node.update(&*interval(&constraint, 1, 2, 3), 1, true);
assert_eq!(bounds_of(&*node, 1), (1, 4));
}
#[test]
fn folding_does_not_depend_on_the_order_of_the_parents() {
let constraint = helper();
let left = path_property(&constraint, &[1, 1]);
let right = path_property(&constraint, &[2]);
let mut lr = constraint.identity_property();
lr.update(&*left, 2, true);
lr.update(&*right, 2, true);
let mut rl = constraint.identity_property();
rl.update(&*right, 2, true);
rl.update(&*left, 2, true);
assert!(same(&*lr, &*rl));
}
#[test]
fn a_parent_without_paths_stays_without_paths() {
let constraint = helper();
let mut node = constraint.identity_property();
node.update(&*constraint.identity_property(), 1, true);
assert!(same(&*node, &*constraint.identity_property()));
node.update(&*path_property(&constraint, &[2]), 1, true);
assert_eq!(bounds_of(&*node, 1), (1, 1));
assert_eq!(bounds_of(&*node, 2), (1, 1));
}
#[test]
fn merge_takes_the_smallest_min_and_the_largest_max_of_each_value() {
let constraint = helper();
let mut a = path_property(&constraint, &[1, 1, 2]);
a.merge(&*path_property(&constraint, &[1, 2, 2]));
assert_eq!(bounds_of(&*a, 1), (1, 2));
assert_eq!(bounds_of(&*a, 2), (1, 2));
assert_eq!(a.order_key(), vec![1.0, 1.0, 2.0, 2.0]);
}
#[test]
fn merge_is_idempotent_commutative_and_has_the_identity_as_neutral() {
let constraint = helper();
let a = path_property(&constraint, &[1, 2]);
let b = interval(&constraint, 2, 0, 3);
let mut twice = clone_of(&*a);
twice.merge(&*a);
assert!(same(&*twice, &*a));
let mut ab = clone_of(&*a);
ab.merge(&*b);
let mut ba = clone_of(&*b);
ba.merge(&*a);
assert!(same(&*ab, &*ba));
let mut with_identity = clone_of(&*a);
with_identity.merge(&*constraint.identity_property());
assert!(same(&*with_identity, &*a));
}
#[test]
fn eq_and_hash_compare_every_value() {
let constraint = helper();
let a = path_property(&constraint, &[1, 2]);
assert!(same(&*a, &*path_property(&constraint, &[2, 1])));
assert_eq!(hash_of(&*a), hash_of(&*path_property(&constraint, &[2, 1])));
for other in [
path_property(&constraint, &[1]),
path_property(&constraint, &[2]),
interval(&constraint, 1, 1, 2),
{
let mut p = path_property(&constraint, &[1, 2]);
p.merge(&*path_property(&constraint, &[1, 2, 2]));
p
},
] {
assert!(!same(&*a, &*other));
assert_ne!(hash_of(&*a), hash_of(&*other));
}
}
#[test]
fn a_gcc_without_bounds_has_a_single_state() {
let constraint = gcc_of(3, &[]);
let identity = constraint.identity_property();
let empty = constraint.empty_property();
assert!(same(&*identity, &*empty));
let mut node = constraint.identity_property();
node.update(&*empty, 1, true);
assert!(same(&*node, &*empty));
for value in 0..3 {
assert!(!constraint.is_assignment_invalid(&*empty, &*empty, 1, value));
}
}
#[test]
#[should_panic(expected = "Calling update on property")]
fn update_with_a_property_of_another_constraint_is_rejected() {
helper().identity_property().update(&*foreign(), 0, true);
}
#[test]
#[should_panic(expected = "Calling merge on property")]
fn merge_with_a_property_of_another_constraint_is_rejected() {
helper().identity_property().merge(&*foreign());
}
#[test]
#[should_panic(expected = "Calling eq on property")]
fn eq_with_a_property_of_another_constraint_is_rejected() {
same(&*helper().identity_property(), &*foreign());
}
#[test]
fn the_bounds_of_a_value_are_inclusive() {
let helper = helper();
let parent = interval(&helper, 1, 1, 2);
let child = interval(&helper, 1, 0, 1);
let cases = [
(5, 5, 1, true), (4, 4, 1, false), (0, 2, 1, false), (0, 1, 1, true), (4, 4, 0, true), (3, 3, 0, false), (0, 1, 0, false), (0, 0, 0, true), ];
for (lo, hi, value, invalid) in cases {
let constraint = gcc_of(10, &[(1, lo, hi), (2, 0, 3)]);
assert_eq!(
constraint.is_assignment_invalid(&*parent, &*child, 1, value),
invalid,
"bounds [{lo}, {hi}] edge value {value}"
);
}
}
#[test]
fn every_bounded_value_is_checked() {
let helper = helper();
let nothing = helper.empty_property();
let needs_two = gcc_of(10, &[(1, 0, 3), (2, 3, 3)]);
assert!(needs_two.is_assignment_invalid(&*nothing, &*nothing, 1, 1));
let needs_one = gcc_of(10, &[(1, 3, 3), (2, 0, 3)]);
assert!(needs_one.is_assignment_invalid(&*nothing, &*nothing, 1, 2));
let fine = gcc_of(10, &[(1, 0, 3), (2, 0, 3)]);
assert!(!fine.is_assignment_invalid(&*nothing, &*nothing, 1, 1));
}
#[test]
fn an_edge_with_an_unbounded_value_can_be_invalid() {
let constraint = gcc_of(10, &[(1, 2, 3), (2, 0, 3)]);
let nothing = constraint.empty_property();
assert!(constraint.is_assignment_invalid(&*nothing, &*nothing, 1, 0));
let one = path_property(&constraint, &[1]);
assert!(!constraint.is_assignment_invalid(&*one, &*one, 1, 0));
}
#[test]
fn only_the_value_of_the_edge_is_shifted() {
let constraint = gcc_of(10, &[(1, 0, 1), (2, 0, 1)]);
let parent = path_property(&constraint, &[1]);
let child = constraint.empty_property();
assert!(constraint.is_assignment_invalid(&*parent, &*child, 1, 1));
assert!(!constraint.is_assignment_invalid(&*parent, &*child, 1, 2));
assert!(!constraint.is_assignment_invalid(&*parent, &*child, 1, 0));
}
#[test]
fn the_parent_and_the_child_both_count() {
let constraint = gcc_of(10, &[(1, 2, 2), (2, 0, 3)]);
let one = path_property(&constraint, &[1]);
let none = constraint.empty_property();
assert!(!constraint.is_assignment_invalid(&*one, &*none, 1, 1));
assert!(!constraint.is_assignment_invalid(&*none, &*one, 1, 1));
assert!(constraint.is_assignment_invalid(&*one, &*one, 1, 1));
}
#[test]
fn an_edge_next_to_a_node_without_paths_is_invalid() {
let constraint = helper();
let identity = constraint.identity_property();
let real = path_property(&constraint, &[1]);
assert!(constraint.is_assignment_invalid(&*identity, &*identity, 0, 0));
assert!(constraint.is_assignment_invalid(&*identity, &*real, 0, 1));
assert!(constraint.is_assignment_invalid(&*real, &*identity, 0, 1));
}
#[test]
#[should_panic(expected = "instead of GccProperty")]
fn a_property_of_another_constraint_is_rejected() {
let constraint = helper();
let own = constraint.empty_property();
constraint.is_assignment_invalid(&*foreign(), &*own, 0, 0);
}
fn permutations(n: usize) -> Vec<Vec<usize>> {
if n == 0 {
return vec![vec![]];
}
let mut result = vec![];
for rest in permutations(n - 1) {
for position in 0..=rest.len() {
let mut order = rest.clone();
order.insert(position, n - 1);
result.push(order);
}
}
result
}
#[test]
fn exact_mdd_for_small_cases_and_every_ordering() {
let cases: Vec<Case> = vec![
(
vec![dom(3), dom(3), dom(3)],
vec![(0, 0, 1), (1, 0, 1), (2, 0, 1)],
),
(vec![dom(2); 4], vec![(1, 2, 2)]),
(vec![dom(3), dom(3), dom(3)], vec![(0, 1, 2), (2, 0, 1)]),
(vec![dom(2), dom(2), dom(2)], vec![(1, 0, 3)]),
(
vec![dom(3), dom(3), dom(3), dom(3)],
vec![(0, 1, 1), (1, 1, 1)],
),
(
vec![vec![-1, 4], vec![4, 7], vec![-1, 7]],
vec![(4, 1, 1), (-1, 0, 1)],
),
(vec![dom(3), vec![5, 6], dom(3)], vec![(5, 1, 2), (0, 1, 1)]),
(vec![dom(3); 4], vec![(0, 1, 4), (1, 1, 4)]),
];
for (domains, bounds) in cases {
let n = domains.len();
let scope: Vec<usize> = (0..n).collect();
for order in permutations(n) {
let (problem, _) = full(&domains, &bounds);
let mdd = settled(problem, order.clone());
assert_eq!(
accepted(&mdd),
expected(&domains, &[(&scope, &bounds)]),
"domains {domains:?} bounds {bounds:?} order {order:?}"
);
}
}
}
#[test]
fn unreachable_bounds_are_unsat() {
let cases: Vec<Case> = vec![
(vec![vec![0], vec![0]], vec![(1, 1, 2)]),
(vec![vec![1], vec![1]], vec![(1, 0, 1)]),
(vec![dom(2); 3], vec![(0, 2, 3), (1, 2, 3)]),
(vec![dom(2); 2], vec![(1, 2, 1)]),
];
for (domains, bounds) in cases {
let (problem, _) = full(&domains, &bounds);
let mdd = settled(problem, (0..domains.len()).collect());
assert!(accepted(&mdd).is_empty(), "{domains:?} {bounds:?}");
}
}
#[test]
fn a_value_that_cannot_occur_may_still_be_capped_at_zero() {
let domains = [dom(2), dom(2)];
let (problem, _) = full(&domains, &[(9, 0, 0)]);
assert_eq!(accepted(&settled(problem, vec![0, 1])).len(), 4);
}
#[test]
fn no_bound_accepts_every_tuple() {
let domains = [dom(2), dom(3)];
let (problem, _) = full(&domains, &[]);
assert_eq!(accepted(&settled(problem, vec![0, 1])).len(), 6);
}
#[test]
fn a_single_bound_is_an_among_on_that_value() {
let cases: Vec<(Vec<Vec<isize>>, isize, usize, usize)> = vec![
(vec![dom(3); 3], 1, 1, 2),
(vec![dom(2); 4], 1, 2, 2),
(vec![dom(3); 3], 2, 0, 1),
(vec![dom(3); 3], 0, 2, 3),
];
for (domains, value, lo, hi) in cases {
let (problem, _) = full(&domains, &[(value, lo, hi)]);
let from_gcc = accepted(&settled(problem, (0..domains.len()).collect()));
let mut problem = Problem::default();
let vars: Vec<VariableIndex> = domains
.iter()
.map(|d| problem.add_variable(d.clone()))
.collect();
among(&mut problem, vars, vec![value], lo, hi);
let from_among = accepted(&settled(problem, (0..domains.len()).collect()));
assert_eq!(from_gcc, from_among, "value {value} in [{lo}, {hi}]");
}
}
#[test]
fn at_most_one_of_each_value_is_all_different() {
let domains = [dom(4), dom(4), dom(4)];
let bounds: Vec<(isize, usize, usize)> = (0..4).map(|v| (v, 0, 1)).collect();
let (problem, _) = full(&domains, &bounds);
let from_gcc = accepted(&settled(problem, vec![0, 1, 2]));
let mut problem = Problem::default();
let vars: Vec<VariableIndex> = domains
.iter()
.map(|d| problem.add_variable(d.clone()))
.collect();
all_different(&mut problem, vars);
let from_all_different = accepted(&settled(problem, vec![0, 1, 2]));
assert_eq!(from_gcc.len(), 24);
assert_eq!(from_gcc, from_all_different);
}
fn two_scopes(domains: &[Vec<isize>], first: Spec, second: Spec) -> Problem {
let (mut problem, vars) = scoped(domains, first.0, first.1);
gcc(
&mut problem,
second.0.iter().map(|&i| vars[i]).collect(),
second.1.to_vec(),
);
problem
}
#[test]
fn a_constraint_ignores_the_layers_of_the_other_one() {
let domains = [dom(3), dom(3), dom(3), dom(3)];
let first: Spec = (&[0, 2], &[(1, 1, 1)]);
let second: Spec = (&[1, 3], &[(2, 1, 2), (0, 0, 1)]);
for order in [vec![0, 1, 2, 3], vec![3, 1, 2, 0], vec![1, 3, 0, 2]] {
let problem = two_scopes(&domains, first, second);
let mdd = settled(problem, order.clone());
assert_eq!(
accepted(&mdd),
expected(&domains, &[first, second]),
"order {order:?}"
);
}
}
#[test]
fn overlapping_scopes_are_exact() {
let domains = [dom(3), dom(3), dom(3)];
let first: Spec = (&[0, 1], &[(1, 1, 1), (2, 0, 1)]);
let second: Spec = (&[1, 2], &[(0, 1, 2)]);
let problem = two_scopes(&domains, first, second);
let mdd = settled(problem, vec![0, 1, 2]);
let want = expected(&domains, &[first, second]);
assert_eq!(accepted(&mdd), want);
assert!(!want.is_empty());
}
#[test]
fn combined_with_not_equals_is_exact() {
let domains = [dom(3), dom(3), dom(3)];
let bounds = [(2, 1, 1)];
let (mut problem, vars) = full(&domains, &bounds);
not_equals(&mut problem, vars[0], vars[1]);
let mdd = settled(problem, vec![0, 1, 2]);
let want: Vec<Vec<isize>> = expected(&domains, &[(&[0, 1, 2], &bounds)])
.into_iter()
.filter(|t| t[0] != t[1])
.collect();
assert_eq!(accepted(&mdd), want);
assert!(!want.is_empty());
}
#[test]
fn a_shift_cover_like_the_one_of_the_nurse_models_is_exact() {
let domains = vec![dom(4); 5];
let bounds = [(1, 1, 2), (2, 0, 2), (3, 1, 3)];
let (problem, _) = full(&domains, &bounds);
let mdd = settled(problem, (0..5).collect());
let scope: Vec<usize> = (0..5).collect();
assert_eq!(accepted(&mdd), expected(&domains, &[(&scope, &bounds)]));
}
#[test]
fn a_saturated_value_needs_at_most_lo_plus_one_nodes_per_layer() {
let domains = vec![dom(2); 6];
let (problem, _) = full(&domains, &[(1, 2, 6)]);
let mdd = settled(problem, (0..6).collect());
let sizes: Vec<usize> = (0..=6).map(|l| mdd.number_nodes_in_layer(l)).collect();
assert_eq!(sizes, vec![1, 2, 3, 3, 3, 2, 1]);
}
#[test]
fn a_value_whose_upper_bound_can_bind_keeps_every_count() {
let domains = vec![dom(2); 6];
let (problem, _) = full(&domains, &[(1, 0, 3)]);
let mdd = settled(problem, (0..6).collect());
let widest = (0..=6).map(|l| mdd.number_nodes_in_layer(l)).max().unwrap();
assert_eq!(widest, 4);
}
#[test]
fn a_saturated_lower_bound_compiles_smaller_than_the_same_among() {
let domains = vec![dom(2); 6];
let (problem, _) = full(&domains, &[(1, 2, 6)]);
let compact = settled(problem, (0..6).collect());
let mut problem = Problem::default();
let vars: Vec<VariableIndex> = domains
.iter()
.map(|d| problem.add_variable(d.clone()))
.collect();
among(&mut problem, vars, vec![1], 2, 7);
let verbose = settled(problem, (0..6).collect());
assert_eq!(accepted(&compact), accepted(&verbose));
let nodes = |mdd: &Mdd| -> usize { (0..=6).map(|l| mdd.number_nodes_in_layer(l)).sum() };
assert!(nodes(&compact) < nodes(&verbose));
}
struct Lcg(u64);
impl Lcg {
fn below(&mut self, bound: u64) -> u64 {
self.0 = self
.0
.wrapping_mul(6364136223846793005)
.wrapping_add(1442695040888963407);
(self.0 >> 33) % bound
}
}
fn random_instance(rng: &mut Lcg) -> Case {
let n = 2 + rng.below(4) as usize;
let domains: Vec<Vec<isize>> = (0..n)
.map(|_| {
let mut d: Vec<isize> = (0..4).filter(|_| rng.below(2) == 1).collect();
if d.is_empty() {
d.push(rng.below(4) as isize);
}
d
})
.collect();
let mut bounds = vec![];
for value in 0..4isize {
if rng.below(2) == 1 {
let lo = rng.below(n as u64 + 1) as usize;
let hi = lo + rng.below((n + 2 - lo) as u64) as usize;
bounds.push((value, lo, hi));
}
}
for i in (1..bounds.len()).rev() {
bounds.swap(i, rng.below(i as u64 + 1) as usize);
}
(domains, bounds)
}
#[test]
fn random_instances_are_exact_once_settled() {
let mut rng = Lcg(2024);
for _ in 0..200 {
let (domains, bounds) = random_instance(&mut rng);
let n = domains.len();
let mut order: Vec<usize> = (0..n).collect();
for i in (1..n).rev() {
order.swap(i, rng.below(i as u64 + 1) as usize);
}
let scope: Vec<usize> = (0..n).collect();
let (problem, _) = full(&domains, &bounds);
let mdd = settled(problem, order.clone());
assert_eq!(
accepted(&mdd),
expected(&domains, &[(&scope, &bounds)]),
"domains {domains:?} bounds {bounds:?} order {order:?}"
);
}
}
#[test]
fn the_initial_relaxation_never_loses_a_solution() {
let mut rng = Lcg(77);
for _ in 0..200 {
let (domains, bounds) = random_instance(&mut rng);
let n = domains.len();
let scope: Vec<usize> = (0..n).collect();
let want = expected(&domains, &[(&scope, &bounds)]);
let (problem, _) = full(&domains, &bounds);
let got = accepted(&compile(problem, (0..n).collect(), 1));
for solution in &want {
assert!(
got.contains(solution),
"lost {solution:?}: domains {domains:?} bounds {bounds:?}"
);
}
}
}
#[test]
fn relaxed_mdds_never_lose_a_solution() {
let mut rng = Lcg(77);
for _ in 0..200 {
let (domains, bounds) = random_instance(&mut rng);
let n = domains.len();
let mut order: Vec<usize> = (0..n).collect();
for i in (1..n).rev() {
order.swap(i, rng.below(i as u64 + 1) as usize);
}
let scope: Vec<usize> = (0..n).collect();
let want = expected(&domains, &[(&scope, &bounds)]);
for width in [1usize, 2, 3, usize::MAX] {
let (problem, _) = full(&domains, &bounds);
let mdd = compile(problem, order.clone(), width);
let got = accepted(&mdd);
for solution in &want {
assert!(
got.contains(solution),
"lost {solution:?}: domains {domains:?} bounds {bounds:?} order {order:?} width {width}"
);
}
}
}
}
#[test]
fn a_domain_that_shrinks_after_construction_is_fine() {
let (mut problem, vars) = full(&[dom(3), dom(3)], &[(1, 1, 1)]);
problem[vars[0]].set_domain(vec![1]);
let mdd = settled(problem, vec![0, 1]);
assert_eq!(accepted(&mdd), vec![vec![1, 0], vec![1, 2]]);
}
#[test]
fn a_domain_that_grows_after_construction_is_fine() {
let (mut problem, vars) = full(&[dom(2), dom(2)], &[(9, 1, 1)]);
problem[vars[0]].set_domain(vec![0, 9]);
let mdd = settled(problem, vec![0, 1]);
assert_eq!(accepted(&mdd), vec![vec![9, 0], vec![9, 1]]);
}
#[test]
fn a_property_is_a_single_state_when_every_path_has_the_same_counts() {
let constraint = gcc_of(3, &[(1, 0, 2), (2, 0, 2)]);
assert!(constraint.empty_property().is_single_state());
assert!(path_property(&constraint, &[1, 2]).is_single_state());
let mut same_counts = path_property(&constraint, &[1, 2]);
same_counts.merge(&*path_property(&constraint, &[2, 1]));
assert!(same_counts.is_single_state());
assert!(!interval(&constraint, 1, 0, 2).is_single_state());
let mut other_counts = path_property(&constraint, &[1, 2]);
other_counts.merge(&*path_property(&constraint, &[1, 1]));
assert!(!other_counts.is_single_state());
assert!(!constraint.identity_property().is_single_state());
}
}