Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How to functionally merge overlapping number-ranges from a List

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.

like image 845
recalcitrant Avatar asked Feb 09 '12 21:02

recalcitrant


2 Answers

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))
like image 93
Rex Kerr Avatar answered Sep 24 '22 01:09

Rex Kerr


I love these sorts of puzzles:

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's 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
    }
  }
like image 44
leedm777 Avatar answered Sep 22 '22 01:09

leedm777