bundles/org.simantics.scl.compiler/src/org/simantics/scl/compiler/elaboration/query/compilation/DynamicProgrammingOrdering.java

   1 package org.simantics.scl.compiler.elaboration.query.compilation;
   2
   3 import gnu.trove.map.hash.TLongObjectHashMap;
   4 import gnu.trove.procedure.TLongObjectProcedure;
   5
   6 import java.util.ArrayList;
   7 import java.util.Collections;
   8
   9 public class DynamicProgrammingOrdering {
  10     final ConstraintCollectionContext collectionContext;
  11     int variableCount;
  12     final QueryConstraint[] constraints;
  13     TLongObjectHashMap<Entry> entries = new TLongObjectHashMap<Entry>();
  14
  15     private static class Path {
  16         public final QueryConstraint constraint;
  17         public final Path prev;
  18
  19         public Path(QueryConstraint constraint, Path prev) {
  20             this.constraint = constraint;
  21             this.prev = prev;
  22         }
  23
  24         public void updateOrder(QueryConstraint[] constraints) {
  25             Path path = this;
  26             for(int i=constraints.length-1;i>=0;--i,path=path.prev)
  27                 constraints[i] = path.constraint;
  28         }
  29     }
  30
  31     private static class Entry {
  32         double branching;
  33         double cost;
  34         Path path;
  35         long variables;
  36
  37         public Entry(double branching, double cost, Path path, long variables) {
  38             this.branching = branching;
  39             this.cost = cost;
  40             this.path = path;
  41             this.variables = variables;
  42         }
  43     }
  44
  45     private DynamicProgrammingOrdering(ConstraintCollectionContext collectionContext,
  46             QueryConstraint[] constraints) {
  47         this.collectionContext = collectionContext;
  48         this.constraints = constraints;
  49
  50         //for(QueryConstraint constraint : constraints)
  51         //    System.out.println(constraint);
  52
  53         int maxVariable = -1;
  54         for(QueryConstraint constraint : constraints)
  55             for(int v : constraint.variables)
  56                 maxVariable = Math.max(maxVariable, v);
  57         this.variableCount = maxVariable + 1;
  58     }
  59
  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)
  63             nextEntries();
  64
  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);
  71     }
  72
  73     private void updateFinalBoundVariables(long boundVariables) {
  74         for(QueryConstraint constraint : constraints) {
  75             constraint.finalBoundVariables = boundVariables;
  76             boundVariables |= constraint.getVariableMask();
  77         }
  78     }
  79
  80     private void nextEntries() throws UnsolvableQueryException {
  81         TLongObjectHashMap<Entry> oldEntries = entries;
  82         entries = new TLongObjectHashMap<Entry>();
  83         oldEntries.forEachEntry(new TLongObjectProcedure<Entry>() {
  84             @Override
  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;
  90                 {
  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) {
  99                                 bestConstraint = i;
 100                                 bestBranching = newBranching;
 101                             }
 102                         }
 103                     }
 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;
 109
 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()));
 115                         }
 116                         else {
 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);
 122                             }
 123                         }
 124                         return true;
 125                     }
 126                 }
 127
 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;
 135
 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()));
 141                             }
 142                             else {
 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);
 148                                 }
 149                             }
 150                         }
 151                     }
 152                 }
 153                 return true;
 154             }
 155         });
 156         if(entries.isEmpty()) {
 157             Entry entry = oldEntries.valueCollection().iterator().next();
 158             long variables = entry.variables;
 159
 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);
 165
 166             StringBuilder b = new StringBuilder();
 167             b.append("Unsolved variables: ");
 168             for(int i=0;i<variableNames.size();++i) {
 169                 if(i > 0)
 170                     b.append(", ");
 171                 b.append(variableNames.get(i));
 172             }
 173
 174             /*b.append("\nUnsolved constraints:");
 175             for(QueryConstraint constraint : constraints)
 176                 if(!constraint.canBeSolvedFrom(entry.variables))
 177                     b.append("\n    ").append(constraint);
 178             */
 179             throw new UnsolvableQueryException(b.toString());
 180         }
 181     }
 182
 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);
 187     }
 188 }