Splitting text into lines from a max width value for CANVAS

Question

Ok so this works as is, and is not actually slow at all (from what I can see) - However I don't like the taste of nested while loops and was wondering if anyone could give some insight on a different approach? Or how to improve mine to take away the while() { while() {}}

Here it is:

/* takes a string and a maxWidth and splits the text into lines */
 // ctx is available in the parent scope.
function fragmentText(text, maxWidth) {
    var words = text.split(' '),
        lines = [],
        line = "";
    if (ctx.measureText(text).width < maxWidth) {
        return [text];
    }
    while (words.length > 0) {
        while (ctx.measureText(words[0]).width >= maxWidth) {
            var tmp = words[0];
            words[0] = tmp.slice(0, -1);
            if (words.length > 1) {
                words[1] = tmp.slice(-1) + words[1];
            } else {
                words.push(tmp.slice(-1));
            }
        }
        if (ctx.measureText(line + words[0]).width < maxWidth) {
            line += words.shift() + " ";
        } else {
            lines.push(line);
            line = "";
        }
        if (words.length === 0) {
            lines.push(line);
        }
    }
    return lines;
}

Answer 1

The first thing I notice is an excessive use of measureText, which I am inclined to assume is a relatively expensive operation. At a minimum, every word is measured twice - once to verify it fits within the maxWidth constraint, and once again to verify it fits on the current line. Of course, as the line grows, all previous words are measured again by virtue of the current line being measured on each loop.

Second, when a word doesn't fit on the current line, it must be processed again (it isn't shifted off the array in this condition).

With this kind of problem, I prefer to separate tasks - that is, measure first (no need to measure twice), build second. I would prefer to loop through the word list a couple of times to minimize the calls to measureText. I have rewritten the function with this in mind. The function is much longer now, but I feel it is easier to follow and to maintain when edge cases arise.

var emmeasure = ctx.measureText("M").width;
var spacemeasure = ctx.measureText(" ").width;

/* takes a string and a maxWidth and splits the text into lines */ 
 // ctx is available in the parent scope. 
function fragmentText(text, maxWidth) { 
    if (maxWidth < emmeasure) // To prevent weird looping anamolies farther on.
        throw "Can't fragment less than one character.";

    if (ctx.measureText(text).width < maxWidth) { 
        return [text]; 
    } 

    var words = text.split(' '), 
        metawords = [],
        lines = [];

    // measure first.
    for (var w in words) {
        var word = words[w];
        var measure = ctx.measureText(word).width;

        // Edge case - If the current word is too long for one line, break it into maximized pieces.
        if (measure > maxWidth) {
            // TODO - a divide and conquer method might be nicer.
            var edgewords = (function(word, maxWidth) {
                var wlen = word.length;
                if (wlen == 0) return [];
                if (wlen == 1) return [word];

                var awords = [], cword = "", cmeasure = 0, letters = [];

                // Measure each letter.
                for (var l = 0; l < wlen; l++)
                    letters.push({"letter":word[l], "measure":ctx.measureText(word[l]).width});

                // Assemble the letters into words of maximized length.
                for (var ml in letters) {
                    var metaletter = letters[ml];

                    if (cmeasure + metaletter.measure > maxWidth) {
                        awords.push({ "word":cword, "len":cword.length, "measure":cmeasure });
                        cword = "";
                        cmeasure = 0;
                    }

                    cword += metaletter.letter;
                    cmeasure += metaletter.measure;
                }
                // there will always be one more word to push.
                awords.push({ "word":cword, "len":cword.length, "measure":cmeasure });
                return awords;
            })(word, maxWidth);

            // could use metawords = metawords.concat(edgwords)
            for (var ew in edgewords)
                metawords.push(edgewords[ew]);
        }
        else {
            metawords.push({ "word":word, "len":word.length, "measure":measure });
        }
    }

    // build array of lines second.
    var cline = "";
    var cmeasure = 0;
    for (var mw in metawords) {
        var metaword = metawords[mw];

        // If current word doesn't fit on current line, push the current line and start a new one.
        // Unless (edge-case): this is a new line and the current word is one character.
        if ((cmeasure + metaword.measure > maxWidth) && cmeasure > 0 && metaword.len > 1) {
            lines.push(cline)
            cline = "";
            cmeasure = 0;
        }

        cline += metaword.word;
        cmeasure += metaword.measure;

        // If there's room, append a space, else push the current line and start a new one.
        if (cmeasure + spacemeasure < maxWidth) {
            cline += " ";
            cmeasure += spacemeasure;
        } else {
            lines.push(cline)
            cline = "";
            cmeasure = 0;
        }
    }
    if (cmeasure > 0)
        lines.push(cline);

    return lines;
} 

Performance: I executed this test on my machine in IE9. Note the assumption of a table called "splittertest" with the columns: Words, MaxWidth, New (ms), Old (ms). The original function is called fragmentText_old in this test.

var tests = [{"twc":50, "tmw":500},
             {"twc":50, "tmw":50},
             {"twc":500, "tmw":500},
             {"twc":500, "tmw":50},
             {"twc":5000, "tmw":500},
             {"twc":5000, "tmw":50},
             {"twc":10000, "tmw":500},
             {"twc":10000, "tmw":50}];
var results = [];

for (var tt in tests) {
    var test = tests[tt];

    var testline = (function(twc) {
        var testwords = [];
        for (var x = 0; x < twc; x++) {
            var len = 3 + Math.floor(Math.random()*11);
            var letters = [];
            for (var y = 0; y < len; y++)
                letters.push(String.fromCharCode("a".charCodeAt() + y));
            testwords.push(letters.join(""));
        }
        return testwords;   
    })(test.twc).join(" ");

    var st, dur1, dur2;

    st = new Date().getTime();
    var ss = fragmentText(testline, test.tmw);
    dur1 = new Date().getTime() - st;

    st = new Date().getTime();
    var sso = fragmentText_old(testline, test.tmw);
    dur2 = new Date().getTime() - st;

    results.push("<tr><td>" + test.twc + "</td><td>" + test.tmw + "</td><td>" + dur1 + "</td><td>" + dur2 + "</td></tr>");
}

$("#splittertest").append(results.join(""));

The results show mine about twice as fast when there is no chance a word will exceed the maxWidth, and exponentially faster when words frequently exceed the maxWidth.

Words  MaxWidth  New (ms)  Old (ms)
50     500       1         1
50     50        3         5
500    500       3         7
500    50        16        331
5000   500       31        76
5000   50        195       167820 (2.8 mins)
10000  500       60        155
10000  50        337       1121565 (18.7 mins)

It's worth noting that the results are significantly less on subsequent runs in the same browser because of some caching done - probably within the canvas context.

Answer 2

Here's a different tack to take, namely recursion. It's CoffeeScript (sorry - I find myself thinking better when I don't have to deal with curly braces).

It's not perfect, and mostly here to hopefully give someone an idea for something better.

# Called it "wordWrap" since that's the usual name for such a function
wordWrap = (text, maxWidth) ->
  # Internal wrapping function
  wrap = (text, delim, hyphen = "") ->
    delimWidth = ctx.measureText delim

    parts  = text.split delim
    chunks = []

    while parts.length
      line = ""
      i    = 0

      while i < parts.length
        # Check if the next word/char will overflow
        tmp = line + parts[i] + hyphen + delim
        if ctx.measureText(tmp) > maxWidth + delimWidth
          # It overflowed!
          if i is 0
            # If this is the first checked for this line,
            # recursively wrap it letter-for-letter,
            # adding a hyphen where it breaks
            word = parts.shift()
            wrapped = wrap word, "", "-"
            # The first part of the hyphen-wrapped word
            # becomes our line, while the rest become the
            # the next part(s)
            line = wrapped[0]
            parts = wrapped.slice(1).concat parts

          # Add the hyphen string to the broken line
          line += hyphen
          break
        else
          # No overflow; add the part and move on
          line += parts[i] + delim
          i++

      # Loop broke, add the line, and remove
      # the parts we've processed
      chunks.push line.trim()
      parts = parts.slice i

    # Return chunks
    chunks

  # Call wrap with a space as the delimiter
  # and return the result
  wrap text, " "

Basically, it'll break words into lines, and - if a word is too long to fit on one line - it'll break that word with a hyphen.

Limitations: It will break a word with no regard for hyphenation rules, and might break a word to make room for the hyphen, even the word would fit without the hyphen. I.e. in the worst case the string "longword!" might break into "long-", "word-", "!"

So again, this is far from perfect.