Elenco di partizioni Java 8 in gruppi in base a elementi precedenti

Question

Supponiamo di avere un elenco di intervalli (ordinati per inizio) e di suddividerli in modo da avere un elenco di gruppi di intervalli sovrapposti. Così, per esempio, con Interval come:

public class Interval { 
    private final int start; 
    private final int end; 

    public Interval(int start,int end){ 
     this.start = start; 
     this.end = end; 
    } 

    public int getStart(){return start;} 
    public int getEnd(){return end;} 

    public String toString(){ return "("+start+","+end+")"; } 
} 

E un List<Interval> come:

[(0,4),(1,7),(6,10),(13,17),(20,100),(22,31),(60,65)] 

voglio una potenza di List<List<Interval>>:

[[(0,4),(1,7),(6,10)],[(13,17)],[(20,100),(22,31),(60,65)]] 

posso codice questo in su, ma io Mi sto davvero godendo l'approccio più funzionale di Java 8 e voglio sapere se c'è qualcosa di simile a un modo idiomatico per farlo usando i flussi Java 8.

Ho dato uno sguardo agli stili "raggruppati" di Collectors forniti, ma non sembrano applicabili poiché non sto realmente raggruppando per un classificatore- non è possibile calcolare i gruppi basati solo su una proprietà di ogni singolo elemento, devi considerare le proprietà di ogni elemento in relazione ai gruppi che sono stati calcolati finora.

Certamente non esiste un modo non folle di farlo in linguaggi funzionali (anche se parlo come qualcuno che non è realmente un programmatore funzionale :-)). Come posso farlo con i flussi in Java 8?

Answer 1

Non è possibile. Gli stream non sono adatti a questo tipo di problema; i flussi non hanno nozione di "elementi precedenti" e sono autorizzati a operare su elementi in ordine arbitrario. Puoi farlo in Java, certo, e puoi farlo in linguaggi funzionali, ma ciò non significa che gli stream funzionino come le strutture dati del linguaggio funzionale a cui sei abituato.

Answer 2

Stavo cercando il posto giusto quando studi i collettori groupingBy, ma hai anche ragione che non forniranno la logica necessaria per gli intervalli di fusione. Ma sono elementi concettualmente fondenti nello stato creato da elementi precedenti. Devi implementare un collezionista simile tu stesso.

Contando sulla vostra specifica che gli elementi sono già preordinati dal loro indice di partenza, si può fare come:

Comparator<Interval> byStart = Comparator.comparingInt(Interval::getStart); 
Comparator<Interval> byEnd = Comparator.comparingInt(Interval::getEnd); 
Collection<List<Interval>> merged = intervalList.stream().collect(
     () -> new TreeMap<Interval,List<Interval>>(byStart), 
     (map,i) -> { 
      Map.Entry<Interval,List<Interval>> e=map.floorEntry(i); 
      if(e!=null && Collections.max(e.getValue(), byEnd).getEnd()>=i.getStart()) 
       e.getValue().add(i); 
      else map.computeIfAbsent(i, x->new ArrayList<>()).add(i); 
     }, 
     (m1,m2) -> m2.forEach((i,list) -> { 
      Map.Entry<Interval,List<Interval>> e=m1.floorEntry(i); 
      if(e!=null && Collections.max(e.getValue(), byEnd).getEnd()>=i.getStart()) 
       e.getValue().addAll(list); 
      else m1.put(i, list); 
     }) 
    ).values(); 

Questo crea un Collection piuttosto che un List, ma si può semplicemente creare un List fuori iT:

List<List<Interval>> list = new ArrayList<>(merged); 

si dovrebbe fare che sicuramente se avete intenzione di mantenere il risultato per un tempo più lungo, piuttosto che il trattamento subito, come il Collection restituito dal raccoglitore è una vista in un TreeMap in possesso di più risorse del necessario.

Immagino che nella maggior parte dei casi si stia meglio con una soluzione basata su loop.