7
\$\begingroup\$

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;
}
\$\endgroup\$
3
  • \$\begingroup\$ What's the difference between str.length and ctx.measureText(str)? \$\endgroup\$ Oct 1, 2012 at 22:44
  • 2
    \$\begingroup\$ @LarryBattle .length gives you the number of characters in the string; measureText gives you the width in pixels of the string if it were to be drawn with the selected font. So: Big difference :) \$\endgroup\$
    – Flambino
    Oct 1, 2012 at 22:54
  • \$\begingroup\$ @Flambino lol. I found that out before you left your comment. \$\endgroup\$ Oct 1, 2012 at 22:57

2 Answers 2

3
\$\begingroup\$

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.

\$\endgroup\$
6
  • 1
    \$\begingroup\$ My version behaves slighly differently in that it allows a line to reach maxWidth, where-as yours excludes maxWidth. Indeed, mine is a bit inconsistent where the space is concerned. \$\endgroup\$
    – Griffin
    Oct 2, 2012 at 14:24
  • \$\begingroup\$ Not sure I would rely on a space character always having the same width. With proportional typefaces and proper kerning, I imagine spaces can vary in width. I'm not saying that that's the case, but I wouldn't be surprised. \$\endgroup\$
    – Flambino
    Oct 2, 2012 at 18:09
  • \$\begingroup\$ @Flambino - Indeed. Kerning and other font effects can mess up this entire algorithm, both mine and the original. To wit, the sum measure of words and spaces may not equal the meaure of the total string - likewise the sum measure of letters may not equal the total measure of the word. In that regard, the original is slightly better, since it is always measuring the proposed string in full. However, its performance drops faster than mine - I've added some performance metrics to my answer. \$\endgroup\$
    – Griffin
    Oct 2, 2012 at 19:33
  • \$\begingroup\$ True, it's performance vs precision. However, my worries were unfounded: jsfiddle test. I tried a bunch of fonts, but the full-text width and the summed up letter width seems to be the same in all cases. Interestingly, Lucida Grande (which is highly optimized on OS X) was the only font I found that resulted in non-integer widths - but even then they were identical. I guess canvas just doesn't do any kerning (sadly). \$\endgroup\$
    – Flambino
    Oct 2, 2012 at 20:07
  • \$\begingroup\$ I think yours performs more than adequately as long as the case when a word exceeds the maxWidth is rare (which I imagine it generally would be). Even at 10K words with a maxWidth of 500, my test showed yours completing in 155ms. Now I have to chew over this some more. :) \$\endgroup\$
    – Griffin
    Oct 2, 2012 at 20:22
0
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.