From 2b4ad89e72fdf9612854b27bc8dd818c8f062d35 Mon Sep 17 00:00:00 2001 From: Jannis Harder Date: Mon, 13 Jun 2011 22:19:31 +0200 Subject: 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 --- .../fdsolver/constraint/ComparatorConstraint.java | 67 ++++++++++++++++++++++ .../fdsolver/constraint/ComparatorPropagator.java | 42 ++++++++++++++ src/jrummikub/ai/fdsolver/constraint/Filter.java | 5 ++ .../ai/fdsolver/constraint/FilterConstraint.java | 65 +++++++++++++++++++++ .../ai/fdsolver/constraint/FilterPropagator.java | 31 ++++++++++ .../ai/fdsolver/constraint/GreaterThan.java | 18 ++++++ .../ai/fdsolver/constraint/GreaterThanConst.java | 15 +++++ src/jrummikub/ai/fdsolver/constraint/LessThan.java | 17 ++++++ .../ai/fdsolver/constraint/LessThanConst.java | 18 ++++++ 9 files changed, 278 insertions(+) create mode 100644 src/jrummikub/ai/fdsolver/constraint/ComparatorConstraint.java create mode 100644 src/jrummikub/ai/fdsolver/constraint/ComparatorPropagator.java create mode 100644 src/jrummikub/ai/fdsolver/constraint/Filter.java create mode 100644 src/jrummikub/ai/fdsolver/constraint/FilterConstraint.java create mode 100644 src/jrummikub/ai/fdsolver/constraint/FilterPropagator.java create mode 100644 src/jrummikub/ai/fdsolver/constraint/GreaterThan.java create mode 100644 src/jrummikub/ai/fdsolver/constraint/GreaterThanConst.java create mode 100644 src/jrummikub/ai/fdsolver/constraint/LessThan.java create mode 100644 src/jrummikub/ai/fdsolver/constraint/LessThanConst.java (limited to 'src/jrummikub/ai/fdsolver/constraint') 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 implements Constraint { + Var x, y; + Comparator comparator, reverseComparator; + ComparatorPropagator trueX, trueY, falseX, falseY; + boolean allowEqual; + + ComparatorConstraint(final Comparator comparator, boolean allowEqual, Var x, Var y) { + this.x = x; + this.y = y; + this.comparator = comparator; + this.allowEqual = allowEqual; + reverseComparator = new Comparator() { + @Override + public int compare(T o1, T o2) { + return comparator.compare(o2, o1); + } + }; + trueX = new ComparatorPropagator(comparator, allowEqual, x, y); + trueY = new ComparatorPropagator(reverseComparator, allowEqual, y, x); + falseX = new ComparatorPropagator(reverseComparator, !allowEqual, x, y); + falseY = new ComparatorPropagator(comparator, !allowEqual, y, x); + } + + @Override + public Collection> getWatchedVars() { + return Arrays.>asList(x,y); + } + + @Override + public Collection getPropagators(boolean negate) { + if (negate) { + return Arrays.asList(falseX,falseY); + } else { + return Arrays.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 implements Propagator { + private Var x, y; + private Comparator comparator; + private boolean allowEqual; + public ComparatorPropagator(Comparator comparator, boolean allowEqual, Var x, Var y) { + this.comparator = comparator; + this.allowEqual = allowEqual; + this.x = x; + this.y = y; + } + + @Override + public Collection> getWatchedVars() { + return Arrays.>asList(y); + } + + @Override + public void propagate() { + T maxY = Collections.max(y.getRange(), comparator); + + for(Iterator 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 { + 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 implements Constraint { + private Var var; + private Propagator trueProp, falseProp; + private Filter filter; + + public FilterConstraint(final Filter filter, Var var) { + this.var = var; + this.filter = filter; + trueProp = new FilterPropagator(filter, var); + falseProp = new FilterPropagator(new Filter() { + @Override + public boolean accept(T value) { + return !filter.accept(value); + } + }, var); + } + + @Override + public Collection> getWatchedVars() { + return Arrays.> asList(var); + } + + @Override + public Collection 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 implements Propagator { + private Filter filter; + private Var var; + + public FilterPropagator(Filter filter, Var var) { + this.filter = filter; + this.var = var; + } + + @Override + public Collection> getWatchedVars() { + return Arrays.>asList(var); + } + + @Override + public void propagate() { + for(Iterator 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> extends + ComparatorConstraint { + + public GreaterThan(boolean allowEqual, Var x, Var y) { + super(new Comparator() { + @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> extends + FilterConstraint { + public GreaterThanConst(final boolean allowEqual, Var x, final T y) { + super(new Filter() { + @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> extends ComparatorConstraint { + + public LessThan(boolean allowEqual, Var x, Var y) { + super(new Comparator() { + @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> extends FilterConstraint { + public LessThanConst(final boolean allowEqual, Var x, final T y) { + super(new Filter() { + @Override + public boolean accept(T value) { + return value.compareTo(y) < (allowEqual ? 1 : 0); + } + }, x); + } +} -- cgit v1.2.3