diff options
Diffstat (limited to 'libs/cassowary/cassowary')
38 files changed, 4255 insertions, 0 deletions
diff --git a/libs/cassowary/cassowary/.cvsignore b/libs/cassowary/cassowary/.cvsignore new file mode 100644 index 0000000000..282522db03 --- /dev/null +++ b/libs/cassowary/cassowary/.cvsignore @@ -0,0 +1,2 @@ +Makefile +Makefile.in diff --git a/libs/cassowary/cassowary/Cassowary.h b/libs/cassowary/cassowary/Cassowary.h new file mode 100644 index 0000000000..8413f321f9 --- /dev/null +++ b/libs/cassowary/cassowary/Cassowary.h @@ -0,0 +1,40 @@ +// $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 +// +// Cassowary.h + +#ifndef Cassowary_H +#define Cassowary_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 + +#ifndef CL_PTR_HASH_DIVISOR + #define CL_PTR_HASH_DIVISOR 4 +#endif + +#include "ClConstraintHash.h" +#include <climits> + +#include <string> +#include <cassert> +#include <iostream> + +typedef double Number; + +typedef long FDNumber; + +enum { FDN_NOTSET = LONG_MIN }; + +#define NEWVAR(x) do { cerr << "line " << __LINE__ << ": new " << x << endl; } while (0) +#define DELVAR(x) do { cerr << "line " << __LINE__ << ": del " << x << endl; } while (0) + +#endif // Cassowary_H diff --git a/libs/cassowary/cassowary/Cl.h b/libs/cassowary/cassowary/Cl.h new file mode 100644 index 0000000000..6c2604da6f --- /dev/null +++ b/libs/cassowary/cassowary/Cl.h @@ -0,0 +1,49 @@ +// $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 +// +// Cl.h +// This is the top level include file for external clients + +#ifndef CL_H +#define CL_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 + +#ifdef CL_NO_IO +#undef CL_TRACE +#undef CL_SOLVER_STATS +#undef CL_DEBUG_FAILURES +#undef CL_TRACE_VERBOSE +#endif + +#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 "cassowary/ClVariable.h" +#include "cassowary/ClSimplexSolver.h" +#include "cassowary/ClLinearEquation.h" +#include "cassowary/ClLinearInequality.h" +#include "cassowary/ClErrors.h" +#include "cassowary/ClEditConstraint.h" +#include "cassowary/ClStayConstraint.h" +#include "cassowary/ClReader.h" +#include "cassowary/ClConstraint.h" +#if defined(CL_HAVE_GTL) && defined(CL_BUILD_FD_SOLVER) +#include "cassowary/ClFDBinaryOneWayConstraint.h" +#include "cassowary/ClFDSolver.h" +#endif + +extern const char *szCassowaryVersion; + +#endif diff --git a/libs/cassowary/cassowary/ClAbstractVariable.h b/libs/cassowary/cassowary/ClAbstractVariable.h new file mode 100644 index 0000000000..08ade9ec98 --- /dev/null +++ b/libs/cassowary/cassowary/ClAbstractVariable.h @@ -0,0 +1,161 @@ +// $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 +// +// ClAbstractVariable.h + +#ifndef ClAbstractVariable_H +#define ClAbstractVariable_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 <cstdio> /* for sprintf */ +#include "Cassowary.h" +#include "ClErrors.h" +#include <memory> +#include <string> +#include <iostream> +#include "cl_auto_ptr.h" + +using std::string; +using std::ostream; + +class ClAbstractVariable { +public: + ClAbstractVariable(string Name = "") : + _name(Name), _pv(0) + { + ++iVariableNumber; +#ifdef CL_FIND_LEAK + ++cAbstractVariables; +#endif + if (Name.length() == 0) + { + char sz[16]; + sprintf(sz,"v%ld",iVariableNumber); + _name = string(sz); + } + } + + ClAbstractVariable(long varnumber, char *prefix) : + _pv(0) + { + cl_auto_ptr<char> pch (new char[16+strlen(prefix)]); + iVariableNumber++; +#ifdef CL_FIND_LEAK + ++cAbstractVariables; +#endif + sprintf(pch.get(),"%s%ld",prefix,varnumber); + _name = string(pch.get()); + } + + virtual ~ClAbstractVariable() +#ifdef CL_FIND_LEAK + { --cAbstractVariables; } + + static long cAbstractVariables; +#else + { } +#endif + + // Return the Name of the variable + string Name() const + { return _name; } + + // Set the Name of the variable + virtual void SetName(string const &Name) + { _name = Name; } + + // Return true iff this variable is a ClFloatVariable + virtual bool IsFloatVariable() const + { return false; } + + // Return true iff this variable is a ClFDVariable + virtual bool IsFDVariable() const + { return false; } + + // Return true if this a dummy variable (used as a marker variable + // for required equality constraints). Such variables aren't + // allowed to enter the basis when pivoting. + virtual bool IsDummy() const + { return false; } + + // Return true if this a variable known outside the solver. + // (We need to give such variables a Value after solving is complete.) + virtual bool IsExternal() const + { return false; } + + // Return true if we can Pivot on this variable. + virtual bool IsPivotable() const + { throw ExCLTooDifficultSpecial("Variable not usable inside SimplexSolver"); return false; } + + // Return true if this is a restricted (or slack) variable. Such + // variables are constrained to be non-negative and occur only + // internally to the simplex solver. + virtual bool IsRestricted() const + { throw ExCLTooDifficultSpecial("Variable not usable inside SimplexSolver"); return false; } + +#ifndef CL_NO_IO + // Prints a semi-descriptive representation to the stream, using the + // Name if there is one, and otherwise the hash number of this + // object. + // EXAMPLES + // x[10.0] -- w/ Name + // x[0.0,100] -- w/ Name, bounds but no Value yet + // CV#345(10.0) -- w/o Name + virtual ostream &PrintOn(ostream &xo) const = 0; + + friend ostream& operator<<(ostream &xos, const ClAbstractVariable &clv) + { clv.PrintOn(xos); return xos; } + +#endif // CL_NO_IO + + friend bool operator<(const ClAbstractVariable &cl1, const ClAbstractVariable &cl2) + { return &cl1 < &cl2; } + + friend bool operator==(const ClAbstractVariable &cl1, const ClAbstractVariable &cl2) + { + return &cl1 == &cl2; + } + + friend bool operator!=(const ClAbstractVariable &cl1, const ClAbstractVariable &cl2) + { + return !(cl1 == cl2); + } + + virtual Number Value() const { return 0; } + virtual int IntValue() const { return 0; } + + virtual void SetValue(Number) + { assert(false); } + + virtual void ChangeValue(Number) + { assert(false); } + + void SetPv(void *pv) + { _pv = pv; } + + void *Pv() const + { return _pv; } + +private: + string _name; + + static long iVariableNumber; + + // C-style extension mechanism so I + // don't have to wrap ScwmClVariables separately + void *_pv; +}; + +typedef ClAbstractVariable *PClAbstractVariable; + +#endif diff --git a/libs/cassowary/cassowary/ClConstraint.h b/libs/cassowary/cassowary/ClConstraint.h new file mode 100644 index 0000000000..0b670e6c07 --- /dev/null +++ b/libs/cassowary/cassowary/ClConstraint.h @@ -0,0 +1,198 @@ +// $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 +// +// ClConstraint.h + +#ifndef ClConstraint_H +#define ClConstraint_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 "debug.h" + +#include "Cassowary.h" +#include "ClLinearExpression.h" +#include "ClStrength.h" +#include <string> + +using std::string; + +class ClSimplexSolver; +class ClFDSolver; +class ClBlueSolver; + +// enum setup so additive inverse flips the direction of the inequality +enum ClCnRelation {cnEQ = 0, cnNEQ = 100, cnLEQ = 2, cnGEQ = -2, cnLT = 3, cnGT = -3 }; + +inline enum ClCnRelation +ReverseInequality(enum ClCnRelation c) +{ + if (c != cnNEQ) + c = (enum ClCnRelation) (- int(c)); + return c; +} + +inline string +StrCnRelation(enum ClCnRelation rel) { + switch (rel) { + case cnEQ: return "="; + case cnNEQ: return "=/="; + case cnLEQ: return "<="; + case cnGEQ: return ">="; + case cnLT: return "<"; + case cnGT: return ">"; + default: assert(false); + } +} + + + +class ClConstraint { +public: + + ClConstraint(const ClStrength &strength = ClsRequired(), double weight = 1.0 ) : + _strength(strength), + _readOnlyVars(), + _weight(weight), + _pv(0), + _times_added(0) + { + CtrTracer(__FUNCTION__,this); + } + + virtual ~ClConstraint() + { + DtrTracer(__FUNCTION__,this); + } + + // Return my linear Expression. (For linear equations, this + // constraint represents Expression=0; for linear inequalities it + // represents Expression>=0.) + virtual ClLinearExpression Expression() const + { assert(false); } + + // Returns true if this is an edit constraint + virtual bool IsEditConstraint() const + { return false; } + + // Return true if this is an inequality constraint and + // false if it is an equality constraint. The default is + // that it is not. + virtual bool IsInequality() const + { return false; } + + virtual bool IsStrictInequality() const + { return false; } + + virtual bool IsRequired() const + { return _strength.IsRequired(); } + + virtual bool isStayConstraint() const + { return false; } + + virtual const ClStrength &strength() const + { return _strength; } + + virtual double weight() const + { return _weight; } + +#ifndef CL_NO_IO + virtual ostream &PrintOn(ostream &xo) const = 0; + + friend ostream& operator<<(ostream &xos, const ClConstraint &constraint) + { constraint.PrintOn(xos); return xos; } + +#endif + + + void SetPv(void *pv) + { _pv = pv; } + + void *Pv() const + { return _pv; } + + virtual bool FIsSatisfied() const { return false; } + + virtual bool FIsInSolver() const { return _times_added != 0; } + + virtual bool FIsOkayForSimplexSolver() const { return true; } + + void ChangeStrength( const ClStrength &strength) + { + if (_times_added == 0) { + setStrength(strength); + } else { + throw ExCLTooDifficult(); + } + } + + void ChangeWeight( double weight ) + { + if (_times_added == 0) { + setWeight(weight); + } else { + throw ExCLTooDifficult(); + } + } + + bool FIsReadOnlyVar(ClVariable v) const { + return !(_readOnlyVars.find(v) == _readOnlyVars.end()); + } + + const ClVarSet &ReadOnlyVars() const { + return _readOnlyVars; + } + + ClConstraint &AddROVars(const ClVarSet &setClv) { + for ( ClVarSet::const_iterator it = setClv.begin(); + it != setClv.end(); ++it) { + _readOnlyVars.insert(*it); + } + return *this; + } + + friend class ClSimplexSolver; + friend class ClFDSolver; + friend class ClBlueSolver; +private: + + ClSymbolicWeight symbolicWeight() const { + return _strength.symbolicWeight(); + } + + void addedTo(const ClSimplexSolver &) + { ++_times_added; } + + void removedFrom(const ClSimplexSolver &) + { --_times_added; } + + void setStrength( const ClStrength &strength ) + { _strength = strength; } + + void setWeight( double weight ) + { _weight = weight; } + + /// instance variables + ClStrength _strength; + + ClVarSet _readOnlyVars; + + double _weight; + + void *_pv; + + int _times_added; +}; + +typedef ClConstraint* PClConstraint; + +#endif diff --git a/libs/cassowary/cassowary/ClConstraintHash.h b/libs/cassowary/cassowary/ClConstraintHash.h new file mode 100644 index 0000000000..9d51fad311 --- /dev/null +++ b/libs/cassowary/cassowary/ClConstraintHash.h @@ -0,0 +1,39 @@ +// $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 +// +// ClHash.h + +#ifndef CL_HASH_H__ +#define CL_HASH_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 + +#ifdef CL_USE_HASH_MAP_AND_SET + +#include <hash_map> + +class ClConstraint; + +struct hash<const ClConstraint *> { + size_t operator()(const ClConstraint * const p) const + { return size_t((unsigned long)p/CL_PTR_HASH_DIVISOR); } +}; + +struct hash<ClConstraint *> { + size_t operator()(ClConstraint * const p) const + { return size_t((unsigned long)p/CL_PTR_HASH_DIVISOR); } +}; + +#endif // CL_USE_HASH_MAP_AND_SET + + +#endif diff --git a/libs/cassowary/cassowary/ClDummyVariable.h b/libs/cassowary/cassowary/ClDummyVariable.h new file mode 100644 index 0000000000..ad959a6d20 --- /dev/null +++ b/libs/cassowary/cassowary/ClDummyVariable.h @@ -0,0 +1,88 @@ +// $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 +// +// ClDummyVariable.h + +#ifndef ClDummyVariable_H +#define ClDummyVariable_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 "Cassowary.h" +#include "ClAbstractVariable.h" + +class ClTableau; +class ClSimplexSolver; + +class ClDummyVariable : public ClAbstractVariable { + +public: + +#ifdef CL_FIND_LEAK + ~ClDummyVariable() { --cDummyVariables; }; + + static long cDummyVariables; + +#endif + +protected: + friend class ClTableau; + friend class ClSimplexSolver; + + ClDummyVariable(string Name = "") : + ClAbstractVariable(Name) + { +#ifdef CL_FIND_LEAK + ++cDummyVariables; +#endif + } + + ClDummyVariable(long number, char *prefix) : + ClAbstractVariable(number,prefix) + { +#ifdef CL_FIND_LEAK + ++cDummyVariables; +#endif + } + +#ifndef CL_NO_IO + virtual ostream &PrintOn(ostream &xo) const + { + xo << "[" << Name() << ":dummy]"; + return xo; + } +#endif + + // Return true if this a dummy variable (used as a marker variable + // for required equality constraints). Such variables aren't + // allowed to enter the basis when pivoting. + virtual bool IsDummy() const + { return true; } + + // Return true if this a variable known outside the solver. + // (We need to give such variables a Value after solving is complete.) + virtual bool IsExternal() const + { return false; } + + // Return true if we can Pivot on this variable. + virtual bool IsPivotable() const + { return false; } + + // Return true if this is a restricted (or slack) variable. Such + // variables are constrained to be non-negative and occur only + // internally to the simplex solver. + virtual bool IsRestricted() const + { return true; } + +}; + +#endif diff --git a/libs/cassowary/cassowary/ClEditConstraint.h b/libs/cassowary/cassowary/ClEditConstraint.h new file mode 100644 index 0000000000..4bd91e2ca2 --- /dev/null +++ b/libs/cassowary/cassowary/ClEditConstraint.h @@ -0,0 +1,45 @@ +// $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 +// +// ClEditConstraint.h + +#ifndef ClEditConstraint_H +#define ClEditConstraint_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 "Cassowary.h" +#include "ClEditOrStayConstraint.h" + +class ClEditConstraint : public ClEditOrStayConstraint { + typedef ClEditOrStayConstraint super; + public: + + ClEditConstraint(const ClVariable var, + const ClStrength &strength = ClsStrong(), double weight = 1.0 ) : + ClEditOrStayConstraint(var,strength,weight) + { } + + // Returns true if this is an edit constraint + virtual bool IsEditConstraint() const + { return true; } + +#ifndef CL_NO_IO + virtual ostream &PrintOn(ostream &xo) const + { super::PrintOn(xo); return xo << "= edit)"; } +#endif + + private: + +}; + +#endif diff --git a/libs/cassowary/cassowary/ClEditOrStayConstraint.h b/libs/cassowary/cassowary/ClEditOrStayConstraint.h new file mode 100644 index 0000000000..79b6761b69 --- /dev/null +++ b/libs/cassowary/cassowary/ClEditOrStayConstraint.h @@ -0,0 +1,51 @@ +// $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 +// +// ClEditOrStayConstraint.h + +#ifndef ClEditOrStayConstraint_H +#define ClEditOrStayConstraint_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 "ClConstraint.h" +#include "ClLinearExpression.h" + +class ClVariable; + +class ClEditOrStayConstraint : public ClConstraint { + public: + + ClEditOrStayConstraint(const ClVariable var, + const ClStrength &strength = ClsRequired(), double weight = 1.0 ) : + ClConstraint(strength,weight), + _variable(var) + { } + + const ClVariable variable() const + { return _variable; } + + ClLinearExpression Expression() const + { return ClLinearExpression(_variable,-1,_variable.Value()); } + + private: + + void setVariable( const ClVariable v) + { _variable = v; } + + /// instance variables + ClVariable _variable; + + +}; + +#endif diff --git a/libs/cassowary/cassowary/ClErrors.h b/libs/cassowary/cassowary/ClErrors.h new file mode 100644 index 0000000000..867c578dbc --- /dev/null +++ b/libs/cassowary/cassowary/ClErrors.h @@ -0,0 +1,179 @@ +// $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 +// +// ClErrors.h + +#ifndef ClErrors_H +#define ClErrors_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 "Cassowary.h" +#include "ClTypedefs.h" +#include <string> +#include <exception> + +using std::string; +using std::exception; + +class ExCLError : public exception { + public: + ExCLError() : _msg(0) { } + virtual ~ExCLError() throw() {} + virtual string description() const + { return "(ExCLError) An error has occured in CL"; } + protected: + char *_msg; +}; + +class ExCLInternalError : public ExCLError { + public: + ExCLInternalError(const char *sz) + { _msg = strdup(sz); } + virtual string description() const + { + if (_msg) return _msg; + else return "(ExCLInternalError) An internal error has occurred"; + } +}; + +class ExCLBadResolve : public ExCLError { + public: + ExCLBadResolve(const char *sz) + { _msg = strdup(sz); } + virtual string description() const + { + if (_msg) return _msg; + else return "(ExCLBadResolve) Number of resolve values did not match number of edit vars"; + } +}; + +class ExCLEditMisuse : public ExCLError { + public: + ExCLEditMisuse(const char *sz) + { _msg = strdup(sz); } + virtual string description() const + { + if (_msg) return _msg; + return "(ExCLEditMisuse) Edit protocol usage violation"; + } +}; + +class ExCLTooDifficult : public ExCLError { + public: + virtual string description() const + { return "(ExCLTooDifficult) The constraints are too difficult to solve"; } +}; + +class ExCLTooDifficultSpecial : public ExCLTooDifficult { + public: + ExCLTooDifficultSpecial(const char *sz) + { _msg = strdup(sz); } + virtual string description() const + { + if (_msg) return _msg; + else return "(ExCLTooDifficultSpecial) Solver requirements are not satisfied"; + } +}; + +class ExCLReadOnlyNotAllowed : public ExCLTooDifficult { + public: + virtual string description() const + { return "(ExCLReadOnlyNotAllowed) The read-only annotation is not permitted by the solver"; } +}; + +class ExCLCycleNotAllowed : public ExCLTooDifficult { + public: + virtual string description() const + { return "(ExCLCycleNotAllowed) A cyclic constraint graph is not permitted by the solver"; } +}; + +class ExCLStrictInequalityNotAllowed : public ExCLTooDifficult { + public: + virtual string description() const + { return "(ExCLStrictInequalityNotAllowed) The strict inequality is not permitted by the solver"; } +}; + +class ExCLRequiredFailure : public ExCLError { + public: + virtual ~ExCLRequiredFailure() throw() {} + virtual string description() const + { return "(ExCLRequiredFailure) A required constraint cannot be satisfied"; } +}; + +class ExCLNotEnoughStays : public ExCLError { + public: + virtual string description() const + { return "(ExCLNotEnoughStays) There are not enough stays to give specific values to every variable"; } +}; + +class ExCLNonlinearExpression : public ExCLError { + public: + virtual string description() const + { return "(ExCLNonlinearExpression) The resulting expression would be nonlinear"; } +}; + +class ExCLConstraintNotFound : public ExCLError { + public: + virtual string description() const + { return "(ExCLConstraintNotFound) Tried to remove a constraint that was never added"; } +}; + +class ExCLParseError : public ExCLError { + public: + virtual ~ExCLParseError() throw() {} + virtual string description() const + { return "(ExCLParseError)"; } +}; + +class ExCLParseErrorMisc : public ExCLParseError { + public: + ExCLParseErrorMisc(const string &s) + : _msg("(ExCLParseError) ") + { _msg += s; } + virtual ~ExCLParseErrorMisc() throw() {} + virtual string description() const + { return _msg; } + private: + string _msg; +}; + +class ExCLParseErrorBadIdentifier : public ExCLParseError { + public: + ExCLParseErrorBadIdentifier(const string &id) + : _msg("(ExCLParseErrorBadIdentifier) Did not recognize identifier '") + { + _msg += id; + _msg += "'"; + } + virtual ~ExCLParseErrorBadIdentifier() throw() {} + virtual string description() const + { return _msg; } + private: + string _msg; +}; + +class ExCLRequiredFailureWithExplanation : public ExCLRequiredFailure +{ +public: + virtual ~ExCLRequiredFailureWithExplanation() throw() {} + virtual string description() const + { return "(ExCLRequiredFailureWithExplanation) A required constraint cannot be satisfied"; } + virtual void AddConstraint(const ClConstraint *cnExpl) + { _explanation.insert(cnExpl); } + virtual const ClConstraintSet & explanation() const + { return _explanation; } +protected: + ClConstraintSet _explanation; +}; + +#endif // ClErrors_H diff --git a/libs/cassowary/cassowary/ClFDBinaryOneWayConstraint.h b/libs/cassowary/cassowary/ClFDBinaryOneWayConstraint.h new file mode 100644 index 0000000000..a779ec1f91 --- /dev/null +++ b/libs/cassowary/cassowary/ClFDBinaryOneWayConstraint.h @@ -0,0 +1,94 @@ +// $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 +// +// ClFDBinaryOneWayConstraint.h + +#ifndef ClFDBinaryOneWayConstraint_H +#define ClFDBinaryOneWayConstraint_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 "Cassowary.h" +#include "ClFDConstraint.h" + +class ClLinearConstraint; + +// Just a node in the class hierarchy for now +class ClFDBinaryOneWayConstraint : public ClFDConstraint { + private: typedef ClFDConstraint super; + + public: + + ClFDBinaryOneWayConstraint(ClVariable vRW, enum ClCnRelation rel, ClVariable vRO, + double coefficient = 1.0, double constant = 0.0, + const ClStrength &strength = ClsRequired(), + double weight = 1.0) + : ClFDConstraint(strength,weight), _vRW(vRW), _rel(rel), _vRO(vRO), + _coefficient(coefficient), _constant(constant) + { } + + ClFDBinaryOneWayConstraint(ClVariable vRW, enum ClCnRelation rel, double constant, + const ClStrength &strength = ClsRequired(), + double weight = 1.0) + : ClFDConstraint(strength,weight), _vRW(vRW), _rel(rel), _vRO(clvNil), + _coefficient(0), _constant(constant) + { } + + ClFDBinaryOneWayConstraint(const ClConstraint &cn); + + static void EnsurePreconditionsForCn(const ClConstraint &cn); + + static bool FCanConvertCn(const ClConstraint &cn); + +#ifndef CL_NO_IO + virtual ostream &PrintOn(ostream &xo) const + { + xo << "FDCn: " << _vRW << " " << StrCnRelation(_rel) << " "; + if (_coefficient != 0) { + if (_coefficient != 1) xo << _coefficient << "*"; + if (_vRO != clvNil) xo << _vRO; + } + if (_constant != 0) xo << " + " << _constant; + return xo; + } + + friend ostream& operator<<(ostream &xos, const ClFDBinaryOneWayConstraint &constraint) + { return constraint.PrintOn(xos); } + +#endif + + ClVariable ClvRW() const + { return _vRW; } + ClVariable ClvRO() const + { return _vRO; } + enum ClCnRelation Relation() const + { return _rel; } + double Coefficient() const + { return _coefficient; } + double Constant() const + { return _constant; } + + bool IsInequality() const + { return (_rel != cnEQ && _rel != cnNEQ); } + + bool IsStrictInequality() const + { return (_rel == cnGT || _rel == cnLT); } + + protected: + ClVariable _vRW; + enum ClCnRelation _rel; + ClVariable _vRO; + double _coefficient; + double _constant; +}; + +#endif diff --git a/libs/cassowary/cassowary/ClFDConnectorVariable.h b/libs/cassowary/cassowary/ClFDConnectorVariable.h new file mode 100644 index 0000000000..4ae38ae42e --- /dev/null +++ b/libs/cassowary/cassowary/ClFDConnectorVariable.h @@ -0,0 +1,89 @@ +// $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 +// +// ClFDConnectorVariable.h + +#ifndef ClFDConnectorVariable_H +#define ClFDConnectorVariable_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 <stdio.h> +#include <map> +#include <string> +#include <list> +#include "Cassowary.h" +#include "ClVariable.h" +#include "ClFDVariable.h" +#include "ClLinearEquation.h" +#include "ClSimplexSolver.h" + +/* Creates a new variable in the FD region + that sets clvFloat in solver (simplex region) + when it changes */ +class ClFDConnectorVariable : public ClFDVariable { +public: + typedef ClFDVariable super; + + ClFDConnectorVariable(string name, FDNumber Value, const list<FDNumber> &initial_domain, + ClSimplexSolver &solver, ClVariable clvFloat) : + ClFDVariable(name,Value,initial_domain), + _solver(solver), + _clvFloat(clvFloat), + _pcnRequiredLink(new ClLinearEquation(clvFloat,Value)) + { solver.AddConstraint(_pcnRequiredLink); } + +#ifndef CL_NO_IO + // Prints a semi-descriptive representation to the stream, using the + // name if there is one, and otherwise the hash number of this + // object. + // EXAMPLE + // [x:10.0] -- name = "x", Value = 10.0 + virtual ostream &PrintOn(ostream &xo) const; +#endif + + // permit overriding in subclasses in case something needs to be + // done when the Value is changed by the solver + // may be called when the Value hasn't actually changed -- just + // means the solver is setting the external variable + virtual void ChangeValue(FDNumber Value) + { + if (_value != Value) { + _value = Value; + cerr << "Updating " << _clvFloat << " now!" << endl; + _solver.RemoveConstraint(_pcnRequiredLink); + _pcnRequiredLink->ChangeConstant(_value); + _solver.AddConstraint(_pcnRequiredLink); + } + } + +private: + + // similar to SetValue -- see caveat above -- made private for now + // since it's probably the wrong thing and is too easy to invoke + FDNumber operator=(FDNumber Value) + { _value = Value; return Value; } + + // Copy constructor left undefined since we want to + // outlaw passing by Value! Will get a link error if you + // try to use within ClFDConnectorVariable.c, compile-time error everywhere else + ClFDConnectorVariable(const ClFDConnectorVariable &); + + ClSimplexSolver &_solver; + + ClVariable _clvFloat; + + ClLinearEquation *_pcnRequiredLink; + +}; + +#endif diff --git a/libs/cassowary/cassowary/ClFDConstraint.h b/libs/cassowary/cassowary/ClFDConstraint.h new file mode 100644 index 0000000000..2cf9776449 --- /dev/null +++ b/libs/cassowary/cassowary/ClFDConstraint.h @@ -0,0 +1,40 @@ +// $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 +// +// ClFDConstraint.h + +#ifndef ClFDConstraint_H +#define ClFDConstraint_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 "Cassowary.h" +#include "ClConstraint.h" + + +// Just a node in the class hierarchy for now +class ClFDConstraint : public ClConstraint { + private: typedef ClConstraint super; + + public: + // Constructor + ClFDConstraint(const ClStrength &strength = ClsRequired(), + double weight = 1.0) + : ClConstraint(strength, weight) { } + + virtual bool FIsOkayForSimplexSolver() const { return false; } + + protected: + +}; + +#endif diff --git a/libs/cassowary/cassowary/ClFDSolver.h b/libs/cassowary/cassowary/ClFDSolver.h new file mode 100644 index 0000000000..2fbb637764 --- /dev/null +++ b/libs/cassowary/cassowary/ClFDSolver.h @@ -0,0 +1,120 @@ +// $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 +// +// ClSolver.h + +#ifndef ClFDSolver_H +#define ClFDSolver_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 "Cassowary.h" +#include "ClSolver.h" +#include "ClVariable.h" +#include "ClErrors.h" +#include "ClTypedefs.h" +#include "ClSymbolicWeight.h" +#include <GTL/graph.h> +#include <map> + +using std::map; + +class ClVariable; +class ClFDBinaryOneWayConstraint; + +// ClFDSolver is a concrete class +// implementing a very restricted (for now --04/23/99 gjb) +// finite-domain constraint solving algorithm +class ClFDSolver: public ClSolver { + public: + ClFDSolver() + : _setCns(), _mapClvToCns(), G(), nodeToVar(G) + { G.make_directed(); } + + virtual ~ClFDSolver() + { } + + virtual ClFDSolver &AddConstraint(ClConstraint *const pcn); + + virtual ClFDSolver &RemoveConstraint(ClConstraint *const pcn); + + virtual ClFDSolver &Solve(); + + virtual ClFDSolver &ShowSolve(); + + void ChangeClv(ClVariable clv, FDNumber n) { + clv.ChangeValue(n); + if (_pfnChangeClvCallback) { + _pfnChangeClvCallback(&clv,this); + } + } + + +#ifndef CL_NO_IO + ostream &PrintOn(ostream &xo) const; + + ostream &PrintInternalInfo(ostream &xo) const; + + ostream &PrintOnVerbose(ostream &xo) const + { PrintOn(xo); PrintInternalInfo(xo); xo << endl; return xo; } + + friend ostream &operator<<(ostream &xo, const ClFDSolver &solver); + +#endif + + protected: + + virtual ClFDSolver &AddConstraintInternal(ClConstraint *const pcn); + + virtual ClFDSolver &RemoveConstraintInternal(ClConstraint *const pcn); + + /* Create node for v in G, if necessary, + otherwise return the node we already created. */ + node GetVarNode(ClVariable v); + + /* return the best (lowest) incremental error and the value + at which that error occurs */ + pair<ClSymbolicWeight,FDNumber> ComputeBest(ClFDVariable *pcldv); + + ClSymbolicWeight ErrorForClvAtValSubjectToCn(ClFDVariable *pcldv, + FDNumber value,const ClConstraint &cn); + + /* Turn all FDVariable FIsSet() flags to false */ + void ResetSetFlagsOnVariables(); + + /* all the constraints in the solver */ + ClConstraintSet _setCns; + + /* _mapClvToCns maps variable to the constraints in which + it is rw (it omits where it is ro) */ + ClVarToConstraintSetMap _mapClvToCns; + + /* track what edges correspond to which constraints + so we can update the constraint graph when + removing a constraint */ + map<ClConstraint *, edge> _mapCnToEdge; + + /* track what nodes correspond to which variables */ + map<ClVariable, node> _mapVarToNode; + + /* directed graph that mirrors the structure of + the relations of the added constraints */ + graph G; + + node_map<ClVariable> nodeToVar; +}; + +#define FDN_EOL LONG_MIN + +void ListPushOnto(list<FDNumber> *pl, ...); + +#endif diff --git a/libs/cassowary/cassowary/ClFDVariable.h b/libs/cassowary/cassowary/ClFDVariable.h new file mode 100644 index 0000000000..326b339459 --- /dev/null +++ b/libs/cassowary/cassowary/ClFDVariable.h @@ -0,0 +1,126 @@ +// $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 +// +// ClFDVariable.h + +#ifndef ClFDVariable_H +#define ClFDVariable_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 <cstdio> +#include <map> +#include <string> +#include <list> +#include "Cassowary.h" +#include "ClAbstractVariable.h" + +using std::map; +using std::list; +using std::string; + +class ClFDVariable : public ClAbstractVariable { +public: + typedef ClAbstractVariable super; + +#if 0 /* GJB:FIXME:: */ + ClFDVariable(string name, FDNumber Value) : + ClAbstractVariable(name), + _value(Value), + _fSet(true), + _desired_value(Value), + _plfdnInitialDomain(0) + { } +#endif + + ClFDVariable(string name, FDNumber Value, const list<FDNumber> &initial_domain) : + ClAbstractVariable(name), + _value(Value), + _fSet(true), + _desired_value(Value), + _plfdnInitialDomain(new list<FDNumber>()) + { + *_plfdnInitialDomain = initial_domain; + } + + virtual bool IsFDVariable() const + { return true; } + + // Return true if this a variable known outside the solver. + // (We need to give such variables a Value after solving is complete.) + virtual bool IsExternal() const + { return true; } + +#ifndef CL_NO_IO + // Prints a semi-descriptive representation to the stream, using the + // name if there is one, and otherwise the hash number of this + // object. + // EXAMPLE + // [x:10.0] -- name = "x", Value = 10.0 + virtual ostream &PrintOn(ostream &xo) const; +#endif + + // Return the current Value I hold. + Number Value() const + { return _value; } + + // Round the Value to an integer and return it + int IntValue() const + { return _value; } + + // change the Value held -- should *not* use this if the variable is + // in a solver -- instead use AddEditVar() and SuggestValue() interface + void SetValue(FDNumber Value) + { _value = Value; } + + // permit overriding in subclasses in case something needs to be + // done when the Value is changed by the solver + // may be called when the Value hasn't actually changed -- just + // means the solver is setting the external variable + virtual void ChangeValue(FDNumber Value) + { _value = Value; } + + virtual bool FIsSet() + { return _fSet; } + + virtual void SetFIsSet(bool f) + { _fSet = f; } + + virtual FDNumber DesiredValue() const + { return _desired_value; } + + virtual const list<FDNumber> *PlfdnDomain() const + { return _plfdnInitialDomain; } + +protected: + + // similar to SetValue -- see caveat above -- made private for now + // since it's probably the wrong thing and is too easy to invoke + FDNumber operator=(FDNumber Value) + { _value = Value; return Value; } + + // Copy constructor left undefined since we want to + // outlaw passing by Value! Will get a link error if you + // try to use within ClFDVariable.c, compile-time error everywhere else + ClFDVariable(const ClFDVariable &); + + FDNumber _value; + + // has the _value been set? Used during solves. + bool _fSet; + + FDNumber _desired_value; + + list<FDNumber> *_plfdnInitialDomain; +}; + +#endif diff --git a/libs/cassowary/cassowary/ClFloatVariable.h b/libs/cassowary/cassowary/ClFloatVariable.h new file mode 100644 index 0000000000..4e58036ab7 --- /dev/null +++ b/libs/cassowary/cassowary/ClFloatVariable.h @@ -0,0 +1,119 @@ +// $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 +// +// ClFloatVariable.h + +#ifndef ClFloatVariable_H +#define ClFloatVariable_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 <cstdio> +#include <map> +#include <string> +#include "Cassowary.h" +#include "ClAbstractVariable.h" + +using std::map; +using std::string; + +class ClFloatVariable : public ClAbstractVariable { +public: + typedef ClAbstractVariable super; + + ClFloatVariable(string name, Number Value = 0.0) : + ClAbstractVariable(name), + _value(Value) + { } + + ClFloatVariable(Number Value = 0.0) : + ClAbstractVariable(""), + _value(Value) + { } + + ClFloatVariable(long number, char *prefix, Number Value = 0.0) : + ClAbstractVariable(number,prefix), + _value(Value) + { } + + virtual bool IsFloatVariable() const + { return true; } + + // Return true if this a dummy variable (used as a marker variable + // for required equality constraints). Such variables aren't + // allowed to enter the basis when pivoting. + virtual bool IsDummy() const + { return false; } + + // Return true if this a variable known outside the solver. + // (We need to give such variables a Value after solving is complete.) + virtual bool IsExternal() const + { return true; } + + // Return true if we can Pivot on this variable. + virtual bool IsPivotable() const + { return false; } + + // Return true if this is a restricted (or slack) variable. Such + // variables are constrained to be non-negative and occur only + // internally to the simplex solver. + virtual bool IsRestricted() const + { return false; } + +#ifndef CL_NO_IO + // Prints a semi-descriptive representation to the stream, using the + // name if there is one, and otherwise the hash number of this + // object. + // EXAMPLE + // [x:10.0] -- name = "x", Value = 10.0 + virtual ostream &PrintOn(ostream &xo) const; +#endif + + // Return the current Value I hold. + Number Value() const + { return _value; } + + // Round the Value to an integer and return it + int IntValue() const + { return int(_value + 0.5); } + + // change the Value held -- should *not* use this if the variable is + // in a solver -- instead use AddEditVar() and SuggestValue() interface + void SetValue(Number Value) + { _value = Value; } + + // permit overriding in subclasses in case something needs to be + // done when the Value is changed by the solver + // may be called when the Value hasn't actually changed -- just + // means the solver is setting the external variable + virtual void ChangeValue(Number Value) + { _value = Value; } + +private: + + // similar to SetValue -- see caveat above -- made private for now + // since it's probably the wrong thing and is too easy to invoke + Number operator=(Number Value) + { _value = Value; return Value; } + + // Copy constructor left undefined since we want to + // outlaw passing by Value! Will get a link error if you + // try to use within ClFloatVariable.c, compile-time error everywhere else + ClFloatVariable(const ClFloatVariable &); + + Number _value; + +}; + + + +#endif diff --git a/libs/cassowary/cassowary/ClLinearConstraint.h b/libs/cassowary/cassowary/ClLinearConstraint.h new file mode 100644 index 0000000000..d657d1d73e --- /dev/null +++ b/libs/cassowary/cassowary/ClLinearConstraint.h @@ -0,0 +1,61 @@ +// $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 +// +// ClLinearConstraint.h + +#ifndef ClLinearConstraint_H +#define ClLinearConstraint_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 "Cassowary.h" +#include "ClConstraint.h" +#include "ClLinearExpression.h" + + +// Add the ClLinearExpression member variable needed for both +// ClLinearEquation and ClLinearInequality +class ClLinearConstraint : public ClConstraint { + private: typedef ClConstraint super; + + public: + + // Constructor + ClLinearConstraint(const ClLinearExpression &cle, + const ClStrength &strength = ClsRequired(), + double weight = 1.0) : + ClConstraint(strength, weight), + _expression(cle) + { } + + virtual ~ClLinearConstraint() {} + + // Return my linear Expression. (For linear equations, this + // constraint represents Expression=0; for linear inequalities it + // represents Expression>=0.) + ClLinearExpression Expression() const + { return _expression; } + + // do not do this if *this is inside a solver + void ChangeConstant(Number constant) + { _expression.Set_constant(constant); } + + protected: + + ClLinearExpression _expression; + + virtual void setExpression( const ClLinearExpression &expr) + { _expression = expr; } + +}; + +#endif diff --git a/libs/cassowary/cassowary/ClLinearEquation.h b/libs/cassowary/cassowary/ClLinearEquation.h new file mode 100644 index 0000000000..a02b51d70b --- /dev/null +++ b/libs/cassowary/cassowary/ClLinearEquation.h @@ -0,0 +1,74 @@ +// $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 +// +// ClLinearEquation.h + +#ifndef ClLinearEquation_H +#define ClLinearEquation_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 "Cassowary.h" +#include "ClLinearConstraint.h" +#include "ClLinearExpression.h" + +class ClStrength; +class ClVariable; + +class ClLinearEquation : public ClLinearConstraint { + private: typedef ClLinearConstraint super; + + public: + //// Constructors + + // ClLinearEquation(expr,...) is expr == 0 + ClLinearEquation(const ClLinearExpression &cle, + const ClStrength &strength = ClsRequired(), + double weight = 1.0) : + ClLinearConstraint(cle,strength, weight) + { } + + // ClLinearEquation(var,expr,...) is var == expr + ClLinearEquation(ClVariable clv, + const ClLinearExpression &cle, + const ClStrength &strength = ClsRequired(), + double weight = 1.0) : + ClLinearConstraint(cle,strength,weight) + { _expression.AddVariable(clv,-1.0); } + + // ClLinearEquation(expr,var,...) is var == expr + ClLinearEquation(const ClLinearExpression &cle, + ClVariable clv, + const ClStrength &strength = ClsRequired(), + double weight = 1.0) : + ClLinearConstraint(cle,strength,weight) + { _expression.AddVariable(clv,-1.0); } + + // ClLinearEquation(expr,expr,...) is expr == expr + ClLinearEquation(const ClLinearExpression &cle1, + const ClLinearExpression &cle2, + const ClStrength &strength = ClsRequired(), + double weight = 1.0) : + ClLinearConstraint(cle1,strength,weight) + { _expression.AddExpression(cle2,-1.0); } + +#ifndef CL_NO_IO + virtual ostream &PrintOn(ostream &xo) const + { super::PrintOn(xo); xo << " = 0 )"; return xo; } +#endif + + virtual bool FIsSatisfied() const + { return (_expression.Evaluate() == 0); } + +}; + +#endif diff --git a/libs/cassowary/cassowary/ClLinearExpression.h b/libs/cassowary/cassowary/ClLinearExpression.h new file mode 100644 index 0000000000..0a1df9c243 --- /dev/null +++ b/libs/cassowary/cassowary/ClLinearExpression.h @@ -0,0 +1,298 @@ +// $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.h + +#ifndef ClLinearExpression_H +#define ClLinearExpression_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 "Cassowary.h" +#include "debug.h" +#include "ClVariable.h" +#include "ClLinearExpression_fwd.h" + +class ClSimplexSolver; +class ClTableau; +class ClSymbolicWeight; + +ClLinearExpression &cleNil(); + +template <class T> +class ClGenericLinearExpression { + public: + typedef std::map<ClVariable,T> ClVarToCoeffMap; + + // convert Number-s into ClLinearExpression-s + ClGenericLinearExpression(T num = 0.0); + + // Convert from ClVariable to a ClLinearExpression + // this replaces ClVariable::asLinearExpression + ClGenericLinearExpression(ClVariable clv, T value = 1.0, T constant = 0.0); + + // copy ctr + ClGenericLinearExpression(const ClGenericLinearExpression<T> &expr) : + _constant(expr._constant), + _terms(expr._terms) + { } + + virtual ~ClGenericLinearExpression(); + + // Return a new linear expression formed by multiplying self by x. + // (Note that this result must be linear.) + ClGenericLinearExpression<T> Times(Number x) const; + + // Return a new linear expression formed by multiplying self by x. + // (Note that this result must be linear.) + ClGenericLinearExpression<T> Times(const ClGenericLinearExpression<T> &expr) const; + + // Return a new linear expression formed by adding x to self. + ClGenericLinearExpression<T> Plus(const ClGenericLinearExpression<T> &expr) const; + + // Return a new linear expression formed by subtracting x from self. + ClGenericLinearExpression<T> Minus(const ClGenericLinearExpression<T> &expr) const; + + // Return a new linear expression formed by dividing self by x. + // (Note that this result must be linear.) + ClGenericLinearExpression<T> Divide(Number x) const; + + + + // Return a new linear expression formed by multiplying self by x. + // (Note that this result must be linear.) + ClGenericLinearExpression<T> *P_times(Number x) const + { return new ClGenericLinearExpression<T>(Times(x)); } + + // Return a new linear expression formed by adding x to self. + ClGenericLinearExpression<T> *P_plus(const ClGenericLinearExpression<T> &expr) const + { return new ClGenericLinearExpression<T>(Plus(expr)); } + + // Return a new linear expression formed by subtracting x from self. + ClGenericLinearExpression<T> *P_minus(const ClGenericLinearExpression<T> &expr) const + { return new ClGenericLinearExpression<T>(Minus(expr)); } + + // Return a new linear expression formed by dividing self by x. + // (Note that this result must be linear.) + ClGenericLinearExpression<T> *P_divide(Number x) const + { return new ClGenericLinearExpression<T>(Divide(x)); } + + // Return a new linear expression formed by dividing self by x. + // (Note that this result must be linear.) + ClGenericLinearExpression<T> Divide(const ClGenericLinearExpression<T> &expr) const; + + // Return a new linear expression (aNumber/this). Since the result + // must be linear, this is permissible only if 'this' is a constant. + ClGenericLinearExpression<T> DivFrom(const ClGenericLinearExpression<T> &expr) const; + + // Return a new linear expression (aNumber-this). + ClGenericLinearExpression<T> SubtractFrom(const ClGenericLinearExpression<T> &expr) const + { return expr.Minus(*this); } + + // Add n*expr to this expression from another expression expr. + ClGenericLinearExpression<T> &AddExpression(const ClGenericLinearExpression<T> &expr, + Number n = 1.0); + + // Add n*expr to this expression from another expression expr. + // Notify the solver if a variable is added or deleted from this + // expression. + ClGenericLinearExpression<T> &AddExpression(const ClGenericLinearExpression<T> &expr, Number n, + ClVariable subject, + ClTableau &solver); + + // 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. + ClGenericLinearExpression<T> &AddVariable(ClVariable v, T c = 1.0); + + // 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. + ClGenericLinearExpression<T> &setVariable(ClVariable v, T c) + {assert(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. + ClGenericLinearExpression<T> &AddVariable(ClVariable v, T c, + ClVariable subject, + ClTableau &solver); + + // Return a pivotable variable in this expression. (It is an error + // if this expression is constant -- signal ExCLInternalError in + // that case). Return NULL if no pivotable variables + ClVariable AnyPivotableVariable() const; + + // 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. + void SubstituteOut(ClVariable v, + const ClGenericLinearExpression<T> &expr, + ClVariable subject, + ClTableau &solver); + + // 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. + void ChangeSubject(ClVariable old_subject, + ClVariable new_subject); + + // 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 + // + // Note that the term involving subject has been dropped. + // Returns the reciprocal, so ChangeSubject can use it, too + T NewSubject(ClVariable subject); + + // Return the value of the linear expression + // given the current assignments of values to contained variables + T Evaluate() const; + + // Return the coefficient corresponding to variable var, i.e., + // the 'ci' corresponding to the 'vi' that var is: + // v1*c1 + v2*c2 + .. + vn*cn + c + T CoefficientFor(ClVariable var) const + { + typename ClVarToCoeffMap::const_iterator it = _terms.find(var); + if (it != _terms.end()) + return (*it).second; + return 0.0; + } + + T Constant() const + { return _constant; } + + void Set_constant(T c) + { _constant = c; } + + const ClVarToCoeffMap &Terms() const + { return _terms; } + + ClVarToCoeffMap &Terms() + { return _terms; } + + void IncrementConstant(T c) + { _constant += c; } + + bool IsConstant() const + { return _terms.size() == 0; } + +#ifndef CL_NO_IO + virtual ostream &PrintOn(ostream &xo) const; + + friend ostream &operator<<(ostream &xo,const ClGenericLinearExpression<T> &cle) + { return cle.PrintOn(xo); } +#endif + + friend ClGenericLinearExpression<T> operator+(const ClGenericLinearExpression<T> &e1, + const ClGenericLinearExpression<T> &e2) + { return e1.Plus(e2); } + + friend ClGenericLinearExpression<T> operator-(const ClGenericLinearExpression<T> &e1, + const ClGenericLinearExpression<T> &e2) + { return e1.Minus(e2); } + + friend ClGenericLinearExpression<T> operator*(const ClGenericLinearExpression<T> &e1, + const ClGenericLinearExpression<T> &e2) + { return e1.Times(e2); } + + + friend ClGenericLinearExpression<T> operator/(const ClGenericLinearExpression<T> &e1, + const ClGenericLinearExpression<T> &e2) + { return e1.Divide(e2); } + + // FIXGJB -- this may be wrong -- should test underlying expression for equality + friend bool operator==(const ClGenericLinearExpression<T> &e1, + const ClGenericLinearExpression<T> &e2) + { return &e1 == &e2; } + + /// Named versions of the operator functions for ease of + /// wrapping, or expressing using prefix notation + + friend ClGenericLinearExpression<T> Plus(const ClGenericLinearExpression<T> &e1, + const ClGenericLinearExpression<T> &e2) + { return e1.Plus(e2); } + + friend ClGenericLinearExpression<T> Minus(const ClGenericLinearExpression<T> &e1, + const ClGenericLinearExpression<T> &e2) + { return e1.Minus(e2); } + + friend ClGenericLinearExpression<T> Times(const ClGenericLinearExpression<T> &e1, + const ClGenericLinearExpression<T> &e2) + { return e1.Times(e2); } + + + friend ClGenericLinearExpression<T> *Divide(const ClGenericLinearExpression<T> &e1, + const ClGenericLinearExpression<T> &e2) + { return new ClGenericLinearExpression<T>(e1.Divide(e2)); } + + friend ClGenericLinearExpression<T> *p_Plus(const ClGenericLinearExpression<T> &e1, + const ClGenericLinearExpression<T> &e2) + { return new ClGenericLinearExpression<T>(e1.Plus(e2)); } + + friend ClGenericLinearExpression<T> *p_Minus(const ClGenericLinearExpression<T> &e1, + const ClGenericLinearExpression<T> &e2) + { return new ClGenericLinearExpression<T>(e1.Minus(e2)); } + + friend ClGenericLinearExpression<T> *p_Times(const ClGenericLinearExpression<T> &e1, + const ClGenericLinearExpression<T> &e2) + { return new ClGenericLinearExpression<T>(e1.Times(e2)); } + + friend ClGenericLinearExpression<T> *p_Divide(const ClGenericLinearExpression<T> &e1, + const ClGenericLinearExpression<T> &e2) + { return new ClGenericLinearExpression<T>(e1.Divide(e2)); } + + + // FIXGJB -- this may be wrong -- should test underlying expression for equality + friend bool FEquals(const ClGenericLinearExpression<T> &e1, + const ClGenericLinearExpression<T> &e2) + { return &e1 == &e2; } + + ClGenericLinearExpression<T> &MultiplyMe(T x); + + private: + + T _constant; + ClVarToCoeffMap _terms; + +}; + +typedef ClGenericLinearExpression<Number>::ClVarToCoeffMap ClVarToNumberMap; + +#endif diff --git a/libs/cassowary/cassowary/ClLinearExpression_fwd.h b/libs/cassowary/cassowary/ClLinearExpression_fwd.h new file mode 100644 index 0000000000..99b48557ec --- /dev/null +++ b/libs/cassowary/cassowary/ClLinearExpression_fwd.h @@ -0,0 +1,26 @@ +// $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.h + +#ifndef ClLinearExpression_fwd_H +#define ClLinearExpression_fwd_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 "Cassowary.h" + +template <class T> class ClGenericLinearExpression; +typedef ClGenericLinearExpression<Number> ClLinearExpression; +typedef ClLinearExpression* PClLinearExpression; + +#endif diff --git a/libs/cassowary/cassowary/ClLinearInequality.h b/libs/cassowary/cassowary/ClLinearInequality.h new file mode 100644 index 0000000000..017c4b819e --- /dev/null +++ b/libs/cassowary/cassowary/ClLinearInequality.h @@ -0,0 +1,167 @@ +// $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 +// +// ClLinearInequality.h + +#ifndef ClLinearInequality_H +#define ClLinearInequality_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 "ClConstraint.h" +#include "ClLinearConstraint.h" + +class ClVariable; + +class ClLinearInequality : public ClLinearConstraint { + private: typedef ClLinearConstraint super; + + public: + //// Constructors + // ClLinearInequality(expr,...) is expr >= 0 + ClLinearInequality(const ClLinearExpression &cle, + const ClStrength &strength = ClsRequired(), + double weight = 1.0) : + ClLinearConstraint(cle,strength, weight), + _fStrictInequality(false) + { } + + // ClLinearInequality(var,OP,expr) is var >= expr + ClLinearInequality(const ClVariable clv, + enum ClCnRelation op, + const ClLinearExpression &cle, + const ClStrength &strength = ClsRequired(), + double weight = 1.0) : + ClLinearConstraint( cle, strength, weight), + _fStrictInequality(false) + { + if (op == cnGEQ || op == cnGT) + { + _expression.MultiplyMe(-1.0); + _expression.AddVariable(clv,1.0); + } + else if (op == cnLEQ || op == cnGEQ) + { + _expression.AddVariable(clv,-1.0); + } + else + { + throw ExCLEditMisuse("Cannot use that operator for ClLinearInequality objects"); + } + if (op == cnLT || op == cnGT) { + _fStrictInequality = true; + } + } + +#ifdef FIXGJB_AMBIGUOUS + // ClLinearInequality(expr,OP,var) is var ?<>? expr + ClLinearInequality(const ClLinearExpression &cle, + enum ClCnRelation op, + const ClVariable clv, + const ClStrength &strength = ClsRequired(), + double weight = 1.0) : + ClLinearConstraint( cle, strength, weight), + _fStrictInequality(false) + { + if (op == cnLEQ || op == cnLT) + { + _expression.MultiplyMe(-1.0); + _expression.AddVariable(clv,1.0); + } + else if (op == cnGEQ || op == cnGT) + { + _expression.AddVariable(clv,-1.0); + } + if (op == cnLT || op == cnGT) { + _fStrictInequality = true; + } + } +#endif + + // ClLinearInequality(expr,OP,expr) is expr >= expr + ClLinearInequality(const ClLinearExpression &cle1, + enum ClCnRelation op, + const ClLinearExpression &cle2, + const ClStrength &strength = ClsRequired(), + double weight = 1.0) : + ClLinearConstraint( cle2, strength, weight), + _fStrictInequality(false) + { + if (op == cnGEQ || op == cnGT) + { + _expression.MultiplyMe(-1.0); + _expression.AddExpression(cle1); + } + else if (op == cnLEQ || op == cnLT) + { + _expression.AddExpression(cle1,-1.0); + } + if (op == cnLT || op == cnGT) { + _fStrictInequality = true; + } + } + +#ifdef FIXGJB_AMBIGUOUS + // ClLinearInequality(var,OP,var) is var ?<>? var + ClLinearInequality(const ClVariable clv1, + enum ClCnRelation op, + const ClVariable clv2, + const ClStrength &strength = ClsRequired(), + double weight = 1.0) : + ClLinearConstraint( clv2, strength, weight), + _fStrictInequality(false) + { + if (op == cnGEQ || op == cnGT) + { + _expression.MultiplyMe(-1.0); + _expression.AddVariable(clv1,1.0); + } + else if (op == cnLEQ || op == cnLT) + { + _expression.AddVariable(clv1,-1.0); + } + if (op == cnLT || op == cnGT) { + _fStrictInequality = true; + } + } +#endif + + + // Return true if this is an inequality constraint and + // false if it is an equality constraint. The default is + // that it is not. + virtual bool IsInequality() const + { return true; } + + virtual bool IsStrictInequality() const + { return _fStrictInequality; } + +#ifndef CL_NO_IO + virtual ostream &PrintOn(ostream &xo) const + { super::PrintOn(xo); xo << " >= 0 )"; return xo; } +#endif + + virtual bool FIsSatisfied() const + { + Number v = _expression.Evaluate(); + if (_fStrictInequality) + return (v > 0); + else + return (v >= 0); + } + + private: + + bool _fStrictInequality; +}; + +#endif diff --git a/libs/cassowary/cassowary/ClObjectiveVariable.h b/libs/cassowary/cassowary/ClObjectiveVariable.h new file mode 100644 index 0000000000..664e2d65a4 --- /dev/null +++ b/libs/cassowary/cassowary/ClObjectiveVariable.h @@ -0,0 +1,63 @@ +// $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 +// +// ClObjectiveVariable.h + +#ifndef ClObjectiveVariable_H +#define ClObjectiveVariable_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 "Cassowary.h" +#include "ClAbstractVariable.h" + +class ClTableau; +class ClSimplexSolver; + +class ClObjectiveVariable : public ClAbstractVariable { +protected: + friend class ClTableau; + friend class ClSimplexSolver; + + ClObjectiveVariable(string name = "") : + ClAbstractVariable(name) + { } + + ClObjectiveVariable(long number, char *prefix) : + ClAbstractVariable(number,prefix) + { } + +#ifndef CL_NO_IO + virtual ostream &PrintOn(ostream &xo) const + { + xo << "[" << Name() << ":obj]"; + return xo; + } +#endif + + // We don't need to give such variables a Value after solving is complete. + virtual bool IsExternal() const + { return false; } + + // Return true if we can Pivot on this variable. + virtual bool IsPivotable() const + { return false; } + + // Return true if this is a restricted (or slack) variable. Such + // variables are constrained to be non-negative and occur only + // internally to the simplex solver. + virtual bool IsRestricted() const + { return false; } + +}; + +#endif diff --git a/libs/cassowary/cassowary/ClPoint.h b/libs/cassowary/cassowary/ClPoint.h new file mode 100644 index 0000000000..15139aa73b --- /dev/null +++ b/libs/cassowary/cassowary/ClPoint.h @@ -0,0 +1,74 @@ +// $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 +// +// ClPoint.h + +#ifndef ClPoint_H +#define ClPoint_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 "Cassowary.h" +#include "ClVariable.h" + +// ClPoint is just a convenience class for pairs of +// ClVariables -- often useful for coordinate pairs in 2-space +class ClPoint { + public: + ClPoint(Number x, Number y) + : _clv_x(x), _clv_y(y) + { } + + ClPoint() + { } + + ClVariable X() + { return _clv_x; } + + ClVariable Y() + { return _clv_y; } + + const ClVariable X() const + { return _clv_x; } + + const ClVariable Y() const + { return _clv_y; } + + void SetXY(Number x, Number y) + { _clv_x.SetValue(x); _clv_y.SetValue(y); } + + Number Xvalue() const + { return X().Value(); } + + Number Yvalue() const + { return Y().Value(); } + + private: + ClVariable _clv_x; + ClVariable _clv_y; + +#ifndef CL_NO_IO + friend ostream &operator<<(ostream &xo, const ClPoint &clp); +#endif + +}; + +#ifndef CL_NO_IO +inline ostream & +operator<<(ostream &xo, const ClPoint &clp) +{ + xo << "(" << clp._clv_x << ", " << clp._clv_y << ")"; + return xo; +} +#endif + +#endif diff --git a/libs/cassowary/cassowary/ClReader.h b/libs/cassowary/cassowary/ClReader.h new file mode 100644 index 0000000000..59369d6ac2 --- /dev/null +++ b/libs/cassowary/cassowary/ClReader.h @@ -0,0 +1,117 @@ +// $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 +// +// ClReader.h +// Original implementation contributed by Steve Wolfman +// Subsequently largely revised by Greg J. Badros + +#ifndef CREADER_H +#define CREADER_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 <string> +#include <map> +#include <algorithm> +#include <iostream> +#include "ClErrors.h" +#include "ClVariable.h" +#include "ClStrength.h" +#include "ClLinearExpression_fwd.h" + +using std::string; +using std::istream; + +class ClConstraint; + +class ClVarLookupFunction : public std::unary_function<const string &,ClVariable *> { +public: + virtual ClVariable *operator()(const string &) const { return &clvNil; } +}; + + +// Attempts to read a constraint of input stream in +// Returns constraint (freshly allocated, client responsibility to deallocate) +// if succesful. Otherwise, returns 0. +ClConstraint *PcnParseConstraint(istream &xi, const ClVarLookupFunction &lookup_func, + const ClStrength &strength = ClsRequired()); + +class ClVarLookupInMap : public ClVarLookupFunction { +public: + ClVarLookupInMap(StringToVarMap *pmapVars, bool fAutoCreate) + : _pmapVars(pmapVars), _fAutoCreate(fAutoCreate) { } + + ClVariable *operator()(const string &str) const + { + if (!_pmapVars) + return &clvNil; + StringToVarMap &_mapVars = *_pmapVars; + StringToVarMap::iterator it = _mapVars.find(str); + if (it != _mapVars.end()) { + return &it->second; + } else if (_fAutoCreate) { + // save the old symbol table, if any + StringToVarMap *pmapOld = ClVariable::VarMap(); + // and set it to this one temporarily + ClVariable::SetVarMap(&_mapVars); + ClVariable *pclv = new ClVariable(str); + // now switch it back + ClVariable::SetVarMap(pmapOld); + return pclv; + } else { + return &clvNil; + } + } +private: + StringToVarMap *_pmapVars; + bool _fAutoCreate; +}; + + +/* the "yyerror" function */ +void clerror(const char *sz); + +struct ClParseData { + ClParseData(istream &xi, const ClVarLookupFunction &lookup_func) + : _xi(xi), _lookup_func(lookup_func) { } + + ClConstraint *Pcn() { return _pcn; } + + ClVarSet _readOnlyVarsSoFar; + + istream & _xi; + ClConstraint * _pcn; + const ClVarLookupFunction &_lookup_func; +}; + + +inline +const ClStrength +&ClsFromSz(const char *sz) +{ + const ClStrength *pcls = &ClsRequired(); + double n1, n2, n3; + if (strcmp("required",sz) == 0) + ; /* initialized to ClsRequired, above */ + else if (strcasecmp("strong",sz) == 0) { pcls = &ClsStrong(); } + else if (strcasecmp("medium",sz) == 0) { pcls = &ClsMedium(); } + else if (strcasecmp("weak",sz) == 0) { pcls = &ClsWeak(); } + else if (sscanf(sz,"(%lf,%lf,%lf)",&n1,&n2,&n3) == 3) { + pcls = new ClStrength("parsed",n1,n2,n3); + } else { + throw ExCLParseErrorMisc("Error parsing strength"); + } + return *pcls; +} + + +#endif 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 diff --git a/libs/cassowary/cassowary/ClSlackVariable.h b/libs/cassowary/cassowary/ClSlackVariable.h new file mode 100644 index 0000000000..ca116702e9 --- /dev/null +++ b/libs/cassowary/cassowary/ClSlackVariable.h @@ -0,0 +1,75 @@ +// $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 +// +// ClSlackVariable.h + +#ifndef ClSlackVariable_H +#define ClSlackVariable_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 "Cassowary.h" +#include "ClAbstractVariable.h" + +class ClTableau; +class ClSimplexSolver; + + +class ClSlackVariable : public ClAbstractVariable { +public: +#ifdef CL_FIND_LEAK + ~ClSlackVariable() { --cSlackVariables; }; + + static long cSlackVariables; +#endif + +protected: + friend class ClTableau; + friend class ClSimplexSolver; + + ClSlackVariable(string Name = "") : + ClAbstractVariable(Name) + { +#ifdef CL_FIND_LEAK + ++cSlackVariables; +#endif + } + + ClSlackVariable(long number, char *prefix) : + ClAbstractVariable(number,prefix) + { +#ifdef CL_FIND_LEAK + ++cSlackVariables; +#endif + } + +#ifndef CL_NO_IO + virtual ostream &PrintOn(ostream &xo) const + { + xo << "[" << Name() << ":slack]"; + return xo; + } +#endif + + virtual bool IsExternal() const + { return false; } + + virtual bool IsPivotable() const + { return true; } + + virtual bool IsRestricted() const + { return true; } + +}; + + +#endif diff --git a/libs/cassowary/cassowary/ClSolver.h b/libs/cassowary/cassowary/ClSolver.h new file mode 100644 index 0000000000..16e798d491 --- /dev/null +++ b/libs/cassowary/cassowary/ClSolver.h @@ -0,0 +1,167 @@ +// $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 +// +// ClSolver.h + +#ifndef ClSolver_H +#define ClSolver_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 "Cassowary.h" +#include "ClErrors.h" +#include "ClTypedefs.h" +#include <list> +#include <iostream> + +using std::list; +using std::ostream; + +class ClVariable; + +// ClSolver is an abstract base class +class ClSolver { + public: + + ClSolver() : _pv(0), _fAutosolve(true), _pfnChangeClvCallback(0) { } + + virtual ~ClSolver() + { } + + // Add the constraint cn to the solver + virtual ClSolver &AddConstraint(ClConstraint *const pcn) = 0; + + // Remove the constraint cn from the solver + virtual ClSolver &RemoveConstraint(ClConstraint *const pcn) = 0; + + // Same as above, but returns false if the constraint cannot be solved + // (i.e., the resulting system would be unsatisfiable) + // The above function "AddConstraint" throws an exception in that case + // which may be inconvenient + virtual bool AddConstraintNoException(ClConstraint *const pcn) + { + try { + AddConstraint(pcn); + return true; + } + catch (const ExCLRequiredFailure &e) + { return false; } + catch (const ExCLTooDifficult &e) + { return false; } + } + +#ifndef CL_NO_DEPRECATED + // Deprecated --02/22/99 gjb + bool AddConstraintNoException(ClConstraint &cn) + { return AddConstraintNoException(&cn); } +#endif + + virtual bool RemoveConstraintNoException(ClConstraint *const pcn) + { + try { + RemoveConstraint(pcn); + return true; + } + catch (const ExCLConstraintNotFound &e) + { return false; } + } + +#ifndef CL_NO_DEPRECATED + // Deprecated --02/22/99 gjb + bool RemoveConstraintNoException(ClConstraint &cn) + { return RemoveConstraintNoException(&cn); } +#endif + + + virtual ClSolver &Solve() + { assert(false); return *this; } + + virtual bool SolveNoException() + { + try { + Solve(); + return true; + } + catch (const ExCLTooDifficult &e) + { return false; } + catch (const ExCLRequiredFailure &e) + { return false; } + } + + + virtual void Resolve() + { assert(false); } + + void SetPv(void *pv) + { _pv = pv; } + + void *Pv() const + { return _pv; } + + typedef void (*PfnChangeClvCallback)(ClVariable *pclv, ClSolver *psolver); + + void SetChangeClvCallback(PfnChangeClvCallback pfn) + { _pfnChangeClvCallback = pfn; } + + // Control whether optimization and setting of external variables + // is done automatically or not. By default it is done + // automatically and solve() never needs to be explicitly + // called by client code; if SetAutosolve is put to false, + // then solve() needs to be invoked explicitly before using + // variables' values + // (Turning off autosolve while adding lots and lots of + // constraints [ala the addDel test in ClTests] saved + // about 20% in runtime, from 68sec to 54sec for 900 constraints, + // with 126 failed adds) + ClSolver &SetAutosolve(bool f) + { _fAutosolve = f; if (f) Solve(); return *this; } + + // Tell whether we are autosolving + bool FIsAutosolving() const + { return _fAutosolve; } + + +#ifndef CL_NO_IO + friend ostream &operator<<(ostream &xo, const ClSolver &solver); + + virtual ostream &PrintOn(ostream &xo) const = 0; + +#endif + + protected: + + // C-style extension mechanism so I + // don't have to wrap ScwmClSolver separately + void *_pv; + + bool _fAutosolve; + + PfnChangeClvCallback _pfnChangeClvCallback; +}; + + +#ifndef CL_NO_IO +ostream &PrintTo(ostream &xo, const ClVarVector &varlist); +ostream &operator<<(ostream &xo, const ClVarVector &varlist); + +ostream &PrintTo(ostream &xo, const ClConstraintToVarSetMap &mapCnToVarSet); +ostream &operator<<(ostream &xo, const ClConstraintToVarSetMap &mapCnToVarSet); + +ostream &PrintTo(ostream &xo, const ClConstraintSet &setCn); +ostream &operator<<(ostream &xo, const ClConstraintSet &setCn); + +ostream &PrintTo(ostream &xo, const list<FDNumber> &listFDN); +ostream &operator<<(ostream &xo, const list<FDNumber> &listFDN); + +#endif + +#endif diff --git a/libs/cassowary/cassowary/ClStayConstraint.h b/libs/cassowary/cassowary/ClStayConstraint.h new file mode 100644 index 0000000000..f009731b09 --- /dev/null +++ b/libs/cassowary/cassowary/ClStayConstraint.h @@ -0,0 +1,43 @@ +// $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 +// +// ClStayConstraint.h + +#ifndef ClStayConstraint_H +#define ClStayConstraint_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 "Cassowary.h" +#include "ClEditOrStayConstraint.h" + +class ClStayConstraint : public ClEditOrStayConstraint { + typedef ClEditOrStayConstraint super; + public: + + ClStayConstraint(const ClVariable var, + const ClStrength &strength = ClsWeak(), double weight = 1.0 ) : + ClEditOrStayConstraint(var,strength,weight) + { } + + virtual bool isStayConstraint() const + { return true; } + +#ifndef CL_NO_IO + virtual ostream &PrintOn(ostream &xo) const + { super::PrintOn(xo); return xo << " STAY)"; } +#endif + + private: +}; + +#endif diff --git a/libs/cassowary/cassowary/ClStrength.h b/libs/cassowary/cassowary/ClStrength.h new file mode 100644 index 0000000000..644c04cb5f --- /dev/null +++ b/libs/cassowary/cassowary/ClStrength.h @@ -0,0 +1,91 @@ +// $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 +// +// ClStrength.h + +#ifndef ClStrength_H +#define ClStrength_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 <string> + +#include "Cassowary.h" +#include "ClSymbolicWeight.h" + +using std::string; + +class ClStrength; + +const ClStrength &ClsRequired(); +const ClStrength &ClsStrong(); +const ClStrength &ClsMedium(); +const ClStrength &ClsWeak(); + +class ClStrength { + public: + + ClStrength(const string &Name, const ClSymbolicWeight &symbolicWeight) : + _name(Name), _symbolicWeight(symbolicWeight) + { } + + // special case for when nLevels = 3, should assert nLevels() == 3 + ClStrength(const string &Name, double w1, double w2, double w3); + + virtual ~ClStrength() + { } + + virtual bool IsRequired() const + { return (_symbolicWeight == ClsRequired()._symbolicWeight); } + +#ifndef CL_NO_IO + virtual ostream &PrintOn(ostream &xo) const + { + xo << Name(); + if (!IsRequired()) + xo << ":" << symbolicWeight(); + return xo; + } + + friend ostream& operator<<(ostream &xos, const ClStrength &Cls) + { Cls.PrintOn(xos); return xos; } + +#endif + + virtual const ClSymbolicWeight &symbolicWeight() const + { return _symbolicWeight; } + + void SetPv(void *pv) + { _pv = pv; } + + void *Pv() const + { return _pv; } + + private: + string Name() const + { return _name; } + + void SetName(string Name) + { _name = Name; } + + void SetSymbolicWeight(const ClSymbolicWeight &symbolicWeight) + { _symbolicWeight = symbolicWeight; } + + // instance variables + string _name; + ClSymbolicWeight _symbolicWeight; + + void *_pv; + +}; + +#endif diff --git a/libs/cassowary/cassowary/ClSymbolicWeight.h b/libs/cassowary/cassowary/ClSymbolicWeight.h new file mode 100644 index 0000000000..1c0339c887 --- /dev/null +++ b/libs/cassowary/cassowary/ClSymbolicWeight.h @@ -0,0 +1,197 @@ +// $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 +// +// ClSymbolicWeight.h + +#ifndef ClSymbolicWeight_H +#define ClSymbolicWeight_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 "Cassowary.h" +#include "ClErrors.h" +#include <vector> +#include <iostream> + +using std::vector; +using std::ostream; + +class ClSymbolicWeight { + public: + ClSymbolicWeight(unsigned int CLevels = 3, Number value = 0.0); + + ClSymbolicWeight(Number w1, Number w2, Number w3); + + ClSymbolicWeight(const vector<Number> &weights); + + static ClSymbolicWeight &Zero(); + + ClSymbolicWeight &negated(); + + ClSymbolicWeight &MultiplyMe(Number n); + + ClSymbolicWeight Times(Number n) const + { ClSymbolicWeight cl = *this; cl.MultiplyMe(n); return cl; } + + ClSymbolicWeight DivideBy(Number n) const; + + ClSymbolicWeight &addtoMe(const ClSymbolicWeight &cl); + + ClSymbolicWeight Add(const ClSymbolicWeight &cl) const + { ClSymbolicWeight clRet = *this; clRet.addtoMe(cl); return clRet; } + + ClSymbolicWeight Subtract(const ClSymbolicWeight &cl) const; + + ClSymbolicWeight operator*(const Number &n) const + { return Times(n); } + + ClSymbolicWeight operator/(const Number &n) const + { return DivideBy(n); } + + // FIXGJB: can we express this statically? + ClSymbolicWeight operator*(ClSymbolicWeight &w) const + { throw ExCLInternalError("Multiplication of symbolic weights encountered"); + return w; } + ClSymbolicWeight &operator*=(ClSymbolicWeight &w) + { throw ExCLInternalError("Multiplicative assignment of symbolic weights encountered"); + return w; } + + // FIXGJB: can we express this statically? + ClSymbolicWeight operator-() const + { throw ExCLInternalError("Can not negate a symbolic weight"); + return ClSymbolicWeight::Zero(); } + + friend ClSymbolicWeight ReciprocalOf(const ClSymbolicWeight &); + + ClSymbolicWeight &operator*=(const Number &n) + { return MultiplyMe(n); } + + ClSymbolicWeight operator+(const ClSymbolicWeight &cl) const + { return Add(cl); } + + ClSymbolicWeight operator+=(const ClSymbolicWeight &cl) + { return addtoMe(cl); } + + ClSymbolicWeight operator*(const Number &n) + { ClSymbolicWeight answer(*this); + answer *= n; + return answer; } + + bool lessThan(const ClSymbolicWeight &cl) const; + bool lessThanOrEqual(const ClSymbolicWeight &cl) const; + bool equal(const ClSymbolicWeight &cl) const; + bool greaterThan(const ClSymbolicWeight &cl) const; + bool greaterThanOrEqual(const ClSymbolicWeight &cl) const; + bool isNegative() const; + + friend bool operator==(const ClSymbolicWeight &cl1, const ClSymbolicWeight &cl2) + { return cl1.equal(cl2); } + + friend bool operator!=(const ClSymbolicWeight &cl1, const ClSymbolicWeight &cl2) + { return !(cl1 == cl2); } + + friend bool operator<(const ClSymbolicWeight &cl1, const ClSymbolicWeight &cl2) + { return cl1.lessThan(cl2); } + + friend bool operator>(const ClSymbolicWeight &cl1, const ClSymbolicWeight &cl2) + { return (cl2 < cl1); } + + // function.h provides operator>, >=, <= from operator< + + double AsDouble() const + { + vector<Number>::const_reverse_iterator i = _values.rbegin(); + Number sum = 0; + Number factor = 1; + // A. Beurive' Wed Jul 7 11:07:47 CEST 1999 + Number multiplier = 1000000; + for ( ; i != _values.rend(); ++i) + { + sum += *i * factor; + factor *= multiplier; + } + return sum; + } + +#ifndef CL_NO_IO + ostream &PrintOn(ostream &xo) const + { + vector<Number>::const_iterator i = _values.begin(); + if (i == _values.end()) + return xo; + + xo << *i; + for (++i; i != _values.end(); ++i) + { + xo << "," << *i; + } + return xo; + } + + // FIXGJB: use a template function to generate these automatically + friend ostream& operator<<(ostream &xos, const ClSymbolicWeight &clsw) + { clsw.PrintOn(xos); return xos; } +#endif + + int CLevels() const + { return _values.size(); } + + friend bool ClApprox(const ClSymbolicWeight &cl, Number n); + friend bool ClApprox(const ClSymbolicWeight &cl1, const ClSymbolicWeight &cl2); + + private: + vector<Number> _values; + + void push_back(Number d) + { _values.push_back(d); } + +}; + +inline bool ClApprox(const ClSymbolicWeight &cl, Number n) +{ + vector<Number>::const_iterator it = cl._values.begin(); + if (!ClApprox(*it,n)) + return false; + + ++it; + for (; it != cl._values.end(); ++it) + { + if (!ClApprox(*it,0)) + return false; + } + + return true; +} + +inline bool ClApprox(const ClSymbolicWeight &cl1, const ClSymbolicWeight &cl2) +{ + vector<Number>::const_iterator it1 = cl1._values.begin(); + vector<Number>::const_iterator it2 = cl2._values.begin(); + + for (; it1 != cl1._values.end() && it2 != cl2._values.end(); + ++it1, ++it2) + { + if (!ClApprox(*it1,*it2)) + return false; + } + + if (it1 == cl1._values.end() && it2 == cl2._values.end()) + return true; + + return false; +} + +inline ClSymbolicWeight ReciprocalOf(const ClSymbolicWeight &) +{ throw(ExCLInternalError("Cannot take ReciprocalOf symbolic weight")); + return ClSymbolicWeight::Zero(); } + +#endif diff --git a/libs/cassowary/cassowary/ClTableau.h b/libs/cassowary/cassowary/ClTableau.h new file mode 100644 index 0000000000..117ed0fb9d --- /dev/null +++ b/libs/cassowary/cassowary/ClTableau.h @@ -0,0 +1,230 @@ +// $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 +// +// ClTableau.h + +#ifndef ClTableau_H +#define ClTableau_H + +#include <iostream> + +#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 "Cassowary.h" +#include "ClLinearExpression.h" +#include "ClVariable.h" +#include "ClTypedefs.h" + + +#ifndef CL_NO_IO +class ClTableau; + +ostream &operator<<(ostream &xo, const ClTableau &clt); + +ostream &operator<<(ostream &xo, const ClVarSet &varset); + +ostream &operator<<(ostream &xo, const ClTableauColumnsMap &varmap); + +ostream &operator<<(ostream &xo, const ClTableauRowsMap &rows); + +ostream &operator<<(ostream &xo, const ClVarVector &varlist); +#endif // CL_NO_IO + +class ClTableau { + + public: + // No public constructor, since this does nothing but support + // an ADT for the ClSimplexSolver + + // Variable v has been removed from an Expression. If the + // Expression is in a tableau the corresponding basic variable is + // subject (or if subject is nil then it's in the objective function). + // Update the column cross-indices. + void NoteRemovedVariable(ClVariable v, ClVariable subject) + { +#ifdef CL_TRACE + Tracer TRACER(__FUNCTION__); + std::cerr << "(" << v << ", " << subject << ")" << std::endl; +#endif + ClVarSet &column = _columns[v]; + ClVarSet::const_iterator it = column.find(subject); + assert(it != column.end()); + column.erase(it); +#ifdef CL_TRACE_VERBOSE + std::cerr << "v = " << v << " and Columns[v].size() = " + << column.size() << std::endl; +#endif + if (column.size() == 0) + { + _columns.erase(v); + _externalRows.erase(v); + _externalParametricVars.erase(v); + } + } + + // v has been added to the linear Expression for subject + // update column cross indices + void NoteAddedVariable(ClVariable v, ClVariable subject) + { +#ifdef CL_TRACE + Tracer TRACER(__FUNCTION__); + std::cerr << "(" << v << ", " << subject << ")" << std::endl; +#endif + _columns[v].insert(subject); + if (v.IsExternal() && !FIsBasicVar(v)) + { + _externalParametricVars.insert(v); + } + } + +#ifndef CL_NO_IO + std::ostream &PrintOn(ostream &xo) const; + + ostream &PrintInternalInfo(ostream &xo) const; + + ostream &printExternalVariablesTo(ostream &xo) const; + +#endif + + // Check integrity of the tableau + // not complete, yet, but a start, at least + // Guard calls to AssertValid with CL_SOLVER_CHECK_INTEGRITY, + // since this is expensive + virtual void AssertValid() const { +#ifndef NDEBUG + // all external basic variables are in _externalRows + // and all external parametric variables are in _externalParametricVars + ClTableauRowsMap::const_iterator itRow = _rows.begin(); + for (; itRow != _rows.end(); ++itRow) + { + const ClVariable clv = (*itRow).first; + if (clv.IsExternal()) + { + if (_externalRows.find(clv) == _externalRows.end()) + { +#ifndef CL_NO_IO + std::cerr << "External basic variable " << clv + << " is not in _externalRows" << std::endl; +#endif + } + } + const ClLinearExpression *pcle = RowExpression(clv); + assert(pcle); + ClVarToNumberMap::const_iterator it = pcle->Terms().begin(); + for (; it != pcle->Terms().end(); ++it) + { + ClVariable clv = (*it).first; + if (clv.IsExternal()) + { + if (_externalParametricVars.find(clv) == _externalParametricVars.end()) + { +#ifndef CL_NO_IO + std::cerr << "External parametric variable " << clv + << " is not in _externalParametricVars" << std::endl; +#endif + } + } + } + } +#endif /* !NDEBUG */ + } + + + protected: + // Constructor -- want to start with empty objects so not much to do + ClTableau() + { } + + virtual ~ClTableau(); + + // Add v=expr to the tableau, update column cross indices + // v becomes a basic variable + // expr is now owned by ClTableau class, + // and ClTableauis responsible for deleting it + // (also, expr better be allocated on the heap!) + void addRow(ClVariable v, const ClLinearExpression &expr); + + // Remove v from the tableau -- remove the column cross indices for v + // and remove v from every Expression in rows in which v occurs + // returns a pointer to the variable (since we often want to delete + // the variable) + ClVariable RemoveColumn(ClVariable v); + + // Remove the basic variable v from the tableau row v=expr + // Then update column cross indices + // Probably want to call delete on the ClLinearExpression * returned + // unless you're adding that same Expression back into the + // tableau + ClLinearExpression *RemoveRow(ClVariable v); + + // Replace all occurrences of oldVar with expr, and update column cross indices + // oldVar should now be a basic variable + void SubstituteOut(ClVariable oldVar, const ClLinearExpression &expr); + + ClTableauColumnsMap Columns() + { return _columns; } + + ClTableauRowsMap Rows() + { return _rows; } + + // return true iff the variable subject is in the Columns keys + bool ColumnsHasKey(ClVariable subject) const + { + ClTableauColumnsMap::const_iterator i = _columns.find(subject); + return (i != _columns.end()); + } + + const ClLinearExpression *RowExpression(ClVariable v) const + { + ClTableauRowsMap::const_iterator i = _rows.find(v); + if (i != _rows.end()) + return (*i).second; + else + return 0; + } + + ClLinearExpression *RowExpression(ClVariable v) + { + const ClTableau *pthis = const_cast<const ClTableau *>(this); + return const_cast<ClLinearExpression *>(pthis->RowExpression(v)); + } + + + bool FIsBasicVar(ClVariable v) + { return RowExpression(v) != 0; } + + // private: FIXGJB: can I improve the encapsulation? + + // _columns is a mapping from variables which occur in expressions to the + // set of basic variables whose expressions contain them + // i.e., it's a mapping from variables in expressions (a column) to the + // set of rows that contain them + ClTableauColumnsMap _columns; + + // _rows maps basic variables to the expressions for that row in the tableau + ClTableauRowsMap _rows; + + // the collection of basic variables that have infeasible rows + // (used when reoptimizing) + ClVarSet _infeasibleRows; + + // the set of rows where the basic variable is external + // this was added to the C++ version to reduce time in SetExternalVariables() + ClVarSet _externalRows; + + // the set of external variables which are parametric + // this was added to the C++ version to reduce time in SetExternalVariables() + ClVarSet _externalParametricVars; + +}; + +#endif diff --git a/libs/cassowary/cassowary/ClTypedefs.h b/libs/cassowary/cassowary/ClTypedefs.h new file mode 100644 index 0000000000..74b625a72b --- /dev/null +++ b/libs/cassowary/cassowary/ClTypedefs.h @@ -0,0 +1,48 @@ +// $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 +// +// ClTypedefs.h + +#ifndef CL_TYPEDEFS_H__ +#define CL_TYPEDEFS_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 "ClLinearExpression_fwd.h" +#include <set> +#include <map> +#include <vector> + +using std::set; +using std::map; +using std::vector; + +class ClVariable; +class ClConstraint; +class ClEditInfo; + +typedef set<ClVariable> ClVarSet; +typedef map<ClVariable, ClVarSet > ClTableauColumnsMap; +typedef map<ClVariable, ClLinearExpression *> ClTableauRowsMap; + +// For Solver +typedef map<const ClConstraint *, ClVarSet> ClConstraintToVarSetMap; +typedef map<const ClConstraint *, ClVariable> ClConstraintToVarMap; +typedef map<ClVariable, const ClConstraint *> ClVarToConstraintMap; +typedef vector<ClVariable> ClVarVector; + +typedef set<const ClConstraint *> ClConstraintSet; + +// For FDSolver +typedef map<ClVariable, ClConstraintSet> ClVarToConstraintSetMap; + +#endif diff --git a/libs/cassowary/cassowary/ClVariable.h b/libs/cassowary/cassowary/ClVariable.h new file mode 100644 index 0000000000..03814e5ef2 --- /dev/null +++ b/libs/cassowary/cassowary/ClVariable.h @@ -0,0 +1,166 @@ +// $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 +// +// ClVariable.h +// A handle on ClAbstractVariable-s + +#ifndef ClVariable_H +#define ClVariable_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 <cstdio> +#include <map> +#include <string> +#include "Cassowary.h" +#include "ClFloatVariable.h" +#include "ClFDVariable.h" + +using std::map; +using std::string; + +class ClVariable; +typedef map<const string,ClVariable> StringToVarMap; + + +class ClVariable { + ClAbstractVariable *pclv; +public: + // converters from raw ClAbstractVariable + ClVariable(ClAbstractVariable *pclv_) : pclv(pclv_) { } + ClVariable(ClAbstractVariable &clv_) : pclv(&clv_) { } + + // Copy ctr + ClVariable(const ClVariable &clv_) : pclv(clv_.pclv) { } + + /// These ctrs build ClFloatVariable-s + ClVariable(string name, Number Value = 0.0) + : pclv(new ClFloatVariable(name,Value)) + { if (pmapStrPclv) { (*pmapStrPclv)[name] = *this; } } + ClVariable(Number Value = 0.0) + : pclv(new ClFloatVariable(Value)) { } + ClVariable(long number, char *prefix, Number Value = 0.0) + : pclv(new ClFloatVariable(number,prefix,Value)) { } + + // This one builds a ClFDVariable + ClVariable(ClFDVariable *pcfv) + : pclv(pcfv) + { if (pmapStrPclv) { (*pmapStrPclv)[pcfv->Name()] = *this; } } + + /// permit ClVariables to be used as pointers to pclvs + ClAbstractVariable *operator->() { return pclv; } + const ClAbstractVariable *operator->() const { return pclv; } + + /// and also forward the function calls along + + + bool IsFloatVariable() const { assert(pclv); return pclv->IsFloatVariable(); } + bool IsFDVariable() const { assert(pclv); return pclv->IsFDVariable(); } + bool IsDummy() const { assert(pclv); return pclv->IsDummy(); } + bool IsExternal() const { assert(pclv); return pclv->IsExternal(); } + bool IsPivotable() const { assert(pclv); return pclv->IsPivotable(); } + bool IsRestricted() const { assert(pclv); return pclv->IsRestricted(); } + + string Name() const { assert(pclv); return pclv->Name(); } + + Number Value() const { assert(pclv); return pclv->Value(); } + int IntValue() const { assert(pclv); return pclv->IntValue(); } + void SetValue(Number Value) + { assert(pclv); pclv->SetValue(Value); } + void ChangeValue(Number Value) + { assert(pclv); pclv->ChangeValue(Value); } + void SetPv(void *pv) + { assert(pclv); pclv->SetPv(pv); } + void *Pv() const + { assert(pclv); return pclv->Pv(); } + + void SetName(string const &nm) { + assert(pclv); + if (pmapStrPclv) { + pmapStrPclv->erase(Name()); + (*pmapStrPclv)[nm] = *this; + } + pclv->SetName(nm); + } + + ClAbstractVariable *get_pclv() const { return pclv; } + bool IsNil() const { return pclv == 0; } + + virtual FDNumber DesiredValue() const + { assert(false); } + + virtual list<FDNumber> *PlfdnDomain() + { assert(false); return 0; } + + static void SetVarMap(StringToVarMap *pmap) { pmapStrPclv = pmap; } + static StringToVarMap *VarMap() { return pmapStrPclv; } + static StringToVarMap *pmapStrPclv; +#ifndef CL_NO_IO + ostream &PrintOn(ostream &xo) const + { + if (pclv) return pclv->PrintOn(xo); /* return xo << "@" << pclv << endl; */ + return xo << "clvNil"; + } +#endif + + friend bool operator<(ClVariable cl1, ClVariable cl2) + { return cl1.pclv < cl2.pclv; } + + friend bool operator==(ClVariable cl1, ClVariable cl2) + { return cl1.pclv == cl2.pclv; } + + friend bool operator!=(ClVariable cl1, ClVariable cl2) + { return !(cl1 == cl2); } + +}; + +#ifndef CL_NO_IO +inline ostream &operator<<(ostream &xo, const ClVariable &clv) +{ return clv.PrintOn(xo); } +#endif + +#ifdef CL_USE_HASH_MAP_AND_SET +struct hash<ClVariable> { + size_t operator()(const ClVariable & v) const + { return size_t((unsigned long)v.get_pclv()/CL_PTR_HASH_DIVISOR); } +}; +#endif + + +#include <math.h> + +// Compare two double-s approximately, since equality is no good +inline bool ClApprox(double a, double b) +{ + const double epsilon = 1.0e-8; + if (a > b) { + return (a - b) < epsilon; + } else { + return (b - a) < epsilon; + } +} + +// Can remove these if I decide to +// autoconvert from ClVariable-s to double-s +inline bool ClApprox(ClVariable clv, double b) +{ + return ClApprox(clv->Value(),b); +} + +inline bool ClApprox(double a, ClVariable clv) +{ + return ClApprox(a,clv->Value()); +} + +extern ClVariable clvNil; + +#endif diff --git a/libs/cassowary/cassowary/Makefile.am b/libs/cassowary/cassowary/Makefile.am new file mode 100644 index 0000000000..cc581b80ff --- /dev/null +++ b/libs/cassowary/cassowary/Makefile.am @@ -0,0 +1,36 @@ +MAINTAINERCLEANFILES = autom4te.cache Makefile.in + +noinst_HEADERS = \ + Cassowary.h \ + ClAbstractVariable.h \ + ClDummyVariable.h \ + ClObjectiveVariable.h \ + ClSlackVariable.h \ + ClConstraint.h \ + ClConstraintHash.h \ + ClEditConstraint.h \ + ClEditOrStayConstraint.h \ + ClErrors.h \ + ClLinearConstraint.h \ + ClLinearEquation.h \ + ClLinearExpression.h \ + ClLinearExpression_fwd.h \ + ClLinearInequality.h \ + ClSolver.h \ + ClSimplexSolver.h \ + ClStayConstraint.h \ + ClStrength.h \ + ClSymbolicWeight.h \ + ClTableau.h \ + ClFDVariable.h \ + ClFDConnectorVariable.h \ + ClFloatVariable.h \ + ClVariable.h \ + ClReader.h \ + ClTypedefs.h \ + ClPoint.h \ + cl_auto_ptr.h \ + config-inline.h \ + debug.h \ + timer.h + diff --git a/libs/cassowary/cassowary/cl_auto_ptr.h b/libs/cassowary/cassowary/cl_auto_ptr.h new file mode 100644 index 0000000000..3c37429676 --- /dev/null +++ b/libs/cassowary/cassowary/cl_auto_ptr.h @@ -0,0 +1,69 @@ +// $Id$ +// See http://cseng.aw.com/bookdetail.qry?ISBN=0-201-63371-X&ptype=634 +// auto_ptr from More Effective C++ an earlier appendix (works w/ egcs) + + +#ifndef CL_AUTO_PTR_H +#define CL_AUTO_PTR_H + +#ifdef _MSC_VER +#include <memory> +template<class T> +void ReinitializeAutoPtr(auto_ptr<T> &apref, T *pt) +{ + auto_ptr<T> ap(pt); + apref = ap; +} +#define cl_auto_ptr auto_ptr +#else +// FIXGJB: This implementation for egcs is buggy -- be careful +// and replace ASAP +template<class T> +class cl_auto_ptr { + public: + explicit cl_auto_ptr(T *p = 0): pointee(p) {} + + template<class U> + cl_auto_ptr(cl_auto_ptr<U>& rhs): pointee(rhs.release()) {} + + ~cl_auto_ptr() { delete pointee; } + + template<class U> + cl_auto_ptr<T>& operator=(cl_auto_ptr<U>& rhs) + { + if (this != &rhs) reset(rhs.release()); + return *this; + } + + T& operator*() const { return *pointee; } + + T* operator->() const { return pointee; } + + T* get() const { return pointee; } + + T* release() + { + T *oldPointee = pointee; + pointee = 0; + return oldPointee; + } + + // protected: + // This is non-standard + void reset(T *p = 0) { delete pointee; pointee = p; } + + private: + T *pointee; +}; + +template<class T> +void ReinitializeAutoPtr(cl_auto_ptr<T> &apref, T *pt) +{ + apref.reset(pt); +} + + +#endif + + +#endif diff --git a/libs/cassowary/cassowary/config-inline.h b/libs/cassowary/cassowary/config-inline.h new file mode 100644 index 0000000000..8b13789179 --- /dev/null +++ b/libs/cassowary/cassowary/config-inline.h @@ -0,0 +1 @@ + diff --git a/libs/cassowary/cassowary/debug.h b/libs/cassowary/cassowary/debug.h new file mode 100644 index 0000000000..aa0499c641 --- /dev/null +++ b/libs/cassowary/cassowary/debug.h @@ -0,0 +1,48 @@ +// $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 +// +// debug.h + +#ifndef CASSOWARY_DEBUG_H_ +#define CASSOWARY_DEBUG_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 <vector> +#include "Cassowary.h" + +#ifdef CL_TRACE +class Tracer { + public: + Tracer(const char *const sz) : sz_(sz) { cerr << "* " << sz; } + ~Tracer() { cerr << "x " << sz_ << " exited." << endl; } + private: + const char *const sz_; +}; + +inline void CtrTracer(const char *const sz, const void *pv) +{ cerr << "@+ " << sz << " ctrnew@ " << pv << endl; } + +inline void DtrTracer(const char *const sz, const void *pv) +{ cerr << "@- " << sz << " dtrnew@ " << pv << endl; } + +#else +class Tracer { + public: + Tracer(const char *const) { } +}; + +inline void CtrTracer(const char *const, const void *) { } +inline void DtrTracer(const char *const, const void *) { } +#endif // CL_TRACE + +#endif diff --git a/libs/cassowary/cassowary/timer.h b/libs/cassowary/cassowary/timer.h new file mode 100644 index 0000000000..6bad1a6fef --- /dev/null +++ b/libs/cassowary/cassowary/timer.h @@ -0,0 +1,176 @@ +/* $Id$ */ +#ifndef _TIMER_H_ +#define _TIMER_H_ + +// Programmer: John P. Russo +// -------------------------- +// John Russo has given permission to any of my students to use his +// "timer" class. +// +// Please give full credit to him any time you wish to use this class. +// Hossein Hakimzadeh 11/5/96 + +/************************** timer.cpp ********************************** + + A simple example that shows how C++ classes can be used to implement + a "Timer" object, which mimics the familiar actions of a stopwatch. + + The code relies heavily on the clock() function defined in the time + library. The clock() function returns the number of "ticks" that have + elapsed since a program starts. The size of a "tick" is compiler + dependent, but for PC compilers is about 1/18 second. + + The problem with the clock function is that it is not convenient to + use for typical timing operations. The timer class, defined below, by + contrast, shows that an object-oriented approach to modules can + provide tools that are natural and easy to use. + += = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = */ +#include <time.h> + +class Timer +{ + //==================== public section ================================ + + // The functions and/or data in the public section of a class are + // accessible to anyone who uses the Timer class. + +public: + Timer(); // Constructor, used to declare Timer objects + void Start(); // Starts a timer object + void Stop(); // Stop a timer object + void Reset(); // Reset timer object + int IsRunning(); // Is the timer object running? + double ElapsedTime(); // How much time has been recorded? + double Resolution(); // Shortest measurable amount of time + + //-------------------- private section ------------------------------- + + // The functions and/or data in the private section of a class are NOT + // accessible to those who use the Timer class. They are accessible by + // member functions of the class. This allows access to the data to be + // carefully controlled. + +private: + long StartReading; // Number of ticks when timer object last started. + long ElapsedTicks; // Number of ticks on timer object. + int TimerIsRunning; // 1 if and only if timer object is running. + double TicksPerSecond() // This inline function is used to convert +// {return 18.206481;} // "ticks" (returned by clock() ) to seconds. + {return CLOCKS_PER_SEC;} // "ticks" (returned by clock() ) to seconds. + // In most UNIX systems this is 1000000 +}; + +/**************************** Start ************************************ + + If the declaration "Timer StopWatch;" has been made, the the call, + "StopWatch.Start();" is like push the start button of a real stopwatch. + +- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/ +void Timer::Start() +{ + TimerIsRunning = 1; // Stopwatch is now running + StartReading = clock(); // Look at internal clock and remember reading +} + +/**************************** Stop ************************************ + + Looks at the PC's internal clock and computes the number of ticks that + have elapsed since the timer was started. + + Note that if a timer is not reset, it can be used to time several events + and return the elapsed time for the enter set of events. + +- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/ +void Timer::Stop() +{ + TimerIsRunning = 0; // Stop timer object. + ElapsedTicks += clock() - StartReading; // Add elapsed time to the +} // previous time. + +/**************************** Reset ************************************ + + Clears a Timer of previous elapsed times, so that a new event can be + timed. + +- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/ +void Timer::Reset() +{ + TimerIsRunning = 0; // Start not yet called. + ElapsedTicks = 0; // No time on timer object yet. +} + +/************************** IsRunning ************************************ + + The data member, "TimerIsRunning" is used to keep track of whether a + timer is active, i.e. whether an event is being timed. While we want + those using the timer class to know when a timer is active, we do NOT + want them to directly access the TimerIsRunning variable. We solve this + problem, by making TimerIsRunning private and providing the public + "access function" below. + +- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/ +int Timer::IsRunning() +{ + return TimerIsRunning; +} + +/************************* ElapsedTime *********************************** + + This function allows a client to determine the amount of time that has + elapsed on a timer object. Note that there are two possibilities: + + 1) A timer object has been started and stopped. We can detect this + case, because the variable "TimerIsRunning" is false. + + 2) A timer object is "running", i.e. is still in the process of timing + an event. It is not expected that this case will occur as frequently + as case 1). + + In either case, this function converts ticks to seconds. Note that + since the function TicksPerSecond() returns a value of type double, + an implicit type conversion takes place before doing the division + required in either case. + +- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/ +double Timer::ElapsedTime() +{ + if ( !TimerIsRunning ) // Normal case + return ElapsedTicks/TicksPerSecond(); + + else + return (ElapsedTicks + clock() - StartReading)/TicksPerSecond(); +} + +/************************** Resolution *********************************** + + Althould we have no way of knowing how accurate the internal clock is, + we can predict its resolution, which is the shortest event that can be + measured by the clock. + +- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/ +double Timer::Resolution() +{ + return 1/TicksPerSecond(); // Note 1 is coverted to 1.0 before division +} + +/******************** Timer (constructor) ******************************* + + A "constructor" is a special class member function, one which has the + same name as the class. The "default constructor" is a constructor that + has no parameters. A constructor is called automatically when an + instance of a class is declared. For example, the constructor defined + below is called when the declaration "Timer T;" is executed. + + If the programmer does not write a default constructor, then the + compiler will generate one automatically. However, by writing the + constructor below, we provide automatic initialization of timer objects. + +- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/ +Timer::Timer() +{ + TimerIsRunning = 0; // Start not yet called. + ElapsedTicks = 0; // No time on timer object yet. +} + +#endif /* _TIMER_H_ */ |