Sunday, May 25, 2008

About layout engines

Michael put up this post in his blog. In it, there is the assertion that several ways of doing widget layout are incompatible with each other. In particular,

So what is the end result of these four different layout models [fixed, stack/grid, constraints, flow]? Well, for one, they're all completely incompatible with each other.

I beg to differ. Back in 2000 while at Exobox I wrote a layout engine for Morphic which, based on a tree of nodes which affected how their children would be laid out, was quite capable of doing fixed, stack/grid and constraint based layout (plus arbitrary coordinate geometry), all in the same UI. It did not do flow because it was not a requirement and as such it never came up.

As an example of what this layout engine can do, one of the demos was managing a spreadsheet of 64x32 cells, each of which had its own text morph, supporting columns and rows of variable size by changing the width/height of the header cell only, and all of this using quad trees embedded in the layout tree so as to avoid Morphic work when cells were outside the viewing area. No problem at all.

Therefore, in my opinion, these models are not incompatible with each other. The proof of this is an actual, working example driving production applications.

In more abstract terms, the interesting cases of layout problems are solved in a finite number of operations, and as such the individual operations are in a well ordered set. Once they are in a well ordered set, putting them in a tree that respects the order of evaluation (perhaps having nodes / leaves appearing in the tree multiple times) is more or less straightforward because each node of the tree could be a representation of a distinction made by us regarding the layout algorithm (this part, that part, etc).

The simplest way to do this would be with a 1-level deep tree in which the root node has leaves each of which represent each particular step (taken to extremes: a root node with a single leaf representing "do everything").

As a side note, integer linear programming problems are NP (one such problem is the Minesweeper Consistency Problem, which is NP-complete). As such, I suspect that some layout problems can be NP-complete as well (mod rounding the solution to a general linear programming problem).

See also Vassili Vykov's post here for more references regarding UI layout.

No comments: