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.