Creating overlapping text spans in javascript

Question

See Fiddle

I am given a series of "spans" and need to add divs in the HTML at those indexes in order to "highlight" that range of text. Currently I am adding spanStarting spanEnding around the text I want to highlight. Later, I replace spanStarting/spanEnding with .

A span looks like this:

{
"begin": 145,
"end": 155
}

I have this working as long as the spans never overlap, now I need to deal with overlapping spans. For example, overlapping spans look like this:

{
"begin": 4,
"end": 18
},{
"begin": 4,
"end": 41
}

Adding spanStarting/spanEnding when there are overlapping spans distorts the indexes and makes it impossible to find the correct text to highlight. You can see what I have so far in this fiddle. Since there are overlapping spans, my code is unable to find the correct indices to place the code.

My code:

String.prototype.replaceBetween = function(start, end, what) {
  start = this.substring(0, start);
  end = this.substring(end, this.length);
  return start + what + end;
};

function createHighlights(subElements, snippet, raw) {
  var currentHighlight = subElements;
  currentHighlight.spanStart = currentHighlight.begin;
  currentHighlight.spanStop = currentHighlight.end;
  var currentWord = raw.substring(currentHighlight.spanStart, currentHighlight.spanStop);
  currentHighlight.spanStart = snippet.text.indexOf(currentWord);
  currentHighlight.spanStop = currentHighlight.spanStart + currentWord.length;
  snippet.text = snippet.text.replaceBetween(currentHighlight.spanStart, currentHighlight.spanStop, 'spanStarting' + currentWord + 'spanEnding');
}

var element = {
    "text": "The blood pressure was initially elevated on the patient's outpatient medications, so his hypertension medicines were adjusted by increasing his lisinopril to 20 mg qd."
  },
  rawText = element.text.slice(),
  spans = [{
    "begin": 145,
    "end": 155
  }, {
    "begin": 4,
    "end": 18
  }, {
    "begin": 4,
    "end": 18
  }, {
    "begin": 90,
    "end": 102
  }, {
    "begin": 4,
    "end": 41
  }];

spans.forEach(function(currentHighlight) {
  if (element.text.indexOf('<span') === -1) {
    createHighlights(currentHighlight, element, rawText)
  };
})

element.text = element.text.replace(/spanStarting/g, '<span class="highlight">');
element.text = element.text.replace(/spanEnding/g, '</span>');

document.getElementById('text').innerHTML = element.text;

Answer 1

One of the keys to displaying layered highlights is to first "flatten" your collection of highlight ranges. This is not unlike performing an orthogonal projection of a 3-dimensional object onto a 2-dimensional plane. The 3-dimensional object in this case is your collection of highlight layers. The key is to project these layers onto a single layer while persisting the overlapped data. If you can flatten all your layers into a single layer, it will be easier to display them to the user, and you will not run into the problem you are having with the multiple layers competing with each other when you try to add tags surrounding the ranges. It will also remove conflicts that may arise when the user tries to interact with sections that have multiple layers stacked on top of each other (for instance, with tooltips).

I would suggest creating a function that flattens all of your highlight ranges. Intersecting ranges can be mathematically reduced to a flat array of ranges and can include consolidated information about each flattened section (such as the number of intersections in that section to produce a darker highlight, and the collections of attributes that come from multiple intersections for that consolidated span, such as a collection of tooltips in that range).

For example, if you have three ranges

{begin:4,end:18,tooltip:'section 1'}
{begin:4,end:41,tooltip:'section 2'}
{begin:10,end:51,tooltip:'section 3'}

they will be consolidated into this structure:

{begin:4,end:10,tooltip:['section 1','section 2'],count:2},
{begin:10,end:18,tooltip:['section 1','section 2','section 3'],count:3},
{begin:18,end:41,tooltip:['section 2','section 3'],count:2}
{begin:41,end:51,tooltip:['section 3'],count:1}

This essentially takes the layered ranges and flattens them while consolidating both the number of intersections and the collections of attributes. You will notice that in the new structure, everything is sequential. There are no overlapping ranges (which will eliminate the conflicts you are experiencing in the UI). You will also notice that all the data from the original structure is also present in the new structure.

In addition, after flattening your layers, you would need to do a few "DOM-specific" things to your new collection. I would recommend "inflating" your collection of ranges, so that sections of text that are not highlighted will be put in a special range object (a range without a highlight). This will make it easier to execute the final step: rendering those ranges to the DOM. You can also double check your ranges here to make sure the indexes line up correctly for a zero-based index string.

Here is a flatten function that will flatten your collection of overlapping ranges into a "flat" sequence of ranges and consolidate any extra data (for example, tooltips).

function flattenRanges(ranges) {
  var points = [];
  var flattened = [];
  for (var i in ranges) {
    if (ranges[i].end < ranges[i].begin) { //RE-ORDER THIS ITEM (BEGIN/END)
      var tmp = ranges[i].end; //RE-ORDER BY SWAPPING
      ranges[i].end = ranges[i].begin;
      ranges[i].begin = tmp;
    }
    points.push(ranges[i].begin);
    points.push(ranges[i].end);
  }
  //MAKE SURE OUR LIST OF POINTS IS IN ORDER
  points.sort(function(a, b){return a-b});
  //FIND THE INTERSECTING SPANS FOR EACH PAIR OF POINTS (IF ANY)
  //ALSO MERGE THE ATTRIBUTES OF EACH INTERSECTING SPAN, AND INCREASE THE COUNT FOR EACH INTERSECTION
  for (var i in points) {
    if (i==0 || points[i]==points[i-1]) continue;
    var includedRanges = ranges.filter(function(x){
      return (Math.max(x.begin,points[i-1]) < Math.min(x.end,points[i]));
    });
    if (includedRanges.length > 0) {
      var flattenedRange = {
        begin:points[i-1],
        end:points[i],
        count:0
      }
      for (var j in includedRanges) {
        var includedRange = includedRanges[j];
        for (var prop in includedRange) {
          if (prop != 'begin' && prop != 'end') {
            if (!flattenedRange[prop]) flattenedRange[prop] = [];
            flattenedRange[prop].push(includedRange[prop]);
          }
        }
        flattenedRange.count++;
      }
      flattened.push(flattenedRange);
    }
  }
  return flattened;
}

The next step would be to inflate the flattened ranges. This function will fill in the sections that do not have highlights with just an empty range structure. It also cleans up any indexes that might cause overlap in the DOM.

function inflateRanges(ranges, length=0) {
  var inflated = [];
  var lastIndex;
  for (var i in ranges) {
    if (i==0) {
      //IF THERE IS EMPTY TEXT IN THE BEGINNING, CREATE AN EMOTY RANGE
      if (ranges[i].begin > 0){
        inflated.push({
          begin:0,
          end:ranges[i].begin-1,
          count:0
        });
      }
      inflated.push(ranges[i]);
    } else {
      if (ranges[i].begin == ranges[i-1].end) {
        ranges[i-1].end--;
      }
      if (ranges[i].begin - ranges[i-1].end > 1) {
        inflated.push({
          begin:ranges[i-1].end+1,
          end:ranges[i].begin-1,
          count:0
        });
      }
      inflated.push(ranges[i]);
    }
    lastIndex = ranges[i].end;
  }
  //FOR SIMPLICITY, ADD ANY REMAINING TEXT AS AN EMPTY RANGE
  if (lastIndex+1 < length-1) {
    inflated.push({
      begin:lastIndex+1,
      end:length-1,
      count:0
    })
  }
  return inflated;
}

Finally, I would recommend adding the actual text that is inside each of these ranges to each corresponding range as well. This is not absolutely necessary, but it makes testing easier.

function fillRanges(ranges, text) {
  for (var i in ranges) {
    ranges[i].text = text.slice(ranges[i].begin,ranges[i].end+1);
  }
  return ranges;
}

I also created a working example, using the exact data in your question. I did add an additional property called tooltip to illustrate how the consolidated properties can be used. In addition, I also added some simple tooltip CSS to showcase a practical example of how the tooltips are used with the layered ranges.

Here is the working example: https://jsfiddle.net/mspinks/shfpxp82/