Creating Sequenced Collections, Sets, and Maps

Three interfaces introduced in JDK 21 represent collections with a defined encounter order. Each collection has a well-defined first element, second element, and so forth, up to the last element. They provide uniform APIs for accessing their first and last elements, and processing their elements in forward and reverse order.

Prior to JDK 21, the Java Collections Framework lacked a collection type that represented a sequence of elements with a defined encounter order. For example, List and Deque defined an encounter order but their common supertype, Collection, did not. Similarly, Set and subtypes such as HashSet do not define an encounter order, while subtypes such as SortedSet and LinkedHashSet do. Given the lack of a collection type with a defined encounter order, there is no uniform set of operations that respect encounter order. While there are operations that respect encounter order, they're not uniform.

An example of where a common order-significant operation is missing in the Collections Framework is to get the first element of a Deque and of a List. To get the first element of a Deque, you use the getFirst() method. However, to get the first element of a List, you use get(0).

Support for encounter order was spread across the type hierarchy, making it difficult to express certain useful concepts in APIs. Neither Collection nor List could describe a parameter or return value that had an encounter order. Collection was too general, relegating such constraints to the specification, and possibly leading to hard-to-debug errors. If an API wanted to receive a collection with a defined encounter order, then using List was too specific, because it excluded SortedSet and LinkedHashSet. A related problem was that view collections were often forced to downgrade to weaker semantics. For example, wrapping a LinkedHashSet with Collections::unmodifiableSet yields a Set that discards the information about encounter order.

Without interfaces to define them, operations related to encounter order were either inconsistent or missing. Many implementations support getting the first or last element, but each collection defines its own approach, and some are not obvious or are missing entirely.

Retrofitting the Collections Framework with Sequenced Interfaces

Beginning with JDK 21, JEP 431 introduces three Java Collections Framework interfaces for creating sequenced collections, sequenced sets, and sequenced maps:

These three interfaces provide the Java Collections Framework with a collection type that represents a sequence of elements with a defined encounter order and with a uniform set of operations applied across the collections. The interfaces fit into the collections type hierarchy as shown in the following diagram.

Figure 5-1 Collections Framework with Sequenced Interfaces

Description of "Figure 5-1 Collections Framework with Sequenced Interfaces"

The diagram shows the following adjustments that integrated the SequencedCollection, SequencedSet, and SequencedMap interfaces into the Java Collections Framework hierarchy of classes and interfaces:

List has SequencedCollection as its immediate superinterface.
Deque has SequencedCollection as its immediate superinterface.
LinkedHashSet implements SequencedSet.
SortedSet has SequencedSet as its immediate superinterface.
LinkedHashMap implements SequencedMap.
SortedMap has SequencedMap as its immediate superinterface.
Covariant overrides for the reversed() method are defined in the appropriate places. For example, List::reversed is overridden to return a value of type List rather than a value of type SequencedCollection.
Methods added to the Collections utility class create unmodifiable wrappers for three new types:
- Collections.unmodifiableSequencedCollection(sequencedCollection)
- Collections.unmodifiableSequencedSet(sequencedSet)
- Collections.unmodifiableSequencedMap(sequencedMap)

See JEP 431 for background information about the interfaces for sequenced collections, sequenced sets, and sequenced maps.

Topics

SequencedCollection

A SequencedCollection is a collection type added in JDK 21 that represents a sequence of elements with a defined encounter order.

A SequencedCollection has first and last elements with the elements between them having successors and predecessors. A SequencedCollection supports common operations at either end, and it supports processing the elements from first to last and from last to first (such as, forward and reverse).

interface SequencedCollection<E> extends Collection<E> {
    SequencedCollection<E> reversed();
    // methods promoted from Deque
    void addFirst(E);
    void addLast(E);
    E getFirst();
    E getLast();
    E removeFirst();
    E removeLast();
}

The reversed() method provides a reverse-ordered view of the original collection. Any modifications to the original collection are visible in the view.

The encounter order of elements in the returned view is the inverse of the encounter order of elements in this collection. The reverse ordering affects all order-sensitive operations, including those on the view collections of the returned view.

Changes to the underlying collection might or might not be visible in the reversed view, depending upon the implementation. If permitted, modifications to the view "write through" to the original collection. The reverse-ordered view enables all the different sequenced types to process elements in both directions, using all the usual iteration mechanisms:

Enhanced for loops
Explicit iterator() loops
forEach()
stream()
parallelStream()
toArray()

For example, obtaining a reverse-ordered stream from a LinkedHashSet was previously quite difficult; now it is simply:

linkedHashSet.reversed().stream()

Note:

The reversed() method is essentially a renamed NavigableSet::descendingSet, promoted to SequencedCollection.

The following methods of SequencedCollection are promoted from Deque. They support adding, getting, and removing elements at both ends:

void addFirst(E)
void addLast(E)
E getFirst()
E getLast()
E removeFirst()
E removeLast()
The add*(E) and remove*() methods are optional, primarily to support the case of unmodifiable collections. The get*() and remove*() methods throw a NoSuchElementException if the collection is empty. There are no definitions of equals() and hashCode() in SequencedCollection because its subinterfaces have conflicting definitions.

SequencedSet

A SequencedSet is both a SequencedCollection and a Set.

A SequencedSet can be thought of either as a Set that also has a well-defined encounter order, or as a SequencedCollection that also has unique elements.

interface SequencedSet<E> extends Set<E>, SequencedCollection<E> {
    SequencedSet<E> reversed();    // covariant override
}

This interface has the same requirements on the equals and hashCode methods as defined by Set.equals and Set.hashCode. A Set and a SequencedSet compare equals if and only if they have equal elements, irrespective of ordering.

SequencedSet defines the reversed() method, which provides a reverse-ordered view of this set. The only difference from the SequencedCollection.reversed method is that the return type of SequencedSet.reversed is SequencedSet.

In SequencedSet, the add*(E) methods of the SequencedCollection perform the following:

addFirst(E) - Adds an element as the first element of the collection.
addLast(E) - Adds an element as the last element of the collection.

The add*(E) methods of the SequencedCollection also have the following special-case behaviors for LinkedHashSet and SortedSet.

Special-case behaviors for LinkedHashSet:

The addFirst(E) and addLast(E) methods have special-case semantics for collections such as LinkedHashSet. LinkedHashSet repositions the entry if it is already present in the set. If the element is already present in the set then it is moved to the appropriate position. This remedies a long-standing deficiency in LinkedHashSet, namely the inability to reposition elements.

Special-case behaviors for SortedSet:

Collections such as SortedSet, which position elements by relative comparison, cannot support explicit-positioning operations such as the addFirst(E) and addLast(E) methods declared in the SequencedCollection superinterface. These methods throw an UnsupportedOperationException.

SequencedMap

A SequencedMap provides methods to add mappings, to retrieve mappings, and to remove mappings at either end of the map's encounter order. This interface also defines the reversed() method, which provides a reverse-ordered view of this map.

A SequencedMap has a well-defined encounter order that supports operations at both ends and is reversible. A map's reverse-ordered view is generally not serializable, even if the original map is serializable. The encounter order of a SequencedMap is similar to that of the elements of a SequencedCollection, but the ordering applies to mappings instead of individual elements:

interface SequencedMap<K,V> extends Map<K,V> {
    SequencedMap<K,V> reversed();
    SequencedSet<K> sequencedKeySet();
    SequencedCollection<V> sequencedValues();
    SequencedSet<Entry<K,V>> sequencedEntrySet();
    V putFirst(K, V);
    V putLast(K, V);
    // methods promoted from NavigableMap
    Entry<K, V> firstEntry();
    Entry<K, V> lastEntry();
    Entry<K, V> pollFirstEntry();
    Entry<K, V> pollLastEntry();
}

The sequencedKeySet(), sequencedValues(), and sequencedEntrySet()methods are exactly analogous to the keySet(), values(), and entrySet() methods of Map interface. All of these methods return views of the underlying collection; where modifications to the view are visible in the underlying collection and vice versa. The encounter order of these views exactly corresponds to the encounter order of the underlying map.

The difference between the SequencedMap interface methods and the methods of Map is that the sequenced*() methods have a sequenced return type:

In SequencedSet<K> sequencedKeySet(), the implemention returns a SequencedSet view of the map's keySet and behaves as follows:
- add and addAll methods throw UnsupportedOperationException.
- reversed method returns the sequencedKeySet view of the reversed view of the map.
- Its other methods call the corresponding methods of the keySet view of the map.
In SequencedCollection<V> sequencedValues(), the implemention returns a SequencedCollection view of the map's values collection and behaves as follows:
- add and addAll methods throw UnsupportedOperationException.
- reversed method returns the sequencedValues view of the reversed view of the map.
- equals and hashCode methods are inherited from Object.
- Its other methods call the corresponding methods of the values view of the map.
In SequencedSet<Entry<K,V>> sequencedEntrySet(), the implemention returns a SequencedSet view of the map's entrySetand behaves as follows:
- add and addAll methods throw UnsupportedOperationException.
- reversed method returns the sequencedEntrySet view of the reversed view of the map.
- Its other methods call the corresponding methods of the entrySet view of the map.

The put*(K, V) methods have special-case semantics, similar to the corresponding add*(E) methods of SequencedSet:

For maps such as LinkedHashMap, they have the additional effect of repositioning the entry if it is already present in the map.
For maps such as SortedMap, these methods throw UnsupportedOperationException.

The following methods of SequencedMap are promoted from NavigableMap. They support getting and removing entries at both ends:

Entry<K, V> firstEntry()
Entry<K, V> lastEntry()
Entry<K, V> pollFirstEntry()
Entry<K, V> pollLastEntry()

The methods firstEntry(), lastEntry(), pollFirstEntry(), and pollLastEntry() return Map.Entry instances that represent snapshots of mappings as of the time of the call. They do not support mutation of the underlying map via the optional setValue method.

Demonstrating ArrayList and LinkedHashMap Reversed Views

Several scenarios are provided of using the sequenced interfaces in the Collections Framework.

Topics

Demonstrating a Reverse-Ordered View of a Collection

The following example demonstrates how the reversed() method of the sequenced interfaces produces a reverse-ordered view of a collection, how modifications to a reversed view affect the original collection, and how modifications to the original collection are visible in the reversed view.

The reversed view is "live" and not a snapshot of a collection. This characteristic is illustrated in the following examples by using an ArrayList and its reversed view.

Note:

Unessential jshell output is not included in the following example code.

Start a jshell session and use the ArrayList class to create a list of String objects.

jshell> var list = new ArrayList<>(Arrays.asList("a", "b", "c", "d", "e"))
list ==> [a, b, c, d, e]

Next, use the reversed() method to produce a reverse-ordered view of the collection.

jshell> var rev = list.reversed()
rev ==> [e, d, c, b, a]

When you modify the reversed view, it affects the original collection. Add f as an entry to the reverse-ordered view and then verify that it is added to the original collection.

jshell> rev.add(1, "f")
jshell> rev
rev ==> [e, f, d, c, b, a]
jshell> list
list ==> [a, b, c, d, f, e]

When you modify the original collection, your modifications are visible in the reversed view. Set the element at index 2 to X, verify it is added to the collection, and then produce a reverse-ordered view of the modified collection.

jshell> list.set(2, "X")
jshell> list
list ==> [a, b, X, d, f, e]
jshell> rev
rev ==> [e, f, d, X, b, a]

Demonstrating Composition of LinkedHashMap Views

In addition to using ArrayList, a reversed() view can also be composed of other views such as List.subList().reversed() or SequencedMap.sequencedKeySet().reversed() and SequencedMap.reversed().sequencedKeySet().

The SequencedMap.sequencedKeySet().reversed() and SequencedMap.reversed().sequencedKeySet() views are functionally equivalent and are illustrated by using the LinkedHashMap class in the following example code.

Start a jshell session and use the LinkedHashMap class to create a map of String objects.

jshell> var map = new LinkedHashMap<String, Integer>()
jshell> map.put("a", 1)
jshell> map.put("b", 2)
jshell> map.put("c", 3)
jshell> map.put("d", 4)
jshell> map.put("e", 5)
map ==> {a=1, b=2, c=3, d=4, e=5}

Next, use the reversed() method to produce a reverse-ordered view of the keySet view of the original collection.

jshell> map.sequencedKeySet().reversed()
$17 ==> [e, d, c, b, a]

Demonstrating SequencedMap Does Not Support Mutation of the Underlying Map

This demonstration illustrates the final statement in the SequencedMap section that firstEntry(), lastEntry(), pollFirstEntry(), and pollLastEntry() methods do not support mutation of the underlying map through use of the optional setValue method.

Attempting to change an entry in the underlying map by using setValue() with these methods will throw an UnsupportedOperationException. This is in contrast to changing a map entry obtained by iterating the entrySet. If you call seqmap.entrySet().iterator().next() to return a map entry and then call setValue() on the entry, it will modify the original map.

Open a jshell session and use the map produced in Demonstrating Composition of LinkedHashMap Views.

Call map.entrySet().iterator().next() to return the first map entry.

jshell> var entry = map.entrySet().iterator().next()
entry ==> a=1

Use setValue() to change the value of the map entry to 77. The entry was obtained by iterating the entrySet so it can be modified in the original map. Verify that the value in map changed to 77.

jshell> entry.setValue(77)
$19 ==> 1
jshell> map
map ==> {a=77, b=2, c=3, d=4, e=5}

Note:

The ability to call setValue() on the entry returned by the iterator is not a new behavior introduced in JDK 21.

Use setValue() to try and change the map entry to 999. Because the map entry was not obtained by iterating with entrySet, it throws an UnsupportedOperationException.

jshell> entry = map.firstEntry()
entry ==> a=77
jshell> entry.setValue(999)
 | Exception java.lang.UnsupportedOperationException: not supported
 | at NullableKeyValueHolder.setValue (NullableKeyValueHolder.java:126)
 | at (#22:1)