Jak funkcjonalnie połączyć nakładających numer waha się od listy

Question

mam szereg piecyk obiektów, które muszę połączyć tak, że wszystkie zachodzące na siebie zakresy zniknąć:

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

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

Oto zakresy:

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

Po zakończeniu dostaniemy:

1 50 
70 90 
100 200 

Imperatyw algorytmu:

1. Pop() pierwszy zakres-obj i iteracja przez resztę listy, porównując go z każdym z pozostałych zakresów.
2. jeśli występuje nakładający się element, scal je razem (To daje nową instancję zasięgu) i usuń 2 kandydatów scalających z listy źródłowej.
3. Na końcu listy dodaj obiekt Range (który mógł się wiele razy zmienić poprzez scalenie) do listy końcowych wyników.
4. Powtórz to z następną z pozostałych pozycji.
5. Gdy lista źródeł jest pusta, skończyliśmy.

Aby to zrobić koniecznie trzeba stworzyć wiele zmiennych tymczasowych, indeksowane pętle itd

Więc zastanawiam się, czy jest podejście bardziej funkcjonalne?

Na pierwszy rzut oka, kolekcja źródłowa musi być w stanie działać jak Stack w dostarczaniu pop() PLUS dając możliwość usuwania elementów poprzez indeks podczas iteracji nad nim, ale wtedy to nie byłoby już funkcjonalne.

Answer 1

Spróbuj ogon rekurencji. (Adnotacja jest potrzebna tylko po to, aby ostrzec cię, jeśli optymalizacja rekursji ogona się nie powiedzie, kompilator zrobi to, jeśli potrafi, niezależnie od tego, czy napiszesz adnotację, czy nie).

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

Uwielbiam te rodzaje łamigłówek:

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 3

Oto moje rozwiązanie:

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