solver.dart 17 KB
Newer Older
1 2 3 4 5 6 7
// Copyright (c) 2015 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

part of cassowary;

class Solver {
8 9 10 11 12 13 14
  final Map<Constraint, _Tag> _constraints = new Map<Constraint, _Tag>();
  final Map<_Symbol, _Row> _rows = new Map<_Symbol, _Row>();
  final Map<Variable, _Symbol> _vars = new Map<Variable, _Symbol>();
  final Map<Variable, _EditInfo> _edits = new Map<Variable, _EditInfo>();
  final List<_Symbol> _infeasibleRows = new List<_Symbol>();
  final _Row _objective = new _Row(0.0);
  _Row _artificial = new _Row(0.0);
15
  int tick = 1;
16

17 18 19 20
  /// Attempts to add the constraints in the list to the solver. If it cannot
  /// add any for some reason, a cleanup is attempted so that either all
  /// constraints will be added or none.
  Result addConstraints(List<Constraint> constraints) {
21 22
    _SolverBulkUpdate applier = (Constraint c) => addConstraint(c);
    _SolverBulkUpdate undoer = (Constraint c) => removeConstraint(c);
23

24
    return _bulkEdit(constraints, applier, undoer);
25 26
  }

27 28 29 30 31
  Result addConstraint(Constraint constraint) {
    if (_constraints.containsKey(constraint)) {
      return Result.duplicateConstraint;
    }

32 33
    _Tag tag = new _Tag(new _Symbol(_SymbolType.invalid, 0),
        new _Symbol(_SymbolType.invalid, 0));
34

35
    _Row row = _createRow(constraint, tag);
36

37
    _Symbol subject = _chooseSubjectForRow(row, tag);
38

39
    if (subject.type == _SymbolType.invalid && _allDummiesInRow(row)) {
40 41 42 43 44 45 46
      if (!_nearZero(row.constant)) {
        return Result.unsatisfiableConstraint;
      } else {
        subject = tag.marker;
      }
    }

47
    if (subject.type == _SymbolType.invalid) {
48 49 50 51 52 53 54 55 56 57 58
      if (!_addWithArtificialVariableOnRow(row)) {
        return Result.unsatisfiableConstraint;
      }
    } else {
      row.solveForSymbol(subject);
      _substitute(subject, row);
      _rows[subject] = row;
    }

    _constraints[constraint] = tag;

59
    return _optimizeObjectiveRow(_objective);
60 61
  }

62 63 64 65 66 67 68
  Result removeConstraints(List<Constraint> constraints) {
    _SolverBulkUpdate applier = (Constraint c) => removeConstraint(c);
    _SolverBulkUpdate undoer = (Constraint c) => addConstraint(c);

    return _bulkEdit(constraints, applier, undoer);
  }

69
  Result removeConstraint(Constraint constraint) {
70
    _Tag tag = _constraints[constraint];
71 72 73 74
    if (tag == null) {
      return Result.unknownConstraint;
    }

75
    tag = new _Tag.fromTag(tag);
76 77 78 79
    _constraints.remove(constraint);

    _removeConstraintEffects(constraint, tag);

80
    _Row row = _rows[tag.marker];
81 82 83
    if (row != null) {
      _rows.remove(tag.marker);
    } else {
84
      _Pair<_Symbol, _Row> rowPair = _leavingRowPairForMarkerSymbol(tag.marker);
85 86 87 88 89

      if (rowPair == null) {
        return Result.internalSolverError;
      }

90
      _Symbol leaving = rowPair.first;
91 92 93 94 95 96 97 98
      row = rowPair.second;
      var removed = _rows.remove(rowPair.first);
      assert(removed != null);
      row.solveForSymbols(leaving, tag.marker);
      _substitute(tag.marker, row);
    }

    return _optimizeObjectiveRow(_objective);
99 100
  }

101 102
  bool hasConstraint(Constraint constraint) {
    return _constraints.containsKey(constraint);
103 104
  }

105 106 107 108 109 110 111
  Result addEditVariables(List<Variable> variables, double priority) {
    _SolverBulkUpdate applier = (Variable v) => addEditVariable(v, priority);
    _SolverBulkUpdate undoer = (Variable v) => removeEditVariable(v);

    return _bulkEdit(variables, applier, undoer);
  }

112 113 114 115 116 117 118 119 120 121 122
  Result addEditVariable(Variable variable, double priority) {
    if (_edits.containsKey(variable)) {
      return Result.duplicateEditVariable;
    }

    if (!_isValidNonRequiredPriority(priority)) {
      return Result.badRequiredStrength;
    }

    Constraint constraint = new Constraint(
        new Expression([new Term(variable, 1.0)], 0.0), Relation.equalTo);
123
    constraint.priority = priority;
124 125 126 127 128

    if (addConstraint(constraint) != Result.success) {
      return Result.internalSolverError;
    }

129
    _EditInfo info = new _EditInfo();
130 131 132 133 134 135 136
    info.tag = _constraints[constraint];
    info.constraint = constraint;
    info.constant = 0.0;

    _edits[variable] = info;

    return Result.success;
137 138
  }

139 140 141 142 143 144 145 146
  Result removeEditVariables(List<Variable> variables) {
    _SolverBulkUpdate applier = (Variable v) => removeEditVariable(v);
    _SolverBulkUpdate undoer = (Variable v) =>
        addEditVariable(v, _edits[v].constraint.priority);

    return _bulkEdit(variables, applier, undoer);
  }

147
  Result removeEditVariable(Variable variable) {
148
    _EditInfo info = _edits[variable];
149 150 151 152 153 154 155 156 157 158
    if (info == null) {
      return Result.unknownEditVariable;
    }

    if (removeConstraint(info.constraint) != Result.success) {
      return Result.internalSolverError;
    }

    _edits.remove(variable);
    return Result.success;
159 160
  }

161 162
  bool hasEditVariable(Variable variable) {
    return _edits.containsKey(variable);
163 164
  }

165 166 167 168 169 170 171 172
  Result suggestValueForVariable(Variable variable, double value) {
    if (!_edits.containsKey(variable)) {
      return Result.unknownEditVariable;
    }

    _suggestValueForEditInfoWithoutDualOptimization(_edits[variable], value);

    return _dualOptimize();
173 174
  }

175 176
  Set flushUpdates() {
    Set updates = new Set();
177

178
    for (Variable variable in _vars.keys) {
179 180
      _Symbol symbol = _vars[variable];
      _Row row = _rows[symbol];
181 182 183 184

      double updatedValue = row == null ? 0.0 : row.constant;

      if (variable._applyUpdate(updatedValue) && variable._owner != null) {
185 186 187 188 189
        dynamic context = variable._owner.context;

        if (context != null) {
          updates.add(context);
        }
190 191
      }
    }
192

193
    return updates;
194
  }
195

196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222
  Result _bulkEdit(Iterable items,
                   _SolverBulkUpdate applier,
                   _SolverBulkUpdate undoer) {
    List applied = new List();
    bool needsCleanup = false;

    Result result = Result.success;

    for (dynamic item in items) {
      result = applier(item);
      if (result == Result.success) {
        applied.add(item);
      } else {
        needsCleanup = true;
        break;
      }
    }

    if (needsCleanup) {
      for (dynamic item in applied.reversed) {
        undoer(item);
      }
    }

    return result;
  }

223
  _Symbol _symbolForVariable(Variable variable) {
224
    _Symbol symbol = _vars[variable];
225 226 227 228 229

    if (symbol != null) {
      return symbol;
    }

230
    symbol = new _Symbol(_SymbolType.external, tick++);
231 232 233 234 235
    _vars[variable] = symbol;

    return symbol;
  }

236
  _Row _createRow(Constraint constraint, _Tag tag) {
237
    Expression expr = new Expression.fromExpression(constraint.expression);
238
    _Row row = new _Row(expr.constant);
239 240 241

    expr.terms.forEach((term) {
      if (!_nearZero(term.coefficient)) {
242
        _Symbol symbol = _symbolForVariable(term.variable);
243

244
        _Row foundRow = _rows[symbol];
245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260

        if (foundRow != null) {
          row.insertRow(foundRow, term.coefficient);
        } else {
          row.insertSymbol(symbol, term.coefficient);
        }
      }
    });

    switch (constraint.relation) {
      case Relation.lessThanOrEqualTo:
      case Relation.greaterThanOrEqualTo:
        {
          double coefficient =
              constraint.relation == Relation.lessThanOrEqualTo ? 1.0 : -1.0;

261
          _Symbol slack = new _Symbol(_SymbolType.slack, tick++);
262 263 264
          tag.marker = slack;
          row.insertSymbol(slack, coefficient);

265
          if (constraint.priority < Priority.required) {
266
            _Symbol error = new _Symbol(_SymbolType.error, tick++);
267 268 269 270 271 272 273
            tag.other = error;
            row.insertSymbol(error, -coefficient);
            _objective.insertSymbol(error, constraint.priority);
          }
        }
        break;
      case Relation.equalTo:
274
        if (constraint.priority < Priority.required) {
275 276
          _Symbol errPlus = new _Symbol(_SymbolType.error, tick++);
          _Symbol errMinus = new _Symbol(_SymbolType.error, tick++);
277 278 279 280 281 282 283
          tag.marker = errPlus;
          tag.other = errMinus;
          row.insertSymbol(errPlus, -1.0);
          row.insertSymbol(errMinus, 1.0);
          _objective.insertSymbol(errPlus, constraint.priority);
          _objective.insertSymbol(errMinus, constraint.priority);
        } else {
284
          _Symbol dummy = new _Symbol(_SymbolType.dummy, tick++);
285 286 287 288 289 290 291 292 293 294 295 296 297
          tag.marker = dummy;
          row.insertSymbol(dummy);
        }
        break;
    }

    if (row.constant < 0.0) {
      row.reverseSign();
    }

    return row;
  }

298 299
  _Symbol _chooseSubjectForRow(_Row row, _Tag tag) {
    for (_Symbol symbol in row.cells.keys) {
300
      if (symbol.type == _SymbolType.external) {
301 302 303 304
        return symbol;
      }
    }

305 306
    if (tag.marker.type == _SymbolType.slack ||
        tag.marker.type == _SymbolType.error) {
307 308 309 310 311
      if (row.coefficientForSymbol(tag.marker) < 0.0) {
        return tag.marker;
      }
    }

312 313
    if (tag.other.type == _SymbolType.slack ||
        tag.other.type == _SymbolType.error) {
314 315 316 317 318
      if (row.coefficientForSymbol(tag.other) < 0.0) {
        return tag.other;
      }
    }

319
    return new _Symbol(_SymbolType.invalid, 0);
320 321
  }

322 323
  bool _allDummiesInRow(_Row row) {
    for (_Symbol symbol in row.cells.keys) {
324
      if (symbol.type != _SymbolType.dummy) {
325 326 327 328 329 330
        return false;
      }
    }
    return true;
  }

331
  bool _addWithArtificialVariableOnRow(_Row row) {
332
    _Symbol artificial = new _Symbol(_SymbolType.slack, tick++);
333 334
    _rows[artificial] = new _Row.fromRow(row);
    _artificial = new _Row.fromRow(row);
335 336 337 338 339 340 341 342 343

    Result result = _optimizeObjectiveRow(_artificial);

    if (result.error) {
      // FIXME(csg): Propagate this up!
      return false;
    }

    bool success = _nearZero(_artificial.constant);
344
    _artificial = new _Row(0.0);
345

346
    _Row foundRow = _rows[artificial];
347 348 349 350 351 352
    if (foundRow != null) {
      _rows.remove(artificial);
      if (foundRow.cells.isEmpty) {
        return success;
      }

353
      _Symbol entering = _anyPivotableSymbol(foundRow);
354
      if (entering.type == _SymbolType.invalid) {
355 356 357 358 359 360 361 362
        return false;
      }

      foundRow.solveForSymbols(artificial, entering);
      _substitute(entering, foundRow);
      _rows[entering] = foundRow;
    }

363
    for (_Row row in _rows.values) {
364 365 366 367 368 369
      row.removeSymbol(artificial);
    }
    _objective.removeSymbol(artificial);
    return success;
  }

370
  Result _optimizeObjectiveRow(_Row objective) {
371
    while (true) {
372
      _Symbol entering = _enteringSymbolForObjectiveRow(objective);
373
      if (entering.type == _SymbolType.invalid) {
374 375 376
        return Result.success;
      }

377
      _Pair<_Symbol, _Row> leavingPair = _leavingRowForEnteringSymbol(entering);
378 379 380 381 382

      if (leavingPair == null) {
        return Result.internalSolverError;
      }

383 384
      _Symbol leaving = leavingPair.first;
      _Row row = leavingPair.second;
385 386 387 388 389 390 391
      _rows.remove(leavingPair.first);
      row.solveForSymbols(leaving, entering);
      _substitute(entering, row);
      _rows[entering] = row;
    }
  }

392
  _Symbol _enteringSymbolForObjectiveRow(_Row objective) {
393
    Map<_Symbol, double> cells = objective.cells;
394

395
    for (_Symbol symbol in cells.keys) {
396
      if (symbol.type != _SymbolType.dummy && cells[symbol] < 0.0) {
397 398 399 400
        return symbol;
      }
    }

401
    return new _Symbol(_SymbolType.invalid, 0);
402 403
  }

404
  _Pair<_Symbol, _Row> _leavingRowForEnteringSymbol(_Symbol entering) {
405
    double ratio = double.MAX_FINITE;
406
    _Pair<_Symbol, _Row> result = new _Pair(null, null);
407 408

    _rows.forEach((symbol, row) {
409
      if (symbol.type != _SymbolType.external) {
410 411 412
        double temp = row.coefficientForSymbol(entering);

        if (temp < 0.0) {
Hixie's avatar
Hixie committed
413
          double tempRatio = -row.constant / temp;
414

Hixie's avatar
Hixie committed
415 416
          if (tempRatio < ratio) {
            ratio = tempRatio;
417 418 419 420 421 422 423 424 425 426 427 428 429 430
            result.first = symbol;
            result.second = row;
          }
        }
      }
    });

    if (result.first == null || result.second == null) {
      return null;
    }

    return result;
  }

431
  void _substitute(_Symbol symbol, _Row row) {
432 433
    _rows.forEach((first, second) {
      second.substitute(symbol, row);
434
      if (first.type != _SymbolType.external && second.constant < 0.0) {
435 436 437 438 439 440 441 442 443 444
        _infeasibleRows.add(first);
      }
    });

    _objective.substitute(symbol, row);
    if (_artificial != null) {
      _artificial.substitute(symbol, row);
    }
  }

445 446
  _Symbol _anyPivotableSymbol(_Row row) {
    for (_Symbol symbol in row.cells.keys) {
447 448
      if (symbol.type == _SymbolType.slack ||
          symbol.type == _SymbolType.error) {
449 450 451
        return symbol;
      }
    }
452
    return new _Symbol(_SymbolType.invalid, 0);
453
  }
454

455
  void _removeConstraintEffects(Constraint cn, _Tag tag) {
456
    if (tag.marker.type == _SymbolType.error) {
457 458
      _removeMarkerEffects(tag.marker, cn.priority);
    }
459
    if (tag.other.type == _SymbolType.error) {
460 461 462 463
      _removeMarkerEffects(tag.other, cn.priority);
    }
  }

464 465
  void _removeMarkerEffects(_Symbol marker, double strength) {
    _Row row = _rows[marker];
466 467 468 469 470 471 472
    if (row != null) {
      _objective.insertRow(row, -strength);
    } else {
      _objective.insertSymbol(marker, -strength);
    }
  }

473
  _Pair<_Symbol, _Row> _leavingRowPairForMarkerSymbol(_Symbol marker) {
474 475 476
    double r1 = double.MAX_FINITE;
    double r2 = double.MAX_FINITE;

477
    _Pair<_Symbol, _Row> first, second, third;
478 479 480 481 482 483 484 485

    _rows.forEach((symbol, row) {
      double c = row.coefficientForSymbol(marker);

      if (c == 0.0) {
        return;
      }

486
      if (symbol.type == _SymbolType.external) {
487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510
        third = new _Pair(symbol, row);
      } else if (c < 0.0) {
        double r = -row.constant / c;
        if (r < r1) {
          r1 = r;
          first = new _Pair(symbol, row);
        }
      } else {
        double r = row.constant / c;
        if (r < r2) {
          r2 = r;
          second = new _Pair(symbol, row);
        }
      }
    });

    if (first != null) {
      return first;
    }
    if (second != null) {
      return second;
    }
    return third;
  }
511 512

  void _suggestValueForEditInfoWithoutDualOptimization(
513
      _EditInfo info, double value) {
514 515 516 517
    double delta = value - info.constant;
    info.constant = value;

    {
518 519
      _Symbol symbol = info.tag.marker;
      _Row row = _rows[info.tag.marker];
520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538

      if (row != null) {
        if (row.add(-delta) < 0.0) {
          _infeasibleRows.add(symbol);
        }
        return;
      }

      symbol = info.tag.other;
      row = _rows[info.tag.other];

      if (row != null) {
        if (row.add(delta) < 0.0) {
          _infeasibleRows.add(symbol);
        }
        return;
      }
    }

539 540
    for (_Symbol symbol in _rows.keys) {
      _Row row = _rows[symbol];
541 542 543
      double coeff = row.coefficientForSymbol(info.tag.marker);
      if (coeff != 0.0 &&
          row.add(delta * coeff) < 0.0 &&
544
          symbol.type != _SymbolType.external) {
545 546 547 548 549 550 551
        _infeasibleRows.add(symbol);
      }
    }
  }

  Result _dualOptimize() {
    while (_infeasibleRows.length != 0) {
552 553
      _Symbol leaving = _infeasibleRows.removeLast();
      _Row row = _rows[leaving];
554 555

      if (row != null && row.constant < 0.0) {
556
        _Symbol entering = _dualEnteringSymbolForRow(row);
557

558
        if (entering.type == _SymbolType.invalid) {
559 560 561 562 563 564 565 566 567 568 569 570 571
          return Result.internalSolverError;
        }

        _rows.remove(leaving);

        row.solveForSymbols(leaving, entering);
        _substitute(entering, row);
        _rows[entering] = row;
      }
    }
    return Result.success;
  }

572
  _Symbol _dualEnteringSymbolForRow(_Row row) {
573
    _Symbol entering;
574 575 576

    double ratio = double.MAX_FINITE;

577
    Map<_Symbol, double> rowCells = row.cells;
578

579
    for (_Symbol symbol in rowCells.keys) {
580 581
      double value = rowCells[symbol];

582
      if (value > 0.0 && symbol.type != _SymbolType.dummy) {
583 584 585 586 587 588 589 590 591
        double coeff = _objective.coefficientForSymbol(symbol);
        double r = coeff / value;
        if (r < ratio) {
          ratio = r;
          entering = symbol;
        }
      }
    }

592
    return _elvis(entering, new _Symbol(_SymbolType.invalid, 0));
593
  }
594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629

  String toString() {
    StringBuffer buffer = new StringBuffer();
    String separator = "\n~~~~~~~~~";

    // Objective
    buffer.writeln(separator + " Objective");
    buffer.writeln(_objective.toString());

    // Tableau
    buffer.writeln(separator + " Tableau");
    _rows.forEach((symbol, row) {
      buffer.write(symbol.toString());
      buffer.write(" | ");
      buffer.writeln(row.toString());
    });

    // Infeasible
    buffer.writeln(separator + " Infeasible");
    _infeasibleRows.forEach((symbol) => buffer.writeln(symbol.toString()));

    // Variables
    buffer.writeln(separator + " Variables");
    _vars.forEach((variable, symbol) =>
        buffer.writeln("${variable.toString()} = ${symbol.toString()}"));

    // Edit Variables
    buffer.writeln(separator + " Edit Variables");
    _edits.forEach((variable, editinfo) => buffer.writeln(variable));

    // Constraints
    buffer.writeln(separator + " Constraints");
    _constraints.forEach((constraint, _) => buffer.writeln(constraint));

    return buffer.toString();
  }
630
}
631

632 633 634
class _Tag {
  _Symbol marker;
  _Symbol other;
635

636 637
  _Tag(this.marker, this.other);
  _Tag.fromTag(_Tag tag)
638 639
      : this.marker = tag.marker,
        this.other = tag.other;
640 641
}

642 643
class _EditInfo {
  _Tag tag;
644 645 646
  Constraint constraint;
  double constant;
}
647 648

bool _isValidNonRequiredPriority(double priority) {
649
  return (priority >= 0.0 && priority < Priority.required);
650
}
651 652

typedef Result _SolverBulkUpdate(dynamic item);