Finding set difference between ranges

[Chris Angelico]

On Fri, Apr 20, 2018 at 8:34 PM, tejaswi prakash
<tejaswidprakash at gmail.com> wrote:
> I generate the values using range and then convert them to sets.
> I am thinking about an approach which involves subtracting the ranges, or
> something along those lines, nothing concrete yet.

(Please don't top-post)

I would recommend keeping them as ranges. You know for certain that
they are ranges of consecutive integers, so the only info you actually
need to work with is start,stop (step is guaranteed to be 1). How many
ways are there for the set difference to be calculated?

minu.difference(sub)

1) sub.stop <= sub.start
    # Empty subtrahend, nothing to remove
    difference = minu
2) sub.stop < minu.start or sub.start >= minu.stop
    # No overlap
    difference = minu
3) sub.start <= minu.start < sub.stop < minu.stop
    # minuend overlaps start of subtrahend
    difference = range(sub.stop, minu.stop)
4) minu.start < sub.start < minu.stop <= sub.stop
    # minuend overlaps end of subtrahend
    difference = range(minu.start, sub.start)
5) minu.start < sub.start < sub.stop < minu.stop
    # minuend is entirely surrounded by subtrahend

Situation 5 is the only complicated one. It's now fractured the range
into two halves (removing the middle). So now you have to work with
two minuends for the next step, subtracting the same subtrahend from
each of them. If either of them is completely emptied by the second
step, you can ignore it, but otherwise, you now have two pieces. (Or
three, if you get a second fracturing.)

This would be the easiest way to handle this, I think.

ChrisA