LinkedHashMap/LinkedHashSet enhancement: OrderedMap/OrderedSet

[Jason Mehrens]

Looks like It is intentional that unmodifiable queues are not present.  See: https://bugs.openjdk.java.net/browse/JDK-5030930.  The same logic would have been used for when Deque was added in the following release.

Jason

________________________________________
From: core-libs-dev <core-libs-dev-bounces at openjdk.java.net> on behalf of Stuart Marks <stuart.marks at oracle.com>
Sent: Tuesday, April 28, 2020 6:57 PM
To: Paul Sandoz
Cc: core-libs-dev
Subject: Re: LinkedHashMap/LinkedHashSet enhancement: OrderedMap/OrderedSet

Hi Paul,

I too hesitate about adding Ordered* interfaces. As I said previously, I don't
think they're very useful, and they do seem rather Queue- or Deque-like.

Indeed, Tagir was musing the other day on Twitter about a Deque view of
LinkedHashSet and possibly LinkedHashMap. I think that might be a more
worthwhile direction to pursue. Providing Deque views is more in keeping with
the current collections idioms than making LHS/LHM implement Deque directly.
This is rather like Map providing entry and key Set views and values Collection
views.

Note that these "view collections" provide live views of the backing collection
and that they aren't necessarily read-only. They support iteration in various
forms (e.g., streaming), and they can also permit removal (but not addition).
This is a bit odd but it can come in handy.

I'm thinking that the form of Iterable that supports access to first/last
elements, and iteration in either order, is in fact Deque itself. Deque already
supports descendingIterator(), which is a useful mechanism, but it's somewhat
inconvenient: you can't use it with enhanced-for, stream, or toArray. It would
be good to have a reversed-view Deque that flips the order of all the
operations. That avoids having to provide descendingStream(),
descendingToArray(), etc., and it adapts to anything that consumes an Iterable
or Collection.

(It occurs to me that we're missing a Collections.unmodifiableDeque wrapper.)

The LHS/LHM views, and various Deque wrappers, should all be pretty simple, with
the typical bunch of one-liner methods. (With the possible exception of
toArray(T[]).) Whether they are sufficiently useful, though, is still an open
question.

s'marks

On 4/28/20 10:59 AM, Paul Sandoz wrote:
> Hi Tagir,
>
> I am hesitant to add new interfaces specific to Set/Map for a non-indexed encounter order.
>
> The interface OrderedSet is tantalizingly queue-like, in fact rather close to the read-only part of Deque.  Did you consider the possibility of LinkedHashSet implementing Deque?
>
> I have not thought about this too deeply, but since LinkedHashMap is implemented as a doubly linked list it might be possible (as LinkedList implements Deque).
>
> If so we could also add the method:
>
>    LinkedHashSet<Map.Entry<K,V>> LinkedHashMap.entryLinkedSet()
>
> and thereby avoid the addition of any new interfaces, although it might require some refinement to the specification of Deque; a new notion of an unmodifiable queue, which I admit is a little odd, and as a result is probably not be a good idea.
>
> More generally I think the core abstraction is really a new form Iterable supporting access to first + last elements and reverse iteration (and possibly iteration starting from a containing element).
>
> Paul.
>
>> On Apr 25, 2020, at 9:51 AM, Tagir Valeev <amaembo at gmail.com> wrote:
>>
>> Hello!
>>
>> To me, it was always a pity that the internal structure of
>> LinkedHashMap allows doing more things easily, yet this functionality
>> is not exposed to the external clients, so if somebody really needs
>> such things they will need to waste memory/CPU to emulate them. The
>> functionality I'm speaking about includes:
>> - getting the last (i.e. most recently added/accessed) entry
>> - getting the descending iterator going from newest to oldest entries
>> - getting the iterator that starts at given existing entry
>>
>> It's easy to do such things with TreeMap and other NavigableMap
>> implementations. However, LinkedHashMap provides no additional visible
>> methods in addition to the Map interface (well, except
>> removeEldestEntry()). The same considerations apply to LinkedHashSet.
>>
>> So we can provide new interfaces j.u.OrderedMap and OrderedSet that
>> provide the additional functionality and make
>> LinkedHashMap/LinkedHashSet implement them. Aside from new
>> functionality, the interfaces will carry additional semantics: their
>> iteration order is always predictable and their spliterators return
>> DISTINCT|ORDERED characteristics, so some clients may require
>> OrderedMap/Set just to assert that they rely on predictable iteration
>> order. We can even make existing NavigableMap/Set extend
>> OrderedMap/Set because NavigableMap/Set are ordered. Some of
>> NavigableMap/Set methods will naturally fit the OrderedMap/Set
>> interfaces.
>>
>> I think I can devote my spare time to write the spec, implementation,
>> and tests for this enhancement, participate in the API design
>> discussions and do any other job necessary to make this improvement
>> happen. However, I'd like to know in advance whether such kind of
>> change would be met positively. What do you think? Is it possible to
>> do this or this improvement contradicts the OpenJDK goals and will
>> likely be rejected? Also, do I need to write a JEP for this?
>>
>> It's probably too early to discuss the exact API, but for more
>> specificity of my proposal, here's the quick draft:
>>
>> package java.util;
>>
>> public interface OrderedSet<E> extends Set<E> {
>>   // First or NSEE if empty
>>   E first() throws NoSuchElementException;
>>   // Last or NSEE if empty
>>   E last() throws NoSuchElementException;
>>   // Retrieve&remove first or null if empty
>>   E pollFirst();
>>   // Retrieve&remove last or null if empty
>>   E pollLast();
>>   // Iterator starting from element, or NSEE if not found
>>   Iterator<E> iteratorFrom(E fromElement) throws NoSuchElementException;
>>   // Descending
>>   Iterator<E> descendingIterator();
>>   // Descending iterator starting from element, or NSEE if not found
>>   Iterator<E> descendingIteratorFrom(E fromElement) throws
>> NoSuchElementException;
>>   // TBD: descendingSet()
>> }
>>
>> All the methods except iteratorFrom and descendingIteratorFrom are
>> already present in NavigableSet, so the spec will be mostly copied
>> from there. For iteratorFrom and descendingIteratorFrom it's easy to
>> provide a default implementation in NavigableSet. All methods can be
>> implemented easily in LinkedHashSet and LinkedHashMap::keySet
>>
>> package java.util;
>>
>> public interface OrderedMap<K, V> extends Map<K, V> {
>>   // First entry or null if empty
>>   Map.Entry<K,V> firstEntry();
>>   // Last entry or null if empty
>>   Map.Entry<K,V> lastEntry();
>>   // Retrieve&remove first entry or null if empty
>>   Map.Entry<K,V> pollFirstEntry();
>>   // Retrieve&remove last entry or null if empty
>>   Map.Entry<K,V> pollLastEntry();
>>   // First key or NSEE if empty
>>   K firstKey();
>>   // Last key or NSEE if empty
>>   K lastKey();
>>   // Ordered keySet()
>>   OrderedSet<K> orderedKeySet();
>>   // TBD: OrderedSet<K> descendingKeySet();
>>   // TBD: OrderedSet<Entry<K,V>> orderedEntrySet();
>> }
>>
>> All the methods except orderedKeySet() are already present in
>> NavigableMap, and the orderedKeySet() is just an alias for
>> navigableKeySet(). Also, all of them can be implemented easily in
>> LinkedHashMap.
>>
>> Any feedback is welcome.
>>
>> Thank you in advance,
>> Tagir Valeev.
>