StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POOptimal flexible box layout algorithm
text
Body
copied!<p>I'm implementing the <a href="http://www.w3.org/TR/2009/WD-css3-flexbox-20090723/" rel="noreferrer">CSS3 flexible box layout module</a> as defined by the W3C, which is similar to <a href="https://developer.mozilla.org/en/XUL_Tutorial/The_Box_Model" rel="noreferrer">Mozilla's box model for xul</a>. While these standards specify how the model should behave, they don't give any details on how they should be implemented. </p> <p>The parts of the model I'm interested in are:</p> <ol> <li>Boxes have a width and height.</li> <li>Boxes can contain other boxes.</li> <li>Container boxes (parent boxes) are responsible for sizing and positioning the boxes they contain (child boxes).</li> <li>Boxes have orientation which may be horizontal or vertical. The orientation determines how the child boxes are positioned and resized.</li> <li>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.</li> <li>Flexibility is relative to other child boxes in the same container, boxes with higher flexibility are resized more than boxes with lower flexibility.</li> <li>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.</li> </ol> <p>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:</p> <ol> <li>Place all the boxes in a list.</li> <li>Loop through each child box and resize it using the flexibility to determine the amount to resize it by.</li> <li>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.</li> </ol> <p>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.</p> <p>I expect there is a recognised optimal solution considering this is a fairly common feature in browsers and frameworks (XUL, .Net, Flex, etc).</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload