"Flow layouts" inside a GUI -- how do I come up with a good algorithm?

I was trying to write some simple code for a "flow layout" manager and what I came up with initially was something like the following (semi-pseudocode):

int rowHeight = 0;
RECT rect = parent.getClientRect();
POINT pos = rect.position;  // Start at top-left corner, row by row

foreach (Window child in parent.children)
{
    // POINT is a tuple of: (x, y)
    // SIZE is a tuple of: (width, height)
    // RECT is a tuple of: (left, top, right, bottom)
    RECT proposed1 = RECT(rect.left + pos.x, rect.top + pos.y, rect.right, rect.bottom),
         proposed2 = RECT(rect.left, rect.top + pos.y + rowHeight, rect.right, rect.bottom);
    SIZE size1 = child.getPreferredSize(proposed1),
         size2 = child.getPreferredSize(proposed2);
    if (size1.width <= proposed1.width)
    {
        child.put(proposed1);  // same row
        pos.x += size1.width;
        rowHeight = max(rowHeight, size1.height);
    }
    else
    {
        child.put(proposed2);  // new row
        pos.x = rect.left;
        pos.y += rowHeight;
        rowHeight = size2.height;
    }
}

In other words, the algorithm is very simple:

The layout manager asks every component, "is the remaining portion of the row enough for you?" and, if the component says "no, my width is too long", it places the component on the next row instead.

There are two major problems with this approach:

-
This algorithm results in very long, thin components, because it is essentially greedy with the width of each component -- if a component wants the whole row, it will use the whole row (ugly), even if it could use a smaller width (but larger height).

-
It only works if you already know what the parent's size is -- but you might not! Instead, you might simply have a restriction, "the parent's size must be between these two dimensions", but the rest might be open-ended.

I am, however, at a loss of how to come up with a better algorithm -- how do I figure out what would be a good size to to 'propose' to the compone

I've encountered variations of this problem several times doing GUI layout work. Your question about "What should I optimize?" is key to answering your question. Until you've decided that you really can't create a better algorithm.

More than likely you'd like to consider the size-ratios. Each child will have likely a minimum size, possibly a maximum in each dimension, and a preferred ratio, or range of acceptable ratios. You can use this basic data to make a guess as to what the layout should be. Now, for the resulting layout of each child you need a way to produce the preference score.

Now you simply have an optimization problem: maximize the total score of all the children. You can also include global scoring attributes, like the parent size (to cover your second problem). Some layouts you can also reject if they produce invalid results (parent too wide, child not acceptable).

Depending on how many children you have, and how optimal your layout needs to be, will determine how good your algorithm needs to be. For a very simple greedy approach you can simply do line-based. For example, just consider two lines at a time, the current line, and the next line. You should be able to come up with a list of items that easily have enough space on this line, and some that maybe don't. Then just try a few combinations of those trailing components (this line or next) and find a maximum score.

StackExchange Computer Science Q#2306, answer score: 3