How to functionally merge overlapping number-ranges from a List

Question

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:

1. Pop() the first range-obj and iterate through the rest of the list comparing it with each of the other ranges.
2. if there is an overlapping item, merge them together ( This yields a new Range instance ) and delete the 2 merge-candidates from the source-list.
3. At the end of the list add the Range object (which could have changed numerous times through merging) to the final-result-list.
4. Repeat this with the next of the remaining items.
5. Once the source-list is empty we're done.

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.

Answer 1

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))