1

我有一组具有名称（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]

我错过了什么？

4

3 回答 3

2

您遗漏了几件事（以更难修复的顺序，从更容易的顺序开始）：

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

您可以通过在返回之前检查thison的依赖关系并使用for tie-break来相对轻松地修复前两个。o1a.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);
}

第三个可以通过切换到一个数组来修复，并且只有在所有插入完成后才对其进行排序。

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

于 2013-04-21T11:20:09.100 回答
0

如果有人感兴趣，这就是它的工作原理 - 最后（感谢 dasblinkenlight）：

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

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

/**
 *
 * @author Krusty
 */
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 {
                if (o.b.isEmpty() && b.isEmpty()) {
                    return a.compareTo(o.a);
                } else
                if (o.b.isEmpty() || b.isEmpty()) {
                    return b.isEmpty() ? -1 : 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");
        }}));

        // Cycle
        /*
        tos.add(new Foo.TestOrder("a", new HashSet<String>() {{
            add("e");
        }}));
        */
        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());
        }*/

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

    public static Set<TestOrder> sort(Set<TestOrder> tos) {
        Set<TestOrder> sorted = new LinkedHashSet<>();
        Set<String> cache = new LinkedHashSet<>();
        Set<TestOrder> cycles = new LinkedHashSet<>();
        Set<String> cycache = new LinkedHashSet<>();

        Iterator<TestOrder> it;
        while ((it = tos.iterator()).hasNext()) {
            TestOrder to = it.next();
            if (to.b.isEmpty())  {
                sorted.add(to);
                cache.add(to.a);
                it.remove();
            } else if (cache.containsAll(to.b)) {
                sorted.add(to);
                cache.add(to.a);
                it.remove();
            } else if (cycache.containsAll(to.b)) {
                cycles.add(to);
                cycache.add(to.a);
                it.remove();
            } else {
                cycles.add(to);
                cycache.add(to.a);
                it.remove();
            }
        }

        System.err.println("cycles");
        for (TestOrder to : cycles) {
            System.err.println(to.toString());
        }

        return sorted;
    }
}
于 2013-04-21T14:07:30.780 回答
0

您的比较方法在空集和不包含字符串“a”的集之间没有区别。这种比较方法

    public int compareTo(TestOrder o) {
        if (o.b.contains(a)) {
            return -1;
        } else {
            if (o.b.isEmpty() && b.isEmpty()) {
                return a.compareTo(o.a);
            } else
            if (o.b.isEmpty() || b.isEmpty()) {
                return b.isEmpty() ? -1 : 1;
            } else {
                return 1;
            }
        }
    }

会给出结果

c - []
d - []
b - [d, c]
a - [b, c]
e - [a]
于 2013-04-21T11:54:40.427 回答