Is there a range data structure in Scala?

Question

I'm looking for a way to handle ranges in Scala. What I need to do is:

given a set of ranges and a range(A) return the range(B) where range(A) intersect range (B) is not empty

given a set of ranges and a range(A) remove/add range(A) from/to the set of ranges.

given range(A) and range(B) create a range(C) = [min(A,B), max(A,B)]

I saw something similar in java - http://docs.guava-libraries.googlecode.com/git/javadoc/com/google/common/collect/RangeSet.html Though subRangeSet returns only the intersect values and not the range in the set (or list of ranges) that it intersects with.

 RangeSet rangeSet = TreeRangeSet.create();
 rangeSet.add(Range.closed(0, 10));
 rangeSet.add(Range.closed(30, 40));
 Range range = Range.closed(12, 32);
 System.out.println(rangeSet.subRangeSet(range)); //[30,32] (I need [30,40])
 System.out.println(range.span(Range.closed(30, 40))); //[12,40]

Answer 1

There is an Interval[A] type in the spire math library. This allows working with ranges of arbitrary types that define an Order. Boundaries can be inclusive, exclusive or omitted. So e.g. (-∞, 0.0] or [0.0, 1.0) would be possible intervals of doubles.

Here is a library intervalset for working with sets of non-overlapping intervals (IntervalSeq or IntervalTrie) as well as maps of intervals to arbitrary values (IntervalMap).

Here is a related question that describes how to use IntervalSeq with DateTime.

Note that if the type you want to use is 64bit or less (basically any primitive), IntervalTrie is extremely fast. See the Benchmarks.

Answer 2

As Tzach Zohar has mentioned in the comment, if all you need is range of Int - go for scala.collection.immutable.Range:

val rangeSet = Set(0 to 10, 30 to 40)
val r = 12 to 32
rangeSet.filter(range => range.contains(r.start) ||  range.contains(r.end))

If you need it for another underlying type - implement it by yourself, it's easy for your usecase.