CODEWITHSUNDEEP
algorithm
Irdis
Irdis

Reputation: 964

Find set difference between two integer intervals

I've recently faced a problem. I had to find set difference between two integer intervals. Interval is determined by two borders - high and low. Where the high point isn't included.

Well I came up with solution, to consider several cases. All of a sudden it's ~12 cases. I listed some of them below. Looks wierd. Is there a simpler solution?

        //a[  a) b[  b) 
        // [   )  
        if (a._end <= b._start)
            return Lst(a);

        //a[  b[  a)  b)
        // [   )
        if (a._start < b._start && b._start < a._end &&
            b._start < a._end && a._end < b._end)
            return Lst(Rng(a.Start(), b.Start()));

        //b[  a[  b)  a)
        //         [   )
        if (b._start < a._start && a._start < b._end &&
            a._start < b._end && b._end < a._end)
            return Lst(Rng(b.End(), a.End()));

        //b[  b) a[  a)  
        //        [   )
        if (b._end <= a._start)
            return Lst(a);

        //a[  b[  b)  a)
        // [   )   [   )
        if (a._start < b._start && b._start < a._end &&
            a._start < b._end && b._end < a._end)
            return Lst(
                Rng(a.Start(), b.Start()),
                Rng(b.End(), a.End()));

Upvotes: 0

Views: 830

Answers (1)

AnT stands with Russia
AnT stands with Russia

Reputation: 320391

(I don't see why you decided to generate such redundant conditions as ... b._start < a._end && b._start < a._end ...)

Among other things, your code is made more complicated by your attempts to build the entire result within a single return statement. If you could just build the result incrementally in a local variable and then just return that local variable, the code would be greatly simplified.

Relying on standard functions like min and max instead of embedding the min/max logic into your code will also make it much more compact.

Let's say we build the result in the local list variable result and append intervals to it by doing result.append().

The difference operation can produce up to two intervals: one to the left of b, another to the right of b. Let's just calculate them in that order

List result;

if (a._start < b._start)
  // Left portion exists
  result.append(Rng(a._start, min(a._end, b_start)));

if (a._end > b._end)
  // Right portion exists
  result.append(Rng(max(a._start, b._end), a._end));
  
return result;

I assumed that the intervals are already normalized, i.e. a._start <= a._end, but it seems that your code also relies on that assumption.

Upvotes: 4

Related Questions