Netopyr GmbH

This is the first part in a series of articles about JavaFX sequences. It will focus on the basic concepts of the implementation and explain some of the possibilities how to create JavaFX sequences in Java programs.

The first and foremost concept one needs to know in order to understand the implementation of JavaFX sequences is, that they are immutable. This is surprising, considering how often sequences are changed. But immutable objects have a number of advantages. If you want to know more about them, I recommend this article. After reading the article, it would have been a bigger surprise, if Brian, the author, had not implemented sequences as immutable objects.

But inspite the many advantages of immutable objects, it is not obvious to come up with an implementation for a general purpose data-structure like JavaFX sequences. In this article I will provide an overview on how sequences are implemented. This will not only give a better understanding of the internals of JavaFX, but it may also serve as a good example, if one wants to design an immutable data-structure oneself.

Overview

When a sequence is changed, a new sequence-object needs to be created. The trick is not to copy the elements of the original sequence to the new object, but to store a reference together with an implementation of the change. For example if two sequences need to be concatenated, the new sequence stores references to the original sequences and resolves requests by calculating the result of the concatenation on the fly.

The highlevel-design of sequences is as follows. An interface defines the general behavior of a sequence. The implementations can be divided into two categories. There are the atomic sequence-types, which build the foundation of any sequence, and the derived sequences-types, which take one (or more) sequences and implement exactly one operation on them.

There are some more classes which are essential when dealing with sequences. On of them is the class Sequences, which is mentioned a couple of times in this article. Among others, it contains a number of useful methods to create and change sequences. All of these classes are located in the package com.sun.javafx.runtime.sequence, which can be found in the openjfx-repository and which are part of the JavaFX runtime.

Atomic Sequence Types

Atomic sequence types do not refer to any other sequence, but hold all information themselves. Every sequence is based on one or more atomic sequence.

EmptySequence

An empty sequence contains no element, but nevertheless it stores the class of the elements. That’s because an empty sequence of class A-elements is different from an empty sequence of class B-elements. The implementation of empty sequences takes advantage of the fact that they are immutable to save memory. For every class only one empty sequence gets created. Any subsequent call of the factory-method returns a reference to that sequence.

An empty sequence can be created in Java code by calling Sequences.emptySequence() with the class of the sequence-elements as parameter.

SingletonSequence

The name of this class might be misleading, because it has nothing to do with the Singleton pattern, as one might associate. A SingletonSequence is simply a sequence, which contains only one element.

A sequence with exactly one element can be created in Java code by calling Sequences.singleton() with the class of the sequence-elements and the single element as parameter.

ArraySequence

An ArraySequence is the most flexible atomic sequence type. Its values are backed by an array, thus allowing an arbitrary sequence of elements. But remember, null-values are not allowed in a sequence. This is certainly true for an ArraySequence as well, therefore the underlying array is not allowed to contain null-values.

There are a number of factory-methods to create arbitrary atomic sequences, mainly Sequences.make() with different parameter-sets (e.g. varargs, List) and Sequences.fromArray() to create sequences directly from arrays.

IntRangeSequence / NumberRangeSequence

The classes IntRangeSequence and NumberRangeSequence are used to represent number intervals. They are defined by a start-value, the size of the sequence and a step-size. The content of these sequences are calculated on request.

Range-sequences can be created with Sequences.range() or Sequences.rangeExclusive(). Parameters for these factory-methods are the lower and upper bounds as well as the optional step-size. The type of the created sequence depends on the type of the input-parameters. If all parameters are integers, the result is an IntRangeSequence, and in all other cases the result is a NumberRangeSequence. The method range() creates a sequence with the upper bound included, while rangeExclusive creates a sequence without the upper bound.

Derived Sequence Types

A derived sequence is created, when an existing sequence is altered. A derived sequence stores a reference to the original sequence(s) and implements methods to calculate the changes on-the-fly. The referenced sequences are accessed by the interface Sequence, thus they can be any type of sequence, atomic or derived.

CompositeSequence

A CompositeSequence implements the concatenation of an arbitrary number of sequences. To get an element of the concatenated sequence, first the right subsequence needs to be selected and after that the element can be requested from that subsequence. Figure 1a) shows this process for a sequence which is the concatenation of three subsequences. First the CompositeSequence determines the second sequence as the one containing position x and after that the element is requested from that sequence.

Sequences can be concatenated in Java code by calling the method Sequences.concatenate().

SubSequence

A SubSequence is a part of a sequence. The implementation is straightforward, the bounds are stored and used to get the elements of the subsequence. Figure 1b) shows how the elements of a SubSequence are requested from the underlying sequence.

The subsequence of a sequence can be evaluated in Java code by calling Sequences.subsequence() or by calling the method subsequence() of the sequence directly.

ReplacementSequence

A ReplacementSequence replaces one element of the underlying sequence. The position and the value of the new element are stored. The getter compares the requested position with the position of that element and returns the stored value, if they match. Otherwise the element is requested from the underlying sequence.

A ReplacementSequence is usually not created directly but it is heavily used by the SequenceMutator, which I will cover in another article of this series.

ReverseSequence

A ReverseSequence is the reversal of a sequence. The elements are not copied in reverse order to create the new sequence, but instead the getter of a ReverseSequence recalculates the position to request the elements from the original sequence. So when the first element of the ReverseSequence is requested, the last element of the original sequence is returned, if the second element is requested, the last but one is returned etc. Figure 1c) shows the reversal of the sequence by recalculating positions.

The reversal of a sequence can be calculated in Java code by calling Sequences.reverse() or by calling the method reverse() of the sequence directly.

UpcastSequence

A sequence can be casted to a sequence, which elements are supertypes of the original sequence’s elements. An UpcastSequence is taking care of that by upcasting the requested elements in the getter.

Upcasting of a sequence can be achieved in Java code by calling Sequences.upcast().

FilterSequence

A FilterSequence applies a filter in form of a bitfield on a sequence. The bitfield defines which elements are visible and which ones are ignored. To simplify the usage, an array to store the positions of the visible elements is created during initialization. Figure 1d) shows an example. The first and third elements are visible, while the second element is not. Therefore the created array contains the first and third posit
ion, omitting the second one.

To filter a sequence in Java code the method Sequences.filter() can be used.

Conclusion

This article, presented the basic concepts of the implementation for JavaFX sequences. The foundation of a sequence are always one or more atomic sequences. Since sequences are implemented immutable, derived sequences were introduced to implement changes on sequences. A derived sequence implements exactly one operation on one or more sequences.

If a sequence is altered again and again, a tree of derived sequences
is created to represent those changes. As one can imagine, this can
easily result in inefficient structures, therefore optimizations are going to be introduced to increase performance. This is an ongoing process and currently under discussion, therefore I did not cover it in this article.

The next article will cover some more possibilities to create and alter sequences in Java code by introducing the classes SequenceBuilder and SequenceMutator.