How to functionally combine overlapping ranges of numbers from a list

Question

I have a number of range objects that I need to combine 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) 

The ranges below are:

  3 40 1 45 2 50 70 75 75 90 80 85 100 200 

Upon completion, we will receive:

  1 50 70 90 100 200 

Imperative Algorithm:

• Pop () the first range-obj and iterate over the rest of the list, comparing it with each of the other ranges.
• if there is an overlapping element, merge them together (this gives a new Range instance) and remove 2 merge lists from the original list.
• At the end of the list, add a Range object (which could change several times by merging) in the final list of results.
• Repeat this with the next remaining item.
• Once the source list is empty, we are done.

To do this, you need to create many temporary variables, indexed loops, etc.

So, I wonder if there is a more functional approach?

At first glance, the source compilation should be able to act as a stack in providing pop () PLUS, providing the ability to delete items by index during iteration over it, but then it will no longer function.

Answer 1

Try tail recursion. (Annotation is only needed to warn you if tailing optimization does not happen, the compiler will do this, if possible, if 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)) 

Answer 2

I like puzzles like this:

 case class Range(from:Int, to:Int) { assert(from <= to) /** Returns true if given Range is completely contained in this range */ def contains(rhs: Range) = from <= rhs.from && rhs.to <= to /** Returns true if given value is contained in this range */ def contains(v: Int) = from <= v && v <= to } def collapse(rangelist: List[Range]) = // sorting the list puts overlapping ranges adjacent to one another in the list // foldLeft runs a function on successive elements. it a great way to process // a list when the results are not a 1:1 mapping. rangelist.sortBy(_.from).foldLeft(List.empty[Range]) { (acc, r) => acc match { case head :: tail if head.contains(r) => // r completely contained; drop it head :: tail case head :: tail if head.contains(r.from) => // partial overlap; expand head to include both head and r Range(head.from, r.to) :: tail case _ => // no overlap; prepend r to list r :: acc } } 

Answer 3

Here is my solution:

 def merge(ranges:List[Range]) = ranges .sortWith{(a, b) => a.from < b.from || (a.from == b.from && a.to < b.to)} .foldLeft(List[Range]()){(buildList, range) => buildList match { case Nil => List(range) case head :: tail => if (head.to >= range.from) { Range(head.from, head.to.max(range.to)) :: tail } else { range :: buildList } }} .reverse merge(List(Range(1, 3), Range(4, 5), Range(10, 11), Range(1, 6), Range(2, 8))) //List[Range] = List(Range(1,8), Range(10,11))