Java 8: Come confrontare tutti gli elementi di un Set

Question

Questa potrebbe essere una domanda già posta ma non trovo la risposta di cui ho bisogno.

Ho una serie di oggetti, come

public class MyObject { 
    private LocalDate dateBeginning; 
    private LocalDate dateEnd; 

    public boolean overlap(MyObject otherDate) { /*code to check overlapping*/ } 
} 

ho bisogno di controllare se il set contiene agli elementi che si sovrappongono l'un l'altro. In "old-java" passerei due volte il set e controllerò tutte le combinazioni esistenti e poi interromperò o restituirò quando lo trovo.

Come possiamo farlo con stream e lambda in Java 8?

Ho già provato con reduction() e filter() ma nessuno di loro sembra funzionare

.filter((obj1, obj2) -> { if (obj1.overlap(obj2)) return true;}) //doesn't work 

Answer 1

Come ha detto nella sua interrogazione, una possibile soluzione è quella di un loop all'interno di set di due volte e determinare se ci sono delle sovrapposizioni . Quindi quello che dobbiamo determinare è se, per ogni elemento nel set, possiamo trovare qualsiasi altro elemento che è diverso e si sovrappone ad esso.

Con l'API Stream, è avrebbe così la seguente:

boolean overlap = set.stream().anyMatch(o1 -> set.stream().anyMatch(o2 -> o1 != o2 && o1.overlap(o2))); 

anyMatch determinerà se tutti gli elementi del flusso soddisfa la condizione data. Il codice sopra chiede quindi se c'è uno o1 tale che ci sia uno o2 diverso da o1 (possiamo tranquillamente usare != qui poiché entrambi gli oggetti provengono dallo stesso set) e sovrapposti ad esso.

Si noti che questa è un'implementazione O (n²): il set viene attraversato due volte. Questo potrebbe essere possibile in una singola iterazione: ad ogni iterazione, viene mantenuta un'unione degli intervalli [dateBeginning, dateEnd]; se in qualsiasi momento l'intersezione tra l'intervallo corrente e l'unione accumulata non è nulla, allora sappiamo che è stata colpita una sovrapposizione.

Answer 2

Un'implementazione dell'idea con sostituzione di compareTo. Usalo se hai bisogno di ottenere esattamente gli intervalli sovrapposti o il loro numero.

public class Range implements Comparable<Range> { 
    private LocalDate startDate; 
    private LocalDate endDate; 

    public Range(LocalDate startDate, LocalDate endDate) { 
     this.startDate = startDate; 
     this.endDate = endDate; 
    } 

    @Override 
    public int compareTo(Range range) { 
     if (range.endDate.compareTo(endDate) >= 0 && range.startDate.compareTo(endDate) >= 0) return 1; 
     if (range.endDate.compareTo(startDate) <= 0 && range.startDate.compareTo(startDate) <= 0) return -1; 
     return 0; 
    } 
} 

provarla:

LocalDate May1 = LocalDate.of(2016, 5, 1); 
LocalDate May3 = LocalDate.of(2016, 5, 3); 
LocalDate May5 = LocalDate.of(2016, 5, 5); 
LocalDate May7 = LocalDate.of(2016, 5, 7); 
LocalDate May9 = LocalDate.of(2016, 5, 9); 

Set<Range> ranges = new HashSet<>(); 

ranges.add(new Range(May1, May5)); 
ranges.add(new Range(May3, May7)); 
ranges.add(new Range(May7, May9)); 

Set filteredRanges = ranges.stream().collect(Collectors.toCollection(TreeSet::new)); 
long totalOverlaps = ranges.size() - filteredRanges.size(); 
System.out.println(totalOverlaps + " overlapping range(s)"); 

essere consapevoli del fatto che gli intervalli {} 1..3, 3..5 sono considerati non sovrapposte. Per trattare tali casi (quando endDate di un intervallo è uguale a startDate di un altro) come sovrapposto sostituire <=, >= con <, >.

Answer 3

Posso anche suggerire di utilizzare la classe org.apache.commons.lang3.Range per questo caso e un parallelStream per ottenere perfomance. Combinando questo con Tunaki's solution otteniamo:

Set<Range> ranges = new HashSet<>(); 
ranges.add(Range.between(LocalDate.of(2016, 5, 1), LocalDate.of(2016, 5, 5))); 
ranges.add(Range.between(LocalDate.of(2016, 5, 3), LocalDate.of(2016, 5, 7))); 

boolean overlap = ranges.parallelStream().anyMatch(
       o1 -> ranges.parallelStream() 
         .anyMatch(o2 -> o1 != o2 && o1.isOverlappedBy(o2)) 
); 

System.out.println("overlap = " + overlap);