CODEWITHSUNDEEP
scalarangerangeset
user_s
user_s

Reputation: 1078

Is there a range data structure in Scala?

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]

Upvotes: 4

Views: 2354

Answers (2)

Rüdiger Klaehn
Rüdiger Klaehn

Reputation: 12565

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.

Upvotes: 6

Vitalii Kotliarenko
Vitalii Kotliarenko

Reputation: 2967

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.

Upvotes: 2

Related Questions