284java.util.PrimitiveIterator.OfInt

Author: Dr Heinz M. KabutzDate: 2020-09-30Java Version: 8+Category: Tips and Tricks

Abstract: Java 8 Streams were the first time that Java deliberately split utility classes into multiple versions to be used for Object, int, long and double. This design was also applied to Iterator, which now has specialized types for these primites in the form of the PrimitiveIterator. In this newsletter we have a look at how we can use that in our own primitive collections.

Welcome to the 284th edition of The Java(tm) Specialists' Newsletter, sent to you from the beautiful Island of Crete. Whenever possible, I volunteer for the morning school drop-off, then head down to Kalathas Beach for a run on the soft sand and a dip in the sea afterwards. This morning, as I arrived, I saw one of the regulars doing his morning run, and a 70 year old grandmother from Ireland. I knew that the guy is usually faster than me, but he does not run as far. It seemed that he was faster than the granny, but it left me wondering: where do I fit into the speed of things? I waited until they were on the other side of the beach before starting my run. That way, they would have a long way to catch up and I could rest assured that even though I was slow, it was unlikely they would make up an entire stretch of beach. My plan was working, and I was feeling pretty confident that I would not get embarassed. After about a mile of running, granny popped into the sea to cool off. All good. I kept on running. When she emerged from the waves, she was about 30 meters behind me. How can a 48 year old Java programmer feel threatened by someone whose grandson is already 24? I picked up the pace a bit. I got to the end of the beach before her and turned around. She had gained about 15 meters on me. I upped the pace even more. After more running, and with the end in sight, I saw her pulling past me. If I am in a race, and the rest of the race are all pensioners, you can place a safe bet on me coming in last. But that won't stop me from running every day :-) Today was #720 in a row. I'm not trying to break land-speed records, but rather am aiming for a consistent focus on health and exercise. Still, it was funny when she pulled past me and I'm sure it made her day. Amazing!

javaspecialists.teachable.com: Please visit our new self-study course catalog to see how you can upskill your Java knowledge.

java.util.PrimitiveIterator.OfInt

Last week I taught the abstract class pattern to students of my Java Design Patterns Course. This pattern is used extensively in the Java Development Kit. For example, the ArrayDeque inherits a partial implementation from AbstractCollection and implements the Collection interface. BTW, due to the current COVID-19 pandemic, we are no longer delivering our courses in person, but instead via remote delivery. So far we have had very happy students. Our calendar is filling up and we only have a couple of weeks available until the end of 2020. So if you would like to treat your team to an awesome Java course, please let me know :-) Lots of topics available, and also short one-day workshops.

The students then had to apply their knowledge. I had written an IntArrayList and an IntArrayDeque, as the name would suggest, primitive int versions of ArrayList and ArrayDeque. However, these did not have a common superclass and so my students had to integrate everything into a common hierarchy. I wrote these classes about two years ago. The IntArrayList is almost exactly the same as ArrayList, but based on an int[]. However, when I tried to convert the ArrayDeque I got stuck. They were using null values in the array to check for concurrent modification errors. At the time I left the array as an Integer[], wanting to one day get back to it.

During one of my recent remote design patterns courses, I had given the students 15 minutes to solve the above mentioned exercise, and thought that should suffice to quickly do the conversion. Whilst looking at it, I realized that what I was really missing was a thorough test for the ArrayDeque. Whenever we refactor code, we need to have a test suite to make sure we do not break anything. Talking of refactoring, I have also completely rewritten my Refactoring to Streams Course. We take an existing 300k LOC ERP application and go nuts rewriting the code into modern Java. It is more fun than should be allowed. During the refactoring course we don't bother testing, because none of our refactorings are pushed to production. But in real life we need good tests whenever we work on code.

Two days ago I was again looking at my IntArrayDeque, feeling like Captain Ahab, wondering when I would finally conquer my Moby Dick. I started writing some tests, but then started scratching around in the OpenJDK. After some searching, I found the TCK suite for the java.util.concurrent package. After a bit (ok a lot) of fiddling, I managed to convert it to work with my IntArrayDeque. As so often happens when one looks into the abyss of one's own code, I found a little bug in my IntArrayList#equals() method, thanks to the TCK. Oh, and I found a bug in the TCK :-)

During the process of refactoring the code over and over, I went through quite a few approaches to designing these primitive collections. Before we go on, I think I need to state the obvious: this is an intellectual curiosity, rather than of great practical consequence. In the last 23 years of coding Java, I am not sure that I ever truly needed a primitive ArrayDeque. But I did learn something new about what Java has to offer, and would like to share that with you today.

When I first tried creating a primitive collection, the first interface I created was an IntIterator, like so:

import java.util.*;
import java.util.function.*;

public interface IntIterator {
  boolean hasNext();

  int next();

  default void remove() {
    throw new UnsupportedOperationException("remove");
  }

  default void forEachRemaining(IntConsumer action) {
    Objects.requireNonNull(action);
    while (hasNext()) action.accept(next());
  }
}

The IntIterator had the benefit of not needing to construct Integer objects every time we called the next() method.

This naturally flowed into the IntIterable:

import java.util.*;
import java.util.function.*;

public interface IntIterable {
  IntIterator iterator();

  default void forEach(IntConsumer action) {
    Objects.requireNonNull(action);
    for (IntIterator it = iterator(); it.hasNext(); )
      action.accept(it.next());
  }

  default Spliterator.OfInt spliterator() {
    return new IntIteratorSpliterator(iterator(), 0);
  }
}

You might observe two weaknesses with this approach. Firstly, the enhanced for-in loop takes either an array or a java.lang.Iterable. Our IntIterable is neither. We thus cannot use the enhanced for-in loop for the body of our forEach() function. Back to the old iterator code idiom. The second issue is that we need to create an IntIteratorSpliterator, similar to the spliterator that is created for an iterator with Spliterators.spliteratorUnknownSize(Iterator).

import java.util.*;
import java.util.function.*;

public class IntIteratorSpliterator implements Spliterator.OfInt {
  static final int BATCH_UNIT = 1 << 10;  // batch array size increment
  static final int MAX_BATCH = 1 << 25;  // max batch array size;
  private final IntIterator it;
  private final int characteristics;
  private long est;             // size estimate
  private int batch;            // batch size for splits

  public IntIteratorSpliterator(IntIterator iterator, int characteristics) {
    this.it = iterator;
    this.est = Long.MAX_VALUE;
    this.characteristics = characteristics &
        ~(Spliterator.SIZED | Spliterator.SUBSIZED);
  }

  public OfInt trySplit() {
    long s = est;
    if (s > 1 && it.hasNext()) {
      int n = batch + BATCH_UNIT;
      if (n > s)
        n = (int) s;
      if (n > MAX_BATCH)
        n = MAX_BATCH;
      int[] a = new int[n];
      int j = 0;
      do { a[j] = it.next(); }
      while (++j < n && it.hasNext());
      batch = j;
      if (est != Long.MAX_VALUE)
        est -= j;
      return new IntArraySpliterator(a, 0, j, characteristics);
    }
    return null;
  }

  public void forEachRemaining(IntConsumer action) {
    if (action == null) throw new NullPointerException();
    it.forEachRemaining(action);
  }

  public boolean tryAdvance(IntConsumer action) {
    if (action == null) throw new NullPointerException();
    if (it.hasNext()) {
      action.accept(it.next());
      return true;
    }
    return false;
  }

  public long estimateSize() {
    return est;
  }

  public int characteristics() {
    return characteristics;
  }

  private static final class IntArraySpliterator implements OfInt {
    private final int[] array;
    private int index;        // current index, modified on advance/split
    private final int fence;  // one past last index
    private final int characteristics;

    public IntArraySpliterator(int[] array, int origin, int fence,
                               int additionalCharacteristics) {
      this.array = array;
      this.index = origin;
      this.fence = fence;
      this.characteristics = additionalCharacteristics |
          Spliterator.SIZED | Spliterator.SUBSIZED;
    }

    public OfInt trySplit() {
      int lo = index, mid = (lo + fence) >>> 1;
      return (lo >= mid)
          ? null
          : new IntArraySpliterator(array, lo, index = mid, characteristics);
    }

    public void forEachRemaining(IntConsumer action) {
      if (action == null)
        throw new NullPointerException();
      int[] a;
      int i, hi; // hoist accesses and checks from loop
      if ((a = array).length >= (hi = fence) &&
          (i = index) >= 0 && i < (index = hi)) {
        do { action.accept(a[i]); } while (++i < hi);
      }
    }

    public boolean tryAdvance(IntConsumer action) {
      if (action == null)
        throw new NullPointerException();
      if (index >= 0 && index < fence) {
        action.accept(array[index++]);
        return true;
      }
      return false;
    }

    public long estimateSize() {
      return (long) (fence - index);
    }

    public int characteristics() {
      return characteristics;
    }

    public Comparator<? super Integer> getComparator() {
      if (hasCharacteristics(Spliterator.SORTED))
        return null;
      throw new IllegalStateException();
    }
  }
}

This bothers me. Not as much as that sweet granny running past me on the beach, but almost as much. I knew that there were four different types of Spliterator. One for Object and then one for the primitives int, long and double. Could we also get different types of Iterator?

Some more digging brought up the java.util.PrimitiveIterator. It contains three inner interfaces OfInt, OfLong and OfDouble. Each of these has a specialized method for their type. For example PrimitiveIterator.OfInt has a nextInt() method. They are also preconfigured to use the correct consumer for their type.

I thus deleted my IntIterator changed IntIterable to the following:

import java.util.*;
import java.util.function.*;
import java.util.stream.*;

public interface IntIterable {
  PrimitiveIterator.OfInt iterator();

  default void forEach(IntConsumer action) {
    Objects.requireNonNull(action);
    for (PrimitiveIterator.OfInt it = iterator(); it.hasNext(); )
      action.accept(it.next());
  }

  default Spliterator.OfInt spliterator() {
    return Spliterators.spliteratorUnknownSize(iterator(), 0);
  }
}

Note that the forEach() method remained the same, but the spliterator now uses the standard spliterator produced by my special type of iterator.

I then tried to apply this to my IntIterable, attempting to produce a PrimitiveIterable. It worked remarkably well:

import java.util.*;
import java.util.function.*;

public interface PrimitiveIterable<T, T_CONS> extends Iterable<T> {
  void forEach(T_CONS action);

  interface OfInt extends PrimitiveIterable<Integer, IntConsumer> {
    PrimitiveIterator.OfInt iterator();

    default Spliterator.OfInt spliterator() {
      return Spliterators.spliteratorUnknownSize(iterator(), 0);
    }

    default void forEach(IntConsumer action) {
      Objects.requireNonNull(action);
      for (PrimitiveIterator.OfInt it = iterator(); it.hasNext(); )
        action.accept(it.nextInt());
    }
  }

  interface OfLong extends PrimitiveIterable<Long, LongConsumer> {
    PrimitiveIterator.OfLong iterator();

    default Spliterator.OfLong spliterator() {
      return Spliterators.spliteratorUnknownSize(iterator(), 0);
    }

    default void forEach(LongConsumer action) {
      Objects.requireNonNull(action);
      for (PrimitiveIterator.OfLong it = iterator(); it.hasNext(); )
        action.accept(it.nextLong());
    }
  }

  interface OfDouble extends PrimitiveIterable<Double, DoubleConsumer> {
    PrimitiveIterator.OfDouble iterator();

    default Spliterator.OfDouble spliterator() {
      return Spliterators.spliteratorUnknownSize(iterator(), 0);
    }

    default void forEach(DoubleConsumer action) {
      Objects.requireNonNull(action);
      for (PrimitiveIterator.OfDouble it = iterator(); it.hasNext(); )
        action.accept(it.nextDouble());
    }
  }
}

Since our PrimitiveIterable.OfInt is also an Iterable<Integer>, we can use it in the enhanced for-in loop. In addition, Java should be smart enough to eliminate the object creation that happens due to the boxing and unboxing. However, I did not confirm that.

My final IntCollection looked like this:

import java.util.*;
import java.util.function.*;
import java.util.stream.*;

public interface IntCollection extends PrimitiveIterable.OfInt {
  int size();
  boolean isEmpty();
  boolean contains(int element);
  int[] toArray();
  boolean add(int element);
  boolean remove(int element);
  boolean containsAll(IntCollection c);
  boolean addAll(IntCollection c);
  boolean removeAll(IntCollection c);
  boolean retainAll(IntCollection c);
  void clear();

  default boolean removeIf(IntPredicate filter) {
    Objects.requireNonNull(filter);
    boolean removed = false;
    final PrimitiveIterator.OfInt each = iterator();
    while (each.hasNext()) {
      if (filter.test(each.nextInt())) {
        each.remove();
        removed = true;
      }
    }
    return removed;
  }

  default IntStream stream() {
    return StreamSupport.intStream(spliterator(), false);
  }

  default IntStream parallelStream() {
    return StreamSupport.intStream(spliterator(), true);
  }
}

I started trying to also "primitivize" this interface, but got stuck on some of the methods, so abandoned that. Also, if we create an IntQueue interface, we could return an OptionalInt from the poll() and peek() methods. This would have been a better design than the current Queue that returns null when the queue is empty.

Initially I was going to post the entire IntArrayDeque implementation, but it got a bit too long. Also, there are at least a dozen subtleties in the code that would need some explaining. Perhaps one day I will offer it as a code walk-through webinar. But now I need to get ready for my jconf-dev talk starting in 30 minutes :-)

Kind regards from Crete

Heinz

Comments

We are always happy to receive comments from our readers. Feel free to send me a comment via email or discuss the newsletter in our JavaSpecialists Slack Channel (Get an invite here)

Related Articles

Browse the Newsletter Archive