Comparable 與 Comparator

在收集物件之後，對物件進行排序是常用的動作，你不用親自實作排序演算法，java.util.Collections 提供有 sort 方法，由於必須有索引才能進行排序，因此 Collections 的 sort 方法接受 List 實作物件。例如：

package cc.openhome;

import java.util.*;

public class Sort {
    public static void main(String[] args) {
        List numbers = Arrays.asList(10, 2, 3, 1, 9, 15, 4);
        Collections.sort(numbers);
        System.out.println(numbers);
    }
}

執行結果是顯示由小至大的號碼：

[1, 2, 3, 4, 9, 10, 15]

實作 Comparable

如果是以下的範例呢？

package cc.openhome;

import java.util.*;

class Account {
    private String name;
    private String number;
    private int balance;

    Account(String name, String number, int balance) {
        this.name = name;
        this.number = number;
        this.balance = balance;
    }

    @Override
    public String toString() {
        return String.format("Account(%s, %s, %d)", name, number, balance);
    } 
}

public class Sort2 {
    public static void main(String[] args) {
        List accounts = Arrays.asList(
                new Account("Justin", "X1234", 1000),
                new Account("Monica", "X5678", 500),
                new Account("Irene", "X2468", 200)
        );
        Collections.sort(accounts);
        System.out.println(accounts);
    }
}

執行結果將會很奇怪地拋出 ClassCastException？

Exception in thread "main" java.lang.ClassCastException: cc.openhome.Account cannot be cast to java.lang.Comparable
...略

如果你直接將範例的 accounts 宣告為 List<Account>，更會直接發生編輯錯誤？

要說原因，是因為你根本沒告訴 Collections 的 sort 方法，到底要根據 Account 的 name、number 或 balance 進行排序，那它要怎麼排？Collections 的 sort 方法要求被排序的物件，必須實作 java.lang.Comparable 介面，這個介面有個 compareTo 方法必須傳回大於 0、等於 0 或小於0的數，作用為何？直接來看如何針對帳戶餘額進行排序就可以瞭解：

package cc.openhome;

import java.util.*;

class Account2 implements Comparable<Account2> {
    private String name;
    private String number;
    private int balance;

    Account2(String name, String number, int balance) {
        this.name = name;
        this.number = number;
        this.balance = balance;
    }

    @Override
    public String toString() {
        return String.format("Account2(%s, %s, %d)", name, number, balance);
    }

    @Override
    public int compareTo(Account2 other) {
        return this.balance - other.balance;
    }
}

public class Sort3 {
    public static void main(String[] args) {
        List<Account2> accounts = Arrays.asList(
                new Account2("Justin", "X1234", 1000),
                new Account2("Monica", "X5678", 500),
                new Account2("Irene", "X2468", 200)
        );
        Collections.sort(accounts);
        System.out.println(accounts);
    }
}

Collections 的 sort 方法在取得 a 物件跟 b 物件進行比較時，會先 a 物件扮演（Cast）為 Comparable（也因此若物件沒實作 Comparable，將會拋出 ClassCastException，若使用了泛型宣告，編譯器會檢查出型態不符），然後呼叫 a.compareTo(b)，如果 a 物件順序上小於 b 物件，必須傳回小於 0，若順序上相等則傳回 0，若順序上 a 大於 b 傳回大於 0 的值。因此，上面的範例，將會依餘額從小到大排列帳戶物件：

[Account2(Irene, X2468, 200), Account2(Monica, X5678, 500), Account2(Justin, X1234, 1000)]

實作 Comparator

為何先前的 Sort 類別中，可以直接對 Integer 進行排序呢？若查看 API 文件，可以發現 Integer 就有實作 Comparable 介面。

實際開發總是不斷有意外，如果你的物件無法實作 Comparable 呢？也許你拿不到原始碼！也許你不能修改原始碼！舉個例子來說，String 本身有實作 Comparable，可以如下排序：

package cc.openhome;

import java.util.*;

public class Sort4 {
    public static void main(String[] args) {
        List words = Arrays.asList("B", "X", "A", "M", "F", "W", "O");
        Collections.sort(words);
        System.out.println(words);
    }
}

依 String 實作的 Comparable，將會有以下的執行結果：

[A, B, F, M, O, W, X]

如果今天想讓排序結果反過來呢？

Collections 的 sort 方法有另一個重載版本，可接受 java.util.Comparator 介面的實作物件，如果使用這個版本，排序方式將根據 Comparator 的 compare 定義來決定。例如：

import java.util.*;

class StringComparator implements Comparator<String> {
    @Override
    public int compare(String s1, String s2) {
        return -s1.compareTo(s2);
    }
}

public class Sort5 {
    public static void main(String[] args) {
        List<String> words = Arrays.asList("B", "X", "A", "M", "F", "W", "O");
        Collections.sort(words, new StringComparator());
        System.out.println(words);
    }
}

Comparator 的 compare 會傳入兩個物件，如果 o1 順序上小於 o2，必須傳回小於0的值，順序相等傳回0，順序上 o1 大於 o2 傳回大於 0 的值。

在這個範例中，由於 String 本身就是 Comparable，所以將 compareTo 傳回的值乘上 -1，就可以調換排列順序。執行結果如下：

[X, W, O, M, F, B, A]

在Java的規範中，跟順序有關的行為，通常要不物件本身是 Comparable，要不就是另行指定 Comparator 物件告知如何排序。

例如，如果想針對陣列進行排序，可以使用 java.util.Arrays 的 sort 方法，如果查詢 API 文件，會發現該方法針對物件排序時有兩個版本，一個是你收集在陣列中的物件必須是 Comparable（否則會拋出 ClassCastException），另一個版本則可以傳入 Comparator 指定排序方式。

Set 的實作類別之一 java.util.TreeSet，不僅擁有收集不重複物件之能力，還可用紅黑樹方式排序收集的物件，條件就是收集的物件必須是 Comparable（否則會拋出 ClassCastException），或者是在建構 TreeSet 時指定 Comparator 物件。

Queue 的實作類別之一 java.util.PriorityQueue 也是，收集至 PriorityQueue 的物件，會根據指定的優先權來決定物件在佇列中的順序，優先權的告知，要不就是物件必須是 Comparable（否則會拋出 ClassCastException），或者是建構 PriorityQueue 時指定 Comparator 物件。

結合 Lambda

使用 Lambda 的話，上面的範例可以更簡潔一些：

List<String> words = Arrays.asList("B", "X", "A", "M", "F", "W", "O");
Collections.sort(words, String::compareTo);

會想到這點還不錯，不過，如果你知道，List 有個 sort 方法，可接受 Comparator 實例來指定排序方式，那麼你還可以寫成：

List<String> words = Arrays.asList("B", "X", "A", "M", "F", "W", "O");
words.sort(String::compareTo);

來考慮一個更複雜的情況，如果有個 List 中某些索引處包括 null，現在你打算讓那些 null 排在最前頭，之後依字串的長度由大到小排序，那會怎麼寫？這樣嗎？

class StringLengthInverseNullFirstComparator implements Comparator<String> {
    @Override
    public int compare(String s1, String s2) {
        if(s1 == s2) {
            return 0;
        }
        if(s1 == null) {
            return -1;
        }
        if(s2 == null) {
            return 1;
        }
        if(s1.length() == s2.length()) {
            return 0;
        }
        if(s1.length() > s2.length()) {
            return -1;
        }
        return 1;
    }
}

不怎麼好讀，對吧！更別說為了表示這個比較器的目的，必須取個又臭又長的類別名稱！其實排序會有各式各樣的組合需求，Comparator 定義了一些預設方法與靜態方法，結合這些方法，可以讓程式碼寫來具有較高的可讀性。

以方才的需求為例，要建立對應的 Comparator 實例，可以如下撰寫：

package cc.openhome;

import java.util.*;
import static java.util.Comparator.*;

public class Sort6 {
    public static void main(String[] args) {
        List words = Arrays.asList("B", "X", "A", "M", null ,"F", "W", "O", null);
        // 以下也可以寫為 words.sort(nullsFirst(naturalOrder().reversed()));
        words.sort(nullsFirst(reverseOrder()));
        System.out.println(words);
    }
}

執行結果如下：

[null, null, X, W, O, M, F, B, A]

你也可能想要排序時先依某人的姓來排，如果姓相同再依名來排，如果姓名都相同，再依他們居住地的郵遞區號來排，那麼你可以如下建立 Comparator：

package cc.openhome;

import java.util.*;
import static java.util.Comparator.*;
 
public class Person {
    private String firstName;
    private String lastName;
    private Integer zipCode;
    
    public Person(String firstName, String lastName, Integer zipCode) {
        this.firstName = firstName;
        this.lastName = lastName;
        this.zipCode = zipCode;
    }
    
    public String toString() {
        return String.format("Person(%s %s, %d)", firstName, lastName, zipCode);
    }
    
    public static void main(String[] args) {
        List persons = Arrays.asList(
            new Person("Justin", "Lin", 804),
            new Person("Monica", "Huang", 804),
            new Person("Irene", "Lin", 804)
        );
        
        persons.sort(
            Comparator.<Person, String>comparing(p -> p.lastName)
               .thenComparing(p -> p.firstName)
               .thenComparing(p -> p.zipCode)
        );
        
        System.out.println(persons);
    }
}

執行結果如下：

[Person(Monica Huang, 804), Person(Irene Lin, 804), Person(Justin Lin, 804)]

單就這邊範例的閱讀來說，sort 時比較的是 lastName、接著是 firstName，接著是 zipCode，目的一目瞭然，至於 comparing 方法接受的型態是什麼？答案是 Function 型態！關於這類型態的細節，將留在後面的篇幅說明。