LinkedHashMap/LinkedHashSet enhancement: OrderedMap/OrderedSet

[Paul Sandoz]

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.