diff options
Diffstat (limited to 'libs/cassowary/ClLinearExpression.cc')
| -rw-r--r-- | libs/cassowary/ClLinearExpression.cc | 473 |
1 files changed, 473 insertions, 0 deletions
diff --git a/libs/cassowary/ClLinearExpression.cc b/libs/cassowary/ClLinearExpression.cc new file mode 100644 index 0000000000..72383ffec1 --- /dev/null +++ b/libs/cassowary/ClLinearExpression.cc @@ -0,0 +1,473 @@ +// $Id$ +// +// Cassowary Incremental Constraint Solver +// Original Smalltalk Implementation by Alan Borning +// This C++ Implementation by Greg J. Badros, <gjb@cs.washington.edu> +// http://www.cs.washington.edu/homes/gjb +// (C) 1998, 1999 Greg J. Badros and Alan Borning +// See ../LICENSE for legal details regarding this software +// +// ClLinearExpression.cc + +using namespace std; + +#include <cassowary/ClLinearExpression.h> +#include <cassowary/ClSymbolicWeight.h> /// needed only to instantiate with T=ClSymbolicWeight +#include <cassowary/ClVariable.h> +#include <cassowary/ClTableau.h> +#include <cassowary/ClErrors.h> + +#ifdef HAVE_CONFIG_H +#include <config.h> +#define CONFIG_H_INCLUDED +#endif + +template <class T> +ClGenericLinearExpression<T>::ClGenericLinearExpression(T num) : + _constant(num) +{ } + +// Convert from ClVariable to a ClLinearExpression +// this replaces ClVariable::asLinearExpression +template <class T> +ClGenericLinearExpression<T>::ClGenericLinearExpression(ClVariable clv, T value, + T Constant) : + _constant(Constant) +{ + _terms[clv] = value; +} + +template <class T> +ClGenericLinearExpression<T>::~ClGenericLinearExpression() +{ } + +#ifndef CL_NO_IO +template <class T> +ostream & +ClGenericLinearExpression<T>::PrintOn(ostream &xo) const +{ + typename ClVarToCoeffMap::const_iterator i = _terms.begin(); + + if (!ClApprox(_constant,0.0) || i == _terms.end()) + { + xo << _constant; + } + else + { + if (i == _terms.end()) + return xo; + xo << (*i).second << "*" << (*i).first; + ++i; + } + for ( ; i != _terms.end(); ++i) + { + xo << " + " << (*i).second << "*" << (*i).first; + } + return xo; +} +#endif + + + +// Destructively multiply self by x. +// (private memfn) +template <class T> +ClGenericLinearExpression<T> & +ClGenericLinearExpression<T>::MultiplyMe(T x) +{ + _constant *= x; + + typename ClVarToCoeffMap::const_iterator i = _terms.begin(); + for ( ; i != _terms.end(); ++i) + { + _terms[(*i).first] = (*i).second * x; + } + return *this; +} + +// Return a new linear expression formed by multiplying self by x. +// (Note that this result must be linear.) +template <class T> +ClGenericLinearExpression<T> +ClGenericLinearExpression<T>::Times(Number x) const +{ + ClGenericLinearExpression<T> result = *this; + return result.MultiplyMe(x); +} + +// Return a new linear expression formed by multiplying self by x. +// (Note that this result must be linear.) +// The above function optimizes the specific case of multiplying +// by a Constant, here is the more general case +template <class T> +ClGenericLinearExpression<T> +ClGenericLinearExpression<T>::Times(const ClGenericLinearExpression<T> &expr) const +{ + if (IsConstant()) + { + return expr.Times(_constant); + } + else if (!expr.IsConstant()) + { + // neither are constants, so we'd introduce non-linearity + throw ExCLNonlinearExpression(); + } + return Times(expr._constant); +} + + +// Return a new linear expression formed by adding x to self. +template <class T> +ClGenericLinearExpression<T> +ClGenericLinearExpression<T>::Plus(const ClGenericLinearExpression<T> &expr) const +{ + ClGenericLinearExpression<T> result = *this; + result.AddExpression(expr,1.0); + return result; +} + +// Return a new linear expression formed by subtracting x from self. +template <class T> +ClGenericLinearExpression<T> +ClGenericLinearExpression<T>::Minus(const ClGenericLinearExpression<T> &expr) const +{ + ClGenericLinearExpression<T> result = *this; + result.AddExpression(expr,-1.0); + return result; +} + +// Return a new linear expression formed by dividing self by x. +// (Note that this result must be linear.) +template <class T> +ClGenericLinearExpression<T> +ClGenericLinearExpression<T>::Divide(Number x) const +{ + if (ClApprox(x,0.0)) + { + throw ExCLNonlinearExpression(); + } + return Times(1.0/x); +} + +// Return a new linear expression formed by dividing self by x. +// (Note that this result must be linear.) +template <class T> +ClGenericLinearExpression<T> +ClGenericLinearExpression<T>::Divide(const ClGenericLinearExpression<T> &expr) const +{ + if (!expr.IsConstant()) + { + throw ExCLNonlinearExpression(); + } + return Divide(expr._constant); +} + + +// Return a new linear expression (expr/this). Since the result +// must be linear, this is permissible only if 'this' is a Constant. +template <class T> +ClGenericLinearExpression<T> +ClGenericLinearExpression<T>::DivFrom(const ClGenericLinearExpression<T> &expr) const +{ + if (!IsConstant() || ClApprox(_constant,0.0)) + { + throw ExCLNonlinearExpression(); + } + return expr.Divide(_constant); +} + +// Add n*expr to this expression for another expression expr. +template <class T> +ClGenericLinearExpression<T> & +ClGenericLinearExpression<T>::AddExpression(const ClGenericLinearExpression<T> &expr, Number n) +{ + IncrementConstant(expr.Constant()*n); + + typename ClVarToCoeffMap::const_iterator i = expr._terms.begin(); + for ( ; i != expr._terms.end(); ++i) + { + AddVariable((*i).first, (*i).second * n); + } + return *this; +} + +// Add n*expr to this expression for another expression expr. +// Notify the solver if a variable is added or deleted from this +// expression. +template <class T> +ClGenericLinearExpression<T> & +ClGenericLinearExpression<T>::AddExpression(const ClGenericLinearExpression<T> &expr, Number n, + ClVariable subject, + ClTableau &solver) +{ + IncrementConstant(expr.Constant() * n); + + typename ClVarToCoeffMap::const_iterator i = expr._terms.begin(); + for ( ; i != expr._terms.end(); ++i) + { + AddVariable((*i).first, (*i).second * n, subject, solver); + } + return *this; +} + +// Add a term c*v to this expression. If the expression already +// contains a term involving v, Add c to the existing coefficient. +// If the new coefficient is approximately 0, delete v. +template <class T> +ClGenericLinearExpression<T> & +ClGenericLinearExpression<T>::AddVariable(ClVariable v, T c) +{ // body largely duplicated below +#ifdef CL_TRACE + Tracer TRACER(__FUNCTION__); + cerr << "(" << v << ", " << c << ")" << endl; +#endif + typename ClVarToCoeffMap::iterator i = _terms.find(v); + if (i != _terms.end()) + { + // expression already contains that variable, so Add to it + T new_coefficient = 0; + new_coefficient = (*i).second + c; + if (ClApprox(new_coefficient,0.0)) + { + // new coefficient is Zero, so erase it + _terms.erase(i); + } + else + { + (*i).second = new_coefficient; + } + } + else // expression did not contain that variable + { + if (!ClApprox(c,0.0)) + { + _terms[v] = c; + } + } + return *this; +} + +// Add a term c*v to this expression. If the expression already +// contains a term involving v, Add c to the existing coefficient. +// If the new coefficient is approximately 0, delete v. Notify the +// solver if v appears or disappears from this expression. +template <class T> +ClGenericLinearExpression<T> & +ClGenericLinearExpression<T>::AddVariable(ClVariable v, T c, + ClVariable subject, + ClTableau &solver) +{ // body largely duplicated above +#ifdef CL_TRACE + Tracer TRACER(__FUNCTION__); + cerr << "(" << v << ", " << c << ", " << subject << ", ...)" << endl; +#endif + typename ClVarToCoeffMap::iterator i = _terms.find(v); + if (i != _terms.end()) + { + // expression already contains that variable, so Add to it + T new_coefficient = (*i).second + c; + if (ClApprox(new_coefficient,0.0)) + { + // new coefficient is Zero, so erase it + solver.NoteRemovedVariable((*i).first,subject); + _terms.erase(i); + } + else + { + (*i).second = new_coefficient; + } + } + else // expression did not contain that variable + { + if (!ClApprox(c,0.0)) + { + _terms[v] = c; + solver.NoteAddedVariable(v,subject); + } + } +#ifdef CL_TRACE + cerr << "Now *this == " << *this << endl; +#endif + return *this; +} + +// Return a variable in this expression. (It is an error if this +// expression is Constant -- signal ExCLInternalError in that case). +template <class T> +ClVariable +ClGenericLinearExpression<T>::AnyPivotableVariable() const +{ + if (IsConstant()) + { + throw ExCLInternalError("(ExCLInternalError) No pivotable variables in Constant expression"); + } + typename ClVarToCoeffMap::const_iterator i = _terms.begin(); + for ( ; i != _terms.end(); ++i) + { + ClVariable v = (*i).first; + if (v.IsPivotable()) + return v; + } + return clvNil; +} + +// Replace var with a symbolic expression expr that is equal to it. +// If a variable has been added to this expression that wasn't there +// before, or if a variable has been dropped from this expression +// because it now has a coefficient of 0, inform the solver. +// PRECONDITIONS: +// var occurs with a non-Zero coefficient in this expression. +template <class T> +void +ClGenericLinearExpression<T>::SubstituteOut(ClVariable var, + const ClGenericLinearExpression<T> &expr, + ClVariable subject, + ClTableau &solver) +{ +#ifdef CL_TRACE + cerr << "* ClGenericLinearExpression::"; + Tracer TRACER(__FUNCTION__); + cerr << "(" << var << ", " << expr << ", " << subject << ", " + << solver << ")" << endl; + cerr << "*this == " << *this << endl; +#endif + + typename ClVarToCoeffMap::iterator pv = _terms.find(var); + +#ifndef NDEBUG + if (pv == _terms.end()) + { +#ifndef CL_NO_IO + cerr << "SubstituteOut: pv != _terms.end()" << endl; + cerr << "(" << var << ", " << expr << ", " << subject << ", " + << ")" << endl; + cerr << "*this == " << *this << endl; +#endif + throw "SubstituteOut: pv != _terms.end()"; + } +#endif + assert(pv != _terms.end()); + // FIXGJB: this got thrown! assert(!ClApprox((*pv).second,0.0)); + + T multiplier = (*pv).second; + _terms.erase(pv); + IncrementConstant(multiplier * expr._constant); + typename ClVarToCoeffMap::const_iterator i = expr._terms.begin(); + for ( ; i != expr._terms.end(); ++i) + { + ClVariable v = (*i).first; + T c = (*i).second; + typename ClVarToCoeffMap::iterator poc = _terms.find(v); + if (poc != _terms.end()) + { // if oldCoeff is not nil +#ifdef CL_TRACE + cerr << "Considering (*poc) == " << (*poc).second << "*" << (*poc).first << endl; +#endif + // found it, so new coefficient is old one Plus what is in *i + T newCoeff = (*poc).second + (multiplier*c); + if (ClApprox(newCoeff,0.0)) + { + solver.NoteRemovedVariable((*poc).first,subject); + _terms.erase(poc); + } + else + { + (*poc).second = newCoeff; + } + } + else + { // did not have that variable already (oldCoeff == nil) +#ifdef CL_TRACE + cerr << "Adding (*i) == " << (*i).second << "*" << (*i).first << endl; +#endif + _terms[v] = multiplier * c; + solver.NoteAddedVariable(v,subject); + } + } +#ifdef CL_TRACE + cerr << "Now (*this) is " << *this << endl; +#endif +} + +// This linear expression currently represents the equation +// oldSubject=self. Destructively modify it so that it represents +// the equation NewSubject=self. +// +// Precondition: NewSubject currently has a nonzero coefficient in +// this expression. +// +// NOTES +// Suppose this expression is c + a*NewSubject + a1*v1 + ... + an*vn. +// +// Then the current equation is +// oldSubject = c + a*NewSubject + a1*v1 + ... + an*vn. +// The new equation will be +// NewSubject = -c/a + oldSubject/a - (a1/a)*v1 - ... - (an/a)*vn. +// Note that the term involving NewSubject has been dropped. +// +// Basically, we consider the expression to be an equation with oldSubject +// equal to the expression, then Resolve the equation for NewSubject, +// and destructively make the expression what NewSubject is then equal to +template <class T> +void +ClGenericLinearExpression<T>::ChangeSubject(ClVariable old_subject, + ClVariable new_subject) +{ + _terms[old_subject] = NewSubject(new_subject); +} + +inline double ReciprocalOf(double n) +{ return 1.0/n; } + +// This linear expression currently represents the equation self=0. Destructively modify it so +// that subject=self represents an equivalent equation. +// +// Precondition: subject must be one of the variables in this expression. +// NOTES +// Suppose this expression is +// c + a*subject + a1*v1 + ... + an*vn +// representing +// c + a*subject + a1*v1 + ... + an*vn = 0 +// The modified expression will be +// subject = -c/a - (a1/a)*v1 - ... - (an/a)*vn +// representing +// subject = -c/a - (a1/a)*v1 - ... - (an/a)*vn = 0 +// +// Note that the term involving subject has been dropped. +// +// Returns the reciprocal, so that NewSubject can be used by ChangeSubject +template <class T> +T +ClGenericLinearExpression<T>::NewSubject(ClVariable subject) +{ +#ifdef CL_TRACE + Tracer TRACER(__FUNCTION__); + cerr << "(" << subject << ")" << endl; +#endif + typename ClVarToCoeffMap::iterator pnewSubject = _terms.find(subject); + assert(pnewSubject != _terms.end()); + // assert(!ClApprox((*pnewSubject).second,0.0)); + T reciprocal = ReciprocalOf((*pnewSubject).second); + _terms.erase(pnewSubject); + MultiplyMe(-reciprocal); + return reciprocal; +} + +template <class T> +T +ClGenericLinearExpression<T>::Evaluate() const +{ + T answer = _constant; + typename ClVarToCoeffMap::const_iterator i = _terms.begin(); + + for ( ; i != _terms.end(); ++i) + { + ClVariable v = (*i).first; + answer += (*i).second * v.Value(); + } + return answer; +} + + +template class ClGenericLinearExpression<Number>; +// template class ClGenericLinearExpression<ClSymbolicWeight>; |