1a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// Copyright 2008 the V8 project authors. All rights reserved. 2a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// Copyright 1996 John Maloney and Mario Wolczko. 3a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 4a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// This program is free software; you can redistribute it and/or modify 5a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// it under the terms of the GNU General Public License as published by 6a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// the Free Software Foundation; either version 2 of the License, or 7a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// (at your option) any later version. 8a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// 9a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// This program is distributed in the hope that it will be useful, 10a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// but WITHOUT ANY WARRANTY; without even the implied warranty of 11a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 12a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// GNU General Public License for more details. 13a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// 14a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// You should have received a copy of the GNU General Public License 15a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// along with this program; if not, write to the Free Software 16a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA 17a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 18a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 19a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// This implementation of the DeltaBlue benchmark is derived 20a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// from the Smalltalk implementation by John Maloney and Mario 21a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// Wolczko. Some parts have been translated directly, whereas 22a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// others have been modified more aggresively to make it feel 23a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// more like a JavaScript program. 24a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 25a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 260d5e116f6aee03185f237311a943491bb079a768Kristian Monsenvar DeltaBlue = new BenchmarkSuite('DeltaBlue', 66118, [ 27a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block new Benchmark('DeltaBlue', deltaBlue) 28a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block]); 29a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 30a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 31a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block/** 328defd9ff6930b4e24729971a61cf7469daf119beSteve Block * A JavaScript implementation of the DeltaBlue constraint-solving 33a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * algorithm, as described in: 34a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * 35a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * "The DeltaBlue Algorithm: An Incremental Constraint Hierarchy Solver" 36a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * Bjorn N. Freeman-Benson and John Maloney 37a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * January 1990 Communications of the ACM, 38a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * also available as University of Washington TR 89-08-06. 39a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * 40a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * Beware: this benchmark is written in a grotesque style where 41a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * the constraint model is built by side-effects from constructors. 42a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * I've kept it this way to avoid deviating too much from the original 43a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * implementation. 44a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block */ 45a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 46a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 47a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block/* --- O b j e c t M o d e l --- */ 48a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 49a7e24c173cf37484693b9abb38e494fa7bd7baebSteve BlockObject.prototype.inheritsFrom = function (shuper) { 50a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block function Inheriter() { } 51a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block Inheriter.prototype = shuper.prototype; 52a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block this.prototype = new Inheriter(); 53a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block this.superConstructor = shuper; 54a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 55a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 56a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blockfunction OrderedCollection() { 57a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block this.elms = new Array(); 58a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 59a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 60a7e24c173cf37484693b9abb38e494fa7bd7baebSteve BlockOrderedCollection.prototype.add = function (elm) { 61a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block this.elms.push(elm); 62a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 63a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 64a7e24c173cf37484693b9abb38e494fa7bd7baebSteve BlockOrderedCollection.prototype.at = function (index) { 65a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block return this.elms[index]; 66a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 67a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 68a7e24c173cf37484693b9abb38e494fa7bd7baebSteve BlockOrderedCollection.prototype.size = function () { 69a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block return this.elms.length; 70a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 71a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 72a7e24c173cf37484693b9abb38e494fa7bd7baebSteve BlockOrderedCollection.prototype.removeFirst = function () { 73a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block return this.elms.pop(); 74a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 75a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 76a7e24c173cf37484693b9abb38e494fa7bd7baebSteve BlockOrderedCollection.prototype.remove = function (elm) { 77a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var index = 0, skipped = 0; 78a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block for (var i = 0; i < this.elms.length; i++) { 79a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var value = this.elms[i]; 80a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (value != elm) { 81a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block this.elms[index] = value; 82a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block index++; 83a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } else { 84a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block skipped++; 85a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 86a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 87a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block for (var i = 0; i < skipped; i++) 88a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block this.elms.pop(); 89a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 90a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 91a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block/* --- * 92a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * S t r e n g t h 93a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * --- */ 94a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 95a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block/** 96a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * Strengths are used to measure the relative importance of constraints. 97a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * New strengths may be inserted in the strength hierarchy without 98a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * disrupting current constraints. Strengths cannot be created outside 99a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * this class, so pointer comparison can be used for value comparison. 100a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block */ 101a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blockfunction Strength(strengthValue, name) { 102a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block this.strengthValue = strengthValue; 103a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block this.name = name; 104a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 105a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 106a7e24c173cf37484693b9abb38e494fa7bd7baebSteve BlockStrength.stronger = function (s1, s2) { 107a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block return s1.strengthValue < s2.strengthValue; 108a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 109a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 110a7e24c173cf37484693b9abb38e494fa7bd7baebSteve BlockStrength.weaker = function (s1, s2) { 111a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block return s1.strengthValue > s2.strengthValue; 112a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 113a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 114a7e24c173cf37484693b9abb38e494fa7bd7baebSteve BlockStrength.weakestOf = function (s1, s2) { 115a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block return this.weaker(s1, s2) ? s1 : s2; 116a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 117a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 118a7e24c173cf37484693b9abb38e494fa7bd7baebSteve BlockStrength.strongest = function (s1, s2) { 119a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block return this.stronger(s1, s2) ? s1 : s2; 120a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 121a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 122a7e24c173cf37484693b9abb38e494fa7bd7baebSteve BlockStrength.prototype.nextWeaker = function () { 123a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block switch (this.strengthValue) { 124a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block case 0: return Strength.WEAKEST; 125a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block case 1: return Strength.WEAK_DEFAULT; 126a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block case 2: return Strength.NORMAL; 127a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block case 3: return Strength.STRONG_DEFAULT; 128a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block case 4: return Strength.PREFERRED; 129a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block case 5: return Strength.REQUIRED; 130a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 131a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 132a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 133a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// Strength constants. 134a7e24c173cf37484693b9abb38e494fa7bd7baebSteve BlockStrength.REQUIRED = new Strength(0, "required"); 135a7e24c173cf37484693b9abb38e494fa7bd7baebSteve BlockStrength.STONG_PREFERRED = new Strength(1, "strongPreferred"); 136a7e24c173cf37484693b9abb38e494fa7bd7baebSteve BlockStrength.PREFERRED = new Strength(2, "preferred"); 137a7e24c173cf37484693b9abb38e494fa7bd7baebSteve BlockStrength.STRONG_DEFAULT = new Strength(3, "strongDefault"); 138a7e24c173cf37484693b9abb38e494fa7bd7baebSteve BlockStrength.NORMAL = new Strength(4, "normal"); 139a7e24c173cf37484693b9abb38e494fa7bd7baebSteve BlockStrength.WEAK_DEFAULT = new Strength(5, "weakDefault"); 140a7e24c173cf37484693b9abb38e494fa7bd7baebSteve BlockStrength.WEAKEST = new Strength(6, "weakest"); 141a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 142a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block/* --- * 143a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * C o n s t r a i n t 144a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * --- */ 145a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 146a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block/** 147a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * An abstract class representing a system-maintainable relationship 148a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * (or "constraint") between a set of variables. A constraint supplies 149a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * a strength instance variable; concrete subclasses provide a means 150a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * of storing the constrained variables and other information required 151a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * to represent a constraint. 152a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block */ 153a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blockfunction Constraint(strength) { 154a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block this.strength = strength; 155a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 156a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 157a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block/** 158a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * Activate this constraint and attempt to satisfy it. 159a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block */ 160a7e24c173cf37484693b9abb38e494fa7bd7baebSteve BlockConstraint.prototype.addConstraint = function () { 161a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block this.addToGraph(); 162a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block planner.incrementalAdd(this); 163a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 164a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 165a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block/** 166a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * Attempt to find a way to enforce this constraint. If successful, 167a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * record the solution, perhaps modifying the current dataflow 168a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * graph. Answer the constraint that this constraint overrides, if 169a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * there is one, or nil, if there isn't. 170a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * Assume: I am not already satisfied. 171a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block */ 172a7e24c173cf37484693b9abb38e494fa7bd7baebSteve BlockConstraint.prototype.satisfy = function (mark) { 173a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block this.chooseMethod(mark); 174a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (!this.isSatisfied()) { 175a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (this.strength == Strength.REQUIRED) 176a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block alert("Could not satisfy a required constraint!"); 177a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block return null; 178a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 179a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block this.markInputs(mark); 180a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var out = this.output(); 181a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var overridden = out.determinedBy; 182a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (overridden != null) overridden.markUnsatisfied(); 183a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block out.determinedBy = this; 184a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (!planner.addPropagate(this, mark)) 185a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block alert("Cycle encountered"); 186a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block out.mark = mark; 187a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block return overridden; 188a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 189a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 190a7e24c173cf37484693b9abb38e494fa7bd7baebSteve BlockConstraint.prototype.destroyConstraint = function () { 191a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (this.isSatisfied()) planner.incrementalRemove(this); 192a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block else this.removeFromGraph(); 193a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 194a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 195a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block/** 196a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * Normal constraints are not input constraints. An input constraint 197a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * is one that depends on external state, such as the mouse, the 198a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * keybord, a clock, or some arbitraty piece of imperative code. 199a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block */ 200a7e24c173cf37484693b9abb38e494fa7bd7baebSteve BlockConstraint.prototype.isInput = function () { 201a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block return false; 202a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 203a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 204a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block/* --- * 205a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * U n a r y C o n s t r a i n t 206a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * --- */ 207a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 208a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block/** 209a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * Abstract superclass for constraints having a single possible output 210a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * variable. 211a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block */ 212a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blockfunction UnaryConstraint(v, strength) { 213a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block UnaryConstraint.superConstructor.call(this, strength); 214a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block this.myOutput = v; 215a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block this.satisfied = false; 216a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block this.addConstraint(); 217a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 218a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 219a7e24c173cf37484693b9abb38e494fa7bd7baebSteve BlockUnaryConstraint.inheritsFrom(Constraint); 220a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 221a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block/** 222a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * Adds this constraint to the constraint graph 223a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block */ 224a7e24c173cf37484693b9abb38e494fa7bd7baebSteve BlockUnaryConstraint.prototype.addToGraph = function () { 225a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block this.myOutput.addConstraint(this); 226a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block this.satisfied = false; 227a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 228a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 229a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block/** 230a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * Decides if this constraint can be satisfied and records that 231a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * decision. 232a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block */ 233a7e24c173cf37484693b9abb38e494fa7bd7baebSteve BlockUnaryConstraint.prototype.chooseMethod = function (mark) { 234a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block this.satisfied = (this.myOutput.mark != mark) 235a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block && Strength.stronger(this.strength, this.myOutput.walkStrength); 236a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 237a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 238a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block/** 239a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * Returns true if this constraint is satisfied in the current solution. 240a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block */ 241a7e24c173cf37484693b9abb38e494fa7bd7baebSteve BlockUnaryConstraint.prototype.isSatisfied = function () { 242a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block return this.satisfied; 243a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 244a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 245a7e24c173cf37484693b9abb38e494fa7bd7baebSteve BlockUnaryConstraint.prototype.markInputs = function (mark) { 246a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // has no inputs 247a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 248a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 249a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block/** 250a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * Returns the current output variable. 251a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block */ 252a7e24c173cf37484693b9abb38e494fa7bd7baebSteve BlockUnaryConstraint.prototype.output = function () { 253a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block return this.myOutput; 254a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 255a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 256a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block/** 257a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * Calculate the walkabout strength, the stay flag, and, if it is 258a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * 'stay', the value for the current output of this constraint. Assume 259a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * this constraint is satisfied. 260a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block */ 261a7e24c173cf37484693b9abb38e494fa7bd7baebSteve BlockUnaryConstraint.prototype.recalculate = function () { 262a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block this.myOutput.walkStrength = this.strength; 263a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block this.myOutput.stay = !this.isInput(); 264a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (this.myOutput.stay) this.execute(); // Stay optimization 265a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 266a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 267a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block/** 268a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * Records that this constraint is unsatisfied 269a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block */ 270a7e24c173cf37484693b9abb38e494fa7bd7baebSteve BlockUnaryConstraint.prototype.markUnsatisfied = function () { 271a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block this.satisfied = false; 272a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 273a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 274a7e24c173cf37484693b9abb38e494fa7bd7baebSteve BlockUnaryConstraint.prototype.inputsKnown = function () { 275a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block return true; 276a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 277a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 278a7e24c173cf37484693b9abb38e494fa7bd7baebSteve BlockUnaryConstraint.prototype.removeFromGraph = function () { 279a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (this.myOutput != null) this.myOutput.removeConstraint(this); 280a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block this.satisfied = false; 281a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 282a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 283a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block/* --- * 284a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * S t a y C o n s t r a i n t 285a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * --- */ 286a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 287a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block/** 288a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * Variables that should, with some level of preference, stay the same. 289a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * Planners may exploit the fact that instances, if satisfied, will not 290a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * change their output during plan execution. This is called "stay 291a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * optimization". 292a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block */ 293a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blockfunction StayConstraint(v, str) { 294a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block StayConstraint.superConstructor.call(this, v, str); 295a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 296a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 297a7e24c173cf37484693b9abb38e494fa7bd7baebSteve BlockStayConstraint.inheritsFrom(UnaryConstraint); 298a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 299a7e24c173cf37484693b9abb38e494fa7bd7baebSteve BlockStayConstraint.prototype.execute = function () { 300a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // Stay constraints do nothing 301a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 302a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 303a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block/* --- * 304a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * E d i t C o n s t r a i n t 305a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * --- */ 306a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 307a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block/** 308a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * A unary input constraint used to mark a variable that the client 309a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * wishes to change. 310a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block */ 311a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blockfunction EditConstraint(v, str) { 312a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block EditConstraint.superConstructor.call(this, v, str); 313a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 314a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 315a7e24c173cf37484693b9abb38e494fa7bd7baebSteve BlockEditConstraint.inheritsFrom(UnaryConstraint); 316a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 317a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block/** 318a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * Edits indicate that a variable is to be changed by imperative code. 319a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block */ 320a7e24c173cf37484693b9abb38e494fa7bd7baebSteve BlockEditConstraint.prototype.isInput = function () { 321a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block return true; 322a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 323a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 324a7e24c173cf37484693b9abb38e494fa7bd7baebSteve BlockEditConstraint.prototype.execute = function () { 325a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // Edit constraints do nothing 326a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 327a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 328a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block/* --- * 329a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * B i n a r y C o n s t r a i n t 330a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * --- */ 331a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 332a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blockvar Direction = new Object(); 333a7e24c173cf37484693b9abb38e494fa7bd7baebSteve BlockDirection.NONE = 0; 334a7e24c173cf37484693b9abb38e494fa7bd7baebSteve BlockDirection.FORWARD = 1; 335a7e24c173cf37484693b9abb38e494fa7bd7baebSteve BlockDirection.BACKWARD = -1; 336a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 337a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block/** 338a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * Abstract superclass for constraints having two possible output 339a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * variables. 340a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block */ 341a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blockfunction BinaryConstraint(var1, var2, strength) { 342a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block BinaryConstraint.superConstructor.call(this, strength); 343a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block this.v1 = var1; 344a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block this.v2 = var2; 345a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block this.direction = Direction.NONE; 346a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block this.addConstraint(); 347a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 348a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 349a7e24c173cf37484693b9abb38e494fa7bd7baebSteve BlockBinaryConstraint.inheritsFrom(Constraint); 350a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 351a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block/** 3528defd9ff6930b4e24729971a61cf7469daf119beSteve Block * Decides if this constraint can be satisfied and which way it 353a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * should flow based on the relative strength of the variables related, 354a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * and record that decision. 355a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block */ 356a7e24c173cf37484693b9abb38e494fa7bd7baebSteve BlockBinaryConstraint.prototype.chooseMethod = function (mark) { 357a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (this.v1.mark == mark) { 3588defd9ff6930b4e24729971a61cf7469daf119beSteve Block this.direction = (this.v2.mark != mark && Strength.stronger(this.strength, this.v2.walkStrength)) 359a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block ? Direction.FORWARD 360a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block : Direction.NONE; 361a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 362a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (this.v2.mark == mark) { 363a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block this.direction = (this.v1.mark != mark && Strength.stronger(this.strength, this.v1.walkStrength)) 364a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block ? Direction.BACKWARD 365a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block : Direction.NONE; 366a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 367a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (Strength.weaker(this.v1.walkStrength, this.v2.walkStrength)) { 368a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block this.direction = Strength.stronger(this.strength, this.v1.walkStrength) 369a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block ? Direction.BACKWARD 370a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block : Direction.NONE; 371a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } else { 372a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block this.direction = Strength.stronger(this.strength, this.v2.walkStrength) 373a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block ? Direction.FORWARD 374a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block : Direction.BACKWARD 375a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 376a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 377a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 378a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block/** 379a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * Add this constraint to the constraint graph 380a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block */ 381a7e24c173cf37484693b9abb38e494fa7bd7baebSteve BlockBinaryConstraint.prototype.addToGraph = function () { 382a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block this.v1.addConstraint(this); 383a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block this.v2.addConstraint(this); 384a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block this.direction = Direction.NONE; 385a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 386a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 387a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block/** 388a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * Answer true if this constraint is satisfied in the current solution. 389a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block */ 390a7e24c173cf37484693b9abb38e494fa7bd7baebSteve BlockBinaryConstraint.prototype.isSatisfied = function () { 391a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block return this.direction != Direction.NONE; 392a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 393a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 394a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block/** 395a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * Mark the input variable with the given mark. 396a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block */ 397a7e24c173cf37484693b9abb38e494fa7bd7baebSteve BlockBinaryConstraint.prototype.markInputs = function (mark) { 398a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block this.input().mark = mark; 399a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 400a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 401a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block/** 402a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * Returns the current input variable 403a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block */ 404a7e24c173cf37484693b9abb38e494fa7bd7baebSteve BlockBinaryConstraint.prototype.input = function () { 405a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block return (this.direction == Direction.FORWARD) ? this.v1 : this.v2; 406a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 407a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 408a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block/** 409a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * Returns the current output variable 410a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block */ 411a7e24c173cf37484693b9abb38e494fa7bd7baebSteve BlockBinaryConstraint.prototype.output = function () { 412a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block return (this.direction == Direction.FORWARD) ? this.v2 : this.v1; 413a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 414a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 415a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block/** 416a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * Calculate the walkabout strength, the stay flag, and, if it is 417a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * 'stay', the value for the current output of this 418a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * constraint. Assume this constraint is satisfied. 419a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block */ 420a7e24c173cf37484693b9abb38e494fa7bd7baebSteve BlockBinaryConstraint.prototype.recalculate = function () { 421a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var ihn = this.input(), out = this.output(); 422a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block out.walkStrength = Strength.weakestOf(this.strength, ihn.walkStrength); 423a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block out.stay = ihn.stay; 424a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (out.stay) this.execute(); 425a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 426a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 427a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block/** 428a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * Record the fact that this constraint is unsatisfied. 429a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block */ 430a7e24c173cf37484693b9abb38e494fa7bd7baebSteve BlockBinaryConstraint.prototype.markUnsatisfied = function () { 431a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block this.direction = Direction.NONE; 432a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 433a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 434a7e24c173cf37484693b9abb38e494fa7bd7baebSteve BlockBinaryConstraint.prototype.inputsKnown = function (mark) { 435a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var i = this.input(); 436a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block return i.mark == mark || i.stay || i.determinedBy == null; 437a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 438a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 439a7e24c173cf37484693b9abb38e494fa7bd7baebSteve BlockBinaryConstraint.prototype.removeFromGraph = function () { 440a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (this.v1 != null) this.v1.removeConstraint(this); 441a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (this.v2 != null) this.v2.removeConstraint(this); 442a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block this.direction = Direction.NONE; 443a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 444a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 445a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block/* --- * 446a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * S c a l e C o n s t r a i n t 447a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * --- */ 448a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 449a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block/** 450a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * Relates two variables by the linear scaling relationship: "v2 = 451a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * (v1 * scale) + offset". Either v1 or v2 may be changed to maintain 452a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * this relationship but the scale factor and offset are considered 453a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * read-only. 454a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block */ 455a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blockfunction ScaleConstraint(src, scale, offset, dest, strength) { 456a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block this.direction = Direction.NONE; 457a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block this.scale = scale; 458a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block this.offset = offset; 459a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block ScaleConstraint.superConstructor.call(this, src, dest, strength); 460a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 461a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 462a7e24c173cf37484693b9abb38e494fa7bd7baebSteve BlockScaleConstraint.inheritsFrom(BinaryConstraint); 463a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 464a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block/** 465a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * Adds this constraint to the constraint graph. 466a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block */ 467a7e24c173cf37484693b9abb38e494fa7bd7baebSteve BlockScaleConstraint.prototype.addToGraph = function () { 468a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block ScaleConstraint.superConstructor.prototype.addToGraph.call(this); 469a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block this.scale.addConstraint(this); 470a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block this.offset.addConstraint(this); 471a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 472a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 473a7e24c173cf37484693b9abb38e494fa7bd7baebSteve BlockScaleConstraint.prototype.removeFromGraph = function () { 474a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block ScaleConstraint.superConstructor.prototype.removeFromGraph.call(this); 475a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (this.scale != null) this.scale.removeConstraint(this); 476a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (this.offset != null) this.offset.removeConstraint(this); 477a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 478a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 479a7e24c173cf37484693b9abb38e494fa7bd7baebSteve BlockScaleConstraint.prototype.markInputs = function (mark) { 480a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block ScaleConstraint.superConstructor.prototype.markInputs.call(this, mark); 481a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block this.scale.mark = this.offset.mark = mark; 482a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 483a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 484a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block/** 485a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * Enforce this constraint. Assume that it is satisfied. 486a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block */ 487a7e24c173cf37484693b9abb38e494fa7bd7baebSteve BlockScaleConstraint.prototype.execute = function () { 488a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (this.direction == Direction.FORWARD) { 489a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block this.v2.value = this.v1.value * this.scale.value + this.offset.value; 490a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } else { 491a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block this.v1.value = (this.v2.value - this.offset.value) / this.scale.value; 492a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 493a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 494a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 495a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block/** 496a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * Calculate the walkabout strength, the stay flag, and, if it is 497a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * 'stay', the value for the current output of this constraint. Assume 498a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * this constraint is satisfied. 499a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block */ 500a7e24c173cf37484693b9abb38e494fa7bd7baebSteve BlockScaleConstraint.prototype.recalculate = function () { 501a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var ihn = this.input(), out = this.output(); 502a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block out.walkStrength = Strength.weakestOf(this.strength, ihn.walkStrength); 503a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block out.stay = ihn.stay && this.scale.stay && this.offset.stay; 504a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (out.stay) this.execute(); 505a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 506a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 507a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block/* --- * 508a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * E q u a l i t y C o n s t r a i n t 509a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * --- */ 510a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 511a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block/** 512a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * Constrains two variables to have the same value. 513a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block */ 514a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blockfunction EqualityConstraint(var1, var2, strength) { 515a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block EqualityConstraint.superConstructor.call(this, var1, var2, strength); 516a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 517a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 518a7e24c173cf37484693b9abb38e494fa7bd7baebSteve BlockEqualityConstraint.inheritsFrom(BinaryConstraint); 519a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 520a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block/** 521a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * Enforce this constraint. Assume that it is satisfied. 522a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block */ 523a7e24c173cf37484693b9abb38e494fa7bd7baebSteve BlockEqualityConstraint.prototype.execute = function () { 524a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block this.output().value = this.input().value; 525a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 526a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 527a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block/* --- * 528a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * V a r i a b l e 529a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * --- */ 530a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 531a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block/** 532a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * A constrained variable. In addition to its value, it maintain the 533a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * structure of the constraint graph, the current dataflow graph, and 534a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * various parameters of interest to the DeltaBlue incremental 535a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * constraint solver. 536a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block **/ 537a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blockfunction Variable(name, initialValue) { 538a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block this.value = initialValue || 0; 539a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block this.constraints = new OrderedCollection(); 540a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block this.determinedBy = null; 541a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block this.mark = 0; 542a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block this.walkStrength = Strength.WEAKEST; 543a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block this.stay = true; 544a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block this.name = name; 545a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 546a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 547a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block/** 548a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * Add the given constraint to the set of all constraints that refer 549a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * this variable. 550a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block */ 551a7e24c173cf37484693b9abb38e494fa7bd7baebSteve BlockVariable.prototype.addConstraint = function (c) { 552a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block this.constraints.add(c); 553a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 554a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 555a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block/** 556a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * Removes all traces of c from this variable. 557a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block */ 558a7e24c173cf37484693b9abb38e494fa7bd7baebSteve BlockVariable.prototype.removeConstraint = function (c) { 559a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block this.constraints.remove(c); 560a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (this.determinedBy == c) this.determinedBy = null; 561a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 562a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 563a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block/* --- * 564a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * P l a n n e r 565a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * --- */ 566a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 567a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block/** 568a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * The DeltaBlue planner 569a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block */ 570a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blockfunction Planner() { 571a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block this.currentMark = 0; 572a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 573a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 574a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block/** 575a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * Attempt to satisfy the given constraint and, if successful, 576a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * incrementally update the dataflow graph. Details: If satifying 577a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * the constraint is successful, it may override a weaker constraint 578a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * on its output. The algorithm attempts to resatisfy that 579a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * constraint using some other method. This process is repeated 580a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * until either a) it reaches a variable that was not previously 581a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * determined by any constraint or b) it reaches a constraint that 582a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * is too weak to be satisfied using any of its methods. The 583a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * variables of constraints that have been processed are marked with 584a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * a unique mark value so that we know where we've been. This allows 585a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * the algorithm to avoid getting into an infinite loop even if the 586a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * constraint graph has an inadvertent cycle. 587a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block */ 588a7e24c173cf37484693b9abb38e494fa7bd7baebSteve BlockPlanner.prototype.incrementalAdd = function (c) { 589a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var mark = this.newMark(); 590a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var overridden = c.satisfy(mark); 591a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block while (overridden != null) 592a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block overridden = overridden.satisfy(mark); 593a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 594a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 595a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block/** 596a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * Entry point for retracting a constraint. Remove the given 597a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * constraint and incrementally update the dataflow graph. 598a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * Details: Retracting the given constraint may allow some currently 599a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * unsatisfiable downstream constraint to be satisfied. We therefore collect 600a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * a list of unsatisfied downstream constraints and attempt to 601a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * satisfy each one in turn. This list is traversed by constraint 602a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * strength, strongest first, as a heuristic for avoiding 603a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * unnecessarily adding and then overriding weak constraints. 604a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * Assume: c is satisfied. 605a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block */ 606a7e24c173cf37484693b9abb38e494fa7bd7baebSteve BlockPlanner.prototype.incrementalRemove = function (c) { 607a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var out = c.output(); 608a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block c.markUnsatisfied(); 609a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block c.removeFromGraph(); 610a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var unsatisfied = this.removePropagateFrom(out); 611a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var strength = Strength.REQUIRED; 612a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block do { 613a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block for (var i = 0; i < unsatisfied.size(); i++) { 614a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var u = unsatisfied.at(i); 615a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (u.strength == strength) 616a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block this.incrementalAdd(u); 617a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 618a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block strength = strength.nextWeaker(); 619a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } while (strength != Strength.WEAKEST); 620a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 621a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 622a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block/** 623a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * Select a previously unused mark value. 624a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block */ 625a7e24c173cf37484693b9abb38e494fa7bd7baebSteve BlockPlanner.prototype.newMark = function () { 626a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block return ++this.currentMark; 627a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 628a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 629a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block/** 630a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * Extract a plan for resatisfaction starting from the given source 631a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * constraints, usually a set of input constraints. This method 632a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * assumes that stay optimization is desired; the plan will contain 633a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * only constraints whose output variables are not stay. Constraints 634a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * that do no computation, such as stay and edit constraints, are 635a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * not included in the plan. 636a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * Details: The outputs of a constraint are marked when it is added 637a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * to the plan under construction. A constraint may be appended to 638a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * the plan when all its input variables are known. A variable is 639a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * known if either a) the variable is marked (indicating that has 640a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * been computed by a constraint appearing earlier in the plan), b) 641a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * the variable is 'stay' (i.e. it is a constant at plan execution 642a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * time), or c) the variable is not determined by any 643a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * constraint. The last provision is for past states of history 644a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * variables, which are not stay but which are also not computed by 645a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * any constraint. 646a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * Assume: sources are all satisfied. 647a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block */ 648a7e24c173cf37484693b9abb38e494fa7bd7baebSteve BlockPlanner.prototype.makePlan = function (sources) { 649a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var mark = this.newMark(); 650a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var plan = new Plan(); 651a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var todo = sources; 652a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block while (todo.size() > 0) { 653a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var c = todo.removeFirst(); 654a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (c.output().mark != mark && c.inputsKnown(mark)) { 655a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block plan.addConstraint(c); 656a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block c.output().mark = mark; 657a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block this.addConstraintsConsumingTo(c.output(), todo); 658a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 659a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 660a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block return plan; 661a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 662a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 663a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block/** 664a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * Extract a plan for resatisfying starting from the output of the 665a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * given constraints, usually a set of input constraints. 666a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block */ 667a7e24c173cf37484693b9abb38e494fa7bd7baebSteve BlockPlanner.prototype.extractPlanFromConstraints = function (constraints) { 668a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var sources = new OrderedCollection(); 669a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block for (var i = 0; i < constraints.size(); i++) { 670a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var c = constraints.at(i); 671a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (c.isInput() && c.isSatisfied()) 672a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // not in plan already and eligible for inclusion 673a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block sources.add(c); 674a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 675a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block return this.makePlan(sources); 676a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 677a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 678a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block/** 679a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * Recompute the walkabout strengths and stay flags of all variables 680a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * downstream of the given constraint and recompute the actual 681a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * values of all variables whose stay flag is true. If a cycle is 682a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * detected, remove the given constraint and answer 683a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * false. Otherwise, answer true. 684a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * Details: Cycles are detected when a marked variable is 685a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * encountered downstream of the given constraint. The sender is 686a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * assumed to have marked the inputs of the given constraint with 687a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * the given mark. Thus, encountering a marked node downstream of 688a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * the output constraint means that there is a path from the 689a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * constraint's output to one of its inputs. 690a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block */ 691a7e24c173cf37484693b9abb38e494fa7bd7baebSteve BlockPlanner.prototype.addPropagate = function (c, mark) { 692a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var todo = new OrderedCollection(); 693a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block todo.add(c); 694a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block while (todo.size() > 0) { 695a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var d = todo.removeFirst(); 696a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (d.output().mark == mark) { 697a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block this.incrementalRemove(c); 698a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block return false; 699a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 700a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block d.recalculate(); 701a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block this.addConstraintsConsumingTo(d.output(), todo); 702a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 703a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block return true; 704a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 705a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 706a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 707a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block/** 708a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * Update the walkabout strengths and stay flags of all variables 709a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * downstream of the given constraint. Answer a collection of 710a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * unsatisfied constraints sorted in order of decreasing strength. 711a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block */ 712a7e24c173cf37484693b9abb38e494fa7bd7baebSteve BlockPlanner.prototype.removePropagateFrom = function (out) { 713a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block out.determinedBy = null; 714a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block out.walkStrength = Strength.WEAKEST; 715a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block out.stay = true; 716a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var unsatisfied = new OrderedCollection(); 717a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var todo = new OrderedCollection(); 718a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block todo.add(out); 719a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block while (todo.size() > 0) { 720a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var v = todo.removeFirst(); 721a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block for (var i = 0; i < v.constraints.size(); i++) { 722a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var c = v.constraints.at(i); 723a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (!c.isSatisfied()) 724a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block unsatisfied.add(c); 725a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 726a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var determining = v.determinedBy; 727a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block for (var i = 0; i < v.constraints.size(); i++) { 728a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var next = v.constraints.at(i); 729a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (next != determining && next.isSatisfied()) { 730a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block next.recalculate(); 731a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block todo.add(next.output()); 732a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 733a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 734a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 735a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block return unsatisfied; 736a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 737a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 738a7e24c173cf37484693b9abb38e494fa7bd7baebSteve BlockPlanner.prototype.addConstraintsConsumingTo = function (v, coll) { 739a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var determining = v.determinedBy; 740a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var cc = v.constraints; 741a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block for (var i = 0; i < cc.size(); i++) { 742a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var c = cc.at(i); 743a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (c != determining && c.isSatisfied()) 744a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block coll.add(c); 745a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 746a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 747a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 748a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block/* --- * 749a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * P l a n 750a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * --- */ 751a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 752a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block/** 753a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * A Plan is an ordered list of constraints to be executed in sequence 754a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * to resatisfy all currently satisfiable constraints in the face of 755a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * one or more changing inputs. 756a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block */ 757a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blockfunction Plan() { 758a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block this.v = new OrderedCollection(); 759a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 760a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 761a7e24c173cf37484693b9abb38e494fa7bd7baebSteve BlockPlan.prototype.addConstraint = function (c) { 762a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block this.v.add(c); 763a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 764a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 765a7e24c173cf37484693b9abb38e494fa7bd7baebSteve BlockPlan.prototype.size = function () { 766a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block return this.v.size(); 767a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 768a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 769a7e24c173cf37484693b9abb38e494fa7bd7baebSteve BlockPlan.prototype.constraintAt = function (index) { 770a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block return this.v.at(index); 771a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 772a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 773a7e24c173cf37484693b9abb38e494fa7bd7baebSteve BlockPlan.prototype.execute = function () { 774a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block for (var i = 0; i < this.size(); i++) { 775a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var c = this.constraintAt(i); 776a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block c.execute(); 777a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 778a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 779a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 780a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block/* --- * 781a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * M a i n 782a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * --- */ 783a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 784a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block/** 785a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * This is the standard DeltaBlue benchmark. A long chain of equality 786a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * constraints is constructed with a stay constraint on one end. An 787a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * edit constraint is then added to the opposite end and the time is 788a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * measured for adding and removing this constraint, and extracting 789a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * and executing a constraint satisfaction plan. There are two cases. 790a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * In case 1, the added constraint is stronger than the stay 791a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * constraint and values must propagate down the entire length of the 792a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * chain. In case 2, the added constraint is weaker than the stay 793a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * constraint so it cannot be accomodated. The cost in this case is, 794a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * of course, very low. Typical situations lie somewhere between these 795a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * two extremes. 796a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block */ 797a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blockfunction chainTest(n) { 798a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block planner = new Planner(); 799a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var prev = null, first = null, last = null; 800a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 801a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block // Build chain of n equality constraints 802a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block for (var i = 0; i <= n; i++) { 803a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var name = "v" + i; 804a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var v = new Variable(name); 805a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (prev != null) 806a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block new EqualityConstraint(prev, v, Strength.REQUIRED); 807a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (i == 0) first = v; 808a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (i == n) last = v; 809a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block prev = v; 810a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 811a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 812a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block new StayConstraint(last, Strength.STRONG_DEFAULT); 813a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var edit = new EditConstraint(first, Strength.PREFERRED); 814a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var edits = new OrderedCollection(); 815a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block edits.add(edit); 816a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var plan = planner.extractPlanFromConstraints(edits); 817a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block for (var i = 0; i < 100; i++) { 818a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block first.value = i; 819a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block plan.execute(); 820a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (last.value != i) 821a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block alert("Chain test failed."); 822a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 823a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 824a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 825a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block/** 826a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * This test constructs a two sets of variables related to each 827a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * other by a simple linear transformation (scale and offset). The 828a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * time is measured to change a variable on either side of the 829a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block * mapping and to change the scale and offset factors. 830a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block */ 831a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blockfunction projectionTest(n) { 832a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block planner = new Planner(); 833a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var scale = new Variable("scale", 10); 834a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var offset = new Variable("offset", 1000); 835a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var src = null, dst = null; 836a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 837a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var dests = new OrderedCollection(); 838a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block for (var i = 0; i < n; i++) { 839a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block src = new Variable("src" + i, i); 840a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block dst = new Variable("dst" + i, i); 841a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block dests.add(dst); 842a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block new StayConstraint(src, Strength.NORMAL); 843a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block new ScaleConstraint(src, scale, offset, dst, Strength.REQUIRED); 844a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 845a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 846a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block change(src, 17); 847a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (dst.value != 1170) alert("Projection 1 failed"); 848a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block change(dst, 1050); 849a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (src.value != 5) alert("Projection 2 failed"); 850a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block change(scale, 5); 851a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block for (var i = 0; i < n - 1; i++) { 852a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (dests.at(i).value != i * 5 + 1000) 853a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block alert("Projection 3 failed"); 854a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 855a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block change(offset, 2000); 856a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block for (var i = 0; i < n - 1; i++) { 857a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block if (dests.at(i).value != i * 5 + 2000) 858a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block alert("Projection 4 failed"); 859a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 860a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 861a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 862a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blockfunction change(v, newValue) { 863a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var edit = new EditConstraint(v, Strength.PREFERRED); 864a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var edits = new OrderedCollection(); 865a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block edits.add(edit); 866a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block var plan = planner.extractPlanFromConstraints(edits); 867a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block for (var i = 0; i < 10; i++) { 868a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block v.value = newValue; 869a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block plan.execute(); 870a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block } 871a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block edit.destroyConstraint(); 872a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 873a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 874a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block// Global variable holding the current planner. 875a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blockvar planner = null; 876a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block 877a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Blockfunction deltaBlue() { 878a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block chainTest(100); 879a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block projectionTest(100); 880a7e24c173cf37484693b9abb38e494fa7bd7baebSteve Block} 881