CODEWITHSUNDEEP
algorithmword-wrap
treecoder
treecoder

Reputation: 45131

Line Wrapping Algorithm: The greedy approach

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(' '))
            );
        }
    };

Upvotes: 1

Views: 3243

Answers (1)

Adrian Leonhard
Adrian Leonhard

Reputation: 7370

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

Upvotes: 1

Related Questions