Range intersection / union

Question

I'm developing a programming language for which I want to provide a Range data type which for now is, not as usually, a list of pairs of int values (x,y) with the constraint that x < y. I say not as usually because usually a range is just a pair but in my case it is more than than, allowing to have for example

1 to 5, 7 to 11, 13 to 22

all contained in a single object.

I would like to provide two functions to generate the union and the instersection of two ranges, that should contain the least number of non-overlapping intervals from a couple of ranges.. so for example

1 to 5 || 3 to 8 = 1 to 8
1 to 5 && 3 to 8 = 3 to 5
(1 to 3, 4 to 8) && 2 to 6 = (2 to 3, 4 to 6)

where || is union and && is intersection.

For now their implementation is, as stated before, just a list.. I know that a more suitable data structure exists (interval tree) but for now I'm more concerned in building new lists from the union/intersection of other lists..

Which are the state-of-the-art algorithms to implement these two functions?

Thanks in advance

Answer 1

Since you don't want to deal with interval trees and use only lists, I would suggest you keep your range representation as a list of disjoint intervals sorted by the x coordinates.

Given two lists, you can compute the union and intersection by doing a kind of merge step like we do in merge of sorted lists.

Example:

For union of L1 and L2:

Create L to be empty List.

Take the interval with smallest x from L1 and L2 and put onto L.

Now take smallest again, compare with last element of L, and decide whether they need to be merged (if overlap) or a new interval appended (if they don't overlap) at the end of L and continue processing, like we do in merging two sorted lists.

Once you are done, L will be the union whose intervals are sorted by x and are disjoint.

For intersection, you can do something similar.

Answer 2

It seems to me that the best way of storing intervals - interval trees - is also the means to perform operations on them. Since doing point-tree intersections is the main case supported by interval tree query, it doesn't seem to be too hard to extend that to interval-interval intersection: for each interval in tree1, query tree2 for both endpoints. For intersection, subtract the intersecting interval from tree1, and for union, add the intersecting interval. For each subtract/add operation, you'll get a new set of intervals to add to your new tree3, which will end up being the result of your operation.