Merge pull request #29 from abarth/basic_structure
Start building the repository structure
diff --git a/.travis.yml b/.travis.yml
new file mode 100644
index 0000000..169eacd
--- /dev/null
+++ b/.travis.yml
@@ -0,0 +1,8 @@
+language: dart
+sudo: false
+dart:
+ - stable
+before_script:
+ - ./travis/setup.sh
+script:
+ - ./travis/test.sh
diff --git a/packages/cassowary/lib/cassowary.dart b/packages/cassowary/lib/cassowary.dart
new file mode 100644
index 0000000..913ec48
--- /dev/null
+++ b/packages/cassowary/lib/cassowary.dart
@@ -0,0 +1,22 @@
+// 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.
+
+library cassowary;
+
+import 'dart:math';
+
+part 'constraint.dart';
+part 'expression.dart';
+part 'term.dart';
+part 'variable.dart';
+part 'equation_member.dart';
+part 'constant_member.dart';
+part 'solver.dart';
+part 'symbol.dart';
+part 'row.dart';
+part 'utils.dart';
+part 'result.dart';
+part 'parser_exception.dart';
+part 'param.dart';
+part 'priority.dart';
diff --git a/packages/cassowary/lib/constant_member.dart b/packages/cassowary/lib/constant_member.dart
new file mode 100644
index 0000000..fed8d20
--- /dev/null
+++ b/packages/cassowary/lib/constant_member.dart
@@ -0,0 +1,19 @@
+// 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 ConstantMember extends _EquationMember {
+ final double value;
+
+ bool get isConstant => true;
+
+ ConstantMember(this.value);
+
+ Expression asExpression() => new Expression([], this.value);
+}
+
+ConstantMember cm(double value) {
+ return new ConstantMember(value);
+}
diff --git a/packages/cassowary/lib/constraint.dart b/packages/cassowary/lib/constraint.dart
new file mode 100644
index 0000000..83a5946
--- /dev/null
+++ b/packages/cassowary/lib/constraint.dart
@@ -0,0 +1,42 @@
+// 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;
+
+enum Relation { equalTo, lessThanOrEqualTo, greaterThanOrEqualTo, }
+
+class Constraint {
+ final Relation relation;
+ final Expression expression;
+ double priority = Priority.required;
+
+ Constraint(this.expression, this.relation);
+
+ Constraint operator |(double p) => this..priority = p;
+
+ String toString() {
+ StringBuffer buffer = new StringBuffer();
+ buffer.write(expression.toString());
+
+ switch (relation) {
+ case Relation.equalTo:
+ buffer.write(" == 0 ");
+ break;
+ case Relation.greaterThanOrEqualTo:
+ buffer.write(" >= 0 ");
+ break;
+ case Relation.lessThanOrEqualTo:
+ buffer.write(" <= 0 ");
+ break;
+ }
+
+ buffer.write(" | priority = ${priority}");
+
+ if (priority == Priority.required) {
+ buffer.write(" (required)");
+ }
+
+ return buffer.toString();
+ }
+}
diff --git a/packages/cassowary/lib/equation_member.dart b/packages/cassowary/lib/equation_member.dart
new file mode 100644
index 0000000..247710d
--- /dev/null
+++ b/packages/cassowary/lib/equation_member.dart
@@ -0,0 +1,30 @@
+// 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;
+
+abstract class _EquationMember {
+ Expression asExpression();
+
+ bool get isConstant;
+
+ double get value;
+
+ Constraint operator >=(_EquationMember m) => asExpression() >= m;
+
+ Constraint operator <=(_EquationMember m) => asExpression() <= m;
+
+ operator ==(_EquationMember m) => asExpression() == m;
+
+ Expression operator +(_EquationMember m) => asExpression() + m;
+
+ Expression operator -(_EquationMember m) => asExpression() - m;
+
+ Expression operator *(_EquationMember m) => asExpression() * m;
+
+ Expression operator /(_EquationMember m) => asExpression() / m;
+
+ int get hashCode =>
+ throw "An equation member is not comparable and cannot be added to collections";
+}
diff --git a/packages/cassowary/lib/expression.dart b/packages/cassowary/lib/expression.dart
new file mode 100644
index 0000000..0c7f1e9
--- /dev/null
+++ b/packages/cassowary/lib/expression.dart
@@ -0,0 +1,172 @@
+// 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 Expression extends _EquationMember {
+ final List<Term> terms;
+
+ final double constant;
+
+ bool get isConstant => terms.length == 0;
+
+ double get value => terms.fold(constant, (value, term) => value + term.value);
+
+ Expression(this.terms, this.constant);
+ Expression.fromExpression(Expression expr)
+ : this.terms = new List<Term>.from(expr.terms),
+ this.constant = expr.constant;
+
+ Expression asExpression() => this;
+
+ Constraint _createConstraint(
+ _EquationMember /* rhs */ value, Relation relation) {
+ if (value is ConstantMember) {
+ return new Constraint(
+ new Expression(new List.from(terms), constant - value.value),
+ relation);
+ }
+
+ if (value is Param) {
+ var newTerms = new List<Term>.from(terms)
+ ..add(new Term(value.variable, -1.0));
+ return new Constraint(new Expression(newTerms, constant), relation);
+ }
+
+ if (value is Term) {
+ var newTerms = new List<Term>.from(terms)
+ ..add(new Term(value.variable, -value.coefficient));
+ return new Constraint(new Expression(newTerms, constant), relation);
+ }
+
+ if (value is Expression) {
+ var newTerms = value.terms.fold(new List<Term>.from(terms),
+ (list, t) => list..add(new Term(t.variable, -t.coefficient)));
+ return new Constraint(
+ new Expression(newTerms, constant - value.constant), relation);
+ }
+
+ assert(false);
+ return null;
+ }
+
+ Constraint operator >=(_EquationMember value) =>
+ _createConstraint(value, Relation.greaterThanOrEqualTo);
+
+ Constraint operator <=(_EquationMember value) =>
+ _createConstraint(value, Relation.lessThanOrEqualTo);
+
+ operator ==(_EquationMember value) =>
+ _createConstraint(value, Relation.equalTo);
+
+ Expression operator +(_EquationMember m) {
+ if (m is ConstantMember) {
+ return new Expression(new List.from(terms), constant + m.value);
+ }
+
+ if (m is Param) {
+ return new Expression(
+ new List.from(terms)..add(new Term(m.variable, 1.0)), constant);
+ }
+
+ if (m is Term) {
+ return new Expression(new List.from(terms)..add(m), constant);
+ }
+
+ if (m is Expression) {
+ return new Expression(
+ new List.from(terms)..addAll(m.terms), constant + m.constant);
+ }
+
+ assert(false);
+ return null;
+ }
+
+ Expression operator -(_EquationMember m) {
+ if (m is ConstantMember) {
+ return new Expression(new List.from(terms), constant - m.value);
+ }
+
+ if (m is Param) {
+ return new Expression(
+ new List.from(terms)..add(new Term(m.variable, -1.0)), constant);
+ }
+
+ if (m is Term) {
+ return new Expression(new List.from(terms)
+ ..add(new Term(m.variable, -m.coefficient)), constant);
+ }
+
+ if (m is Expression) {
+ var copiedTerms = new List<Term>.from(terms);
+ m.terms.forEach(
+ (t) => copiedTerms.add(new Term(t.variable, -t.coefficient)));
+ return new Expression(copiedTerms, constant - m.constant);
+ }
+
+ assert(false);
+ return null;
+ }
+
+ _EquationMember _applyMultiplicand(double m) {
+ var newTerms = terms.fold(new List<Term>(), (list, term) => list
+ ..add(new Term(term.variable, term.coefficient * m)));
+ return new Expression(newTerms, constant * m);
+ }
+
+ _Pair<Expression, double> _findMulitplierAndMultiplicand(_EquationMember m) {
+ // At least on of the the two members must be constant for the resulting
+ // expression to be linear
+
+ if (!this.isConstant && !m.isConstant) {
+ return null;
+ }
+
+ if (this.isConstant) {
+ return new _Pair(m.asExpression(), this.value);
+ }
+
+ if (m.isConstant) {
+ return new _Pair(this.asExpression(), m.value);
+ }
+
+ assert(false);
+ return null;
+ }
+
+ _EquationMember operator *(_EquationMember m) {
+ _Pair<Expression, double> args = _findMulitplierAndMultiplicand(m);
+
+ if (args == null) {
+ throw new ParserException(
+ "Could not find constant multiplicand or multiplier", [this, m]);
+ return null;
+ }
+
+ return args.first._applyMultiplicand(args.second);
+ }
+
+ _EquationMember operator /(_EquationMember m) {
+ if (!m.isConstant) {
+ throw new ParserException(
+ "The divisor was not a constant expression", [this, m]);
+ return null;
+ }
+
+ return this._applyMultiplicand(1.0 / m.value);
+ }
+
+ String toString() {
+ StringBuffer buffer = new StringBuffer();
+
+ terms.forEach((t) => buffer.write("${t}"));
+
+ if (constant != 0.0) {
+ buffer.write(constant.sign > 0.0 ? "+" : "-");
+ buffer.write(constant.abs());
+ }
+
+ return buffer.toString();
+ }
+}
diff --git a/packages/cassowary/lib/param.dart b/packages/cassowary/lib/param.dart
new file mode 100644
index 0000000..6efe14d
--- /dev/null
+++ b/packages/cassowary/lib/param.dart
@@ -0,0 +1,29 @@
+// 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 Param extends _EquationMember {
+ final Variable variable;
+ dynamic context;
+
+ Param([double value = 0.0]) : variable = new Variable(value) {
+ variable._owner = this;
+ }
+
+ Param.withContext(ctx, [double value = 0.0])
+ : variable = new Variable(value),
+ context = ctx {
+ variable._owner = this;
+ }
+
+ bool get isConstant => false;
+
+ double get value => variable.value;
+
+ String get name => variable.name;
+ set name(String name) => variable.name = name;
+
+ Expression asExpression() => new Expression([new Term(variable, 1.0)], 0.0);
+}
diff --git a/packages/cassowary/lib/parser_exception.dart b/packages/cassowary/lib/parser_exception.dart
new file mode 100644
index 0000000..979533c
--- /dev/null
+++ b/packages/cassowary/lib/parser_exception.dart
@@ -0,0 +1,16 @@
+// 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 ParserException implements Exception {
+ final String message;
+ List<_EquationMember> members;
+ ParserException(this.message, this.members);
+
+ String toString() {
+ if (message == null) return "Error while parsing constraint or expression";
+ return "Error: '$message' while trying to parse constraint or expression";
+ }
+}
diff --git a/packages/cassowary/lib/priority.dart b/packages/cassowary/lib/priority.dart
new file mode 100644
index 0000000..9e432e1
--- /dev/null
+++ b/packages/cassowary/lib/priority.dart
@@ -0,0 +1,24 @@
+// 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 Priority {
+ static final double required = create(1e3, 1e3, 1e3);
+ static final double strong = create(1.0, 0.0, 0.0);
+ static final double medium = create(0.0, 1.0, 0.0);
+ static final double weak = create(0.0, 0.0, 1.0);
+
+ static double create(double a, double b, double c) {
+ double result = 0.0;
+ result += max(0.0, min(1e3, a)) * 1e6;
+ result += max(0.0, min(1e3, b)) * 1e3;
+ result += max(0.0, min(1e3, c));
+ return result;
+ }
+
+ static double clamp(double value) {
+ return max(0.0, min(required, value));
+ }
+}
diff --git a/packages/cassowary/lib/result.dart b/packages/cassowary/lib/result.dart
new file mode 100644
index 0000000..36c822b
--- /dev/null
+++ b/packages/cassowary/lib/result.dart
@@ -0,0 +1,29 @@
+// 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 Result {
+ final String message;
+ final bool error;
+
+ const Result(this.message, { bool isError: true }) : error = isError;
+
+ static final Result success = const Result("Success", isError: false);
+ static final Result unimplemented = const Result("Unimplemented");
+ static final Result duplicateConstraint =
+ const Result("Duplicate Constraint");
+ static final Result unsatisfiableConstraint =
+ const Result("Unsatisfiable Constraint");
+ static final Result unknownConstraint =
+ const Result("Unknown Constraint");
+ static final Result duplicateEditVariable =
+ const Result("Duplicate Edit Variable");
+ static final Result badRequiredStrength =
+ const Result("Bad Required Strength");
+ static final Result unknownEditVariable =
+ const Result("Unknown Edit Variable");
+ static final Result internalSolverError =
+ const Result("Internal Solver Error");
+}
diff --git a/packages/cassowary/lib/row.dart b/packages/cassowary/lib/row.dart
new file mode 100644
index 0000000..5c49c0c
--- /dev/null
+++ b/packages/cassowary/lib/row.dart
@@ -0,0 +1,78 @@
+// 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 _Row {
+ final Map<_Symbol, double> cells;
+ double constant = 0.0;
+
+ _Row(this.constant) : this.cells = new Map<_Symbol, double>();
+ _Row.fromRow(_Row row)
+ : this.cells = new Map<_Symbol, double>.from(row.cells),
+ this.constant = row.constant;
+
+ double add(double value) => constant += value;
+
+ void insertSymbol(_Symbol symbol, [double coefficient = 1.0]) {
+ double val = _elvis(cells[symbol], 0.0);
+
+ if (_nearZero(val + coefficient)) {
+ cells.remove(symbol);
+ } else {
+ cells[symbol] = val + coefficient;
+ }
+ }
+
+ void insertRow(_Row other, [double coefficient = 1.0]) {
+ constant += other.constant * coefficient;
+ other.cells.forEach((s, v) => insertSymbol(s, v * coefficient));
+ }
+
+ void removeSymbol(_Symbol symbol) {
+ cells.remove(symbol);
+ }
+
+ void reverseSign() {
+ constant = -constant;
+ cells.forEach((s, v) => cells[s] = -v);
+ }
+
+ void solveForSymbol(_Symbol symbol) {
+ assert(cells.containsKey(symbol));
+ double coefficient = -1.0 / cells[symbol];
+ cells.remove(symbol);
+ constant *= coefficient;
+ cells.forEach((s, v) => cells[s] = v * coefficient);
+ }
+
+ void solveForSymbols(_Symbol lhs, _Symbol rhs) {
+ insertSymbol(lhs, -1.0);
+ solveForSymbol(rhs);
+ }
+
+ double coefficientForSymbol(_Symbol symbol) => _elvis(cells[symbol], 0.0);
+
+ void substitute(_Symbol symbol, _Row row) {
+ double coefficient = cells[symbol];
+
+ if (coefficient == null) {
+ return;
+ }
+
+ cells.remove(symbol);
+ insertRow(row, coefficient);
+ }
+
+ String toString() {
+ StringBuffer buffer = new StringBuffer();
+
+ buffer.write(constant);
+
+ cells.forEach((symbol, value) =>
+ buffer.write(" + " + value.toString() + " * " + symbol.toString()));
+
+ return buffer.toString();
+ }
+}
diff --git a/packages/cassowary/lib/solver.dart b/packages/cassowary/lib/solver.dart
new file mode 100644
index 0000000..249560d
--- /dev/null
+++ b/packages/cassowary/lib/solver.dart
@@ -0,0 +1,652 @@
+// 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 {
+ 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);
+ int tick = 1;
+
+ /// 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) {
+ _SolverBulkUpdate applier = (Constraint c) => addConstraint(c);
+ _SolverBulkUpdate undoer = (Constraint c) => removeConstraint(c);
+
+ return _bulkEdit(constraints, applier, undoer);
+ }
+
+ Result addConstraint(Constraint constraint) {
+ if (_constraints.containsKey(constraint)) {
+ return Result.duplicateConstraint;
+ }
+
+ _Tag tag = new _Tag(new _Symbol(_SymbolType.invalid, 0),
+ new _Symbol(_SymbolType.invalid, 0));
+
+ _Row row = _createRow(constraint, tag);
+
+ _Symbol subject = _chooseSubjectForRow(row, tag);
+
+ if (subject.type == _SymbolType.invalid && _allDummiesInRow(row)) {
+ if (!_nearZero(row.constant)) {
+ return Result.unsatisfiableConstraint;
+ } else {
+ subject = tag.marker;
+ }
+ }
+
+ if (subject.type == _SymbolType.invalid) {
+ if (!_addWithArtificialVariableOnRow(row)) {
+ return Result.unsatisfiableConstraint;
+ }
+ } else {
+ row.solveForSymbol(subject);
+ _substitute(subject, row);
+ _rows[subject] = row;
+ }
+
+ _constraints[constraint] = tag;
+
+ return _optimizeObjectiveRow(_objective);
+ }
+
+ Result removeConstraints(List<Constraint> constraints) {
+ _SolverBulkUpdate applier = (Constraint c) => removeConstraint(c);
+ _SolverBulkUpdate undoer = (Constraint c) => addConstraint(c);
+
+ return _bulkEdit(constraints, applier, undoer);
+ }
+
+ Result removeConstraint(Constraint constraint) {
+ _Tag tag = _constraints[constraint];
+ if (tag == null) {
+ return Result.unknownConstraint;
+ }
+
+ tag = new _Tag.fromTag(tag);
+ _constraints.remove(constraint);
+
+ _removeConstraintEffects(constraint, tag);
+
+ _Row row = _rows[tag.marker];
+ if (row != null) {
+ _rows.remove(tag.marker);
+ } else {
+ _Pair<_Symbol, _Row> rowPair = _leavingRowPairForMarkerSymbol(tag.marker);
+
+ if (rowPair == null) {
+ return Result.internalSolverError;
+ }
+
+ _Symbol leaving = rowPair.first;
+ row = rowPair.second;
+ var removed = _rows.remove(rowPair.first);
+ assert(removed != null);
+ row.solveForSymbols(leaving, tag.marker);
+ _substitute(tag.marker, row);
+ }
+
+ return _optimizeObjectiveRow(_objective);
+ }
+
+ bool hasConstraint(Constraint constraint) {
+ return _constraints.containsKey(constraint);
+ }
+
+ 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);
+ }
+
+ 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);
+ constraint.priority = priority;
+
+ if (addConstraint(constraint) != Result.success) {
+ return Result.internalSolverError;
+ }
+
+ _EditInfo info = new _EditInfo();
+ info.tag = _constraints[constraint];
+ info.constraint = constraint;
+ info.constant = 0.0;
+
+ _edits[variable] = info;
+
+ return Result.success;
+ }
+
+ 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);
+ }
+
+ Result removeEditVariable(Variable variable) {
+ _EditInfo info = _edits[variable];
+ if (info == null) {
+ return Result.unknownEditVariable;
+ }
+
+ if (removeConstraint(info.constraint) != Result.success) {
+ return Result.internalSolverError;
+ }
+
+ _edits.remove(variable);
+ return Result.success;
+ }
+
+ bool hasEditVariable(Variable variable) {
+ return _edits.containsKey(variable);
+ }
+
+ Result suggestValueForVariable(Variable variable, double value) {
+ if (!_edits.containsKey(variable)) {
+ return Result.unknownEditVariable;
+ }
+
+ _suggestValueForEditInfoWithoutDualOptimization(_edits[variable], value);
+
+ return _dualOptimize();
+ }
+
+ Set flushUpdates() {
+ Set updates = new Set();
+
+ for (Variable variable in _vars.keys) {
+ _Symbol symbol = _vars[variable];
+ _Row row = _rows[symbol];
+
+ double updatedValue = row == null ? 0.0 : row.constant;
+
+ if (variable._applyUpdate(updatedValue) && variable._owner != null) {
+ dynamic context = variable._owner.context;
+
+ if (context != null) {
+ updates.add(context);
+ }
+ }
+ }
+
+ return updates;
+ }
+
+ 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;
+ }
+
+ _Symbol _symbolForVariable(Variable variable) {
+ _Symbol symbol = _vars[variable];
+
+ if (symbol != null) {
+ return symbol;
+ }
+
+ symbol = new _Symbol(_SymbolType.external, tick++);
+ _vars[variable] = symbol;
+
+ return symbol;
+ }
+
+ _Row _createRow(Constraint constraint, _Tag tag) {
+ Expression expr = new Expression.fromExpression(constraint.expression);
+ _Row row = new _Row(expr.constant);
+
+ expr.terms.forEach((term) {
+ if (!_nearZero(term.coefficient)) {
+ _Symbol symbol = _symbolForVariable(term.variable);
+
+ _Row foundRow = _rows[symbol];
+
+ 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;
+
+ _Symbol slack = new _Symbol(_SymbolType.slack, tick++);
+ tag.marker = slack;
+ row.insertSymbol(slack, coefficient);
+
+ if (constraint.priority < Priority.required) {
+ _Symbol error = new _Symbol(_SymbolType.error, tick++);
+ tag.other = error;
+ row.insertSymbol(error, -coefficient);
+ _objective.insertSymbol(error, constraint.priority);
+ }
+ }
+ break;
+ case Relation.equalTo:
+ if (constraint.priority < Priority.required) {
+ _Symbol errPlus = new _Symbol(_SymbolType.error, tick++);
+ _Symbol errMinus = new _Symbol(_SymbolType.error, tick++);
+ 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 {
+ _Symbol dummy = new _Symbol(_SymbolType.dummy, tick++);
+ tag.marker = dummy;
+ row.insertSymbol(dummy);
+ }
+ break;
+ }
+
+ if (row.constant < 0.0) {
+ row.reverseSign();
+ }
+
+ return row;
+ }
+
+ _Symbol _chooseSubjectForRow(_Row row, _Tag tag) {
+ for (_Symbol symbol in row.cells.keys) {
+ if (symbol.type == _SymbolType.external) {
+ return symbol;
+ }
+ }
+
+ if (tag.marker.type == _SymbolType.slack ||
+ tag.marker.type == _SymbolType.error) {
+ if (row.coefficientForSymbol(tag.marker) < 0.0) {
+ return tag.marker;
+ }
+ }
+
+ if (tag.other.type == _SymbolType.slack ||
+ tag.other.type == _SymbolType.error) {
+ if (row.coefficientForSymbol(tag.other) < 0.0) {
+ return tag.other;
+ }
+ }
+
+ return new _Symbol(_SymbolType.invalid, 0);
+ }
+
+ bool _allDummiesInRow(_Row row) {
+ for (_Symbol symbol in row.cells.keys) {
+ if (symbol.type != _SymbolType.dummy) {
+ return false;
+ }
+ }
+ return true;
+ }
+
+ bool _addWithArtificialVariableOnRow(_Row row) {
+ _Symbol artificial = new _Symbol(_SymbolType.slack, tick++);
+ _rows[artificial] = new _Row.fromRow(row);
+ _artificial = new _Row.fromRow(row);
+
+ Result result = _optimizeObjectiveRow(_artificial);
+
+ if (result.error) {
+ // FIXME(csg): Propagate this up!
+ return false;
+ }
+
+ bool success = _nearZero(_artificial.constant);
+ _artificial = new _Row(0.0);
+
+ _Row foundRow = _rows[artificial];
+ if (foundRow != null) {
+ _rows.remove(artificial);
+ if (foundRow.cells.isEmpty) {
+ return success;
+ }
+
+ _Symbol entering = _anyPivotableSymbol(foundRow);
+ if (entering.type == _SymbolType.invalid) {
+ return false;
+ }
+
+ foundRow.solveForSymbols(artificial, entering);
+ _substitute(entering, foundRow);
+ _rows[entering] = foundRow;
+ }
+
+ for (_Row row in _rows.values) {
+ row.removeSymbol(artificial);
+ }
+ _objective.removeSymbol(artificial);
+ return success;
+ }
+
+ Result _optimizeObjectiveRow(_Row objective) {
+ while (true) {
+ _Symbol entering = _enteringSymbolForObjectiveRow(objective);
+ if (entering.type == _SymbolType.invalid) {
+ return Result.success;
+ }
+
+ _Pair<_Symbol, _Row> leavingPair = _leavingRowForEnteringSymbol(entering);
+
+ if (leavingPair == null) {
+ return Result.internalSolverError;
+ }
+
+ _Symbol leaving = leavingPair.first;
+ _Row row = leavingPair.second;
+ _rows.remove(leavingPair.first);
+ row.solveForSymbols(leaving, entering);
+ _substitute(entering, row);
+ _rows[entering] = row;
+ }
+ }
+
+ _Symbol _enteringSymbolForObjectiveRow(_Row objective) {
+ Map<_Symbol, double> cells = objective.cells;
+
+ for (_Symbol symbol in cells.keys) {
+ if (symbol.type != _SymbolType.dummy && cells[symbol] < 0.0) {
+ return symbol;
+ }
+ }
+
+ return new _Symbol(_SymbolType.invalid, 0);
+ }
+
+ _Pair<_Symbol, _Row> _leavingRowForEnteringSymbol(_Symbol entering) {
+ double ratio = double.MAX_FINITE;
+ _Pair<_Symbol, _Row> result = new _Pair(null, null);
+
+ _rows.forEach((symbol, row) {
+ if (symbol.type != _SymbolType.external) {
+ double temp = row.coefficientForSymbol(entering);
+
+ if (temp < 0.0) {
+ double temp_ratio = -row.constant / temp;
+
+ if (temp_ratio < ratio) {
+ ratio = temp_ratio;
+ result.first = symbol;
+ result.second = row;
+ }
+ }
+ }
+ });
+
+ if (result.first == null || result.second == null) {
+ return null;
+ }
+
+ return result;
+ }
+
+ void _substitute(_Symbol symbol, _Row row) {
+ _rows.forEach((first, second) {
+ second.substitute(symbol, row);
+ if (first.type != _SymbolType.external && second.constant < 0.0) {
+ _infeasibleRows.add(first);
+ }
+ });
+
+ _objective.substitute(symbol, row);
+ if (_artificial != null) {
+ _artificial.substitute(symbol, row);
+ }
+ }
+
+ _Symbol _anyPivotableSymbol(_Row row) {
+ for (_Symbol symbol in row.cells.keys) {
+ if (symbol.type == _SymbolType.slack ||
+ symbol.type == _SymbolType.error) {
+ return symbol;
+ }
+ }
+ return new _Symbol(_SymbolType.invalid, 0);
+ }
+
+ void _removeConstraintEffects(Constraint cn, _Tag tag) {
+ if (tag.marker.type == _SymbolType.error) {
+ _removeMarkerEffects(tag.marker, cn.priority);
+ }
+ if (tag.other.type == _SymbolType.error) {
+ _removeMarkerEffects(tag.other, cn.priority);
+ }
+ }
+
+ void _removeMarkerEffects(_Symbol marker, double strength) {
+ _Row row = _rows[marker];
+ if (row != null) {
+ _objective.insertRow(row, -strength);
+ } else {
+ _objective.insertSymbol(marker, -strength);
+ }
+ }
+
+ _Pair<_Symbol, _Row> _leavingRowPairForMarkerSymbol(_Symbol marker) {
+ double r1 = double.MAX_FINITE;
+ double r2 = double.MAX_FINITE;
+
+ _Pair<_Symbol, _Row> first, second, third;
+
+ _rows.forEach((symbol, row) {
+ double c = row.coefficientForSymbol(marker);
+
+ if (c == 0.0) {
+ return;
+ }
+
+ if (symbol.type == _SymbolType.external) {
+ 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;
+ }
+
+ void _suggestValueForEditInfoWithoutDualOptimization(
+ _EditInfo info, double value) {
+ double delta = value - info.constant;
+ info.constant = value;
+
+ {
+ _Symbol symbol = info.tag.marker;
+ _Row row = _rows[info.tag.marker];
+
+ 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;
+ }
+ }
+
+ for (_Symbol symbol in _rows.keys) {
+ _Row row = _rows[symbol];
+ double coeff = row.coefficientForSymbol(info.tag.marker);
+ if (coeff != 0.0 &&
+ row.add(delta * coeff) < 0.0 &&
+ symbol.type != _SymbolType.external) {
+ _infeasibleRows.add(symbol);
+ }
+ }
+ }
+
+ Result _dualOptimize() {
+ while (_infeasibleRows.length != 0) {
+ _Symbol leaving = _infeasibleRows.removeLast();
+ _Row row = _rows[leaving];
+
+ if (row != null && row.constant < 0.0) {
+ _Symbol entering = _dualEnteringSymbolForRow(row);
+
+ if (entering.type == _SymbolType.invalid) {
+ return Result.internalSolverError;
+ }
+
+ _rows.remove(leaving);
+
+ row.solveForSymbols(leaving, entering);
+ _substitute(entering, row);
+ _rows[entering] = row;
+ }
+ }
+ return Result.success;
+ }
+
+ _Symbol _dualEnteringSymbolForRow(_Row row) {
+ _Symbol entering;
+
+ double ratio = double.MAX_FINITE;
+
+ Map<_Symbol, double> rowCells = row.cells;
+
+ for (_Symbol symbol in rowCells.keys) {
+ double value = rowCells[symbol];
+
+ if (value > 0.0 && symbol.type != _SymbolType.dummy) {
+ double coeff = _objective.coefficientForSymbol(symbol);
+ double r = coeff / value;
+ if (r < ratio) {
+ ratio = r;
+ entering = symbol;
+ }
+ }
+ }
+
+ return _elvis(entering, new _Symbol(_SymbolType.invalid, 0));
+ }
+
+ 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();
+ }
+}
+
+class _Tag {
+ _Symbol marker;
+ _Symbol other;
+
+ _Tag(this.marker, this.other);
+ _Tag.fromTag(_Tag tag)
+ : this.marker = tag.marker,
+ this.other = tag.other;
+}
+
+class _EditInfo {
+ _Tag tag;
+ Constraint constraint;
+ double constant;
+}
+
+bool _isValidNonRequiredPriority(double priority) {
+ return (priority >= 0.0 && priority < Priority.required);
+}
+
+typedef Result _SolverBulkUpdate(dynamic item);
diff --git a/packages/cassowary/lib/symbol.dart b/packages/cassowary/lib/symbol.dart
new file mode 100644
index 0000000..cd7bcf4
--- /dev/null
+++ b/packages/cassowary/lib/symbol.dart
@@ -0,0 +1,36 @@
+// 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;
+
+enum _SymbolType { invalid, external, slack, error, dummy, }
+
+class _Symbol {
+ final _SymbolType type;
+ final int tick;
+
+ _Symbol(this.type, this.tick);
+
+ String toString() {
+ String typeString = "unknown";
+ switch (type) {
+ case _SymbolType.invalid:
+ typeString = "i";
+ break;
+ case _SymbolType.external:
+ typeString = "v";
+ break;
+ case _SymbolType.slack:
+ typeString = "s";
+ break;
+ case _SymbolType.error:
+ typeString = "e";
+ break;
+ case _SymbolType.dummy:
+ typeString = "d";
+ break;
+ }
+ return "${typeString}${tick}";
+ }
+}
diff --git a/packages/cassowary/lib/term.dart b/packages/cassowary/lib/term.dart
new file mode 100644
index 0000000..5849f65
--- /dev/null
+++ b/packages/cassowary/lib/term.dart
@@ -0,0 +1,34 @@
+// 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 Term extends _EquationMember {
+ final Variable variable;
+ final double coefficient;
+
+ bool get isConstant => false;
+
+ double get value => coefficient * variable.value;
+
+ Term(this.variable, this.coefficient);
+
+ Expression asExpression() =>
+ new Expression([new Term(this.variable, this.coefficient)], 0.0);
+
+ String toString() {
+ StringBuffer buffer = new StringBuffer();
+
+ buffer.write(coefficient.sign > 0.0 ? "+" : "-");
+
+ if (coefficient.abs() != 1.0) {
+ buffer.write(coefficient.abs());
+ buffer.write("*");
+ }
+
+ buffer.write(variable);
+
+ return buffer.toString();
+ }
+}
diff --git a/packages/cassowary/lib/utils.dart b/packages/cassowary/lib/utils.dart
new file mode 100644
index 0000000..699a6ae
--- /dev/null
+++ b/packages/cassowary/lib/utils.dart
@@ -0,0 +1,21 @@
+// 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;
+
+bool _nearZero(double value) {
+ const double epsilon = 1.0e-8;
+ return value < 0.0 ? -value < epsilon : value < epsilon;
+}
+
+// Workaround for the lack of a null coalescing operator. Uses a ternary
+// instead. Sadly, due the lack of generic types on functions, we have to use
+// dynamic instead.
+_elvis(a, b) => a != null ? a : b;
+
+class _Pair<X, Y> {
+ X first;
+ Y second;
+ _Pair(this.first, this.second);
+}
diff --git a/packages/cassowary/lib/variable.dart b/packages/cassowary/lib/variable.dart
new file mode 100644
index 0000000..93850e7
--- /dev/null
+++ b/packages/cassowary/lib/variable.dart
@@ -0,0 +1,27 @@
+// 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 Variable {
+ double value;
+ String name;
+
+ Param _owner;
+
+ final int _tick;
+ static int _total = 0;
+
+ Variable(this.value) : _tick = _total++;
+
+ bool _applyUpdate(double updated) {
+ bool res = updated != value;
+ value = updated;
+ return res;
+ }
+
+ String get debugName => _elvis(name, "variable${_tick}");
+
+ String toString() => debugName;
+}
diff --git a/packages/cassowary/pubspec.yaml b/packages/cassowary/pubspec.yaml
new file mode 100644
index 0000000..5583877
--- /dev/null
+++ b/packages/cassowary/pubspec.yaml
@@ -0,0 +1,11 @@
+name: cassowary
+description: Cassowary Constraint Solving Toolkit
+version: 0.1.7
+author: Flutter Authors <flutter-dev@googlegroups.com>
+homepage: https://github.com/flutter/flutter/tree/master/packages/cassowary
+environment:
+ sdk: '>=1.0.0 <2.0.0'
+dev_dependencies:
+ test: '>=0.12.0 <0.13.0'
+ test_runner: '<=0.2.16'
+ dart_coveralls: '<=0.3.0'
diff --git a/packages/cassowary/test/cassowary_test.dart b/packages/cassowary/test/cassowary_test.dart
new file mode 100644
index 0000000..300f5e8
--- /dev/null
+++ b/packages/cassowary/test/cassowary_test.dart
@@ -0,0 +1,627 @@
+// 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.
+
+library cassowary.test;
+
+import 'package:test/test.dart';
+
+import 'package:cassowary/cassowary.dart';
+
+void main() {
+ test('variable', () {
+ var v = new Param(22.0);
+ expect(v.value, 22);
+ });
+
+ test('variable1', () {
+ var v = new Param(22.0);
+ expect((v + cm(22.0)).value, 44.0);
+ expect((v - cm(20.0)).value, 2.0);
+ });
+
+ test('term', () {
+ var t = new Term(new Variable(22.0), 2.0);
+ expect(t.value, 44);
+ });
+
+ test('expression', () {
+ var terms = [
+ new Term(new Variable(22.0), 2.0),
+ new Term(new Variable(1.0), 1.0),
+ ];
+ var e = new Expression(terms, 40.0);
+ expect(e.value, 85.0);
+ });
+
+ test('expression1', () {
+ var v1 = new Param(10.0);
+ var v2 = new Param(10.0);
+ var v3 = new Param(22.0);
+
+ expect(v1 is Param, true);
+ expect(v1 + cm(20.0) is Expression, true);
+ expect(v1 + v2 is Expression, true);
+
+ expect((v1 + v2).value, 20.0);
+ expect((v1 - v2).value, 0.0);
+
+ expect((v1 + v2 + v3) is Expression, true);
+ expect((v1 + v2 + v3).value, 42.0);
+ });
+
+ test('expression2', () {
+ var e = new Param(10.0) + cm(5.0);
+ expect(e.value, 15.0);
+ expect(e is Expression, true);
+
+ // Constant
+ expect((e + cm(2.0)) is Expression, true);
+ expect((e + cm(2.0)).value, 17.0);
+ expect((e - cm(2.0)) is Expression, true);
+ expect((e - cm(2.0)).value, 13.0);
+
+ expect(e.value, 15.0);
+
+ // Param
+ var v = new Param(2.0);
+ expect((e + v) is Expression, true);
+ expect((e + v).value, 17.0);
+ expect((e - v) is Expression, true);
+ expect((e - v).value, 13.0);
+
+ expect(e.value, 15.0);
+
+ // Term
+ var t = new Term(v.variable, 2.0);
+ expect((e + t) is Expression, true);
+ expect((e + t).value, 19.0);
+ expect((e - t) is Expression, true);
+ expect((e - t).value, 11.0);
+
+ expect(e.value, 15.0);
+
+ // Expression
+ var e2 = new Param(7.0) + new Param(3.0);
+ expect((e + e2) is Expression, true);
+ expect((e + e2).value, 25.0);
+ expect((e - e2) is Expression, true);
+ expect((e - e2).value, 5.0);
+
+ expect(e.value, 15.0);
+ });
+
+ test('term2', () {
+ var t = new Term(new Variable(12.0), 1.0);
+
+ // Constant
+ var c = cm(2.0);
+ expect((t + c) is Expression, true);
+ expect((t + c).value, 14.0);
+ expect((t - c) is Expression, true);
+ expect((t - c).value, 10.0);
+
+ // Variable
+ var v = new Param(2.0);
+ expect((t + v) is Expression, true);
+ expect((t + v).value, 14.0);
+ expect((t - v) is Expression, true);
+ expect((t - v).value, 10.0);
+
+ // Term
+ var t2 = new Term(new Variable(1.0), 2.0);
+ expect((t + t2) is Expression, true);
+ expect((t + t2).value, 14.0);
+ expect((t - t2) is Expression, true);
+ expect((t - t2).value, 10.0);
+
+ // Expression
+ var exp = new Param(1.0) + cm(1.0);
+ expect((t + exp) is Expression, true);
+ expect((t + exp).value, 14.0);
+ expect((t - exp) is Expression, true);
+ expect((t - exp).value, 10.0);
+ });
+
+ test('variable3', () {
+ var v = new Param(3.0);
+
+ // Constant
+ var c = cm(2.0);
+ expect((v + c) is Expression, true);
+ expect((v + c).value, 5.0);
+ expect((v - c) is Expression, true);
+ expect((v - c).value, 1.0);
+
+ // Variable
+ var v2 = new Param(2.0);
+ expect((v + v2) is Expression, true);
+ expect((v + v2).value, 5.0);
+ expect((v - v2) is Expression, true);
+ expect((v - v2).value, 1.0);
+
+ // Term
+ var t2 = new Term(new Variable(1.0), 2.0);
+ expect((v + t2) is Expression, true);
+ expect((v + t2).value, 5.0);
+ expect((v - t2) is Expression, true);
+ expect((v - t2).value, 1.0);
+
+ // Expression
+ var exp = new Param(1.0) + cm(1.0);
+ expect(exp.terms.length, 1);
+
+ expect((v + exp) is Expression, true);
+ expect((v + exp).value, 5.0);
+ expect((v - exp) is Expression, true);
+ expect((v - exp).value, 1.0);
+ });
+
+ test('constantmember', () {
+ var c = cm(3.0);
+
+ // Constant
+ var c2 = cm(2.0);
+ expect((c + c2) is Expression, true);
+ expect((c + c2).value, 5.0);
+ expect((c - c2) is Expression, true);
+ expect((c - c2).value, 1.0);
+
+ // Variable
+ var v2 = new Param(2.0);
+ expect((c + v2) is Expression, true);
+ expect((c + v2).value, 5.0);
+ expect((c - v2) is Expression, true);
+ expect((c - v2).value, 1.0);
+
+ // Term
+ var t2 = new Term(new Variable(1.0), 2.0);
+ expect((c + t2) is Expression, true);
+ expect((c + t2).value, 5.0);
+ expect((c - t2) is Expression, true);
+ expect((c - t2).value, 1.0);
+
+ // Expression
+ var exp = new Param(1.0) + cm(1.0);
+
+ expect((c + exp) is Expression, true);
+ expect((c + exp).value, 5.0);
+ expect((c - exp) is Expression, true);
+ expect((c - exp).value, 1.0);
+ });
+
+ test('constraint2', () {
+ var left = new Param(10.0);
+ var right = new Param(100.0);
+
+ var c = right - left >= cm(25.0);
+ expect(c is Constraint, true);
+ });
+
+ test('simple_multiplication', () {
+ // Constant
+ var c = cm(20.0);
+ expect((c * cm(2.0)).value, 40.0);
+
+ // Variable
+ var v = new Param(20.0);
+ expect((v * cm(2.0)).value, 40.0);
+
+ // Term
+ var t = new Term(v.variable, 1.0);
+ expect((t * cm(2.0)).value, 40.0);
+
+ // Expression
+ var e = new Expression([t], 0.0);
+ expect((e * cm(2.0)).value, 40.0);
+ });
+
+ test('simple_division', () {
+ // Constant
+ var c = cm(20.0);
+ expect((c / cm(2.0)).value, 10.0);
+
+ // Variable
+ var v = new Param(20.0);
+ expect((v / cm(2.0)).value, 10.0);
+
+ // Term
+ var t = new Term(v.variable, 1.0);
+ expect((t / cm(2.0)).value, 10.0);
+
+ // Expression
+ var e = new Expression([t], 0.0);
+ expect((e / cm(2.0)).value, 10.0);
+ });
+
+ test('full_constraints_setup', () {
+ var left = new Param(2.0);
+ var right = new Param(10.0);
+
+ var c1 = right - left >= cm(20.0);
+ expect(c1 is Constraint, true);
+ expect(c1.expression.constant, -20.0);
+ expect(c1.relation, Relation.greaterThanOrEqualTo);
+
+ var c2 = (right - left == cm(30.0)) as Constraint;
+ expect(c2 is Constraint, true);
+ expect(c2.expression.constant, -30.0);
+ expect(c2.relation, Relation.equalTo);
+
+ var c3 = right - left <= cm(30.0);
+ expect(c3 is Constraint, true);
+ expect(c3.expression.constant, -30.0);
+ expect(c3.relation, Relation.lessThanOrEqualTo);
+ });
+
+ test('constraint_strength_update', () {
+ var left = new Param(2.0);
+ var right = new Param(10.0);
+
+ var c = (right - left >= cm(200.0)) | 750.0;
+ expect(c is Constraint, true);
+ expect(c.expression.terms.length, 2);
+ expect(c.expression.constant, -200.0);
+ expect(c.priority, 750.0);
+ });
+
+ test('solver', () {
+ var s = new Solver();
+
+ var left = new Param(2.0);
+ var right = new Param(100.0);
+
+ var c1 = right - left >= cm(200.0);
+
+ expect((right >= left) is Constraint, true);
+
+ expect(s.addConstraint(c1), Result.success);
+ });
+
+ test('constraint_complex', () {
+ var e = new Param(200.0) - new Param(100.0);
+
+ // Constant
+ var c1 = e >= cm(50.0);
+ expect(c1 is Constraint, true);
+ expect(c1.expression.terms.length, 2);
+ expect(c1.expression.constant, -50.0);
+
+ // Variable
+ var c2 = e >= new Param(2.0);
+ expect(c2 is Constraint, true);
+ expect(c2.expression.terms.length, 3);
+ expect(c2.expression.constant, 0.0);
+
+ // Term
+ var c3 = e >= new Term(new Variable(2.0), 1.0);
+ expect(c3 is Constraint, true);
+ expect(c3.expression.terms.length, 3);
+ expect(c3.expression.constant, 0.0);
+
+ // Expression
+ var c4 = e >= new Expression([new Term(new Variable(2.0), 1.0)], 20.0);
+ expect(c4 is Constraint, true);
+ expect(c4.expression.terms.length, 3);
+ expect(c4.expression.constant, -20.0);
+ });
+
+ test('constraint_complex_non_exprs', () {
+ // Constant
+ var c1 = cm(100.0) >= cm(50.0);
+ expect(c1 is Constraint, true);
+ expect(c1.expression.terms.length, 0);
+ expect(c1.expression.constant, 50.0);
+
+ // Variable
+ var c2 = new Param(100.0) >= new Param(2.0);
+ expect(c2 is Constraint, true);
+ expect(c2.expression.terms.length, 2);
+ expect(c2.expression.constant, 0.0);
+
+ // Term
+ var t = new Term(new Variable(100.0), 1.0);
+ var c3 = t >= new Term(new Variable(2.0), 1.0);
+ expect(c3 is Constraint, true);
+ expect(c3.expression.terms.length, 2);
+ expect(c3.expression.constant, 0.0);
+
+ // Expression
+ var e = new Expression([t], 0.0);
+ var c4 = e >= new Expression([new Term(new Variable(2.0), 1.0)], 20.0);
+ expect(c4 is Constraint, true);
+ expect(c4.expression.terms.length, 2);
+ expect(c4.expression.constant, -20.0);
+ });
+
+ test('constraint_update_in_solver', () {
+ var s = new Solver();
+
+ var left = new Param(2.0);
+ var right = new Param(100.0);
+
+ var c1 = right - left >= cm(200.0);
+ var c2 = right >= right;
+
+ expect(s.addConstraint(c1), Result.success);
+ expect(s.addConstraint(c1), Result.duplicateConstraint);
+ expect(s.removeConstraint(c2), Result.unknownConstraint);
+ expect(s.removeConstraint(c1), Result.success);
+ expect(s.removeConstraint(c1), Result.unknownConstraint);
+ });
+
+ test('test_multiplication_division_override', () {
+ var c = cm(10.0);
+ var v = new Param(c.value);
+ var t = new Term(v.variable, 1.0);
+ var e = new Expression([t], 0.0);
+
+ // Constant
+ expect((c * cm(10.0)).value, 100);
+
+ // Variable
+ expect((v * cm(10.0)).value, 100);
+
+ // Term
+ expect((t * cm(10.0)).value, 100);
+
+ // Expression
+ expect((e * cm(10.0)).value, 100);
+
+ // Constant
+ expect((c / cm(10.0)).value, 1);
+
+ // Variable
+ expect((v / cm(10.0)).value, 1);
+
+ // Term
+ expect((t / cm(10.0)).value, 1);
+
+ // Expression
+ expect((e / cm(10.0)).value, 1);
+ });
+
+ test('test_multiplication_division_exceptions', () {
+ var c = cm(10.0);
+ var v = new Param(c.value);
+ var t = new Term(v.variable, 1.0);
+ var e = new Expression([t], 0.0);
+
+ expect((c * c).value, 100);
+ expect(() => v * v, throwsA(new isInstanceOf<ParserException>()));
+ expect(() => v / v, throwsA(new isInstanceOf<ParserException>()));
+ expect(() => v * t, throwsA(new isInstanceOf<ParserException>()));
+ expect(() => v / t, throwsA(new isInstanceOf<ParserException>()));
+ expect(() => v * e, throwsA(new isInstanceOf<ParserException>()));
+ expect(() => v / e, throwsA(new isInstanceOf<ParserException>()));
+ expect(() => v * c, returnsNormally);
+ expect(() => v / c, returnsNormally);
+ });
+
+ test('edit_updates', () {
+ Solver s = new Solver();
+
+ var left = new Param(0.0);
+ var right = new Param(100.0);
+ var mid = new Param(0.0);
+
+ Constraint c = left + right >= cm(2.0) * mid;
+ expect(s.addConstraint(c), Result.success);
+
+ expect(s.addEditVariable(mid.variable, 999.0), Result.success);
+ expect(
+ s.addEditVariable(mid.variable, 999.0), Result.duplicateEditVariable);
+ expect(s.removeEditVariable(mid.variable), Result.success);
+ expect(s.removeEditVariable(mid.variable), Result.unknownEditVariable);
+ });
+
+ test('bug1', () {
+ var left = new Param(0.0);
+ var right = new Param(100.0);
+ var mid = new Param(0.0);
+
+ expect(((left + right) >= (cm(2.0) * mid)) is Constraint, true);
+ });
+
+ test('single_item', () {
+ var left = new Param(-20.0);
+ Solver s = new Solver();
+ s.addConstraint(left >= cm(0.0));
+ s.flushUpdates();
+ expect(left.value, 0.0);
+ });
+
+ test('midpoints', () {
+ var left = new Param(0.0)..name = "left";
+ var right = new Param(0.0)..name = "right";
+ var mid = new Param(0.0)..name = "mid";
+
+ Solver s = new Solver();
+
+ expect(s.addConstraint((right + left == mid * cm(2.0)) as Constraint),
+ Result.success);
+ expect(s.addConstraint(right - left >= cm(100.0)), Result.success);
+ expect(s.addConstraint(left >= cm(0.0)), Result.success);
+
+ s.flushUpdates();
+
+ expect(left.value, 0.0);
+ expect(mid.value, 50.0);
+ expect(right.value, 100.0);
+ });
+
+ test('addition_of_multiple', () {
+ var left = new Param(0.0);
+ var right = new Param(0.0);
+ var mid = new Param(0.0);
+
+ Solver s = new Solver();
+
+ var c = (left >= cm(0.0));
+
+ expect(s.addConstraints([
+ (left + right == cm(2.0) * mid) as Constraint,
+ (right - left >= cm(100.0)),
+ c
+ ]), Result.success);
+
+ expect(s.addConstraints([(right >= cm(-20.0)), c]),
+ Result.duplicateConstraint);
+ });
+
+ test('edit_constraints', () {
+ var left = new Param(0.0)..name = "left";
+ var right = new Param(0.0)..name = "right";
+ var mid = new Param(0.0)..name = "mid";
+
+ Solver s = new Solver();
+
+ expect(s.addConstraint((right + left == mid * cm(2.0)) as Constraint),
+ Result.success);
+ expect(s.addConstraint(right - left >= cm(100.0)), Result.success);
+ expect(s.addConstraint(left >= cm(0.0)), Result.success);
+
+ expect(s.addEditVariable(mid.variable, Priority.strong), Result.success);
+ expect(s.suggestValueForVariable(mid.variable, 300.0), Result.success);
+
+ s.flushUpdates();
+
+ expect(left.value, 0.0);
+ expect(mid.value, 300.0);
+ expect(right.value, 600.0);
+ });
+
+ test('test_description', () {
+ var left = new Param(0.0);
+ var right = new Param(100.0);
+ var c1 = right >= left;
+ var c2 = right <= left;
+ var c3 = (right == left) as Constraint;
+
+ Solver s = new Solver();
+ expect(s.addConstraint(c1), Result.success);
+ expect(s.addConstraint(c2), Result.success);
+ expect(s.addConstraint(c3), Result.success);
+
+ expect(s.toString() != null, true);
+ });
+
+ test('solution_with_optimize', () {
+ Param p1 = new Param();
+ Param p2 = new Param();
+ Param p3 = new Param();
+
+ Param container = new Param();
+
+ Solver solver = new Solver();
+
+ solver.addEditVariable(container.variable, Priority.strong);
+ solver.suggestValueForVariable(container.variable, 100.0);
+
+ solver.addConstraint((p1 >= cm(30.0)) | Priority.strong);
+ solver.addConstraint(((p1 == p3) as Constraint) | Priority.medium);
+ solver.addConstraint((p2 == cm(2.0) * p1) as Constraint);
+ solver.addConstraint((container == (p1 + p2 + p3)) as Constraint);
+
+ solver.flushUpdates();
+
+ expect(container.value, 100.0);
+
+ expect(p1.value, 30.0);
+ expect(p2.value, 60.0);
+ expect(p3.value, 10.0);
+ });
+
+ test('test_updates_collection', () {
+ Param left = new Param.withContext("left");
+ Param mid = new Param.withContext("mid");
+ Param right = new Param.withContext("right");
+
+ Solver s = new Solver();
+
+ expect(s.addEditVariable(mid.variable, Priority.strong), Result.success);
+
+ expect(s.addConstraint((mid * cm(2.0) == left + right) as Constraint),
+ Result.success);
+ expect(s.addConstraint(left >= cm(0.0)), Result.success);
+
+ expect(s.suggestValueForVariable(mid.variable, 50.0), Result.success);
+
+ var updates = s.flushUpdates();
+
+ expect(updates.length, 2);
+
+ expect(left.value, 0.0);
+ expect(mid.value, 50.0);
+ expect(right.value, 100.0);
+ });
+
+ test('test_updates_collection_is_set', () {
+ Param left = new Param.withContext("a");
+ Param mid = new Param.withContext("a");
+ Param right = new Param.withContext("a");
+
+ Solver s = new Solver();
+
+ expect(s.addEditVariable(mid.variable, Priority.strong), Result.success);
+
+ expect(s.addConstraint((mid * cm(2.0) == left + right) as Constraint),
+ Result.success);
+ expect(s.addConstraint(left >= cm(10.0)), Result.success);
+
+ expect(s.suggestValueForVariable(mid.variable, 50.0), Result.success);
+
+ var updates = s.flushUpdates();
+
+ expect(updates.length, 1);
+
+ expect(left.value, 10.0);
+ expect(mid.value, 50.0);
+ expect(right.value, 90.0);
+ });
+
+ test('param_context_non_final', () {
+ var p = new Param.withContext("a");
+ p.context = "b";
+ expect(p.context, "b");
+ });
+
+ test('check_type_of_eq_result', () {
+ Param left = new Param();
+ Param right = new Param();
+
+ expect((left == right).runtimeType, Constraint);
+ });
+
+ test('bulk_add_edit_variables', () {
+ Solver s = new Solver();
+
+ var left = new Param(0.0);
+ var right = new Param(100.0);
+ var mid = new Param(0.0);
+
+ expect(s.addEditVariables(
+ [left.variable, right.variable, mid.variable], 999.0), Result.success);
+ });
+
+ test('bulk_remove_constraints_and_variables', () {
+ Solver s = new Solver();
+
+ var left = new Param(0.0);
+ var right = new Param(100.0);
+ var mid = new Param(0.0);
+
+ expect(s.addEditVariables(
+ [left.variable, right.variable, mid.variable], 999.0), Result.success);
+
+ var c1 = left <= mid;
+ var c2 = mid <= right;
+
+ expect(s.addConstraints([c1, c2]), Result.success);
+
+ expect(s.removeConstraints([c1, c2]), Result.success);
+
+ expect(s.removeEditVariables(
+ [left.variable, right.variable, mid.variable]), Result.success);
+ });
+}
diff --git a/packages/newton/README.md b/packages/newton/README.md
new file mode 100644
index 0000000..ccd16ea
--- /dev/null
+++ b/packages/newton/README.md
@@ -0,0 +1,9 @@
+# Newton
+[](https://travis-ci.org/flutter/newton)
+[](https://coveralls.io/r/domokit/newton?branch=master)
+
+Simple Physics Simulations for Dart. Springs, friction, gravity, etc.
+
+To run the tests:
+pub get
+dart test/newton_test.dart
diff --git a/packages/newton/lib/newton.dart b/packages/newton/lib/newton.dart
new file mode 100644
index 0000000..c70ca3c
--- /dev/null
+++ b/packages/newton/lib/newton.dart
@@ -0,0 +1,18 @@
+// 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.
+
+library newton;
+
+import 'dart:math' as math;
+
+part 'src/simulation.dart';
+part 'src/simulation_group.dart';
+part 'src/tolerance.dart';
+part 'src/utils.dart';
+
+part 'src/friction_simulation.dart';
+part 'src/gravity_simulation.dart';
+part 'src/scroll_simulation.dart';
+part 'src/spring_simulation.dart';
+part 'src/spring_solution.dart';
diff --git a/packages/newton/lib/src/friction_simulation.dart b/packages/newton/lib/src/friction_simulation.dart
new file mode 100644
index 0000000..38671b9
--- /dev/null
+++ b/packages/newton/lib/src/friction_simulation.dart
@@ -0,0 +1,68 @@
+// 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 newton;
+
+class FrictionSimulation extends Simulation {
+ final double _drag;
+ final double _dragLog;
+ final double _x;
+ final double _v;
+
+ FrictionSimulation(double drag, double position, double velocity)
+ : _drag = drag,
+ _dragLog = math.log(drag),
+ _x = position,
+ _v = velocity;
+
+ // Return the drag value for a FrictionSimulation whose x() and dx() values pass
+ // through the specified start and end position/velocity values.
+ //
+ // Total time to reach endVelocity is just: (log(endVelocity) / log(startVelocity)) / log(_drag)
+ // or (log(v1) - log(v0)) / log(D), given v = v0 * D^t per the dx() function below.
+ // Solving for D given x(time) is trickier. Algebra courtesy of Wolfram Alpha:
+ // x1 = x0 + (v0 * D^((log(v1) - log(v0)) / log(D))) / log(D) - v0 / log(D), find D
+ static double _dragFor(double startPosition, double endPosition, double startVelocity, double endVelocity) {
+ return math.pow(math.E, (startVelocity - endVelocity) / (startPosition - endPosition));
+ }
+
+ // A friction simulation that starts and ends at the specified positions
+ // and velocities.
+ factory FrictionSimulation.through(double startPosition, double endPosition, double startVelocity, double endVelocity) {
+ return new FrictionSimulation(
+ _dragFor(startPosition, endPosition, startVelocity, endVelocity),
+ startPosition,
+ startVelocity)
+ .. tolerance = new Tolerance(velocity: endVelocity.abs());
+ }
+
+ double x(double time) => _x + _v * math.pow(_drag, time) / _dragLog - _v / _dragLog;
+
+ double dx(double time) => _v * math.pow(_drag, time);
+
+ @override
+ bool isDone(double time) => dx(time).abs() < this.tolerance.velocity;
+}
+
+class BoundedFrictionSimulation extends FrictionSimulation {
+ BoundedFrictionSimulation(
+ double drag,
+ double position,
+ double velocity,
+ double this._minX,
+ double this._maxX) : super(drag, position, velocity);
+
+ final double _minX;
+ final double _maxX;
+
+ double x(double time) {
+ return super.x(time).clamp(_minX, _maxX);
+ }
+
+ bool isDone(double time) {
+ return super.isDone(time) ||
+ (x(time) - _minX).abs() < tolerance.distance ||
+ (x(time) - _maxX).abs() < tolerance.distance;
+ }
+}
diff --git a/packages/newton/lib/src/gravity_simulation.dart b/packages/newton/lib/src/gravity_simulation.dart
new file mode 100644
index 0000000..2f002b7
--- /dev/null
+++ b/packages/newton/lib/src/gravity_simulation.dart
@@ -0,0 +1,26 @@
+// 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 newton;
+
+class GravitySimulation extends Simulation {
+ final double _x;
+ final double _v;
+ final double _a;
+ final double _end;
+
+ GravitySimulation(
+ double acceleration, double distance, double endDistance, double velocity)
+ : _a = acceleration,
+ _x = distance,
+ _v = velocity,
+ _end = endDistance;
+
+ double x(double time) => _x + _v * time + 0.5 * _a * time * time;
+
+ double dx(double time) => _v + time * _a;
+
+ @override
+ bool isDone(double time) => x(time).abs() >= _end;
+}
diff --git a/packages/newton/lib/src/scroll_simulation.dart b/packages/newton/lib/src/scroll_simulation.dart
new file mode 100644
index 0000000..64e0a45
--- /dev/null
+++ b/packages/newton/lib/src/scroll_simulation.dart
@@ -0,0 +1,67 @@
+// 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 newton;
+
+/// Simulates kinetic scrolling behavior between a leading and trailing
+/// boundary. Friction is applied within the extends and a spring action applied
+/// at the boundaries. This simulation can only step forward.
+class ScrollSimulation extends SimulationGroup {
+ ScrollSimulation(
+ double position,
+ double velocity,
+ this._leadingExtent,
+ this._trailingExtent,
+ this._spring,
+ this._drag) {
+ _chooseSimulation(position, velocity, 0.0);
+ }
+
+ final double _leadingExtent;
+ final double _trailingExtent;
+ final SpringDescription _spring;
+ final double _drag;
+
+ bool _isSpringing = false;
+ Simulation _currentSimulation;
+ double _offset = 0.0;
+
+ @override
+ bool step(double time) => _chooseSimulation(
+ _currentSimulation.x(time - _offset),
+ _currentSimulation.dx(time - _offset), time);
+
+ @override
+ Simulation get currentSimulation => _currentSimulation;
+
+ @override
+ double get currentIntervalOffset => _offset;
+
+ bool _chooseSimulation(double position, double velocity, double intervalOffset) {
+ if (_spring == null && (position > _trailingExtent || position < _leadingExtent))
+ return false;
+
+ /// This simulation can only step forward.
+ if (!_isSpringing) {
+ if (position > _trailingExtent) {
+ _isSpringing = true;
+ _offset = intervalOffset;
+ _currentSimulation = new ScrollSpringSimulation(_spring, position, _trailingExtent, velocity);
+ return true;
+ } else if (position < _leadingExtent) {
+ _isSpringing = true;
+ _offset = intervalOffset;
+ _currentSimulation = new ScrollSpringSimulation(_spring, position, _leadingExtent, velocity);
+ return true;
+ }
+ }
+
+ if (_currentSimulation == null) {
+ _currentSimulation = new FrictionSimulation(_drag, position, velocity);
+ return true;
+ }
+
+ return false;
+ }
+}
diff --git a/packages/newton/lib/src/simulation.dart b/packages/newton/lib/src/simulation.dart
new file mode 100644
index 0000000..e374c9d
--- /dev/null
+++ b/packages/newton/lib/src/simulation.dart
@@ -0,0 +1,23 @@
+// 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 newton;
+
+abstract class Simulatable {
+ /// The current position of the object in the simulation
+ double x(double time);
+
+ /// The current velocity of the object in the simulation
+ double dx(double time);
+}
+
+/// The base class for all simulations. The user is meant to instantiate an
+/// instance of a simulation and query the same for the position and velocity
+/// of the body at a given interval.
+abstract class Simulation implements Simulatable {
+ Tolerance tolerance = toleranceDefault;
+
+ /// Returns if the simulation is done at a given time
+ bool isDone(double time);
+}
diff --git a/packages/newton/lib/src/simulation_group.dart b/packages/newton/lib/src/simulation_group.dart
new file mode 100644
index 0000000..a7359da
--- /dev/null
+++ b/packages/newton/lib/src/simulation_group.dart
@@ -0,0 +1,58 @@
+// 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 newton;
+
+/// The abstract base class for all composite simulations. Concrete subclasses
+/// must implement the appropriate methods to select the appropriate simulation
+/// at a given time interval. The simulation group takes care to call the `step`
+/// method at appropriate intervals. If more fine grained control over the the
+/// step is necessary, subclasses may override `Simulatable` methods.
+abstract class SimulationGroup extends Simulation {
+
+ /// The currently active simulation
+ Simulation get currentSimulation;
+
+ /// The time offset applied to the currently active simulation;
+ double get currentIntervalOffset;
+
+ /// Called when a significant change in the interval is detected. Subclasses
+ /// must decide if the the current simulation must be switched (or updated).
+ /// The result is whether the simulation was switched in this step.
+ bool step(double time);
+
+ double x(double time) {
+ _stepIfNecessary(time);
+ return currentSimulation.x(time - currentIntervalOffset);
+ }
+
+ double dx(double time) {
+ _stepIfNecessary(time);
+ return currentSimulation.dx(time - currentIntervalOffset);
+ }
+
+ @override
+ void set tolerance(Tolerance t) {
+ this.currentSimulation.tolerance = t;
+ super.tolerance = t;
+ }
+
+ @override
+ bool isDone(double time) {
+ _stepIfNecessary(time);
+ return currentSimulation.isDone(time - currentIntervalOffset);
+ }
+
+ double _lastStep = -1.0;
+ void _stepIfNecessary(double time) {
+ if (_nearEqual(_lastStep, time, toleranceDefault.time)) {
+ return;
+ }
+
+ _lastStep = time;
+ if (step(time)) {
+ this.currentSimulation.tolerance = this.tolerance;
+ }
+ }
+}
diff --git a/packages/newton/lib/src/spring_simulation.dart b/packages/newton/lib/src/spring_simulation.dart
new file mode 100644
index 0000000..143f96c
--- /dev/null
+++ b/packages/newton/lib/src/spring_simulation.dart
@@ -0,0 +1,83 @@
+// 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 newton;
+
+class SpringDescription {
+ /// The mass of the spring (m)
+ final double mass;
+
+ /// The spring constant (k)
+ final double springConstant;
+
+ /// The damping coefficient.
+ /// Note: Not to be confused with the damping ratio. Use the separate
+ /// constructor provided for this purpose
+ final double damping;
+
+ SpringDescription(
+ {double this.mass, double this.springConstant, double this.damping}) {
+ assert(mass != null);
+ assert(springConstant != null);
+ assert(damping != null);
+ }
+
+ /// Create a spring given the mass, spring constant and the damping ratio. The
+ /// damping ratio is especially useful trying to determing the type of spring
+ /// to create. A ratio of 1.0 creates a critically damped spring, > 1.0
+ /// creates an overdamped spring and < 1.0 an underdamped one.
+ SpringDescription.withDampingRatio(
+ {double mass, double springConstant, double ratio: 1.0})
+ : mass = mass,
+ springConstant = springConstant,
+ damping = ratio * 2.0 * math.sqrt(mass * springConstant);
+}
+
+enum SpringType { unknown, criticallyDamped, underDamped, overDamped, }
+
+/// Creates a spring simulation. Depending on the spring description, a
+/// critically, under or overdamped spring will be created.
+class SpringSimulation extends Simulation {
+ final double _endPosition;
+
+ final _SpringSolution _solution;
+
+ /// A spring description with the provided spring description, start distance,
+ /// end distance and velocity.
+ SpringSimulation(
+ SpringDescription desc, double start, double end, double velocity)
+ : this._endPosition = end,
+ _solution = new _SpringSolution(desc, start - end, velocity);
+
+ SpringType get type => _solution.type;
+
+ double x(double time) => _endPosition + _solution.x(time);
+
+ double dx(double time) => _solution.dx(time);
+
+ @override
+ bool isDone(double time) =>
+ _nearEqual(x(time), _endPosition, this.tolerance.distance) &&
+ _nearZero(dx(time), this.tolerance.velocity);
+}
+
+/// A SpringSimulation where the value of x() is guaranteed to have exactly the
+/// end value when the simulation isDone().
+class ScrollSpringSimulation extends SpringSimulation {
+ ScrollSpringSimulation(SpringDescription desc, double start, double end, double velocity)
+ : super(desc, start, end, velocity);
+
+ bool _isDone(double position, double velocity) {
+ return _nearEqual(position, _endPosition, tolerance.distance) && _nearZero(velocity, tolerance.velocity);
+ }
+
+ @override
+ double x(double time) {
+ double xAtTime = super.x(time);
+ return _isDone(xAtTime, dx(time)) ? _endPosition : xAtTime;
+ }
+
+ @override
+ bool isDone(double time) => _isDone(x(time), dx(time));
+}
diff --git a/packages/newton/lib/src/spring_solution.dart b/packages/newton/lib/src/spring_solution.dart
new file mode 100644
index 0000000..3241311
--- /dev/null
+++ b/packages/newton/lib/src/spring_solution.dart
@@ -0,0 +1,118 @@
+// 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 newton;
+
+abstract class _SpringSolution implements Simulatable {
+ factory _SpringSolution(
+ SpringDescription desc, double initialPosition, double initialVelocity) {
+ double cmk =
+ desc.damping * desc.damping - 4 * desc.mass * desc.springConstant;
+
+ if (cmk == 0.0) {
+ return new _CriticalSolution(desc, initialPosition, initialVelocity);
+ } else if (cmk > 0.0) {
+ return new _OverdampedSolution(desc, initialPosition, initialVelocity);
+ } else {
+ return new _UnderdampedSolution(desc, initialPosition, initialVelocity);
+ }
+
+ return null;
+ }
+
+ SpringType get type;
+}
+
+class _CriticalSolution implements _SpringSolution {
+ final double _r, _c1, _c2;
+
+ factory _CriticalSolution(
+ SpringDescription desc, double distance, double velocity) {
+ final double r = -desc.damping / (2.0 * desc.mass);
+ final double c1 = distance;
+ final double c2 = velocity / (r * distance);
+ return new _CriticalSolution.withArgs(r, c1, c2);
+ }
+
+ SpringType get type => SpringType.criticallyDamped;
+
+ _CriticalSolution.withArgs(double r, double c1, double c2)
+ : _r = r,
+ _c1 = c1,
+ _c2 = c2;
+
+ double x(double time) => (_c1 + _c2 * time) * math.pow(math.E, _r * time);
+
+ double dx(double time) {
+ final double power = math.pow(math.E, _r * time);
+ return _r * (_c1 + _c2 * time) * power + _c2 * power;
+ }
+}
+
+class _OverdampedSolution implements _SpringSolution {
+ final double _r1, _r2, _c1, _c2;
+
+ factory _OverdampedSolution(
+ SpringDescription desc, double distance, double velocity) {
+ final double cmk =
+ desc.damping * desc.damping - 4 * desc.mass * desc.springConstant;
+
+ final double r1 = (-desc.damping - math.sqrt(cmk)) / (2.0 * desc.mass);
+ final double r2 = (-desc.damping + math.sqrt(cmk)) / (2.0 * desc.mass);
+ final double c2 = (velocity - r1 * distance) / (r2 - r1);
+ final double c1 = distance - c2;
+
+ return new _OverdampedSolution.withArgs(r1, r2, c1, c2);
+ }
+
+ _OverdampedSolution.withArgs(double r1, double r2, double c1, double c2)
+ : _r1 = r1,
+ _r2 = r2,
+ _c1 = c1,
+ _c2 = c2;
+
+ SpringType get type => SpringType.overDamped;
+
+ double x(double time) =>
+ (_c1 * math.pow(math.E, _r1 * time) + _c2 * math.pow(math.E, _r2 * time));
+
+ double dx(double time) => (_c1 * _r1 * math.pow(math.E, _r1 * time) +
+ _c2 * _r2 * math.pow(math.E, _r2 * time));
+}
+
+class _UnderdampedSolution implements _SpringSolution {
+ final double _w, _r, _c1, _c2;
+
+ factory _UnderdampedSolution(
+ SpringDescription desc, double distance, double velocity) {
+ final double w = math.sqrt(4.0 * desc.mass * desc.springConstant -
+ desc.damping * desc.damping) /
+ (2.0 * desc.mass);
+ final double r = -(desc.damping / 2.0 * desc.mass);
+ final double c1 = distance;
+ final double c2 = (velocity - r * distance) / w;
+
+ return new _UnderdampedSolution.withArgs(w, r, c1, c2);
+ }
+
+ _UnderdampedSolution.withArgs(double w, double r, double c1, double c2)
+ : _w = w,
+ _r = r,
+ _c1 = c1,
+ _c2 = c2;
+
+ SpringType get type => SpringType.underDamped;
+
+ double x(double time) => math.pow(math.E, _r * time) *
+ (_c1 * math.cos(_w * time) + _c2 * math.sin(_w * time));
+
+ double dx(double time) {
+ final double power = math.pow(math.E, _r * time);
+ final double cosine = math.cos(_w * time);
+ final double sine = math.sin(_w * time);
+
+ return power * (_c2 * _w * cosine - _c1 * _w * sine) +
+ _r * power * (_c2 * sine + _c1 * cosine);
+ }
+}
diff --git a/packages/newton/lib/src/tolerance.dart b/packages/newton/lib/src/tolerance.dart
new file mode 100644
index 0000000..b52d075
--- /dev/null
+++ b/packages/newton/lib/src/tolerance.dart
@@ -0,0 +1,17 @@
+// 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 newton;
+
+class Tolerance {
+ final double distance;
+ final double time;
+ final double velocity;
+
+ const Tolerance({this.distance: epsilonDefault, this.time: epsilonDefault,
+ this.velocity: epsilonDefault});
+}
+
+const double epsilonDefault = 1e-3;
+const Tolerance toleranceDefault = const Tolerance();
diff --git a/packages/newton/lib/src/utils.dart b/packages/newton/lib/src/utils.dart
new file mode 100644
index 0000000..75709a3
--- /dev/null
+++ b/packages/newton/lib/src/utils.dart
@@ -0,0 +1,10 @@
+// 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 newton;
+
+bool _nearEqual(double a, double b, double epsilon) =>
+ (a > (b - epsilon)) && (a < (b + epsilon));
+
+bool _nearZero(double a, double epsilon) => _nearEqual(a, 0.0, epsilon);
diff --git a/packages/newton/pubspec.yaml b/packages/newton/pubspec.yaml
new file mode 100644
index 0000000..801aac3
--- /dev/null
+++ b/packages/newton/pubspec.yaml
@@ -0,0 +1,11 @@
+name: newton
+description: Simple Physics Simulations for Dart
+version: 0.1.5
+author: Flutter Authors <flutter-dev@googlegroups.com>
+homepage: https://github.com/flutter/flutter/tree/master/packages/newton
+environment:
+ sdk: '>=1.0.0 <2.0.0'
+dev_dependencies:
+ test: '>=0.12.0 <0.13.0'
+ test_runner: '<=0.2.16'
+ dart_coveralls: '<=0.3.0'
diff --git a/packages/newton/test/newton_test.dart b/packages/newton/test/newton_test.dart
new file mode 100644
index 0000000..20efa21
--- /dev/null
+++ b/packages/newton/test/newton_test.dart
@@ -0,0 +1,252 @@
+// 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.
+
+library simple_physics.test;
+
+import 'package:test/test.dart';
+
+import 'package:newton/newton.dart';
+
+void main() {
+ test('test_friction', () {
+ var friction = new FrictionSimulation(0.3, 100.0, 400.0);
+
+ friction.tolerance = const Tolerance(velocity: 1.0);
+
+ expect(friction.isDone(0.0), false);
+ expect(friction.x(0.0), 100);
+ expect(friction.dx(0.0), 400.0);
+
+ expect(friction.x(1.0) > 330 && friction.x(1.0) < 335, true);
+
+ expect(friction.dx(1.0), 120.0);
+ expect(friction.dx(2.0), 36.0);
+ expect(friction.dx(3.0), 10.8);
+ expect(friction.dx(4.0) < 3.5, true);
+
+ expect(friction.isDone(5.0), true);
+ expect(friction.x(5.0) > 431 && friction.x(5.0) < 432, true);
+ });
+
+ test('test_friction_through', () {
+ // Use a normal FrictionSimulation to generate start and end
+ // velocity and positions with drag = 0.025.
+ var startPosition = 10.0;
+ var startVelocity = 600.0;
+ var f = new FrictionSimulation(0.025, startPosition, startVelocity);
+ var endPosition = f.x(1.0);
+ var endVelocity = f.dx(1.0);
+ expect(endPosition, greaterThan(startPosition));
+ expect(endVelocity, lessThan(startVelocity));
+
+ // Verify that that the "through" FrictionSimulation ends up at
+ // endPosition and endVelocity; implies that it computed the right
+ // value for _drag.
+ var friction = new FrictionSimulation.through(
+ startPosition, endPosition, startVelocity, endVelocity);
+ expect(friction.isDone(0.0), false);
+ expect(friction.x(0.0), 10.0);
+ expect(friction.dx(0.0), 600.0);
+
+ double epsilon = 1e-4;
+ expect(friction.isDone(1.0 + epsilon), true);
+ expect(friction.x(1.0), closeTo(endPosition, epsilon));
+ expect(friction.dx(1.0), closeTo(endVelocity, epsilon));
+
+ // Same scenario as above except that the velocities are
+ // are negative.
+ startPosition = 1000.0;
+ startVelocity = -500.0;
+ f = new FrictionSimulation(0.025, 1000.0, -500.0);
+ endPosition = f.x(1.0);
+ endVelocity = f.dx(1.0);
+ expect(endPosition, lessThan(startPosition));
+ expect(endVelocity, greaterThan(startVelocity));
+
+ friction = new FrictionSimulation.through(
+ startPosition, endPosition, startVelocity, endVelocity);
+ expect(friction.isDone(1.0 + epsilon), true);
+ expect(friction.x(1.0), closeTo(endPosition, epsilon));
+ expect(friction.dx(1.0), closeTo(endVelocity, epsilon));
+ });
+
+ test('test_gravity', () {
+ var gravity = new GravitySimulation(200.0, 100.0, 600.0, 0.0);
+
+ expect(gravity.isDone(0.0), false);
+ expect(gravity.x(0.0), 100.0);
+ expect(gravity.dx(0.0), 0.0);
+
+ // Starts at 100
+ expect(gravity.x(0.25), 106.25);
+ expect(gravity.x(0.50), 125);
+ expect(gravity.x(0.75), 156.25);
+ expect(gravity.x(1.00), 200);
+ expect(gravity.x(1.25), 256.25);
+ expect(gravity.x(1.50), 325);
+ expect(gravity.x(1.75), 406.25);
+
+ // Starts at 0.0
+ expect(gravity.dx(0.25), 50.0);
+ expect(gravity.dx(0.50), 100);
+ expect(gravity.dx(0.75), 150.00);
+ expect(gravity.dx(1.00), 200.0);
+ expect(gravity.dx(1.25), 250.0);
+ expect(gravity.dx(1.50), 300);
+ expect(gravity.dx(1.75), 350);
+
+ expect(gravity.isDone(2.5), true);
+ expect(gravity.x(2.5), 725);
+ expect(gravity.dx(2.5), 500.0);
+ });
+
+ test('spring_types', () {
+ var crit = new SpringSimulation(new SpringDescription.withDampingRatio(
+ mass: 1.0, springConstant: 100.0), 0.0, 300.0, 0.0);
+ expect(crit.type, SpringType.criticallyDamped);
+
+ crit = new SpringSimulation(new SpringDescription.withDampingRatio(
+ mass: 1.0, springConstant: 100.0, ratio: 1.0), 0.0, 300.0, 0.0);
+ expect(crit.type, SpringType.criticallyDamped);
+
+ var under = new SpringSimulation(new SpringDescription.withDampingRatio(
+ mass: 1.0, springConstant: 100.0, ratio: 0.75), 0.0, 300.0, 0.0);
+ expect(under.type, SpringType.underDamped);
+
+ var over = new SpringSimulation(new SpringDescription.withDampingRatio(
+ mass: 1.0, springConstant: 100.0, ratio: 1.25), 0.0, 300.0, 0.0);
+ expect(over.type, SpringType.overDamped);
+
+ // Just so we don't forget how to create a desc without the ratio.
+ var other = new SpringSimulation(
+ new SpringDescription(mass: 1.0, springConstant: 100.0, damping: 20.0),
+ 0.0, 20.0, 20.0);
+ expect(other.type, SpringType.criticallyDamped);
+ });
+
+ test('crit_spring', () {
+ var crit = new SpringSimulation(new SpringDescription.withDampingRatio(
+ mass: 1.0, springConstant: 100.0, ratio: 1.0), 0.0, 500.0, 0.0);
+
+ crit.tolerance = const Tolerance(distance: 0.01, velocity: 0.01);
+
+ expect(crit.type, SpringType.criticallyDamped);
+
+ expect(crit.isDone(0.0), false);
+ expect(crit.x(0.0), 0.0);
+ expect(crit.dx(0.0), 5000.0);
+
+ expect(crit.x(0.25).floor(), 458.0);
+ expect(crit.x(0.50).floor(), 496.0);
+ expect(crit.x(0.75).floor(), 499.0);
+
+ expect(crit.dx(0.25).floor(), 410);
+ expect(crit.dx(0.50).floor(), 33);
+ expect(crit.dx(0.75).floor(), 2);
+
+ expect(crit.isDone(1.50), true);
+ expect(crit.x(1.5) > 499.0 && crit.x(1.5) < 501.0, true);
+ expect(crit.dx(1.5) < 0.1, true /* basically within tolerance */);
+ });
+
+ test('overdamped_spring', () {
+ var over = new SpringSimulation(new SpringDescription.withDampingRatio(
+ mass: 1.0, springConstant: 100.0, ratio: 1.25), 0.0, 500.0, 0.0);
+
+ over.tolerance = const Tolerance(distance: 0.01, velocity: 0.01);
+
+ expect(over.type, SpringType.overDamped);
+
+ expect(over.isDone(0.0), false);
+ expect(over.x(0.0), 0.0);
+
+ expect(over.x(0.5).floor(), 445.0);
+ expect(over.x(1.0).floor(), 495.0);
+ expect(over.x(1.5).floor(), 499.0);
+
+ expect(over.dx(0.5).floor(), 273.0);
+ expect(over.dx(1.0).floor(), 22.0);
+ expect(over.dx(1.5).floor(), 1.0);
+
+ expect(over.isDone(3.0), true);
+ });
+
+ test('underdamped_spring', () {
+ var under = new SpringSimulation(new SpringDescription.withDampingRatio(
+ mass: 1.0, springConstant: 100.0, ratio: 0.25), 0.0, 300.0, 0.0);
+ expect(under.type, SpringType.underDamped);
+
+ expect(under.isDone(0.0), false);
+
+ // Overshot with negative velocity
+ expect(under.x(1.0).floor(), 325);
+ expect(under.dx(1.0).floor(), -65);
+
+ expect(under.dx(6.0).floor(), 0.0);
+ expect(under.x(6.0).floor(), 299);
+
+ expect(under.isDone(6.0), true);
+ });
+
+ test('test_kinetic_scroll', () {
+ var spring = new SpringDescription.withDampingRatio(
+ mass: 1.0, springConstant: 50.0, ratio: 0.5);
+
+ var scroll = new ScrollSimulation(100.0, 800.0, 0.0, 300.0, spring, 0.3);
+ scroll.tolerance = const Tolerance(velocity: 0.5, distance: 0.1);
+ expect(scroll.isDone(0.0), false);
+ expect(scroll.isDone(0.5), false); // switch from friction to spring
+ expect(scroll.isDone(3.5), true);
+
+ var scroll2 = new ScrollSimulation(100.0, -800.0, 0.0, 300.0, spring, 0.3);
+ scroll2.tolerance = const Tolerance(velocity: 0.5, distance: 0.1);
+ expect(scroll2.isDone(0.0), false);
+ expect(scroll2.isDone(0.5), false); // switch from friction to spring
+ expect(scroll2.isDone(3.5), true);
+ });
+
+ test('scroll_with_inf_edge_ends', () {
+ var spring = new SpringDescription.withDampingRatio(
+ mass: 1.0, springConstant: 50.0, ratio: 0.5);
+
+ var scroll =
+ new ScrollSimulation(100.0, 400.0, 0.0, double.INFINITY, spring, 0.3);
+ scroll.tolerance = const Tolerance(velocity: 1.0);
+
+ expect(scroll.isDone(0.0), false);
+ expect(scroll.x(0.0), 100);
+ expect(scroll.dx(0.0), 400.0);
+
+ expect(scroll.x(1.0) > 330 && scroll.x(1.0) < 335, true);
+
+ expect(scroll.dx(1.0), 120.0);
+ expect(scroll.dx(2.0), 36.0);
+ expect(scroll.dx(3.0), 10.8);
+ expect(scroll.dx(4.0) < 3.5, true);
+
+ expect(scroll.isDone(5.0), true);
+ expect(scroll.x(5.0) > 431 && scroll.x(5.0) < 432, true);
+
+ // We should never switch
+ expect(scroll.currentIntervalOffset, 0.0);
+ });
+
+ test('over/under scroll spring', () {
+ var spring = new SpringDescription.withDampingRatio(mass: 1.0, springConstant: 170.0, ratio: 1.1);
+ var scroll = new ScrollSimulation(500.0, -7500.0, 0.0, 1000.0, spring, 0.025);
+ scroll.tolerance = new Tolerance(velocity: 45.0, distance: 1.5);
+
+ expect(scroll.isDone(0.0), false);
+ expect(scroll.x(0.0), closeTo(500.0, .0001));
+ expect(scroll.dx(0.0), closeTo(-7500.0, .0001));
+
+ expect(scroll.isDone(0.025), false);
+ expect(scroll.x(0.025), closeTo(320.0, 1.0));
+ expect(scroll.dx(0.25), closeTo(-2982, 1.0));
+
+ expect(scroll.isDone(2.0), true);
+ expect(scroll.x(2.0), 0.0);
+ expect(scroll.dx(2.0), closeTo(0.0, 45.0));
+ });
+}
diff --git a/travis/setup.sh b/travis/setup.sh
new file mode 100755
index 0000000..f135a26
--- /dev/null
+++ b/travis/setup.sh
@@ -0,0 +1,7 @@
+#!/bin/bash
+set -ex
+
+(cd packages/cassowary; pub get)
+(cd packages/newton; pub get)
+
+pub global activate tuneup
diff --git a/travis/test.sh b/travis/test.sh
new file mode 100755
index 0000000..134c465
--- /dev/null
+++ b/travis/test.sh
@@ -0,0 +1,5 @@
+#!/bin/bash
+set -ex
+
+(cd packages/cassowary; pub global run tuneup check; pub run test -j1)
+(cd packages/newton; pub global run tuneup check; pub run test -j1)
