Hi Rémi,
I see that you're trying to reduce the number of interfaces introduced by unifying
things around an existing interface, List. Yes, it's true that List is an ordered
collection. However, your analysis conveniently omits other facts about List that
make it unsuitable as a general "ordered collection" interface. Specifically:
1) List supports element access by int index; and
2) List is externally ordered. That is, its ordering is determined by a succession
of API calls, irrespective of element values. This is in contrast to SortedSet et al
which are internally ordered, in that the ordering is determined by the element values.
The problem with indexed element access is that it creates a bunch of hidden
performance pitfalls for any data structure where element access is other than O(1).
So get(i) degrades to O(n), binarySearch degrades from O(log n) to O(n). (This is in
the sequential implementation; the random access implementation degrades to O(n log
n)). Apparently innocuous indexed for-loops degrade to quadratic. This is one of the
reasons why LinkedList is a bad List implementation.
If we refactor LinkedHashSet to implement List, we basically have created another
situation just like LinkedList. That's a step in the wrong direction.
Turning to internal ordering (SortedSet): it's fundamentally incompatible with
List's external ordering. List has a lot of positional mutation operations such as
add(i, obj); after this call, you expect obj to appear at position i. That can't
work with a SortedSet.
There is implicit positioning semantics in other methods that don't have index
arguments. For example, replaceAll replaces each element of a List with the result
of calling a function on that element. Crucially, the function result goes into the
same location as the original element. That to cannot work with SortedSet.
Well, we can try to deal with these issues somehow, like making certain methods
throw UnsupportedOperationException, or by relaxing the semantics of the methods so
that they no longer have the same element positioning semantics. Either of these
approaches contorts the List interface to such an extent that it's no longer a List.
So, no, it's not useful or effective to try to make List be the common "ordered
collection" interface.
s'marks
On 2/10/22 3:14 AM, Remi Forax wrote:
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
