排序家長和孩子的使用Java

Question

我有一個「項目」類，它包含以下字段（簡稱）：身份證（與商品相關的表的SQL Server上的主鍵），描述，序列（非空整數），並鏈接（父對象的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

考慮您的數據結構是樹（與null作爲根節點），沒有循環：

你，直到你找到一個共同的祖先走了樹都o1和o2。一旦你這樣做，退一步沿着兩個分支找到它們的相對順序（與Sequence）

尋找共同的祖先可能會非常棘手的事，我不知道這是否線性時間是可能的， 但肯定有可能在O（n日誌n）時間（與n的分支的長度）

Answer 2

新的答案：我不認爲你想要一個比較器來控制完整的排序，因爲當你需要排序的孩子父級的順序，並且您無法從比較器中輕鬆或自然地訪問它。

相反，我建議在多個步驟的排序：

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

Answer 3

鑑於層次結構中只有兩層，這歸結爲經典的多層排序。根據link字段是否爲空來區分父項目和子項目兩種。訣竅是每個級別的排序不在特定的領域。相反，排序的價值取決於它是什麼樣的項目。

第一級排序應該在父級值上。父項的父項值是其順序，但子項的父項值是其鏈接到的父項的順序。子項目通過其ID連接於母公司的項目，所以我們需要做的第一件事是建立從ID的地圖測序父節點的值：

Map<Integer, Integer> idSeqMap = 
     list.stream() 
      .filter(it -> it.getLink() == null) 
      .collect(Collectors.toMap(Item::getId, Item::getSequence)); 

（假設ID是唯一的，這是合理的，因爲它們與表主鍵相關。）

現在我們有了這張圖，可以編寫一個lambda表達式，從該項中獲取適當的父值。 （這是假設所有非空鏈接值指向現有項目），這是如下：

(Item it) -> it.getLink() == null ? it.getSequence() : idSeqMap.get(it.getLink()) 

排序應該是對孩子價值的第二個層次。父項的子值爲空，因此在任何非空值之前需要對空值進行排序。兒童項目的孩子價值是其順序。爲讓孩子值lambda表達式是：

(Item it) -> it.getLink() == null ? null : it.getSequence() 

現在，我們可以使用這些用Java 8中引入的Comparator輔助函數的結果可以直接傳遞到List.sort()方法結合起來。

list.sort(Comparator.comparingInt((Item it) -> it.getLink() == null ? it.getSequence() : idSeqMap.get(it.getLink())) 
        .thenComparing((Item it) -> it.getLink() == null ? null : it.getSequence(), 
            Comparator.nullsFirst(Integer::compare)) 
        .thenComparingInt(Item::getId)); 

第一級排序非常簡單;只需將第一個lambda表達式（提取父值）傳遞給Comparator.comparingInt即可。

第二級排序有點棘手。我假設getLink()的結果是可空的Integer。首先，我們必須使用第二個lambda表達式來提取子值。這會導致一個可爲空的值，所以如果我們通過thenComparing，我們會得到一個NullPointerException。相反，thenComparing允許我們傳遞一個輔助比較器。我們將用它來處理空值。對於該二次比較我們通過

Comparator.nullsFirst(Integer::compare) 

此相比Integer對象，用空值排序第一，以及使用該方法Integer.compare反過來相比非空值。

最後，我們比較ID值作爲最後的手段。如果您僅將此比較器用於排序，則此選項是可選的;重複將會彼此相鄰。但是如果你使用這個比較器作爲TreeSet，你需要確保不同的項目永遠不會比較等於。據推測，數據庫ID值足以區分所有獨特的項目。