Function textwrap::core::wrap_optimal_fit[][src]

pub fn wrap_optimal_fit<'a, T: Fragment, F: Fn(usize) -> usize>(
    fragments: &'a [T],
    line_widths: F
) -> Vec<&'a [T]>

Wrap abstract fragments into lines with an optimal-fit algorithm.

The line_widths map line numbers (starting from 0) to a target line width. This can be used to implement hanging indentation.

The fragments must already have been split into the desired widths, this function will not (and cannot) attempt to split them further when arranging them into lines.

Optimal-Fit Algorithm

The algorithm considers all possible break points and picks the breaks which minimizes the gaps at the end of each line. More precisely, the algorithm assigns a cost or penalty to each break point, determined by cost = gap * gap where gap = target_width - line_width. Shorter lines are thus penalized more heavily since they leave behind a larger gap.

We can illustrate this with the text “To be, or not to be: that is the question”. We will be wrapping it in a narrow column with room for only 10 characters. The greedy algorithm will produce these lines, each annotated with the corresponding penalty:

"To be, or"   1² =  1
"not to be:"  0² =  0
"that is"     3² =  9
"the"         7² = 49
"question"    2² =  4

We see that line four with “the” leaves a gap of 7 columns, which gives it a penalty of 49. The sum of the penalties is 63.

There are 10 words, which means that there are 2_u32.pow(9) or 512 different ways to typeset it. We can compute the sum of the penalties for each possible line break and search for the one with the lowest sum:

"To be,"     4² = 16
"or not to"  1² =  1
"be: that"   2² =  4
"is the"     4² = 16
"question"   2² =  4

The sum of the penalties is 41, which is better than what the greedy algorithm produced.

Searching through all possible combinations would normally be prohibitively slow. However, it turns out that the problem can be formulated as the task of finding column minima in a cost matrix. This matrix has a special form (totally monotone) which lets us use a linear-time algorithm called SMAWK to find the optimal break points.

This means that the time complexity remains O(n) where n is the number of words. Compared to wrap_first_fit, this function is about 4 times slower.

The optimization of per-line costs over the entire paragraph is inspired by the line breaking algorithm used in TeX, as described in the 1981 article Breaking Paragraphs into Lines by Knuth and Plass. The implementation here is based on Python code by David Eppstein.

Note: Only available when the smawk Cargo feature is enabled.