Optimal flexible box layout algorithm

Question

I'm implementing the CSS3 flexible box layout module as defined by the W3C, which is similar to Mozilla's box model for xul. While these standards specify how the model should behave, they don't give any details on how they should be implemented.

The parts of the model I'm interested in are:

1. Boxes have a width and height.
2. Boxes can contain other boxes.
3. Container boxes (parent boxes) are responsible for sizing and positioning the boxes they contain (child boxes).
4. Boxes have orientation which may be horizontal or vertical. The orientation determines how the child boxes are positioned and resized.
5. Child boxes may be flexible or inflexible. If the child box is inflexible it is drawn at the size specified in the width and height parameters. If it is flexible, then it is resized to fit into the available space in the parent container.
6. Flexibility is relative to other child boxes in the same container, boxes with higher flexibility are resized more than boxes with lower flexibility.
7. Child boxes can be constrained to a minimum or maximum size. If the child box is flexible, the parent box will never resize it below the minimum size, or above the maximum size.

Features 1-5 can be implemented quite efficiently. Feature 6 is problematic as the most efficient algorithm I can come up with is quite naive. The algorithm works as follows:

1. Place all the boxes in a list.
2. Loop through each child box and resize it using the flexibility to determine the amount to resize it by.
3. If the size exceeds one of the limits, then set the box size to the limit and remove it from the list, and start from the beginning of the list.

Step 3 is where the efficiency drops. For example, if there are ten items in the list, and the last one has a constraint, then the algorithm calculates the size for the first nine items, then when it reaches the tenth one it needs to redo all of the calculations. I have considered keeping the list sorted and first sizing all the constrained boxes, however this comes with the cost of added complexity and the overhead of sorting the list.

I expect there is a recognised optimal solution considering this is a fairly common feature in browsers and frameworks (XUL, .Net, Flex, etc).

Answer 1

Most box/container layout algorithms use a 2 pass algorithm. In the case of .NET (WPF) they are called "Measure" and "Arrange". Each control can measure its content and report a "desired size" in the recursive measure pass.

During the second pass (arrange) if the childrens desired sizes will not fit inside the parent, the parent uses its layout algorithm to provide the actual size to each child, for example by assigning the actual size weighted by desired size. Minimum/maximum sizes, box flexibility etc can come into play here.

More information on the WPF layout system http://msdn.microsoft.com/en-us/library/ms745058.aspx

Xul layout http://www-archive.mozilla.org/projects/xul/layout.html