10bf48ef3be53ddaa52bbead65dfd75bf90e7a2b5Ben Murdoch// Copyright 2008 the V8 project authors. All rights reserved. 2563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// Copyright 1996 John Maloney and Mario Wolczko. 3563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 4563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// This program is free software; you can redistribute it and/or modify 5563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// it under the terms of the GNU General Public License as published by 6563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// the Free Software Foundation; either version 2 of the License, or 7563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// (at your option) any later version. 8563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// 9563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// This program is distributed in the hope that it will be useful, 10563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// but WITHOUT ANY WARRANTY; without even the implied warranty of 11563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 12563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// GNU General Public License for more details. 13563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// 14563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// You should have received a copy of the GNU General Public License 15563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// along with this program; if not, write to the Free Software 16563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA 17563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 18563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 190bf48ef3be53ddaa52bbead65dfd75bf90e7a2b5Ben Murdoch// This implementation of the DeltaBlue benchmark is derived 200bf48ef3be53ddaa52bbead65dfd75bf90e7a2b5Ben Murdoch// from the Smalltalk implementation by John Maloney and Mario 210bf48ef3be53ddaa52bbead65dfd75bf90e7a2b5Ben Murdoch// Wolczko. Some parts have been translated directly, whereas 220bf48ef3be53ddaa52bbead65dfd75bf90e7a2b5Ben Murdoch// others have been modified more aggresively to make it feel 23563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// more like a JavaScript program. 24563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 25563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark/** 26563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * A JavaScript implementation of the DeltaBlue constrain-solving 27563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * algorithm, as described in: 28563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * 29563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * "The DeltaBlue Algorithm: An Incremental Constraint Hierarchy Solver" 30563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * Bjorn N. Freeman-Benson and John Maloney 31563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * January 1990 Communications of the ACM, 32563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * also available as University of Washington TR 89-08-06. 33563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * 34563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * Beware: this benchmark is written in a grotesque style where 35563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * the constraint model is built by side-effects from constructors. 36563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * I've kept it this way to avoid deviating too much from the original 37563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * implementation. 38563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark */ 39563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 40563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 41563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark/* --- O b j e c t M o d e l --- */ 42563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 43563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkObject.prototype.inherits = function (shuper) { 44563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark function Inheriter() { } 45563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark Inheriter.prototype = shuper.prototype; 46563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.prototype = new Inheriter(); 47563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.superConstructor = shuper; 48563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 49563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 50563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction OrderedCollection() { 51563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.elms = new Array(); 52563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 53563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 54563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkOrderedCollection.prototype.add = function (elm) { 55563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.elms.push(elm); 56563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 57563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 58563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkOrderedCollection.prototype.at = function (index) { 59563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark return this.elms[index]; 60563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 61563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 62563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkOrderedCollection.prototype.size = function () { 63563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark return this.elms.length; 64563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 65563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 66563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkOrderedCollection.prototype.removeFirst = function () { 67563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark return this.elms.pop(); 68563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 69563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 70563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkOrderedCollection.prototype.remove = function (elm) { 71563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var index = 0, skipped = 0; 72563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark for (var i = 0; i < this.elms.length; i++) { 73563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var value = this.elms[i]; 74563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if (value != elm) { 75563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.elms[index] = value; 76563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark index++; 77563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark } else { 78563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark skipped++; 79563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark } 80563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark } 81563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark for (var i = 0; i < skipped; i++) 82563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.elms.pop(); 83563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 84563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 85563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark/* --- * 86563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * S t r e n g t h 87563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * --- */ 88563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 89563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark/** 90563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * Strengths are used to measure the relative importance of constraints. 91563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * New strengths may be inserted in the strength hierarchy without 92563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * disrupting current constraints. Strengths cannot be created outside 93563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * this class, so pointer comparison can be used for value comparison. 94563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark */ 95563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction Strength(strengthValue, name) { 96563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.strengthValue = strengthValue; 97563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.name = name; 98563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 99563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 100563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkStrength.stronger = function (s1, s2) { 101563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark return s1.strengthValue < s2.strengthValue; 102563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 103563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 104563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkStrength.weaker = function (s1, s2) { 105563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark return s1.strengthValue > s2.strengthValue; 106563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 107563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 108563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkStrength.weakestOf = function (s1, s2) { 109563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark return this.weaker(s1, s2) ? s1 : s2; 110563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 111563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 112563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkStrength.strongest = function (s1, s2) { 113563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark return this.stronger(s1, s2) ? s1 : s2; 114563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 115563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 116563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkStrength.prototype.nextWeaker = function () { 117563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark switch (this.strengthValue) { 118563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark case 0: return Strength.WEAKEST; 119563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark case 1: return Strength.WEAK_DEFAULT; 120563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark case 2: return Strength.NORMAL; 121563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark case 3: return Strength.STRONG_DEFAULT; 122563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark case 4: return Strength.PREFERRED; 123563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark case 5: return Strength.REQUIRED; 124563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark } 125563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 126563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 127563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// Strength constants. 128563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkStrength.REQUIRED = new Strength(0, "required"); 129563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkStrength.STONG_PREFERRED = new Strength(1, "strongPreferred"); 130563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkStrength.PREFERRED = new Strength(2, "preferred"); 131563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkStrength.STRONG_DEFAULT = new Strength(3, "strongDefault"); 132563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkStrength.NORMAL = new Strength(4, "normal"); 133563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkStrength.WEAK_DEFAULT = new Strength(5, "weakDefault"); 134563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkStrength.WEAKEST = new Strength(6, "weakest"); 135563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 136563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark/* --- * 137563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * C o n s t r a i n t 138563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * --- */ 139563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 140563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark/** 141563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * An abstract class representing a system-maintainable relationship 142563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * (or "constraint") between a set of variables. A constraint supplies 143563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * a strength instance variable; concrete subclasses provide a means 144563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * of storing the constrained variables and other information required 145563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * to represent a constraint. 146563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark */ 147563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction Constraint(strength) { 148563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.strength = strength; 149563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 150563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 151563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark/** 152563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * Activate this constraint and attempt to satisfy it. 153563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark */ 154563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkConstraint.prototype.addConstraint = function () { 155563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.addToGraph(); 156563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark planner.incrementalAdd(this); 157563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 158563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 159563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark/** 160563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * Attempt to find a way to enforce this constraint. If successful, 161563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * record the solution, perhaps modifying the current dataflow 162563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * graph. Answer the constraint that this constraint overrides, if 163563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * there is one, or nil, if there isn't. 164563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * Assume: I am not already satisfied. 165563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark */ 166563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkConstraint.prototype.satisfy = function (mark) { 167563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.chooseMethod(mark); 168563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if (!this.isSatisfied()) { 169563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if (this.strength == Strength.REQUIRED) 170563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark alert("Could not satisfy a required constraint!"); 171563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark return null; 172563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark } 173563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.markInputs(mark); 174563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var out = this.output(); 175563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var overridden = out.determinedBy; 176563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if (overridden != null) overridden.markUnsatisfied(); 177563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark out.determinedBy = this; 178563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if (!planner.addPropagate(this, mark)) 179563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark alert("Cycle encountered"); 180563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark out.mark = mark; 181563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark return overridden; 182563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 183563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 184563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkConstraint.prototype.destroyConstraint = function () { 185563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if (this.isSatisfied()) planner.incrementalRemove(this); 186563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark else this.removeFromGraph(); 187563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 188563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 189563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark/** 190563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * Normal constraints are not input constraints. An input constraint 191563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * is one that depends on external state, such as the mouse, the 192563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * keybord, a clock, or some arbitraty piece of imperative code. 193563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark */ 194563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkConstraint.prototype.isInput = function () { 195563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark return false; 196563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 197563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 198563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark/* --- * 199563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * U n a r y C o n s t r a i n t 200563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * --- */ 201563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 202563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark/** 203563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * Abstract superclass for constraints having a single possible output 204563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * variable. 205563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark */ 206563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction UnaryConstraint(v, strength) { 207563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark UnaryConstraint.superConstructor.call(this, strength); 208563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.myOutput = v; 209563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.satisfied = false; 210563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.addConstraint(); 211563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 212563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 213563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkUnaryConstraint.inherits(Constraint); 214563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 215563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark/** 216563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * Adds this constraint to the constraint graph 217563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark */ 218563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkUnaryConstraint.prototype.addToGraph = function () { 219563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.myOutput.addConstraint(this); 220563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.satisfied = false; 221563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 222563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 223563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark/** 224563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * Decides if this constraint can be satisfied and records that 225563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * decision. 226563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark */ 227563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkUnaryConstraint.prototype.chooseMethod = function (mark) { 228563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.satisfied = (this.myOutput.mark != mark) 229563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark && Strength.stronger(this.strength, this.myOutput.walkStrength); 230563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 231563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 232563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark/** 233563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * Returns true if this constraint is satisfied in the current solution. 234563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark */ 235563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkUnaryConstraint.prototype.isSatisfied = function () { 236563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark return this.satisfied; 237563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 238563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 239563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkUnaryConstraint.prototype.markInputs = function (mark) { 240563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark // has no inputs 241563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 242563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 243563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark/** 244563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * Returns the current output variable. 245563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark */ 246563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkUnaryConstraint.prototype.output = function () { 247563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark return this.myOutput; 248563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 249563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 250563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark/** 251563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * Calculate the walkabout strength, the stay flag, and, if it is 252563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * 'stay', the value for the current output of this constraint. Assume 253563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * this constraint is satisfied. 254563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark */ 255563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkUnaryConstraint.prototype.recalculate = function () { 256563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.myOutput.walkStrength = this.strength; 257563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.myOutput.stay = !this.isInput(); 258563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if (this.myOutput.stay) this.execute(); // Stay optimization 259563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 260563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 261563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark/** 262563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * Records that this constraint is unsatisfied 263563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark */ 264563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkUnaryConstraint.prototype.markUnsatisfied = function () { 265563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.satisfied = false; 266563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 267563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 268563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkUnaryConstraint.prototype.inputsKnown = function () { 269563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark return true; 270563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 271563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 272563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkUnaryConstraint.prototype.removeFromGraph = function () { 273563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if (this.myOutput != null) this.myOutput.removeConstraint(this); 274563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.satisfied = false; 275563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 276563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 277563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark/* --- * 278563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * S t a y C o n s t r a i n t 279563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * --- */ 280563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 281563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark/** 282563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * Variables that should, with some level of preference, stay the same. 283563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * Planners may exploit the fact that instances, if satisfied, will not 284563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * change their output during plan execution. This is called "stay 285563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * optimization". 286563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark */ 287563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction StayConstraint(v, str) { 288563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark StayConstraint.superConstructor.call(this, v, str); 289563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 290563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 291563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkStayConstraint.inherits(UnaryConstraint); 292563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 293563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkStayConstraint.prototype.execute = function () { 294563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark // Stay constraints do nothing 295563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 296563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 297563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark/* --- * 298563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * E d i t C o n s t r a i n t 299563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * --- */ 300563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 301563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark/** 302563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * A unary input constraint used to mark a variable that the client 303563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * wishes to change. 304563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark */ 305563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction EditConstraint(v, str) { 306563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark EditConstraint.superConstructor.call(this, v, str); 307563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 308563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 309563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkEditConstraint.inherits(UnaryConstraint); 310563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 311563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark/** 312563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * Edits indicate that a variable is to be changed by imperative code. 313563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark */ 314563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkEditConstraint.prototype.isInput = function () { 315563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark return true; 316563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 317563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 318563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkEditConstraint.prototype.execute = function () { 319563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark // Edit constraints do nothing 320563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 321563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 322563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark/* --- * 323563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * B i n a r y C o n s t r a i n t 324563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * --- */ 325563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 326563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkvar Direction = new Object(); 327563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkDirection.NONE = 0; 328563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkDirection.FORWARD = 1; 329563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkDirection.BACKWARD = -1; 330563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 331563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark/** 332563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * Abstract superclass for constraints having two possible output 333563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * variables. 334563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark */ 335563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction BinaryConstraint(var1, var2, strength) { 336563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark BinaryConstraint.superConstructor.call(this, strength); 337563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.v1 = var1; 338563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.v2 = var2; 339563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.direction = Direction.NONE; 340563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.addConstraint(); 341563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 342563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 343563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkBinaryConstraint.inherits(Constraint); 344563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 345563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark/** 346563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * Decides if this constratint can be satisfied and which way it 347563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * should flow based on the relative strength of the variables related, 348563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * and record that decision. 349563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark */ 350563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkBinaryConstraint.prototype.chooseMethod = function (mark) { 351563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if (this.v1.mark == mark) { 352563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.direction = (this.v1.mark != mark && Strength.stronger(this.strength, this.v2.walkStrength)) 353563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark ? Direction.FORWARD 354563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark : Direction.NONE; 355563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark } 356563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if (this.v2.mark == mark) { 357563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.direction = (this.v1.mark != mark && Strength.stronger(this.strength, this.v1.walkStrength)) 358563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark ? Direction.BACKWARD 359563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark : Direction.NONE; 360563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark } 361563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if (Strength.weaker(this.v1.walkStrength, this.v2.walkStrength)) { 362563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.direction = Strength.stronger(this.strength, this.v1.walkStrength) 363563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark ? Direction.BACKWARD 364563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark : Direction.NONE; 365563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark } else { 366563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.direction = Strength.stronger(this.strength, this.v2.walkStrength) 367563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark ? Direction.FORWARD 368563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark : Direction.BACKWARD 369563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark } 370563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 371563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 372563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark/** 373563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * Add this constraint to the constraint graph 374563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark */ 375563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkBinaryConstraint.prototype.addToGraph = function () { 376563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.v1.addConstraint(this); 377563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.v2.addConstraint(this); 378563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.direction = Direction.NONE; 379563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 380563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 381563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark/** 382563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * Answer true if this constraint is satisfied in the current solution. 383563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark */ 384563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkBinaryConstraint.prototype.isSatisfied = function () { 385563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark return this.direction != Direction.NONE; 386563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 387563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 388563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark/** 389563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * Mark the input variable with the given mark. 390563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark */ 391563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkBinaryConstraint.prototype.markInputs = function (mark) { 392563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.input().mark = mark; 393563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 394563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 395563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark/** 396563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * Returns the current input variable 397563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark */ 398563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkBinaryConstraint.prototype.input = function () { 399563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark return (this.direction == Direction.FORWARD) ? this.v1 : this.v2; 400563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 401563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 402563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark/** 403563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * Returns the current output variable 404563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark */ 405563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkBinaryConstraint.prototype.output = function () { 406563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark return (this.direction == Direction.FORWARD) ? this.v2 : this.v1; 407563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 408563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 409563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark/** 410563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * Calculate the walkabout strength, the stay flag, and, if it is 411563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * 'stay', the value for the current output of this 412563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * constraint. Assume this constraint is satisfied. 413563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark */ 414563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkBinaryConstraint.prototype.recalculate = function () { 415563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var ihn = this.input(), out = this.output(); 416563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark out.walkStrength = Strength.weakestOf(this.strength, ihn.walkStrength); 417563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark out.stay = ihn.stay; 418563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if (out.stay) this.execute(); 419563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 420563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 421563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark/** 422563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * Record the fact that this constraint is unsatisfied. 423563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark */ 424563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkBinaryConstraint.prototype.markUnsatisfied = function () { 425563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.direction = Direction.NONE; 426563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 427563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 428563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkBinaryConstraint.prototype.inputsKnown = function (mark) { 429563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var i = this.input(); 430563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark return i.mark == mark || i.stay || i.determinedBy == null; 431563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 432563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 433563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkBinaryConstraint.prototype.removeFromGraph = function () { 434563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if (this.v1 != null) this.v1.removeConstraint(this); 435563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if (this.v2 != null) this.v2.removeConstraint(this); 436563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.direction = Direction.NONE; 437563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 438563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 439563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark/* --- * 440563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * S c a l e C o n s t r a i n t 441563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * --- */ 442563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 443563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark/** 444563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * Relates two variables by the linear scaling relationship: "v2 = 445563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * (v1 * scale) + offset". Either v1 or v2 may be changed to maintain 446563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * this relationship but the scale factor and offset are considered 447563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * read-only. 448563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark */ 449563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction ScaleConstraint(src, scale, offset, dest, strength) { 450563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.direction = Direction.NONE; 451563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.scale = scale; 452563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.offset = offset; 453563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark ScaleConstraint.superConstructor.call(this, src, dest, strength); 454563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 455563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 456563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkScaleConstraint.inherits(BinaryConstraint); 457563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 458563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark/** 459563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * Adds this constraint to the constraint graph. 460563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark */ 461563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkScaleConstraint.prototype.addToGraph = function () { 462563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark ScaleConstraint.superConstructor.prototype.addToGraph.call(this); 463563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.scale.addConstraint(this); 464563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.offset.addConstraint(this); 465563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 466563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 467563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkScaleConstraint.prototype.removeFromGraph = function () { 468563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark ScaleConstraint.superConstructor.prototype.removeFromGraph.call(this); 469563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if (this.scale != null) this.scale.removeConstraint(this); 470563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if (this.offset != null) this.offset.removeConstraint(this); 471563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 472563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 473563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkScaleConstraint.prototype.markInputs = function (mark) { 474563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark ScaleConstraint.superConstructor.prototype.markInputs.call(this, mark); 475563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.scale.mark = this.offset.mark = mark; 476563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 477563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 478563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark/** 479563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * Enforce this constraint. Assume that it is satisfied. 480563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark */ 481563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkScaleConstraint.prototype.execute = function () { 482563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if (this.direction == Direction.FORWARD) { 483563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.v2.value = this.v1.value * this.scale.value + this.offset.value; 484563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark } else { 485563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.v1.value = (this.v2.value - this.offset.value) / this.scale.value; 486563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark } 487563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 488563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 489563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark/** 490563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * Calculate the walkabout strength, the stay flag, and, if it is 491563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * 'stay', the value for the current output of this constraint. Assume 492563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * this constraint is satisfied. 493563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark */ 494563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkScaleConstraint.prototype.recalculate = function () { 495563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var ihn = this.input(), out = this.output(); 496563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark out.walkStrength = Strength.weakestOf(this.strength, ihn.walkStrength); 497563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark out.stay = ihn.stay && this.scale.stay && this.offset.stay; 498563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if (out.stay) this.execute(); 499563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 500563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 501563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark/* --- * 502563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * E q u a l i t y C o n s t r a i n t 503563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * --- */ 504563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 505563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark/** 506563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * Constrains two variables to have the same value. 507563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark */ 508563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction EqualityConstraint(var1, var2, strength) { 509563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark EqualityConstraint.superConstructor.call(this, var1, var2, strength); 510563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 511563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 512563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkEqualityConstraint.inherits(BinaryConstraint); 513563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 514563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark/** 515563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * Enforce this constraint. Assume that it is satisfied. 516563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark */ 517563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkEqualityConstraint.prototype.execute = function () { 518563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.output().value = this.input().value; 519563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 520563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 521563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark/* --- * 522563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * V a r i a b l e 523563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * --- */ 524563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 525563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark/** 526563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * A constrained variable. In addition to its value, it maintain the 527563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * structure of the constraint graph, the current dataflow graph, and 528563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * various parameters of interest to the DeltaBlue incremental 529563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * constraint solver. 530563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark **/ 531563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction Variable(name, initialValue) { 532563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.value = initialValue || 0; 533563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.constraints = new OrderedCollection(); 534563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.determinedBy = null; 535563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.mark = 0; 536563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.walkStrength = Strength.WEAKEST; 537563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.stay = true; 538563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.name = name; 539563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 540563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 541563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark/** 542563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * Add the given constraint to the set of all constraints that refer 543563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * this variable. 544563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark */ 545563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkVariable.prototype.addConstraint = function (c) { 546563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.constraints.add(c); 547563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 548563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 549563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark/** 550563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * Removes all traces of c from this variable. 551563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark */ 552563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkVariable.prototype.removeConstraint = function (c) { 553563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.constraints.remove(c); 554563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if (this.determinedBy == c) this.determinedBy = null; 555563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 556563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 557563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark/* --- * 558563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * P l a n n e r 559563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * --- */ 560563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 561563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark/** 562563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * The DeltaBlue planner 563563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark */ 564563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction Planner() { 565563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.currentMark = 0; 566563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 567563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 568563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark/** 569563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * Attempt to satisfy the given constraint and, if successful, 570563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * incrementally update the dataflow graph. Details: If satifying 571563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * the constraint is successful, it may override a weaker constraint 572563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * on its output. The algorithm attempts to resatisfy that 573563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * constraint using some other method. This process is repeated 574563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * until either a) it reaches a variable that was not previously 575563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * determined by any constraint or b) it reaches a constraint that 576563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * is too weak to be satisfied using any of its methods. The 577563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * variables of constraints that have been processed are marked with 578563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * a unique mark value so that we know where we've been. This allows 579563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * the algorithm to avoid getting into an infinite loop even if the 580563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * constraint graph has an inadvertent cycle. 581563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark */ 582563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkPlanner.prototype.incrementalAdd = function (c) { 583563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var mark = this.newMark(); 584563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var overridden = c.satisfy(mark); 585563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark while (overridden != null) 586563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark overridden = overridden.satisfy(mark); 587563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 588563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 589563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark/** 590563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * Entry point for retracting a constraint. Remove the given 591563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * constraint and incrementally update the dataflow graph. 592563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * Details: Retracting the given constraint may allow some currently 593563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * unsatisfiable downstream constraint to be satisfied. We therefore collect 594563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * a list of unsatisfied downstream constraints and attempt to 595563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * satisfy each one in turn. This list is traversed by constraint 596563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * strength, strongest first, as a heuristic for avoiding 597563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * unnecessarily adding and then overriding weak constraints. 598563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * Assume: c is satisfied. 599563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark */ 600563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkPlanner.prototype.incrementalRemove = function (c) { 601563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var out = c.output(); 602563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark c.markUnsatisfied(); 603563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark c.removeFromGraph(); 604563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var unsatisfied = this.removePropagateFrom(out); 605563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var strength = Strength.REQUIRED; 606563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark do { 607563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark for (var i = 0; i < unsatisfied.size(); i++) { 608563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var u = unsatisfied.at(i); 609563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if (u.strength == strength) 610563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.incrementalAdd(u); 611563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark } 612563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark strength = strength.nextWeaker(); 613563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark } while (strength != Strength.WEAKEST); 614563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 615563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 616563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark/** 617563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * Select a previously unused mark value. 618563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark */ 619563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkPlanner.prototype.newMark = function () { 620563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark return ++this.currentMark; 621563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 622563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 623563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark/** 624563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * Extract a plan for resatisfaction starting from the given source 625563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * constraints, usually a set of input constraints. This method 626563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * assumes that stay optimization is desired; the plan will contain 627563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * only constraints whose output variables are not stay. Constraints 628563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * that do no computation, such as stay and edit constraints, are 629563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * not included in the plan. 630563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * Details: The outputs of a constraint are marked when it is added 631563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * to the plan under construction. A constraint may be appended to 632563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * the plan when all its input variables are known. A variable is 633563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * known if either a) the variable is marked (indicating that has 634563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * been computed by a constraint appearing earlier in the plan), b) 635563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * the variable is 'stay' (i.e. it is a constant at plan execution 636563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * time), or c) the variable is not determined by any 637563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * constraint. The last provision is for past states of history 638563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * variables, which are not stay but which are also not computed by 639563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * any constraint. 640563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * Assume: sources are all satisfied. 641563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark */ 642563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkPlanner.prototype.makePlan = function (sources) { 643563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var mark = this.newMark(); 644563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var plan = new Plan(); 645563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var todo = sources; 646563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark while (todo.size() > 0) { 647563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var c = todo.removeFirst(); 648563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if (c.output().mark != mark && c.inputsKnown(mark)) { 649563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark plan.addConstraint(c); 650563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark c.output().mark = mark; 651563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.addConstraintsConsumingTo(c.output(), todo); 652563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark } 653563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark } 654563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark return plan; 655563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 656563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 657563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark/** 658563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * Extract a plan for resatisfying starting from the output of the 659563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * given constraints, usually a set of input constraints. 660563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark */ 661563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkPlanner.prototype.extractPlanFromConstraints = function (constraints) { 662563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var sources = new OrderedCollection(); 663563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark for (var i = 0; i < constraints.size(); i++) { 664563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var c = constraints.at(i); 665563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if (c.isInput() && c.isSatisfied()) 666563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark // not in plan already and eligible for inclusion 667563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark sources.add(c); 668563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark } 669563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark return this.makePlan(sources); 670563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 671563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 672563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark/** 673563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * Recompute the walkabout strengths and stay flags of all variables 674563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * downstream of the given constraint and recompute the actual 675563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * values of all variables whose stay flag is true. If a cycle is 676563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * detected, remove the given constraint and answer 677563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * false. Otherwise, answer true. 678563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * Details: Cycles are detected when a marked variable is 679563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * encountered downstream of the given constraint. The sender is 680563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * assumed to have marked the inputs of the given constraint with 681563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * the given mark. Thus, encountering a marked node downstream of 682563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * the output constraint means that there is a path from the 683563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * constraint's output to one of its inputs. 684563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark */ 685563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkPlanner.prototype.addPropagate = function (c, mark) { 686563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var todo = new OrderedCollection(); 687563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark todo.add(c); 688563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark while (todo.size() > 0) { 689563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var d = todo.removeFirst(); 690563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if (d.output().mark == mark) { 691563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.incrementalRemove(c); 692563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark return false; 693563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark } 694563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark d.recalculate(); 695563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.addConstraintsConsumingTo(d.output(), todo); 696563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark } 697563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark return true; 698563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 699563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 700563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 701563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark/** 702563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * Update the walkabout strengths and stay flags of all variables 703563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * downstream of the given constraint. Answer a collection of 704563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * unsatisfied constraints sorted in order of decreasing strength. 705563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark */ 706563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkPlanner.prototype.removePropagateFrom = function (out) { 707563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark out.determinedBy = null; 708563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark out.walkStrength = Strength.WEAKEST; 709563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark out.stay = true; 710563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var unsatisfied = new OrderedCollection(); 711563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var todo = new OrderedCollection(); 712563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark todo.add(out); 713563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark while (todo.size() > 0) { 714563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var v = todo.removeFirst(); 715563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark for (var i = 0; i < v.constraints.size(); i++) { 716563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var c = v.constraints.at(i); 717563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if (!c.isSatisfied()) 718563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark unsatisfied.add(c); 719563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark } 720563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var determining = v.determinedBy; 721563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark for (var i = 0; i < v.constraints.size(); i++) { 722563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var next = v.constraints.at(i); 723563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if (next != determining && next.isSatisfied()) { 724563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark next.recalculate(); 725563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark todo.add(next.output()); 726563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark } 727563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark } 728563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark } 729563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark return unsatisfied; 730563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 731563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 732563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkPlanner.prototype.addConstraintsConsumingTo = function (v, coll) { 733563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var determining = v.determinedBy; 734563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var cc = v.constraints; 735563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark for (var i = 0; i < cc.size(); i++) { 736563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var c = cc.at(i); 737563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if (c != determining && c.isSatisfied()) 738563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark coll.add(c); 739563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark } 740563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 741563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 742563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark/* --- * 743563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * P l a n 744563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * --- */ 745563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 746563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark/** 747563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * A Plan is an ordered list of constraints to be executed in sequence 748563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * to resatisfy all currently satisfiable constraints in the face of 749563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * one or more changing inputs. 750563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark */ 751563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction Plan() { 752563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.v = new OrderedCollection(); 753563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 754563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 755563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkPlan.prototype.addConstraint = function (c) { 756563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.v.add(c); 757563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 758563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 759563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkPlan.prototype.size = function () { 760563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark return this.v.size(); 761563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 762563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 763563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkPlan.prototype.constraintAt = function (index) { 764563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark return this.v.at(index); 765563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 766563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 767563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkPlan.prototype.execute = function () { 768563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark for (var i = 0; i < this.size(); i++) { 769563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var c = this.constraintAt(i); 770563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark c.execute(); 771563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark } 772563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 773563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 774563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark/* --- * 775563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * M a i n 776563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * --- */ 777563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 778563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark/** 779563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * This is the standard DeltaBlue benchmark. A long chain of equality 780563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * constraints is constructed with a stay constraint on one end. An 781563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * edit constraint is then added to the opposite end and the time is 782563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * measured for adding and removing this constraint, and extracting 783563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * and executing a constraint satisfaction plan. There are two cases. 784563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * In case 1, the added constraint is stronger than the stay 785563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * constraint and values must propagate down the entire length of the 786563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * chain. In case 2, the added constraint is weaker than the stay 787563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * constraint so it cannot be accomodated. The cost in this case is, 788563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * of course, very low. Typical situations lie somewhere between these 789563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * two extremes. 790563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark */ 791563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction chainTest(n) { 792563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark planner = new Planner(); 793563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var prev = null, first = null, last = null; 794563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 795563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark // Build chain of n equality constraints 796563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark for (var i = 0; i <= n; i++) { 797563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var name = "v" + i; 798563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var v = new Variable(name); 799563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if (prev != null) 800563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark new EqualityConstraint(prev, v, Strength.REQUIRED); 801563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if (i == 0) first = v; 802563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if (i == n) last = v; 803563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark prev = v; 804563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark } 805563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 806563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark new StayConstraint(last, Strength.STRONG_DEFAULT); 807563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var edit = new EditConstraint(first, Strength.PREFERRED); 808563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var edits = new OrderedCollection(); 809563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark edits.add(edit); 810563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var plan = planner.extractPlanFromConstraints(edits); 811563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark for (var i = 0; i < 100; i++) { 812563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark first.value = i; 813563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark plan.execute(); 814563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if (last.value != i) 815563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark alert("Chain test failed."); 816563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark } 817563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 818563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 819563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark/** 820563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * This test constructs a two sets of variables related to each 821563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * other by a simple linear transformation (scale and offset). The 822563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * time is measured to change a variable on either side of the 823563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * mapping and to change the scale and offset factors. 824563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark */ 825563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction projectionTest(n) { 826563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark planner = new Planner(); 827563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var scale = new Variable("scale", 10); 828563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var offset = new Variable("offset", 1000); 829563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var src = null, dst = null; 830563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 831563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var dests = new OrderedCollection(); 832563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark for (var i = 0; i < n; i++) { 833563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark src = new Variable("src" + i, i); 834563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark dst = new Variable("dst" + i, i); 835563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark dests.add(dst); 836563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark new StayConstraint(src, Strength.NORMAL); 837563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark new ScaleConstraint(src, scale, offset, dst, Strength.REQUIRED); 838563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark } 839563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 840563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark change(src, 17); 841563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if (dst.value != 1170) alert("Projection 1 failed"); 842563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark change(dst, 1050); 843563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if (src.value != 5) alert("Projection 2 failed"); 844563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark change(scale, 5); 845563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark for (var i = 0; i < n - 1; i++) { 846563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if (dests.at(i).value != i * 5 + 1000) 847563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark alert("Projection 3 failed"); 848563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark } 849563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark change(offset, 2000); 850563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark for (var i = 0; i < n - 1; i++) { 851563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if (dests.at(i).value != i * 5 + 2000) 852563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark alert("Projection 4 failed"); 853563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark } 854563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 855563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 856563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction change(v, newValue) { 857563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var edit = new EditConstraint(v, Strength.PREFERRED); 858563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var edits = new OrderedCollection(); 859563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark edits.add(edit); 860563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var plan = planner.extractPlanFromConstraints(edits); 861563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark for (var i = 0; i < 10; i++) { 862563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark v.value = newValue; 863563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark plan.execute(); 864563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark } 865563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark edit.destroyConstraint(); 866563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 867563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 868563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// Global variable holding the current planner. 869563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkvar planner = null; 870563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 871563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction deltaBlue() { 872563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark chainTest(100); 873563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark projectionTest(100); 874563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 875563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 876563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfor (var i = 0; i < 155; ++i) 877563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark deltaBlue(); 878