diff options
Diffstat (limited to 'libs/cassowary/cassowary/ClSimplexSolver.h')
| -rw-r--r-- | libs/cassowary/cassowary/ClSimplexSolver.h | 588 |
1 files changed, 0 insertions, 588 deletions
diff --git a/libs/cassowary/cassowary/ClSimplexSolver.h b/libs/cassowary/cassowary/ClSimplexSolver.h deleted file mode 100644 index c187992728..0000000000 --- a/libs/cassowary/cassowary/ClSimplexSolver.h +++ /dev/null @@ -1,588 +0,0 @@ -// $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 |