java - 使用 Java 对 parent 和 child 进行排序

Question

我有一个“Item”类，其中包含以下字段(简而言之):id(与 SQL Server 上 Item 表的主键相关)、描述、序列(非空整数)和链接(a对父对象 id 的引用)，可以为 null)

我想使用 Java 进行排序，如下所示:

Id    Sequence   Link    Description
1     1          null    Item A
99    ..1        1       Son of A, first of the sequence
57    ..2        1       Son of A, second of the sequence
66    ..3        1       Son of A, third of the sequence
2     2          null    Item B
3     3          null    Item C
...

(我放置点是为了更好地可视化)

也就是说，我希望某个项目的子项直接位于其父项下方，按“序列”字段排序。

我尝试使用比较器，但失败了:

public class SequenceComparator implements Comparator<Item> {
    @Override
    public int compare(Item o1, Item o2) {
        String x1 = o1.getSequence().toString();
        String x2 = o2.getSequence().toString();
        int sComp = x1.compareTo(x2);

        if (sComp != 0) {
            return sComp;
        } else {
            x1 = o1.getLink().toString();
            x2 = o2.getLink() == null?"":o2.getLink().toString();
            return x1.compareTo(x2);
        }
    }
}

我怎样才能做到这一点？

Answer 1

新答案:我认为您不希望一个比较器来控制完整的排序，因为在对子项进行排序时，您需要父级的序列，并且您无法从比较器内轻松或自然地访问该序列.

相反，我建议分几个步骤进行排序:

1. 按父项将项分组。因此，一组将是 id 为 1 的项目及其所有子项目。没有子项的项目将单独位于一个组中。
2. 对每个组进行排序，使父级排在前面，然后按正确的顺序排列所有子级。
3. 按父级的顺序对组进行排序。
4. 将排序后的组连接到一个列表中。

像这样，使用 Java 8 流和 List.sort():

    // group by parent id
    Map<Integer, List<Item>> intermediate = input.stream()
            .collect(Collectors.groupingBy(i -> i.getLink() == null ? Integer.valueOf(i.getId()) : i.getLink()));

    // sort each inner list so that parent comes first and then children by sequence
    for (List<Item> innerList : intermediate.values()) {
        innerList.sort((i1, i2) -> {
            if (i1.getLink() == null) { // i1 is parent
                return -1; // parent first
            }
            if (i2.getLink() == null) {
                return 1;
            }
            return i1.getSequence().compareTo(i2.getSequence());
        });
    }

    // sort lists by parent’s sequence, that is, sequence of first item
    List<Item> result = intermediate.values().stream()
            .sorted(Comparator.comparing(innerList -> innerList.get(0).getSequence()))
            .flatMap(List::stream)
            .collect(Collectors.toList());

输出为(省略项目描述):

 1 1   null
99 ..1 1
57 ..2 1
66 ..3 1
 2 2   null
 3 3   null

(此输出是使用 toString 方法生成的，该方法在将具有父项的项目转换为 String 时打印点。)

如果您无法使用 Java 8，我仍然相信上述步骤的总体思路是可行的，只是某些步骤需要更多代码。

我删除了之前的答案，因为我误解了有关 getLink() 返回内容的部分，然后认为该答案不值得尝试挽救。

编辑:

我实际上忽略了Collectors.groupingBy()文档中的这一部分:“无法保证返回的...List对象的...可变性”。它仍然适用于我的 Java 8。如果列表的不变性应阻止排序，解决方案是创建一个包含相同项目的新 ArrayList。

感谢 Stuart Marks 的启发，用于对内部列表进行排序的比较器不必像上面那样笨拙。排序可以用这种简洁的方式编写:

        innerList.sort(Comparator.comparing(itm -> itm.getLink() == null ? null : itm.getSequence(),
                Comparator.nullsFirst(Integer::compare)));