Several speed optimizations

git-svn-id: svn://sunsvr01.isp.uni-luebeck.de/swproj13/trunk@438 72836036-5685-4462-b002-a69064685172

1 files changed, 39 insertions, 22 deletions

diff --git a/src/jrummikub/ai/fdsolver/Solver.java b/src/jrummikub/ai/fdsolver/Solver.java
index 2277ba4..0bdb344 100644
--- a/src/jrummikub/ai/fdsolver/Solver.java
+++ b/src/jrummikub/ai/fdsolver/Solver.java
@@ -7,6 +7,7 @@ import java.util.Collections;
 import java.util.HashMap;
 import java.util.HashSet;
 import java.util.Iterator;
+import java.util.List;
 import java.util.Map;
 import java.util.Set;
 import static jrummikub.ai.fdsolver.Satisfiability.*;
@@ -24,6 +25,8 @@ public class Solver {
 
 	Set<Constraint> constraints = new HashSet<Constraint>();
 
+	Set<Constraint> dirtyConstraints = new HashSet<Constraint>();
+
 	ArrayList<StackFrame> stack = new ArrayList<StackFrame>();
 
 	boolean contradiction = false;
@@ -83,27 +86,19 @@ public class Solver {
 		}
 	}
 
-	public void propagateOnce() {
-		Var<?> dirtyVar = Collections.min(dirtyVars);
-		dirtyVars.remove(dirtyVar);
-		outerLoop: for (Iterator<Constraint> i = dirtyVar.getConstraints()
-				.iterator(); i.hasNext();) {
-			Constraint constraint = i.next();
-			Satisfiability sat = constraint.getSatisfiability();
-			if (sat == UNSAT) {
-				contradiction = true;
-				break;
-			}
-			if (sat == TAUT) {
-				i.remove();
-				finishedConstraint(constraint, dirtyVar);
-				continue;
-			}
-			for (Propagator propagator : constraint.cachedPropagators) {
-				if (propagator.getWatchedVars().contains(dirtyVar)) {
-					propagator.propagate();
-					if (contradiction) {
-						break outerLoop;
+	public void propagateEach() {
+		List<Var<?>> oldDirtyVars = new ArrayList<Var<?>>(dirtyVars);
+		dirtyVars.clear();
+		Collections.sort(oldDirtyVars);
+		outerLoop: for(Var<?> dirtyVar : oldDirtyVars) {
+			for (Constraint constraint : dirtyVar.getConstraints()) {
+				dirtyConstraints.add(constraint);
+				for (Propagator propagator : constraint.cachedPropagators) {
+					if (propagator.getWatchedVars().contains(dirtyVar)) {
+						propagator.propagate();
+						if (contradiction) {
+							break outerLoop;
+						}
 					}
 				}
 			}
@@ -111,9 +106,31 @@ public class Solver {
 	}
 
 	public void propagateAll() {
+		int i = 0;
 		while (!(dirtyVars.isEmpty() || contradiction)) {
-			propagateOnce();
+			i++;
+			if (i == 50) {
+				cleanUpConstraints();
+				i = 0;
+			} else {
+				propagateEach();
+			}
+		}
+		cleanUpConstraints();
+	}
+	
+	private void cleanUpConstraints() {
+		for (Constraint constraint : dirtyConstraints) {
+			Satisfiability sat = constraint.getSatisfiability();
+			if (sat == UNSAT) {
+				contradiction = true;
+				break;
+			}
+			if (sat == TAUT) {
+				finishedConstraint(constraint, null);
+			}
 		}
+		dirtyConstraints.clear();
 	}
 
 	public void addVar(Var<?> var) {