Java 8 partition list into groups by condition involving previous elements

Your were looking at the right place when studying the groupingBy collectors, but you are also right that they won’t provide the necessary logic for merging intervals. But they are conceptionally merging elements into the state created by previous elements. You have to implement a similar collector yourself.

Relying on your specification that the elements are already presorted by their start index, you can do it like:

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

This creates a Collection rather than a List, but you can simply create a List out of it:

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

You should do that definitely if you intend to keep the result for a longer time rather than processing it immediately, as the Collection returned by the collector is a view into a TreeMap holding more resources than necessary.

I guess, in most cases you are better off with a loop based solution.


You cannot. Streams are not suited to this sort of problem; streams have no notion of "previous elements" and are allowed to operate over elements in arbitrary order. You can do it in Java, sure, and you can do it in functional languages, but that doesn't mean streams work like the functional language data structures you're used to.