summaryrefslogtreecommitdiffstats
path: root/src/jrummikub/ai/fdsolver/constraint
diff options
context:
space:
mode:
authorJannis Harder <harder@informatik.uni-luebeck.de>2011-06-13 22:19:31 +0200
committerJannis Harder <harder@informatik.uni-luebeck.de>2011-06-13 22:19:31 +0200
commit2b4ad89e72fdf9612854b27bc8dd818c8f062d35 (patch)
treecf323935dd3e58f43cdd4b2c19660055639948e0 /src/jrummikub/ai/fdsolver/constraint
parenta15626ac3b86d3153e32b7b160403c9ab66b1034 (diff)
downloadJRummikub-2b4ad89e72fdf9612854b27bc8dd818c8f062d35.tar
JRummikub-2b4ad89e72fdf9612854b27bc8dd818c8f062d35.zip
Restructured fdsolver api and made first test succeed
git-svn-id: svn://sunsvr01.isp.uni-luebeck.de/swproj13/trunk@423 72836036-5685-4462-b002-a69064685172
Diffstat (limited to 'src/jrummikub/ai/fdsolver/constraint')
-rw-r--r--src/jrummikub/ai/fdsolver/constraint/ComparatorConstraint.java67
-rw-r--r--src/jrummikub/ai/fdsolver/constraint/ComparatorPropagator.java42
-rw-r--r--src/jrummikub/ai/fdsolver/constraint/Filter.java5
-rw-r--r--src/jrummikub/ai/fdsolver/constraint/FilterConstraint.java65
-rw-r--r--src/jrummikub/ai/fdsolver/constraint/FilterPropagator.java31
-rw-r--r--src/jrummikub/ai/fdsolver/constraint/GreaterThan.java18
-rw-r--r--src/jrummikub/ai/fdsolver/constraint/GreaterThanConst.java15
-rw-r--r--src/jrummikub/ai/fdsolver/constraint/LessThan.java17
-rw-r--r--src/jrummikub/ai/fdsolver/constraint/LessThanConst.java18
9 files changed, 278 insertions, 0 deletions
diff --git a/src/jrummikub/ai/fdsolver/constraint/ComparatorConstraint.java b/src/jrummikub/ai/fdsolver/constraint/ComparatorConstraint.java
new file mode 100644
index 0000000..24e7ecf
--- /dev/null
+++ b/src/jrummikub/ai/fdsolver/constraint/ComparatorConstraint.java
@@ -0,0 +1,67 @@
+package jrummikub.ai.fdsolver.constraint;
+
+import static jrummikub.ai.fdsolver.Satisfiability.*;
+
+import java.util.Arrays;
+import java.util.Collection;
+import java.util.Collections;
+import java.util.Comparator;
+
+import jrummikub.ai.fdsolver.Constraint;
+import jrummikub.ai.fdsolver.Propagator;
+import jrummikub.ai.fdsolver.Satisfiability;
+import jrummikub.ai.fdsolver.Var;
+
+public class ComparatorConstraint<T> implements Constraint {
+ Var<T> x, y;
+ Comparator<T> comparator, reverseComparator;
+ ComparatorPropagator<T> trueX, trueY, falseX, falseY;
+ boolean allowEqual;
+
+ ComparatorConstraint(final Comparator<T> comparator, boolean allowEqual, Var<T> x, Var<T> y) {
+ this.x = x;
+ this.y = y;
+ this.comparator = comparator;
+ this.allowEqual = allowEqual;
+ reverseComparator = new Comparator<T>() {
+ @Override
+ public int compare(T o1, T o2) {
+ return comparator.compare(o2, o1);
+ }
+ };
+ trueX = new ComparatorPropagator<T>(comparator, allowEqual, x, y);
+ trueY = new ComparatorPropagator<T>(reverseComparator, allowEqual, y, x);
+ falseX = new ComparatorPropagator<T>(reverseComparator, !allowEqual, x, y);
+ falseY = new ComparatorPropagator<T>(comparator, !allowEqual, y, x);
+ }
+
+ @Override
+ public Collection<Var<?>> getWatchedVars() {
+ return Arrays.<Var<?>>asList(x,y);
+ }
+
+ @Override
+ public Collection<Propagator> getPropagators(boolean negate) {
+ if (negate) {
+ return Arrays.<Propagator>asList(falseX,falseY);
+ } else {
+ return Arrays.<Propagator>asList(trueX,trueY);
+ }
+ }
+
+ @Override
+ public Satisfiability getSatisfiability() {
+ T maxX = Collections.max(x.getRange(), comparator);
+ T minY = Collections.min(y.getRange(), comparator);
+ if (comparator.compare(maxX, minY) < (allowEqual ? 1 : 0)) {
+ return TAUT;
+ }
+ T minX = Collections.min(x.getRange(), comparator);
+ T maxY = Collections.max(y.getRange(), comparator);
+ if (comparator.compare(maxY, minX) < (allowEqual ? 0 : 1)) {
+ return UNSAT;
+ }
+ return SAT;
+ }
+
+}
diff --git a/src/jrummikub/ai/fdsolver/constraint/ComparatorPropagator.java b/src/jrummikub/ai/fdsolver/constraint/ComparatorPropagator.java
new file mode 100644
index 0000000..b3a3089
--- /dev/null
+++ b/src/jrummikub/ai/fdsolver/constraint/ComparatorPropagator.java
@@ -0,0 +1,42 @@
+package jrummikub.ai.fdsolver.constraint;
+
+import java.util.Arrays;
+import java.util.Collection;
+import java.util.Collections;
+import java.util.Comparator;
+import java.util.HashSet;
+import java.util.Iterator;
+import java.util.List;
+
+import jrummikub.ai.fdsolver.Propagator;
+import jrummikub.ai.fdsolver.Var;
+
+public class ComparatorPropagator<T> implements Propagator {
+ private Var<T> x, y;
+ private Comparator<T> comparator;
+ private boolean allowEqual;
+ public ComparatorPropagator(Comparator<T> comparator, boolean allowEqual, Var<T> x, Var<T> y) {
+ this.comparator = comparator;
+ this.allowEqual = allowEqual;
+ this.x = x;
+ this.y = y;
+ }
+
+ @Override
+ public Collection<Var<?>> getWatchedVars() {
+ return Arrays.<Var<?>>asList(y);
+ }
+
+ @Override
+ public void propagate() {
+ T maxY = Collections.max(y.getRange(), comparator);
+
+ for(Iterator<T> i = x.iterator(); i.hasNext();) {
+ T value = i.next();
+ int comparision = comparator.compare(value, maxY);
+ if (comparision > 0 || comparision == 0 && !allowEqual) {
+ i.remove();
+ }
+ }
+ }
+}
diff --git a/src/jrummikub/ai/fdsolver/constraint/Filter.java b/src/jrummikub/ai/fdsolver/constraint/Filter.java
new file mode 100644
index 0000000..59c880a
--- /dev/null
+++ b/src/jrummikub/ai/fdsolver/constraint/Filter.java
@@ -0,0 +1,5 @@
+package jrummikub.ai.fdsolver.constraint;
+
+public interface Filter<T> {
+ public boolean accept(T value);
+}
diff --git a/src/jrummikub/ai/fdsolver/constraint/FilterConstraint.java b/src/jrummikub/ai/fdsolver/constraint/FilterConstraint.java
new file mode 100644
index 0000000..e676882
--- /dev/null
+++ b/src/jrummikub/ai/fdsolver/constraint/FilterConstraint.java
@@ -0,0 +1,65 @@
+package jrummikub.ai.fdsolver.constraint;
+
+import static jrummikub.ai.fdsolver.Satisfiability.SAT;
+import static jrummikub.ai.fdsolver.Satisfiability.TAUT;
+import static jrummikub.ai.fdsolver.Satisfiability.UNSAT;
+
+import java.util.Arrays;
+import java.util.Collection;
+
+import jrummikub.ai.fdsolver.Constraint;
+import jrummikub.ai.fdsolver.Propagator;
+import jrummikub.ai.fdsolver.Satisfiability;
+import jrummikub.ai.fdsolver.Var;
+
+public class FilterConstraint<T> implements Constraint {
+ private Var<T> var;
+ private Propagator trueProp, falseProp;
+ private Filter<T> filter;
+
+ public FilterConstraint(final Filter<T> filter, Var<T> var) {
+ this.var = var;
+ this.filter = filter;
+ trueProp = new FilterPropagator<T>(filter, var);
+ falseProp = new FilterPropagator<T>(new Filter<T>() {
+ @Override
+ public boolean accept(T value) {
+ return !filter.accept(value);
+ }
+ }, var);
+ }
+
+ @Override
+ public Collection<Var<?>> getWatchedVars() {
+ return Arrays.<Var<?>> asList(var);
+ }
+
+ @Override
+ public Collection<Propagator> getPropagators(boolean negate) {
+ return Arrays.asList(negate ? falseProp : trueProp);
+ }
+
+ @Override
+ public Satisfiability getSatisfiability() {
+ boolean any = false;
+ boolean all = true;
+
+ for (T value : var.getRange()) {
+ boolean accepted = filter.accept(value);
+ if (accepted) {
+ any = true;
+ } else {
+ all = false;
+ }
+ }
+
+ if (all && any) {
+ return TAUT;
+ } else if (any) {
+ return SAT;
+ } else {
+ return UNSAT;
+ }
+ }
+
+}
diff --git a/src/jrummikub/ai/fdsolver/constraint/FilterPropagator.java b/src/jrummikub/ai/fdsolver/constraint/FilterPropagator.java
new file mode 100644
index 0000000..80518c9
--- /dev/null
+++ b/src/jrummikub/ai/fdsolver/constraint/FilterPropagator.java
@@ -0,0 +1,31 @@
+package jrummikub.ai.fdsolver.constraint;
+
+import java.util.Arrays;
+import java.util.Collection;
+import java.util.Iterator;
+
+import jrummikub.ai.fdsolver.Propagator;
+import jrummikub.ai.fdsolver.Var;
+
+public class FilterPropagator<T> implements Propagator {
+ private Filter<T> filter;
+ private Var<T> var;
+
+ public FilterPropagator(Filter<T> filter, Var<T> var) {
+ this.filter = filter;
+ this.var = var;
+ }
+
+ @Override
+ public Collection<Var<?>> getWatchedVars() {
+ return Arrays.<Var<?>>asList(var);
+ }
+
+ @Override
+ public void propagate() {
+ for(Iterator<T> i = var.iterator(); i.hasNext();) {
+ if(!filter.accept(i.next()))
+ i.remove();
+ }
+ }
+}
diff --git a/src/jrummikub/ai/fdsolver/constraint/GreaterThan.java b/src/jrummikub/ai/fdsolver/constraint/GreaterThan.java
new file mode 100644
index 0000000..9bdccd2
--- /dev/null
+++ b/src/jrummikub/ai/fdsolver/constraint/GreaterThan.java
@@ -0,0 +1,18 @@
+package jrummikub.ai.fdsolver.constraint;
+
+import java.util.Comparator;
+
+import jrummikub.ai.fdsolver.Var;
+
+public class GreaterThan<T extends Comparable<T>> extends
+ ComparatorConstraint<T> {
+
+ public GreaterThan(boolean allowEqual, Var<T> x, Var<T> y) {
+ super(new Comparator<T>() {
+ @Override
+ public int compare(T o1, T o2) {
+ return o2.compareTo(o1);
+ }
+ }, allowEqual, x, y);
+ }
+}
diff --git a/src/jrummikub/ai/fdsolver/constraint/GreaterThanConst.java b/src/jrummikub/ai/fdsolver/constraint/GreaterThanConst.java
new file mode 100644
index 0000000..6b00ee3
--- /dev/null
+++ b/src/jrummikub/ai/fdsolver/constraint/GreaterThanConst.java
@@ -0,0 +1,15 @@
+package jrummikub.ai.fdsolver.constraint;
+
+import jrummikub.ai.fdsolver.Var;
+
+public class GreaterThanConst<T extends Comparable<T>> extends
+ FilterConstraint<T> {
+ public GreaterThanConst(final boolean allowEqual, Var<T> x, final T y) {
+ super(new Filter<T>() {
+ @Override
+ public boolean accept(T value) {
+ return y.compareTo(value) < (allowEqual ? 1 : 0);
+ }
+ }, x);
+ }
+}
diff --git a/src/jrummikub/ai/fdsolver/constraint/LessThan.java b/src/jrummikub/ai/fdsolver/constraint/LessThan.java
new file mode 100644
index 0000000..b79252c
--- /dev/null
+++ b/src/jrummikub/ai/fdsolver/constraint/LessThan.java
@@ -0,0 +1,17 @@
+package jrummikub.ai.fdsolver.constraint;
+
+import java.util.Comparator;
+
+import jrummikub.ai.fdsolver.Var;
+
+public class LessThan<T extends Comparable<T>> extends ComparatorConstraint<T> {
+
+ public LessThan(boolean allowEqual, Var<T> x, Var<T> y) {
+ super(new Comparator<T>() {
+ @Override
+ public int compare(T o1, T o2) {
+ return o1.compareTo(o2);
+ }
+ }, allowEqual, x, y);
+ }
+}
diff --git a/src/jrummikub/ai/fdsolver/constraint/LessThanConst.java b/src/jrummikub/ai/fdsolver/constraint/LessThanConst.java
new file mode 100644
index 0000000..18d8827
--- /dev/null
+++ b/src/jrummikub/ai/fdsolver/constraint/LessThanConst.java
@@ -0,0 +1,18 @@
+package jrummikub.ai.fdsolver.constraint;
+
+import java.util.Collection;
+
+import jrummikub.ai.fdsolver.Propagator;
+import jrummikub.ai.fdsolver.Solver;
+import jrummikub.ai.fdsolver.Var;
+
+public class LessThanConst<T extends Comparable<T>> extends FilterConstraint<T> {
+ public LessThanConst(final boolean allowEqual, Var<T> x, final T y) {
+ super(new Filter<T>() {
+ @Override
+ public boolean accept(T value) {
+ return value.compareTo(y) < (allowEqual ? 1 : 0);
+ }
+ }, x);
+ }
+}