5

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;

2 Answers 2

16
+50

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/

11
  • Thanks for the suggestion. My issue with this solution is that I very well may need to add tooltips for each span in the future or maybe different coloring to indicate overlapping spans.
    – Mcestone
    Feb 7, 2017 at 16:43
  • What happens if you have two intersecting spans of a different color? What color would the intersection be? Also, if you have intersecting spans with tooltips, talking from a high-level, how do you envision determining which tooltip to show when they hover over an intersection? Feb 7, 2017 at 16:46
  • The way that annotator.js handles overlapping spans is an ideal solution annotatorjs.org. Basically, you can have a large string of text with a highlight (lighter yellow) which has a tooltip you can see on hover. Within the large string of text there is a single word that is also highlighted. This is a darker yellow and has its own tooltip. On hover of the single word you see both the single word tooltip and the parent text tooltip.
    – Mcestone
    Feb 7, 2017 at 16:51
  • Hmm. I see. Let me think about that some more. Feb 7, 2017 at 16:53
  • Hi @mcestone, I've been thinking about this a bit more. Intersecting spans can be 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 section). Check my updated answer and see if that gets you an answer. Feb 7, 2017 at 21:36
0
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
  }];

var flags = new Array();
for (i = 0; i < spans.length; i++) { 
    for (j = spans[i].begin; j <= spans[i].end; j++) { 
    flags[j] = true;
    }
}

isSpan = false
var starts = new Array();
var ends = new Array();
for (i = 0; i < flags.length; i++) { 
    if (flags[i]) {
    if (!isSpan) {
      starts.push(i);
    }
    isSpan = true;
  }
  else {
    if (isSpan) {
      ends.push(i);
    }
    isSpan = false;
  }
}
if (flags.length > 0 && ends.length < starts.lenght) {
    ends.push(flags.length - 1);
}

var newSpans = new Array();
for (i = 0; i < starts.length; i++) { 
    newSpans.push({"begin": starts[i], "end": ends[i]});
}

newSpans.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;

Your Answer

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

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