--- /dev/null
+package org.simantics.scl.compiler.elaboration.query.compilation;
+
+import gnu.trove.map.hash.TLongObjectHashMap;
+import gnu.trove.procedure.TLongObjectProcedure;
+
+import java.util.ArrayList;
+import java.util.Collections;
+
+public class DynamicProgrammingOrdering {
+ final ConstraintCollectionContext collectionContext;
+ int variableCount;
+ final QueryConstraint[] constraints;
+ TLongObjectHashMap<Entry> entries = new TLongObjectHashMap<Entry>();
+
+ private static class Path {
+ public final QueryConstraint constraint;
+ public final Path prev;
+
+ public Path(QueryConstraint constraint, Path prev) {
+ this.constraint = constraint;
+ this.prev = prev;
+ }
+
+ public void updateOrder(QueryConstraint[] constraints) {
+ Path path = this;
+ for(int i=constraints.length-1;i>=0;--i,path=path.prev)
+ constraints[i] = path.constraint;
+ }
+ }
+
+ private static class Entry {
+ double branching;
+ double cost;
+ Path path;
+ long variables;
+
+ public Entry(double branching, double cost, Path path, long variables) {
+ this.branching = branching;
+ this.cost = cost;
+ this.path = path;
+ this.variables = variables;
+ }
+ }
+
+ private DynamicProgrammingOrdering(ConstraintCollectionContext collectionContext,
+ QueryConstraint[] constraints) {
+ this.collectionContext = collectionContext;
+ this.constraints = constraints;
+
+ //for(QueryConstraint constraint : constraints)
+ // System.out.println(constraint);
+
+ int maxVariable = -1;
+ for(QueryConstraint constraint : constraints)
+ for(int v : constraint.variables)
+ maxVariable = Math.max(maxVariable, v);
+ this.variableCount = maxVariable + 1;
+ }
+
+ private void run(long initialVariableBindings) throws UnsolvableQueryException {
+ entries.put(0L, new Entry(1.0, 0.0, null, initialVariableBindings));
+ for(int i=0;i<constraints.length;++i)
+ nextEntries();
+
+ Entry entry = entries.valueCollection().iterator().next();
+ if(entry.path != null)
+ entry.path.updateOrder(constraints);
+ updateFinalBoundVariables(initialVariableBindings);
+ //System.out.println("cost = " + entry.cost);
+ //System.out.println("branching = " + entry.branching);
+ }
+
+ private void updateFinalBoundVariables(long boundVariables) {
+ for(QueryConstraint constraint : constraints) {
+ constraint.finalBoundVariables = boundVariables;
+ boundVariables |= constraint.getVariableMask();
+ }
+ }
+
+ private void nextEntries() throws UnsolvableQueryException {
+ TLongObjectHashMap<Entry> oldEntries = entries;
+ entries = new TLongObjectHashMap<Entry>();
+ oldEntries.forEachEntry(new TLongObjectProcedure<Entry>() {
+ @Override
+ public boolean execute(long constraintPattern, Entry entry) {
+ double branching = entry.branching;
+ double cost = entry.cost;
+ Path path = entry.path;
+ long variables = entry.variables;
+ {
+ // Try to find a nonbranching constraint
+ double bestBranching = Double.POSITIVE_INFINITY;
+ int bestConstraint = -1;
+ for(int i=0;i<constraints.length;++i) {
+ if( ((constraintPattern>>i)&1) == 0 ) {
+ QueryConstraint constraint = constraints[i];
+ double newBranching = constraint.getSolutionBranching(variables);
+ if(newBranching < bestBranching) {
+ bestConstraint = i;
+ bestBranching = newBranching;
+ }
+ }
+ }
+ if(bestBranching <= 1.0) {
+ QueryConstraint constraint = constraints[bestConstraint];
+ long newConstraintPattern = constraintPattern | (1L << bestConstraint);
+ double newBranching = constraint.getSolutionBranching(variables)*branching;
+ double newCost = constraint.getSolutionCost(variables)*branching + cost;
+
+ Entry newEntry = entries.get(newConstraintPattern);
+ if(newEntry == null) {
+ entries.put(newConstraintPattern,
+ new Entry(newBranching, newCost, new Path(constraint, path),
+ variables | constraint.getVariableMask()));
+ }
+ else {
+ if(newBranching < newEntry.branching)
+ newEntry.branching = newBranching;
+ if(newCost < newEntry.cost) {
+ newEntry.cost = newCost;
+ newEntry.path = new Path(constraint, path);
+ }
+ }
+ return true;
+ }
+ }
+
+ for(int i=0;i<constraints.length;++i) {
+ if( ((constraintPattern>>i)&1) == 0 ) {
+ QueryConstraint constraint = constraints[i];
+ if(constraint.canBeSolvedFrom(variables)) {
+ long newConstraintPattern = constraintPattern | (1L << i);
+ double newBranching = constraint.getSolutionBranching(variables)*branching;
+ double newCost = constraint.getSolutionCost(variables)*branching + cost;
+
+ Entry newEntry = entries.get(newConstraintPattern);
+ if(newEntry == null) {
+ entries.put(newConstraintPattern,
+ new Entry(newBranching, newCost, new Path(constraint, path),
+ variables | constraint.getVariableMask()));
+ }
+ else {
+ if(newBranching < newEntry.branching)
+ newEntry.branching = newBranching;
+ if(newCost < newEntry.cost) {
+ newEntry.cost = newCost;
+ newEntry.path = new Path(constraint, path);
+ }
+ }
+ }
+ }
+ }
+ return true;
+ }
+ });
+ if(entries.isEmpty()) {
+ Entry entry = oldEntries.valueCollection().iterator().next();
+ long variables = entry.variables;
+
+ ArrayList<String> variableNames = new ArrayList<String>();
+ for(int i=0;i<variableCount;++i)
+ if( ((variables >> i)&1) == 0 )
+ variableNames.add(collectionContext.variables.get(i).getName());
+ Collections.sort(variableNames);
+
+ StringBuilder b = new StringBuilder();
+ b.append("Unsolved variables: ");
+ for(int i=0;i<variableNames.size();++i) {
+ if(i > 0)
+ b.append(", ");
+ b.append(variableNames.get(i));
+ }
+
+ /*b.append("\nUnsolved constraints:");
+ for(QueryConstraint constraint : constraints)
+ if(!constraint.canBeSolvedFrom(entry.variables))
+ b.append("\n ").append(constraint);
+ */
+ throw new UnsolvableQueryException(b.toString());
+ }
+ }
+
+ public static void order(ConstraintCollectionContext collectionContext,
+ QueryConstraint[] constraints, long initialVariableBindings) throws UnsolvableQueryException {
+ DynamicProgrammingOrdering algorithm = new DynamicProgrammingOrdering(collectionContext, constraints);
+ algorithm.run(initialVariableBindings);
+ }
+}
Code Review / simantics / platform.git / blobdiff