Java 8: How to compare all elements of a Set

Question

This may be an already asked question but I don't find the answer I need.

I have a Set with objects like

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

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

I need to check whether the Set contains to elements that overlap each other. In "old-java" I would go through the set twice and check for all combinations that exist and then break or return when I find it.

How can we do this with streams and lambdas in Java 8?

I have already tried with reduction() and filter() but none of them seem to work

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

Not an answer to your question, nevertheless maybe helpful [Guava's RangeSet might be what you are looking for](https://google.github.io/guava/releases/19.0/api/docs/index.html?com/google/common/collect/RangeSet.html) — ooxi, May 27 '16 at 14:08
@Eran I read that as OP wanting a set of all elements that overlap with any other element in the set. — Cubic, May 27 '16 at 14:09
Yes @Eran I would like a boolean back. But to get a list with the overlapped elements would also be ok — iberbeu, May 27 '16 at 14:13
Since you are dealing with `Set`s--therefore order doesn't matter--and you are not modifying either `Set` in any way, you may find it advantageous to use `parallelStream()`, which may speed things up if your `Set`s are large. — dcsohl, May 27 '16 at 14:37
See this answer: http://codereview.stackexchange.com/questions/30190/find-intersections-of-overlapping-intervals — krokodilko, May 27 '16 at 14:48

score 14 · Accepted Answer · edited Feb 19 '21 at 09:50

14

As you said in your question, a possible solution is to loop over the set twice and determine if there are any overlaps. So what we need to determine is if, for any element in the set, we can find any other element that is different and overlaps with it.

With the Stream API, you could thus have the following:

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

anyMatch will determine if any elements of the stream satisfies the given condition. The code above is therefore asking if there is one o1 such that there is one o2 different than o1 (we can safely use != here since both objects are coming from the same set) and overlapping with it.

Note that this is a O(n²) implementation: the set is traversed twice. This could be possible in a single iteration: at each iteration, an union of the intervals [dateBeginning, dateEnd] is kept; if at any-time the intersection between the current interval and the accumulated union is non-void, then we know an overlap has been hit.

edited Feb 19 '21 at 09:50

catch23

17,519
42
144
217

answered May 27 '16 at 14:10

Tunaki

132,869
46
340
423

This is a very good answer! First the code works and second the possibility of doing it in one iteration is a very good point. Is there a way to do this alternative with streams? – iberbeu May 27 '16 at 14:32
For all those who try this approach let's notice that you cannot use the same stream twice: that means you need to call `set.stream()` twice as it is written in the answer. If you work directly on the stream it won't work. This won't work: `Stream<> stream = set.stream(); boolean overlap = stream.anyMatch(o1 -> stream.anyMatch(o2 -> o1 != o2 && o1.overlap(o2)));` – iberbeu May 27 '16 at 14:34
2

@iberbeu Yes, but you would have to redesign your classes a bit, starting by making an `DateInterval` class that would have a `union` and a `intersect` method. And yes, as commented above, you can't reuse the Stream, they are once-off. – Tunaki May 27 '16 at 14:36
3

I would note, as I noted on the OP, that `parallelStream()` may be advantageous here if the Sets involved are large. – dcsohl May 27 '16 at 14:39

Oleg Mikhailov · Answer 2 · 2016-05-30T14:29:03.343

An implementation of the idea with compareTo override. Use this if you need to get exactly the overlapping ranges or their number.

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 it:

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

Be aware that ranges { 1..3, 3..5 } are considered non-overlapping. To treat such cases (when endDate of one range equals startDate of another) as overlapping replace <=,>= with <,>.

It is not a very good idea to use the `Comparable`- interface for this. Problem 1: It is not really a "natural" ordering for ranges - it is not obvious for a user of the class what a "greater" range means - a longer one or a later one. 2: The order defined by this comparison is not a total ordering (There can be Ranges A, B and C such that A > B, A = C and B = C, for example). — Hulk, May 30 '16 at 08:03

score 0 · Answer 3 · edited May 23 '17 at 12:10

I may also suggest using org.apache.commons.lang3.Range class for this case and a parallelStream to gain perfomance. Combining this with Tunaki's solution we get:

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

Java 8: How to compare all elements of a Set

3 Answers3