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.
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
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)
We deliver relevant courses, by top Java developers to produce more resourceful and efficient programmers within their organisations.