casso

package module
v0.0.0-...-fe75aa8 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: May 31, 2020 License: MIT Imports: 3 Imported by: 1

README

casso

MIT License go.dev reference Discord Chat

casso is a low-level Go implementation of the popular Cassowary constraint solving algorithm.

casso allows you to efficiently and incrementally describe partially-conflicting required/preferential constraints over a set of variables, and solve for a solution against them that is legitimately locally-error-better much like the simplex algorithm.

It is popularly used in Apple's Auto Layout Visual Format Language, and in Grid Style Sheets.

Description

Linear equality and inequality constraints arise naturally in specifying many aspects of user interfaces, such as requiring that one window be to the left of another, requiring that a pane occupy the leftmost 1/3 of a window, or preferring that an object be contained within a rectangle if possible. Current constraint solvers designed for UI applications cannot efficiently handle simultaneous linear equations and inequalities. This is a major limitation. We describe Cassowary—an incremental algorithm based on the dual simplex method that can solve such systems of constraints efficiently.

Paper written by Greg J. Badros, and Alan Borning. For more information, please check out the paper here.

Example

s := casso.NewSolver()

containerWidth := casso.New()

childX := casso.New()
childCompWidth := casso.New()

child2X := casso.New()
child2CompWidth := casso.New()

// c1: childX == (50.0 / 1024) * containerWidth
// c2: childCompWidth == (200.0 / 1024) * containerWidth
// c3: childCompWidth >= 200.0
// c4: child2X - childX - childCompWidth == 50
// c5: child2CompWidth == 50 + containerWidth + child2X

c1 := casso.NewConstraint(casso.EQ, 0, childX.T(1.0), containerWidth.T(-50.0/1024))
c2 := casso.NewConstraint(casso.EQ, 0, childCompWidth.T(1.0), containerWidth.T(-200.0/1024))
c3 := casso.NewConstraint(casso.GTE, -200, childCompWidth.T(1.0))
c4 := casso.NewConstraint(casso.EQ, -50, child2X.T(1.0), childX.T(-1.0), childCompWidth.T(-1.0))
c5 := casso.NewConstraint(casso.EQ, 50, child2CompWidth.T(1.0), containerWidth.T(-1.0), child2X.T(1.0))

// Mark 'containerWidth' as an editable variable with strong precedence.
// Suggest 'containerWidth' to take on the value 2048.

require.NoError(t, s.Edit(containerWidth, casso.Strong))
require.NoError(t, s.Suggest(containerWidth, 2048))

// Add constraints to the solver.

_, err := s.AddConstraint(c1)
require.NoError(t, err)

_, err = s.AddConstraintWithPriority(casso.Weak, c2)
require.NoError(t, err)

_, err = s.AddConstraintWithPriority(casso.Strong, c3)
require.NoError(t, err)

_, err = s.AddConstraint(c4)
require.NoError(t, err)

_, err = s.AddConstraint(c5)
require.NoError(t, err)

// Grab computed values.

require.EqualValues(t, 2048, s.Val(containerWidth))
require.EqualValues(t, 400, s.Val(childCompWidth))
require.EqualValues(t, 1448, s.Val(child2CompWidth))

// Suggest 'containerWidth' to take on the value 500.

require.NoError(t, s.Suggest(containerWidth, 500))

// Grab computed values.

require.EqualValues(t, 500, s.Val(containerWidth))
require.EqualValues(t, 200, s.Val(childCompWidth))
require.EqualValues(t, 175.5859375, s.Val(child2CompWidth))

Remarks

Symbols/references to variables are represented as unsigned 64-bit integers. The first two bits of a symbol denote the symbols type, with the rest of the bits denoting the symbols ID.

A symbol with an ID of zero is marked to be invalid. As a result, a program at any given moment in time may only generate at most 2^62 - 1 symbols, or 4,611,686,018,427,387,903 symbols.

This was done for performance reasons to minimize memory usage and reduce the number of cycles needed to perform some operations. If you need this restriction lifted for a particular reason, please open up a Github issue.

Benchmarks

$ cat /proc/cpuinfo | grep 'model name' | uniq
model name : Intel(R) Core(TM) i7-7700HQ CPU @ 2.80GHz

$ go test -bench=. -benchtime=10s
goos: linux
goarch: amd64
pkg: github.com/lithdew/casso
BenchmarkAddConstraint-8         8426456              1701 ns/op            1168 B/op         11 allocs/op

Documentation

Index

Constants

View Source 
const (
	Weak     Priority = 1
	Medium            = 1e3 * Weak
	Strong            = 1e3 * Medium
	Required          = 1e3 * Strong
)

Variables

View Source 
var (
	ErrBadPriority         = errors.New("priority must be non-negative and not required for edit variable")
	ErrBadEditVariable     = errors.New("symbol is not yet registered as an edit variable")
	ErrBadDummyVariable    = errors.New("constraint is unsatisfiable: non-zero dummy variable")
	ErrBadConstraintMarker = errors.New("symbol is not registered to refer to a constraint")
	ErrBadTermInConstraint = errors.New("one of the terms in the constraint references a nil symbol")
)
View Source 
var OpTable = [...]string{
	EQ:  "=",
	GTE: ">=",
	LTE: "<=",
}
View Source 
var SymbolTable = [...]string{
	External: "External",
	Slack:    "Slack",
	Error:    "Error",
	Dummy:    "Dummy",
}

Functions

This section is empty.

Types

type Constraint 

type Constraint struct {
	// contains filtered or unexported fields
}

func NewConstraint 

func NewConstraint(op Op, constant float64, terms ...Term) Constraint

type Edit 

type Edit struct {
	// contains filtered or unexported fields
}

type Expr 

type Expr struct {
	// contains filtered or unexported fields
}

func NewExpr 

func NewExpr(constant float64, terms ...Term) Expr

type Op 

type Op uint8
const (
	EQ Op = iota
	GTE
	LTE
)

func (Op) String 

func (o Op) String() string

type Priority 

type Priority float64

type Solver 

type Solver struct {
	// contains filtered or unexported fields
}

func NewSolver 

func NewSolver() *Solver

func (*Solver) AddConstraint 

func (s *Solver) AddConstraint(cell Constraint) (Symbol, error)

func (*Solver) AddConstraintWithPriority 

func (s *Solver) AddConstraintWithPriority(priority Priority, cell Constraint) (Symbol, error)

func (*Solver) Edit 

func (s *Solver) Edit(id Symbol, priority Priority) error

func (*Solver) RemoveConstraint 

func (s *Solver) RemoveConstraint(marker Symbol) error

func (*Solver) Suggest 

func (s *Solver) Suggest(id Symbol, val float64) error

func (*Solver) Val 

func (s *Solver) Val(id Symbol) float64

type Symbol 

type Symbol uint64

func New 

func New() Symbol

func (Symbol) Dummy 

func (sym Symbol) Dummy() bool

func (Symbol) EQ 

func (sym Symbol) EQ(val float64) Constraint

func (Symbol) Error 

func (sym Symbol) Error() bool

func (Symbol) External 

func (sym Symbol) External() bool

func (Symbol) GTE 

func (sym Symbol) GTE(val float64) Constraint

func (Symbol) Kind 

func (sym Symbol) Kind() SymbolKind

func (Symbol) LTE 

func (sym Symbol) LTE(val float64) Constraint

func (Symbol) Restricted 

func (sym Symbol) Restricted() bool

func (Symbol) Slack 

func (sym Symbol) Slack() bool

func (Symbol) T 

func (sym Symbol) T(coeff float64) Term

func (Symbol) Zero 

func (sym Symbol) Zero() bool

type SymbolKind 

type SymbolKind uint8
const (
	External SymbolKind = iota
	Slack
	Error
	Dummy
)

func (SymbolKind) Restricted 

func (s SymbolKind) Restricted() bool

func (SymbolKind) String 

func (s SymbolKind) String() string

type Tag 

type Tag struct {
	// contains filtered or unexported fields
}

type Term 

type Term struct {
	// contains filtered or unexported fields
}

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.