I have a number of range-objects which I need to merge so that all overlapping ranges disappear:
case class Range(from:Int, to:Int)
val rangelist = List(Range(3, 40), Range(1, 45), Range(2, 50), etc)
Here is the ranges:
3 40
1 45
2 50
70 75
75 90
80 85
100 200
Once finished we would get:
1 50
70 90
100 200
Imperative Algorithm:
To do this imperatively one must create a lot of temporary variables, indexed loops etc.
So I'm wondering if there is a more functional approach?
At first sight the source-collection must be able to act like a Stack in providing pop() PLUS giving the ability to delete items by index while iterating over it, but then that would not be that functional anymore.
Try tail-recursion. (Annotation is needed only to warn you if tail-recursion optimization doesn't happen; the compiler will do it if it can whether you annotate or not.)
import annotation.{tailrec => tco}
@tco final def collapse(rs: List[Range], sep: List[Range] = Nil): List[Range] = rs match {
case x :: y :: rest =>
if (y.from > x.to) collapse(y :: rest, x :: sep)
else collapse( Range(x.from, x.to max y.to) :: rest, sep)
case _ =>
(rs ::: sep).reverse
}
def merge(rs: List[Range]): List[Range] = collapse(rs.sortBy(_.from))