1 package org.simantics.scl.compiler.elaboration.query.compilation;
3 import gnu.trove.map.hash.TLongObjectHashMap;
4 import gnu.trove.procedure.TLongObjectProcedure;
6 import java.util.ArrayList;
7 import java.util.Collections;
9 public class DynamicProgrammingOrdering {
10 final ConstraintCollectionContext collectionContext;
12 final QueryConstraint[] constraints;
13 TLongObjectHashMap<Entry> entries = new TLongObjectHashMap<Entry>();
15 private static class Path {
16 public final QueryConstraint constraint;
17 public final Path prev;
19 public Path(QueryConstraint constraint, Path prev) {
20 this.constraint = constraint;
24 public void updateOrder(QueryConstraint[] constraints) {
26 for(int i=constraints.length-1;i>=0;--i,path=path.prev)
27 constraints[i] = path.constraint;
31 private static class Entry {
37 public Entry(double branching, double cost, Path path, long variables) {
38 this.branching = branching;
41 this.variables = variables;
45 private DynamicProgrammingOrdering(ConstraintCollectionContext collectionContext,
46 QueryConstraint[] constraints) {
47 this.collectionContext = collectionContext;
48 this.constraints = constraints;
50 //for(QueryConstraint constraint : constraints)
51 // System.out.println(constraint);
54 for(QueryConstraint constraint : constraints)
55 for(int v : constraint.variables)
56 maxVariable = Math.max(maxVariable, v);
57 this.variableCount = maxVariable + 1;
60 private void run(long initialVariableBindings) throws UnsolvableQueryException {
61 entries.put(0L, new Entry(1.0, 0.0, null, initialVariableBindings));
62 for(int i=0;i<constraints.length;++i)
65 Entry entry = entries.valueCollection().iterator().next();
66 if(entry.path != null)
67 entry.path.updateOrder(constraints);
68 updateFinalBoundVariables(initialVariableBindings);
69 //System.out.println("cost = " + entry.cost);
70 //System.out.println("branching = " + entry.branching);
73 private void updateFinalBoundVariables(long boundVariables) {
74 for(QueryConstraint constraint : constraints) {
75 constraint.finalBoundVariables = boundVariables;
76 boundVariables |= constraint.getVariableMask();
80 private void nextEntries() throws UnsolvableQueryException {
81 TLongObjectHashMap<Entry> oldEntries = entries;
82 entries = new TLongObjectHashMap<Entry>();
83 oldEntries.forEachEntry(new TLongObjectProcedure<Entry>() {
85 public boolean execute(long constraintPattern, Entry entry) {
86 double branching = entry.branching;
87 double cost = entry.cost;
88 Path path = entry.path;
89 long variables = entry.variables;
91 // Try to find a nonbranching constraint
92 double bestBranching = Double.POSITIVE_INFINITY;
93 int bestConstraint = -1;
94 for(int i=0;i<constraints.length;++i) {
95 if( ((constraintPattern>>i)&1) == 0 ) {
96 QueryConstraint constraint = constraints[i];
97 double newBranching = constraint.getSolutionBranching(variables);
98 if(newBranching < bestBranching) {
100 bestBranching = newBranching;
104 if(bestBranching <= 1.0) {
105 QueryConstraint constraint = constraints[bestConstraint];
106 long newConstraintPattern = constraintPattern | (1L << bestConstraint);
107 double newBranching = constraint.getSolutionBranching(variables)*branching;
108 double newCost = constraint.getSolutionCost(variables)*branching + cost;
110 Entry newEntry = entries.get(newConstraintPattern);
111 if(newEntry == null) {
112 entries.put(newConstraintPattern,
113 new Entry(newBranching, newCost, new Path(constraint, path),
114 variables | constraint.getVariableMask()));
117 if(newBranching < newEntry.branching)
118 newEntry.branching = newBranching;
119 if(newCost < newEntry.cost) {
120 newEntry.cost = newCost;
121 newEntry.path = new Path(constraint, path);
128 for(int i=0;i<constraints.length;++i) {
129 if( ((constraintPattern>>i)&1) == 0 ) {
130 QueryConstraint constraint = constraints[i];
131 if(constraint.canBeSolvedFrom(variables)) {
132 long newConstraintPattern = constraintPattern | (1L << i);
133 double newBranching = constraint.getSolutionBranching(variables)*branching;
134 double newCost = constraint.getSolutionCost(variables)*branching + cost;
136 Entry newEntry = entries.get(newConstraintPattern);
137 if(newEntry == null) {
138 entries.put(newConstraintPattern,
139 new Entry(newBranching, newCost, new Path(constraint, path),
140 variables | constraint.getVariableMask()));
143 if(newBranching < newEntry.branching)
144 newEntry.branching = newBranching;
145 if(newCost < newEntry.cost) {
146 newEntry.cost = newCost;
147 newEntry.path = new Path(constraint, path);
156 if(entries.isEmpty()) {
157 Entry entry = oldEntries.valueCollection().iterator().next();
158 long variables = entry.variables;
160 ArrayList<String> variableNames = new ArrayList<String>();
161 for(int i=0;i<variableCount;++i)
162 if( ((variables >> i)&1) == 0 )
163 variableNames.add(collectionContext.variables.get(i).getName());
164 Collections.sort(variableNames);
166 StringBuilder b = new StringBuilder();
167 b.append("Unsolved variables: ");
168 for(int i=0;i<variableNames.size();++i) {
171 b.append(variableNames.get(i));
174 /*b.append("\nUnsolved constraints:");
175 for(QueryConstraint constraint : constraints)
176 if(!constraint.canBeSolvedFrom(entry.variables))
177 b.append("\n ").append(constraint);
179 throw new UnsolvableQueryException(b.toString());
183 public static void order(ConstraintCollectionContext collectionContext,
184 QueryConstraint[] constraints, long initialVariableBindings) throws UnsolvableQueryException {
185 DynamicProgrammingOrdering algorithm = new DynamicProgrammingOrdering(collectionContext, constraints);
186 algorithm.run(initialVariableBindings);