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，并且使用a.compareTo(o.a)领带破之前修复前两个比较容易通过检查o的this的依赖。

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集合框架中解决这个问题。

Answer 2

您的比较方法在空集和不包含字符串“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] 

Answer 3

如果有人有兴趣，这是它的工作原理 - 最后（感谢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; 
    } 
}