Find overlap of "circular" ranges

Question

By circular I mean a range can cross the max-value and loop back starting at 0. For example:

Given a max-value:

9 

And two ranges (both of which can be "circular"):

0123456789
----range1 (a normal range)  
ge2----ran (a circular range)

What is a good algorithm to calculate their intersection(s)? In this case the intersection(s) would be:

7-9 
789
ge1
ran

Bonus for an algorithm that can "delete" one from the other. By delete I mean, one range is being completely extracted from another:

0123456789
----range1
ge2----ran

subtracting range2 from range 1 would yield:

3456
-ran

Update: the numbers are always integers. There are only ever two ranges being compared at once and they are always contiguous though, as noted, they may span 0.

Also note, it would be nice to output a boolean if one range fully contained another. I think I may have though of a nice way to do so.

Thanks!

Answer 1

here's an update about how I went about solving my above question. Basically the strategy is to divide and conquer.

Both ranges are split into two separate sections if need be. Then they are compared to each one at a time.

Hope this helps someone out, and tell me if you see any logical errors in this strategy. Later I'll post the "deletion" algorithm I mentioned above.

Also note, the ranges are 0-based.

var arePositiveIntegers = require('./arePositiveIntegers');
//returns an array of the overlaps between two potentially circular ranges
module.exports = function getOverlapsOfPotentiallyCircularRanges(rangeA, rangeB, maxLength) {
  if (!arePositiveIntegers(rangeA.start, rangeA.end, rangeB.start, rangeB.end)) {
    console.warn("unable to calculate ranges of  inputs");
    return [];
  }
  var normalizedRangeA = splitRangeIntoTwoPartsIfItIsCircular(rangeA, maxLength);
  var normalizedRangeB = splitRangeIntoTwoPartsIfItIsCircular(rangeB, maxLength);

  var overlaps = [];
  normalizedRangeA.forEach(function(nonCircularRangeA) {
    normalizedRangeB.forEach(function(nonCircularRangeB) {
      var overlap = getOverlapOfNonCircularRanges(nonCircularRangeA, nonCircularRangeB);
      if (overlap) {
        overlaps.push(overlap);
      }
    });
  });
  return overlaps;
};

//takes a potentially circular range and returns an array containing the range split on the origin
function splitRangeIntoTwoPartsIfItIsCircular(range, maxLength) {
  if (range.start <= range.end) {
    //the range isn't circular, so we just return the range
    return [{
      start: range.start,
      end: range.end
    }];
  } else {
    //the range is cicular, so we return an array of two ranges
    return [{
      start: 0,
      end: range.end
    }, {
      start: range.start,
      end: maxLength - 1
    }];
  }
}

function getOverlapOfNonCircularRanges(rangeA, rangeB) {
  if (!arePositiveIntegers(rangeA.start, rangeA.end, rangeB.start, rangeB.end)) {
    console.warn("unable to calculate ranges of  inputs");
    return null;
  }
  if (rangeA.start < rangeB.start) {
    if (rangeA.end < rangeB.start) {
      //no overlap
    } else {
      if (rangeA.end < rangeB.end) {
        return {
          start: rangeB.start,
          end: rangeA.end
        };
      } else {
        return {
          start: rangeB.start,
          end: rangeB.end
        };
      }
    }
  } else {
    if (rangeA.start > rangeB.end) {
      //no overlap
    } else {
      if (rangeA.end < rangeB.end) {
        return {
          start: rangeA.start,
          end: rangeA.end
        };
      } else {
        return {
          start: rangeA.start,
          end: rangeB.end
        };
      }
    }
  }
}

Answer 2

It looks as though you can simply take each discrete element of your range and put it in a set. You can then perform an intersection of sets to get the output element.

This can be done in O(M+N) time by using a hash table.

Walk through your first range, creating an entry in the hash table for each element which is a member of the range.

Then walk through the second range and look each element up. If it is already in the hash table, then it is part of the intersection of the ranges.

With a little thought, you'll figure out how set differencing works.

If you need to intersect a third range, remove elements from the table that were not part of the second range.