Spliterator の characteristics メソッドが返す値まとめ #java

# Spliterator の characteristics メソッドが返す値まとめ #java

Java 8 で追加されたイテレータインターフェース `Spliterator` は、そのデータソースに応じた characteristics を保持することができます。
どの特性を持つべきか自明でないケースがあると感じたので、標準ライブラリ経由で作成した `Spliterator` が返す `characteristics` の値をまとめてみました。

## Spliterator is 何

`java.util.Spliterator` は Java 8 で新しく追加されたイテレータインターフェースです。
https://docs.oracle.com/javase/jp/8/docs/api/java/util/Spliterator.html

Java のイテレータといえば、古来より [java.util.Iterator](https://docs.oracle.com/javase/jp/8/docs/api/java/util/Iterator.html) が存在します。
`Spliterator` もおおよそはこの `Iterator` と同じですが、より最適化された API を提供します。

### tryAdvance

`java.util.Iterator` の場合、`hasNext` メソッドと `next` メソッドを組み合わせて要素をイテレートします。
`hasNext` で「次の」要素が存在するかチェックし、存在する場合は `next` でその要素を取得するというプロトコルです。

```java
Iterator<String> iterator = ……;
while (iterator.hasNext()) {
  System.out.println(iterator.next());
}
```

一方、`Spliterator` は「次の」要素を取得するために `tryAdvance` という単一のメソッドを提供します。
`tryAdvance` は `Spliterator` の要素を受け取り、何かを行う [Consumer](https://docs.oracle.com/javase/jp/8/docs/api/java/util/function/Consumer.html) を引数に取ります。
「次の」要素が存在する場合はその要素を `Consumer` に消化させつつ `true` を返し、「次の」要素が存在しない場合は `Consumer` を実行せず `false` を返します。

```java
Spliterator<String> spliterator = ……;
do { } while (spliterator.tryAdvance(System.out::println));
```

※単に全要素トラバースするのが目的であれば、`java.util.Iterator`、`java.util.Spliterator` ともに `forEachRemaining` というメソッドを用いた方がよいと思います。

### trySplit

インターフェース名にもその機能が見え隠れしていますが、`Spliterator` はイテレータを分割するための `trySplit` メソッドを提供します。
これはレシーバである `Spliterator` の要素を、戻り値となる `Spliterator` へ分割する API です。 

通常単一の `Iterator` や `Spliterator` はスレッドセーフではありません。
しかし `trySplit` で分割された各 `Spliterator` はそれぞれ別のスレッドで処理できるので、結果として要素を並列にトラバーサルすることが可能となります。
他にも `Spliterator` は要素数を取得できたり、後述する characteristics の指定ができたりなど、並列・分割統治を強く意識したインターフェースとなっています。
[StreamSupport](https://docs.oracle.com/javase/jp/8/docs/api/java/util/stream/StreamSupport.html) はこの `trySplit` や、characteristics を用いてストリームを最適化するそうです。

例えば次のように配列から作成した `Spliterator` の `trySplit` を呼び出すと、それぞれの `Spliterator` がちょうど半分ずつの要素を担当するように分割されます。

```java
final int[] xs = {1, 2, 3, 4, 5, 6, 7, 8};
final Spliterator<Integer> a = Spliterators.spliterator(xs, 0);
final Spliterator<Integer> b = a.trySplit();
a.forEachRemaining(System.out::println); // 5, 6, 7, 8
b.forEachRemaining(System.out::println); // 1, 2, 3, 4
```

## 調べたかったこと

### どのような特性を持つべきか

`Spliterator` は自身が持つ特徴に基づいて、ヒントを格納することができます。
現在 `Spliterator` が持つことができる特徴は「[CONCURRENT](https://docs.oracle.com/javase/jp/8/docs/api/java/util/Spliterator.html#CONCURRENT)」「[DISTINCT](https://docs.oracle.com/javase/jp/8/docs/api/java/util/Spliterator.html#DISTINCT)」「[IMMUTABLE](https://docs.oracle.com/javase/jp/8/docs/api/java/util/Spliterator.html#IMMUTABLE)」「[NONNULL](https://docs.oracle.com/javase/jp/8/docs/api/java/util/Spliterator.html#NONNULL)」「[ORDERED](https://docs.oracle.com/javase/jp/8/docs/api/java/util/Spliterator.html#ORDERED)」「[SIZED](https://docs.oracle.com/javase/jp/8/docs/api/java/util/Spliterator.html#SIZED)」「[SORTED](https://docs.oracle.com/javase/jp/8/docs/api/java/util/Spliterator.html#SORTED)」「[SUBSIZED](https://docs.oracle.com/javase/jp/8/docs/api/java/util/Spliterator.html#SUBSIZED)」の8つです。

意味は定数名通りで、例えば `Set` から作られた `Spliterator` は要素の重複がないことが保証されているから `DISTINCT` 属性を付与する、配列から作られた `Spliterator` は要素数がわかっているから `SIZED` 属性を付与する、といった使い方をします。

ただ要素が1つであることが明白な場合に `DISTINCT` 属性や `SORTED` 属性を付与すべきかどうかが自明でなかったりなど、仕様に微妙に不安を感じました。
そこでさまざまな方法で `Spliterator` を作成し、データ構造と特性の関係を眺めてみることにしました。

## 結果

調査ケースがかなり多いので、いくつかのパターンに分割して結果をまとめました。
それぞれ `Spliterator` のソースと生成された `Spliterator` の具象クラス、`Spliterator` の characteristics を記載しています。

### java.util.Iterator から作成

`Spliterators.spliterator` と `Spliterators.spliteratorUnknownSize` でそれぞれ作成してみました。
そのまんまの結果となりました。

| ソース | Spliterator の具象クラス | Spliterator の characteristics |
|:--|:--|:--|
| サイズ指定あり | java.util.Spliterators\$IteratorSpliterator | SIZED, SUBSIZED |
| サイズ指定なし | java.util.Spliterators\$IteratorSpliterator | なし |

### 配列や通常のコレクションから作成

データ構造の特性が表現されているように見えます。
ただ、配列をソースとする `Spliterator` に `ORDERED` 特性がない点は気になりました。

| ソース | Spliterator の具象クラス | Spliterator の characteristics |
|:--|:--|:--|
| 配列 | java.util.Spliterators\$ArraySpliterator | SIZED, SUBSIZED |
| ArrayList | java.util.ArrayList\$ArrayListSpliterator | ORDERED, SIZED, SUBSIZED |
| LinkedList | java.util.LinkedList\$LLSpliterator| ORDERED, SIZED, SUBSIZED |
| HashSet | java.util.HashMap\$KeySpliterator | DISTINCT, SIZED |
| LinkedHashSet | java.util.Spliterators\$IteratorSpliterator | DISTINCT, ORDERED, SIZED, SUBSIZED |
| TreeSet | java.util.TreeMap\$KeySpliterator | DISTINCT, ORDERED, SIZED, SORTED |
| PriorityQueue | java.util.PriorityQueue\$PriorityQueueSpliterator | NONNULL, SIZED, SUBSIZED |

### 並行コレクションから作成

ほぼすべてのパターンで、`IMMUTABLE` もしくは `CONCURRENT` 特性が付与されています。
`PriorityBlockingQueue` にそれらがないのは、ヒープのデータ構造に由来しているのだと思っています。

| ソース | Spliterator の具象クラス | Spliterator の特性 |
|:--|:--|:--|
| CopyOnWriteArrayList | java.util.Spliterators\$ArraySpliterator | IMMUTABLE, ORDERED, SIZED, SUBSIZED |
| CopyOnWriteArraySet | java.util.Spliterators\$ArraySpliterator | DISTINCT, IMMUTABLE, SIZED, SUBSIZED |
| ConcurrentSkipListSet | java.util.concurrent.ConcurrentSkipListMap\$KeySpliterator | CONCURRENT, DISTINCT, NONNULL, ORDERED, SORTED |
| ConcurrentLinkedQueue | java.util.concurrent.ConcurrentLinkedQueue\$CLQSpliterator | CONCURRENT, NONNULL, ORDERED |
| LinkedBlockingQueue | java.util.concurrent.LinkedBlockingQueue\$LBQSpliterator | CONCURRENT, NONNULL, ORDERED |
| LinkedTransferQueue | java.util.concurrent.LinkedTransferQueue\$LTQSpliterator | CONCURRENT, NONNULL, ORDERED |
| PriorityBlockingQueue | java.util.concurrent.PriorityBlockingQueue\$PBQSpliterator | NONNULL, SIZED, SUBSIZED |

### 特殊な制約のあるパターン

`Collections` クラスを使って作成した不変シングルトンリストや、不変空リストなどを試してみました。
不変空コレクションの characteristics は正直色々足りていない気がします。

| ソース | Spliterator の具象クラス | Spliterator の特性 |
|:--|:--|:--|
| Collections.singletonList | java.util.Collections\$2 | DISTINCT, IMMUTABLE, NONNULL, ORDERED, SIZED, SUBSIZED |
| Collections.singleton | java.util.Collections\$2 | DISTINCT, IMMUTABLE, NONNULL, ORDERED, SIZED, SUBSIZED |
| Collections.emptyList | java.util.Spliterators\$EmptySpliterator\$OfRef | SIZED, SUBSIZED |
| Collections.emptySet | java.util.Spliterators\$EmptySpliterator\$OfRef | SIZED, SUBSIZED |
| Collections.emptySortedSet | java.util.TreeMap\$KeySpliterator | DISTINCT, ORDERED, SIZED, SORTED |
| Spliterators.emptySpliterator | java.util.Spliterators\$EmptySpliterator\$OfRef | SIZED, SUBSIZED |

## まとめ

様々な方法で `Spliterator` を作成し、それぞれの characteristics を取得してみました。
おおよその傾向はつかめたものの、標準ライブラリ自体、必ずしも一貫した実装となっているわけではなさそうです。

## 調査履歴

調査ログです。
長いので結果まとめの参照をオススメします。

Java は「Java HotSpot(TM) 64-Bit Server VM, Java 1.8.0_60」です。

### 前提

Scala REPL で試しました。
あらかじめ次のインポートとメソッド定義を行っておきます。

```scala
import java.util._
import java.util.concurrent._
def printCharacteristics[T](spliterator: Spliterator[T]): Unit = {
  println(Seq(
    if (spliterator.hasCharacteristics(Spliterator.CONCURRENT)) Some("CONCURRENT") else None,
    if (spliterator.hasCharacteristics(Spliterator.DISTINCT)) Some("DISTINCT") else None,
    if (spliterator.hasCharacteristics(Spliterator.IMMUTABLE)) Some("IMMUTABLE") else None,
    if (spliterator.hasCharacteristics(Spliterator.NONNULL)) Some("NONNULL") else None,
    if (spliterator.hasCharacteristics(Spliterator.ORDERED)) Some("ORDERED") else None,
    if (spliterator.hasCharacteristics(Spliterator.SIZED)) Some("SIZED") else None,
    if (spliterator.hasCharacteristics(Spliterator.SORTED)) Some("SORTED") else None,
    if (spliterator.hasCharacteristics(Spliterator.SUBSIZED)) Some("SUBSIZED") else None
  ).flatten.mkString(", "))
}
```

### java.util.Iterator から作成

#### サイズ指定あり

`Spliterators.spliterator` の第二引数はイテレータのサイズ、第三引数は追加で指定する characteristics です。
例えば要素が `null` でないことがアプリケーションレベルで保証されている場合、第三引数に `NONNULL` を指定する、といった使い方ができます。
0を指定すると何も characteristics を追加しません。

```scala
scala> val iterator = new java.util.Iterator[Int] {
     |   var i = 0
     |   def hasNext(): Boolean = i < 8
     |   def next(): Int = {
     |     if (i >= 8) throw new NoSuchElementException()
     |     i += 1
     |     i
     |   }
     | }
iterator: java.util.Iterator[Int]{def i: Int; def i_=(x$1: Int): Unit} = $anon$1@1d6dc2b8

scala> val spliterator = Spliterators.spliterator(iterator, 8, 0)
spliterator: java.util.Spliterator[Int] = java.util.Spliterators$IteratorSpliterator@5c8e7687

scala> printCharacteristics(spliterator)
SIZED, SUBSIZED
```

#### サイズ指定なし

イテレータはあらかじめ要素数が確定していなかったり、あるいは無限の要素を持つ可能性があります。
そのような場合、`Spliterators.spliteratorUnknownSize` を用いて `Spliterator` を作成します。
第二引数はは追加で指定する characteristics です

```scala
scala> val iterator = new java.util.Iterator[Int] {
     |   var i = 0
     |   def hasNext(): Boolean = i < 8
     |   def next(): Int = {
     |     if (i >= 8) throw new NoSuchElementException()
     |     i += 1
     |     i
     |   }
     | }
iterator: java.util.Iterator[Int]{def i: Int; def i_=(x$1: Int): Unit} = $anon$1@1c96bf1e

scala> val spliterator = Spliterators.spliteratorUnknownSize(iterator, 0)
spliterator: java.util.Spliterator[Int] = java.util.Spliterators$IteratorSpliterator@44ba9f25

scala> printCharacteristics(spliterator)
```

### 配列や通常のコレクションから作成

#### 配列

`Array[Int]` からそのまま `Spliterator` を作るとプリミティブ配列に特化した `Spliterator` ができるので、`AnyRef`(Java の `Object` 型)にキャストしています。

```scala
scala> val spliterator = Spliterators.spliterator[Int]((1 to 8).toArray.map(_.asInstanceOf[AnyRef]), 0)
spliterator: java.util.Spliterator[Int] = java.util.Spliterators$ArraySpliterator@32ca397b

scala> printCharacteristics(spliterator)
SIZED, SUBSIZED
```

#### ArrayList

```scala
scala> val collection = new ArrayList[Int]()
collection: java.util.ArrayList[Int] = []

scala> (1 to 8).foreach(collection.add)

scala> val spliterator = collection.spliterator()
spliterator: java.util.Spliterator[Int] = java.util.ArrayList$ArrayListSpliterator@7d3af2f0

scala> printCharacteristics(spliterator)
ORDERED, SIZED, SUBSIZED
```

#### LinkedList

```scala
scala> val collection = new LinkedList[Int]()
collection: java.util.LinkedList[Int] = []

scala> (1 to 8).foreach(collection.add)

scala> val spliterator = collection.spliterator()
spliterator: java.util.Spliterator[Int] = java.util.LinkedList$LLSpliterator@71637a85

scala> printCharacteristics(spliterator)
ORDERED, SIZED, SUBSIZED
```

#### HashSet

```scala
scala> val collection = new HashSet[Int]()
collection: java.util.HashSet[Int] = []

scala> (1 to 8).foreach(collection.add)

scala> val spliterator = collection.spliterator()
spliterator: java.util.Spliterator[Int] = java.util.HashMap$KeySpliterator@71daf5d6

scala> printCharacteristics(spliterator)
DISTINCT, SIZED
```

#### LinkedHashSet

```scala
scala> val collection = new LinkedHashSet[Int]()
collection: java.util.LinkedHashSet[Int] = []

scala> (1 to 8).foreach(collection.add)

scala> val spliterator = collection.spliterator()
spliterator: java.util.Spliterator[Int] = java.util.Spliterators$IteratorSpliterator@28391cc6

scala> printCharacteristics(spliterator)
DISTINCT, ORDERED, SIZED, SUBSIZED
```

#### TreeSet

```scala
scala> val collection = new TreeSet[Int]()
collection: java.util.TreeSet[Int] = []

scala> (1 to 8).foreach(collection.add)

scala> val spliterator = collection.spliterator()
spliterator: java.util.Spliterator[Int] = java.util.TreeMap$KeySpliterator@62b630e0

scala> printCharacteristics(spliterator)
DISTINCT, ORDERED, SIZED, SORTED
```

#### PriorityQueue

```scala
scala> val collection = new PriorityQueue[Int]()
collection: java.util.PriorityQueue[Int] = []

scala> (1 to 8).foreach(collection.add)

scala> val spliterator = collection.spliterator()
spliterator: java.util.Spliterator[Int] = java.util.PriorityQueue$PriorityQueueSpliterator@6f75d11b

scala> printCharacteristics(spliterator)
NONNULL, SIZED, SUBSIZED
```

### 並行コレクション

#### CopyOnWriteArrayList

```scala
scala> val collection = new CopyOnWriteArrayList[Int]()
collection: java.util.concurrent.CopyOnWriteArrayList[Int] = []

scala> (1 to 8).foreach(collection.add)

scala> val spliterator = collection.spliterator()
spliterator: java.util.Spliterator[Int] = java.util.Spliterators$ArraySpliterator@5a931c02

scala> printCharacteristics(spliterator)
IMMUTABLE, ORDERED, SIZED, SUBSIZED
```

#### CopyOnWriteArraySet

```scala
scala> val collection = new CopyOnWriteArraySet[Int]()
collection: java.util.concurrent.CopyOnWriteArraySet[Int] = []

scala> (1 to 8).foreach(collection.add)

scala> val spliterator = collection.spliterator()
spliterator: java.util.Spliterator[Int] = java.util.Spliterators$ArraySpliterator@ca024d8

scala> printCharacteristics(spliterator)
DISTINCT, IMMUTABLE, SIZED, SUBSIZED
```

#### ConcurrentSkipListSet

```scala
scala> val collection = new ConcurrentSkipListSet[Int]()
collection: java.util.concurrent.ConcurrentSkipListSet[Int] = []

scala> (1 to 8).foreach(collection.add)

scala> val spliterator = collection.spliterator()
spliterator: java.util.Spliterator[Int] = java.util.concurrent.ConcurrentSkipListMap$KeySpliterator@7e003cf0

scala> printCharacteristics(spliterator)
CONCURRENT, DISTINCT, NONNULL, ORDERED, SORTED
```

#### ConcurrentLinkedQueue

```scala
scala> val collection = new ConcurrentLinkedQueue[Int]()
collection: java.util.concurrent.ConcurrentLinkedQueue[Int] = []

scala> (1 to 8).foreach(collection.add)

scala> val spliterator = collection.spliterator()
spliterator: java.util.Spliterator[Int] = java.util.concurrent.ConcurrentLinkedQueue$CLQSpliterator@ffbdb79

scala> printCharacteristics(spliterator)
CONCURRENT, NONNULL, ORDERED
```

#### LinkedBlockingQueue

```scala
scala> val collection = new LinkedBlockingQueue[Int]()
collection: java.util.concurrent.LinkedBlockingQueue[Int] = []

scala> (1 to 8).foreach(collection.add)

scala> val spliterator = collection.spliterator()
spliterator: java.util.Spliterator[Int] = java.util.concurrent.LinkedBlockingQueue$LBQSpliterator@d57ba2a

scala> printCharacteristics(spliterator)
CONCURRENT, NONNULL, ORDERED
```

#### LinkedTransferQueue

```scala
scala> val collection = new LinkedTransferQueue[Int]()
collection: java.util.concurrent.LinkedTransferQueue[Int] = []

scala> (1 to 8).foreach(collection.add)

scala> val spliterator = collection.spliterator()
spliterator: java.util.Spliterator[Int] = java.util.concurrent.LinkedTransferQueue$LTQSpliterator@2977084e

scala> printCharacteristics(spliterator)
CONCURRENT, NONNULL, ORDERED
```

#### PriorityBlockingQueue

```scala
scala> val collection = new PriorityBlockingQueue[Int]()
collection: java.util.concurrent.PriorityBlockingQueue[Int] = []

scala> (1 to 8).foreach(collection.add)

scala> val spliterator = collection.spliterator()
spliterator: java.util.Spliterator[Int] = java.util.concurrent.PriorityBlockingQueue$PBQSpliterator@1fd97710

scala> printCharacteristics(spliterator)
NONNULL, SIZED, SUBSIZED
```

### 特殊な制約のあるパターン

#### Collections.singletonList

要素が１つしかない不変リストです。

```scala
scala> val collection = Collections.singletonList(1)
collection: java.util.List[Int] = [1]

scala> val spliterator = collection.spliterator()
spliterator: java.util.Spliterator[Int] = java.util.Collections$2@56625ce9

scala> printCharacteristics(spliterator)
DISTINCT, IMMUTABLE, NONNULL, ORDERED, SIZED, SUBSIZED
```

#### Collections.singlton

要素が1つしかない不変セットです。

```scala
scala> val collection = Collections.singleton(1)
collection: java.util.Set[Int] = [1]

scala> val spliterator = collection.spliterator()
spliterator: java.util.Spliterator[Int] = java.util.Collections$2@60d501f6

scala> printCharacteristics(spliterator)
DISTINCT, IMMUTABLE, NONNULL, ORDERED, SIZED, SUBSIZED
```

#### Collections.emptyList

不変空リストです。

```scala
scala> val collection = Collections.emptyList[Int]()
collection: java.util.List[Int] = []

scala> val spliterator = collection.spliterator()
spliterator: java.util.Spliterator[Int] = java.util.Spliterators$EmptySpliterator$OfRef@170f6972

scala> printCharacteristics(spliterator)
SIZED, SUBSIZED
```

#### Collections.emptySet

不変空セットです。

```scala
scala> val collection = Collections.emptySet[Int]()
collection: java.util.Set[Int] = []

scala> val spliterator = collection.spliterator()
spliterator: java.util.Spliterator[Int] = java.util.Spliterators$EmptySpliterator$OfRef@170f6972

scala> printCharacteristics(spliterator)
SIZED, SUBSIZED
```

#### Collections.emptySortedSet

不変空 SortedSet です。

```scala
scala> val collection = Collections.emptySortedSet[Int]()
collection: java.util.SortedSet[Int] = []

scala> val spliterator = collection.spliterator()
spliterator: java.util.Spliterator[Int] = java.util.TreeMap$KeySpliterator@d5ce7bb

scala> printCharacteristics(spliterator)
DISTINCT, ORDERED, SIZED, SORTED
```

#### Spliterators.emptySpliterator

空 `Spliterator` です。

```scala
scala> val spliterator = Spliterators.emptySpliterator[Int]()
spliterator: java.util.Spliterator[Int] = java.util.Spliterators$EmptySpliterator$OfRef@170f6972

scala> printCharacteristics(spliterator)
SIZED, SUBSIZED
```