Applies a HTML formatting to a raw string

string2html.js

/**
 * Applies HTML formatting to a raw string
 * Runtime: O(n)
 *
 * @param str {String} A raw string
 * @param formats {Array} An array of formats where each one has the following structure: [startOffset, endOffset, tagName]
 * @return formattedString {String}
 **/
function format(str, formats) {
  var formatsLen = formats.length;
  var strLen = str.length;
  var startTag = {}, endTag = {}, formattedStr = '';
 
 // let's preprocess the input, so we can query the formats
 // by character position in amortized constant time.
  for (var i = 0; i < formatsLen; i++) {
    if (!startTag[ formats[i][0] ]) {
      startTag[ formats[i][0] ] = [];
    }
    if (!endTag[ formats[i][1] ]) {
      endTag[ formats[i][1] ] = [];
    }
    // save the formats using the starting position as the key
    startTag[ formats[i][0] ].push(i);
      
    // save the formats using the ending position as the key
    endTag[ formats[i][1] ].push(i);
  }

  var currentFormat, tagName;
  // a single stack will keep track of where we are in the tree
  var scopeStack = [];
  
  // will concat all start tags by providing an array of formats
  var addStartTags = function(currentFormats) {
    var formatsLen = currentFormats.length;
    var tags = '';
    for (var i = 0; i < formatsLen; i++) {
      var tagName = formats[ currentFormats[i] ][2];
      tags += '<' + tagName + '>';
       // push it onto the stack
      scopeStack.push(currentFormats[i]);
    }
    return tags;
  }
  // will concat all end tags by providing an array of formats
  // and may open tags if they are needed
  var addEndTags = function(currentFormats) {
    var formatsLen = currentFormats.length;
    var tags = '';
      
    for (var i = 0; i < formatsLen; i++) {
      var currentFormat = currentFormats[i];
      var tagName = formats[currentFormat][2];
      var j = scopeStack.length - 1;

      while (j >== 0 && scopeStack[j] !== currentFormat) {
        tags += '</' + formats[ scopeStack[j] ][2] + '>';
        j = j - 1;
      }
      if (j >== 0 && scopeStack[j] === currentFormat) {
        tags += '</' +  formats[ scopeStack[j] ][2] + '>';
      }
      // pop the tag at position j out the stack
      scopeStack.splice(j, 1);

      // add the formats that are still active after closing the last tag
      while (j >== 0 && j < scopeStack.length) {
       tags += '<' + formats[ scopeStack[j] ][2] + '>';
       j++;
      }
    }
    return tags;
  }

  for (var i = 0; i < strLen; i++) {
     // add the tags that start at this position
    if (startTag[i]) {
      formattedStr += addStartTags(startTag[i]);
    }
    // add the tags that end at this position
    if (endTag[i]) {
      formattedStr += addEndTags(endTag[i]);
    }
    // add the character
    formattedStr +=str.charAt(i);
  }
   if (endTag[strLen]) {
     formattedStr += addEndTags(endTag[strLen]);
   }
  //strip off empty tags just in case..
  return formattedStr.replace(/<\w+><\/\w+>/g, '');
}
// Example  usage
var formattedStr = format('Hello there', [
  [0, 3, 'b'],
  [1, 2, 'i'],
  [4, 5, 'u']
]);

console.log(formattedStr);
// will output: <b>H<i>e</i>l</b>l<u>o</u> there