Come unire funzionalmente sovrapposte numero-range da un elenco

Question

Ho un certo numero di range-oggetti che ho bisogno di unire in modo che tutti gli intervalli sovrapposti scompaiono:

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

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

Ecco l'gamme:

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

una volta finito otterremmo:

1 50 
70 90 
100 200 

imperativo Algoritmo:

0.123.

1. Pop() il primo intervallo-oggetto e scorrere il resto dell'elenco confrontandolo con ciascuno degli altri intervalli.
2. se è presente un elemento sovrapposto, unire insieme (questo produce una nuova istanza di intervallo) ed eliminare i 2 candidati di unione dall'elenco di origine.
3. Alla fine dell'elenco aggiungere l'oggetto Range (che potrebbe essere stato modificato numerose volte mediante fusione) all'elenco dei risultati finali.
4. Ripeti l'operazione con il prossimo degli articoli rimanenti.
5. Una volta che l'elenco delle fonti è vuoto, abbiamo finito.

Per fare questo si deve imperativamente creare un sacco di variabili temporanee, cicli ecc indicizzati

Quindi mi chiedo se c'è un approccio più funzionale?

A prima vista la raccolta di origini deve essere in grado di comportarsi come una pila fornendo pop() PLUS dando la possibilità di eliminare elementi per indice mentre si esegue iterazione su di esso, ma in tal caso non sarebbe più funzionale.

Answer 1

Try coda ricorsione. (L'annotazione è necessaria solo per avvisarti se l'ottimizzazione coda-ricorsione non avviene, il compilatore lo farà se può annotarlo o meno.)

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

mi piace questo tipo di puzzle:

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

Ecco la mia soluzione:

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