19258b6bc66e09368ada54001f619d53b4fc976d5ager@chromium.org// Copyright 2008 the V8 project authors. All rights reserved. 2727e995b7bba3c57fb1e5c156d386ca11894f781v// Copyright 1996 John Maloney and Mario Wolczko. 3727e995b7bba3c57fb1e5c156d386ca11894f781v 4727e995b7bba3c57fb1e5c156d386ca11894f781v// This program is free software; you can redistribute it and/or modify 5727e995b7bba3c57fb1e5c156d386ca11894f781v// it under the terms of the GNU General Public License as published by 6727e995b7bba3c57fb1e5c156d386ca11894f781v// the Free Software Foundation; either version 2 of the License, or 7727e995b7bba3c57fb1e5c156d386ca11894f781v// (at your option) any later version. 8727e995b7bba3c57fb1e5c156d386ca11894f781v// 9727e995b7bba3c57fb1e5c156d386ca11894f781v// This program is distributed in the hope that it will be useful, 10727e995b7bba3c57fb1e5c156d386ca11894f781v// but WITHOUT ANY WARRANTY; without even the implied warranty of 11727e995b7bba3c57fb1e5c156d386ca11894f781v// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 12727e995b7bba3c57fb1e5c156d386ca11894f781v// GNU General Public License for more details. 13727e995b7bba3c57fb1e5c156d386ca11894f781v// 14727e995b7bba3c57fb1e5c156d386ca11894f781v// You should have received a copy of the GNU General Public License 15727e995b7bba3c57fb1e5c156d386ca11894f781v// along with this program; if not, write to the Free Software 16727e995b7bba3c57fb1e5c156d386ca11894f781v// Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA 17727e995b7bba3c57fb1e5c156d386ca11894f781v 18727e995b7bba3c57fb1e5c156d386ca11894f781v 19b3284ad36ee358a35b81379ad1c449e4f8021362kasperl@chromium.org// This implementation of the DeltaBlue benchmark is derived 20b3284ad36ee358a35b81379ad1c449e4f8021362kasperl@chromium.org// from the Smalltalk implementation by John Maloney and Mario 21b3284ad36ee358a35b81379ad1c449e4f8021362kasperl@chromium.org// Wolczko. Some parts have been translated directly, whereas 22b3284ad36ee358a35b81379ad1c449e4f8021362kasperl@chromium.org// others have been modified more aggresively to make it feel 23727e995b7bba3c57fb1e5c156d386ca11894f781v// more like a JavaScript program. 24727e995b7bba3c57fb1e5c156d386ca11894f781v 25727e995b7bba3c57fb1e5c156d386ca11894f781v 26d88afa260e45de10e729b05a20146184a488aff7erik.corry@gmail.comvar DeltaBlue = new BenchmarkSuite('DeltaBlue', 66118, [ 27727e995b7bba3c57fb1e5c156d386ca11894f781v new Benchmark('DeltaBlue', deltaBlue) 28727e995b7bba3c57fb1e5c156d386ca11894f781v]); 29727e995b7bba3c57fb1e5c156d386ca11894f781v 30727e995b7bba3c57fb1e5c156d386ca11894f781v 31727e995b7bba3c57fb1e5c156d386ca11894f781v/** 3232d961d4454609ab4251a760fc46b19f661da90clrn@chromium.org * A JavaScript implementation of the DeltaBlue constraint-solving 33727e995b7bba3c57fb1e5c156d386ca11894f781v * algorithm, as described in: 34727e995b7bba3c57fb1e5c156d386ca11894f781v * 35727e995b7bba3c57fb1e5c156d386ca11894f781v * "The DeltaBlue Algorithm: An Incremental Constraint Hierarchy Solver" 36727e995b7bba3c57fb1e5c156d386ca11894f781v * Bjorn N. Freeman-Benson and John Maloney 37727e995b7bba3c57fb1e5c156d386ca11894f781v * January 1990 Communications of the ACM, 38727e995b7bba3c57fb1e5c156d386ca11894f781v * also available as University of Washington TR 89-08-06. 39727e995b7bba3c57fb1e5c156d386ca11894f781v * 40727e995b7bba3c57fb1e5c156d386ca11894f781v * Beware: this benchmark is written in a grotesque style where 41727e995b7bba3c57fb1e5c156d386ca11894f781v * the constraint model is built by side-effects from constructors. 42727e995b7bba3c57fb1e5c156d386ca11894f781v * I've kept it this way to avoid deviating too much from the original 43727e995b7bba3c57fb1e5c156d386ca11894f781v * implementation. 44727e995b7bba3c57fb1e5c156d386ca11894f781v */ 45727e995b7bba3c57fb1e5c156d386ca11894f781v 46727e995b7bba3c57fb1e5c156d386ca11894f781v 47727e995b7bba3c57fb1e5c156d386ca11894f781v/* --- O b j e c t M o d e l --- */ 48727e995b7bba3c57fb1e5c156d386ca11894f781v 4968ac009f55a85e6891742d58914eaf717f667b26kasperl@chromium.orgObject.prototype.inheritsFrom = function (shuper) { 50727e995b7bba3c57fb1e5c156d386ca11894f781v function Inheriter() { } 51727e995b7bba3c57fb1e5c156d386ca11894f781v Inheriter.prototype = shuper.prototype; 52727e995b7bba3c57fb1e5c156d386ca11894f781v this.prototype = new Inheriter(); 53727e995b7bba3c57fb1e5c156d386ca11894f781v this.superConstructor = shuper; 54727e995b7bba3c57fb1e5c156d386ca11894f781v} 55727e995b7bba3c57fb1e5c156d386ca11894f781v 56727e995b7bba3c57fb1e5c156d386ca11894f781vfunction OrderedCollection() { 57727e995b7bba3c57fb1e5c156d386ca11894f781v this.elms = new Array(); 58727e995b7bba3c57fb1e5c156d386ca11894f781v} 59727e995b7bba3c57fb1e5c156d386ca11894f781v 60727e995b7bba3c57fb1e5c156d386ca11894f781vOrderedCollection.prototype.add = function (elm) { 61727e995b7bba3c57fb1e5c156d386ca11894f781v this.elms.push(elm); 62727e995b7bba3c57fb1e5c156d386ca11894f781v} 63727e995b7bba3c57fb1e5c156d386ca11894f781v 64727e995b7bba3c57fb1e5c156d386ca11894f781vOrderedCollection.prototype.at = function (index) { 65727e995b7bba3c57fb1e5c156d386ca11894f781v return this.elms[index]; 66727e995b7bba3c57fb1e5c156d386ca11894f781v} 67727e995b7bba3c57fb1e5c156d386ca11894f781v 68727e995b7bba3c57fb1e5c156d386ca11894f781vOrderedCollection.prototype.size = function () { 69727e995b7bba3c57fb1e5c156d386ca11894f781v return this.elms.length; 70727e995b7bba3c57fb1e5c156d386ca11894f781v} 71727e995b7bba3c57fb1e5c156d386ca11894f781v 72727e995b7bba3c57fb1e5c156d386ca11894f781vOrderedCollection.prototype.removeFirst = function () { 73727e995b7bba3c57fb1e5c156d386ca11894f781v return this.elms.pop(); 74727e995b7bba3c57fb1e5c156d386ca11894f781v} 75727e995b7bba3c57fb1e5c156d386ca11894f781v 76727e995b7bba3c57fb1e5c156d386ca11894f781vOrderedCollection.prototype.remove = function (elm) { 77727e995b7bba3c57fb1e5c156d386ca11894f781v var index = 0, skipped = 0; 78727e995b7bba3c57fb1e5c156d386ca11894f781v for (var i = 0; i < this.elms.length; i++) { 79727e995b7bba3c57fb1e5c156d386ca11894f781v var value = this.elms[i]; 80727e995b7bba3c57fb1e5c156d386ca11894f781v if (value != elm) { 81727e995b7bba3c57fb1e5c156d386ca11894f781v this.elms[index] = value; 82727e995b7bba3c57fb1e5c156d386ca11894f781v index++; 83727e995b7bba3c57fb1e5c156d386ca11894f781v } else { 84727e995b7bba3c57fb1e5c156d386ca11894f781v skipped++; 85727e995b7bba3c57fb1e5c156d386ca11894f781v } 86727e995b7bba3c57fb1e5c156d386ca11894f781v } 87727e995b7bba3c57fb1e5c156d386ca11894f781v for (var i = 0; i < skipped; i++) 88727e995b7bba3c57fb1e5c156d386ca11894f781v this.elms.pop(); 89727e995b7bba3c57fb1e5c156d386ca11894f781v} 90727e995b7bba3c57fb1e5c156d386ca11894f781v 91727e995b7bba3c57fb1e5c156d386ca11894f781v/* --- * 92727e995b7bba3c57fb1e5c156d386ca11894f781v * S t r e n g t h 93727e995b7bba3c57fb1e5c156d386ca11894f781v * --- */ 94727e995b7bba3c57fb1e5c156d386ca11894f781v 95727e995b7bba3c57fb1e5c156d386ca11894f781v/** 96727e995b7bba3c57fb1e5c156d386ca11894f781v * Strengths are used to measure the relative importance of constraints. 97727e995b7bba3c57fb1e5c156d386ca11894f781v * New strengths may be inserted in the strength hierarchy without 98727e995b7bba3c57fb1e5c156d386ca11894f781v * disrupting current constraints. Strengths cannot be created outside 99727e995b7bba3c57fb1e5c156d386ca11894f781v * this class, so pointer comparison can be used for value comparison. 100727e995b7bba3c57fb1e5c156d386ca11894f781v */ 101727e995b7bba3c57fb1e5c156d386ca11894f781vfunction Strength(strengthValue, name) { 102727e995b7bba3c57fb1e5c156d386ca11894f781v this.strengthValue = strengthValue; 103727e995b7bba3c57fb1e5c156d386ca11894f781v this.name = name; 104727e995b7bba3c57fb1e5c156d386ca11894f781v} 105727e995b7bba3c57fb1e5c156d386ca11894f781v 106727e995b7bba3c57fb1e5c156d386ca11894f781vStrength.stronger = function (s1, s2) { 107727e995b7bba3c57fb1e5c156d386ca11894f781v return s1.strengthValue < s2.strengthValue; 108727e995b7bba3c57fb1e5c156d386ca11894f781v} 109727e995b7bba3c57fb1e5c156d386ca11894f781v 110727e995b7bba3c57fb1e5c156d386ca11894f781vStrength.weaker = function (s1, s2) { 111727e995b7bba3c57fb1e5c156d386ca11894f781v return s1.strengthValue > s2.strengthValue; 112727e995b7bba3c57fb1e5c156d386ca11894f781v} 113727e995b7bba3c57fb1e5c156d386ca11894f781v 114727e995b7bba3c57fb1e5c156d386ca11894f781vStrength.weakestOf = function (s1, s2) { 115727e995b7bba3c57fb1e5c156d386ca11894f781v return this.weaker(s1, s2) ? s1 : s2; 116727e995b7bba3c57fb1e5c156d386ca11894f781v} 117727e995b7bba3c57fb1e5c156d386ca11894f781v 118727e995b7bba3c57fb1e5c156d386ca11894f781vStrength.strongest = function (s1, s2) { 119727e995b7bba3c57fb1e5c156d386ca11894f781v return this.stronger(s1, s2) ? s1 : s2; 120727e995b7bba3c57fb1e5c156d386ca11894f781v} 121727e995b7bba3c57fb1e5c156d386ca11894f781v 122727e995b7bba3c57fb1e5c156d386ca11894f781vStrength.prototype.nextWeaker = function () { 123727e995b7bba3c57fb1e5c156d386ca11894f781v switch (this.strengthValue) { 124ef33a5482a35a9a25f702f8e3f02bb6b49f3854cjkummerow@chromium.org case 0: return Strength.STRONG_PREFERRED; 125ef33a5482a35a9a25f702f8e3f02bb6b49f3854cjkummerow@chromium.org case 1: return Strength.PREFERRED; 126ef33a5482a35a9a25f702f8e3f02bb6b49f3854cjkummerow@chromium.org case 2: return Strength.STRONG_DEFAULT; 127ef33a5482a35a9a25f702f8e3f02bb6b49f3854cjkummerow@chromium.org case 3: return Strength.NORMAL; 128ef33a5482a35a9a25f702f8e3f02bb6b49f3854cjkummerow@chromium.org case 4: return Strength.WEAK_DEFAULT; 129ef33a5482a35a9a25f702f8e3f02bb6b49f3854cjkummerow@chromium.org case 5: return Strength.WEAKEST; 130727e995b7bba3c57fb1e5c156d386ca11894f781v } 131727e995b7bba3c57fb1e5c156d386ca11894f781v} 132727e995b7bba3c57fb1e5c156d386ca11894f781v 133727e995b7bba3c57fb1e5c156d386ca11894f781v// Strength constants. 134ef33a5482a35a9a25f702f8e3f02bb6b49f3854cjkummerow@chromium.orgStrength.REQUIRED = new Strength(0, "required"); 135ef33a5482a35a9a25f702f8e3f02bb6b49f3854cjkummerow@chromium.orgStrength.STRONG_PREFERRED = new Strength(1, "strongPreferred"); 136ef33a5482a35a9a25f702f8e3f02bb6b49f3854cjkummerow@chromium.orgStrength.PREFERRED = new Strength(2, "preferred"); 137ef33a5482a35a9a25f702f8e3f02bb6b49f3854cjkummerow@chromium.orgStrength.STRONG_DEFAULT = new Strength(3, "strongDefault"); 138ef33a5482a35a9a25f702f8e3f02bb6b49f3854cjkummerow@chromium.orgStrength.NORMAL = new Strength(4, "normal"); 139ef33a5482a35a9a25f702f8e3f02bb6b49f3854cjkummerow@chromium.orgStrength.WEAK_DEFAULT = new Strength(5, "weakDefault"); 140ef33a5482a35a9a25f702f8e3f02bb6b49f3854cjkummerow@chromium.orgStrength.WEAKEST = new Strength(6, "weakest"); 141727e995b7bba3c57fb1e5c156d386ca11894f781v 142727e995b7bba3c57fb1e5c156d386ca11894f781v/* --- * 143727e995b7bba3c57fb1e5c156d386ca11894f781v * C o n s t r a i n t 144727e995b7bba3c57fb1e5c156d386ca11894f781v * --- */ 145727e995b7bba3c57fb1e5c156d386ca11894f781v 146727e995b7bba3c57fb1e5c156d386ca11894f781v/** 147727e995b7bba3c57fb1e5c156d386ca11894f781v * An abstract class representing a system-maintainable relationship 148727e995b7bba3c57fb1e5c156d386ca11894f781v * (or "constraint") between a set of variables. A constraint supplies 149727e995b7bba3c57fb1e5c156d386ca11894f781v * a strength instance variable; concrete subclasses provide a means 150727e995b7bba3c57fb1e5c156d386ca11894f781v * of storing the constrained variables and other information required 151727e995b7bba3c57fb1e5c156d386ca11894f781v * to represent a constraint. 152727e995b7bba3c57fb1e5c156d386ca11894f781v */ 153727e995b7bba3c57fb1e5c156d386ca11894f781vfunction Constraint(strength) { 154727e995b7bba3c57fb1e5c156d386ca11894f781v this.strength = strength; 155727e995b7bba3c57fb1e5c156d386ca11894f781v} 156727e995b7bba3c57fb1e5c156d386ca11894f781v 157727e995b7bba3c57fb1e5c156d386ca11894f781v/** 158727e995b7bba3c57fb1e5c156d386ca11894f781v * Activate this constraint and attempt to satisfy it. 159727e995b7bba3c57fb1e5c156d386ca11894f781v */ 160727e995b7bba3c57fb1e5c156d386ca11894f781vConstraint.prototype.addConstraint = function () { 161727e995b7bba3c57fb1e5c156d386ca11894f781v this.addToGraph(); 162727e995b7bba3c57fb1e5c156d386ca11894f781v planner.incrementalAdd(this); 163727e995b7bba3c57fb1e5c156d386ca11894f781v} 164727e995b7bba3c57fb1e5c156d386ca11894f781v 165727e995b7bba3c57fb1e5c156d386ca11894f781v/** 166727e995b7bba3c57fb1e5c156d386ca11894f781v * Attempt to find a way to enforce this constraint. If successful, 167727e995b7bba3c57fb1e5c156d386ca11894f781v * record the solution, perhaps modifying the current dataflow 168727e995b7bba3c57fb1e5c156d386ca11894f781v * graph. Answer the constraint that this constraint overrides, if 169727e995b7bba3c57fb1e5c156d386ca11894f781v * there is one, or nil, if there isn't. 170727e995b7bba3c57fb1e5c156d386ca11894f781v * Assume: I am not already satisfied. 171727e995b7bba3c57fb1e5c156d386ca11894f781v */ 172727e995b7bba3c57fb1e5c156d386ca11894f781vConstraint.prototype.satisfy = function (mark) { 173727e995b7bba3c57fb1e5c156d386ca11894f781v this.chooseMethod(mark); 174727e995b7bba3c57fb1e5c156d386ca11894f781v if (!this.isSatisfied()) { 175727e995b7bba3c57fb1e5c156d386ca11894f781v if (this.strength == Strength.REQUIRED) 176727e995b7bba3c57fb1e5c156d386ca11894f781v alert("Could not satisfy a required constraint!"); 177727e995b7bba3c57fb1e5c156d386ca11894f781v return null; 178727e995b7bba3c57fb1e5c156d386ca11894f781v } 179727e995b7bba3c57fb1e5c156d386ca11894f781v this.markInputs(mark); 180727e995b7bba3c57fb1e5c156d386ca11894f781v var out = this.output(); 181727e995b7bba3c57fb1e5c156d386ca11894f781v var overridden = out.determinedBy; 182727e995b7bba3c57fb1e5c156d386ca11894f781v if (overridden != null) overridden.markUnsatisfied(); 183727e995b7bba3c57fb1e5c156d386ca11894f781v out.determinedBy = this; 184727e995b7bba3c57fb1e5c156d386ca11894f781v if (!planner.addPropagate(this, mark)) 185727e995b7bba3c57fb1e5c156d386ca11894f781v alert("Cycle encountered"); 186727e995b7bba3c57fb1e5c156d386ca11894f781v out.mark = mark; 187727e995b7bba3c57fb1e5c156d386ca11894f781v return overridden; 188727e995b7bba3c57fb1e5c156d386ca11894f781v} 189727e995b7bba3c57fb1e5c156d386ca11894f781v 190727e995b7bba3c57fb1e5c156d386ca11894f781vConstraint.prototype.destroyConstraint = function () { 191727e995b7bba3c57fb1e5c156d386ca11894f781v if (this.isSatisfied()) planner.incrementalRemove(this); 192727e995b7bba3c57fb1e5c156d386ca11894f781v else this.removeFromGraph(); 193727e995b7bba3c57fb1e5c156d386ca11894f781v} 194727e995b7bba3c57fb1e5c156d386ca11894f781v 195727e995b7bba3c57fb1e5c156d386ca11894f781v/** 196727e995b7bba3c57fb1e5c156d386ca11894f781v * Normal constraints are not input constraints. An input constraint 197727e995b7bba3c57fb1e5c156d386ca11894f781v * is one that depends on external state, such as the mouse, the 198727e995b7bba3c57fb1e5c156d386ca11894f781v * keybord, a clock, or some arbitraty piece of imperative code. 199727e995b7bba3c57fb1e5c156d386ca11894f781v */ 200727e995b7bba3c57fb1e5c156d386ca11894f781vConstraint.prototype.isInput = function () { 201727e995b7bba3c57fb1e5c156d386ca11894f781v return false; 202727e995b7bba3c57fb1e5c156d386ca11894f781v} 203727e995b7bba3c57fb1e5c156d386ca11894f781v 204727e995b7bba3c57fb1e5c156d386ca11894f781v/* --- * 205727e995b7bba3c57fb1e5c156d386ca11894f781v * U n a r y C o n s t r a i n t 206727e995b7bba3c57fb1e5c156d386ca11894f781v * --- */ 207727e995b7bba3c57fb1e5c156d386ca11894f781v 208727e995b7bba3c57fb1e5c156d386ca11894f781v/** 209727e995b7bba3c57fb1e5c156d386ca11894f781v * Abstract superclass for constraints having a single possible output 210727e995b7bba3c57fb1e5c156d386ca11894f781v * variable. 211727e995b7bba3c57fb1e5c156d386ca11894f781v */ 212727e995b7bba3c57fb1e5c156d386ca11894f781vfunction UnaryConstraint(v, strength) { 213727e995b7bba3c57fb1e5c156d386ca11894f781v UnaryConstraint.superConstructor.call(this, strength); 214727e995b7bba3c57fb1e5c156d386ca11894f781v this.myOutput = v; 215727e995b7bba3c57fb1e5c156d386ca11894f781v this.satisfied = false; 216727e995b7bba3c57fb1e5c156d386ca11894f781v this.addConstraint(); 217727e995b7bba3c57fb1e5c156d386ca11894f781v} 218727e995b7bba3c57fb1e5c156d386ca11894f781v 21968ac009f55a85e6891742d58914eaf717f667b26kasperl@chromium.orgUnaryConstraint.inheritsFrom(Constraint); 220727e995b7bba3c57fb1e5c156d386ca11894f781v 221727e995b7bba3c57fb1e5c156d386ca11894f781v/** 222727e995b7bba3c57fb1e5c156d386ca11894f781v * Adds this constraint to the constraint graph 223727e995b7bba3c57fb1e5c156d386ca11894f781v */ 224727e995b7bba3c57fb1e5c156d386ca11894f781vUnaryConstraint.prototype.addToGraph = function () { 225727e995b7bba3c57fb1e5c156d386ca11894f781v this.myOutput.addConstraint(this); 226727e995b7bba3c57fb1e5c156d386ca11894f781v this.satisfied = false; 227727e995b7bba3c57fb1e5c156d386ca11894f781v} 228727e995b7bba3c57fb1e5c156d386ca11894f781v 229727e995b7bba3c57fb1e5c156d386ca11894f781v/** 230727e995b7bba3c57fb1e5c156d386ca11894f781v * Decides if this constraint can be satisfied and records that 231727e995b7bba3c57fb1e5c156d386ca11894f781v * decision. 232727e995b7bba3c57fb1e5c156d386ca11894f781v */ 233727e995b7bba3c57fb1e5c156d386ca11894f781vUnaryConstraint.prototype.chooseMethod = function (mark) { 234727e995b7bba3c57fb1e5c156d386ca11894f781v this.satisfied = (this.myOutput.mark != mark) 235727e995b7bba3c57fb1e5c156d386ca11894f781v && Strength.stronger(this.strength, this.myOutput.walkStrength); 236727e995b7bba3c57fb1e5c156d386ca11894f781v} 237727e995b7bba3c57fb1e5c156d386ca11894f781v 238727e995b7bba3c57fb1e5c156d386ca11894f781v/** 239727e995b7bba3c57fb1e5c156d386ca11894f781v * Returns true if this constraint is satisfied in the current solution. 240727e995b7bba3c57fb1e5c156d386ca11894f781v */ 241727e995b7bba3c57fb1e5c156d386ca11894f781vUnaryConstraint.prototype.isSatisfied = function () { 242727e995b7bba3c57fb1e5c156d386ca11894f781v return this.satisfied; 243727e995b7bba3c57fb1e5c156d386ca11894f781v} 244727e995b7bba3c57fb1e5c156d386ca11894f781v 245727e995b7bba3c57fb1e5c156d386ca11894f781vUnaryConstraint.prototype.markInputs = function (mark) { 246727e995b7bba3c57fb1e5c156d386ca11894f781v // has no inputs 247727e995b7bba3c57fb1e5c156d386ca11894f781v} 248727e995b7bba3c57fb1e5c156d386ca11894f781v 249727e995b7bba3c57fb1e5c156d386ca11894f781v/** 250727e995b7bba3c57fb1e5c156d386ca11894f781v * Returns the current output variable. 251727e995b7bba3c57fb1e5c156d386ca11894f781v */ 252727e995b7bba3c57fb1e5c156d386ca11894f781vUnaryConstraint.prototype.output = function () { 253727e995b7bba3c57fb1e5c156d386ca11894f781v return this.myOutput; 254727e995b7bba3c57fb1e5c156d386ca11894f781v} 255727e995b7bba3c57fb1e5c156d386ca11894f781v 256727e995b7bba3c57fb1e5c156d386ca11894f781v/** 257727e995b7bba3c57fb1e5c156d386ca11894f781v * Calculate the walkabout strength, the stay flag, and, if it is 258727e995b7bba3c57fb1e5c156d386ca11894f781v * 'stay', the value for the current output of this constraint. Assume 259727e995b7bba3c57fb1e5c156d386ca11894f781v * this constraint is satisfied. 260727e995b7bba3c57fb1e5c156d386ca11894f781v */ 261727e995b7bba3c57fb1e5c156d386ca11894f781vUnaryConstraint.prototype.recalculate = function () { 262727e995b7bba3c57fb1e5c156d386ca11894f781v this.myOutput.walkStrength = this.strength; 263727e995b7bba3c57fb1e5c156d386ca11894f781v this.myOutput.stay = !this.isInput(); 264727e995b7bba3c57fb1e5c156d386ca11894f781v if (this.myOutput.stay) this.execute(); // Stay optimization 265727e995b7bba3c57fb1e5c156d386ca11894f781v} 266727e995b7bba3c57fb1e5c156d386ca11894f781v 267727e995b7bba3c57fb1e5c156d386ca11894f781v/** 268727e995b7bba3c57fb1e5c156d386ca11894f781v * Records that this constraint is unsatisfied 269727e995b7bba3c57fb1e5c156d386ca11894f781v */ 270727e995b7bba3c57fb1e5c156d386ca11894f781vUnaryConstraint.prototype.markUnsatisfied = function () { 271727e995b7bba3c57fb1e5c156d386ca11894f781v this.satisfied = false; 272727e995b7bba3c57fb1e5c156d386ca11894f781v} 273727e995b7bba3c57fb1e5c156d386ca11894f781v 274727e995b7bba3c57fb1e5c156d386ca11894f781vUnaryConstraint.prototype.inputsKnown = function () { 275727e995b7bba3c57fb1e5c156d386ca11894f781v return true; 276727e995b7bba3c57fb1e5c156d386ca11894f781v} 277727e995b7bba3c57fb1e5c156d386ca11894f781v 278727e995b7bba3c57fb1e5c156d386ca11894f781vUnaryConstraint.prototype.removeFromGraph = function () { 279727e995b7bba3c57fb1e5c156d386ca11894f781v if (this.myOutput != null) this.myOutput.removeConstraint(this); 280727e995b7bba3c57fb1e5c156d386ca11894f781v this.satisfied = false; 281727e995b7bba3c57fb1e5c156d386ca11894f781v} 282727e995b7bba3c57fb1e5c156d386ca11894f781v 283727e995b7bba3c57fb1e5c156d386ca11894f781v/* --- * 284727e995b7bba3c57fb1e5c156d386ca11894f781v * S t a y C o n s t r a i n t 285727e995b7bba3c57fb1e5c156d386ca11894f781v * --- */ 286727e995b7bba3c57fb1e5c156d386ca11894f781v 287727e995b7bba3c57fb1e5c156d386ca11894f781v/** 288727e995b7bba3c57fb1e5c156d386ca11894f781v * Variables that should, with some level of preference, stay the same. 289727e995b7bba3c57fb1e5c156d386ca11894f781v * Planners may exploit the fact that instances, if satisfied, will not 290727e995b7bba3c57fb1e5c156d386ca11894f781v * change their output during plan execution. This is called "stay 291727e995b7bba3c57fb1e5c156d386ca11894f781v * optimization". 292727e995b7bba3c57fb1e5c156d386ca11894f781v */ 293727e995b7bba3c57fb1e5c156d386ca11894f781vfunction StayConstraint(v, str) { 294727e995b7bba3c57fb1e5c156d386ca11894f781v StayConstraint.superConstructor.call(this, v, str); 295727e995b7bba3c57fb1e5c156d386ca11894f781v} 296727e995b7bba3c57fb1e5c156d386ca11894f781v 29768ac009f55a85e6891742d58914eaf717f667b26kasperl@chromium.orgStayConstraint.inheritsFrom(UnaryConstraint); 298727e995b7bba3c57fb1e5c156d386ca11894f781v 299727e995b7bba3c57fb1e5c156d386ca11894f781vStayConstraint.prototype.execute = function () { 300727e995b7bba3c57fb1e5c156d386ca11894f781v // Stay constraints do nothing 301727e995b7bba3c57fb1e5c156d386ca11894f781v} 302727e995b7bba3c57fb1e5c156d386ca11894f781v 303727e995b7bba3c57fb1e5c156d386ca11894f781v/* --- * 304727e995b7bba3c57fb1e5c156d386ca11894f781v * E d i t C o n s t r a i n t 305727e995b7bba3c57fb1e5c156d386ca11894f781v * --- */ 306727e995b7bba3c57fb1e5c156d386ca11894f781v 307727e995b7bba3c57fb1e5c156d386ca11894f781v/** 308727e995b7bba3c57fb1e5c156d386ca11894f781v * A unary input constraint used to mark a variable that the client 309727e995b7bba3c57fb1e5c156d386ca11894f781v * wishes to change. 310727e995b7bba3c57fb1e5c156d386ca11894f781v */ 311727e995b7bba3c57fb1e5c156d386ca11894f781vfunction EditConstraint(v, str) { 312727e995b7bba3c57fb1e5c156d386ca11894f781v EditConstraint.superConstructor.call(this, v, str); 313727e995b7bba3c57fb1e5c156d386ca11894f781v} 314727e995b7bba3c57fb1e5c156d386ca11894f781v 31568ac009f55a85e6891742d58914eaf717f667b26kasperl@chromium.orgEditConstraint.inheritsFrom(UnaryConstraint); 316727e995b7bba3c57fb1e5c156d386ca11894f781v 317727e995b7bba3c57fb1e5c156d386ca11894f781v/** 318727e995b7bba3c57fb1e5c156d386ca11894f781v * Edits indicate that a variable is to be changed by imperative code. 319727e995b7bba3c57fb1e5c156d386ca11894f781v */ 320727e995b7bba3c57fb1e5c156d386ca11894f781vEditConstraint.prototype.isInput = function () { 321727e995b7bba3c57fb1e5c156d386ca11894f781v return true; 322727e995b7bba3c57fb1e5c156d386ca11894f781v} 323727e995b7bba3c57fb1e5c156d386ca11894f781v 324727e995b7bba3c57fb1e5c156d386ca11894f781vEditConstraint.prototype.execute = function () { 325727e995b7bba3c57fb1e5c156d386ca11894f781v // Edit constraints do nothing 326727e995b7bba3c57fb1e5c156d386ca11894f781v} 327727e995b7bba3c57fb1e5c156d386ca11894f781v 328727e995b7bba3c57fb1e5c156d386ca11894f781v/* --- * 329727e995b7bba3c57fb1e5c156d386ca11894f781v * B i n a r y C o n s t r a i n t 330727e995b7bba3c57fb1e5c156d386ca11894f781v * --- */ 331727e995b7bba3c57fb1e5c156d386ca11894f781v 332727e995b7bba3c57fb1e5c156d386ca11894f781vvar Direction = new Object(); 333727e995b7bba3c57fb1e5c156d386ca11894f781vDirection.NONE = 0; 334727e995b7bba3c57fb1e5c156d386ca11894f781vDirection.FORWARD = 1; 335727e995b7bba3c57fb1e5c156d386ca11894f781vDirection.BACKWARD = -1; 336727e995b7bba3c57fb1e5c156d386ca11894f781v 337727e995b7bba3c57fb1e5c156d386ca11894f781v/** 338727e995b7bba3c57fb1e5c156d386ca11894f781v * Abstract superclass for constraints having two possible output 339727e995b7bba3c57fb1e5c156d386ca11894f781v * variables. 340727e995b7bba3c57fb1e5c156d386ca11894f781v */ 341727e995b7bba3c57fb1e5c156d386ca11894f781vfunction BinaryConstraint(var1, var2, strength) { 342727e995b7bba3c57fb1e5c156d386ca11894f781v BinaryConstraint.superConstructor.call(this, strength); 343727e995b7bba3c57fb1e5c156d386ca11894f781v this.v1 = var1; 344727e995b7bba3c57fb1e5c156d386ca11894f781v this.v2 = var2; 345727e995b7bba3c57fb1e5c156d386ca11894f781v this.direction = Direction.NONE; 346727e995b7bba3c57fb1e5c156d386ca11894f781v this.addConstraint(); 347727e995b7bba3c57fb1e5c156d386ca11894f781v} 348727e995b7bba3c57fb1e5c156d386ca11894f781v 34968ac009f55a85e6891742d58914eaf717f667b26kasperl@chromium.orgBinaryConstraint.inheritsFrom(Constraint); 350727e995b7bba3c57fb1e5c156d386ca11894f781v 351727e995b7bba3c57fb1e5c156d386ca11894f781v/** 35232d961d4454609ab4251a760fc46b19f661da90clrn@chromium.org * Decides if this constraint can be satisfied and which way it 353727e995b7bba3c57fb1e5c156d386ca11894f781v * should flow based on the relative strength of the variables related, 354727e995b7bba3c57fb1e5c156d386ca11894f781v * and record that decision. 355727e995b7bba3c57fb1e5c156d386ca11894f781v */ 356727e995b7bba3c57fb1e5c156d386ca11894f781vBinaryConstraint.prototype.chooseMethod = function (mark) { 357727e995b7bba3c57fb1e5c156d386ca11894f781v if (this.v1.mark == mark) { 35832d961d4454609ab4251a760fc46b19f661da90clrn@chromium.org this.direction = (this.v2.mark != mark && Strength.stronger(this.strength, this.v2.walkStrength)) 359727e995b7bba3c57fb1e5c156d386ca11894f781v ? Direction.FORWARD 360727e995b7bba3c57fb1e5c156d386ca11894f781v : Direction.NONE; 361727e995b7bba3c57fb1e5c156d386ca11894f781v } 362727e995b7bba3c57fb1e5c156d386ca11894f781v if (this.v2.mark == mark) { 363727e995b7bba3c57fb1e5c156d386ca11894f781v this.direction = (this.v1.mark != mark && Strength.stronger(this.strength, this.v1.walkStrength)) 364727e995b7bba3c57fb1e5c156d386ca11894f781v ? Direction.BACKWARD 365727e995b7bba3c57fb1e5c156d386ca11894f781v : Direction.NONE; 366727e995b7bba3c57fb1e5c156d386ca11894f781v } 367727e995b7bba3c57fb1e5c156d386ca11894f781v if (Strength.weaker(this.v1.walkStrength, this.v2.walkStrength)) { 368727e995b7bba3c57fb1e5c156d386ca11894f781v this.direction = Strength.stronger(this.strength, this.v1.walkStrength) 369727e995b7bba3c57fb1e5c156d386ca11894f781v ? Direction.BACKWARD 370727e995b7bba3c57fb1e5c156d386ca11894f781v : Direction.NONE; 371727e995b7bba3c57fb1e5c156d386ca11894f781v } else { 372727e995b7bba3c57fb1e5c156d386ca11894f781v this.direction = Strength.stronger(this.strength, this.v2.walkStrength) 373727e995b7bba3c57fb1e5c156d386ca11894f781v ? Direction.FORWARD 374727e995b7bba3c57fb1e5c156d386ca11894f781v : Direction.BACKWARD 375727e995b7bba3c57fb1e5c156d386ca11894f781v } 376727e995b7bba3c57fb1e5c156d386ca11894f781v} 377727e995b7bba3c57fb1e5c156d386ca11894f781v 378727e995b7bba3c57fb1e5c156d386ca11894f781v/** 379727e995b7bba3c57fb1e5c156d386ca11894f781v * Add this constraint to the constraint graph 380727e995b7bba3c57fb1e5c156d386ca11894f781v */ 381727e995b7bba3c57fb1e5c156d386ca11894f781vBinaryConstraint.prototype.addToGraph = function () { 382727e995b7bba3c57fb1e5c156d386ca11894f781v this.v1.addConstraint(this); 383727e995b7bba3c57fb1e5c156d386ca11894f781v this.v2.addConstraint(this); 384727e995b7bba3c57fb1e5c156d386ca11894f781v this.direction = Direction.NONE; 385727e995b7bba3c57fb1e5c156d386ca11894f781v} 386727e995b7bba3c57fb1e5c156d386ca11894f781v 387727e995b7bba3c57fb1e5c156d386ca11894f781v/** 388727e995b7bba3c57fb1e5c156d386ca11894f781v * Answer true if this constraint is satisfied in the current solution. 389727e995b7bba3c57fb1e5c156d386ca11894f781v */ 390727e995b7bba3c57fb1e5c156d386ca11894f781vBinaryConstraint.prototype.isSatisfied = function () { 391727e995b7bba3c57fb1e5c156d386ca11894f781v return this.direction != Direction.NONE; 392727e995b7bba3c57fb1e5c156d386ca11894f781v} 393727e995b7bba3c57fb1e5c156d386ca11894f781v 394727e995b7bba3c57fb1e5c156d386ca11894f781v/** 395727e995b7bba3c57fb1e5c156d386ca11894f781v * Mark the input variable with the given mark. 396727e995b7bba3c57fb1e5c156d386ca11894f781v */ 397727e995b7bba3c57fb1e5c156d386ca11894f781vBinaryConstraint.prototype.markInputs = function (mark) { 398727e995b7bba3c57fb1e5c156d386ca11894f781v this.input().mark = mark; 399727e995b7bba3c57fb1e5c156d386ca11894f781v} 400727e995b7bba3c57fb1e5c156d386ca11894f781v 401727e995b7bba3c57fb1e5c156d386ca11894f781v/** 402727e995b7bba3c57fb1e5c156d386ca11894f781v * Returns the current input variable 403727e995b7bba3c57fb1e5c156d386ca11894f781v */ 404727e995b7bba3c57fb1e5c156d386ca11894f781vBinaryConstraint.prototype.input = function () { 405727e995b7bba3c57fb1e5c156d386ca11894f781v return (this.direction == Direction.FORWARD) ? this.v1 : this.v2; 406727e995b7bba3c57fb1e5c156d386ca11894f781v} 407727e995b7bba3c57fb1e5c156d386ca11894f781v 408727e995b7bba3c57fb1e5c156d386ca11894f781v/** 409727e995b7bba3c57fb1e5c156d386ca11894f781v * Returns the current output variable 410727e995b7bba3c57fb1e5c156d386ca11894f781v */ 411727e995b7bba3c57fb1e5c156d386ca11894f781vBinaryConstraint.prototype.output = function () { 412727e995b7bba3c57fb1e5c156d386ca11894f781v return (this.direction == Direction.FORWARD) ? this.v2 : this.v1; 413727e995b7bba3c57fb1e5c156d386ca11894f781v} 414727e995b7bba3c57fb1e5c156d386ca11894f781v 415727e995b7bba3c57fb1e5c156d386ca11894f781v/** 416727e995b7bba3c57fb1e5c156d386ca11894f781v * Calculate the walkabout strength, the stay flag, and, if it is 417727e995b7bba3c57fb1e5c156d386ca11894f781v * 'stay', the value for the current output of this 418727e995b7bba3c57fb1e5c156d386ca11894f781v * constraint. Assume this constraint is satisfied. 419727e995b7bba3c57fb1e5c156d386ca11894f781v */ 420727e995b7bba3c57fb1e5c156d386ca11894f781vBinaryConstraint.prototype.recalculate = function () { 421727e995b7bba3c57fb1e5c156d386ca11894f781v var ihn = this.input(), out = this.output(); 422727e995b7bba3c57fb1e5c156d386ca11894f781v out.walkStrength = Strength.weakestOf(this.strength, ihn.walkStrength); 423727e995b7bba3c57fb1e5c156d386ca11894f781v out.stay = ihn.stay; 424727e995b7bba3c57fb1e5c156d386ca11894f781v if (out.stay) this.execute(); 425727e995b7bba3c57fb1e5c156d386ca11894f781v} 426727e995b7bba3c57fb1e5c156d386ca11894f781v 427727e995b7bba3c57fb1e5c156d386ca11894f781v/** 428727e995b7bba3c57fb1e5c156d386ca11894f781v * Record the fact that this constraint is unsatisfied. 429727e995b7bba3c57fb1e5c156d386ca11894f781v */ 430727e995b7bba3c57fb1e5c156d386ca11894f781vBinaryConstraint.prototype.markUnsatisfied = function () { 431727e995b7bba3c57fb1e5c156d386ca11894f781v this.direction = Direction.NONE; 432727e995b7bba3c57fb1e5c156d386ca11894f781v} 433727e995b7bba3c57fb1e5c156d386ca11894f781v 434727e995b7bba3c57fb1e5c156d386ca11894f781vBinaryConstraint.prototype.inputsKnown = function (mark) { 435727e995b7bba3c57fb1e5c156d386ca11894f781v var i = this.input(); 436727e995b7bba3c57fb1e5c156d386ca11894f781v return i.mark == mark || i.stay || i.determinedBy == null; 437727e995b7bba3c57fb1e5c156d386ca11894f781v} 438727e995b7bba3c57fb1e5c156d386ca11894f781v 439727e995b7bba3c57fb1e5c156d386ca11894f781vBinaryConstraint.prototype.removeFromGraph = function () { 440727e995b7bba3c57fb1e5c156d386ca11894f781v if (this.v1 != null) this.v1.removeConstraint(this); 441727e995b7bba3c57fb1e5c156d386ca11894f781v if (this.v2 != null) this.v2.removeConstraint(this); 442727e995b7bba3c57fb1e5c156d386ca11894f781v this.direction = Direction.NONE; 443727e995b7bba3c57fb1e5c156d386ca11894f781v} 444727e995b7bba3c57fb1e5c156d386ca11894f781v 445727e995b7bba3c57fb1e5c156d386ca11894f781v/* --- * 446727e995b7bba3c57fb1e5c156d386ca11894f781v * S c a l e C o n s t r a i n t 447727e995b7bba3c57fb1e5c156d386ca11894f781v * --- */ 448727e995b7bba3c57fb1e5c156d386ca11894f781v 449727e995b7bba3c57fb1e5c156d386ca11894f781v/** 450727e995b7bba3c57fb1e5c156d386ca11894f781v * Relates two variables by the linear scaling relationship: "v2 = 451727e995b7bba3c57fb1e5c156d386ca11894f781v * (v1 * scale) + offset". Either v1 or v2 may be changed to maintain 452727e995b7bba3c57fb1e5c156d386ca11894f781v * this relationship but the scale factor and offset are considered 453727e995b7bba3c57fb1e5c156d386ca11894f781v * read-only. 454727e995b7bba3c57fb1e5c156d386ca11894f781v */ 455727e995b7bba3c57fb1e5c156d386ca11894f781vfunction ScaleConstraint(src, scale, offset, dest, strength) { 456727e995b7bba3c57fb1e5c156d386ca11894f781v this.direction = Direction.NONE; 457727e995b7bba3c57fb1e5c156d386ca11894f781v this.scale = scale; 458727e995b7bba3c57fb1e5c156d386ca11894f781v this.offset = offset; 459727e995b7bba3c57fb1e5c156d386ca11894f781v ScaleConstraint.superConstructor.call(this, src, dest, strength); 460727e995b7bba3c57fb1e5c156d386ca11894f781v} 461727e995b7bba3c57fb1e5c156d386ca11894f781v 46268ac009f55a85e6891742d58914eaf717f667b26kasperl@chromium.orgScaleConstraint.inheritsFrom(BinaryConstraint); 463727e995b7bba3c57fb1e5c156d386ca11894f781v 464727e995b7bba3c57fb1e5c156d386ca11894f781v/** 465727e995b7bba3c57fb1e5c156d386ca11894f781v * Adds this constraint to the constraint graph. 466727e995b7bba3c57fb1e5c156d386ca11894f781v */ 467727e995b7bba3c57fb1e5c156d386ca11894f781vScaleConstraint.prototype.addToGraph = function () { 468727e995b7bba3c57fb1e5c156d386ca11894f781v ScaleConstraint.superConstructor.prototype.addToGraph.call(this); 469727e995b7bba3c57fb1e5c156d386ca11894f781v this.scale.addConstraint(this); 470727e995b7bba3c57fb1e5c156d386ca11894f781v this.offset.addConstraint(this); 471727e995b7bba3c57fb1e5c156d386ca11894f781v} 472727e995b7bba3c57fb1e5c156d386ca11894f781v 473727e995b7bba3c57fb1e5c156d386ca11894f781vScaleConstraint.prototype.removeFromGraph = function () { 474727e995b7bba3c57fb1e5c156d386ca11894f781v ScaleConstraint.superConstructor.prototype.removeFromGraph.call(this); 475727e995b7bba3c57fb1e5c156d386ca11894f781v if (this.scale != null) this.scale.removeConstraint(this); 476727e995b7bba3c57fb1e5c156d386ca11894f781v if (this.offset != null) this.offset.removeConstraint(this); 477727e995b7bba3c57fb1e5c156d386ca11894f781v} 478727e995b7bba3c57fb1e5c156d386ca11894f781v 479727e995b7bba3c57fb1e5c156d386ca11894f781vScaleConstraint.prototype.markInputs = function (mark) { 480727e995b7bba3c57fb1e5c156d386ca11894f781v ScaleConstraint.superConstructor.prototype.markInputs.call(this, mark); 481727e995b7bba3c57fb1e5c156d386ca11894f781v this.scale.mark = this.offset.mark = mark; 482727e995b7bba3c57fb1e5c156d386ca11894f781v} 483727e995b7bba3c57fb1e5c156d386ca11894f781v 484727e995b7bba3c57fb1e5c156d386ca11894f781v/** 485727e995b7bba3c57fb1e5c156d386ca11894f781v * Enforce this constraint. Assume that it is satisfied. 486727e995b7bba3c57fb1e5c156d386ca11894f781v */ 487727e995b7bba3c57fb1e5c156d386ca11894f781vScaleConstraint.prototype.execute = function () { 488727e995b7bba3c57fb1e5c156d386ca11894f781v if (this.direction == Direction.FORWARD) { 489727e995b7bba3c57fb1e5c156d386ca11894f781v this.v2.value = this.v1.value * this.scale.value + this.offset.value; 490727e995b7bba3c57fb1e5c156d386ca11894f781v } else { 491727e995b7bba3c57fb1e5c156d386ca11894f781v this.v1.value = (this.v2.value - this.offset.value) / this.scale.value; 492727e995b7bba3c57fb1e5c156d386ca11894f781v } 493727e995b7bba3c57fb1e5c156d386ca11894f781v} 494727e995b7bba3c57fb1e5c156d386ca11894f781v 495727e995b7bba3c57fb1e5c156d386ca11894f781v/** 496727e995b7bba3c57fb1e5c156d386ca11894f781v * Calculate the walkabout strength, the stay flag, and, if it is 497727e995b7bba3c57fb1e5c156d386ca11894f781v * 'stay', the value for the current output of this constraint. Assume 498727e995b7bba3c57fb1e5c156d386ca11894f781v * this constraint is satisfied. 499727e995b7bba3c57fb1e5c156d386ca11894f781v */ 500727e995b7bba3c57fb1e5c156d386ca11894f781vScaleConstraint.prototype.recalculate = function () { 501727e995b7bba3c57fb1e5c156d386ca11894f781v var ihn = this.input(), out = this.output(); 502727e995b7bba3c57fb1e5c156d386ca11894f781v out.walkStrength = Strength.weakestOf(this.strength, ihn.walkStrength); 503727e995b7bba3c57fb1e5c156d386ca11894f781v out.stay = ihn.stay && this.scale.stay && this.offset.stay; 504727e995b7bba3c57fb1e5c156d386ca11894f781v if (out.stay) this.execute(); 505727e995b7bba3c57fb1e5c156d386ca11894f781v} 506727e995b7bba3c57fb1e5c156d386ca11894f781v 507727e995b7bba3c57fb1e5c156d386ca11894f781v/* --- * 508727e995b7bba3c57fb1e5c156d386ca11894f781v * E q u a l i t y C o n s t r a i n t 509727e995b7bba3c57fb1e5c156d386ca11894f781v * --- */ 510727e995b7bba3c57fb1e5c156d386ca11894f781v 511727e995b7bba3c57fb1e5c156d386ca11894f781v/** 512727e995b7bba3c57fb1e5c156d386ca11894f781v * Constrains two variables to have the same value. 513727e995b7bba3c57fb1e5c156d386ca11894f781v */ 514727e995b7bba3c57fb1e5c156d386ca11894f781vfunction EqualityConstraint(var1, var2, strength) { 515727e995b7bba3c57fb1e5c156d386ca11894f781v EqualityConstraint.superConstructor.call(this, var1, var2, strength); 516727e995b7bba3c57fb1e5c156d386ca11894f781v} 517727e995b7bba3c57fb1e5c156d386ca11894f781v 51868ac009f55a85e6891742d58914eaf717f667b26kasperl@chromium.orgEqualityConstraint.inheritsFrom(BinaryConstraint); 519727e995b7bba3c57fb1e5c156d386ca11894f781v 520727e995b7bba3c57fb1e5c156d386ca11894f781v/** 521727e995b7bba3c57fb1e5c156d386ca11894f781v * Enforce this constraint. Assume that it is satisfied. 522727e995b7bba3c57fb1e5c156d386ca11894f781v */ 523727e995b7bba3c57fb1e5c156d386ca11894f781vEqualityConstraint.prototype.execute = function () { 524727e995b7bba3c57fb1e5c156d386ca11894f781v this.output().value = this.input().value; 525727e995b7bba3c57fb1e5c156d386ca11894f781v} 526727e995b7bba3c57fb1e5c156d386ca11894f781v 527727e995b7bba3c57fb1e5c156d386ca11894f781v/* --- * 528727e995b7bba3c57fb1e5c156d386ca11894f781v * V a r i a b l e 529727e995b7bba3c57fb1e5c156d386ca11894f781v * --- */ 530727e995b7bba3c57fb1e5c156d386ca11894f781v 531727e995b7bba3c57fb1e5c156d386ca11894f781v/** 532727e995b7bba3c57fb1e5c156d386ca11894f781v * A constrained variable. In addition to its value, it maintain the 533727e995b7bba3c57fb1e5c156d386ca11894f781v * structure of the constraint graph, the current dataflow graph, and 534727e995b7bba3c57fb1e5c156d386ca11894f781v * various parameters of interest to the DeltaBlue incremental 535727e995b7bba3c57fb1e5c156d386ca11894f781v * constraint solver. 536727e995b7bba3c57fb1e5c156d386ca11894f781v **/ 537727e995b7bba3c57fb1e5c156d386ca11894f781vfunction Variable(name, initialValue) { 538727e995b7bba3c57fb1e5c156d386ca11894f781v this.value = initialValue || 0; 539727e995b7bba3c57fb1e5c156d386ca11894f781v this.constraints = new OrderedCollection(); 540727e995b7bba3c57fb1e5c156d386ca11894f781v this.determinedBy = null; 541727e995b7bba3c57fb1e5c156d386ca11894f781v this.mark = 0; 542727e995b7bba3c57fb1e5c156d386ca11894f781v this.walkStrength = Strength.WEAKEST; 543727e995b7bba3c57fb1e5c156d386ca11894f781v this.stay = true; 544727e995b7bba3c57fb1e5c156d386ca11894f781v this.name = name; 545727e995b7bba3c57fb1e5c156d386ca11894f781v} 546727e995b7bba3c57fb1e5c156d386ca11894f781v 547727e995b7bba3c57fb1e5c156d386ca11894f781v/** 548727e995b7bba3c57fb1e5c156d386ca11894f781v * Add the given constraint to the set of all constraints that refer 549727e995b7bba3c57fb1e5c156d386ca11894f781v * this variable. 550727e995b7bba3c57fb1e5c156d386ca11894f781v */ 551727e995b7bba3c57fb1e5c156d386ca11894f781vVariable.prototype.addConstraint = function (c) { 552727e995b7bba3c57fb1e5c156d386ca11894f781v this.constraints.add(c); 553727e995b7bba3c57fb1e5c156d386ca11894f781v} 554727e995b7bba3c57fb1e5c156d386ca11894f781v 555727e995b7bba3c57fb1e5c156d386ca11894f781v/** 556727e995b7bba3c57fb1e5c156d386ca11894f781v * Removes all traces of c from this variable. 557727e995b7bba3c57fb1e5c156d386ca11894f781v */ 558727e995b7bba3c57fb1e5c156d386ca11894f781vVariable.prototype.removeConstraint = function (c) { 559727e995b7bba3c57fb1e5c156d386ca11894f781v this.constraints.remove(c); 560727e995b7bba3c57fb1e5c156d386ca11894f781v if (this.determinedBy == c) this.determinedBy = null; 561727e995b7bba3c57fb1e5c156d386ca11894f781v} 562727e995b7bba3c57fb1e5c156d386ca11894f781v 563727e995b7bba3c57fb1e5c156d386ca11894f781v/* --- * 564727e995b7bba3c57fb1e5c156d386ca11894f781v * P l a n n e r 565727e995b7bba3c57fb1e5c156d386ca11894f781v * --- */ 566727e995b7bba3c57fb1e5c156d386ca11894f781v 567727e995b7bba3c57fb1e5c156d386ca11894f781v/** 568727e995b7bba3c57fb1e5c156d386ca11894f781v * The DeltaBlue planner 569727e995b7bba3c57fb1e5c156d386ca11894f781v */ 570727e995b7bba3c57fb1e5c156d386ca11894f781vfunction Planner() { 571727e995b7bba3c57fb1e5c156d386ca11894f781v this.currentMark = 0; 572727e995b7bba3c57fb1e5c156d386ca11894f781v} 573727e995b7bba3c57fb1e5c156d386ca11894f781v 574727e995b7bba3c57fb1e5c156d386ca11894f781v/** 575727e995b7bba3c57fb1e5c156d386ca11894f781v * Attempt to satisfy the given constraint and, if successful, 576727e995b7bba3c57fb1e5c156d386ca11894f781v * incrementally update the dataflow graph. Details: If satifying 577727e995b7bba3c57fb1e5c156d386ca11894f781v * the constraint is successful, it may override a weaker constraint 578727e995b7bba3c57fb1e5c156d386ca11894f781v * on its output. The algorithm attempts to resatisfy that 579727e995b7bba3c57fb1e5c156d386ca11894f781v * constraint using some other method. This process is repeated 580727e995b7bba3c57fb1e5c156d386ca11894f781v * until either a) it reaches a variable that was not previously 581727e995b7bba3c57fb1e5c156d386ca11894f781v * determined by any constraint or b) it reaches a constraint that 582727e995b7bba3c57fb1e5c156d386ca11894f781v * is too weak to be satisfied using any of its methods. The 583727e995b7bba3c57fb1e5c156d386ca11894f781v * variables of constraints that have been processed are marked with 584727e995b7bba3c57fb1e5c156d386ca11894f781v * a unique mark value so that we know where we've been. This allows 585727e995b7bba3c57fb1e5c156d386ca11894f781v * the algorithm to avoid getting into an infinite loop even if the 586727e995b7bba3c57fb1e5c156d386ca11894f781v * constraint graph has an inadvertent cycle. 587727e995b7bba3c57fb1e5c156d386ca11894f781v */ 588727e995b7bba3c57fb1e5c156d386ca11894f781vPlanner.prototype.incrementalAdd = function (c) { 589727e995b7bba3c57fb1e5c156d386ca11894f781v var mark = this.newMark(); 590727e995b7bba3c57fb1e5c156d386ca11894f781v var overridden = c.satisfy(mark); 591727e995b7bba3c57fb1e5c156d386ca11894f781v while (overridden != null) 592727e995b7bba3c57fb1e5c156d386ca11894f781v overridden = overridden.satisfy(mark); 593727e995b7bba3c57fb1e5c156d386ca11894f781v} 594727e995b7bba3c57fb1e5c156d386ca11894f781v 595727e995b7bba3c57fb1e5c156d386ca11894f781v/** 596727e995b7bba3c57fb1e5c156d386ca11894f781v * Entry point for retracting a constraint. Remove the given 597727e995b7bba3c57fb1e5c156d386ca11894f781v * constraint and incrementally update the dataflow graph. 598727e995b7bba3c57fb1e5c156d386ca11894f781v * Details: Retracting the given constraint may allow some currently 599727e995b7bba3c57fb1e5c156d386ca11894f781v * unsatisfiable downstream constraint to be satisfied. We therefore collect 600727e995b7bba3c57fb1e5c156d386ca11894f781v * a list of unsatisfied downstream constraints and attempt to 601727e995b7bba3c57fb1e5c156d386ca11894f781v * satisfy each one in turn. This list is traversed by constraint 602727e995b7bba3c57fb1e5c156d386ca11894f781v * strength, strongest first, as a heuristic for avoiding 603727e995b7bba3c57fb1e5c156d386ca11894f781v * unnecessarily adding and then overriding weak constraints. 604727e995b7bba3c57fb1e5c156d386ca11894f781v * Assume: c is satisfied. 605727e995b7bba3c57fb1e5c156d386ca11894f781v */ 606727e995b7bba3c57fb1e5c156d386ca11894f781vPlanner.prototype.incrementalRemove = function (c) { 607727e995b7bba3c57fb1e5c156d386ca11894f781v var out = c.output(); 608727e995b7bba3c57fb1e5c156d386ca11894f781v c.markUnsatisfied(); 609727e995b7bba3c57fb1e5c156d386ca11894f781v c.removeFromGraph(); 610727e995b7bba3c57fb1e5c156d386ca11894f781v var unsatisfied = this.removePropagateFrom(out); 611727e995b7bba3c57fb1e5c156d386ca11894f781v var strength = Strength.REQUIRED; 612727e995b7bba3c57fb1e5c156d386ca11894f781v do { 613727e995b7bba3c57fb1e5c156d386ca11894f781v for (var i = 0; i < unsatisfied.size(); i++) { 614727e995b7bba3c57fb1e5c156d386ca11894f781v var u = unsatisfied.at(i); 615727e995b7bba3c57fb1e5c156d386ca11894f781v if (u.strength == strength) 616727e995b7bba3c57fb1e5c156d386ca11894f781v this.incrementalAdd(u); 617727e995b7bba3c57fb1e5c156d386ca11894f781v } 618727e995b7bba3c57fb1e5c156d386ca11894f781v strength = strength.nextWeaker(); 619727e995b7bba3c57fb1e5c156d386ca11894f781v } while (strength != Strength.WEAKEST); 620727e995b7bba3c57fb1e5c156d386ca11894f781v} 621727e995b7bba3c57fb1e5c156d386ca11894f781v 622727e995b7bba3c57fb1e5c156d386ca11894f781v/** 623727e995b7bba3c57fb1e5c156d386ca11894f781v * Select a previously unused mark value. 624727e995b7bba3c57fb1e5c156d386ca11894f781v */ 625727e995b7bba3c57fb1e5c156d386ca11894f781vPlanner.prototype.newMark = function () { 626727e995b7bba3c57fb1e5c156d386ca11894f781v return ++this.currentMark; 627727e995b7bba3c57fb1e5c156d386ca11894f781v} 628727e995b7bba3c57fb1e5c156d386ca11894f781v 629727e995b7bba3c57fb1e5c156d386ca11894f781v/** 630727e995b7bba3c57fb1e5c156d386ca11894f781v * Extract a plan for resatisfaction starting from the given source 631727e995b7bba3c57fb1e5c156d386ca11894f781v * constraints, usually a set of input constraints. This method 632727e995b7bba3c57fb1e5c156d386ca11894f781v * assumes that stay optimization is desired; the plan will contain 633727e995b7bba3c57fb1e5c156d386ca11894f781v * only constraints whose output variables are not stay. Constraints 634727e995b7bba3c57fb1e5c156d386ca11894f781v * that do no computation, such as stay and edit constraints, are 635727e995b7bba3c57fb1e5c156d386ca11894f781v * not included in the plan. 636727e995b7bba3c57fb1e5c156d386ca11894f781v * Details: The outputs of a constraint are marked when it is added 637727e995b7bba3c57fb1e5c156d386ca11894f781v * to the plan under construction. A constraint may be appended to 638727e995b7bba3c57fb1e5c156d386ca11894f781v * the plan when all its input variables are known. A variable is 639727e995b7bba3c57fb1e5c156d386ca11894f781v * known if either a) the variable is marked (indicating that has 640727e995b7bba3c57fb1e5c156d386ca11894f781v * been computed by a constraint appearing earlier in the plan), b) 641727e995b7bba3c57fb1e5c156d386ca11894f781v * the variable is 'stay' (i.e. it is a constant at plan execution 642727e995b7bba3c57fb1e5c156d386ca11894f781v * time), or c) the variable is not determined by any 643727e995b7bba3c57fb1e5c156d386ca11894f781v * constraint. The last provision is for past states of history 644727e995b7bba3c57fb1e5c156d386ca11894f781v * variables, which are not stay but which are also not computed by 645727e995b7bba3c57fb1e5c156d386ca11894f781v * any constraint. 646727e995b7bba3c57fb1e5c156d386ca11894f781v * Assume: sources are all satisfied. 647727e995b7bba3c57fb1e5c156d386ca11894f781v */ 648727e995b7bba3c57fb1e5c156d386ca11894f781vPlanner.prototype.makePlan = function (sources) { 649727e995b7bba3c57fb1e5c156d386ca11894f781v var mark = this.newMark(); 650727e995b7bba3c57fb1e5c156d386ca11894f781v var plan = new Plan(); 651727e995b7bba3c57fb1e5c156d386ca11894f781v var todo = sources; 652727e995b7bba3c57fb1e5c156d386ca11894f781v while (todo.size() > 0) { 653727e995b7bba3c57fb1e5c156d386ca11894f781v var c = todo.removeFirst(); 654727e995b7bba3c57fb1e5c156d386ca11894f781v if (c.output().mark != mark && c.inputsKnown(mark)) { 655727e995b7bba3c57fb1e5c156d386ca11894f781v plan.addConstraint(c); 656727e995b7bba3c57fb1e5c156d386ca11894f781v c.output().mark = mark; 657727e995b7bba3c57fb1e5c156d386ca11894f781v this.addConstraintsConsumingTo(c.output(), todo); 658727e995b7bba3c57fb1e5c156d386ca11894f781v } 659727e995b7bba3c57fb1e5c156d386ca11894f781v } 660727e995b7bba3c57fb1e5c156d386ca11894f781v return plan; 661727e995b7bba3c57fb1e5c156d386ca11894f781v} 662727e995b7bba3c57fb1e5c156d386ca11894f781v 663727e995b7bba3c57fb1e5c156d386ca11894f781v/** 664727e995b7bba3c57fb1e5c156d386ca11894f781v * Extract a plan for resatisfying starting from the output of the 665727e995b7bba3c57fb1e5c156d386ca11894f781v * given constraints, usually a set of input constraints. 666727e995b7bba3c57fb1e5c156d386ca11894f781v */ 667727e995b7bba3c57fb1e5c156d386ca11894f781vPlanner.prototype.extractPlanFromConstraints = function (constraints) { 668727e995b7bba3c57fb1e5c156d386ca11894f781v var sources = new OrderedCollection(); 669727e995b7bba3c57fb1e5c156d386ca11894f781v for (var i = 0; i < constraints.size(); i++) { 670727e995b7bba3c57fb1e5c156d386ca11894f781v var c = constraints.at(i); 671727e995b7bba3c57fb1e5c156d386ca11894f781v if (c.isInput() && c.isSatisfied()) 672727e995b7bba3c57fb1e5c156d386ca11894f781v // not in plan already and eligible for inclusion 673727e995b7bba3c57fb1e5c156d386ca11894f781v sources.add(c); 674727e995b7bba3c57fb1e5c156d386ca11894f781v } 675727e995b7bba3c57fb1e5c156d386ca11894f781v return this.makePlan(sources); 676727e995b7bba3c57fb1e5c156d386ca11894f781v} 677727e995b7bba3c57fb1e5c156d386ca11894f781v 678727e995b7bba3c57fb1e5c156d386ca11894f781v/** 679727e995b7bba3c57fb1e5c156d386ca11894f781v * Recompute the walkabout strengths and stay flags of all variables 680727e995b7bba3c57fb1e5c156d386ca11894f781v * downstream of the given constraint and recompute the actual 681727e995b7bba3c57fb1e5c156d386ca11894f781v * values of all variables whose stay flag is true. If a cycle is 682727e995b7bba3c57fb1e5c156d386ca11894f781v * detected, remove the given constraint and answer 683727e995b7bba3c57fb1e5c156d386ca11894f781v * false. Otherwise, answer true. 684727e995b7bba3c57fb1e5c156d386ca11894f781v * Details: Cycles are detected when a marked variable is 685727e995b7bba3c57fb1e5c156d386ca11894f781v * encountered downstream of the given constraint. The sender is 686727e995b7bba3c57fb1e5c156d386ca11894f781v * assumed to have marked the inputs of the given constraint with 687727e995b7bba3c57fb1e5c156d386ca11894f781v * the given mark. Thus, encountering a marked node downstream of 688727e995b7bba3c57fb1e5c156d386ca11894f781v * the output constraint means that there is a path from the 689727e995b7bba3c57fb1e5c156d386ca11894f781v * constraint's output to one of its inputs. 690727e995b7bba3c57fb1e5c156d386ca11894f781v */ 691727e995b7bba3c57fb1e5c156d386ca11894f781vPlanner.prototype.addPropagate = function (c, mark) { 692727e995b7bba3c57fb1e5c156d386ca11894f781v var todo = new OrderedCollection(); 693727e995b7bba3c57fb1e5c156d386ca11894f781v todo.add(c); 694727e995b7bba3c57fb1e5c156d386ca11894f781v while (todo.size() > 0) { 695727e995b7bba3c57fb1e5c156d386ca11894f781v var d = todo.removeFirst(); 696727e995b7bba3c57fb1e5c156d386ca11894f781v if (d.output().mark == mark) { 697727e995b7bba3c57fb1e5c156d386ca11894f781v this.incrementalRemove(c); 698727e995b7bba3c57fb1e5c156d386ca11894f781v return false; 699727e995b7bba3c57fb1e5c156d386ca11894f781v } 700727e995b7bba3c57fb1e5c156d386ca11894f781v d.recalculate(); 701727e995b7bba3c57fb1e5c156d386ca11894f781v this.addConstraintsConsumingTo(d.output(), todo); 702727e995b7bba3c57fb1e5c156d386ca11894f781v } 703727e995b7bba3c57fb1e5c156d386ca11894f781v return true; 704727e995b7bba3c57fb1e5c156d386ca11894f781v} 705727e995b7bba3c57fb1e5c156d386ca11894f781v 706727e995b7bba3c57fb1e5c156d386ca11894f781v 707727e995b7bba3c57fb1e5c156d386ca11894f781v/** 708727e995b7bba3c57fb1e5c156d386ca11894f781v * Update the walkabout strengths and stay flags of all variables 709727e995b7bba3c57fb1e5c156d386ca11894f781v * downstream of the given constraint. Answer a collection of 710727e995b7bba3c57fb1e5c156d386ca11894f781v * unsatisfied constraints sorted in order of decreasing strength. 711727e995b7bba3c57fb1e5c156d386ca11894f781v */ 712727e995b7bba3c57fb1e5c156d386ca11894f781vPlanner.prototype.removePropagateFrom = function (out) { 713727e995b7bba3c57fb1e5c156d386ca11894f781v out.determinedBy = null; 714727e995b7bba3c57fb1e5c156d386ca11894f781v out.walkStrength = Strength.WEAKEST; 715727e995b7bba3c57fb1e5c156d386ca11894f781v out.stay = true; 716727e995b7bba3c57fb1e5c156d386ca11894f781v var unsatisfied = new OrderedCollection(); 717727e995b7bba3c57fb1e5c156d386ca11894f781v var todo = new OrderedCollection(); 718727e995b7bba3c57fb1e5c156d386ca11894f781v todo.add(out); 719727e995b7bba3c57fb1e5c156d386ca11894f781v while (todo.size() > 0) { 720727e995b7bba3c57fb1e5c156d386ca11894f781v var v = todo.removeFirst(); 721727e995b7bba3c57fb1e5c156d386ca11894f781v for (var i = 0; i < v.constraints.size(); i++) { 722727e995b7bba3c57fb1e5c156d386ca11894f781v var c = v.constraints.at(i); 723727e995b7bba3c57fb1e5c156d386ca11894f781v if (!c.isSatisfied()) 724727e995b7bba3c57fb1e5c156d386ca11894f781v unsatisfied.add(c); 725727e995b7bba3c57fb1e5c156d386ca11894f781v } 726727e995b7bba3c57fb1e5c156d386ca11894f781v var determining = v.determinedBy; 727727e995b7bba3c57fb1e5c156d386ca11894f781v for (var i = 0; i < v.constraints.size(); i++) { 728727e995b7bba3c57fb1e5c156d386ca11894f781v var next = v.constraints.at(i); 729727e995b7bba3c57fb1e5c156d386ca11894f781v if (next != determining && next.isSatisfied()) { 730727e995b7bba3c57fb1e5c156d386ca11894f781v next.recalculate(); 731727e995b7bba3c57fb1e5c156d386ca11894f781v todo.add(next.output()); 732727e995b7bba3c57fb1e5c156d386ca11894f781v } 733727e995b7bba3c57fb1e5c156d386ca11894f781v } 734727e995b7bba3c57fb1e5c156d386ca11894f781v } 735727e995b7bba3c57fb1e5c156d386ca11894f781v return unsatisfied; 736727e995b7bba3c57fb1e5c156d386ca11894f781v} 737727e995b7bba3c57fb1e5c156d386ca11894f781v 738727e995b7bba3c57fb1e5c156d386ca11894f781vPlanner.prototype.addConstraintsConsumingTo = function (v, coll) { 739727e995b7bba3c57fb1e5c156d386ca11894f781v var determining = v.determinedBy; 740727e995b7bba3c57fb1e5c156d386ca11894f781v var cc = v.constraints; 741727e995b7bba3c57fb1e5c156d386ca11894f781v for (var i = 0; i < cc.size(); i++) { 742727e995b7bba3c57fb1e5c156d386ca11894f781v var c = cc.at(i); 743727e995b7bba3c57fb1e5c156d386ca11894f781v if (c != determining && c.isSatisfied()) 744727e995b7bba3c57fb1e5c156d386ca11894f781v coll.add(c); 745727e995b7bba3c57fb1e5c156d386ca11894f781v } 746727e995b7bba3c57fb1e5c156d386ca11894f781v} 747727e995b7bba3c57fb1e5c156d386ca11894f781v 748727e995b7bba3c57fb1e5c156d386ca11894f781v/* --- * 749727e995b7bba3c57fb1e5c156d386ca11894f781v * P l a n 750727e995b7bba3c57fb1e5c156d386ca11894f781v * --- */ 751727e995b7bba3c57fb1e5c156d386ca11894f781v 752727e995b7bba3c57fb1e5c156d386ca11894f781v/** 753727e995b7bba3c57fb1e5c156d386ca11894f781v * A Plan is an ordered list of constraints to be executed in sequence 754727e995b7bba3c57fb1e5c156d386ca11894f781v * to resatisfy all currently satisfiable constraints in the face of 755727e995b7bba3c57fb1e5c156d386ca11894f781v * one or more changing inputs. 756727e995b7bba3c57fb1e5c156d386ca11894f781v */ 757727e995b7bba3c57fb1e5c156d386ca11894f781vfunction Plan() { 758727e995b7bba3c57fb1e5c156d386ca11894f781v this.v = new OrderedCollection(); 759727e995b7bba3c57fb1e5c156d386ca11894f781v} 760727e995b7bba3c57fb1e5c156d386ca11894f781v 761727e995b7bba3c57fb1e5c156d386ca11894f781vPlan.prototype.addConstraint = function (c) { 762727e995b7bba3c57fb1e5c156d386ca11894f781v this.v.add(c); 763727e995b7bba3c57fb1e5c156d386ca11894f781v} 764727e995b7bba3c57fb1e5c156d386ca11894f781v 765727e995b7bba3c57fb1e5c156d386ca11894f781vPlan.prototype.size = function () { 766727e995b7bba3c57fb1e5c156d386ca11894f781v return this.v.size(); 767727e995b7bba3c57fb1e5c156d386ca11894f781v} 768727e995b7bba3c57fb1e5c156d386ca11894f781v 769727e995b7bba3c57fb1e5c156d386ca11894f781vPlan.prototype.constraintAt = function (index) { 770727e995b7bba3c57fb1e5c156d386ca11894f781v return this.v.at(index); 771727e995b7bba3c57fb1e5c156d386ca11894f781v} 772727e995b7bba3c57fb1e5c156d386ca11894f781v 773727e995b7bba3c57fb1e5c156d386ca11894f781vPlan.prototype.execute = function () { 774727e995b7bba3c57fb1e5c156d386ca11894f781v for (var i = 0; i < this.size(); i++) { 775727e995b7bba3c57fb1e5c156d386ca11894f781v var c = this.constraintAt(i); 776727e995b7bba3c57fb1e5c156d386ca11894f781v c.execute(); 777727e995b7bba3c57fb1e5c156d386ca11894f781v } 778727e995b7bba3c57fb1e5c156d386ca11894f781v} 779727e995b7bba3c57fb1e5c156d386ca11894f781v 780727e995b7bba3c57fb1e5c156d386ca11894f781v/* --- * 781727e995b7bba3c57fb1e5c156d386ca11894f781v * M a i n 782727e995b7bba3c57fb1e5c156d386ca11894f781v * --- */ 783727e995b7bba3c57fb1e5c156d386ca11894f781v 784727e995b7bba3c57fb1e5c156d386ca11894f781v/** 785727e995b7bba3c57fb1e5c156d386ca11894f781v * This is the standard DeltaBlue benchmark. A long chain of equality 786727e995b7bba3c57fb1e5c156d386ca11894f781v * constraints is constructed with a stay constraint on one end. An 787727e995b7bba3c57fb1e5c156d386ca11894f781v * edit constraint is then added to the opposite end and the time is 788727e995b7bba3c57fb1e5c156d386ca11894f781v * measured for adding and removing this constraint, and extracting 789727e995b7bba3c57fb1e5c156d386ca11894f781v * and executing a constraint satisfaction plan. There are two cases. 790727e995b7bba3c57fb1e5c156d386ca11894f781v * In case 1, the added constraint is stronger than the stay 791727e995b7bba3c57fb1e5c156d386ca11894f781v * constraint and values must propagate down the entire length of the 792727e995b7bba3c57fb1e5c156d386ca11894f781v * chain. In case 2, the added constraint is weaker than the stay 793727e995b7bba3c57fb1e5c156d386ca11894f781v * constraint so it cannot be accomodated. The cost in this case is, 794727e995b7bba3c57fb1e5c156d386ca11894f781v * of course, very low. Typical situations lie somewhere between these 795727e995b7bba3c57fb1e5c156d386ca11894f781v * two extremes. 796727e995b7bba3c57fb1e5c156d386ca11894f781v */ 797727e995b7bba3c57fb1e5c156d386ca11894f781vfunction chainTest(n) { 798727e995b7bba3c57fb1e5c156d386ca11894f781v planner = new Planner(); 799727e995b7bba3c57fb1e5c156d386ca11894f781v var prev = null, first = null, last = null; 800727e995b7bba3c57fb1e5c156d386ca11894f781v 801727e995b7bba3c57fb1e5c156d386ca11894f781v // Build chain of n equality constraints 802727e995b7bba3c57fb1e5c156d386ca11894f781v for (var i = 0; i <= n; i++) { 803727e995b7bba3c57fb1e5c156d386ca11894f781v var name = "v" + i; 804727e995b7bba3c57fb1e5c156d386ca11894f781v var v = new Variable(name); 805727e995b7bba3c57fb1e5c156d386ca11894f781v if (prev != null) 806727e995b7bba3c57fb1e5c156d386ca11894f781v new EqualityConstraint(prev, v, Strength.REQUIRED); 807727e995b7bba3c57fb1e5c156d386ca11894f781v if (i == 0) first = v; 808727e995b7bba3c57fb1e5c156d386ca11894f781v if (i == n) last = v; 809727e995b7bba3c57fb1e5c156d386ca11894f781v prev = v; 810727e995b7bba3c57fb1e5c156d386ca11894f781v } 811727e995b7bba3c57fb1e5c156d386ca11894f781v 812727e995b7bba3c57fb1e5c156d386ca11894f781v new StayConstraint(last, Strength.STRONG_DEFAULT); 813727e995b7bba3c57fb1e5c156d386ca11894f781v var edit = new EditConstraint(first, Strength.PREFERRED); 814727e995b7bba3c57fb1e5c156d386ca11894f781v var edits = new OrderedCollection(); 815727e995b7bba3c57fb1e5c156d386ca11894f781v edits.add(edit); 816727e995b7bba3c57fb1e5c156d386ca11894f781v var plan = planner.extractPlanFromConstraints(edits); 817727e995b7bba3c57fb1e5c156d386ca11894f781v for (var i = 0; i < 100; i++) { 818727e995b7bba3c57fb1e5c156d386ca11894f781v first.value = i; 819727e995b7bba3c57fb1e5c156d386ca11894f781v plan.execute(); 820727e995b7bba3c57fb1e5c156d386ca11894f781v if (last.value != i) 821727e995b7bba3c57fb1e5c156d386ca11894f781v alert("Chain test failed."); 822727e995b7bba3c57fb1e5c156d386ca11894f781v } 823727e995b7bba3c57fb1e5c156d386ca11894f781v} 824727e995b7bba3c57fb1e5c156d386ca11894f781v 825727e995b7bba3c57fb1e5c156d386ca11894f781v/** 826727e995b7bba3c57fb1e5c156d386ca11894f781v * This test constructs a two sets of variables related to each 827727e995b7bba3c57fb1e5c156d386ca11894f781v * other by a simple linear transformation (scale and offset). The 828727e995b7bba3c57fb1e5c156d386ca11894f781v * time is measured to change a variable on either side of the 829727e995b7bba3c57fb1e5c156d386ca11894f781v * mapping and to change the scale and offset factors. 830727e995b7bba3c57fb1e5c156d386ca11894f781v */ 831727e995b7bba3c57fb1e5c156d386ca11894f781vfunction projectionTest(n) { 832727e995b7bba3c57fb1e5c156d386ca11894f781v planner = new Planner(); 833727e995b7bba3c57fb1e5c156d386ca11894f781v var scale = new Variable("scale", 10); 834727e995b7bba3c57fb1e5c156d386ca11894f781v var offset = new Variable("offset", 1000); 835727e995b7bba3c57fb1e5c156d386ca11894f781v var src = null, dst = null; 836727e995b7bba3c57fb1e5c156d386ca11894f781v 837727e995b7bba3c57fb1e5c156d386ca11894f781v var dests = new OrderedCollection(); 838727e995b7bba3c57fb1e5c156d386ca11894f781v for (var i = 0; i < n; i++) { 839727e995b7bba3c57fb1e5c156d386ca11894f781v src = new Variable("src" + i, i); 840727e995b7bba3c57fb1e5c156d386ca11894f781v dst = new Variable("dst" + i, i); 841727e995b7bba3c57fb1e5c156d386ca11894f781v dests.add(dst); 842727e995b7bba3c57fb1e5c156d386ca11894f781v new StayConstraint(src, Strength.NORMAL); 843727e995b7bba3c57fb1e5c156d386ca11894f781v new ScaleConstraint(src, scale, offset, dst, Strength.REQUIRED); 844727e995b7bba3c57fb1e5c156d386ca11894f781v } 845727e995b7bba3c57fb1e5c156d386ca11894f781v 846727e995b7bba3c57fb1e5c156d386ca11894f781v change(src, 17); 847727e995b7bba3c57fb1e5c156d386ca11894f781v if (dst.value != 1170) alert("Projection 1 failed"); 848727e995b7bba3c57fb1e5c156d386ca11894f781v change(dst, 1050); 849727e995b7bba3c57fb1e5c156d386ca11894f781v if (src.value != 5) alert("Projection 2 failed"); 850727e995b7bba3c57fb1e5c156d386ca11894f781v change(scale, 5); 851727e995b7bba3c57fb1e5c156d386ca11894f781v for (var i = 0; i < n - 1; i++) { 852727e995b7bba3c57fb1e5c156d386ca11894f781v if (dests.at(i).value != i * 5 + 1000) 853727e995b7bba3c57fb1e5c156d386ca11894f781v alert("Projection 3 failed"); 854727e995b7bba3c57fb1e5c156d386ca11894f781v } 855727e995b7bba3c57fb1e5c156d386ca11894f781v change(offset, 2000); 856727e995b7bba3c57fb1e5c156d386ca11894f781v for (var i = 0; i < n - 1; i++) { 857727e995b7bba3c57fb1e5c156d386ca11894f781v if (dests.at(i).value != i * 5 + 2000) 858727e995b7bba3c57fb1e5c156d386ca11894f781v alert("Projection 4 failed"); 859727e995b7bba3c57fb1e5c156d386ca11894f781v } 860727e995b7bba3c57fb1e5c156d386ca11894f781v} 861727e995b7bba3c57fb1e5c156d386ca11894f781v 862727e995b7bba3c57fb1e5c156d386ca11894f781vfunction change(v, newValue) { 863727e995b7bba3c57fb1e5c156d386ca11894f781v var edit = new EditConstraint(v, Strength.PREFERRED); 864727e995b7bba3c57fb1e5c156d386ca11894f781v var edits = new OrderedCollection(); 865727e995b7bba3c57fb1e5c156d386ca11894f781v edits.add(edit); 866727e995b7bba3c57fb1e5c156d386ca11894f781v var plan = planner.extractPlanFromConstraints(edits); 867727e995b7bba3c57fb1e5c156d386ca11894f781v for (var i = 0; i < 10; i++) { 868727e995b7bba3c57fb1e5c156d386ca11894f781v v.value = newValue; 869727e995b7bba3c57fb1e5c156d386ca11894f781v plan.execute(); 870727e995b7bba3c57fb1e5c156d386ca11894f781v } 871727e995b7bba3c57fb1e5c156d386ca11894f781v edit.destroyConstraint(); 872727e995b7bba3c57fb1e5c156d386ca11894f781v} 873727e995b7bba3c57fb1e5c156d386ca11894f781v 874727e995b7bba3c57fb1e5c156d386ca11894f781v// Global variable holding the current planner. 875727e995b7bba3c57fb1e5c156d386ca11894f781vvar planner = null; 876727e995b7bba3c57fb1e5c156d386ca11894f781v 877727e995b7bba3c57fb1e5c156d386ca11894f781vfunction deltaBlue() { 878727e995b7bba3c57fb1e5c156d386ca11894f781v chainTest(100); 879727e995b7bba3c57fb1e5c156d386ca11894f781v projectionTest(100); 880727e995b7bba3c57fb1e5c156d386ca11894f781v} 881