Summary of values returned by the Spliterator characteristics method #java

Summary of values returned by the Spliterator characteristics method #java

The iterator interface Spliterator, added in Java 8, can retain characteristics depending on its data source. I felt that there were cases where it was not obvious which characteristics should be possessed, so I summarized the values of characteristics returned by Spliterator created via the standard library.

Spliterator is what

java.util.Spliterator is a new iterator interface added in Java 8. https://docs.oracle.com/javase/jp/8/docs/api/java/util/Spliterator.html

Speaking of Java iterators, java.util.Iterator has existed since ancient times. Spliterator is roughly the same as this ʻIterator`, but provides a more optimized API.

tryAdvance

For java.util.Iterator, iterate the element by combining the hasNext and next methods. The protocol is to use hasNext to check for the existence of the" next "element, and if so, to get that element with next.

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

On the other hand, Spliterator provides a single method called tryAdvance to get the "next" element. tryAdvance takes an element of Spliterator and does something Consumer Takes as an argument. If the "next" element exists, it is digested by Consumer and returns true, and if the "next" element does not exist, it does not execute Consumer and returns false.

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

• If the purpose is simply to traverse all elements, it is better to use the method forEachRemaining for both java.util.Iterator and java.util.Spliterator.

trySplit

The interface name also hides its functionality, but Spliterator provides a trySplit method for splitting iterators. This is an API that splits the elements of the receiver Spliterator into the return Spliterator.

Usually a single ʻIterator or Spliteratoris not thread-safe. However, eachSpliterator split by trySplitcan be processed by a separate thread, resulting in parallel traversal of elements. In addition,Spliteratoris an interface that is strongly conscious of parallel / divide and rule, such as being able to acquire the number of elements and specifying the characteristics described later. [StreamSupport](https://docs.oracle.com/javase/jp/8/docs/api/java/util/stream/StreamSupport.html) uses thistrySplit` and characteristics to optimize the stream. That's right.

For example, if you call trySplit of Spliterator created from an array as follows, each Spliterator will be split so that it is responsible for exactly half of the elements.

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

What I wanted to find out

What characteristics should be

Spliterator can store hints based on its own characteristics. Currently, the features that Spliterator can have are" CONCURRENT "" DISTINCT "" [IMMUTABLE](https://docs.oracle.com/javase/ jp / 8 / docs / api / java / util / Spliterator.html # IMMUTABLE) "" [NON NULL](https://docs.oracle.com/javase/jp/8/docs/api/java/util/Spliterator. html # NONNULL) "" 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 " There are eight.

The meaning is as the constant name, for example, Spliterator made from Set is guaranteed to have no duplicate elements, so the DISTINCT attribute is added. Spliterator made from an array has the number of elements. Since we know, we use it to add the SIZED attribute.

However, I was a little worried about the specification, such as it was not clear whether the DISTINCT attribute or the SORTED attribute should be added when it was clear that there was only one element. So I decided to create Spliterator in various ways and look at the relationship between data structures and characteristics.

result

Since there are quite a lot of survey cases, I divided the results into several patterns. The source of Spliterator, the generated concrete class of Spliterator, and the characteristics of Spliterator are described respectively.

Created from java.util.Iterator

I created them with Spliterators.spliterator and Spliterators.spliteratorUnknownSize, respectively. It was the result of that.

Created from arrays or regular collections

It looks like it represents the characteristics of the data structure. However, I was worried that the array-sourced Spliterator does not have the ʻORDERED` property.

Created from a parallel collection

Almost all patterns have the ʻIMMUTABLE or CONCURRENTproperty. I think the reason they aren't in thePriorityBlockingQueue` is due to the heap's data structures.

Patterns with special restrictions

I've tried immutable singleton lists, immutable sky lists, etc. created using the Collections class. To be honest, I feel that the characteristics of the Immutable Sky Collection are not enough.

Summary

I created Spliterator in various ways and tried to get the characteristics of each. Although I've got a rough idea, the standard library itself doesn't seem to have a consistent implementation.

Survey history

This is a survey log. Since it is long, we recommend you to refer to the result summary.

Java is "Java HotSpot (TM) 64-Bit Server VM, Java 1.8.0_60".

Premise

I tried it with Scala REPL. Perform the following import and method definition in advance.

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(", "))
}

Created from java.util.Iterator

With size specification

The second argument of Spliterators.spliterator is the size of the iterator, and the third argument is the characteristics specified additionally. For example, if the application level guarantees that the element is not null, you can specify NONNULL as the third argument. If 0 is specified, no characteristics will be added.

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

No size specified

The iterator may have an undetermined number of elements or an infinite number of elements. In such cases, use Spliterators.spliteratorUnknownSize to create Spliterator. The second argument is the characteristics you specify additionally

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)

Created from arrays or regular collections

Array

If you create Spliterator as it is from ʻArray [Int], you can create Spliterator specialized for primitive arrays, so I cast it to ʻAnyRef (Java ʻObject` type).

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

scala> printCharacteristics(spliterator)
SIZED, SUBSIZED

ArrayList

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

Parallel collection

CopyOnWriteArrayList

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

Patterns with special restrictions

Collections.singletonList

An immutable list with only one element.

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

An immutable set with only one element.

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

It is an immutable sky list.

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

It is an immutable sky set.

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

An immutable sky SortedSet.

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

Empty Spliterator.

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

scala> printCharacteristics(spliterator)
SIZED, SUBSIZED