summaryrefslogtreecommitdiffstats
path: root/src/jrummikub/ai/fdsolver/constraint/IndexConstraint.java
diff options
context:
space:
mode:
authorJannis Harder <harder@informatik.uni-luebeck.de>2011-06-14 17:48:22 +0200
committerJannis Harder <harder@informatik.uni-luebeck.de>2011-06-14 17:48:22 +0200
commit7568f3782466531fe04fc14a40dc4d3a393c1fb9 (patch)
tree7778b598da5b698c35189234fe3a9dd58ae82913 /src/jrummikub/ai/fdsolver/constraint/IndexConstraint.java
parent79767f762e39eac3a0247b9ee75b24258790e0de (diff)
downloadJRummikub-7568f3782466531fe04fc14a40dc4d3a393c1fb9.tar
JRummikub-7568f3782466531fe04fc14a40dc4d3a393c1fb9.zip
Added TurnLogic with rule variables and constraints
git-svn-id: svn://sunsvr01.isp.uni-luebeck.de/swproj13/trunk@436 72836036-5685-4462-b002-a69064685172
Diffstat (limited to 'src/jrummikub/ai/fdsolver/constraint/IndexConstraint.java')
-rw-r--r--src/jrummikub/ai/fdsolver/constraint/IndexConstraint.java134
1 files changed, 134 insertions, 0 deletions
diff --git a/src/jrummikub/ai/fdsolver/constraint/IndexConstraint.java b/src/jrummikub/ai/fdsolver/constraint/IndexConstraint.java
new file mode 100644
index 0000000..999924f
--- /dev/null
+++ b/src/jrummikub/ai/fdsolver/constraint/IndexConstraint.java
@@ -0,0 +1,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> implements 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;
+ }
+ }
+ }
+}