SwiftとJavaにおける同一判定/等値判定/比較/順序


Swiftの `Equatable` と `Comparable` に詳しくなることを目的とした記事です。せっかくなのでJavaと比べてみます。

SwiftもJavaも強い静的片付けです。 `1` は `"1"` じゃないです。Swiftは参照型と値型があってJavaも参照型とプリミティブ型があります。でもSwiftでは「 `String` を `==` で比較しちゃった＞＜」なんて言いません。どこがどう同じで違うのか見ていきます。

確認していく項目は

* 同一判定
* 等値判定
  * nullの扱い
  * ハッシュ値の扱い
  * 他の型との比較
* クラスへの順序付け
  * 等値判定との一貫性
  * nullの扱い
  * 他の型との比較
* コレクションへの順序付け
  * 等値判定との一貫性
  * nullの扱い
  * 他の型との比較
* assertメソッドでの判定

です。

# Swift

## 同一判定

 `===` 演算子を利用する。 `AnyObject` 同士の比較で、 `Equatable` 等を実装しなくても使える。

```swift
public func === (lhs: AnyObject?, rhs: AnyObject?) -> Bool {
  switch (lhs, rhs) {
  case let (l?, r?):
    return Bool(Builtin.cmp_eq_RawPointer(
        Builtin.bridgeToRawPointer(Builtin.castToUnknownObject(l)),
        Builtin.bridgeToRawPointer(Builtin.castToUnknownObject(r))
      ))
  case (nil, nil):
    return true
  default:
    return false
  }
}
```

`===` はEquatable.swiftにいる。

## 等値判定

`Equatable` を実装した型のみが等値判定を行える。
(error: binary operator '==' cannot be applied)

```swift
public protocol Equatable {
  static func == (lhs: Self, rhs: Self) -> Bool
}
```

`Equatable` を実装する場合は代替可能性を保つように実装するべきである。互いに等しい2つのインスタンスは、その値を用いるコードで互換性を持つということである。従って、 `==` は型の可視的な側面を全て考慮するべきである。 `Equatable` な型はclass identify以外の無価値な側面を公開すべきでないし、公開されているものは全てドキュメントに記すべきである。

`Equatable` ならば以下の性質を満たさなければならない。

* 反射性( `a == a` は常にtrue )
* 対称性( `a == b` ならば `b == a` )
* 推移性( `a == b` かつ `b == c` ならば `a == c` )

さらに、 `a != b` は `!(a == b)` である必要がある。これは標準ライブラリ側で満たしている。

```swift
extension Equatable {
  @_transparent
  public static func != (lhs: Self, rhs: Self) -> Bool {
    return !(lhs == rhs)
  }
}
```

### nilの扱い

`Optional<T>` 自身は `Equatable` ではないが、 `Equatable` のものとは別に `==` がいくつか用意されている。どの `==` が使われるかはTが `Equatable` かどうかで定まる。

Tが `Equatable` であるような `Optional<T>` とnilを比較した場合は次の `==` が使われる。

```swift
@_inlineable
public func == <T: Equatable>(lhs: T?, rhs: T?) -> Bool {
  switch (lhs, rhs) {
  case let (l?, r?):
    return l == r
  case (nil, nil):
    return true
  default:
    return false
  }
}
```

Tが `Equatable` でないような `Optional<T>` とnilを比較する場合、

```swift
@_transparent
public func == <T>(lhs: T?, rhs: _OptionalNilComparisonType) -> Bool {
  switch lhs {
  case .some(_):
    return false
  case .none:
    return true
  }
}
```

を使用する。 `_OptionalNilComparisonType` は `Equatable` でないTでもnilと比較できるようにするもので、true/falseの判定処理そのものには使われない。

Tとnilを比較することもできるがwarningの扱い。
(warning: comparing non-optional value of type to nil always returns false)

### ハッシュ値の扱い

`Hashable` を実装することで `Dictionary` のキーになれる。
`Hashable` は `Equatable` を継承している。

```swift
public protocol Hashable : Equatable {
    var hashValue: Int { get }
}
```

任意の2つのオブジェクトa、bについて、 `a == b` ならば `a.hashValue == b.hashValue` である必要がある。 `a.hashValue == b.hashValue` の時に `a == b` である必要はない。


### 他の型との比較

`Self` により同じ型同士の比較に限定されている。

## 型への順序付け

型への順序付けは `Comparable` を実装することにより行う。 `Array` にはソートメソッドがいくつかあるが、 `mutating func sort()` / `func sorted() -> [Element]` を行えるのは `Element` が `Comparable` の時のみである。

```swift
public protocol Comparable : Equatable {
  static func < (lhs: Self, rhs: Self) -> Bool
  static func <= (lhs: Self, rhs: Self) -> Bool
  static func >= (lhs: Self, rhs: Self) -> Bool
  static func > (lhs: Self, rhs: Self) -> Bool
}
```

4つのメソッドが定められているが、 `Equatable` の `==` と `<` を実装すれば残りの3つもカバーされるようになっている。

```swift
extension Comparable {
  public static func > (lhs: Self, rhs: Self) -> Bool {
    return rhs < lhs
  }
  public static func <= (lhs: Self, rhs: Self) -> Bool {
    return !(rhs < lhs)
  }
  public static func >= (lhs: Self, rhs: Self) -> Bool {
    return !(lhs < rhs)
  }
}
```

これにより、 `a == b` / `a < b` / `b < a` のどれか1つだけが必ずtrueになる。

また、狭義の全順序が必ず成り立つ。

* 非反射性( `a < a` は常にfalse)
* 非対称性( `a < b` ならば `!(b < a)`)
* 推移性( `a < b` かつ `b < c` ならば `a < c`)

実装側の型は、例外として扱われて比較の対象にならないような値を含む場合があるが、そのような値を狭義の全順序の中で扱う必要はない。
`FloatingPoint.nan` はどのように比較してもfalseを返す。

```swift
1.21 > Double.nan        // false
1.21 < Double.nan        // false
1.21 = Double.nan        // false
Double.nan == Double.nan // false

Double.nan.isNaN         // true
```

位置付けとしてはデフォルトの比較方法の定義で、あとで紹介する `areInIncreasingOrder` を使えば自由なソートが可能である。

### 等値判定との一貫性

あり。 `Comparable` は `Equatable` を継承している。等号があって初めて不等号の話ができる。

### nilの扱い

nilとの比較になることはない。

ちなみに、 `Optional` への `Comparable` の実装は可能だが、 `Optional where Wrapped: Equatable` のような制約付きのものに対してprotocol実装を行うことはできない。
(error: extension with constraints cannot have an inheritance clause)


### 他の型との比較

`Self` により同じ型同士の比較に限定されている。

## `Array` への順序付け

`(Element, Element) throws -> Bool` を用意することでその場に即したソートができる。

```swift
mutating func sort(by areInIncreasingOrder: (Element, Element) throws -> Bool) rethrows
```

ただし狭義の弱順序が成り立っていなければならない。

* 非反射性( `areInIncreasingOrder(a, a)` は常にfalse)
* 推移比較可能性( `areInIncreasingOrder(a, b)` かつ `areInIncreasingOrder(b, c)` ならば `areInIncreasingOrder(a, c)`)
* 推移不能性(aとbが比較不能でbとcが比較不能ならばaとcも比較不能)

### 等値判定との一貫性

制限なし。実装に依存する。

### nilの扱い

制限なし。実装すれば `Array<Optional<T>>` のソートも可能。

### 他の型との比較

`(Element, Element)` により同じ型同士の比較に限定されている。

## assertメソッドでの判定

`XCTAssertEqual` は `Equatable` を要求する。

```swift
func XCTAssertEqual<T>(
    _ expression1: @autoclosure () throws -> T,
    _ expression2: @autoclosure () throws -> T,
    _ message: @autoclosure () -> String = default,
    file: StaticString = #file,
    line: UInt = #line
) where T : Equatable
```

型安全の関係上 `T?` 版が別に存在する。

# Java

## 同一判定

`==` を用いる。

## 等値判定

`equals` メソッドを用いる。
`equals` メソッド自体はもともとclass `Object` から生えているものである。しかしその実態は同一判定である。

```java
public boolean equals(Object obj) {
    return (this == obj);
}
```

継承側はこれをオーバーライドして定める。以下に `String` の例を示す。

```java
public boolean equals(Object anObject) {
    if (this == anObject) {
        return true;
    }
    if (anObject instanceof String) {
        String anotherString = (String)anObject;
        int n = value.length;
        if (n == anotherString.value.length) {
            char v1[] = value;
            char v2[] = anotherString.value;
            int i = 0;
            while (n-- != 0) {
                if (v1[i] != v2[i])
                    return false;
                i++;
            }
            return true;
        }
    }
    return false;
}
```

`equals` メソッドには

* 反射性( `x.equals(x) == true` )
* 対称性( `y.equals(x) == true` ならば `x.equals(y) == true` )
* 推移性( `x.equals(y) == true` かつ `y.equals(z) == true` ならば `x.equals(z) == true` )
* 一貫性( `equals` 内での比較に使用する情報に変更がない限り結果は一貫して変わらない)

がある。

### nullの扱い

null以外のオブジェクトの比較を想定している。相手がnullの場合はfalseになる。

### ハッシュ値の扱い

`equals` メソッドをオーバーライドする際は同じく `Object` に由来する `public int hashCode()` もオーバーライドして一緒に面倒を見てやる必要がある。 `hashCode` には `equals` に関する次のような規則が定められているからである。

* `equals` メソッドによる比較で使用する情報に変更がなければ、 `hashCode` は常に同じ整数を返す
* `equals` メソッド的に2つのオブジェクトが等しいならば、 `hashCode` はそれぞれに同じ整数を返す
* `equals` メソッド的に2つのオブジェクトが異なる場合は、 `hashCode` は異なる整数を返すほうが望ましい

`String` では次のように `hashCode` をオーバーライドしている。

```java
public int hashCode() {
    int h = hash;
    if (h == 0 && value.length > 0) {
        char val[] = value;

        for (int i = 0; i < value.length; i++) {
            h = 31 * h + val[i];
        }
        hash = h;
    }
    return h;
}
```

### 他の型との比較

全クラスが `Object` を継承しているので `equals` が使える。

## クラスへの順序付け

`Comparable<? super T>` であれば `List<T>` に対するソートメソッドとして

```java
public static <T extends Comparable<? super T>> void sort(List<T> list)
```

を使用することができる。
`public int compareTo(T o)` 実装時には以下が保証されなければならない。

* 全てのxとyについて `sgn(x.compareTo(y))== -sgn(y.compareTo(x))`
  * 片方が例外スローするならもう片方も例外スローする。
* `(x.compareTo(y)>0 && y.compareTo(z)>0)` ならば `x.compareTo(z)>0`
* 全てのzについて `x.compareTo(y)==0` が `sgn(x.compareTo(z))== sgn(y.compareTo(z))` を意味する

### 等値判定との一貫性

クラスCの全てのe1とe2について `e1.compareTo(e2) == 0` と `e1.equals(e2)` の結果が一致する時、 `equals` と一貫性があると言う。
`equals` との一貫性については必須ではないが、ソートセットやソートマップの動作が保証されなくなるので一貫性を持つことを推奨されている。一貫性がない例として `BigDecimal` がある。

一貫性がない場合はその旨を明記することが推奨されている。

### nullの扱い

nullはどのオブジェクトのインスタンスでもないため例外をスローすべきとされる。

### 他の型との比較

`Comparable<T>` は

```java
public interface Comparable<T> {
    public int compareTo(T o);
}
```

からわかるように、別の型との比較を実装できないこともない。

## コレクションへの順序付け

`Comparator<T>` を用意することで

```java
public static <T> void sort(List<T> list, Comparator<? super T> c)
```

によるソートを行うことができる。

`int compare(T o1, T o2)` 実装時には以下が保証されなければならない。

* 全てのxとyについて `sgn(compare(x, y))== -sgn(compare(y, x))`
  * 片方が例外スローする時のみもう片方も例外スローする。
* `((compare(x, y)>0)&& (compare(y, z)>0))` ならば `compare(x, z)>0`
* 全てのzについて `compare(x, y)==0` が `sgn(compare(x, z))==sgn(compare(y, z))` を意味する

### 等値判定との一貫性

セットSの全てのe1とe2について `e1.compareTo(e2) == 0` と `e1.equals(e2)` の結果が一致する時、 `Comparator<T>` は `equals` との一貫性がある。
こちらもソートセットやソートマップの動作が保証されなくなるのでやはり一貫性が推奨される。一貫性がない場合は明記した方がよい。

### nullの扱い

オプション次第でnullとの比較が許可される。
`Comparator<T>` には

```java
public static <T> Comparator<T> nullsLast(Comparator<? super T> comparator)
```

のようなメソッドが用意されている。

### 他の型との比較

同じ型同士の比較を想定したものになっている。

```java
@FunctionalInterface
public interface Comparator<T> {
    int compare(T o1, T o2);
    boolean equals(Object obj);
    // 略
}
```

## assertメソッドでの判定

参照型用には `Object` を取るassertメソッドが用意されている。

```java
static public void assertEquals(String message, Object expected, Object actual)
```

`Object expected` がnullかそうでないかで処理が分かれる。nullだった場合はactualがnullかどうかで結果が決まる。nullでない場合は `expected.equals(actual)` で判定を行う。

一方プリミティブ型用にはそれぞれにメソッドが用意されている。例えば `float` には

```java
static public void assertEquals(String message, float expected, float actual, float delta)
```

があって、中では `Float` の

```java
public static int compare(float f1, float f2) {
    if (f1 < f2)
        return -1;           // Neither val is NaN, thisVal is smaller
    if (f1 > f2)
        return 1;            // Neither val is NaN, thisVal is larger

    // Cannot use floatToRawIntBits because of possibility of NaNs.
    int thisBits    = Float.floatToIntBits(f1);
    int anotherBits = Float.floatToIntBits(f2);

    return (thisBits == anotherBits ?  0 : // Values are equal
            (thisBits < anotherBits ? -1 : // (-0.0, 0.0) or (!NaN, NaN)
             1));                          // (0.0, -0.0) or (NaN, !NaN)
}
```

を呼び出している。

# 一目でわかるSwiftとJavaの違い

||Swift|Java|
|---|---|---|
|同一判定| `===` | `==` |
|等値判定| `==` | `equals` |
|等値判定に課せられた性質|反射性/対称性/推移性|反射性/対称性/推移性/一貫性|
|等値判定でのnullとの比較| `Optional<T>` 型ならtrueになる場合あり|常にfalse|
|等値である時のハッシュ値の一貫性| `Hashable` なら必須|必須|
|等値判定での他の型との比較|不可|可|
|クラスへの順序付け| `Comparable` (狭義の全順序)| `Comparable<T>` (狭義の全順序)|
|クラスへの順序付けと等値判定の一貫性|常にあり|推奨| 
|クラスへの順序付けでのnullとの比較|不可|例外スロー推奨|
|クラスへの順序付けでの他の型との比較|不可|可|
|コレクションへの順序付け| `areInIncreasingOrder` (狭義の弱順序)| `Comparator<T>` (狭義の全順序)|
|コレクションへの順序付けと等値判定の一貫性|言及なし|推奨| 
|コレクションへの順序付けでのnullとの比較| `Optional<T>` なら可|オプションによっては可|
|コレクションへの順序付けでの他の型との比較|不可|不可|
|assertメソッドでの判定| 要 `Equatable` | `equals` を使用|

# おまけ

## Objective-Cのassertメソッド

SwiftとObjective-Cではassertメソッドが異なる。

改めて並べてみると、

```swift
func XCTAssertEqual<T>(_ expression1: @autoclosure () throws -> T, _ expression2: @autoclosure () throws -> T, _ message: @autoclosure () -> String = default, file: StaticString = #file, line: UInt = #line) where T : Equatable
func XCTAssertEqual<T>(_ expression1: @autoclosure () throws -> T?, _ expression2: @autoclosure () throws -> T?, _ message: @autoclosure () -> String = default, file: StaticString = #file, line: UInt = #line) where T : Equatable
```

```objc
XCTAssertEqual(expression1, expression2, ...)
XCTAssertEqualObjects(expression1, expression2, ...)
```

```java
static public void assertEquals(String message, float expected, float actual, float delta)
static public void assertEquals(String message, Object expected, Object actual)
```

この点についてはObjCの方がJavaに近い。

## 順序のルール

狭義の全順序(以下strict total ordering)と狭義の弱順序(以下strict weak ordering)について。れっきとしたどこかの用語である。

何がstrictでtotalでweakかといえば、

* "strict" は非反射性を示す。
* "total" は比較不能を許容しない。そこから、比較不能あり/なしひっくるめたorderingを "partial" と呼ぶ。
* "weak" は "total" より弱く "partial" より強い要求を示す。具体的には推移不能性のこと。

Swiftの `Comparable` は
『非反射性』
『比較不能を許容しない』( `FloatingPoint.nan` などは対象外)
よってstrict total orderingである。

一方

`areInIncreasingOrder` は
『非反射性』
『比較不能を許容する』
『推移不能性』
よってstrict weak orderingである。

__たぶん。__

ちなみに、Javaの `Comparable<T>` と `Comparator<T>` はどちらもクラス説明文でtotal orderingと名乗っていて、メソッド説明で非反射性に触れている。つまりstrict total orderingを想定していると読める。

比較不能については次の項目で。

## Let's try

ストーリーは適当。

たかしくんはお兄さんからボールをたくさんもらいました。

```swift
struct Ball {
    let diameter: Int
    let color: Color

    enum Color {
        case blue
        case red
        case yellow
    }
}
```

```java
class Ball {
    int diameter;
    Color color;
    
    public Ball(int diameter, Color color) {
        this.diameter = diameter;
        this.color = color;
    }

    enum Color {
        BLUE, RED, YERROW
    }
}
```

ボールの大きさや色は様々です。果たして同じボールはあるんだろうか？と思ってしまうほどです。

```swift
extension Ball: Equatable {}

/// 反射性、対称性、推移性を満たす
/// 可視的なものは全て織り込み済み
/// (a != b) と !(a == b)の結果が一致する
func ==(lhs: Ball, rhs: Ball) -> Bool {
    return lhs.diameter == rhs.diameter && lhs.color == rhs.color
}
```

```java
/**
 * 反射性、対称性、推移性、一貫性を満たす
 * hashCodeもオーバーライド済み
 * nullのときはfalseを返す
 */
@Override
public boolean equals(Object anObject) {
    if (this == anObject) {
        return true;
    }
    if (anObject instanceof Ball) {
        Ball anotherBall = (Ball)anObject;
        return this.diameter == anotherBall.diameter && this.color == anotherBall.color;
    }
    return false;
}

/**
 * diameterとcolorに変更がなければ同じ整数を返す
 * `equals` 的に等しいなら同じ整数を返す
 * `equals` 的に異なるなら異なる整数を返す
 */
@Override
public int hashCode() {
    return Objects.hash(this.diameter, this.color);
}
```

それにしてもたくさんありすぎてどんなボールがあるのかわかりません。今度キャッチボールをするのに使うボールを探そうと、まずは大きさ順に並べることにしました。

```swift
let balls: [Ball] = [/* たくさん！ */]

balls.sort {
    return $0.diameter < $1.diameter
}
```

```java
List<Ball> list = Arrays.asList(/* たくさん！ */);

// nullを許容しないつもり
list.sort((Ball o1, Ball o2) ->
    o1.diameter - o2.diameter
);
```

たかしくんは比較不能を許容した。色をどう並べるかを決めなかったので同じ大きさのボールの並べ方が定まらない。
(10, 青)と(10, 赤)を考えると、 (10, 青) `<` (10, 赤)がfalseで(10, 青) `>` (10, 赤) もfalseである。 `<` も `>` もfalseなのだから(10, 青) `==` (10, 赤)が成立する。つまり同じ大きさの色__違い__のボールは__同じ__。比較不能を許容しない場合なら起きない話である。 

この大きさのみに着目した並べ方は

* 非反射性
* 推移比較可能性
* 推移不能性「(10, 青)と(10, 赤)が比較不能で(10, 青)と(10, 黄)が比較不能なら(10, 赤)と(10, 黄)も比較不能」

が成立するので、strict weak orderingである。Swiftの `areInIncreasingOrder` の要求はstrict weak orderingなので大丈夫。
ところがJavaの `Comparator<T>` はtotal orderingを名乗っているので合わない。それだけではなく、大きさにしか注目していないということは、同じ大きさのボールに関して `e1.compareTo(e2) == 0` と `e1.equals(e2)` の結果が一致しないことを意味する。つまり `Comparator<T>` と `equals` メソッドの間に一貫性がない。

ひととおりボールを並べて満足したたかしくんでしたが、お母さんに怒られたのでお片付けをしなければならなくなりました。せっかくなので、大きさと色をそろえてしまうことにしました。

```swift
extension Ball: Comparable {}

/// 非反射性、非対称性、推移性を満たす
func < (lhs: Ball, rhs: Ball) -> Bool {
    if lhs.diameter == rhs.diameter {
        return lhs.color.hashValue < rhs.color.hashValue
    } else {
        return lhs.diameter < rhs.diameter
    }
}
```

```java
/**
 * 非反射性、非対称性、推移性を満たす
 * `equals` との一貫性あり
 * `o` がnullの時ぬるぽをスロー
 */
@Override
public int compareTo(Ball o) {
    if (this.diameter == o.diameter) {
        return this.color.hashCode() - o.color.hashCode();
    } else{
        return this.diameter - o.diameter;
    }
}
```

たかしくんは色も見て並べるようになった。これにより `equals` との一貫性が成立する。もちろん `Equatable` とも一貫性がある。
色の順番をきちんと決めた結果strict total orderingの要件も満たすようになった。これで `Comparable` `Comparable<T>` どちらからの要求も充足される。

# 参考文献

Java
[jdk8/jdk8/jdk: 687fd7c7986d /src/share/classes/](http://hg.openjdk.java.net/jdk8/jdk8/jdk/file/687fd7c7986d/src/share/classes/)
[java.lang (Java Platform SE 8)](https://docs.oracle.com/javase/jp/8/docs/api/java/lang/package-summary.html)
[java.util (Java Platform SE 8)](https://docs.oracle.com/javase/jp/8/docs/api/java/util/package-summary.html)
[Assert (JUnit API)](http://junit.org/junit4/javadoc/4.12/org/junit/Assert.html)

Apple
[Swift Standard Library | Apple Developer Documentation](https://developer.apple.com/documentation/swift)
[apple/swift: The Swift Programming Language](https://github.com/apple/swift)
[[swift-evolution] [Draft][Proposal] Formalized Ordering](https://lists.swift.org/pipermail/swift-evolution/Week-of-Mon-20160718/025284.html)

順序
[2004-05-29 - Cry’s Diary](http://d.hatena.ne.jp/Cryolite/20040529)
[algorithm - cpprefjp C++日本語リファレンス](https://cpprefjp.github.io/reference/algorithm.html)