Как функционально объединить перекрывающиеся диапазоны номеров из списка

Question

У меня есть несколько объектов диапазона, которые мне нужно объединить, чтобы исчезли все перекрывающиеся диапазоны:

case class Range(from:Int, to:Int)

val rangelist = List(Range(3, 40), Range(1, 45), Range(2, 50), etc)

Вот диапазоны:

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

После завершения мы получим:

  1  50  
 70  90  
100 200  

Императивный алгоритм:

1. Pop () первый диапазон-obj и итерации по остальной части списка, сравнивая его с каждым из других диапазонов.
2. если есть перекрывающийся элемент, объединить их вместе (это дает новый экземпляр Range) и удалить 2 кандидатов на слияние из списка источников.
3. В конце списка добавить объект Range (который мог много раз измениться при слиянии) в список окончательных результатов.
4. Повторите это со следующим из оставшихся предметов.
5. Как только список источников пуст, мы закончили.

Для этого необходимо создать много временных переменных, проиндексированных циклов и т. Д.

Так мне интересно, есть ли более функциональный подход?

На первый взгляд, исходная коллекция должна быть в состоянии действовать как стек в обеспечении pop () PLUS. предоставляя возможность удалять элементы по индексу во время итерации по нему, но тогда это больше не будет работать.

Answer 1

Мне нравятся такие головоломки:

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

Answer 2

Попробуйте хвостовую рекурсию. (Аннотация нужна только для того, чтобы предупредить вас, если оптимизация хвостовой рекурсии не произойдет; компилятор сделает это, если сможет, аннотируете вы или нет.)

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 3

Вот мое решение:

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