java - 按递归依赖关系排序的具有可比较性的 TreeSet

Question

我有一组具有名称 (a) 和依赖项 (b) 的对象。我想以解决所有先前依赖关系的方式对对象进行排序。所以我有这个代码:

import java.util.HashSet;
import java.util.Set;
import java.util.TreeSet;

public class Foo {
    static class TestOrder implements Comparable<TestOrder> {
        private final String a;
        private final Set<String> b;

        public TestOrder(String a, Set<String> b) {
            this.a = a;
            this.b = b;
          }

        public int compareTo(TestOrder o) {
            if (o.b.contains(a)) 
              return -1;
            else
              return 1;
        }

        @Override
        public int hashCode() {
            return a.hashCode();
        }

        @Override
        public boolean equals(Object obj) {
            return a.equals(obj);
        }

        public String toString() {
            return a + " - " + b.toString();
        }
    }

    public static void main(String[] args) {
        Set<TestOrder> tos = new TreeSet<>();
        tos.add(new Foo.TestOrder("a", new HashSet<String>() {{
            add("b");
            add("c");
        }}));

        tos.add(new Foo.TestOrder("e", new HashSet<String>() {{
            add("a");
        }}));

        tos.add(new Foo.TestOrder("b", new HashSet<String>() {{
            add("d");
            add("c");
        }}));

        tos.add(new Foo.TestOrder("c", new HashSet<String>() {{ }}));
        tos.add(new Foo.TestOrder("d", new HashSet<String>() {{ }}));

        for (TestOrder to : tos) {
            System.out.println(to.toString());
        }
    }
}

结果是:

c - []
b - [d, c]
a - [b, c]
e - [a]
d - []

但是 - 由于 b 取决于 d - 预期结果是:

c - []
d - []
b - [d, c]
a - [b, c]
e - [a]

我错过了什么？

Answer 1

您遗漏了几件事(按照较难修复的顺序，从较容易的开始):

1. 即使将相同的对象传递给它，您的比较器也永远不会返回零，
2. 当两个对象都不依赖于另一个对象时，就没有明确的决胜局，
3. 在树集中插入对象时，并非所有项目都可用；但是，插入单个新项目可能会更改其他项目的相对顺序。
4. 排序仅考虑直接依赖关系。

您可以通过在返回 1 之前检查 this 对 o 的依赖关系并使用 a 相对轻松地修复前两个问题.compareTo(o.a) 用于打破平局。

public int compareTo(TestOrder o) {
    if (o.b.contains(a)) 
      return -1;
    else if (b.contains(o.a))
      return 1;
    else
      return a.compareTo(o.a);
}

第三个问题可以通过切换到数组并仅在所有插入完成后对其进行排序来修复。

然而，最后一个非常糟糕:为了修复它，每个项目都需要了解集合的其余部分。我没有看到解决这个问题的好方法，所以我建议使用传统的 topological sorting algorithm来排序你的依赖项，而不是试图将这个问题硬塞到 Java 集合的框架中。