15c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// Copyright 2008 the V8 project authors. All rights reserved. 25c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// Copyright 1996 John Maloney and Mario Wolczko. 35c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 45c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// This program is free software; you can redistribute it and/or modify 55c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// it under the terms of the GNU General Public License as published by 65c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// the Free Software Foundation; either version 2 of the License, or 75c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// (at your option) any later version. 85c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// 95c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// This program is distributed in the hope that it will be useful, 105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// but WITHOUT ANY WARRANTY; without even the implied warranty of 115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// GNU General Public License for more details. 135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// 145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// You should have received a copy of the GNU General Public License 155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// along with this program; if not, write to the Free Software 165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA 175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// This implementation of the DeltaBlue benchmark is derived 205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// from the Smalltalk implementation by John Maloney and Mario 215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// Wolczko. Some parts have been translated directly, whereas 225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// others have been modified more aggresively to make it feel 235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// more like a JavaScript program. 245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)/** 265c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * A JavaScript implementation of the DeltaBlue constrain-solving 275c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * algorithm, as described in: 285c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * 295c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * "The DeltaBlue Algorithm: An Incremental Constraint Hierarchy Solver" 305c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * Bjorn N. Freeman-Benson and John Maloney 315c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * January 1990 Communications of the ACM, 325c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * also available as University of Washington TR 89-08-06. 335c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * 345c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * Beware: this benchmark is written in a grotesque style where 355c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * the constraint model is built by side-effects from constructors. 365c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * I've kept it this way to avoid deviating too much from the original 375c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * implementation. 385c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) */ 395c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 405c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 415c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)/* --- O b j e c t M o d e l --- */ 425c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 435c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)Object.prototype.inherits = function (shuper) { 445c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) function Inheriter() { } 455c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) Inheriter.prototype = shuper.prototype; 465c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) this.prototype = new Inheriter(); 475c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) this.superConstructor = shuper; 485c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 495c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 505c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)function OrderedCollection() { 515c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) this.elms = new Array(); 525c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 535c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 545c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)OrderedCollection.prototype.add = function (elm) { 555c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) this.elms.push(elm); 565c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 575c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 585c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)OrderedCollection.prototype.at = function (index) { 595c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return this.elms[index]; 605c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 615c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 625c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)OrderedCollection.prototype.size = function () { 635c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return this.elms.length; 645c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 655c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 665c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)OrderedCollection.prototype.removeFirst = function () { 675c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return this.elms.pop(); 685c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 695c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 705c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)OrderedCollection.prototype.remove = function (elm) { 715c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) var index = 0, skipped = 0; 725c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) for (var i = 0; i < this.elms.length; i++) { 735c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) var value = this.elms[i]; 745c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (value != elm) { 755c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) this.elms[index] = value; 765c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) index++; 775c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } else { 785c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) skipped++; 795c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 805c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 815c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) for (var i = 0; i < skipped; i++) 825c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) this.elms.pop(); 835c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 845c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 855c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)/* --- * 865c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * S t r e n g t h 875c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * --- */ 885c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 895c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)/** 905c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * Strengths are used to measure the relative importance of constraints. 915c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * New strengths may be inserted in the strength hierarchy without 925c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * disrupting current constraints. Strengths cannot be created outside 935c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * this class, so pointer comparison can be used for value comparison. 945c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) */ 955c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)function Strength(strengthValue, name) { 965c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) this.strengthValue = strengthValue; 975c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) this.name = name; 985c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 995c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1005c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)Strength.stronger = function (s1, s2) { 1015c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return s1.strengthValue < s2.strengthValue; 1025c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 1035c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1045c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)Strength.weaker = function (s1, s2) { 1055c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return s1.strengthValue > s2.strengthValue; 1065c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 1075c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1085c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)Strength.weakestOf = function (s1, s2) { 1095c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return this.weaker(s1, s2) ? s1 : s2; 1105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 1115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)Strength.strongest = function (s1, s2) { 1135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return this.stronger(s1, s2) ? s1 : s2; 1145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 1155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)Strength.prototype.nextWeaker = function () { 1175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) switch (this.strengthValue) { 1185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) case 0: return Strength.WEAKEST; 1195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) case 1: return Strength.WEAK_DEFAULT; 1205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) case 2: return Strength.NORMAL; 1215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) case 3: return Strength.STRONG_DEFAULT; 1225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) case 4: return Strength.PREFERRED; 1235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) case 5: return Strength.REQUIRED; 1245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 1255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 1265c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1275c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// Strength constants. 1285c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)Strength.REQUIRED = new Strength(0, "required"); 1295c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)Strength.STONG_PREFERRED = new Strength(1, "strongPreferred"); 1305c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)Strength.PREFERRED = new Strength(2, "preferred"); 1315c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)Strength.STRONG_DEFAULT = new Strength(3, "strongDefault"); 1325c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)Strength.NORMAL = new Strength(4, "normal"); 1335c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)Strength.WEAK_DEFAULT = new Strength(5, "weakDefault"); 1345c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)Strength.WEAKEST = new Strength(6, "weakest"); 1355c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1365c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)/* --- * 1375c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * C o n s t r a i n t 1385c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * --- */ 1395c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1405c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)/** 1415c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * An abstract class representing a system-maintainable relationship 1425c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * (or "constraint") between a set of variables. A constraint supplies 1435c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * a strength instance variable; concrete subclasses provide a means 1445c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * of storing the constrained variables and other information required 1455c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * to represent a constraint. 1465c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) */ 1475c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)function Constraint(strength) { 1485c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) this.strength = strength; 1495c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 1505c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1515c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)/** 1525c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * Activate this constraint and attempt to satisfy it. 1535c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) */ 1545c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)Constraint.prototype.addConstraint = function () { 1555c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) this.addToGraph(); 1565c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) planner.incrementalAdd(this); 1575c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 1585c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1595c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)/** 1605c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * Attempt to find a way to enforce this constraint. If successful, 1615c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * record the solution, perhaps modifying the current dataflow 1625c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * graph. Answer the constraint that this constraint overrides, if 1635c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * there is one, or nil, if there isn't. 1645c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * Assume: I am not already satisfied. 1655c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) */ 1665c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)Constraint.prototype.satisfy = function (mark) { 1675c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) this.chooseMethod(mark); 1685c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (!this.isSatisfied()) { 1695c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (this.strength == Strength.REQUIRED) 1705c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) alert("Could not satisfy a required constraint!"); 1715c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return null; 1725c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 1735c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) this.markInputs(mark); 1745c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) var out = this.output(); 1755c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) var overridden = out.determinedBy; 1765c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (overridden != null) overridden.markUnsatisfied(); 1775c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) out.determinedBy = this; 1785c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (!planner.addPropagate(this, mark)) 1795c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) alert("Cycle encountered"); 1805c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) out.mark = mark; 1815c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return overridden; 1825c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 1835c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1845c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)Constraint.prototype.destroyConstraint = function () { 1855c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (this.isSatisfied()) planner.incrementalRemove(this); 1865c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) else this.removeFromGraph(); 1875c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 1885c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1895c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)/** 1905c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * Normal constraints are not input constraints. An input constraint 1915c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * is one that depends on external state, such as the mouse, the 1925c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * keybord, a clock, or some arbitraty piece of imperative code. 1935c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) */ 1945c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)Constraint.prototype.isInput = function () { 1955c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return false; 1965c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 1975c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1985c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)/* --- * 1995c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * U n a r y C o n s t r a i n t 2005c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * --- */ 2015c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2025c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)/** 2035c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * Abstract superclass for constraints having a single possible output 2045c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * variable. 2055c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) */ 2065c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)function UnaryConstraint(v, strength) { 2075c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) UnaryConstraint.superConstructor.call(this, strength); 2085c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) this.myOutput = v; 2095c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) this.satisfied = false; 2105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) this.addConstraint(); 2115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 2125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)UnaryConstraint.inherits(Constraint); 2145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)/** 2165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * Adds this constraint to the constraint graph 2175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) */ 2185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)UnaryConstraint.prototype.addToGraph = function () { 2195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) this.myOutput.addConstraint(this); 2205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) this.satisfied = false; 2215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 2225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)/** 2245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * Decides if this constraint can be satisfied and records that 2255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * decision. 2265c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) */ 2275c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)UnaryConstraint.prototype.chooseMethod = function (mark) { 2285c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) this.satisfied = (this.myOutput.mark != mark) 2295c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) && Strength.stronger(this.strength, this.myOutput.walkStrength); 2305c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 2315c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2325c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)/** 2335c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * Returns true if this constraint is satisfied in the current solution. 2345c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) */ 2355c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)UnaryConstraint.prototype.isSatisfied = function () { 2365c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return this.satisfied; 2375c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 2385c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2395c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)UnaryConstraint.prototype.markInputs = function (mark) { 2405c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // has no inputs 2415c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 2425c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2435c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)/** 2445c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * Returns the current output variable. 2455c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) */ 2465c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)UnaryConstraint.prototype.output = function () { 2475c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return this.myOutput; 2485c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 2495c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2505c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)/** 2515c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * Calculate the walkabout strength, the stay flag, and, if it is 2525c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * 'stay', the value for the current output of this constraint. Assume 2535c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * this constraint is satisfied. 2545c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) */ 2555c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)UnaryConstraint.prototype.recalculate = function () { 2565c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) this.myOutput.walkStrength = this.strength; 2575c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) this.myOutput.stay = !this.isInput(); 2585c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (this.myOutput.stay) this.execute(); // Stay optimization 2595c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 2605c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2615c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)/** 2625c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * Records that this constraint is unsatisfied 2635c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) */ 2645c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)UnaryConstraint.prototype.markUnsatisfied = function () { 2655c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) this.satisfied = false; 2665c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 2675c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2685c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)UnaryConstraint.prototype.inputsKnown = function () { 2695c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return true; 2705c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 2715c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2725c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)UnaryConstraint.prototype.removeFromGraph = function () { 2735c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (this.myOutput != null) this.myOutput.removeConstraint(this); 2745c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) this.satisfied = false; 2755c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 2765c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2775c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)/* --- * 2785c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * S t a y C o n s t r a i n t 2795c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * --- */ 2805c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2815c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)/** 2825c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * Variables that should, with some level of preference, stay the same. 2835c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * Planners may exploit the fact that instances, if satisfied, will not 2845c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * change their output during plan execution. This is called "stay 2855c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * optimization". 2865c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) */ 2875c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)function StayConstraint(v, str) { 2885c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) StayConstraint.superConstructor.call(this, v, str); 2895c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 2905c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2915c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)StayConstraint.inherits(UnaryConstraint); 2925c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2935c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)StayConstraint.prototype.execute = function () { 2945c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Stay constraints do nothing 2955c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 2965c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 2975c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)/* --- * 2985c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * E d i t C o n s t r a i n t 2995c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * --- */ 3005c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3015c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)/** 3025c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * A unary input constraint used to mark a variable that the client 3035c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * wishes to change. 3045c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) */ 3055c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)function EditConstraint(v, str) { 3065c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) EditConstraint.superConstructor.call(this, v, str); 3075c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 3085c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3095c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)EditConstraint.inherits(UnaryConstraint); 3105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)/** 3125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * Edits indicate that a variable is to be changed by imperative code. 3135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) */ 3145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)EditConstraint.prototype.isInput = function () { 3155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return true; 3165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 3175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)EditConstraint.prototype.execute = function () { 3195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Edit constraints do nothing 3205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 3215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)/* --- * 3235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * B i n a r y C o n s t r a i n t 3245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * --- */ 3255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3265c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)var Direction = new Object(); 3275c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)Direction.NONE = 0; 3285c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)Direction.FORWARD = 1; 3295c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)Direction.BACKWARD = -1; 3305c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3315c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)/** 3325c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * Abstract superclass for constraints having two possible output 3335c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * variables. 3345c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) */ 3355c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)function BinaryConstraint(var1, var2, strength) { 3365c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) BinaryConstraint.superConstructor.call(this, strength); 3375c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) this.v1 = var1; 3385c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) this.v2 = var2; 3395c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) this.direction = Direction.NONE; 3405c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) this.addConstraint(); 3415c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 3425c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3435c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)BinaryConstraint.inherits(Constraint); 3445c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3455c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)/** 3465c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * Decides if this constratint can be satisfied and which way it 3475c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * should flow based on the relative strength of the variables related, 3485c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * and record that decision. 3495c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) */ 3505c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)BinaryConstraint.prototype.chooseMethod = function (mark) { 3515c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (this.v1.mark == mark) { 3525c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) this.direction = (this.v1.mark != mark && Strength.stronger(this.strength, this.v2.walkStrength)) 3535c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ? Direction.FORWARD 3545c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) : Direction.NONE; 3555c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 3565c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (this.v2.mark == mark) { 3575c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) this.direction = (this.v1.mark != mark && Strength.stronger(this.strength, this.v1.walkStrength)) 3585c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ? Direction.BACKWARD 3595c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) : Direction.NONE; 3605c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 3615c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (Strength.weaker(this.v1.walkStrength, this.v2.walkStrength)) { 3625c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) this.direction = Strength.stronger(this.strength, this.v1.walkStrength) 3635c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ? Direction.BACKWARD 3645c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) : Direction.NONE; 3655c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } else { 3665c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) this.direction = Strength.stronger(this.strength, this.v2.walkStrength) 3675c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ? Direction.FORWARD 3685c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) : Direction.BACKWARD 3695c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 3705c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 3715c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3725c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)/** 3735c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * Add this constraint to the constraint graph 3745c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) */ 3755c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)BinaryConstraint.prototype.addToGraph = function () { 3765c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) this.v1.addConstraint(this); 3775c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) this.v2.addConstraint(this); 3785c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) this.direction = Direction.NONE; 3795c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 3805c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3815c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)/** 3825c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * Answer true if this constraint is satisfied in the current solution. 3835c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) */ 3845c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)BinaryConstraint.prototype.isSatisfied = function () { 3855c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return this.direction != Direction.NONE; 3865c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 3875c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3885c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)/** 3895c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * Mark the input variable with the given mark. 3905c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) */ 3915c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)BinaryConstraint.prototype.markInputs = function (mark) { 3925c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) this.input().mark = mark; 3935c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 3945c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 3955c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)/** 3965c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * Returns the current input variable 3975c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) */ 3985c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)BinaryConstraint.prototype.input = function () { 3995c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return (this.direction == Direction.FORWARD) ? this.v1 : this.v2; 4005c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 4015c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4025c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)/** 4035c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * Returns the current output variable 4045c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) */ 4055c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)BinaryConstraint.prototype.output = function () { 4065c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return (this.direction == Direction.FORWARD) ? this.v2 : this.v1; 4075c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 4085c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4095c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)/** 4105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * Calculate the walkabout strength, the stay flag, and, if it is 4115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * 'stay', the value for the current output of this 4125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * constraint. Assume this constraint is satisfied. 4135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) */ 4145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)BinaryConstraint.prototype.recalculate = function () { 4155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) var ihn = this.input(), out = this.output(); 4165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) out.walkStrength = Strength.weakestOf(this.strength, ihn.walkStrength); 4175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) out.stay = ihn.stay; 4185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (out.stay) this.execute(); 4195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 4205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)/** 4225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * Record the fact that this constraint is unsatisfied. 4235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) */ 4245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)BinaryConstraint.prototype.markUnsatisfied = function () { 4255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) this.direction = Direction.NONE; 4265c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 4275c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4285c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)BinaryConstraint.prototype.inputsKnown = function (mark) { 4295c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) var i = this.input(); 4305c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return i.mark == mark || i.stay || i.determinedBy == null; 4315c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 4325c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4335c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)BinaryConstraint.prototype.removeFromGraph = function () { 4345c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (this.v1 != null) this.v1.removeConstraint(this); 4355c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (this.v2 != null) this.v2.removeConstraint(this); 4365c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) this.direction = Direction.NONE; 4375c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 4385c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4395c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)/* --- * 4405c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * S c a l e C o n s t r a i n t 4415c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * --- */ 4425c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4435c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)/** 4445c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * Relates two variables by the linear scaling relationship: "v2 = 4455c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * (v1 * scale) + offset". Either v1 or v2 may be changed to maintain 4465c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * this relationship but the scale factor and offset are considered 4475c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * read-only. 4485c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) */ 4495c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)function ScaleConstraint(src, scale, offset, dest, strength) { 4505c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) this.direction = Direction.NONE; 4515c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) this.scale = scale; 4525c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) this.offset = offset; 4535c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ScaleConstraint.superConstructor.call(this, src, dest, strength); 4545c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 4555c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4565c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)ScaleConstraint.inherits(BinaryConstraint); 4575c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4585c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)/** 4595c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * Adds this constraint to the constraint graph. 4605c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) */ 4615c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)ScaleConstraint.prototype.addToGraph = function () { 4625c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ScaleConstraint.superConstructor.prototype.addToGraph.call(this); 4635c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) this.scale.addConstraint(this); 4645c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) this.offset.addConstraint(this); 4655c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 4665c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4675c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)ScaleConstraint.prototype.removeFromGraph = function () { 4685c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ScaleConstraint.superConstructor.prototype.removeFromGraph.call(this); 4695c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (this.scale != null) this.scale.removeConstraint(this); 4705c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (this.offset != null) this.offset.removeConstraint(this); 4715c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 4725c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4735c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)ScaleConstraint.prototype.markInputs = function (mark) { 4745c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ScaleConstraint.superConstructor.prototype.markInputs.call(this, mark); 4755c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) this.scale.mark = this.offset.mark = mark; 4765c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 4775c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4785c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)/** 4795c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * Enforce this constraint. Assume that it is satisfied. 4805c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) */ 4815c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)ScaleConstraint.prototype.execute = function () { 4825c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (this.direction == Direction.FORWARD) { 4835c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) this.v2.value = this.v1.value * this.scale.value + this.offset.value; 4845c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } else { 4855c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) this.v1.value = (this.v2.value - this.offset.value) / this.scale.value; 4865c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 4875c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 4885c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 4895c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)/** 4905c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * Calculate the walkabout strength, the stay flag, and, if it is 4915c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * 'stay', the value for the current output of this constraint. Assume 4925c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * this constraint is satisfied. 4935c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) */ 4945c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)ScaleConstraint.prototype.recalculate = function () { 4955c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) var ihn = this.input(), out = this.output(); 4965c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) out.walkStrength = Strength.weakestOf(this.strength, ihn.walkStrength); 4975c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) out.stay = ihn.stay && this.scale.stay && this.offset.stay; 4985c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (out.stay) this.execute(); 4995c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 5005c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 5015c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)/* --- * 5025c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * E q u a l i t y C o n s t r a i n t 5035c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * --- */ 5045c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 5055c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)/** 5065c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * Constrains two variables to have the same value. 5075c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) */ 5085c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)function EqualityConstraint(var1, var2, strength) { 5095c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) EqualityConstraint.superConstructor.call(this, var1, var2, strength); 5105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 5115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 5125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)EqualityConstraint.inherits(BinaryConstraint); 5135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 5145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)/** 5155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * Enforce this constraint. Assume that it is satisfied. 5165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) */ 5175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)EqualityConstraint.prototype.execute = function () { 5185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) this.output().value = this.input().value; 5195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 5205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 5215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)/* --- * 5225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * V a r i a b l e 5235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * --- */ 5245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 5255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)/** 5265c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * A constrained variable. In addition to its value, it maintain the 5275c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * structure of the constraint graph, the current dataflow graph, and 5285c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * various parameters of interest to the DeltaBlue incremental 5295c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * constraint solver. 5305c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) **/ 5315c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)function Variable(name, initialValue) { 5325c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) this.value = initialValue || 0; 5335c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) this.constraints = new OrderedCollection(); 5345c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) this.determinedBy = null; 5355c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) this.mark = 0; 5365c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) this.walkStrength = Strength.WEAKEST; 5375c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) this.stay = true; 5385c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) this.name = name; 5395c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 5405c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 5415c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)/** 5425c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * Add the given constraint to the set of all constraints that refer 5435c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * this variable. 5445c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) */ 5455c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)Variable.prototype.addConstraint = function (c) { 5465c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) this.constraints.add(c); 5475c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 5485c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 5495c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)/** 5505c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * Removes all traces of c from this variable. 5515c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) */ 5525c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)Variable.prototype.removeConstraint = function (c) { 5535c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) this.constraints.remove(c); 5545c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (this.determinedBy == c) this.determinedBy = null; 5555c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 5565c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 5575c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)/* --- * 5585c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * P l a n n e r 5595c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * --- */ 5605c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 5615c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)/** 5625c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * The DeltaBlue planner 5635c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) */ 5645c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)function Planner() { 5655c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) this.currentMark = 0; 5665c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 5675c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 5685c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)/** 5695c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * Attempt to satisfy the given constraint and, if successful, 5705c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * incrementally update the dataflow graph. Details: If satifying 5715c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * the constraint is successful, it may override a weaker constraint 5725c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * on its output. The algorithm attempts to resatisfy that 5735c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * constraint using some other method. This process is repeated 5745c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * until either a) it reaches a variable that was not previously 5755c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * determined by any constraint or b) it reaches a constraint that 5765c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * is too weak to be satisfied using any of its methods. The 5775c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * variables of constraints that have been processed are marked with 5785c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * a unique mark value so that we know where we've been. This allows 5795c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * the algorithm to avoid getting into an infinite loop even if the 5805c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * constraint graph has an inadvertent cycle. 5815c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) */ 5825c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)Planner.prototype.incrementalAdd = function (c) { 5835c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) var mark = this.newMark(); 5845c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) var overridden = c.satisfy(mark); 5855c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) while (overridden != null) 5865c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) overridden = overridden.satisfy(mark); 5875c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 5885c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 5895c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)/** 5905c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * Entry point for retracting a constraint. Remove the given 5915c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * constraint and incrementally update the dataflow graph. 5925c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * Details: Retracting the given constraint may allow some currently 5935c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * unsatisfiable downstream constraint to be satisfied. We therefore collect 5945c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * a list of unsatisfied downstream constraints and attempt to 5955c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * satisfy each one in turn. This list is traversed by constraint 5965c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * strength, strongest first, as a heuristic for avoiding 5975c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * unnecessarily adding and then overriding weak constraints. 5985c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * Assume: c is satisfied. 5995c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) */ 6005c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)Planner.prototype.incrementalRemove = function (c) { 6015c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) var out = c.output(); 6025c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) c.markUnsatisfied(); 6035c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) c.removeFromGraph(); 6045c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) var unsatisfied = this.removePropagateFrom(out); 6055c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) var strength = Strength.REQUIRED; 6065c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) do { 6075c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) for (var i = 0; i < unsatisfied.size(); i++) { 6085c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) var u = unsatisfied.at(i); 6095c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (u.strength == strength) 6105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) this.incrementalAdd(u); 6115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 6125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) strength = strength.nextWeaker(); 6135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } while (strength != Strength.WEAKEST); 6145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 6155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 6165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)/** 6175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * Select a previously unused mark value. 6185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) */ 6195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)Planner.prototype.newMark = function () { 6205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return ++this.currentMark; 6215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 6225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 6235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)/** 6245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * Extract a plan for resatisfaction starting from the given source 6255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * constraints, usually a set of input constraints. This method 6265c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * assumes that stay optimization is desired; the plan will contain 6275c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * only constraints whose output variables are not stay. Constraints 6285c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * that do no computation, such as stay and edit constraints, are 6295c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * not included in the plan. 6305c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * Details: The outputs of a constraint are marked when it is added 6315c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * to the plan under construction. A constraint may be appended to 6325c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * the plan when all its input variables are known. A variable is 6335c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * known if either a) the variable is marked (indicating that has 6345c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * been computed by a constraint appearing earlier in the plan), b) 6355c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * the variable is 'stay' (i.e. it is a constant at plan execution 6365c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * time), or c) the variable is not determined by any 6375c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * constraint. The last provision is for past states of history 6385c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * variables, which are not stay but which are also not computed by 6395c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * any constraint. 6405c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * Assume: sources are all satisfied. 6415c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) */ 6425c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)Planner.prototype.makePlan = function (sources) { 6435c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) var mark = this.newMark(); 6445c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) var plan = new Plan(); 6455c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) var todo = sources; 6465c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) while (todo.size() > 0) { 6475c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) var c = todo.removeFirst(); 6485c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (c.output().mark != mark && c.inputsKnown(mark)) { 6495c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) plan.addConstraint(c); 6505c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) c.output().mark = mark; 6515c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) this.addConstraintsConsumingTo(c.output(), todo); 6525c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 6535c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 6545c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return plan; 6555c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 6565c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 6575c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)/** 6585c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * Extract a plan for resatisfying starting from the output of the 6595c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * given constraints, usually a set of input constraints. 6605c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) */ 6615c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)Planner.prototype.extractPlanFromConstraints = function (constraints) { 6625c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) var sources = new OrderedCollection(); 6635c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) for (var i = 0; i < constraints.size(); i++) { 6645c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) var c = constraints.at(i); 6655c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (c.isInput() && c.isSatisfied()) 6665c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // not in plan already and eligible for inclusion 6675c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) sources.add(c); 6685c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 6695c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return this.makePlan(sources); 6705c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 6715c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 6725c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)/** 6735c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * Recompute the walkabout strengths and stay flags of all variables 6745c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * downstream of the given constraint and recompute the actual 6755c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * values of all variables whose stay flag is true. If a cycle is 6765c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * detected, remove the given constraint and answer 6775c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * false. Otherwise, answer true. 6785c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * Details: Cycles are detected when a marked variable is 6795c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * encountered downstream of the given constraint. The sender is 6805c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * assumed to have marked the inputs of the given constraint with 6815c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * the given mark. Thus, encountering a marked node downstream of 6825c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * the output constraint means that there is a path from the 6835c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * constraint's output to one of its inputs. 6845c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) */ 6855c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)Planner.prototype.addPropagate = function (c, mark) { 6865c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) var todo = new OrderedCollection(); 6875c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) todo.add(c); 6885c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) while (todo.size() > 0) { 6895c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) var d = todo.removeFirst(); 6905c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (d.output().mark == mark) { 6915c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) this.incrementalRemove(c); 6925c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return false; 6935c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 6945c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) d.recalculate(); 6955c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) this.addConstraintsConsumingTo(d.output(), todo); 6965c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 6975c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return true; 6985c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 6995c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 7005c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 7015c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)/** 7025c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * Update the walkabout strengths and stay flags of all variables 7035c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * downstream of the given constraint. Answer a collection of 7045c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * unsatisfied constraints sorted in order of decreasing strength. 7055c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) */ 7065c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)Planner.prototype.removePropagateFrom = function (out) { 7075c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) out.determinedBy = null; 7085c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) out.walkStrength = Strength.WEAKEST; 7095c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) out.stay = true; 7105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) var unsatisfied = new OrderedCollection(); 7115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) var todo = new OrderedCollection(); 7125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) todo.add(out); 7135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) while (todo.size() > 0) { 7145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) var v = todo.removeFirst(); 7155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) for (var i = 0; i < v.constraints.size(); i++) { 7165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) var c = v.constraints.at(i); 7175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (!c.isSatisfied()) 7185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) unsatisfied.add(c); 7195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 7205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) var determining = v.determinedBy; 7215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) for (var i = 0; i < v.constraints.size(); i++) { 7225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) var next = v.constraints.at(i); 7235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (next != determining && next.isSatisfied()) { 7245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) next.recalculate(); 7255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) todo.add(next.output()); 7265c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 7275c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 7285c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 7295c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return unsatisfied; 7305c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 7315c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 7325c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)Planner.prototype.addConstraintsConsumingTo = function (v, coll) { 7335c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) var determining = v.determinedBy; 7345c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) var cc = v.constraints; 7355c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) for (var i = 0; i < cc.size(); i++) { 7365c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) var c = cc.at(i); 7375c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (c != determining && c.isSatisfied()) 7385c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) coll.add(c); 7395c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 7405c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 7415c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 7425c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)/* --- * 7435c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * P l a n 7445c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * --- */ 7455c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 7465c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)/** 7475c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * A Plan is an ordered list of constraints to be executed in sequence 7485c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * to resatisfy all currently satisfiable constraints in the face of 7495c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * one or more changing inputs. 7505c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) */ 7515c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)function Plan() { 7525c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) this.v = new OrderedCollection(); 7535c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 7545c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 7555c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)Plan.prototype.addConstraint = function (c) { 7565c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) this.v.add(c); 7575c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 7585c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 7595c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)Plan.prototype.size = function () { 7605c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return this.v.size(); 7615c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 7625c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 7635c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)Plan.prototype.constraintAt = function (index) { 7645c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return this.v.at(index); 7655c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 7665c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 7675c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)Plan.prototype.execute = function () { 7685c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) for (var i = 0; i < this.size(); i++) { 7695c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) var c = this.constraintAt(i); 7705c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) c.execute(); 7715c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 7725c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 7735c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 7745c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)/* --- * 7755c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * M a i n 7765c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * --- */ 7775c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 7785c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)/** 7795c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * This is the standard DeltaBlue benchmark. A long chain of equality 7805c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * constraints is constructed with a stay constraint on one end. An 7815c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * edit constraint is then added to the opposite end and the time is 7825c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * measured for adding and removing this constraint, and extracting 7835c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * and executing a constraint satisfaction plan. There are two cases. 7845c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * In case 1, the added constraint is stronger than the stay 7855c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * constraint and values must propagate down the entire length of the 7865c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * chain. In case 2, the added constraint is weaker than the stay 7875c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * constraint so it cannot be accomodated. The cost in this case is, 7885c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * of course, very low. Typical situations lie somewhere between these 7895c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * two extremes. 7905c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) */ 7915c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)function chainTest(n) { 7925c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) planner = new Planner(); 7935c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) var prev = null, first = null, last = null; 7945c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 7955c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // Build chain of n equality constraints 7965c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) for (var i = 0; i <= n; i++) { 7975c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) var name = "v" + i; 7985c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) var v = new Variable(name); 7995c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (prev != null) 8005c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) new EqualityConstraint(prev, v, Strength.REQUIRED); 8015c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (i == 0) first = v; 8025c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (i == n) last = v; 8035c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) prev = v; 8045c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 8055c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 8065c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) new StayConstraint(last, Strength.STRONG_DEFAULT); 8075c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) var edit = new EditConstraint(first, Strength.PREFERRED); 8085c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) var edits = new OrderedCollection(); 8095c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) edits.add(edit); 8105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) var plan = planner.extractPlanFromConstraints(edits); 8115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) for (var i = 0; i < 100; i++) { 8125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) first.value = i; 8135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) plan.execute(); 8145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (last.value != i) 8155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) alert("Chain test failed."); 8165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 8175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 8185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 8195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)/** 8205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * This test constructs a two sets of variables related to each 8215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * other by a simple linear transformation (scale and offset). The 8225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * time is measured to change a variable on either side of the 8235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * mapping and to change the scale and offset factors. 8245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) */ 8255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)function projectionTest(n) { 8265c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) planner = new Planner(); 8275c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) var scale = new Variable("scale", 10); 8285c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) var offset = new Variable("offset", 1000); 8295c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) var src = null, dst = null; 8305c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 8315c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) var dests = new OrderedCollection(); 8325c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) for (var i = 0; i < n; i++) { 8335c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) src = new Variable("src" + i, i); 8345c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) dst = new Variable("dst" + i, i); 8355c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) dests.add(dst); 8365c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) new StayConstraint(src, Strength.NORMAL); 8375c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) new ScaleConstraint(src, scale, offset, dst, Strength.REQUIRED); 8385c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 8395c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 8405c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) change(src, 17); 8415c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (dst.value != 1170) alert("Projection 1 failed"); 8425c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) change(dst, 1050); 8435c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (src.value != 5) alert("Projection 2 failed"); 8445c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) change(scale, 5); 8455c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) for (var i = 0; i < n - 1; i++) { 8465c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (dests.at(i).value != i * 5 + 1000) 8475c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) alert("Projection 3 failed"); 8485c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 8495c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) change(offset, 2000); 8505c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) for (var i = 0; i < n - 1; i++) { 8515c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (dests.at(i).value != i * 5 + 2000) 8525c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) alert("Projection 4 failed"); 8535c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 8545c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 8555c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 8565c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)function change(v, newValue) { 8575c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) var edit = new EditConstraint(v, Strength.PREFERRED); 8585c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) var edits = new OrderedCollection(); 8595c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) edits.add(edit); 8605c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) var plan = planner.extractPlanFromConstraints(edits); 8615c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) for (var i = 0; i < 10; i++) { 8625c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) v.value = newValue; 8635c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) plan.execute(); 8645c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 8655c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) edit.destroyConstraint(); 8665c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 8675c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 8685c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// Global variable holding the current planner. 8695c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)var planner = null; 8705c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 8715c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)function deltaBlue() { 8725c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) chainTest(100); 8735c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) projectionTest(100); 8745c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 8755c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 8765c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)for (var i = 0; i < 155; ++i) 8775c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) deltaBlue(); 878