[Development] Idea for automatic widget layout

[Kerrick Staley]

Hello,

I had an idea for automating widget layout in a framework like
Clutter, Gtk+, or Qt. Imagine you have a row of widgets that are
competing for horizontal space. Instead of having the developer (who
is using the framework) declare a custom size for each widget, you
could instead have the widget designer declare a mathematical function
that takes the widget's width and returns a value indicating how much
utility [1] the widget gets from that width. Then, you can sum the
utilities for all the widgets in the row, and then run an optimization
algorithm [2] in order to figure out the allocation that maximizes
this sum. This optimization could be performed at compile time to
achieve a static layout, or dynamically at runtime whenever the window
size changes or the widgets' contents change.

As an example, let's say you have a widget displaying a table or
spreadsheet populated with some data. Assume the widget has the
ability to automatically add scrollbars if there is not enough room to
display its contents. If there is not enough room to display all the
columns in this table, then the user will still get some partial
benefit from being able to see only a few of the columns in the table;
they can scroll through the rest. The more columns, the better,
however: this minimizes the amount of scrolling necessary. The user
will *not* get much benefit, however, out of being able to see half of
a column: if there is enough space to display, say, 3.5 columns, then
the table might as well be big enough to display only 3 columns: the
user won't be able to read anything in the extra half-column anyway.
Hence, the utility curve for this widget will end up looking something
like a step function (but will flatten for widths that are enough to
display all the data). As another example, an image will have a
utility curve that grows drastically initially, but slows down once
the image is large enough for the user to discern its contents.

The curve of the widget will depend on the widget's content, and may
change as the program runs. Widgets may change their internal layout
entirely at certain sizes (e.g. a widget may display text and an icon
at larger sizes, but display only an icon at smaller sizes); in this
situation, the utility curve will end up being a piecewise function.
The application designer (who is distinct from the widget designer)
may also be able to supply parameters to alter the utility curve; the
most obvious example is a parameter that would scale the whole utility
curve, making that widget bigger in the layout.

If no "good" choice for a utility curve is immediately apparent, then
a curve of the form k*ln(w) (where w is the input width and k is a
scaling parameter) is a good default. If all the widgets in a row are
assigned this curve, then it turns out that the optimal width of each
widget is proportional to that widget's k parameter.

I don't know how useful/practical this idea is, but I don't think I
have the time to create an effective implementation all by myself. If
some of the Clutter or Gtk+ folks are interested in implementing this
idea in their framework, I'd love to help out, though (sorry Qt devs,
but I'm a GNOME guy).

- Kerrick

[1] The units of the utility value are meaningless, but all the
widgets within a library should have utility curves that are
commensurate with each other, so that their default behavior is
reasonable.

[2] Optimization is well-studied; see
https://en.wikipedia.org/wiki/Mathematical_optimization. However, the
choice of algorithm with which to perform the optimization is crucial,
especially if the optimization will be carried out at runtime. An
appropriate algorithm should be very fast, but doesn't necessarily
need to return the global maximum; instead, it should return a layout
that's "good enough". As time progresses and CPU power increases,
increasingly sophisticated algorithms can be used for this purpose.