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; 
    } 
}