Sequenced Collections

[Remi Forax]

I've read the draft of the JEP on sequenced collection, and i think the proposed design can be improved.
  https://bugs.openjdk.java.net/browse/JDK-8280836

I agree with the motivation, there is a need for an API to consider the element of a list, a sorted set and a linked hash set as an ordered sequence of elements with a simple way to access/add/remove the first/last element and also reverse the elements as view.

I disagree about the conclusion that we need to introduce 4 new interfaces for that matter.

Here are the reasons
1/ Usually an ordered collection is called a list. Introducing an interface SequencedCollection for something which is usually called a list will cause more harm than good. Or maybe we should rename LISP to SEQP :)

2/ There is already an interface List in Java, that represents an ordered sequence of elements, with LinkedList being the name of the the double linked list implementation. You can argue that there is a slight difference between the semantics of java.util.List and the proposed syntax of java.util.SequencedCollection, but given that people already have difficulties to understand basic data structure concepts, as a teacher i dread to have a discussion on those slight differences that are only true in Java.

If the collection API was not already existing, we may discuss about having the same interface java.util.List to both indexed collection and ordered collection, but that boat has sailed a long time ago.

So in first approach, we should refactor sorted set and linked hash set to directly implement java.util.List and all the proposed methods into java.util.List. But as you hint in the Risks and Assumptions section, this will cause regression due to inference and also we will have trouble with LinkedHashMap (see below).

3/ LinkedHashMap mixes 3 implementations in one class, some of these implementations does not conform to the semantics of SequencedMap.
- You can opt-out having the key sequentially ordered as defined by SequencedMap by using the constructor LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) and passing true as last parameter. 
- You can opt-out having the key sequentially ordered as defined by SequencedMap by overriding removeEldestEntry(), removing the first entry at the same time you add a new one.

Because all these reasons, i think we should move to another design, using delegation instead of inheritance, which for the collection framework means exposing new way to access/modify sorted set and linked hash set through java.util.List views.

The concept of views is not a new concept, it's used in Arrays.asList(), List.subList() or Map.keySet()/values()/entrySet() (and more). The idea is not that a sorted set is a list but that it provides a method to see it as a list. It solves our problem of compatibility by not adding super types to existing type and also the problem of the semantics of LinkedHashMap because a view keeps the semantics of the data structure it originated.

Here is the proposed new methods in List, SortedSet and SortedMap.

interface List<E> extends Collection<E> {
  // new methods
  void addFirst();
  void addLast();
  E getFirst();
  E getLast();
  E removeFirst();
  E removeLast();
  List<E> reversedList(); // or descendingList() ??
}

interface SortedSet<E> implements Set<E> {
  // new methods
  List<E> asList(); 
}

interface SortedMap<K,V> implements Map<K,V> {
  // new methods
  List<K> keyList();  // do not use covariant return type
  List<Map.Entry<K,V>> entryList();  // same
}

I believe this design is objectively better than the one proposed because as a user being able to use new interfaces is a slow process, the libraries/dependencies must be updated to take the new interfaces as parameter before the new types can be used. By contrast, the proposed design only enhance existing interfaces so people will enjoy the new methods directly when introduced.

Rémi