【Guava 教學】（3）高階排序概念的實現



排名這種東西，人類還蠻愛的，到了程式設計領域，排序這東西依舊舉足輕重。在 Java 中要進行排序，可以使用標準 API 中 Collections 的 sort 方法，使用前必須遵守的協定是物件本身必須有天生的順序（Natural ordering），也就是必須擁有 Comparable 的行為，語法上具體來說，就是必須實作 Comparable 介面。由於 Collections 已經實作了排序演算法，你只需要告訴它，如果物件要與另一個物件比較時，順序上哪個大哪個小，也就是 compareTo 傳回 1、0、-1 分別來告訴它，順序上物件比另一物件大、相等或小。
用三個值來表示順序，蠻方便的，不是嗎？並不是！有多少次你弄錯了 1、0、-1 的意義呢？實際上，排序的要求還蠻多的，例如你可能想要排序時先依某人的姓來排，如果姓相同再依名來排，如果姓名都相同，再依他們居住地的郵遞區號來排，那你就可能會寫出像 compare/compareTo 中的程式碼： 
class Person implements Comparable<Person> {
  private String lastName;
  private String firstName;
  private int zipCode;

  public int compareTo(Person other) {
    int cmp = lastName.compareTo(other.lastName);
    if (cmp != 0) {
      return cmp;
    }
    cmp = firstName.compareTo(other.firstName);
    if (cmp != 0) {
      return cmp;
    }
    return Integer.compare(zipCode, other.zipCode);
  }
}
你覺得 compareTo 好讀嗎？如果你學過 SQL，應該知道有 ORDER BY 這東西，相較之下，compareTo 的邏輯並不清楚，如果你使用 Guava 的 ComparisonChain，可以寫成這樣： 
import com.google.common.collect.ComparisonChain;

class Person implements Comparable<Person> {
  private String lastName;
  private String firstName;
  private int zipCode;

  public int compareTo(Person other) {
    return ComparisonChain.start()
             .compare(lastName, other.lastName)
             .compare(firstName, other.firstName)
             .compare(zipCode, other.zipCode)
           .result();
  }
}
ComparisonChain 的 start 與 compare 都會傳回 ComparisonChain 實例，在最後 result 計算結果時，就如原先 compareTo 的實作，會逐一比較要比較的對象，只要它們各自的 compareTo 不為 0 時就傳回結果。
Guava 在排序上提供了一些 API ，確實是很好用，不過這不是這篇文章要論述的，這邊要談的是，如何觀察並抽取出程式碼中更高階的抽象概念，像是排序這樣的東西，其實也一直重複著某些模式。上例中的模式就是： 
int cmp = f1.compareTo(other.f1);
if (cmp != 0) {
  return cmp;
}
cmp = f2.compareTo(other.f2);
if (cmp != 0) {
  return cmp;
}
cmp = f3.compareTo(other.f3);
if (cmp != 0) {
  return cmp;
}
...
談到模式，物件導向的開發者都會想到設計模式，想到有關創建、結構與行為模式。實際上寫程式時也有許多流程重複著一定模式，只是因為程式碼太混亂，程式區塊混著太多職責，而觀察不出來罷了，只要你能讓每段程式流程的職責單一化，就可以觀察並抽取出更高階的語義，像是這邊就可抽取出每個 compare 的語義，而這就是 ComparisonChain 在做的事，在使用它之前，你就像是在告訴電腦低階指令，1、0、-1？這什麼東西？在使用 ComparisonChain 之後，會比較像是在跟人說話了。
程式碼太混亂，程式區塊混著太多職責，觀察不出模式，抽取不出高階抽象的另一壞處就是，沒辦法重用某些基礎元素，沒辦法基於這些元素建構更複雜的的元素，因此，每次都得撰寫重複的東西。
舉例來說，如果你不想要用物件天生的順序進行排序，那麼 Collections 的 sort 還有另一個版本，可以指定一個比較器，也就是實現了 Comparator 介面的物件，它的 compare 方法也是得傳回 1、0、-1，告訴 Collections 的 sort 兩個被傳入的元素順序為何。例如，如果有個 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;
    }
}
不怎麼好讀，對吧！更別說為了表示這個比較器的目的，必須取個又臭又長的類別名稱，雖然在必要的時候，不用去畏懼取個較長的名稱，不過名稱真的太長，長到影響可讀性，或者很難簡短地描述出它的意圖時，就得想一下，是不是它做了太多事了？
仔細想想，將 null 全部排序在前或者在後，其實是一種常見的需求，長度是個整數，本身就有由小至大的天生順序，如果要由大至小，就是反向排序，反向排序也是一個經常的需求。有沒有辦法將這些常見需求抽取出來呢？試試看！ 
class Natural implements Comparator<Comparable> {
    @Override
    public int compare(Comparable c1, Comparable c2) {
        return c1.compareTo(c2);
    }
}

class Inverse implements Comparator {
    private Comparator comparator;

    public Inverse(Comparator comparator) {
        this.comparator = comparator;
    }

    @Override
    public int compare(Object o1, Object o2) {
        return -comparator.compare(o1, o2);
    }
}

class NullsFirst implements Comparator {
    private final static int LEFT_IS_GREATER = 1;
    private final static int RIGHT_IS_GREATER = -1;

    private Comparator comparator;

    public NullsFirst(Comparator comparator) {
        this.comparator = comparator;
    }

    @Override
    public int compare(Object o1, Object o2) {
        if(o1 == o2) {
            return 0;
        }
        if(o1 == null) {
            return RIGHT_IS_GREATER;
        }
        if(o2 == null) {
            return LEFT_IS_GREATER;
        }
        return comparator.compare(o1, o2);
    }
}
Natural、Inverse、NullsFirst 都是從過去排序經驗中，不斷重現的流程模式中抽取出來的比較器，這樣一來，先前那個 StringLengthInverseNullFirstComparator 就可以基於它們來建構了： 
interface F1<P, R> {
    R apply(P p);
}

class StringLengthInverseNullFirstComparator implements Comparator<String> {
    private Comparator comparator = new NullsFirst(new Inverse(new Natural()));
    private F1<String, Integer> f = new F1<String, Integer>() {
        @Override
        public Integer apply(String p) {
            return p == null ? null : p.length();
        }
    };
    @Override
    public int compare(String s1, String s2) {
        return comparator.compare(f.apply(s1), f.apply(s2));
    }
}
好吧！難道不能傳入 F1 實例就好嗎？這麼一來，連上頭那個 compare 方法中的流程也能重用了： 
class OnResultOf<P, R> implements Comparator<P> {
    private Comparator comparator;
    private F1<P, R> f;

    public OnResultOf(F1<P, R> f, Comparator comparator) {
        this.f = f;
        this.comparator = comparator;
    }

    @Override
    public int compare(P p1, P p2) {
        return comparator.compare(f.apply(p1), f.apply(p2));
    }    
}
現在你連 StringLengthInverseNullFirstComparator 都不用定義了，可以直接建構並組合相關實例就可以進行複雜的排序了： 
List names = Arrays.asList("Monica", null, "Justin", null, "Jao");

Collections.sort(names, 
        new OnResultOf(new F1<String, Integer>() {
            @Override
            public Integer apply(String p) {
                return p == null ? null : p.length();
            }}, 
        new NullsFirst(new Inverse(new Natural())))
);
這麼一連串的抽取，達到了一些元素的重用，不過語義上並不怎麼流暢，如果比較器可以主動生出另一個比較器，可以改進一下這個問題。在繼續進行重構之前，你發現了 Guava 做了你想做的事了，那就拿來用吧！ 
Collections.sort(names, 
        Ordering.natural().reverse().nullsFirst()
                .onResultOf(new Function<String, Integer>() {
                    @Override
                    public Integer apply(String p) {
                        return p == null ? null : p.length();
                    }
               })
);
Ordering 本身就是比較器，這看看它的類別定義就知道了： 
public abstract class Ordering<T> extends Object implements Comparator<T>
不過，它是個功能強悍的比較器，可以基於目前的比較器，加上某個條件，直接產生新的 Ordering 實例，就如上面的例子中看到的，不過我承認，那個匿名類別實例語法挺惱人的，如果可以用上 JDK8 的 Lambda 語法，也許會好一些： 
Collections.sort(names, 
        Ordering.natural().reverse().nullsFirst()
            .onResultOf(p -> p == null ? null : p.length())
);
只要事物不斷重複，就會形成一種模式，若能抽取出模式，就能用更高階的語義來表述意圖。Guava 在排序這方面，某些部份就是在表現這類意涵，不僅只有排序，實際上撰寫程式時，還存在許多高階語義在程式流程之中，只是就如先前所談到的，也許是因為程式碼太混亂，或者程式區塊混著太多職責，而觀察不出來罷了，因為看不出來，所以重複的工作就一再進行，日復一日地…
Guava 看來只是個程式庫，但它實際上包括了不少高階觀念，先前的兩篇文章 從避免使用 null 開始、命名明確的條件檢查，其實也都是在談這些高階觀念，想善用 Guava，瞭解這些觀念是必要的，不然，只是當個程式庫來使用，就沒辦法用得順手，這樣是有點可惜了。 嗯？Ordering 更多的範例？其實看 API 文件應該就夠清楚了，如果你瞭解 Ordering 存在的目的的話！網路上搜尋一下 「Guava Ordering」，你可以找到一卡車的資料。好吧！我知道有些人很性急，那麼 google's guava library tutorial part 2: joys of Ordering 這個鏈結有不少簡單易懂的範例。