Summary

Add SequencedCollection, SequencedSet, and SequencedMap interfaces and retrofit them into the collection type hierarchy.

Problem

Several different types and implementations in the collections framework embody the notion of having an order or sequence, and some of them support reverse iteration or a reversed view. However, there is no single type in the framework that unifies the concept of a collection or map being arranged in a sequence. Furthermore, while some collections support reverse iteration or a reversed view, the way they do so is inconsistent. Some collections (such as LinkedHashSet) that are logically a sequence support neither reversibility nor operations at either end. Other collections can support operations at either end, but their support is either inconsistent or inconvenient.

Solution

Add interfaces SequencedCollection, SequencedSet, and SequencedMap to the collections type hierarchy. Introduce a reversed method to these interfaces that provides a reversed view of the collection. Introduce covariant overrides of reversed into sub-interfaces of SequencedCollection. Add methods to support add, get, and remove operations at either end of a sequenced collection or map.

Note: earlier versions of this proposal included covariant overrides for Map view methods keySet, values, and entrySet to have SequencedX return types. This proposal no longer includes that change. These view methods are left as-is, and new methods to return sequenced views are added instead. See the compatibility report for analysis and rationale.

A summary of the new interfaces is given below. In addition, several existing interfaces are adjusted to have these new interfaces as their supertypes, various covariant overrides of the reversed method are provided, and unmodifiable sequenced list, set, and map views are provided in the Collections utility class. See the specdiff for full details.

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

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

interface SequencedMap<K,V> extends Map<K,V> {
    // new methods
    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();
}

Specification

See attached specdiff.

Discussion

This proposes fairly major surgery on the collections framework, and as such, it runs the risk of source and binary incompatibilities. Incompatibilities can occur in the following areas:

(1) Name or return value clash by introduction of new methods "reversed" and add/get/remove x First/Last into a widely implemented interface hierarchy.

(2) Covariant overrides of reversed(). I don't think this is likely to be an issue (assuming there are no name clashes with "reversed" itself), as introducing covariant overrides for newly introduced methods should be fairly safe.

(3) (NOTE: this aspect of the design has been modified.) Covariant overrides of view methods of SequencedMap, inherited by LinkedHashMap: keySet, entrySet, and values. If subclasses overrode any of these methods, either using the current return type or a covariant override of their choice, this could lead to incompatibilities. (Indeed, the incompatibilities were such that I've moved away from this design and have not added covariant overrides. I've added new methods alongside instead. See the compatibility report for full details.)

(4) New methods on SequencedMap: putFirst and putLast. There is the possibility of existing subclasses defining these methods, leading to a conflict.

(5) Source incompatibilities with type inference. These are mainly related to the possibility of inference of new types that might clash with assumptions made by existing code written. (These don't seem very significant to me though.)

(6) Conflicting default methods, in general. Several new default methods are being added here. If there's no conflict, an existing method might end up overriding accidentally, which is a concern. However, a class might inherit from some other method with a conflicting default method, which would be binary and source incompatible.

(7) Conflicting default methods, in particular. The default methods here are mostly unlikely to conflict with each other, as few collections implementations inherit from more than one collection family. Indeed, this is usually illegal, as it is semantically invalid for a class to implement, say, both List and Set. However, some collections interfaces are compatible, such as List and Deque. Indeed, LinkedList implements both. (So does an internal class sun.awt.util.IdentityLinkedList.) For these classes, an override must be provided that resolves the conflict. This is mostly a source compatibility issue. It can occur with classes that implement both List and Deque. It can also occur if application code were to create an "off-label" subclass, such as one that extends LinkedHashSet and also implements List. (This is semantically invalid but it's possible that people do it anyway.)

These issues are addressed in the attached compatibility report.