|
 ABSTRACT
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 third of a window, or preferring that an object be contained within a rectangle if possible. Previous constraint solvers designed for user interface applications cannot handle simultaneous linear equations and inequalities efficiently. This is a major limitation, as such systems of constraints arise often in natural declarative specifications. We describe Cassowary---an incremental algorithm based on the dual simplex method, which can solve such systems of constraints efficiently. We have implemented the algorithm as part of a constraint-solving toolkit. We discuss the implementation of the toolkit, its application programming interface, and its performance.
REFERENCES
Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.
 |
1
|
Greg J. Badros , Jojada J. Tirtowidjojo , Kim Marriott , Bernd Meyer , Will Portnoy , Alan Borning, A constraint extension to scalable vector graphics, Proceedings of the 10th international conference on World Wide Web, p.489-498, May 01-05, 2001, Hong Kong, Hong Kong
[doi> 10.1145/371920.372146]
|
| |
2
|
BADROS,G.J.AND BORNING, A. 2001. Cassowary constraint solving toolkit. Web page. http://www.cs.washington.edu/research/constraints/cassowary.
|
| |
3
|
Greg J. Badros , Alan Borning , Kim Marriott , Peter Stuckey, Constraint cascading style sheets for the Web, Proceedings of the 12th annual ACM symposium on User interface software and technology, p.73-82, November 07-10, 1999, Asheville, North Carolina, United States
[doi> 10.1145/320719.322588]
|
| |
4
|
BADROS,G.J.,NICHOLS,J.,AND BORNING, A. 2000. SCWM-the Scheme Constraints Window Manager. In Proceedings of the AAAI Spring Symposium on Smart Graphics.
|
| |
5
|
|
| |
6
|
Alan Borning , Richard Anderson , Bjorn Freeman-Benson, Indigo: a local propagation algorithm for inequality constraints, Proceedings of the 9th annual ACM symposium on User interface software and technology, p.129-136, November 06-08, 1996, Seattle, Washington, United States
[doi> 10.1145/237091.237110]
|
| |
7
|
BORNING,A.AND BADROS, G. 2000. On finding graphically plausible solutions to constraint hierarchies: The split stay problem. In Workshop on Soft Constraints: Theory and Practice. Sixth International Conference on Principles and Practice of Constraint Programming (Singapore). Available from http://www.cs.washington.edu/research/constraints.
|
| |
8
|
|
| |
9
|
|
| |
10
|
Alan Borning , Richard Lin , Kim Marriott, Constraints for the web, Proceedings of the fifth ACM international conference on Multimedia, p.173-182, November 09-13, 1997, Seattle, Washington, United States
[doi> 10.1145/266180.266361]
|
| |
11
|
|
| |
12
|
Alan Borning , Kim Marriott , Peter Stuckey , Yi Xiao, Solving linear arithmetic constraints for user interface applications, Proceedings of the 10th annual ACM symposium on User interface software and technology, p.87-96, October 14-17, 1997, Banff, Alberta, Canada
[doi> 10.1145/263407.263518]
|
| |
13
|
HOSOBE, H., MATSUOKA,S.,AND YONEZAWA, A. 1996. Generalized local propagation: A framework for solving constraint hierarchies. In Proceedings of the Second International Conference on Principles and Practice of Constraint Programming. LINCS 1118, Springer-Verlag, Heidelberg, Germany.
|
| |
14
|
HUDSON,S.AND SMITH, I. 1996. SubArctic UI toolkit user's manual. Tech. Rep., College of Computing, Georgia Institute of Technology.
|
| |
15
|
|
| |
16
|
|
| |
17
|
MARRIOTT,K.AND STUCKEY, P. 1998. Programming with Constraints: An Introduction. MIT Press, Cambridge, MA.
|
| |
18
|
|
| |
19
|
|
| |
20
|
|
| |
21
|
|
| |
22
|
SUTHERLAND, I. 1963. Sketchpad: A man-machine graphical communication system. In Proceedings of the Spring Joint Computer Conference. IFIPS, 329-346.
|
| |
23
|
VAN HENTENRYCK,P.AND GRAF, T. 1990. Standard forms for rational linear arithmetic in constraint logic programming. Internal Rep. ir-lp-2217, European Computer Research Centre.
|
| |
24
|
|
| |
25
|
|
CITED BY 25
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Peter Rigole , Yolande Berbers , Tom Holvoet, Mobile adaptive tasks guided by resource contracts, Proceedings of the 2nd workshop on Middleware for pervasive and ad-hoc computing, p.117-120, October 18-22, 2004, Toronto, Ontario, Canada
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Sofie Goderis, High-level declarative user interfaces, Companion to the 20th annual ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, October 16-20, 2005, San Diego, CA, USA
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Evan Schrier , Mira Dontcheva , Charles Jacobs , Geraldine Wade , David Salesin, Adaptive layout for dynamically aggregated documents, Proceedings of the 13th international conference on Intelligent user interfaces, January 13-16, 2008, Gran Canaria, Spain
|
|
|
Angelo Di Iorio , Luca Furini , Fabio Vitali , John Lumley , Tony Wiley, Higher-level layout through topological abstraction, Proceeding of the eighth ACM symposium on Document engineering, September 16-19, 2008, Sao Paulo, Brazil
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Stefano Bistarelli , Philippe Codognet , H. K. C. Hui , J. H. M. Lee, Solving finite domain constraint hierarchies by local consistency and tree search, Proceedings of the 18th international joint conference on Artificial intelligence, p.1364-1365, August 09-15, 2003, Acapulco, Mexico
|
|
Adobe Acrobat
QuickTime
Windows Media Player
Real Player
Pdf
D.1