blob: 9d80a3720d1be08820c5775e103b209e31dda6f5 (
plain)
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
|
package jrummikub.ai.fdsolver.constraint;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import jrummikub.ai.fdsolver.Constraint;
import jrummikub.ai.fdsolver.Propagator;
import jrummikub.ai.fdsolver.Satisfiability;
import jrummikub.ai.fdsolver.Var;
public class IndexConstraint<T> extends Constraint {
Var<T> target;
Var<Integer> index;
List<Var<T>> list;
Collection<Var<?>> vars = new ArrayList<Var<?>>();
Collection<Var<?>> varsNoTarget = new ArrayList<Var<?>>();
Collection<Var<?>> varsNoIndex = new ArrayList<Var<?>>();
public IndexConstraint(Var<T> target, Var<Integer> index, List<Var<T>> list) {
this.target = target;
this.index = index;
this.list = list;
vars.addAll(list);
vars.add(index);
vars.add(target);
varsNoTarget.addAll(list);
varsNoTarget.add(index);
varsNoIndex.addAll(list);
varsNoIndex.add(target);
}
@Override
public Collection<Var<?>> getWatchedVars() {
return vars;
}
private class UnionProp implements Propagator {
@Override
public Collection<Var<?>> getWatchedVars() {
return varsNoTarget;
}
@Override
public void propagate() {
HashSet<T> union = new HashSet<T>();
for (int i : index.getRange()) {
union.addAll(list.get(i).getRange());
}
for (Iterator<T> i = target.iterator(); i.hasNext();) {
T val = i.next();
if (!union.contains(val)) {
i.remove();
}
}
};
}
private class IndexProp implements Propagator {
@Override
public Collection<Var<?>> getWatchedVars() {
return varsNoIndex;
}
@Override
public void propagate() {
for (Iterator<Integer> i = index.iterator(); i.hasNext();) {
int id = i.next();
HashSet<T> range = new HashSet<T>(target.getRange());
range.retainAll(list.get(id).getRange());
if (range.isEmpty()) {
i.remove();
}
}
}
}
private class VarProp implements Propagator {
@Override
public Collection<Var<?>> getWatchedVars() {
return Arrays.asList(target, index);
}
@Override
public void propagate() {
if (index.getRange().size() != 1)
return;
int id = index.getValue();
Var<T> var = list.get(id);
for(Iterator<T> i = var.iterator(); i.hasNext();) {
if (!target.getRange().contains(i.next())) {
i.remove();
}
}
}
}
@Override
public Collection<Propagator> getPropagators(boolean negate) {
if (negate) {
return Collections.emptyList();
}
return Arrays.<Propagator> asList(new UnionProp(), new IndexProp(), new VarProp());
}
@Override
public Satisfiability getSatisfiability() {
HashSet<T> union = new HashSet<T>();
for (int i : index.getRange()) {
union.addAll(list.get(i).getRange());
}
boolean isSat = false;
for (T val : target.getRange()) {
if (union.contains(val)) {
isSat = true;
break;
}
}
if (!isSat) {
return Satisfiability.UNSAT;
} else {
if (union.size() == 1 && target.getRange().size() == 1) {
return Satisfiability.TAUT;
} else {
return Satisfiability.SAT;
}
}
}
}
|
