0001: /*
0002: * @(#)DeltaBlue.java 1.6 06/10/10
0003: *
0004: * Copyright 1990-2006 Sun Microsystems, Inc. All Rights Reserved.
0005: * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER
0006: *
0007: * This program is free software; you can redistribute it and/or
0008: * modify it under the terms of the GNU General Public License version
0009: * 2 only, as published by the Free Software Foundation.
0010: *
0011: * This program is distributed in the hope that it will be useful, but
0012: * WITHOUT ANY WARRANTY; without even the implied warranty of
0013: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
0014: * General Public License version 2 for more details (a copy is
0015: * included at /legal/license.txt).
0016: *
0017: * You should have received a copy of the GNU General Public License
0018: * version 2 along with this work; if not, write to the Free Software
0019: * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA
0020: * 02110-1301 USA
0021: *
0022: * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa
0023: * Clara, CA 95054 or visit www.sun.com if you need additional
0024: * information or have any questions.
0025: *
0026: */
0027: /*
0028:
0029: This is a Java implemention of the DeltaBlue algorithm described in:
0030: "The DeltaBlue Algorithm: An Incremental Constraint Hierarchy Solver"
0031: by Bjorn N. Freeman-Benson and John Maloney
0032: January 1990 Communications of the ACM,
0033: also available as University of Washington TR 89-08-06.
0034:
0035: This implementation by Mario Wolczko, Sun Microsystems, Sep 1996,
0036: based on the Smalltalk implementation by John Maloney.
0037:
0038: */
0039:
0040: package COM.sun.labs.kanban.DeltaBlue;
0041:
0042: import java.util.Vector;
0043:
0044: import Benchmark;
0045:
0046: /*
0047: Strengths are used to measure the relative importance of constraints.
0048: New strengths may be inserted in the strength hierarchy without
0049: disrupting current constraints. Strengths cannot be created outside
0050: this class, so pointer comparison can be used for value comparison.
0051: */
0052:
0053: class Strength {
0054:
0055: private int strengthValue;
0056: private String name;
0057:
0058: private Strength(int strengthValue, String name) {
0059: this .strengthValue = strengthValue;
0060: this .name = name;
0061: }
0062:
0063: public static boolean stronger(Strength s1, Strength s2) {
0064: return s1.strengthValue < s2.strengthValue;
0065: }
0066:
0067: public static boolean weaker(Strength s1, Strength s2) {
0068: return s1.strengthValue > s2.strengthValue;
0069: }
0070:
0071: public static Strength weakestOf(Strength s1, Strength s2) {
0072: return weaker(s1, s2) ? s1 : s2;
0073: }
0074:
0075: public static Strength strongest(Strength s1, Strength s2) {
0076: return stronger(s1, s2) ? s1 : s2;
0077: }
0078:
0079: // for iteration
0080: public Strength nextWeaker() {
0081: switch (strengthValue) {
0082: case 0:
0083: return weakest;
0084: case 1:
0085: return weakDefault;
0086: case 2:
0087: return normal;
0088: case 3:
0089: return strongDefault;
0090: case 4:
0091: return preferred;
0092: case 5:
0093: return strongPreferred;
0094:
0095: case 6:
0096: default:
0097: System.err.println("Invalid call to nextStrength()!");
0098: System.exit(1);
0099: return null;
0100: }
0101: }
0102:
0103: // Strength constants
0104: public final static Strength required = new Strength(0, "required");
0105: public final static Strength strongPreferred = new Strength(1,
0106: "strongPreferred");
0107: public final static Strength preferred = new Strength(2,
0108: "preferred");
0109: public final static Strength strongDefault = new Strength(3,
0110: "strongDefault");
0111: public final static Strength normal = new Strength(4, "normal");
0112: public final static Strength weakDefault = new Strength(5,
0113: "weakDefault");
0114: public final static Strength weakest = new Strength(6, "weakest");
0115:
0116: public void print() {
0117: System.out.print("strength[" + Integer.toString(strengthValue)
0118: + "]");
0119: }
0120: }
0121:
0122: //------------------------------ variables ------------------------------
0123:
0124: // I represent a constrained variable. In addition to my value, I
0125: // maintain the structure of the constraint graph, the current
0126: // dataflow graph, and various parameters of interest to the DeltaBlue
0127: // incremental constraint solver.
0128:
0129: class Variable {
0130:
0131: public int value; // my value; changed by constraints
0132: public Vector constraints; // normal constraints that reference me
0133: public Constraint determinedBy; // the constraint that currently determines
0134: // my value (or null if there isn't one)
0135: public int mark; // used by the planner to mark constraints
0136: public Strength walkStrength; // my walkabout strength
0137: public boolean stay; // true if I am a planning-time constant
0138: public String name; // a symbolic name for reporting purposes
0139:
0140: private Variable(String name, int initialValue,
0141: Strength walkStrength, int nconstraints) {
0142: value = initialValue;
0143: constraints = new Vector(nconstraints);
0144: determinedBy = null;
0145: mark = 0;
0146: this .walkStrength = walkStrength;
0147: stay = true;
0148: this .name = name;
0149: }
0150:
0151: public Variable(String name, int value) {
0152: this (name, value, Strength.weakest, 2);
0153: }
0154:
0155: public Variable(String name) {
0156: this (name, 0, Strength.weakest, 2);
0157: }
0158:
0159: public void print() {
0160: System.out.print(name + "(");
0161: walkStrength.print();
0162: System.out.print("," + value + ")");
0163: }
0164:
0165: // Add the given constraint to the set of all constraints that refer to me.
0166: public void addConstraint(Constraint c) {
0167: constraints.addElement(c);
0168: }
0169:
0170: // Remove all traces of c from this variable.
0171: public void removeConstraint(Constraint c) {
0172: constraints.removeElement(c);
0173: if (determinedBy == c)
0174: determinedBy = null;
0175: }
0176:
0177: // Attempt to assign the given value to me using the given strength.
0178: public void setValue(int value, Strength strength) {
0179: EditConstraint e = new EditConstraint(this , strength);
0180: if (e.isSatisfied()) {
0181: this .value = value;
0182: DeltaBlue.planner.propagateFrom(this );
0183: }
0184: e.destroyConstraint();
0185: }
0186:
0187: }
0188:
0189: //------------------------ constraints ------------------------------------
0190:
0191: // I am an abstract class representing a system-maintainable
0192: // relationship (or "constraint") between a set of variables. I supply
0193: // a strength instance variable; concrete subclasses provide a means
0194: // of storing the constrained variables and other information required
0195: // to represent a constraint.
0196:
0197: abstract class Constraint {
0198:
0199: public Strength strength; // the strength of this constraint
0200:
0201: protected Constraint() {
0202: } // this has to be here because of
0203:
0204: // Java's constructor idiocy.
0205:
0206: protected Constraint(Strength strength) {
0207: this .strength = strength;
0208: }
0209:
0210: // Answer true if this constraint is satisfied in the current solution.
0211: public abstract boolean isSatisfied();
0212:
0213: // Record the fact that I am unsatisfied.
0214: public abstract void markUnsatisfied();
0215:
0216: // Normal constraints are not input constraints. An input constraint
0217: // is one that depends on external state, such as the mouse, the
0218: // keyboard, a clock, or some arbitrary piece of imperative code.
0219: public boolean isInput() {
0220: return false;
0221: }
0222:
0223: // Activate this constraint and attempt to satisfy it.
0224: protected void addConstraint() {
0225: addToGraph();
0226: DeltaBlue.planner.incrementalAdd(this );
0227: }
0228:
0229: // Deactivate this constraint, remove it from the constraint graph,
0230: // possibly causing other constraints to be satisfied, and destroy
0231: // it.
0232: public void destroyConstraint() {
0233: if (isSatisfied())
0234: DeltaBlue.planner.incrementalRemove(this );
0235: removeFromGraph();
0236: }
0237:
0238: // Add myself to the constraint graph.
0239: public abstract void addToGraph();
0240:
0241: // Remove myself from the constraint graph.
0242: public abstract void removeFromGraph();
0243:
0244: // Decide if I can be satisfied and record that decision. The output
0245: // of the choosen method must not have the given mark and must have
0246: // a walkabout strength less than that of this constraint.
0247: protected abstract void chooseMethod(int mark);
0248:
0249: // Set the mark of all input from the given mark.
0250: protected abstract void markInputs(int mark);
0251:
0252: // Assume that I am satisfied. Answer true if all my current inputs
0253: // are known. A variable is known if either a) it is 'stay' (i.e. it
0254: // is a constant at plan execution time), b) it has the given mark
0255: // (indicating that it has been computed by a constraint appearing
0256: // earlier in the plan), or c) it is not determined by any
0257: // constraint.
0258: public abstract boolean inputsKnown(int mark);
0259:
0260: // Answer my current output variable. Raise an error if I am not
0261: // currently satisfied.
0262: public abstract Variable output();
0263:
0264: // Attempt to find a way to enforce this constraint. If successful,
0265: // record the solution, perhaps modifying the current dataflow
0266: // graph. Answer the constraint that this constraint overrides, if
0267: // there is one, or nil, if there isn't.
0268: // Assume: I am not already satisfied.
0269: //
0270: public Constraint satisfy(int mark) {
0271: chooseMethod(mark);
0272: if (!isSatisfied()) {
0273: if (strength == Strength.required) {
0274: DeltaBlue
0275: .error("Could not satisfy a required constraint");
0276: }
0277: return null;
0278: }
0279: // constraint can be satisfied
0280: // mark inputs to allow cycle detection in addPropagate
0281: markInputs(mark);
0282: Variable out = output();
0283: Constraint overridden = out.determinedBy;
0284: if (overridden != null)
0285: overridden.markUnsatisfied();
0286: out.determinedBy = this ;
0287: if (!DeltaBlue.planner.addPropagate(this , mark)) {
0288: System.out.println("Cycle encountered");
0289: return null;
0290: }
0291: out.mark = mark;
0292: return overridden;
0293: }
0294:
0295: // Enforce this constraint. Assume that it is satisfied.
0296: public abstract void execute();
0297:
0298: // Calculate the walkabout strength, the stay flag, and, if it is
0299: // 'stay', the value for the current output of this
0300: // constraint. Assume this constraint is satisfied.
0301: public abstract void recalculate();
0302:
0303: protected abstract void printInputs();
0304:
0305: protected void printOutput() {
0306: output().print();
0307: }
0308:
0309: public void print() {
0310: int i, outIndex;
0311:
0312: if (!isSatisfied()) {
0313: System.out.print("Unsatisfied");
0314: } else {
0315: System.out.print("Satisfied(");
0316: printInputs();
0317: System.out.print(" -> ");
0318: printOutput();
0319: System.out.print(")");
0320: }
0321: System.out.print("\n");
0322: }
0323:
0324: }
0325:
0326: //-------------unary constraints-------------------------------------------
0327:
0328: // I am an abstract superclass for constraints having a single
0329: // possible output variable.
0330: //
0331: abstract class UnaryConstraint extends Constraint {
0332:
0333: protected Variable myOutput; // possible output variable
0334: protected boolean satisfied; // true if I am currently satisfied
0335:
0336: protected UnaryConstraint(Variable v, Strength strength) {
0337: super (strength);
0338: myOutput = v;
0339: satisfied = false;
0340: addConstraint();
0341: }
0342:
0343: // Answer true if this constraint is satisfied in the current solution.
0344: public boolean isSatisfied() {
0345: return satisfied;
0346: }
0347:
0348: // Record the fact that I am unsatisfied.
0349: public void markUnsatisfied() {
0350: satisfied = false;
0351: }
0352:
0353: // Answer my current output variable.
0354: public Variable output() {
0355: return myOutput;
0356: }
0357:
0358: // Add myself to the constraint graph.
0359: public void addToGraph() {
0360: myOutput.addConstraint(this );
0361: satisfied = false;
0362: }
0363:
0364: // Remove myself from the constraint graph.
0365: public void removeFromGraph() {
0366: if (myOutput != null)
0367: myOutput.removeConstraint(this );
0368: satisfied = false;
0369: }
0370:
0371: // Decide if I can be satisfied and record that decision.
0372: protected void chooseMethod(int mark) {
0373: satisfied = myOutput.mark != mark
0374: && Strength.stronger(strength, myOutput.walkStrength);
0375: }
0376:
0377: protected void markInputs(int mark) {
0378: } // I have no inputs
0379:
0380: public boolean inputsKnown(int mark) {
0381: return true;
0382: }
0383:
0384: // Calculate the walkabout strength, the stay flag, and, if it is
0385: // 'stay', the value for the current output of this
0386: // constraint. Assume this constraint is satisfied."
0387: public void recalculate() {
0388: myOutput.walkStrength = strength;
0389: myOutput.stay = !isInput();
0390: if (myOutput.stay)
0391: execute(); // stay optimization
0392: }
0393:
0394: protected void printInputs() {
0395: } // I have no inputs
0396:
0397: }
0398:
0399: // I am a unary input constraint used to mark a variable that the
0400: // client wishes to change.
0401: //
0402: class EditConstraint extends UnaryConstraint {
0403:
0404: public EditConstraint(Variable v, Strength str) {
0405: super (v, str);
0406: }
0407:
0408: // I indicate that a variable is to be changed by imperative code.
0409: public boolean isInput() {
0410: return true;
0411: }
0412:
0413: public void execute() {
0414: } // Edit constraints do nothing.
0415:
0416: }
0417:
0418: // I mark variables that should, with some level of preference, stay
0419: // the same. I have one method with zero inputs and one output, which
0420: // does nothing. Planners may exploit the fact that, if I am
0421: // satisfied, my output will not change during plan execution. This is
0422: // called "stay optimization".
0423: //
0424: class StayConstraint extends UnaryConstraint {
0425:
0426: // Install a stay constraint with the given strength on the given variable.
0427: public StayConstraint(Variable v, Strength str) {
0428: super (v, str);
0429: }
0430:
0431: public void execute() {
0432: } // Stay constraints do nothing.
0433:
0434: }
0435:
0436: //-------------binary constraints-------------------------------------------
0437:
0438: // I am an abstract superclass for constraints having two possible
0439: // output variables.
0440: //
0441: abstract class BinaryConstraint extends Constraint {
0442:
0443: protected Variable v1, v2; // possible output variables
0444: protected byte direction; // one of the following...
0445: protected static byte backward = -1; // v1 is output
0446: protected static byte nodirection = 0; // not satisfied
0447: protected static byte forward = 1; // v2 is output
0448:
0449: protected BinaryConstraint() {
0450: } // this has to be here because of
0451:
0452: // Java's constructor idiocy.
0453:
0454: protected BinaryConstraint(Variable var1, Variable var2,
0455: Strength strength) {
0456: super (strength);
0457: v1 = var1;
0458: v2 = var2;
0459: direction = nodirection;
0460: addConstraint();
0461: }
0462:
0463: // Answer true if this constraint is satisfied in the current solution.
0464: public boolean isSatisfied() {
0465: return direction != nodirection;
0466: }
0467:
0468: // Add myself to the constraint graph.
0469: public void addToGraph() {
0470: v1.addConstraint(this );
0471: v2.addConstraint(this );
0472: direction = nodirection;
0473: }
0474:
0475: // Remove myself from the constraint graph.
0476: public void removeFromGraph() {
0477: if (v1 != null)
0478: v1.removeConstraint(this );
0479: if (v2 != null)
0480: v2.removeConstraint(this );
0481: direction = nodirection;
0482: }
0483:
0484: // Decide if I can be satisfied and which way I should flow based on
0485: // the relative strength of the variables I relate, and record that
0486: // decision.
0487: //
0488: protected void chooseMethod(int mark) {
0489: if (v1.mark == mark)
0490: direction = v2.mark != mark
0491: && Strength.stronger(strength, v2.walkStrength) ? forward
0492: : nodirection;
0493:
0494: if (v2.mark == mark)
0495: direction = v1.mark != mark
0496: && Strength.stronger(strength, v1.walkStrength) ? backward
0497: : nodirection;
0498:
0499: // If we get here, neither variable is marked, so we have a choice.
0500: if (Strength.weaker(v1.walkStrength, v2.walkStrength))
0501: direction = Strength.stronger(strength, v1.walkStrength) ? backward
0502: : nodirection;
0503: else
0504: direction = Strength.stronger(strength, v2.walkStrength) ? forward
0505: : nodirection;
0506: }
0507:
0508: // Record the fact that I am unsatisfied.
0509: public void markUnsatisfied() {
0510: direction = nodirection;
0511: }
0512:
0513: // Mark the input variable with the given mark.
0514: protected void markInputs(int mark) {
0515: input().mark = mark;
0516: }
0517:
0518: public boolean inputsKnown(int mark) {
0519: Variable i = input();
0520: return i.mark == mark || i.stay || i.determinedBy == null;
0521: }
0522:
0523: // Answer my current output variable.
0524: public Variable output() {
0525: return direction == forward ? v2 : v1;
0526: }
0527:
0528: // Answer my current input variable
0529: public Variable input() {
0530: return direction == forward ? v1 : v2;
0531: }
0532:
0533: // Calculate the walkabout strength, the stay flag, and, if it is
0534: // 'stay', the value for the current output of this
0535: // constraint. Assume this constraint is satisfied.
0536: //
0537: public void recalculate() {
0538: Variable in = input(), out = output();
0539: out.walkStrength = Strength
0540: .weakestOf(strength, in.walkStrength);
0541: out.stay = in.stay;
0542: if (out.stay)
0543: execute();
0544: }
0545:
0546: protected void printInputs() {
0547: input().print();
0548: }
0549:
0550: }
0551:
0552: // I constrain two variables to have the same value: "v1 = v2".
0553: //
0554: class EqualityConstraint extends BinaryConstraint {
0555:
0556: // Install a constraint with the given strength equating the given variables.
0557: public EqualityConstraint(Variable var1, Variable var2,
0558: Strength strength) {
0559: super (var1, var2, strength);
0560: }
0561:
0562: // Enforce this constraint. Assume that it is satisfied.
0563: public void execute() {
0564: output().value = input().value;
0565: }
0566:
0567: }
0568:
0569: // I relate two variables by the linear scaling relationship: "v2 =
0570: // (v1 * scale) + offset". Either v1 or v2 may be changed to maintain
0571: // this relationship but the scale factor and offset are considered
0572: // read-only.
0573: //
0574: class ScaleConstraint extends BinaryConstraint {
0575:
0576: protected Variable scale; // scale factor input variable
0577: protected Variable offset; // offset input variable
0578:
0579: // Install a scale constraint with the given strength on the given variables.
0580: public ScaleConstraint(Variable src, Variable scale,
0581: Variable offset, Variable dest, Strength strength) {
0582: // Curse this wretched language for insisting that constructor invocation
0583: // must be the first thing in a method...
0584: // ..because of that, we must copy the code from the inherited
0585: // constructors.
0586: this .strength = strength;
0587: v1 = src;
0588: v2 = dest;
0589: direction = nodirection;
0590: this .scale = scale;
0591: this .offset = offset;
0592: addConstraint();
0593: }
0594:
0595: // Add myself to the constraint graph.
0596: public void addToGraph() {
0597: super .addToGraph();
0598: scale.addConstraint(this );
0599: offset.addConstraint(this );
0600: }
0601:
0602: // Remove myself from the constraint graph.
0603: public void removeFromGraph() {
0604: super .removeFromGraph();
0605: if (scale != null)
0606: scale.removeConstraint(this );
0607: if (offset != null)
0608: offset.removeConstraint(this );
0609: }
0610:
0611: // Mark the inputs from the given mark.
0612: protected void markInputs(int mark) {
0613: super .markInputs(mark);
0614: scale.mark = offset.mark = mark;
0615: }
0616:
0617: // Enforce this constraint. Assume that it is satisfied.
0618: public void execute() {
0619: if (direction == forward)
0620: v2.value = v1.value * scale.value + offset.value;
0621: else
0622: v1.value = (v2.value - offset.value) / scale.value;
0623: }
0624:
0625: // Calculate the walkabout strength, the stay flag, and, if it is
0626: // 'stay', the value for the current output of this
0627: // constraint. Assume this constraint is satisfied.
0628: public void recalculate() {
0629: Variable in = input(), out = output();
0630: out.walkStrength = Strength
0631: .weakestOf(strength, in.walkStrength);
0632: out.stay = in.stay && scale.stay && offset.stay;
0633: if (out.stay)
0634: execute(); // stay optimization
0635: }
0636: }
0637:
0638: // ------------------------------------------------------------
0639:
0640: // A Plan is an ordered list of constraints to be executed in sequence
0641: // to resatisfy all currently satisfiable constraints in the face of
0642: // one or more changing inputs.
0643:
0644: class Plan {
0645:
0646: private Vector v;
0647:
0648: public Plan() {
0649: v = new Vector();
0650: }
0651:
0652: public void addConstraint(Constraint c) {
0653: v.addElement(c);
0654: }
0655:
0656: public int size() {
0657: return v.size();
0658: }
0659:
0660: public Constraint constraintAt(int index) {
0661: return (Constraint) v.elementAt(index);
0662: }
0663:
0664: public void execute() {
0665: for (int i = 0; i < size(); ++i) {
0666: Constraint c = (Constraint) constraintAt(i);
0667: c.execute();
0668: }
0669: }
0670:
0671: }
0672:
0673: // ------------------------------------------------------------
0674:
0675: // The DeltaBlue planner
0676:
0677: class Planner {
0678:
0679: int currentMark = 0;
0680:
0681: // Select a previously unused mark value.
0682: private int newMark() {
0683: return ++currentMark;
0684: }
0685:
0686: public Planner() {
0687: currentMark = 0;
0688: }
0689:
0690: // Attempt to satisfy the given constraint and, if successful,
0691: // incrementally update the dataflow graph. Details: If satifying
0692: // the constraint is successful, it may override a weaker constraint
0693: // on its output. The algorithm attempts to resatisfy that
0694: // constraint using some other method. This process is repeated
0695: // until either a) it reaches a variable that was not previously
0696: // determined by any constraint or b) it reaches a constraint that
0697: // is too weak to be satisfied using any of its methods. The
0698: // variables of constraints that have been processed are marked with
0699: // a unique mark value so that we know where we've been. This allows
0700: // the algorithm to avoid getting into an infinite loop even if the
0701: // constraint graph has an inadvertent cycle.
0702: //
0703: public void incrementalAdd(Constraint c) {
0704: int mark = newMark();
0705: Constraint overridden = c.satisfy(mark);
0706: while (overridden != null) {
0707: overridden = overridden.satisfy(mark);
0708: }
0709: }
0710:
0711: // Entry point for retracting a constraint. Remove the given
0712: // constraint and incrementally update the dataflow graph.
0713: // Details: Retracting the given constraint may allow some currently
0714: // unsatisfiable downstream constraint to be satisfied. We therefore collect
0715: // a list of unsatisfied downstream constraints and attempt to
0716: // satisfy each one in turn. This list is traversed by constraint
0717: // strength, strongest first, as a heuristic for avoiding
0718: // unnecessarily adding and then overriding weak constraints.
0719: // Assume: c is satisfied.
0720: //
0721: public void incrementalRemove(Constraint c) {
0722: Variable out = c.output();
0723: c.markUnsatisfied();
0724: c.removeFromGraph();
0725: Vector unsatisfied = removePropagateFrom(out);
0726: Strength strength = Strength.required;
0727: do {
0728: for (int i = 0; i < unsatisfied.size(); ++i) {
0729: Constraint u = (Constraint) unsatisfied.elementAt(i);
0730: if (u.strength == strength)
0731: incrementalAdd(u);
0732: }
0733: strength = strength.nextWeaker();
0734: } while (strength != Strength.weakest);
0735: }
0736:
0737: // Recompute the walkabout strengths and stay flags of all variables
0738: // downstream of the given constraint and recompute the actual
0739: // values of all variables whose stay flag is true. If a cycle is
0740: // detected, remove the given constraint and answer
0741: // false. Otherwise, answer true.
0742: // Details: Cycles are detected when a marked variable is
0743: // encountered downstream of the given constraint. The sender is
0744: // assumed to have marked the inputs of the given constraint with
0745: // the given mark. Thus, encountering a marked node downstream of
0746: // the output constraint means that there is a path from the
0747: // constraint's output to one of its inputs.
0748: //
0749: public boolean addPropagate(Constraint c, int mark) {
0750: Vector todo = new Vector();
0751: todo.addElement(c);
0752: while (!todo.isEmpty()) {
0753: Constraint d = (Constraint) todo.elementAt(0);
0754: todo.removeElementAt(0);
0755: if (d.output().mark == mark) {
0756: incrementalRemove(c);
0757: return false;
0758: }
0759: d.recalculate();
0760: addConstraintsConsumingTo(d.output(), todo);
0761: }
0762: return true;
0763: }
0764:
0765: // The given variable has changed. Propagate new values downstream.
0766: public void propagateFrom(Variable v) {
0767: Vector todo = new Vector();
0768: addConstraintsConsumingTo(v, todo);
0769: while (!todo.isEmpty()) {
0770: Constraint c = (Constraint) todo.elementAt(0);
0771: todo.removeElementAt(0);
0772: c.execute();
0773: addConstraintsConsumingTo(c.output(), todo);
0774: }
0775: }
0776:
0777: // Update the walkabout strengths and stay flags of all variables
0778: // downstream of the given constraint. Answer a collection of
0779: // unsatisfied constraints sorted in order of decreasing strength.
0780: //
0781: protected Vector removePropagateFrom(Variable out) {
0782: out.determinedBy = null;
0783: out.walkStrength = Strength.weakest;
0784: out.stay = true;
0785: Vector unsatisfied = new Vector();
0786: Vector todo = new Vector();
0787: todo.addElement(out);
0788: while (!todo.isEmpty()) {
0789: Variable v = (Variable) todo.elementAt(0);
0790: todo.removeElementAt(0);
0791: for (int i = 0; i < v.constraints.size(); ++i) {
0792: Constraint c = (Constraint) v.constraints.elementAt(i);
0793: if (!c.isSatisfied())
0794: unsatisfied.addElement(c);
0795: }
0796: Constraint determiningC = v.determinedBy;
0797: for (int i = 0; i < v.constraints.size(); ++i) {
0798: Constraint nextC = (Constraint) v.constraints
0799: .elementAt(i);
0800: if (nextC != determiningC && nextC.isSatisfied()) {
0801: nextC.recalculate();
0802: todo.addElement(nextC.output());
0803: }
0804: }
0805: }
0806: return unsatisfied;
0807: }
0808:
0809: // Extract a plan for resatisfaction starting from the outputs of
0810: // the given constraints, usually a set of input constraints.
0811: //
0812: protected Plan extractPlanFromConstraints(Vector constraints) {
0813: Vector sources = new Vector();
0814: for (int i = 0; i < constraints.size(); ++i) {
0815: Constraint c = (Constraint) constraints.elementAt(i);
0816: if (c.isInput() && c.isSatisfied())
0817: sources.addElement(c);
0818: }
0819: return makePlan(sources);
0820: }
0821:
0822: // Extract a plan for resatisfaction starting from the given source
0823: // constraints, usually a set of input constraints. This method
0824: // assumes that stay optimization is desired; the plan will contain
0825: // only constraints whose output variables are not stay. Constraints
0826: // that do no computation, such as stay and edit constraints, are
0827: // not included in the plan.
0828: // Details: The outputs of a constraint are marked when it is added
0829: // to the plan under construction. A constraint may be appended to
0830: // the plan when all its input variables are known. A variable is
0831: // known if either a) the variable is marked (indicating that has
0832: // been computed by a constraint appearing earlier in the plan), b)
0833: // the variable is 'stay' (i.e. it is a constant at plan execution
0834: // time), or c) the variable is not determined by any
0835: // constraint. The last provision is for past states of history
0836: // variables, which are not stay but which are also not computed by
0837: // any constraint.
0838: // Assume: sources are all satisfied.
0839: //
0840: protected Plan makePlan(Vector sources) {
0841: int mark = newMark();
0842: Plan plan = new Plan();
0843: Vector todo = sources;
0844: while (!todo.isEmpty()) {
0845: Constraint c = (Constraint) todo.elementAt(0);
0846: todo.removeElementAt(0);
0847: if (c.output().mark != mark && c.inputsKnown(mark)) {
0848: // not in plan already and eligible for inclusion
0849: plan.addConstraint(c);
0850: c.output().mark = mark;
0851: addConstraintsConsumingTo(c.output(), todo);
0852: }
0853: }
0854: return plan;
0855: }
0856:
0857: protected void addConstraintsConsumingTo(Variable v, Vector coll) {
0858: Constraint determiningC = v.determinedBy;
0859: Vector cc = v.constraints;
0860: for (int i = 0; i < cc.size(); ++i) {
0861: Constraint c = (Constraint) cc.elementAt(i);
0862: if (c != determiningC && c.isSatisfied())
0863: coll.addElement(c);
0864: }
0865: }
0866:
0867: }
0868:
0869: //------------------------------------------------------------
0870:
0871: public class DeltaBlue implements Benchmark {
0872:
0873: private long total_ms;
0874:
0875: public long getRunTime() {
0876: return total_ms;
0877: }
0878:
0879: public static Planner planner;
0880:
0881: public static void main(String[] args) {
0882: (new DeltaBlue()).inst_main(args);
0883: }
0884:
0885: public void inst_main(String args[]) {
0886: System.out.println("DeltaBlue benchmark starting...");
0887: int iterations = 100;
0888: long startTime = System.currentTimeMillis();
0889: for (int j = 0; j < iterations; ++j) {
0890: chainTest(100);
0891: projectionTest(100);
0892: }
0893: long endTime = System.currentTimeMillis();
0894: total_ms = endTime - startTime;
0895: System.out.println("Total time for " + iterations
0896: + " iterations of chain and projection tests: "
0897: + total_ms + " ms");
0898: System.out.println("Average time per iteration: "
0899: + ((double) total_ms / iterations) + " ms");
0900:
0901: }
0902:
0903: // This is the standard DeltaBlue benchmark. A long chain of
0904: // equality constraints is constructed with a stay constraint on
0905: // one end. An edit constraint is then added to the opposite end
0906: // and the time is measured for adding and removing this
0907: // constraint, and extracting and executing a constraint
0908: // satisfaction plan. There are two cases. In case 1, the added
0909: // constraint is stronger than the stay constraint and values must
0910: // propagate down the entire length of the chain. In case 2, the
0911: // added constraint is weaker than the stay constraint so it cannot
0912: // be accomodated. The cost in this case is, of course, very
0913: // low. Typical situations lie somewhere between these two
0914: // extremes.
0915: //
0916: private void chainTest(int n) {
0917: planner = new Planner();
0918:
0919: Variable prev = null, first = null, last = null;
0920:
0921: // Build chain of n equality constraints
0922: for (int i = 0; i <= n; i++) {
0923: String name = "v" + Integer.toString(i);
0924: Variable v = new Variable(name);
0925: if (prev != null)
0926: new EqualityConstraint(prev, v, Strength.required);
0927: if (i == 0)
0928: first = v;
0929: if (i == n)
0930: last = v;
0931: prev = v;
0932: }
0933:
0934: new StayConstraint(last, Strength.strongDefault);
0935: Constraint editC = new EditConstraint(first, Strength.preferred);
0936: Vector editV = new Vector();
0937: editV.addElement(editC);
0938: Plan plan = planner.extractPlanFromConstraints(editV);
0939: for (int i = 0; i < 100; i++) {
0940: first.value = i;
0941: plan.execute();
0942: if (last.value != i)
0943: error("Chain test failed!");
0944: }
0945: editC.destroyConstraint();
0946: }
0947:
0948: // This test constructs a two sets of variables related to each
0949: // other by a simple linear transformation (scale and offset). The
0950: // time is measured to change a variable on either side of the
0951: // mapping and to change the scale and offset factors.
0952: //
0953: private void projectionTest(int n) {
0954: planner = new Planner();
0955:
0956: Variable scale = new Variable("scale", 10);
0957: Variable offset = new Variable("offset", 1000);
0958: Variable src = null, dst = null;
0959:
0960: Vector dests = new Vector();
0961:
0962: for (int i = 0; i < n; ++i) {
0963: src = new Variable("src" + Integer.toString(i), i);
0964: dst = new Variable("dst" + Integer.toString(i), i);
0965: dests.addElement(dst);
0966: new StayConstraint(src, Strength.normal);
0967: new ScaleConstraint(src, scale, offset, dst,
0968: Strength.required);
0969: }
0970:
0971: change(src, 17);
0972: if (dst.value != 1170)
0973: error("Projection test 1 failed!");
0974:
0975: change(dst, 1050);
0976: if (src.value != 5)
0977: error("Projection test 2 failed!");
0978:
0979: change(scale, 5);
0980: for (int i = 0; i < n - 1; ++i) {
0981: if (((Variable) dests.elementAt(i)).value != i * 5 + 1000)
0982: error("Projection test 3 failed!");
0983: }
0984:
0985: change(offset, 2000);
0986: for (int i = 0; i < n - 1; ++i) {
0987: if (((Variable) dests.elementAt(i)).value != i * 5 + 2000)
0988: error("Projection test 4 failed!");
0989: }
0990: }
0991:
0992: private void change(Variable var, int newValue) {
0993: EditConstraint editC = new EditConstraint(var,
0994: Strength.preferred);
0995: Vector editV = new Vector();
0996: editV.addElement(editC);
0997: Plan plan = planner.extractPlanFromConstraints(editV);
0998: for (int i = 0; i < 10; i++) {
0999: var.value = newValue;
1000: plan.execute();
1001: }
1002: editC.destroyConstraint();
1003: }
1004:
1005: public static void error(String s) {
1006: System.err.println(s);
1007: System.exit(1);
1008: }
1009:
1010: }
|