Simplify line packing algorithm

[morganthomas]

The current line packing algorithm lets you lay out a series of velements with arbitrarily complex layout problems. Simplify this by having three categories of boxes: rigid, elastic, and fill. The following rules apply.

• A rigid box must be exactly its optimal length.
• An elastic box prefers to be its optimal length but can stretch or shrink.
• A fill box has no preferred length and assumes whatever non-negative length fills out the line. Fill boxes prefer to be shorter, subject to other considerations.
• Lines are never over-filled.
• If a fill box is in a line, then all elastic boxes will be their optimal length or less.
• If a fill box is in a line and the elastic boxes are compressed, then they will be compressed by the same percentage, and the fill box will have length zero.
• If a fill box is not in a line, then all elastic boxes will be stretched by the same percentage to fill the line.
• The badness of a line is proportional to the stretching/shrinking percentage applied to the elastic boxes.
• Pre/post break boxes work the same way as currently. A box which is a breakpoint can be consumed and replaced with the pre-break box on the pre-break line and the post-break box on the post-break line. This is the only way to make line breaks.

Corresponding changes will be required to the paragraph velement.

[morganthomas]

Here's a draft of the new line packing algorithm.

Take boxes and their optimal lengths, considering a fill box to have length 0, until you have more than the line length. You have up to three breakpoints to consider: the box the line length falls inside in this lineup, and the boxes right before and after that box.

Compute the badness and optimal layouts of each of these possible lines. Throw out any non-feasible ones. Update your list of threads accordingly. Prune the threads if necessary. Continue until all your threads are complete, and select the best one.

The badness of a line with no fill box is simply:

|elastic box stretch/shrink ratio - 1|

The badness of a line with a fill box is always zero.

[morganthomas]

Here's how to compute the stretch/shrink ratio in a line with no fill box.

• Let lineWidth be the target line width.
• Let rigidTotal be the sum of the optimal lengths of the rigid boxes.
• Let elasticTotal be the sum of the optimal lengths of the elastic boxes.
• Let leftover = lineWidth - rigidTotal.
• Let stretchShrinkRatio = leftover / elasticTotal.
• Then lineWidth = rigidTotal + stretchShrinkRatio * elasticTotal

[morganthomas]

The badness of a solution is the average of the badnesses of the lines (not the sum).

[morganthomas]

Actually I'm not sure what difference it makes whether you use the average or the sum. Let's use the sum for now, as the simplest option.