Line Wrapping Algorithm: The greedy approach

Question

I needed a simple line wrapping algorithm, so I turned to Wikipedia:

http://en.wikipedia.org/wiki/Line_wrap_and_word_wrap#Minimum_number_of_lines

The greedy algorithm:

1. |  SpaceLeft := LineWidth
2. |  for each Word in Text
3. |      if (Width(Word) + SpaceWidth) > SpaceLeft
4. |         insert line break before Word in Text
5. |         SpaceLeft := LineWidth - Width(Word)
6. |      else
7. |         SpaceLeft := SpaceLeft - (Width(Word) + SpaceWidth)

On line #5, when we start a new line and subtract the word width from the available width, shouldn't we also subtract the space width?

5. |         SpaceLeft := LineWidth - (Width(Word) + SpaceWidth)

Why is the space width not accounted for on line #5?

-- UPDATE --

Some simple testing.

In each of the images, the first paragraph is created by JavaScript using the above wrapping algorithm (orange outline), and the second paragraph is native-rendered by the browser (blue outline).

Interestingly, this extremely bare-bones algorithm, indeed produces the exact same results as the browser rendering, for text with NO edge cases.

This first image shows that when we use

SpaceLeft := LineWidth - Width(Word)

JS rendering and browser rendering are exactly same.

But the following images (different line widths) show the subtle differences between JS and browser renderings when we use:

SpaceLeft := LineWidth - (Width(Word) + SpaceWidth)

The Code


// function getWidth() uses canvas to calculate the widths
// http://stackoverflow.com/questions/118241/calculate-text-width-with-javascript

var wrap = function(container, text, lineWidth) {
        var words = text.split(' ');
        var w, x, i, l;
        var spaceWidth = getWidth(' ');
        var spaceLeft = lineWidth;

        var arr = [], line = [];
        arr.push(line);

        for ( i = 0, l = words.length; i < l; i++ ) {
            w = words[i];
            x = getWidth(w) + spaceWidth;

            if ( x > spaceLeft ) {
                line = [];
                arr.push(line);
                line.push(w);

                // this is the case for Wikipedia algorithm
                // spaceLeft = lineWidth - getWidth(w);

                spaceLeft = lineWidth - x;
            }
            else {
                spaceLeft = spaceLeft - x;
                line.push(w);
            }
        }

        for ( i = 0, l = arr.length; i < l; i++ ) {

            container.append(
                $('<span>').text(arr[i].join(' '))
            );
        }
    };

I'm confused why you even need to define spaceLeft on line 5 at all. It seems by then the line break has already occurred and it's irrelevant. It will just get set back to the default `SpaceLeft := LineWidth` next time you run the loop — Albert Renshaw, Feb 21 '15 at 06:31
Unless space left is unique for each line, in which case the reason they only subtract width(word) is because when you broke the word to the next line, the amount of space left is what it already was minus the word that was just removed. `SpaceLeft-=Width(word)` — Albert Renshaw, Feb 21 '15 at 06:33
On line 4, we insert a break, and then on line 5 we start a new line. Note that the break is being inserted BEFORE the word -- and the word is placed on a new line. Shouldn't a space go with the word too? Because in the `else` part we are always putting space with word. — treecoder, Feb 21 '15 at 06:33
Okay I see. I wouldn't think a space should go with it too unless they type a space. — Albert Renshaw, Feb 21 '15 at 06:35
the new line so far only has the word you were just typing on it, so the space left is the width of that line minus the width of the word. — Albert Renshaw, Feb 21 '15 at 06:35
It's not about typing a space. All spaces are being inserted by the algorithm. We are ONLY taking words from the text. (actually spaces are not inserted, only the space widths accounted for) — treecoder, Feb 21 '15 at 06:36
The Wikipedia algorithm seem wrong to me. Consider what happens when `Width(Word) == LineWidth`. — Björn Lindqvist, Sep 24 '18 at 11:19

score 1 · Answer 1 · edited May 23 '17 at 12:06

The algorithm would probably be "more" correct if line 5 was

5. |         SpaceLeft := LineWidth - (Width(Word) + SpaceWidth)

as you suggest.

In any case, the question is a bit philosophical, as the algorithm is far too simplified for any concrete implementation, considering a real implementation would need to take care of the fact that the text may already contain new lines, that words are not necessarily delimited by spaces (e.g hyphens) and or multiple spaces.

Using an existing implementation is probably the best solution, e.g. for Java: Wrap the string after a number of characters word-wise in Java

Line Wrapping Algorithm: The greedy approach

1 Answers1