classowary
1.0.0An implementation of the Cassowary linear constraint solver toolkit
About Classowary
Classowary is an implementation of the linear constraint solver toolkit Cassowary. It is a variant of the simplex solver algorithm, specifically designed to allow adding, removing, and updating constraints quickly. This makes it a good candidate for layout computations.
How To
After loading Classowary you will likely want to create a local nickname in your package for org.shirakumo.classowary
. We will assume that this nickname is called cass
for this tutorial.
(defvar *solver* (cass:makesolver))
(cass:withvariables (a b c) *solver*
(cass:constrain *solver* (<= 0 a))
(cass:constrain *solver* (<= a 10))
(cass:constrain *solver* (= b (* (+ 1 a) 5)))
(cass:constrain *solver* (= (+ 3 (* 2 c)) (+ a b)))
(cass:updatevariables *solver*)
(values (cass:value a) (cass:value b) (cass:value c)))
;; => 0 5 1
As you can see, the solver picked only one of many possible solutions. When the system is underconstrained, it isn't predictable which solution you will get, but it should always fulfil all constraints that were given. If the system is overconstrained, Cassowary will try to match them as closely as possible according to each constraint's strength.
Cassowary also allows you to "suggest" a value for a variable. This means that the solver will try to keep the variable to this value if possible.
(cass:withvariables (a b c) *solver*
(cass:makesuggestable a)
(cass:suggest a 5)
(cass:updatevariables *solver*)
(values (cass:value a) (cass:value b) (cass:value c)))
;; => 5 30 16
This is typically how you will want to impose additional constraints imposed by the user such as when they explicitly move or resize something.
Naturally you can impose additional constraints at a later point as well.
(cass:withvariables (a b c) *solver*
(cass:constrain *solver* (<= a (/ c 4)) :name 'a)
(cass:updatevariables *solver*)
(values (cass:value a) (cass:value b) (cass:value c)))
;; => 1 10 4
As you can see, with this additional constraint the solver was no longer able to fulfil our suggested value exactly. We can easily remove the offending constraint again.
(cass:deleteconstraint (cass:findconstraint 'a *solver*))
Instead of using the constrain
and withvariables
macros, you can also dynamically build the variables and constraints through makevariable
, makeconstraint
, addterm
, relation
, and addconstraint
. When building constraints and variables, you should make sure to pass the :name
argument so that you can retrieve them from the solver later, or keep references of your own somewhere.
Should a solver or constraint get into a bad state, you can attempt to clear their state out with resetsolver
and resetconstraint
respectively.
Further Reading
The Cassowary algorithm is described in the paper "The Cassowary Linear Arithmetic Constraint Solving Algorithm: Interface and Implementation" by Badros and Borning^{[1]}. You can find the website of the original implementation here.
This implementation is largely based on the Amoeba implementation by Xavier Wang.
System Information
Definition Index

ORG.SHIRAKUMO.CLASSOWARY
No documentation provided.
EXTERNAL CONSTANT +MEDIUM+
Constant for constraints with a medium weight. Corresponds to 1e3. You can also specify the keyword :medium instead of this constant wherever strengths are accepted.

EXTERNAL CONSTANT +NONE+
Constant for constraints with no weight. Corresponds to 0e0. You can also specify the keyword :none instead of this constant wherever strengths are accepted.

EXTERNAL CONSTANT +REQUIRED+
Constant for constraints with a very high weight. Corresponds to 1e9. You can also specify the keyword :required instead of this constant wherever strengths are accepted.

EXTERNAL CONSTANT +STRONG+
Constant for constraints with a high weight. Corresponds to 1e6. You can also specify the keyword :strong instead of this constant wherever strengths are accepted.

EXTERNAL CONSTANT +WEAK+
Constant for constraints with a weak weight. Corresponds to 1e0. You can also specify the keyword :weak instead of this constant wherever strengths are accepted.

EXTERNAL STRUCTURE CONSTRAINT
Represents a constraint in a linear system. Each of the constraints in a system must appear in the following normalised, mathematical form: CONSTRAINT ::= TERM RELATION TERM (\+ TERM)* RELATION ::= <=  =  >= TERM ::= number (\* variable)? number  a SINGLEFLOAT variable  a VARIABLE For instance, the following are valid constraints: 0 = 0 1 = 2 1*x <= 1 2*x >= 3 + 4*y And the following are not valid constraints: 1*x + 1*y = 3*y + 5*z x*x = 2 See MAKECONSTRAINT See CLONECONSTRAINT See DELETECONSTRAINT See FINDCONSTRAINT See ADDCONSTRAINT See REMOVECONSTRAINT See ADDTERM See ADDCONSTANT See RELATION See SOLVER (function) See CONSTRAIN

EXTERNAL STRUCTURE EXPRESSION
The representation of a linear expression. A linear expression represents a constant factor added together with a series of linear variable terms. See TERM

EXTERNAL STRUCTURE SOLVER
Represents a linear constraint system. A linear constraint system is composed out of several constraints that describe an equality or inequality composed out of linear terms. The solver can then attempt to find a solution that fits the variables in the terms to the constraints as well as possible. Note that the solver will bend constraints if there is no solution that does not violate any of them. See CONSTRAINT (type) See MAKESOLVER See RESETSOLVER See AUTOUPDATE See MAKECONSTRAINT See MAKEVARIABLE See CONSTRAIN See WITHVARIABLES See FINDVARIABLE See FINDCONSTRAINT

EXTERNAL STRUCTURE TERM
The representation of a variable term. A term is a variable and a linear multiplication factor.

EXTERNAL STRUCTURE VARIABLE
Represents a variable in a linear system. A variable can appear in an arbitrary number of constraints to express linear terms. A variable has a value and two states: suggestable, or unsuggestable. In the default, unsuggestable state, the variable is freely controlled by the linear system and its value is directly deduced from the constraints. In the suggestable state, the variable has a suggested value that the user supplies, which the solver should attempt to keep constant as the system is solved. See MAKEVARIABLE See DELETEVARIABLE See FINDVARIABLE See ADDTERM See WITHVARIABLES See SOLVER (function) See MAKESUGGESTABLE See MAKEUNSUGGESTABLE See SUGGESTABLEP See SUGGEST See VALUE

EXTERNAL FUNCTION ADDCONSTRAINT
 CONSTRAINT
Adds the constraint to its solver. Without this, the constraint will not apply. If the solver is AUTOUPDATE, the variables will be updated after this operation. See SOLVER See CONSTRAINT (type) See REMOVECONSTRAINT

EXTERNAL FUNCTION ADDTERM
 CONSTRAINT
 MULTIPLIER
 &OPTIONAL
 VARIABLE
Adds the given term description to the constraint. This corresponds to a term of either number or number*variable being added to the constraint depending on whether the variable is given. Note that adding or removing terms can automatically cancel out as soon as either the constant term of the expression reaches zero, or the multiplier of a variable term reaches zero. In the latter case, the variable term is automatically removed from the expression. Returns the updated constraint. See CONSTRAINT (type) See VARIABLE (type) See REMOVETERM

EXTERNAL FUNCTION AUTOUPDATE
 SOLVER
Accessor to whether the solver automatically updates variables on changes. See SOLVER (type)

EXTERNAL FUNCTION (SETF AUTOUPDATE)
 VALUE
 SOLVER
No documentation provided. 
EXTERNAL FUNCTION CLONECONSTRAINT
 OTHER
 &KEY
 STRENGTH
Return a copy of the given constraint. This will copy the constraint including its terms into a fresh instance. See CONSTRAINT (type) See MAKECONSTRAINT See DELETECONSTRAINT

EXTERNAL FUNCTION CONSTRAINEDP
 CONSTRAINT
Returns true if the constraint is additionally constrained through a variable. See CONSTRAINT (TYPE)

EXTERNAL FUNCTION DELETECONSTRAINT
 CONSTRAINT
Deletes the constraint completely from the solver. This will render the constraint useless. Operating on it beyond this point results in undefined behaviour. See CONSTRAINT (type) See MAKECONSTRAINT

EXTERNAL FUNCTION DELETEVARIABLE
 VARIABLE
Deletes the variable completely from the solver. This will remove the variable and all terms in all expressions that include it. See MAKEVARIABLE See VARIABLE (type)

EXTERNAL FUNCTION FINDCONSTRAINT
 SYMBOL
 SOLVER
Returns the constraint associated with the given name, if any. Note that you are /not/ permitted to SETF this place. See CONSTRAINT (type) See SOLVER (type)

EXTERNAL FUNCTION (SETF FINDCONSTRAINT)
 CONSTRAINT
 SYMBOL
 SOLVER
No documentation provided. 
EXTERNAL FUNCTION FINDVARIABLE
 SYMBOL
 SOLVER
Returns the variable associated with the given name, if any. Note that you are /not/ permitted to SETF this place. See VARIABLE (type) See SOLVER (type)

EXTERNAL FUNCTION (SETF FINDVARIABLE)
 VARIABLE
 SYMBOL
 SOLVER
No documentation provided. 
EXTERNAL FUNCTION MAKECONSTRAINT
 SOLVER
 &KEY
 NAME
 STRENGTH
Returns a new constraint for the solver. The STRENGTH designates how strongly this constraint is adhered. By default the strength is +REQUIRED+. The NAME designates the symbol by which this constraint can later be found again. See STRENGTH (type) See DELETECONSTRAINT See FINDCONSTRAINT

EXTERNAL FUNCTION MAKESOLVER
 &KEY
 AUTOUPDATE
Returns a new solver instance. If AUTOUPDATE is T, the solver will automatically call UPDATEVARIABLES when constraints or variables change. See SOLVER (type) See AUTOUPDATE See RESETSOLVER See MAKECONSTRAINT See CONSTRAIN See MAKEVARIABLE See WITHVARIABLES

EXTERNAL FUNCTION MAKESUGGESTABLE
 VARIABLE
 &OPTIONAL
 STRENGTH
Make the variable suggestable. This means that you can edit the variable and suggest a value that the solver should try to keep steady when solving its system. Typically this is used for variables that are constrained by the user somehow. In order to use SUGGEST, a variable must first be made suggestable. If the variable is already suggestable, its strength is updated via (SETF STRENGTH). If the variable was not already suggestable, it is suggested to the current value of the variable. The strength of the suggestion is capped to +STRONG+. Any value above will automatically be reduced to +STRONG+. Returns the variable. See STRENGTH See VARIABLE (type) See MAKEUNSUGGESTABLE See SUGGESTABLEP See SUGGEST See STRENGTH

EXTERNAL FUNCTION MAKEUNSUGGESTABLE
 VARIABLE
Makes the variable unsuggestable again. After this, SUGGEST will fail unless the variable is explicitly made suggestable again. Returns the variable. See MAKESUGGESTABLE See SUGGESTABLEP See VARIABLE (type) See SUGGEST

EXTERNAL FUNCTION MAKEVARIABLE
 SOLVER
 &KEY
 NAME
 STRENGTH
Returns a new variable for the solver. The NAME is an optional identifier for the symbol used for the variable by which it can later be found again. If STRENGTH is given, the variable is made suggestable and its strength set accordingly. STRENGTH may also be T in this case, in which case the strength used is +STRONG+. See VARIABLE (type) See DELETEVARIABLE See MAKESUGGESTABLE See FINDVARIABLE

EXTERNAL FUNCTION RELATION
 CONSTRAINT
Accessor to the relation of the constraint. May be one of the following CL symbols: <= = >= See CONSTRAINT (type)

EXTERNAL FUNCTION (SETF RELATION)
 RELATION
 CONSTRAINT
No documentation provided. 
EXTERNAL FUNCTION REMOVECONSTRAINT
 CONSTRAINT
Removes the constraint from its solver. After this, the constraint will not apply. If the solver is AUTOUPDATE, the variables will be updated after this operation. See SOLVER See CONSTRAINT (type) See REMOVECONSTRAINT

EXTERNAL FUNCTION REMOVETERM
 CONSTRAINT
 MULTIPLIER
 &OPTIONAL
 VARIABLE
Removes the given term description from the constraint. This corresponds to a term of either number or number*variable being removed from the constraint depending on whether the variable is given. Note that adding or removing terms can automatically cancel out as soon as either the constant term of the expression reaches zero, or the multiplier of a variable term reaches zero. In the latter case, the variable term is automatically removed from the expression. This operation is equivalent to ADDTERM with the multiplier inverted. Returns the updated constraint. See CONSTRAINT (type) See VARIABLE (type) See ADDTERM

EXTERNAL FUNCTION RESETCONSTRAINT
 CONSTRAINT
Resets the constraint. This will remove the constraint, unset its relation, and clear its expression of all terms. Returns the updated constraint. See CONSTRAINT (type) See REMOVECONSTRAINT

EXTERNAL FUNCTION RESETSOLVER
 SOLVER
 &OPTIONAL
 CLEARCONSTRAINTS
Resets the solver. This resets all variables and makes them unsuggestable. If the solver is AUTOUPDATE, the variables will be updated before this operation. If CLEARCONSTRAINTS is T, removes all constraints from the solver. See SOLVER (type)

EXTERNAL FUNCTION STRENGTH
 CONSTRAINT
Accessor to the strength of the constraint. The strength is a positive float, denoting how important this constraint is to the overall system. Valid values for the strength are positive real numbers and the following keywords: :REQUIRED :STRONG :MEDIUM :WEAK :NONE Each of these keywords corresponds to the constant of the same name. If a value that is neither a positive real, nor one of the above keywords is set, an error is signalled. If the solver is AUTOUPDATE, the variables will be updated after the strength is updated. See CONSTRAINT (type) See +REQUIRED+ See +STRONG+ See +MEDIUM+ See +WEAK+ See +NONE+

EXTERNAL FUNCTION (SETF STRENGTH)
 STRENGTH
 CONSTRAINT
No documentation provided. 
EXTERNAL FUNCTION SUGGEST
 VARIABLE
 VALUE
 &OPTIONAL
 IFNOTSUGGESTABLE
Suggest a particular value for the variable. The solver will try to solve the system while keeping the value of the variable to the suggested value. Note however that this does not circumvent required constraints. If the variable is not already suggestable, the value of ifnotsuggestable becomes important. It may be one of the following: :ERROR  An error of type VARIABLENOTSUGGESTABLE is signalled. :MAKESUGGESTABLE  The variable is made suggestable with medium strength. NIL  The function simply returns NIL. If the solver is AUTOUPDATE, the variables will be updated after this operation. On success, returns the variable. See VARIABLE (type) See SUGGESTABLEP See MAKESUGGESTABLE See MAKEUNSUGGESTABLE See VARIABLENOTSUGGESTABLE

EXTERNAL FUNCTION SUGGESTABLEP
 VARIABLE
Returns true if the variable is suggestable. See VARIABLE (type) See MAKESUGGESTABLE See MAKEUNSUGGESTABLE See SUGGEST

EXTERNAL FUNCTION UPDATEVARIABLES
 SOLVER
Recomputes the variable values according to the current solver constraints. You should call this function whenever you are done changing constraints or suggesting variables and would like to read out the new, computed values for the variables. Returns the solver. See AUTOUPDATE

EXTERNAL FUNCTION VALUE
 VARIABLE
Returns the current value of the variable. You might need to call UPDATEVARIABLES on the solver before this returns an accurate value for the variable. Note that for suggestable variables this might return a value different from the one previously suggested. See VARIABLE (type)

EXTERNAL GENERICFUNCTION EXPRESSION
 CONDITION
Returns the expression associated with the object. See EXPRESSION (type) See EXPRESSIONUNSATISFIED see EXPRESSIONUNBOUND

EXTERNAL GENERICFUNCTION SOLVER
 CONDITION
Returns the solver associated with the object. See SOLVER (type) See VARIABLE (type) See CONSTRAINT (type) See EXPRESSIONUNSATISFIED See EXPRESSIONUNBOUND

EXTERNAL GENERICFUNCTION VARIABLE
 CONDITION
Returns the variable associated with the object. See VARIABLE (type) See VARIABLENOTSUGGESTABLE

EXTERNAL MACRO CONSTRAIN
 SOLVER
 CONSTRAINT
 &REST
 ARGS
 &KEY
 NAME
 STRENGTH
Constrain the linear system in the solver. The constraint should be an expression of the following form: CONSTRAINT ::= (RELATION EXPRESSION EXPRESSION) RELATION ::= <=  =  >= EXPRESSION ::= TERM  COMPOUND COMPOUND ::= (+ EXPRESSION*)  ( EXPRESSION+)  (* EXPRESSION*)  (/ EXPRESSION+) TERM ::= variable  real  (quote quoted) variable  A CL variable binding name. quoted  A symbol naming a solver variable. real  A real number. If a quoted variable is used, the variable is retrieved from the solver, or created if it does not exist yet. It will have the name of the quoted symbol. Otherwise the variable denotes a CL variable whose value must be of type VARIABLE. If the expression contains nonlinear terms, such as the multiplication of two variables, or the division by a variable, an error is signalled at macroexpansiontime. This macro is a shorthand to create constraint, add terms, set the relation, and add the constraint to the solver. The new constraint instance is returned. See CONSTRAINT (type) See SOLVER (type) See MAKECONSTRAINT See ADDTERM See RELATION See ADDCONSTRAINT

EXTERNAL MACRO WITHVARIABLES
 VARS
 SOLVER
 &BODY
 BODY
Convenience macro to create and bind multiple variables at once. Each binding must follow this structure: BINDING ::= variable  (variable name? strength?) variable  The CL variable the solver variable is bound to. name  The name of the solver variable as a symbol. This can later be used to retrieve the variable. If no explicit name is given, the CL variable name is used. strength  The strength of the variable if it is newly created. If a variable with the given name already exists in the solver, it is returned. Otherwise, a new variable of the given name is created. If NAME is NIL, a new variable is always created. Note that the variables are /not/ deleted on exit from the body. See VARIABLE (type) See SOLVER (type) See FINDVARIABLE See MAKEVARIABLE
