Java 8分区列表按条件涉及前面的元素

Question

假设我有一个间隔列表(按开始排序),我想将它们分解,以便我有一个重叠的间隔组列表.因此,例如,使用Intervalas:

public class Interval {
    private final int start;
    private final int end;

    public Interval(int start,int end){
        this.start = start;
        this.end = end;
    }

    public int getStart(){return start;}
    public int getEnd(){return end;}

    public String toString(){ return "("+start+","+end+")"; }
}

和之List<Interval>类似:

[(0,4),(1,7),(6,10),(13,17),(20,100),(22,31),(60,65)]

我想要一个输出List<List<Interval>>:

[[(0,4),(1,7),(6,10)],[(13,17)],[(20,100),(22,31),(60,65)]]

我可以对此进行编码,但我真的很喜欢Java 8的功能更强大的方法,并想知道是否有任何类似于使用Java 8流的惯用方法.

我已经看过提供的收集器的"分组依据"样式,但它们似乎不适用,因为我不是真的按分类器分组 - 你不能仅根据每个属性来计算组单个元素,您必须考虑与目前已计算的组相关的每个元素的属性.

当然,在函数式语言中有非疯狂的方法(虽然我说的不是一个真正的函数式程序员:-)).如何在Java 8中使用流？

Answer 1

在研究groupingBy收集器时，您正在寻找正确的位置，但您也正确地认为它们不会为合并间隔提供必要的逻辑。但它们在概念上将元素合并到由先前元素创建的状态中。您必须自己实现一个类似的收集器。

根据您的规范，元素已经按其开始索引进行了预排序，您可以这样做：

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

这将创建 aCollection而不是 a List，但您可以简单地从中创建一个List：

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

如果您打算将结果保留更长的时间而不是立即处理它，则绝对应该这样做，因为Collection收集器返回的结果是对TreeMap持有比必要更多资源的看法。

我想，在大多数情况下，您最好使用基于循环的解决方案。

Answer 2

你不能。流不适合解决这类问题；流没有“先前元素”的概念，并且允许以任意顺序对元素进行操作。当然，您可以用 Java 来实现，也可以用函数式语言来实现，但这并不意味着流可以像您习惯的函数式语言数据结构一样工作。