An answer to this question on Stack Overflow.

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

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.