diff options
Diffstat (limited to 'libs/cassowary/cassowary/ClSimplexSolver.h')
| -rw-r--r-- | libs/cassowary/cassowary/ClSimplexSolver.h | 588 |
1 files changed, 588 insertions, 0 deletions
diff --git a/libs/cassowary/cassowary/ClSimplexSolver.h b/libs/cassowary/cassowary/ClSimplexSolver.h new file mode 100644 index 0000000000..c187992728 --- /dev/null +++ b/libs/cassowary/cassowary/ClSimplexSolver.h @@ -0,0 +1,588 @@ +// $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 +// +// ClSimplexSolver.h + +#ifndef ClSimplexSolver_H +#define ClSimplexSolver_H + +#if defined(HAVE_CONFIG_H) && !defined(CONFIG_H_INCLUDED) && !defined(CONFIG_INLINE_H_INCLUDED) +#include <cassowary/config-inline.h> +#define CONFIG_INLINE_H_INCLUDED +#endif + +#include <stack> +#include <list> +#include <iostream> +#include "Cassowary.h" +#include "ClSolver.h" +#include "ClTableau.h" +#include "ClLinearInequality.h" +#include "ClStrength.h" +#include "ClStayConstraint.h" +#include "ClEditConstraint.h" +#include "ClSlackVariable.h" +#include "ClObjectiveVariable.h" +#include "ClErrors.h" +#include "ClTypedefs.h" + +using std::list; +using std::stack; +using std::ostream; + +class ClVariable; +class ClPoint; +class ExCLRequiredFailureWithExplanation; + + +// ClSimplexSolver encapsulates the solving behaviour +// of the cassowary algorithm +class ClSimplexSolver : public ClSolver, public ClTableau { + protected: + class ClEditInfo; + typedef list<ClEditInfo *> ClEditInfoList; + + ClEditInfo *PEditInfoFromClv(ClVariable clv) { + ClEditInfoList::iterator it = _editInfoList.begin(); + for (; it != _editInfoList.end(); ++it) { + ClEditInfo *pei = (*it); + if (pei->_clv == clv) + return pei; + } + return 0; + } + + public: + + // Constructor + ClSimplexSolver() : + ClSolver(), + _objective(ClVariable(new ClObjectiveVariable("Z"))), + _slackCounter(0), + _artificialCounter(0), +#ifdef CL_FIND_LEAK + _cArtificialVarsDeleted(0), +#endif + _dummyCounter(0), + _epsilon(1e-8), + _fResetStayConstantsAutomatically(true), + _fNeedsSolving(false), + _fExplainFailure(false), + _pfnResolveCallback(0), + _pfnCnSatCallback(0) + { + _rows[_objective] = new ClLinearExpression(); + // start out with no edit variables + _stkCedcns.push(0); +#ifdef CL_TRACE + std::cerr << "objective row new@ " << _rows[_objective] << std::endl; +#endif + } + + virtual ~ClSimplexSolver(); + + // Add constraints so that lower<=var<=upper. (nil means no bound.) + ClSimplexSolver &AddLowerBound(ClVariable v, Number lower) + { + ClLinearInequality *pcn = new ClLinearInequality(ClLinearExpression(v - lower)); + return AddConstraint(pcn); + } + ClSimplexSolver &AddUpperBound(ClVariable v, Number upper) + { + ClLinearInequality *pcn = new ClLinearInequality(ClLinearExpression(upper - v)); + return AddConstraint(pcn); + } + ClSimplexSolver &AddBounds(ClVariable v, Number lower, Number upper) + { AddLowerBound(v,lower); AddUpperBound(v,upper); return *this; } + + // Add the constraint cn to the tableau + ClSimplexSolver &AddConstraint(ClConstraint *const pcn); + +#ifndef CL_NO_DEPRECATED + // Deprecated! --02/19/99 gjb + ClSimplexSolver &AddConstraint(ClConstraint &cn) + { return AddConstraint(&cn); } +#endif + + // Add an edit constraint for "v" with given strength + ClSimplexSolver &AddEditVar(const ClVariable v, const ClStrength &strength = ClsStrong(), + double weight = 1.0 ) + { + ClEditConstraint *pedit = new ClEditConstraint(v, strength, weight); + return AddConstraint(pedit); + } + + ClSimplexSolver &RemoveEditVar(ClVariable v) + { + ClEditInfo *pcei = PEditInfoFromClv(v); + if (!pcei) { + throw ExCLEditMisuse("Removing edit variable that was not found"); + } + ClConstraint *pcnEdit = pcei->_pconstraint; + RemoveConstraint(pcnEdit); + delete pcnEdit; + return *this; + } + + // BeginEdit() should be called before sending + // Resolve() messages, after adding the appropriate edit variables + ClSimplexSolver &BeginEdit() + { + if (_editInfoList.size() == 0) { + throw ExCLEditMisuse("BeginEdit called, but no edit variable"); + } + // may later want to do more in here + _infeasibleRows.clear(); + ResetStayConstants(); + _stkCedcns.push(_editInfoList.size()); + return *this; + } + + // EndEdit should be called after editing has finished + // for now, it just removes edit variables added from before the last BeginEdit + ClSimplexSolver &EndEdit() + { + if (_editInfoList.size() == 0) + throw ExCLEditMisuse("EndEdit called but no edit variables"); + Resolve(); + _stkCedcns.pop(); + RemoveEditVarsTo(_stkCedcns.top()); + // may later want to do more in here + return *this; + } + + // RemoveAllEditVars() just eliminates all the edit constraints + // that were added + ClSimplexSolver &RemoveAllEditVars() { RemoveEditVarsTo(0); return *this; } + + // remove the last added edit vars to leave only n edit vars left + ClSimplexSolver &RemoveEditVarsTo(unsigned int n); + + int numEditVars() const + { return _editInfoList.size(); } + + // Add weak stays to the x and y parts of each point. These have + // increasing weights so that the solver will try to satisfy the x + // and y stays on the same point, rather than the x stay on one and + // the y stay on another. + ClSimplexSolver &AddPointStays(const vector<const ClPoint *> &listOfPoints, + const ClStrength &strength = ClsWeak()); + + ClSimplexSolver &AddPointStay(const ClVariable vx, const ClVariable vy, + const ClStrength &strength = ClsWeak(), + double weight = 1.0) + { AddStay(vx,strength,weight); AddStay(vy,strength,weight); return *this; } + + ClSimplexSolver &AddPointStay(const ClPoint &clp, + const ClStrength &strength = ClsWeak(), + double weight = 1.0); + + + // Add a stay of the given strength (default to weak) of v to the tableau + ClSimplexSolver &AddStay(const ClVariable v, + const ClStrength &strength = ClsWeak(), double weight = 1.0 ) + { + ClStayConstraint *pcn = new ClStayConstraint(v,strength,weight); + return AddConstraint(pcn); + } + + // Remove the constraint cn from the tableau + // Also remove any error variable associated with cn + ClSimplexSolver &RemoveConstraint(ClConstraint *const pcn) + { RemoveConstraintInternal(pcn); pcn->removedFrom(*this); return *this; } + +#ifndef CL_NO_DEPRECATED + // Deprecated! --02/19/99 gjb + ClSimplexSolver &RemoveConstraint(ClConstraint &cn) + { return RemoveConstraint(&cn); } +#endif + + + // Re-initialize this solver from the original constraints, thus + // getting rid of any accumulated numerical problems. (Actually, we + // haven't definitely observed any such problems yet) + void Reset(); + + // Re-solve the current collection of constraints, given the new + // values for the edit variables that have already been + // suggested (see SuggestValue() method) + // This is not guaranteed to work if you remove an edit constraint + // from the middle of the edit constraints you added + // (e.g., edit A, edit B, edit C, remove B -> this will fail!) + // DEPRECATED + void Resolve(); + + // Re-solve the current collection of constraints for new values for + // the constants of the edit variables. + // This is implemented in terms of SuggestValue-s, and is + // less efficient than that more natural interface + void Resolve(const vector<Number> &newEditConstants); + + // Convenience function for Resolve-s of two variables + void Resolve(Number x, Number y) + { + vector<Number> vals; + vals.push_back(x); + vals.push_back(y); + Resolve(vals); + } + + // Suggest a new value for an edit variable + // the variable needs to be added as an edit variable + // and BeginEdit() needs to be called before this is called. + // The tableau will not be solved completely until + // after Resolve() has been called + ClSimplexSolver &SuggestValue(ClVariable v, Number x); + + // Set and check whether or not the solver will attempt to compile + // an explanation of failure when a required constraint conflicts + // with another required constraint + ClSimplexSolver &SetExplaining(bool f) + { _fExplainFailure = f; return *this; } + + bool FIsExplaining() const + { return _fExplainFailure; } + + // If autosolving has been turned off, client code needs + // to explicitly call solve() before accessing variables + // values + ClSimplexSolver &Solve() + { +#ifdef CL_SOLVER_CHECK_INTEGRITY + AssertValid(); +#endif + if (_fNeedsSolving) + { + Optimize(_objective); + SetExternalVariables(); +#ifdef CL_TRACE_VERBOSE + std::cerr << "Manual solve actually solving." << std::endl; +#endif + } + return *this; + } + + ClSimplexSolver &SetEditedValue(ClVariable v, double n) + { + if (!FContainsVariable(v)) + { + ChangeClv(v,n); + return *this; + } + + if (!ClApprox(n, v.Value())) + { + AddEditVar(v); + BeginEdit(); + SuggestValue(v,n); + EndEdit(); + } + return *this; + } + + // Solver contains the variable if it's in either the columns + // list or the rows list + bool FContainsVariable(const ClVariable v) + { return ColumnsHasKey(v) || RowExpression(v); } + + ClSimplexSolver &AddVar(const ClVariable v) + { if (!FContainsVariable(v)) + { + AddStay(v); +#ifdef CL_TRACE + std::cerr << "added initial stay on " << v << std::endl; +#endif + } + return *this; } + + typedef void (*PfnResolveCallback)(ClSimplexSolver *psolver); + + void SetResolveCallback(PfnResolveCallback pfn) + { _pfnResolveCallback = pfn; } + + typedef void (*PfnCnSatCallback)(ClSimplexSolver *psolver, + ClConstraint *pcn, bool fSatisfied); + + void SetCnSatCallback(PfnCnSatCallback pfn) + { _pfnCnSatCallback = pfn; } + +#ifndef CL_NO_IO + friend ostream &operator<<(ostream &xo, const ClSimplexSolver &tableau); + + ostream &PrintOn(ostream &xo) const; + + ostream &PrintInternalInfo(ostream &xo) const; + + ostream &PrintOnVerbose(ostream &xo) const + { PrintOn(xo); PrintInternalInfo(xo); xo << std::endl; return xo; } + +#endif + + const ClConstraintToVarMap &ConstraintMap() const + { return _markerVars; } + + const ClVarToConstraintMap &MarkerMap() const + { return _constraintsMarked; } + + bool FIsConstraintSatisfied(const ClConstraint *const pcn) const; + + // DEPRECATED + bool FIsConstraintSatisfied(const ClConstraint &pcn) const + { return FIsConstraintSatisfied(&pcn); } + + // re-set all the external variables to their current values + // most importantly, this re-calls all the ChangeClv callbacks + // (which might be used to copy the ClVariable's value to another + // variable) + void UpdateExternalVariables() + { SetExternalVariables(); } + + // A. Beurive' Tue Jul 6 17:05:39 CEST 1999 + void ChangeStrengthAndWeight(ClConstraint *pcn, const ClStrength &strength, double weight); + void ChangeStrength(ClConstraint *pcn, const ClStrength &strength); + void ChangeWeight(ClConstraint *pcn, double weight); + // void DisplayObjective(); + + // Each of the non-required stays will be represented by an equation + // of the form + // v = c + eplus - eminus + // where v is the variable with the stay, c is the previous value of + // v, and eplus and eminus are slack variables that hold the error + // in satisfying the stay constraint. We are about to change + // something, and we want to fix the constants in the equations + // representing the stays. If both eplus and eminus are nonbasic + // they have value 0 in the current solution, meaning the previous + // stay was exactly satisfied. In this case nothing needs to be + // changed. Otherwise one of them is basic, and the other must + // occur only in the Expression for that basic error variable. + // Reset the Constant in this Expression to 0. + void ResetStayConstants(); + + ClSimplexSolver &SetAutoResetStayConstants(bool f) + { _fResetStayConstantsAutomatically = f; if (f) ResetStayConstants(); return *this; } + + bool FIsAutoResetStayConstants() const + { return _fResetStayConstantsAutomatically; } + + protected: + + // ClEditInfo is a privately-used class + // that just wraps a constraint, its positive and negative + // error variables, and its prior edit Constant. + // It is used as values in _editInfoList, and replaces + // the parallel vectors of error variables and previous edit + // constants from the smalltalk version of the code. + class ClEditInfo { + friend class ClSimplexSolver; + public: + + // These instances own none of the pointers; + // the tableau row (the Expression) owns the peplus, peminus, + // and AddEditVar/RemoveEditVar pair or the client code owns + // the constraint object + ClEditInfo(ClVariable clv, + ClEditConstraint *pconstraint, + ClVariable eplus, ClVariable eminus, + Number prevEditConstant) + :_clv(clv), + _pconstraint(pconstraint), + _clvEditPlus(eplus), _clvEditMinus(eminus), + _prevEditConstant(prevEditConstant) + { } + + ~ClEditInfo() + { } + + ostream &PrintOn(ostream &xo) const + { xo << _clv << " -> [" << _clvEditPlus << ", " << _clvEditMinus << "](" + << _prevEditConstant << ")@" << " -- " + << *_pconstraint; + return xo; } + + friend ostream &operator<<(ostream &xo, const ClEditInfo &cei) + { return cei.PrintOn(xo); } + + private: + ClVariable _clv; + ClConstraint *_pconstraint; + ClVariable _clvEditPlus; + ClVariable _clvEditMinus; + Number _prevEditConstant; + }; + + // Add the constraint expr=0 to the inequality tableau using an + // artificial variable. To do this, create an artificial variable + // av and Add av=expr to the inequality tableau, then make av be 0. + // (Raise an exception if we can't attain av=0.) + // (Raise an exception if we can't attain av=0.) If the Add fails, + // prepare an explanation in e that describes why it failed (note + // that an empty explanation is considered to mean the explanation + // encompasses all active constraints. + bool AddWithArtificialVariable(ClLinearExpression &pexpr, + ExCLRequiredFailureWithExplanation &e); + + // Using the given equation (av = cle) build an explanation which + // implicates all constraints used to construct the equation. That + // is, everything for which the variables in the equation are markers. + // Thanks to Steve Wolfman for the implementation of the explanation feature + void BuildExplanation(ExCLRequiredFailureWithExplanation & e, + ClVariable av, + const ClLinearExpression * pcle); + + // We are trying to Add the constraint expr=0 to the appropriate + // tableau. Try to Add expr directly to the tableax without + // creating an artificial variable. Return true if successful and + // false if not. + bool TryAddingDirectly(ClLinearExpression &pexpr); + + // We are trying to Add the constraint expr=0 to the tableaux. Try + // to choose a subject (a variable to become basic) from among the + // current variables in expr. If expr contains any unrestricted + // variables, then we must choose an unrestricted variable as the + // subject. Also, if the subject is new to the solver we won't have + // to do any substitutions, so we prefer new variables to ones that + // are currently noted as parametric. If expr contains only + // restricted variables, if there is a restricted variable with a + // negative coefficient that is new to the solver we can make that + // the subject. Otherwise we can't find a subject, so return nil. + // (In this last case we have to Add an artificial variable and use + // that variable as the subject -- this is done outside this method + // though.) + // + // Note: in checking for variables that are new to the solver, we + // ignore whether a variable occurs in the objective function, since + // new slack variables are added to the objective function by + // 'NewExpression:', which is called before this method. + ClVariable ChooseSubject(ClLinearExpression &pexpr); + + // Each of the non-required edits will be represented by an equation + // of the form + // v = c + eplus - eminus + // where v is the variable with the edit, c is the previous edit + // value, and eplus and eminus are slack variables that hold the + // error in satisfying the edit constraint. We are about to change + // something, and we want to fix the constants in the equations + // representing the edit constraints. If one of eplus and eminus is + // basic, the other must occur only in the Expression for that basic + // error variable. (They can't both be basic.) Fix the Constant in + // this Expression. Otherwise they are both nonbasic. Find all of + // the expressions in which they occur, and fix the constants in + // those. See the UIST paper for details. + // (This comment was for resetEditConstants(), but that is now + // gone since it was part of the screwey vector-based interface + // to resolveing. --02/15/99 gjb) + void DeltaEditConstant(Number delta, ClVariable pv1, ClVariable pv2); + + // We have set new values for the constants in the edit constraints. + // Re-Optimize using the dual simplex algorithm. + void DualOptimize(); + + // Make a new linear Expression representing the constraint cn, + // replacing any basic variables with their defining expressions. + // Normalize if necessary so that the Constant is non-negative. If + // the constraint is non-required give its error variables an + // appropriate weight in the objective function. + ClLinearExpression *NewExpression(const ClConstraint *pcn, + /* output to */ + ClVariable &clvEplus, + ClVariable &clvEminus, + Number &prevEConstant); + + // Minimize the value of the objective. (The tableau should already + // be feasible.) + void Optimize(ClVariable zVar); + + // Do a Pivot. Move entryVar into the basis (i.e. make it a basic variable), + // and move exitVar out of the basis (i.e., make it a parametric variable) + void Pivot(ClVariable entryVar, ClVariable exitVar); + + // Set the external variables known to this solver to their appropriate values. + // Set each external basic variable to its value, and set each + // external parametric variable to 0. (It isn't clear that we will + // ever have external parametric variables -- every external + // variable should either have a stay on it, or have an equation + // that defines it in terms of other external variables that do have + // stays. For the moment I'll put this in though.) Variables that + // are internal to the solver don't actually store values -- their + // values are just implicit in the tableu -- so we don't need to set + // them. + void SetExternalVariables(); + + // this gets called by RemoveConstraint and by AddConstraint when the + // contraint we're trying to Add is inconsistent + ClSimplexSolver &RemoveConstraintInternal(const ClConstraint *const pcn); + + void ChangeClv(ClVariable clv, Number n) { + clv.ChangeValue(n); + if (_pfnChangeClvCallback) + _pfnChangeClvCallback(&clv,this); + } + + /// instance variables + + // the arrays of positive and negative error vars for the stay constraints + // (need both positive and negative since they have only non-negative values) + ClVarVector _stayMinusErrorVars; + ClVarVector _stayPlusErrorVars; + + // give error variables for a non required constraint, + // maps to ClSlackVariable-s + ClConstraintToVarSetMap _errorVars; + + // Return a lookup table giving the marker variable for each + // constraint (used when deleting a constraint). + ClConstraintToVarMap _markerVars; + + // Reverse of the above-- a lookup table giving the constraint + // for each marker variable (used when building failure explanations) + ClVarToConstraintMap _constraintsMarked; + + ClVariable _objective; + + // Map edit variables to their constraints, errors, and prior + // values + ClEditInfoList _editInfoList; + + int _slackCounter; + int _artificialCounter; +#ifdef CL_FIND_LEAK + int _cArtificialVarsDeleted; +#endif + int _dummyCounter; + const double _epsilon; + + bool _fResetStayConstantsAutomatically; + bool _fNeedsSolving; + bool _fExplainFailure; + + PfnResolveCallback _pfnResolveCallback; + PfnCnSatCallback _pfnCnSatCallback; + + // C-style extension mechanism so I + // don't have to wrap ScwmClSolver separately + void *_pv; + + // a stack of the number of edit constraints + // that existed at the prior BeginEdit. + // an EndEdit needs to pop off the top value, + // then remove constraints to get down + // to the # of constraints as in _stkCedcns.top() + stack<int> _stkCedcns; + + +#ifndef CL_NO_IO + +friend ostream &PrintTo(ostream &xo, const ClSimplexSolver::ClEditInfoList &listPEditInfo); +friend ostream &operator<<(ostream &xo, const ClSimplexSolver::ClEditInfoList &listPEditInfo); + +#endif + +}; + +#endif // ClSimplexSolver_H |