Java 8: Wie man alle Elemente eines Sets vergleicht

Question

Das mag eine schon gestellte Frage sein, aber ich finde die Antwort nicht, die ich brauche.

Ich habe ein Set mit Objekten wie

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

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

Ich muss überprüfen, ob die Set-Elemente enthält, die einander überlappen. In "old-java" würde ich zweimal durch das Set gehen und nach allen existierenden Kombinationen suchen und dann brechen oder zurückkehren, wenn ich es finde.

Wie können wir dies mit Streams und Lambdas in Java 8 tun?

ich bereits versucht haben, mit reduction() und filter() aber keiner von ihnen scheinen

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

Answer 1

zu arbeiten, wie Sie in Ihrer Frage gesagt, eine mögliche Lösung ist zweimal über den Satz zu Schleife und festzustellen, ob es irgendwelche Überschneidungen . Was wir also bestimmen müssen, ist, ob wir für jedes Element in der Menge ein anderes Element finden können, das anders ist und sich damit überschneidet.

Mit dem Stream-API, könnten Sie damit folgende Voraussetzungen erfüllt sein:

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

anyMatch bestimmen, ob irgendwelche Elemente des Stroms die gegebene Bedingung erfüllt. Der obige Code fragt daher, ob es einen o1 gibt, so dass es einen o2 gibt, der sich von o1 unterscheidet (wir können != hier sicher verwenden, da beide Objekte aus demselben Satz stammen) und sich damit überschneiden.

Beachten Sie, dass dies eine O (n²) Implementierung ist: Der Satz wird zweimal durchlaufen. Dies könnte in einer einzigen Iteration möglich sein: Bei jeder Iteration wird eine Vereinigung der Intervalle [dateBeginning, dateEnd] beibehalten; Wenn zu irgendeinem Zeitpunkt der Schnittpunkt zwischen dem aktuellen Intervall und der akkumulierten Vereinigung nicht void ist, dann wissen wir, dass eine Überlappung getroffen wurde.

Answer 2

Eine Implementierung der Idee mit compareTo überschreiben. Verwenden Sie dies, wenn Sie exakt die überlappenden Bereiche oder deren Anzahl benötigen.

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

Testing es:

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

Beachten Sie, dass Bereiche {1..3, 3..5} gelten als nicht überlappen. Um solche Fälle zu behandeln (wenn endDate von einem Bereich gleich startDate eines anderen ist) als überlappend ersetzen <=, >= mit <, >.

Answer 3

Ich kann auch vorschlagen, org.apache.commons.lang3.Range Klasse für diesen Fall und eine parallelStream zu verwenden, um Leistung zu gewinnen. In Kombination mit Tunaki's solution erhalten wir:

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